17283659198

Committed 28 Aug 2025 02:05AM UTC coverage: 93.75% (+1.7%) from 92.046%

Build # 17283659198

Build Type

push

github

Committed by

web-flow

Commit Message

Migrate from jest to vitest and parallelize tests (#90)

Run Details

1121 of 1250 branches covered (89.68%)

Branch coverage included in aggregate %.

388 of 393 new or added lines in 63 files covered. (98.73%)

57 existing lines in 13 files now uncovered.

6364 of 6734 relevant lines covered (94.51%)

51774.21 hits per line

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

91.6

/src/parentHash.ts

import { Decoder, mapDecoders } from "./codec/tlsDecoder.js"
import { contramapEncoders, Encoder } from "./codec/tlsEncoder.js"
import { decodeVarLenData, encodeVarLenData } 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 encodeParentHashInput: Encoder<ParentHashInput> = contramapEncoders(
  [encodeVarLenData, encodeVarLenData, encodeVarLenData],
  (i) => [i.encryptionKey, i.parentHash, i.originalSiblingTreeHash] as const,
)

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(encodeParentHashInput(input)), parentNodeIndex]
}

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

LukaJCB / ts-mls / 17283659198

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