Debian Codegraph @

node_modules/@sigstore/verify/dist/tlog/merkle.js

raw
1 "use strict";
2 Object.defineProperty(exports, "__esModule", { value: true });
3 exports.verifyMerkleInclusion = verifyMerkleInclusion;
4 /*
5 Copyright 2023 The Sigstore Authors.
6
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10
11 http://www.apache.org/licenses/LICENSE-2.0
12
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18 */
19 const core_1 = require("@sigstore/core");
20 const error_1 = require("../error");
21 const RFC6962_LEAF_HASH_PREFIX = Buffer.from([0x00]);
22 const RFC6962_NODE_HASH_PREFIX = Buffer.from([0x01]);
23 function verifyMerkleInclusion(entry, checkpoint) {
24 const inclusionProof = entry.inclusionProof;
25 const logIndex = BigInt(inclusionProof.logIndex);
26 const treeSize = BigInt(checkpoint.logSize);
27 if (logIndex < 0n || logIndex >= treeSize) {
28 throw new error_1.VerificationError({
29 code: 'TLOG_INCLUSION_PROOF_ERROR',
30 message: `invalid index: ${logIndex}`,
31 });
32 }
33 // Figure out which subset of hashes corresponds to the inner and border
34 // nodes
35 const { inner, border } = decompInclProof(logIndex, treeSize);
36 if (inclusionProof.hashes.length !== inner + border) {
37 throw new error_1.VerificationError({
38 code: 'TLOG_INCLUSION_PROOF_ERROR',
39 message: 'invalid hash count',
40 });
41 }
42 const innerHashes = inclusionProof.hashes.slice(0, inner);
43 const borderHashes = inclusionProof.hashes.slice(inner);
44 // The entry's hash is the leaf hash
45 const leafHash = hashLeaf(entry.canonicalizedBody);
46 // Chain the hashes belonging to the inner and border portions
47 const calculatedHash = chainBorderRight(chainInner(leafHash, innerHashes, logIndex), borderHashes);
48 // Calculated hash should match the root hash in the inclusion proof
49 if (!core_1.crypto.bufferEqual(calculatedHash, checkpoint.logHash)) {
50 throw new error_1.VerificationError({
51 code: 'TLOG_INCLUSION_PROOF_ERROR',
52 message: 'calculated root hash does not match inclusion proof',
53 });
54 }
55 }
56 // Breaks down inclusion proof for a leaf at the specified index in a tree of
57 // the specified size. The split point is where paths to the index leaf and
58 // the (size - 1) leaf diverge. Returns lengths of the bottom and upper proof
59 // parts.
60 function decompInclProof(index, size) {
61 const inner = innerProofSize(index, size);
62 const border = onesCount(index >> BigInt(inner));
63 return { inner, border };
64 }
65 // Computes a subtree hash for a node on or below the tree's right border.
66 // Assumes the provided proof hashes are ordered from lower to higher levels
67 // and seed is the initial hash of the node specified by the index.
68 function chainInner(seed, hashes, index) {
69 return hashes.reduce((acc, h, i) => {
70 if ((index >> BigInt(i)) & BigInt(1)) {
71 return hashChildren(h, acc);
72 }
73 else {
74 return hashChildren(acc, h);
75 }
76 }, seed);
77 }
78 // Computes a subtree hash for nodes along the tree's right border.
79 function chainBorderRight(seed, hashes) {
80 return hashes.reduce((acc, h) => hashChildren(h, acc), seed);
81 }
82 function innerProofSize(index, size) {
83 return bitLength(index ^ (size - BigInt(1)));
84 }
85 // Counts the number of ones in the binary representation of the given number.
86 // https://en.wikipedia.org/wiki/Hamming_weight
87 function onesCount(num) {
88 return num.toString(2).split('1').length - 1;
89 }
90 // Returns the number of bits necessary to represent an integer in binary.
91 function bitLength(n) {
92 if (n === 0n) {
93 return 0;
94 }
95 return n.toString(2).length;
96 }
97 // Hashing logic according to RFC6962.
98 // https://datatracker.ietf.org/doc/html/rfc6962#section-2
99 function hashChildren(left, right) {
100 return core_1.crypto.digest('sha256', RFC6962_NODE_HASH_PREFIX, left, right);
101 }
102 function hashLeaf(leaf) {
103 return core_1.crypto.digest('sha256', RFC6962_LEAF_HASH_PREFIX, leaf);
104 }