1 // Copyright 2022 Google LLC. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // Package proof contains helpers for constructing log Merkle tree proofs. 16 package proof 17 18 import ( 19 "fmt" 20 "math/bits" 21 22 "github.com/transparency-dev/merkle/compact" 23 ) 24 25 // Nodes contains information on how to construct a log Merkle tree proof. It 26 // supports any proof that has at most one ephemeral node, such as inclusion 27 // and consistency proofs defined in RFC 6962. 28 type Nodes struct { 29 // IDs contains the IDs of non-ephemeral nodes sufficient to build the proof. 30 // If an ephemeral node is needed for a proof, it can be recomputed based on 31 // a subset of nodes in this list. 32 IDs []compact.NodeID 33 // begin is the beginning index (inclusive) into the IDs[begin:end] subslice 34 // of the nodes which will be used to re-create the ephemeral node. 35 begin int 36 // end is the ending (exclusive) index into the IDs[begin:end] subslice of 37 // the nodes which will be used to re-create the ephemeral node. 38 end int 39 // ephem is the ID of the ephemeral node in the proof. This node is a common 40 // ancestor of all nodes in IDs[begin:end]. It is the node that otherwise 41 // would have been used in the proof if the tree was perfect. 42 ephem compact.NodeID 43 } 44 45 // Inclusion returns the information on how to fetch and construct an inclusion 46 // proof for the given leaf index in a log Merkle tree of the given size. It 47 // requires 0 <= index < size. 48 func Inclusion(index, size uint64) (Nodes, error) { 49 if index >= size { 50 return Nodes{}, fmt.Errorf("index %d out of bounds for tree size %d", index, size) 51 } 52 return nodes(index, 0, size).skipFirst(), nil 53 } 54 55 // Consistency returns the information on how to fetch and construct a 56 // consistency proof between the two given tree sizes of a log Merkle tree. It 57 // requires 0 <= size1 <= size2. 58 func Consistency(size1, size2 uint64) (Nodes, error) { 59 if size1 > size2 { 60 return Nodes{}, fmt.Errorf("tree size %d > %d", size1, size2) 61 } 62 if size1 == size2 || size1 == 0 { 63 return Nodes{IDs: []compact.NodeID{}}, nil 64 } 65 66 // Find the root of the biggest perfect subtree that ends at size1. 67 level := uint(bits.TrailingZeros64(size1)) 68 index := (size1 - 1) >> level 69 // The consistency proof consists of this node (except if size1 is a power of 70 // two, in which case adding this node would be redundant because the client 71 // is assumed to know it from a checkpoint), and nodes of the inclusion proof 72 // into this node in the tree of size2. 73 p := nodes(index, level, size2) 74 75 // Handle the case when size1 is a power of 2. 76 if index == 0 { 77 return p.skipFirst(), nil 78 } 79 return p, nil 80 } 81 82 // nodes returns the node IDs necessary to prove that the (level, index) node 83 // is included in the Merkle tree of the given size. 84 func nodes(index uint64, level uint, size uint64) Nodes { 85 // Compute the `fork` node, where the path from root to (level, index) node 86 // diverges from the path to (0, size). 87 // 88 // The sibling of this node is the ephemeral node which represents a subtree 89 // that is not complete in the tree of the given size. To compute the hash 90 // of the ephemeral node, we need all the non-ephemeral nodes that cover the 91 // same range of leaves. 92 // 93 // The `inner` variable is how many layers up from (level, index) the `fork` 94 // and the ephemeral nodes are. 95 inner := bits.Len64(index^(size>>level)) - 1 96 fork := compact.NewNodeID(level+uint(inner), index>>inner) 97 98 begin, end := fork.Coverage() 99 left := compact.RangeSize(0, begin) 100 right := compact.RangeSize(end, size) 101 102 node := compact.NewNodeID(level, index) 103 // Pre-allocate the exact number of nodes for the proof, in order: 104 // - The seed node for which we are building the proof. 105 // - The `inner` nodes at each level up to the fork node. 106 // - The `right` nodes, comprising the ephemeral node. 107 // - The `left` nodes, completing the coverage of the whole [0, size) range. 108 nodes := append(make([]compact.NodeID, 0, 1+inner+right+left), node) 109 110 // The first portion of the proof consists of the siblings for nodes of the 111 // path going up to the level at which the ephemeral node appears. 112 for ; node.Level < fork.Level; node = node.Parent() { 113 nodes = append(nodes, node.Sibling()) 114 } 115 // This portion of the proof covers the range [begin, end) under it. The 116 // ranges to the left and to the right from it remain to be covered. 117 118 // Add all the nodes (potentially none) that cover the right range, and 119 // represent the ephemeral node. Reverse them so that the Rehash method can 120 // process hashes in the convenient order, from lower to upper levels. 121 len1 := len(nodes) 122 nodes = compact.RangeNodes(end, size, nodes) 123 reverse(nodes[len(nodes)-right:]) 124 len2 := len(nodes) 125 // Add the nodes that cover the left range, ordered increasingly by level. 126 nodes = compact.RangeNodes(0, begin, nodes) 127 reverse(nodes[len(nodes)-left:]) 128 129 // nodes[len1:len2] contains the nodes representing the ephemeral node. If 130 // it's empty, make it zero. Note that it can also contain a single node. 131 // Depending on the preference of the layer above, it may or may not be 132 // considered ephemeral. 133 if len1 >= len2 { 134 len1, len2 = 0, 0 135 } 136 137 return Nodes{IDs: nodes, begin: len1, end: len2, ephem: fork.Sibling()} 138 } 139 140 // Ephem returns the ephemeral node, and indices begin and end, such that 141 // IDs[begin:end] slice contains the child nodes of the ephemeral node. 142 // 143 // The list is empty iff there are no ephemeral nodes in the proof. Some 144 // examples of when this can happen: a proof in a perfect tree; an inclusion 145 // proof for a leaf in a perfect subtree at the right edge of the tree. 146 func (n Nodes) Ephem() (compact.NodeID, int, int) { 147 return n.ephem, n.begin, n.end 148 } 149 150 // Rehash computes the proof based on the slice of node hashes corresponding to 151 // their IDs in the n.IDs field. The slices must be of the same length. The hc 152 // parameter computes a node's hash based on hashes of its children. 153 // 154 // Warning: The passed-in slice of hashes can be modified in-place. 155 func (n Nodes) Rehash(h [][]byte, hc func(left, right []byte) []byte) ([][]byte, error) { 156 if got, want := len(h), len(n.IDs); got != want { 157 return nil, fmt.Errorf("got %d hashes but expected %d", got, want) 158 } 159 cursor := 0 160 // Scan the list of node hashes, and store the rehashed list in-place. 161 // Invariant: cursor <= i, and h[:cursor] contains all the hashes of the 162 // rehashed list after scanning h up to index i-1. 163 for i, ln := 0, len(h); i < ln; i, cursor = i+1, cursor+1 { 164 hash := h[i] 165 if i >= n.begin && i < n.end { 166 // Scan the block of node hashes that need rehashing. 167 for i++; i < n.end; i++ { 168 hash = hc(h[i], hash) 169 } 170 i-- 171 } 172 h[cursor] = hash 173 } 174 return h[:cursor], nil 175 } 176 177 func (n Nodes) skipFirst() Nodes { 178 n.IDs = n.IDs[1:] 179 // Fixup the indices into the IDs slice. 180 if n.begin < n.end { 181 n.begin-- 182 n.end-- 183 } 184 return n 185 } 186 187 func reverse(ids []compact.NodeID) { 188 for i, j := 0, len(ids)-1; i < j; i, j = i+1, j-1 { 189 ids[i], ids[j] = ids[j], ids[i] 190 } 191 } 192