1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
// BSD 2-Clause License
//
// Copyright (c) 2022, the ct authors
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// From:
// https://gitlab.torproject.org/rgdd/ct/-/tree/main/pkg/merkle
//
// The only difference is that leaf hashes rather than leaf data are passed as
// input to TreeHeadFromRangeProof, thus also changing the nodes() helper.
package merkle
import (
"crypto/sha256"
"fmt"
)
// node represents a subtree at some level and a particular index
type node struct {
index uint64
hash [sha256.Size]byte
}
// nodes returns a list of consecutive leaf hashes
func nodes(index uint64, leafHashes [][sha256.Size]byte) (n []node) {
for i, lh := range leafHashes {
n = append(n, node{index + uint64(i), lh})
}
return
}
// compactRange outputs the minimal number of fixed subtree hashes given a
// non-empty list of consecutive leaves that start from a non-zero index. For a
// definition of this algorithm, see the end of ../../doc/tlog_algorithms.md.
func compactRange(nodes []node) [][sha256.Size]byte {
// Step 1
var hashes [][sha256.Size]byte
// Step 2
for len(nodes) > 1 {
// Step 2a
if xor(nodes[1].index, 1) != nodes[0].index {
hashes = append(hashes, nodes[0].hash)
nodes = nodes[1:]
}
// Step 2b; Step 2c; Step 2c(iii)
for i := 0; i < len(nodes); i++ {
// Step 2c(i)
if i+1 != len(nodes) {
nodes[i].hash = HashInteriorNode(nodes[i].hash, nodes[i+1].hash)
nodes = append(nodes[:i+1], nodes[i+2:]...)
}
// Step 2c(ii)
nodes[i].index = rshift(nodes[i].index)
}
}
// Step 3
return append(hashes, nodes[0].hash)
}
// TreeHeadFromRangeProof computes a tree head at size n=len(leafHashes)+index
// if given a list of leaf hashes at indices index,...,n-1 as well as an
// inclusion proof for the first leaf in the tree of size n. This allows a
// verifier to check inclusion of one or more log entries with a single
// inclusion proof.
func TreeHeadFromRangeProof(leafHashes [][sha256.Size]byte, index uint64, proof [][sha256.Size]byte) (root [sha256.Size]byte, err error) {
var cr [][sha256.Size]byte
confirmHash := func(h [sha256.Size]byte) error {
if h != cr[0] {
return fmt.Errorf("aborted due incorrect right-node subtree hash")
}
cr = cr[1:]
return nil
}
copyRoot := func(r [sha256.Size]byte) error {
root = r
return nil
}
if len(leafHashes) == 0 {
return [sha256.Size]byte{}, fmt.Errorf("need at least one leaf to recompute tree head from proof")
}
if len(leafHashes) > 1 {
cr = compactRange(nodes(index+1, leafHashes[1:]))
}
return root, inclusion(leafHashes[0], index, index+uint64(len(leafHashes)), proof, copyRoot, confirmHash)
}
func xor(a, b uint64) uint64 {
return a ^ b
}
|
