diff options
Diffstat (limited to 'internal/merkle/compact.go')
| -rw-r--r-- | internal/merkle/compact.go | 115 |
1 files changed, 0 insertions, 115 deletions
diff --git a/internal/merkle/compact.go b/internal/merkle/compact.go deleted file mode 100644 index 6eeabd0..0000000 --- a/internal/merkle/compact.go +++ /dev/null @@ -1,115 +0,0 @@ -// 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 -} |