20887934276

Committed 11 Jan 2026 02:12AM UTC coverage: 95.727% (+0.06%) from 95.665%

Build # 20887934276

Build Type

push

github

Committed by

LukaJCB

Commit Message

Update to vitest v4

Run Details

409 of 417 branches covered (98.08%)

Branch coverage included in aggregate %.

2369 of 2485 relevant lines covered (95.33%)

80736.06 hits per line

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

93.75

/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, leafWidth, left, NodeIndex, right, root, 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>> {
  return tree.reduce(
    async (acc, node, nodeIndex) => {
      let currentIndex = toNodeIndex(nodeIndex)
      if (!isLeaf(currentIndex) || node === undefined) return acc

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

LukaJCB / ts-mls / 20887934276

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