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

Run Details

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

94.19

/src/updatePath.ts

import { Decoder, mapDecoders } from "./codec/tlsDecoder.js"
import { contramapBufferEncoders, BufferEncoder, encode, Encoder } from "./codec/tlsEncoder.js"
import { decodeVarLenData, decodeVarLenType, varLenDataEncoder, varLenTypeEncoder } from "./codec/variableLength.js"
import { CiphersuiteImpl } from "./crypto/ciphersuite.js"
import { Hash } from "./crypto/hash.js"
import { encryptWithLabel, PrivateKey } from "./crypto/hpke.js"
import { deriveSecret } from "./crypto/kdf.js"
import { groupContextEncoder, GroupContext } from "./groupContext.js"
import {
  decodeLeafNodeCommit,
  leafNodeEncoder,
  LeafNodeCommit,
  LeafNodeTBSCommit,
  signLeafNodeCommit,
} from "./leafNode.js"
import { calculateParentHash } from "./parentHash.js"
import {
  filteredDirectPath,
  filteredDirectPathAndCopathResolution,
  getHpkePublicKey,
  Node,
  RatchetTree,
} from "./ratchetTree.js"
import { treeHashRoot } from "./treeHash.js"
import { isAncestor, LeafIndex, leafToNodeIndex, NodeIndex } from "./treemath.js"
import { constantTimeEqual } from "./util/constantTimeCompare.js"
import { decodeHpkeCiphertext, hpkeCiphertextEncoder, HPKECiphertext } from "./hpkeCiphertext.js"
import { InternalError, ValidationError } from "./mlsError.js"

export interface UpdatePathNode {
  hpkePublicKey: Uint8Array
  encryptedPathSecret: HPKECiphertext[]
}

export const updatePathNodeEncoder: BufferEncoder<UpdatePathNode> = contramapBufferEncoders(
  [varLenDataEncoder, varLenTypeEncoder(hpkeCiphertextEncoder)],
  (node) => [node.hpkePublicKey, node.encryptedPathSecret] as const,
)

export const encodeUpdatePathNode: Encoder<UpdatePathNode> = encode(updatePathNodeEncoder)

export const decodeUpdatePathNode: Decoder<UpdatePathNode> = mapDecoders(
  [decodeVarLenData, decodeVarLenType(decodeHpkeCiphertext)],
  (hpkePublicKey, encryptedPathSecret) => ({ hpkePublicKey, encryptedPathSecret }),
)

export interface UpdatePath {
  leafNode: LeafNodeCommit
  nodes: UpdatePathNode[]
}

export const updatePathEncoder: BufferEncoder<UpdatePath> = contramapBufferEncoders(
  [leafNodeEncoder, varLenTypeEncoder(updatePathNodeEncoder)],
  (path) => [path.leafNode, path.nodes] as const,
)

export const encodeUpdatePath: Encoder<UpdatePath> = encode(updatePathEncoder)

export const decodeUpdatePath: Decoder<UpdatePath> = mapDecoders(
  [decodeLeafNodeCommit, decodeVarLenType(decodeUpdatePathNode)],
  (leafNode, nodes) => ({ leafNode, nodes }),
)

export interface PathSecret {
  nodeIndex: number
  secret: Uint8Array
  sendTo: number[]
}

export async function createUpdatePath(
  originalTree: RatchetTree,
  senderLeafIndex: LeafIndex,
  groupContext: GroupContext,
  signaturePrivateKey: Uint8Array,
  cs: CiphersuiteImpl,
): Promise<[RatchetTree, UpdatePath, PathSecret[], PrivateKey]> {
  const originalLeafNode = originalTree[leafToNodeIndex(senderLeafIndex)]
  if (originalLeafNode === undefined || originalLeafNode.nodeType === "parent")
    throw new InternalError("Expected non-blank leaf node")

  const pathSecret = cs.rng.randomBytes(cs.kdf.size)

  const leafNodeSecret = await deriveSecret(pathSecret, "node", cs.kdf)
  const leafKeypair = await cs.hpke.deriveKeyPair(leafNodeSecret)

  const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, originalTree)

  const [ps, updatedTree]: [PathSecret[], RatchetTree] = await applyInitialTreeUpdate(
    fdp,
    pathSecret,
    senderLeafIndex,
    originalTree,
    cs,
  )

  const treeWithHashes = await insertParentHashes(fdp, updatedTree, cs)

  const leafParentHash = await calculateParentHash(treeWithHashes, leafToNodeIndex(senderLeafIndex), cs.hash)

  const updatedLeafNodeTbs: LeafNodeTBSCommit = {
    leafNodeSource: "commit",
    hpkePublicKey: await cs.hpke.exportPublicKey(leafKeypair.publicKey),
    extensions: originalLeafNode.leaf.extensions,
    capabilities: originalLeafNode.leaf.capabilities,
    credential: originalLeafNode.leaf.credential,
    signaturePublicKey: originalLeafNode.leaf.signaturePublicKey,
    parentHash: leafParentHash[0],
    info: { leafNodeSource: "commit", groupId: groupContext.groupId, leafIndex: senderLeafIndex },
  }

  const updatedLeafNode = await signLeafNodeCommit(updatedLeafNodeTbs, signaturePrivateKey, cs.signature)

  treeWithHashes[leafToNodeIndex(senderLeafIndex)] = {
    nodeType: "leaf",
    leaf: updatedLeafNode,
  }

  const updatedTreeHash = await treeHashRoot(treeWithHashes, cs.hash)

  const updatedGroupContext: GroupContext = {
    ...groupContext,
    treeHash: updatedTreeHash,
    epoch: groupContext.epoch + 1n,
  }

  // we have to remove the leaf secret since we don't send it to anyone
  const pathSecrets = ps.slice(0, ps.length - 1).reverse()

  // we have to pass the old tree here since the receiver won't have the updated public keys yet
  const updatePathNodes: UpdatePathNode[] = await Promise.all(
    pathSecrets.map(encryptSecretsForPath(originalTree, treeWithHashes, updatedGroupContext, cs)),
  )

  const updatePath: UpdatePath = { leafNode: updatedLeafNode, nodes: updatePathNodes }

  return [treeWithHashes, updatePath, pathSecrets, leafKeypair.privateKey] as const
}

function encryptSecretsForPath(
  originalTree: RatchetTree,
  updatedTree: RatchetTree,
  updatedGroupContext: GroupContext,
  cs: CiphersuiteImpl,
): (pathSecret: PathSecret) => Promise<UpdatePathNode> {
  return async (pathSecret) => {
    const key = getHpkePublicKey(updatedTree[pathSecret.nodeIndex]!)

    const res: UpdatePathNode = {
      hpkePublicKey: key,
      encryptedPathSecret: await Promise.all(
        pathSecret.sendTo.map(async (nodeIndex) => {
          const { ct, enc } = await encryptWithLabel(
            await cs.hpke.importPublicKey(getHpkePublicKey(originalTree[nodeIndex]!)),
            "UpdatePathNode",
            encode(groupContextEncoder)(updatedGroupContext),
            pathSecret.secret,
            cs.hpke,
          )
          return { ciphertext: ct, kemOutput: enc }
        }),
      ),
    }
    return res
  }
}

async function insertParentHashes(
  fdp: { resolution: NodeIndex[]; nodeIndex: NodeIndex }[],
  updatedTree: RatchetTree,
  cs: CiphersuiteImpl,
) {
  return await fdp
    .slice()
    .reverse()
    .reduce(async (treePromise, { nodeIndex }) => {
      const tree = await treePromise
      const parentHash = await calculateParentHash(tree, nodeIndex, cs.hash)
      const currentNode = tree[nodeIndex]
      if (currentNode === undefined || currentNode.nodeType === "leaf")
        throw new InternalError("Expected non-blank parent node")
      const updatedNode: Node = { nodeType: "parent", parent: { ...currentNode.parent, parentHash: parentHash[0] } }

      tree[nodeIndex] = updatedNode
      return tree
    }, Promise.resolve(updatedTree))
}

/**
 * Inserts new public keys from a single secret in the update path and returns the resulting tree along with the secrets along the path
 * Note that the path secrets are returned root to leaf
 */
async function applyInitialTreeUpdate(
  fdp: { resolution: number[]; nodeIndex: number }[],
  pathSecret: Uint8Array,
  senderLeafIndex: LeafIndex,
  tree: RatchetTree,
  cs: CiphersuiteImpl,
): Promise<[PathSecret[], RatchetTree]> {
  return await fdp.reduce(
    async (acc, { nodeIndex, resolution }) => {
      const [pathSecrets, tree] = await acc
      const lastPathSecret = pathSecrets[0]!
      const nextPathSecret = await deriveSecret(lastPathSecret.secret, "path", cs.kdf)
      const nextNodeSecret = await deriveSecret(nextPathSecret, "node", cs.kdf)
      const { publicKey } = await cs.hpke.deriveKeyPair(nextNodeSecret)

      tree[nodeIndex] = {
        nodeType: "parent",
        parent: {
          hpkePublicKey: await cs.hpke.exportPublicKey(publicKey),
          parentHash: new Uint8Array(),
          unmergedLeaves: [],
        },
      }

      return [[{ nodeIndex, secret: nextPathSecret, sendTo: resolution }, ...pathSecrets], tree]
    },
    Promise.resolve([
      [{ secret: pathSecret, nodeIndex: leafToNodeIndex(senderLeafIndex), sendTo: [] }],
      tree.slice(),
    ] as [PathSecret[], RatchetTree]),
  )
}

export async function applyUpdatePath(
  tree: RatchetTree,
  senderLeafIndex: LeafIndex,
  path: UpdatePath,
  h: Hash,
  isExternal: boolean = false,
): Promise<RatchetTree> {
  // if this is an external commit, the leaf node did not exist prior
  if (!isExternal) {
    const leafToUpdate = tree[leafToNodeIndex(senderLeafIndex)]

    if (leafToUpdate === undefined || leafToUpdate.nodeType === "parent")
      throw new InternalError("Leaf node not defined or is parent")

    const leafNodePublicKeyNotNew = constantTimeEqual(leafToUpdate.leaf.hpkePublicKey, path.leafNode.hpkePublicKey)

    if (leafNodePublicKeyNotNew)
      throw new ValidationError("Public key in the LeafNode is the same as the committer's current leaf node")
  }

  const pathNodePublicKeysExistInTree = path.nodes.some((node) =>
    tree.some((treeNode) => {
      return treeNode?.nodeType === "parent"
        ? constantTimeEqual(treeNode.parent.hpkePublicKey, node.hpkePublicKey)
        : false
    }),
  )

  if (pathNodePublicKeysExistInTree)
    throw new ValidationError("Public keys in the UpdatePath may not appear in a node of the new ratchet tree")

  const copy = tree.slice()

  copy[leafToNodeIndex(senderLeafIndex)] = { nodeType: "leaf", leaf: path.leafNode }

  const reverseFilteredDirectPath = filteredDirectPath(senderLeafIndex, tree).reverse()

  // need to call .slice here so as not to mutate the original
  const reverseUpdatePath = path.nodes.slice().reverse()

  if (reverseUpdatePath.length !== reverseFilteredDirectPath.length) {
    throw new ValidationError("Invalid length of UpdatePath")
  }

  for (const [level, nodeIndex] of reverseFilteredDirectPath.entries()) {
    const parentHash = await calculateParentHash(copy, nodeIndex, h)

    copy[nodeIndex] = {
      nodeType: "parent",
      parent: { hpkePublicKey: reverseUpdatePath[level]!.hpkePublicKey, unmergedLeaves: [], parentHash: parentHash[0] },
    }
  }

  const leafParentHash = await calculateParentHash(copy, leafToNodeIndex(senderLeafIndex), h)

  if (!constantTimeEqual(leafParentHash[0], path.leafNode.parentHash))
    throw new ValidationError("Parent hash did not match the UpdatePath")

  return copy
}

export function firstCommonAncestor(tree: RatchetTree, leafIndex: LeafIndex, senderLeafIndex: LeafIndex): NodeIndex {
  const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, tree)

  for (const { nodeIndex } of fdp) {
    if (isAncestor(leafToNodeIndex(leafIndex), nodeIndex, tree.length)) {
      return nodeIndex
    }
  }

  throw new ValidationError("Could not find common ancestor")
}

export function firstMatchAncestor(
  tree: RatchetTree,
  leafIndex: LeafIndex,
  senderLeafIndex: LeafIndex,
  path: UpdatePath,
): { nodeIndex: NodeIndex; resolution: NodeIndex[]; updateNode: UpdatePathNode | undefined } {
  const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, tree)

  for (const [n, { nodeIndex, resolution }] of fdp.entries()) {
    if (isAncestor(leafToNodeIndex(leafIndex), nodeIndex, tree.length)) {
      return { nodeIndex, resolution, updateNode: path.nodes[n] }
    }
  }

  throw new ValidationError("Could not find common ancestor")
}

1	import { Decoder, mapDecoders } from "./codec/tlsDecoder.js"	1✔
2	import { contramapBufferEncoders, BufferEncoder, encode, Encoder } from "./codec/tlsEncoder.js"	1✔
3	import { decodeVarLenData, decodeVarLenType, varLenDataEncoder, varLenTypeEncoder } from "./codec/variableLength.js"	1✔
4	import { CiphersuiteImpl } from "./crypto/ciphersuite.js"
5	import { Hash } from "./crypto/hash.js"
6	import { encryptWithLabel, PrivateKey } from "./crypto/hpke.js"	1✔
7	import { deriveSecret } from "./crypto/kdf.js"	1✔
8	import { groupContextEncoder, GroupContext } from "./groupContext.js"	1✔
9	import {	1✔
10	decodeLeafNodeCommit,
11	leafNodeEncoder,
12	LeafNodeCommit,
13	LeafNodeTBSCommit,
14	signLeafNodeCommit,
15	} from "./leafNode.js"
16	import { calculateParentHash } from "./parentHash.js"	1✔
17	import {	1✔
18	filteredDirectPath,
19	filteredDirectPathAndCopathResolution,
20	getHpkePublicKey,
21	Node,
22	RatchetTree,
23	} from "./ratchetTree.js"
24	import { treeHashRoot } from "./treeHash.js"	1✔
25	import { isAncestor, LeafIndex, leafToNodeIndex, NodeIndex } from "./treemath.js"	1✔
26	import { constantTimeEqual } from "./util/constantTimeCompare.js"	1✔
27	import { decodeHpkeCiphertext, hpkeCiphertextEncoder, HPKECiphertext } from "./hpkeCiphertext.js"	1✔
28	import { InternalError, ValidationError } from "./mlsError.js"	1✔
29
30	export interface UpdatePathNode {
31	hpkePublicKey: Uint8Array
32	encryptedPathSecret: HPKECiphertext[]
33	}
34
35	export const updatePathNodeEncoder: BufferEncoder<UpdatePathNode> = contramapBufferEncoders(	1✔
36	[varLenDataEncoder, varLenTypeEncoder(hpkeCiphertextEncoder)],	1✔
37	(node) => [node.hpkePublicKey, node.encryptedPathSecret] as const,	1✔
38	)	1✔
39
40	export const encodeUpdatePathNode: Encoder<UpdatePathNode> = encode(updatePathNodeEncoder)	1✔
41
42	export const decodeUpdatePathNode: Decoder<UpdatePathNode> = mapDecoders(	1✔
43	[decodeVarLenData, decodeVarLenType(decodeHpkeCiphertext)],	1✔
44	(hpkePublicKey, encryptedPathSecret) => ({ hpkePublicKey, encryptedPathSecret }),	1✔
45	)	1✔
46
47	export interface UpdatePath {
48	leafNode: LeafNodeCommit
49	nodes: UpdatePathNode[]
50	}
51
52	export const updatePathEncoder: BufferEncoder<UpdatePath> = contramapBufferEncoders(	1✔
53	[leafNodeEncoder, varLenTypeEncoder(updatePathNodeEncoder)],	1✔
54	(path) => [path.leafNode, path.nodes] as const,	1✔
55	)	1✔
56
57	export const encodeUpdatePath: Encoder<UpdatePath> = encode(updatePathEncoder)	1✔
58
59	export const decodeUpdatePath: Decoder<UpdatePath> = mapDecoders(	1✔
60	[decodeLeafNodeCommit, decodeVarLenType(decodeUpdatePathNode)],	1✔
61	(leafNode, nodes) => ({ leafNode, nodes }),	1✔
62	)	1✔
63
64	export interface PathSecret {
65	nodeIndex: number
66	secret: Uint8Array
67	sendTo: number[]
68	}
69
70	export async function createUpdatePath(	1,101✔
71	originalTree: RatchetTree,	1,101✔
72	senderLeafIndex: LeafIndex,	1,101✔
73	groupContext: GroupContext,	1,101✔
74	signaturePrivateKey: Uint8Array,	1,101✔
75	cs: CiphersuiteImpl,	1,101✔
76	): Promise<[RatchetTree, UpdatePath, PathSecret[], PrivateKey]> {	1,101✔
77	const originalLeafNode = originalTree[leafToNodeIndex(senderLeafIndex)]	1,101✔
78	if (originalLeafNode === undefined \|\| originalLeafNode.nodeType === "parent")	1,101✔
79	throw new InternalError("Expected non-blank leaf node")	1,101!
80
81	const pathSecret = cs.rng.randomBytes(cs.kdf.size)	1,101✔
82
83	const leafNodeSecret = await deriveSecret(pathSecret, "node", cs.kdf)	1,101✔
84	const leafKeypair = await cs.hpke.deriveKeyPair(leafNodeSecret)	1,101✔
85
86	const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, originalTree)	1,101✔
87
88	const [ps, updatedTree]: [PathSecret[], RatchetTree] = await applyInitialTreeUpdate(	1,101✔
89	fdp,	1,101✔
90	pathSecret,	1,101✔
91	senderLeafIndex,	1,101✔
92	originalTree,	1,101✔
93	cs,	1,101✔
94	)	1,101✔
95
96	const treeWithHashes = await insertParentHashes(fdp, updatedTree, cs)	1,101✔
97
98	const leafParentHash = await calculateParentHash(treeWithHashes, leafToNodeIndex(senderLeafIndex), cs.hash)	1,101✔
99
100	const updatedLeafNodeTbs: LeafNodeTBSCommit = {	1,101✔
101	leafNodeSource: "commit",	1,101✔
102	hpkePublicKey: await cs.hpke.exportPublicKey(leafKeypair.publicKey),	1,101✔
103	extensions: originalLeafNode.leaf.extensions,	1,101✔
104	capabilities: originalLeafNode.leaf.capabilities,	1,101✔
105	credential: originalLeafNode.leaf.credential,	1,101✔
106	signaturePublicKey: originalLeafNode.leaf.signaturePublicKey,	1,101✔
107	parentHash: leafParentHash[0],	1,101✔
108	info: { leafNodeSource: "commit", groupId: groupContext.groupId, leafIndex: senderLeafIndex },	1,101✔
109	}	1,101✔
110
111	const updatedLeafNode = await signLeafNodeCommit(updatedLeafNodeTbs, signaturePrivateKey, cs.signature)	1,101✔
112
113	treeWithHashes[leafToNodeIndex(senderLeafIndex)] = {	1,101✔
114	nodeType: "leaf",	1,101✔
115	leaf: updatedLeafNode,	1,101✔
116	}	1,101✔
117
118	const updatedTreeHash = await treeHashRoot(treeWithHashes, cs.hash)	1,101✔
119
120	const updatedGroupContext: GroupContext = {	1,101✔
121	...groupContext,	1,101✔
122	treeHash: updatedTreeHash,	1,101✔
123	epoch: groupContext.epoch + 1n,	1,101✔
124	}	1,101✔
125
126	// we have to remove the leaf secret since we don't send it to anyone
127	const pathSecrets = ps.slice(0, ps.length - 1).reverse()	1,101✔
128
129	// we have to pass the old tree here since the receiver won't have the updated public keys yet
130	const updatePathNodes: UpdatePathNode[] = await Promise.all(	1,101✔
131	pathSecrets.map(encryptSecretsForPath(originalTree, treeWithHashes, updatedGroupContext, cs)),	1,101✔
132	)	1,101✔
133
134	const updatePath: UpdatePath = { leafNode: updatedLeafNode, nodes: updatePathNodes }	1,101✔
135
136	return [treeWithHashes, updatePath, pathSecrets, leafKeypair.privateKey] as const	1,101✔
137	}	1,101✔
138
139	function encryptSecretsForPath(	852✔
140	originalTree: RatchetTree,	852✔
141	updatedTree: RatchetTree,	852✔
142	updatedGroupContext: GroupContext,	852✔
143	cs: CiphersuiteImpl,	852✔
144	): (pathSecret: PathSecret) => Promise<UpdatePathNode> {	852✔
145	return async (pathSecret) => {	852✔
146	const key = getHpkePublicKey(updatedTree[pathSecret.nodeIndex]!)	2,279✔
147
148	const res: UpdatePathNode = {	2,279✔
149	hpkePublicKey: key,	2,279✔
150	encryptedPathSecret: await Promise.all(	2,279✔
151	pathSecret.sendTo.map(async (nodeIndex) => {	2,279✔
152	const { ct, enc } = await encryptWithLabel(	2,514✔
153	await cs.hpke.importPublicKey(getHpkePublicKey(originalTree[nodeIndex]!)),	2,514✔
154	"UpdatePathNode",	2,514✔
155	encode(groupContextEncoder)(updatedGroupContext),	2,514✔
156	pathSecret.secret,	2,514✔
157	cs.hpke,	2,514✔
158	)	2,514✔
159	return { ciphertext: ct, kemOutput: enc }	2,514✔
160	}),	2,279✔
161	),	2,279✔
162	}	2,279✔
163	return res	2,279✔
164	}	2,279✔
165	}	852✔
166
167	async function insertParentHashes(	1,101✔
168	fdp: { resolution: NodeIndex[]; nodeIndex: NodeIndex }[],	1,101✔
169	updatedTree: RatchetTree,	1,101✔
170	cs: CiphersuiteImpl,	1,101✔
171	) {	1,101✔
172	return await fdp	1,101✔
173	.slice()	1,101✔
174	.reverse()	1,101✔
175	.reduce(async (treePromise, { nodeIndex }) => {	1,101✔
176	const tree = await treePromise	2,279✔
177	const parentHash = await calculateParentHash(tree, nodeIndex, cs.hash)	2,279✔
178	const currentNode = tree[nodeIndex]	2,279✔
179	if (currentNode === undefined \|\| currentNode.nodeType === "leaf")	2,279✔
180	throw new InternalError("Expected non-blank parent node")	2,279!
181	const updatedNode: Node = { nodeType: "parent", parent: { ...currentNode.parent, parentHash: parentHash[0] } }	2,279✔
182
183	tree[nodeIndex] = updatedNode	2,279✔
184	return tree	2,279✔
185	}, Promise.resolve(updatedTree))	1,101✔
186	}	1,101✔
187
188	/**
189	* Inserts new public keys from a single secret in the update path and returns the resulting tree along with the secrets along the path
190	* Note that the path secrets are returned root to leaf
191	*/
192	async function applyInitialTreeUpdate(	854✔
193	fdp: { resolution: number[]; nodeIndex: number }[],	854✔
194	pathSecret: Uint8Array,	854✔
195	senderLeafIndex: LeafIndex,	854✔
196	tree: RatchetTree,	854✔
197	cs: CiphersuiteImpl,	854✔
198	): Promise<[PathSecret[], RatchetTree]> {	854✔
199	return await fdp.reduce(	854✔
200	async (acc, { nodeIndex, resolution }) => {	854✔
201	const [pathSecrets, tree] = await acc	2,279✔
202	const lastPathSecret = pathSecrets[0]!	2,279✔
203	const nextPathSecret = await deriveSecret(lastPathSecret.secret, "path", cs.kdf)	2,279✔
204	const nextNodeSecret = await deriveSecret(nextPathSecret, "node", cs.kdf)	2,279✔
205	const { publicKey } = await cs.hpke.deriveKeyPair(nextNodeSecret)	2,279✔
206
207	tree[nodeIndex] = {	2,279✔
208	nodeType: "parent",	2,279✔
209	parent: {	2,279✔
210	hpkePublicKey: await cs.hpke.exportPublicKey(publicKey),	2,279✔
211	parentHash: new Uint8Array(),	2,279✔
212	unmergedLeaves: [],	2,279✔
213	},	2,279✔
214	}	2,279✔
215
216	return [[{ nodeIndex, secret: nextPathSecret, sendTo: resolution }, ...pathSecrets], tree]	2,279✔
217	},	2,279✔
218	Promise.resolve([	854✔
219	[{ secret: pathSecret, nodeIndex: leafToNodeIndex(senderLeafIndex), sendTo: [] }],	854✔
220	tree.slice(),	854✔
221	] as [PathSecret[], RatchetTree]),	854✔
222	)	854✔
223	}	854✔
224
225	export async function applyUpdatePath(	2,441✔
226	tree: RatchetTree,	2,441✔
227	senderLeafIndex: LeafIndex,	2,441✔
228	path: UpdatePath,	2,441✔
229	h: Hash,	2,441✔
230	isExternal: boolean = false,	2,441✔
231	): Promise<RatchetTree> {	2,441✔
232	// if this is an external commit, the leaf node did not exist prior
233	if (!isExternal) {	2,441✔
234	const leafToUpdate = tree[leafToNodeIndex(senderLeafIndex)]	2,365✔
235
236	if (leafToUpdate === undefined \|\| leafToUpdate.nodeType === "parent")	2,365✔
237	throw new InternalError("Leaf node not defined or is parent")	2,365!
238
239	const leafNodePublicKeyNotNew = constantTimeEqual(leafToUpdate.leaf.hpkePublicKey, path.leafNode.hpkePublicKey)	2,365✔
240
241	if (leafNodePublicKeyNotNew)	2,365✔
242	throw new ValidationError("Public key in the LeafNode is the same as the committer's current leaf node")	2,365!
243	}	2,365✔
244
245	const pathNodePublicKeysExistInTree = path.nodes.some((node) =>	2,441✔
246	tree.some((treeNode) => {	6,508✔
247	return treeNode?.nodeType === "parent"	138,560✔
248	? constantTimeEqual(treeNode.parent.hpkePublicKey, node.hpkePublicKey)	28,740✔
249	: false	109,820✔
250	}),	6,508✔
251	)	2,441✔
252
253	if (pathNodePublicKeysExistInTree)	2,441✔
254	throw new ValidationError("Public keys in the UpdatePath may not appear in a node of the new ratchet tree")	2,441!
255
256	const copy = tree.slice()	2,441✔
257
258	copy[leafToNodeIndex(senderLeafIndex)] = { nodeType: "leaf", leaf: path.leafNode }	2,441✔
259
260	const reverseFilteredDirectPath = filteredDirectPath(senderLeafIndex, tree).reverse()	2,441✔
261
262	// need to call .slice here so as not to mutate the original
263	const reverseUpdatePath = path.nodes.slice().reverse()	2,441✔
264
265	if (reverseUpdatePath.length !== reverseFilteredDirectPath.length) {	2,441!
UNCOV 266	throw new ValidationError("Invalid length of UpdatePath")	×
UNCOV 267	}	×
268
269	for (const [level, nodeIndex] of reverseFilteredDirectPath.entries()) {	2,441✔
270	const parentHash = await calculateParentHash(copy, nodeIndex, h)	6,508✔
271
272	copy[nodeIndex] = {	6,508✔
273	nodeType: "parent",	6,508✔
274	parent: { hpkePublicKey: reverseUpdatePath[level]!.hpkePublicKey, unmergedLeaves: [], parentHash: parentHash[0] },	6,508✔
275	}	6,508✔
276	}	6,508✔
277
278	const leafParentHash = await calculateParentHash(copy, leafToNodeIndex(senderLeafIndex), h)	2,441✔
279
280	if (!constantTimeEqual(leafParentHash[0], path.leafNode.parentHash))	2,441✔
281	throw new ValidationError("Parent hash did not match the UpdatePath")	2,441!
282
283	return copy	2,441✔
284	}	2,441✔
285
286	export function firstCommonAncestor(tree: RatchetTree, leafIndex: LeafIndex, senderLeafIndex: LeafIndex): NodeIndex {	1✔
287	const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, tree)	2,117✔
288
289	for (const { nodeIndex } of fdp) {	2,117✔
290	if (isAncestor(leafToNodeIndex(leafIndex), nodeIndex, tree.length)) {	3,095✔
291	return nodeIndex	2,117✔
292	}	2,117✔
293	}	3,095!
294
UNCOV 295	throw new ValidationError("Could not find common ancestor")	×
UNCOV 296	}	×
297
298	export function firstMatchAncestor(	1✔
299	tree: RatchetTree,	6,599✔
300	leafIndex: LeafIndex,	6,599✔
301	senderLeafIndex: LeafIndex,	6,599✔
302	path: UpdatePath,	6,599✔
303	): { nodeIndex: NodeIndex; resolution: NodeIndex[]; updateNode: UpdatePathNode \| undefined } {	6,599✔
304	const fdp = filteredDirectPathAndCopathResolution(senderLeafIndex, tree)	6,599✔
305
306	for (const [n, { nodeIndex, resolution }] of fdp.entries()) {	6,599✔
307	if (isAncestor(leafToNodeIndex(leafIndex), nodeIndex, tree.length)) {	14,437✔
308	return { nodeIndex, resolution, updateNode: path.nodes[n] }	6,599✔
309	}	6,599✔
310	}	14,437!
311
UNCOV 312	throw new ValidationError("Could not find common ancestor")	×
UNCOV 313	}	×

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