20081738515

Committed 09 Dec 2025 11:22PM UTC coverage: 96.422% (-0.001%) from 96.423%

Build # 20081738515

Build Type

Pull #171

github

Committed by

web-flow

Commit Message

Merge 0be266886 into 5e1453cbc

Pull Request Pull Request #171: Reduce tree copies and iterations

Coverage Stats

1206 of 1349 branches covered (89.4%)

Branch coverage included in aggregate %.

29 of 29 new or added lines in 3 files covered. (100.0%)

12 existing lines in 2 files now uncovered.

6825 of 6980 relevant lines covered (97.78%)

45343.14 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.98

/src/parentHash.ts

import { Decoder, mapDecoders } from "./codec/tlsDecoder.js"
import { contramapBufferEncoders, BufferEncoder, encode, Encoder } from "./codec/tlsEncoder.js"
import { decodeVarLenData, varLenDataEncoder } from "./codec/variableLength.js"
import { Hash } from "./crypto/hash.js"
import { InternalError } from "./mlsError.js"
import { findFirstNonBlankAncestor, Node, RatchetTree, removeLeaves } from "./ratchetTree.js"
import { treeHash } from "./treeHash.js"
import {
  isLeaf,
  LeafIndex,
  leafToNodeIndex,
  leafWidth,
  left,
  NodeIndex,
  right,
  root,
  toLeafIndex,
  toNodeIndex,
} from "./treemath.js"

import { constantTimeEqual } from "./util/constantTimeCompare.js"

export interface ParentHashInput {
  encryptionKey: Uint8Array
  parentHash: Uint8Array
  originalSiblingTreeHash: Uint8Array
}

export const parentHashInputEncoder: BufferEncoder<ParentHashInput> = contramapBufferEncoders(
  [varLenDataEncoder, varLenDataEncoder, varLenDataEncoder],
  (i) => [i.encryptionKey, i.parentHash, i.originalSiblingTreeHash] as const,
)

export const encodeParentHashInput: Encoder<ParentHashInput> = encode(parentHashInputEncoder)

export const decodeParentHashInput: Decoder<ParentHashInput> = mapDecoders(
  [decodeVarLenData, decodeVarLenData, decodeVarLenData],
  (encryptionKey, parentHash, originalSiblingTreeHash) => ({
    encryptionKey,
    parentHash,
    originalSiblingTreeHash,
  }),
)

function validateParentHashCoverage(parentIndices: number[], coverage: Record<number, number>): boolean {
  for (const index of parentIndices) {
    if ((coverage[index] ?? 0) !== 1) {
      return false
    }
  }
  return true
}

export async function verifyParentHashes(tree: RatchetTree, h: Hash): Promise<boolean> {
  const parentNodes = tree.reduce((acc, cur, index) => {
    if (cur !== undefined && cur.nodeType === "parent") {
      return [...acc, index]
    } else return acc
  }, [] as number[])

  if (parentNodes.length === 0) return true

  const coverage = await parentHashCoverage(tree, h)

  return validateParentHashCoverage(parentNodes, coverage)
}

/**
 * Traverse tree from bottom up, verifying that all non-blank parent nodes are covered by exactly one chain
 */
function parentHashCoverage(tree: RatchetTree, h: Hash): Promise<Record<number, number>> {
  const leaves = tree.filter((_v, i) => isLeaf(toNodeIndex(i)))
  return leaves.reduce(
    async (acc, leafNode, leafIndex) => {
      if (leafNode === undefined) return acc

      let currentIndex = leafToNodeIndex(toLeafIndex(leafIndex))
      let updated = { ...(await acc) }

      const rootIndex = root(leafWidth(tree.length))

      while (currentIndex !== rootIndex) {
        const currentNode = tree[currentIndex]

        // skip blank nodes
        if (currentNode === undefined) {
          continue
        }

        // parentHashNodeIndex is the node index where the nearest non blank ancestor was
        const [parentHash, parentHashNodeIndex] = await calculateParentHash(tree, currentIndex, h)

        if (parentHashNodeIndex === undefined) {
          throw new InternalError("Reached root before completing parent hash coeverage")
        }

        const expectedParentHash = getParentHash(currentNode)

        if (expectedParentHash !== undefined && constantTimeEqual(parentHash, expectedParentHash)) {
          const newCount = (updated[parentHashNodeIndex] ?? 0) + 1
          updated = { ...updated, [parentHashNodeIndex]: newCount }
        } else {
          // skip to next leaf
          break
        }

        currentIndex = parentHashNodeIndex
      }

      return updated
    },
    Promise.resolve({} as Record<number, number>),
  )
}

