diff options
| -rw-r--r-- | internal/merkle/compact.go | 115 | ||||
| -rw-r--r-- | internal/merkle/merkle.go | 271 |
2 files changed, 386 insertions, 0 deletions
diff --git a/internal/merkle/compact.go b/internal/merkle/compact.go new file mode 100644 index 0000000..6eeabd0 --- /dev/null +++ b/internal/merkle/compact.go @@ -0,0 +1,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 +} diff --git a/internal/merkle/merkle.go b/internal/merkle/merkle.go new file mode 100644 index 0000000..872364f --- /dev/null +++ b/internal/merkle/merkle.go @@ -0,0 +1,271 @@ +// 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 +package merkle + +import ( + "crypto/sha256" + "fmt" +) + +// HashEmptyTree computes the hash of an empty tree. See RFC 6162, §2.1: +// +// MTH({}) = SHA-256() +func HashEmptyTree() [sha256.Size]byte { + return sha256.Sum256(nil) +} + +// HashLeafNode computes the hash of a leaf's data. See RFC 6162, §2.1: +// +// MTH({d(0)}) = SHA-256(0x00 || d(0)) +func HashLeafNode(data []byte) (hash [sha256.Size]byte) { + h := sha256.New() + h.Write([]byte{0x00}) + h.Write(data) + copy(hash[:], h.Sum(nil)) + return +} + +// HashInteriorNode computes the hash of an interior node. See RFC 6962, §2.1: +// +// MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n]) +func HashInteriorNode(left, right [sha256.Size]byte) (hash [sha256.Size]byte) { + h := sha256.New() + h.Write([]byte{0x01}) + h.Write(left[:]) + h.Write(right[:]) + copy(hash[:], h.Sum(nil)) + return +} + +// inclusion implements the algorithm specified in RFC 9162, Section 2.1.3.2. +// In addition, the caller is allowed to confirm right-node subtree hashes. +func inclusion(leaf [sha256.Size]byte, index, size uint64, proof [][sha256.Size]byte, + confirmRoot func([sha256.Size]byte) error, confirmHash func([sha256.Size]byte) error) error { + // Step 1 + if index >= size { + return fmt.Errorf("leaf index must be in [%d, %d]", 0, size-1) + } + + // Step 2 + fn := index + sn := size - 1 + + // Step 3 + r := leaf + + // Step 4 + for i, p := range proof { + // Step 4a + if sn == 0 { + return fmt.Errorf("reached tree head with %d remaining proof hash(es)", len(proof[i:])) + } + + // Step 4b + if isLSB(fn) || fn == sn { + // Step 4b, i + r = HashInteriorNode(p, r) + + // Step 4b, ii + if !isLSB(fn) { + for { + fn = rshift(fn) + sn = rshift(sn) + + if isLSB(fn) || fn == 0 { + break + } + } + } + } else { + // Step 4b, i + r = HashInteriorNode(r, p) + + // Extension: allow the caller to confirm right-node subtree hashes + if err := confirmHash(p); err != nil { + return fmt.Errorf("subtree index %d: %v", fn, err) + } + } + + // Step 4c + fn = rshift(fn) + sn = rshift(sn) + } + + // Step 5 + if sn != 0 { + return fmt.Errorf("stopped at subtree with index %d due to missing proof hashes", fn) + } + return confirmRoot(r) +} + +// consistency implements the algorithm specified in RFC 9162, §2.1.4.2 +func consistency(oldSize, newSize uint64, oldRoot, newRoot [sha256.Size]byte, proof [][sha256.Size]byte) error { + // Step 1 + if len(proof) == 0 { + return fmt.Errorf("need at least one proof hash") + } + + // Step 2 + if isPOW2(oldSize) { + proof = append([][sha256.Size]byte{oldRoot}, proof...) + } + + // Step 3 + fn := oldSize - 1 + sn := newSize - 1 + + // Step 4 + for isLSB(fn) { + fn = rshift(fn) + sn = rshift(sn) + } + + // Step 5 + fr := proof[0] + sr := proof[0] + + // Step 6 + for i, c := range proof[1:] { + // Step 6a + if sn == 0 { + return fmt.Errorf("reached tree head with %d remaining proof hash(es)", len(proof[i+1:])) + } + + // Step 6b + if isLSB(fn) || fn == sn { + // Step 6b, i + fr = HashInteriorNode(c, fr) + // Step 6b, ii + sr = HashInteriorNode(c, sr) + // Step 6b, iii + if !isLSB(fn) { + for { + fn = rshift(fn) + sn = rshift(sn) + + if isLSB(fn) || fn == 0 { + break + } + } + } + } else { + // Step 6b, i + sr = HashInteriorNode(sr, c) + } + + // Step 6c + fn = rshift(fn) + sn = rshift(sn) + } + + // Step 7 + if sn != 0 { + return fmt.Errorf("stopped at subtree with index %d due to missing proof hashes", fn) + } + if fr != oldRoot { + return fmt.Errorf("recomputed old tree head %x is not equal to reference tree head %x", fr[:], oldRoot[:]) + } + if sr != newRoot { + return fmt.Errorf("recomputed new tree head %x is not equal to reference tree head %x", sr[:], newRoot[:]) + } + return nil +} + +// VerifyInclusion verifies that a leaf's data is commited at a given index in a +// reference tree +func VerifyInclusion(data []byte, index, size uint64, root [sha256.Size]byte, proof [][sha256.Size]byte) error { + if size == 0 { + return fmt.Errorf("tree size must be larger than zero") + } + + confirmHash := func(h [sha256.Size]byte) error { return nil } // No compact range extension + confirmRoot := func(r [sha256.Size]byte) error { + if r != root { + return fmt.Errorf("recomputed tree head %x is not equal to reference tree head %x", r[:], root[:]) + } + return nil + } + return inclusion(HashLeafNode(data), index, size, proof, confirmRoot, confirmHash) +} + +// VerifyConsistency verifies that an an old tree is consistent with a new tree +func VerifyConsistency(oldSize, newSize uint64, oldRoot, newRoot [sha256.Size]byte, proof [][sha256.Size]byte) error { + checkTree := func(size uint64, root [sha256.Size]byte) error { + if size == 0 { + if root != HashEmptyTree() { + return fmt.Errorf("non-empty tree head %x for size zero", root[:]) + } + if len(proof) != 0 { + return fmt.Errorf("non-empty proof with %d hashes for size zero", len(proof)) + } + } else if root == HashEmptyTree() { + return fmt.Errorf("empty tree head %x for tree size %d", root[:], size) + } + return nil + } + + if err := checkTree(oldSize, oldRoot); err != nil { + return fmt.Errorf("old: %v", err) + } + if err := checkTree(newSize, newRoot); err != nil { + return fmt.Errorf("new: %v", err) + } + if oldSize == 0 { + return nil + } + + if oldSize == newSize { + if oldRoot != newRoot { + return fmt.Errorf("different tree heads %x and %x with equal tree size %d", oldRoot, newRoot, oldSize) + } + if len(proof) != 0 { + return fmt.Errorf("non-empty proof with %d hashes for equal tree size %d", len(proof), oldSize) + } + return nil + } + if oldSize > newSize { + return fmt.Errorf("old tree size %d must be smaller than or equal to the new tree size %d", oldSize, newSize) + } + + return consistency(oldSize, newSize, oldRoot, newRoot, proof) +} + +// isLSB returns true if the least significant bit of num is set +func isLSB(num uint64) bool { + return (num & 1) != 0 +} + +// isPOW2 returns true if num is a power of two (1, 2, 4, 8, ...) +func isPOW2(num uint64) bool { + return (num & (num - 1)) == 0 +} + +func rshift(num uint64) uint64 { + return num >> 1 +} |