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

LukaJCB / ts-mls / 17283659198

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

push

github

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

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
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✔
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