function getParentHash(node: Node): Uint8Array | undefined {
  if (node.nodeType === "parent") return node.parent.parentHash
  else if (node.leaf.leafNodeSource === "commit") return node.leaf.parentHash
}

/**
 * Calculcates parent hash for a given node or leaf and returns the node index of the parent or undefined if the given node is the root node.
 */
export async function calculateParentHash(
  tree: RatchetTree,
  nodeIndex: NodeIndex,
  h: Hash,
): Promise<[Uint8Array, NodeIndex | undefined]> {
  const rootIndex = root(leafWidth(tree.length))
  if (nodeIndex === rootIndex) {
    return [new Uint8Array(), undefined]
  }

  const parentNodeIndex = findFirstNonBlankAncestor(tree, nodeIndex)

  const parentNode = tree[parentNodeIndex]

  if (parentNodeIndex === rootIndex && parentNode === undefined) {
    return [new Uint8Array(), parentNodeIndex]
  }

  const siblingIndex = nodeIndex < parentNodeIndex ? right(parentNodeIndex) : left(parentNodeIndex)

  if (parentNode === undefined || parentNode.nodeType === "leaf")
    throw new InternalError("Expected non-blank parent Node")

  const removedUnmerged = removeLeaves(tree, parentNode.parent.unmergedLeaves as LeafIndex[])

  const originalSiblingTreeHash = await treeHash(removedUnmerged, siblingIndex, h)

  const input = {
    encryptionKey: parentNode.parent.hpkePublicKey,
    parentHash: parentNode.parent.parentHash,
    originalSiblingTreeHash,
  }

  return [await h.digest(encode(parentHashInputEncoder)(input)), parentNodeIndex]
}

1	import { Decoder, mapDecoders } from "./codec/tlsDecoder.js"	1✔
2	import { contramapBufferEncoders, BufferEncoder, encode, Encoder } from "./codec/tlsEncoder.js"	1✔
3	import { decodeVarLenData, varLenDataEncoder } from "./codec/variableLength.js"	1✔
4	import { Hash } from "./crypto/hash.js"
5	import { InternalError } from "./mlsError.js"	1✔
6	import { findFirstNonBlankAncestor, Node, RatchetTree, removeLeaves } from "./ratchetTree.js"	1✔
7	import { treeHash } from "./treeHash.js"	1✔
8	import {	1✔
9	isLeaf,
10	LeafIndex,
11	leafToNodeIndex,
12	leafWidth,
13	left,
14	NodeIndex,
15	right,
16	root,
17	toLeafIndex,
18	toNodeIndex,
19	} from "./treemath.js"
20
21	import { constantTimeEqual } from "./util/constantTimeCompare.js"	1✔
22
23	export interface ParentHashInput {
24	encryptionKey: Uint8Array
25	parentHash: Uint8Array
26	originalSiblingTreeHash: Uint8Array
27	}
28
29	export const parentHashInputEncoder: BufferEncoder<ParentHashInput> = contramapBufferEncoders(	1✔
30	[varLenDataEncoder, varLenDataEncoder, varLenDataEncoder],	1✔
31	(i) => [i.encryptionKey, i.parentHash, i.originalSiblingTreeHash] as const,	1✔
32	)	1✔
33
34	export const encodeParentHashInput: Encoder<ParentHashInput> = encode(parentHashInputEncoder)	1✔
35
36	export const decodeParentHashInput: Decoder<ParentHashInput> = mapDecoders(	1✔
37	[decodeVarLenData, decodeVarLenData, decodeVarLenData],	1✔
38	(encryptionKey, parentHash, originalSiblingTreeHash) => ({	1✔
39	encryptionKey,	1✔
40	parentHash,	1✔
41	originalSiblingTreeHash,	1✔
42	}),	1✔
43	)	1✔
44
45	function validateParentHashCoverage(parentIndices: number[], coverage: Record<number, number>): boolean {	249✔
46	for (const index of parentIndices) {	249✔
47	if ((coverage[index] ?? 0) !== 1) {	1,505✔
48	return false	19✔
49	}	19✔
50	}	1,505✔
51	return true	230✔
52	}	230✔
53
54	export async function verifyParentHashes(tree: RatchetTree, h: Hash): Promise<boolean> {	1,249✔
55	const parentNodes = tree.reduce((acc, cur, index) => {	1,249✔
56	if (cur !== undefined && cur.nodeType === "parent") {	11,659✔
57	return [...acc, index]	1,505✔
58	} else return acc	11,659✔
59	}, [] as number[])	1,249✔
60
61	if (parentNodes.length === 0) return true	1,249✔
62
63	const coverage = await parentHashCoverage(tree, h)	249✔
64
65	return validateParentHashCoverage(parentNodes, coverage)	249✔
66	}	249✔
67
68	/**
69	* Traverse tree from bottom up, verifying that all non-blank parent nodes are covered by exactly one chain
70	*/
71	function parentHashCoverage(tree: RatchetTree, h: Hash): Promise<Record<number, number>> {	249✔
72	const leaves = tree.filter((_v, i) => isLeaf(toNodeIndex(i)))	249✔
73	return leaves.reduce(	249✔
74	async (acc, leafNode, leafIndex) => {	249✔
75	if (leafNode === undefined) return acc	3,066✔
76
77	let currentIndex = leafToNodeIndex(toLeafIndex(leafIndex))	2,498✔
78	let updated = { ...(await acc) }	2,498✔
79
80	const rootIndex = root(leafWidth(tree.length))	2,498✔
81
82	while (currentIndex !== rootIndex) {	3,066✔
83	const currentNode = tree[currentIndex]	3,754✔
84
85	// skip blank nodes
86	if (currentNode === undefined) {	3,754!
UNCOV 87	continue	×
UNCOV 88	}	×
89
90	// parentHashNodeIndex is the node index where the nearest non blank ancestor was
91	const [parentHash, parentHashNodeIndex] = await calculateParentHash(tree, currentIndex, h)	3,754✔
92
93	if (parentHashNodeIndex === undefined) {	3,754!
UNCOV 94	throw new InternalError("Reached root before completing parent hash coeverage")	×
UNCOV 95	}	×
96
97	const expectedParentHash = getParentHash(currentNode)	3,754✔
98
99	if (expectedParentHash !== undefined && constantTimeEqual(parentHash, expectedParentHash)) {	3,754✔
100	const newCount = (updated[parentHashNodeIndex] ?? 0) + 1	1,486✔
101	updated = { ...updated, [parentHashNodeIndex]: newCount }	1,486✔
102	} else {	3,754✔
103	// skip to next leaf
104	break	2,268✔
105	}	2,268✔
106
107	currentIndex = parentHashNodeIndex	1,486✔
108	}	1,486✔
109
110	return updated	2,498✔
111	},	3,066✔
112	Promise.resolve({} as Record<number, number>),	249✔
113	)	249✔
114	}	249✔
115
116	function getParentHash(node: Node): Uint8Array \| undefined {	3,754✔
117	if (node.nodeType === "parent") return node.parent.parentHash	3,754✔
118	else if (node.leaf.leafNodeSource === "commit") return node.leaf.parentHash	2,498✔
119	}	3,754✔
120
121	/**
122	* Calculcates parent hash for a given node or leaf and returns the node index of the parent or undefined if the given node is the root node.
123	*/
124	export async function calculateParentHash(	16,083✔
125	tree: RatchetTree,	16,083✔
126	nodeIndex: NodeIndex,	16,083✔
127	h: Hash,	16,083✔
128	): Promise<[Uint8Array, NodeIndex \| undefined]> {	16,083✔
129	const rootIndex = root(leafWidth(tree.length))	16,083✔
130	if (nodeIndex === rootIndex) {	16,083✔
131	return [new Uint8Array(), undefined]	3,542✔
132	}	3,542✔
133
134	const parentNodeIndex = findFirstNonBlankAncestor(tree, nodeIndex)	12,541✔
135
136	const parentNode = tree[parentNodeIndex]	12,541✔
137
138	if (parentNodeIndex === rootIndex && parentNode === undefined) {	16,083✔
UNCOV 139	return [new Uint8Array(), parentNodeIndex]	×
UNCOV 140	}	✔
141
142	const siblingIndex = nodeIndex < parentNodeIndex ? right(parentNodeIndex) : left(parentNodeIndex)	16,083✔
143
144	if (parentNode === undefined \|\| parentNode.nodeType === "leaf")	16,083✔
145	throw new InternalError("Expected non-blank parent Node")	16,083✔
146
147	const removedUnmerged = removeLeaves(tree, parentNode.parent.unmergedLeaves as LeafIndex[])	12,541✔
148
149	const originalSiblingTreeHash = await treeHash(removedUnmerged, siblingIndex, h)	12,541✔
150
151	const input = {	12,541✔
152	encryptionKey: parentNode.parent.hpkePublicKey,	12,541✔
153	parentHash: parentNode.parent.parentHash,	12,541✔
154	originalSiblingTreeHash,	12,541✔
155	}	12,541✔
156
157	return [await h.digest(encode(parentHashInputEncoder)(input)), parentNodeIndex]	12,541✔
158	}	12,541✔

LukaJCB / ts-mls / 20081738515

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous