• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

LukaJCB / ts-mls / 20081738515

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

Pull #171

github

web-flow
Merge 0be266886 into 5e1453cbc
Pull Request #171: Reduce tree copies and iterations

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
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
}
×
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc