aboutsummaryrefslogtreecommitdiff
path: root/internal/merkle
diff options
context:
space:
mode:
authorRasmus Dahlberg <rasmus@rgdd.se>2023-03-17 09:45:57 +0100
committerRasmus Dahlberg <rasmus@rgdd.se>2023-03-17 09:45:57 +0100
commit41d60fa299b99d1ac1b4afc865924ad79a91a5d9 (patch)
tree27ca14453ec4b17fa8c002ff9698917a4592fd18 /internal/merkle
parent7548bc1d6ea5cf5a1e72fd6725ea33288b5d2b2b (diff)
Fork merkle package
To get ranged inclusion proofs that operate on leaf hashes rather than the leaf data. Should probably be fixed upstream at some point.
Diffstat (limited to 'internal/merkle')
-rw-r--r--internal/merkle/compact.go115
-rw-r--r--internal/merkle/merkle.go271
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
+}