verify.go

Documentation: github.com/transparency-dev/merkle/proof

     1  // Copyright 2017 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
    16  
    17  import (
    18  	"bytes"
    19  	"errors"
    20  	"fmt"
    21  	"math/bits"
    22  
    23  	"github.com/transparency-dev/merkle"
    24  )
    25  
    26  // RootMismatchError occurs when an inclusion proof fails.
    27  type RootMismatchError struct {
    28  	ExpectedRoot   []byte
    29  	CalculatedRoot []byte
    30  }
    31  
    32  func (e RootMismatchError) Error() string {
    33  	return fmt.Sprintf("calculated root:\n%v\n does not match expected root:\n%v", e.CalculatedRoot, e.ExpectedRoot)
    34  }
    35  
    36  func verifyMatch(calculated, expected []byte) error {
    37  	if !bytes.Equal(calculated, expected) {
    38  		return RootMismatchError{ExpectedRoot: expected, CalculatedRoot: calculated}
    39  	}
    40  	return nil
    41  }
    42  
    43  // VerifyInclusion verifies the correctness of the inclusion proof for the leaf
    44  // with the specified hash and index, relatively to the tree of the given size
    45  // and root hash. Requires 0 <= index < size.
    46  func VerifyInclusion(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte, root []byte) error {
    47  	calcRoot, err := RootFromInclusionProof(hasher, index, size, leafHash, proof)
    48  	if err != nil {
    49  		return err
    50  	}
    51  	return verifyMatch(calcRoot, root)
    52  }
    53  
    54  // RootFromInclusionProof calculates the expected root hash for a tree of the
    55  // given size, provided a leaf index and hash with the corresponding inclusion
    56  // proof. Requires 0 <= index < size.
    57  func RootFromInclusionProof(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte) ([]byte, error) {
    58  	if index >= size {
    59  		return nil, fmt.Errorf("index is beyond size: %d >= %d", index, size)
    60  	}
    61  	if got, want := len(leafHash), hasher.Size(); got != want {
    62  		return nil, fmt.Errorf("leafHash has unexpected size %d, want %d", got, want)
    63  	}
    64  
    65  	inner, border := decompInclProof(index, size)
    66  	if got, want := len(proof), inner+border; got != want {
    67  		return nil, fmt.Errorf("wrong proof size %d, want %d", got, want)
    68  	}
    69  
    70  	res := chainInner(hasher, leafHash, proof[:inner], index)
    71  	res = chainBorderRight(hasher, res, proof[inner:])
    72  	return res, nil
    73  }
    74  
    75  // VerifyConsistency checks that the passed-in consistency proof is valid
    76  // between the passed in tree sizes, with respect to the corresponding root
    77  // hashes. Requires 0 <= size1 <= size2.
    78  func VerifyConsistency(hasher merkle.LogHasher, size1, size2 uint64, proof [][]byte, root1, root2 []byte) error {
    79  	switch {
    80  	case size2 < size1:
    81  		return fmt.Errorf("size2 (%d) < size1 (%d)", size1, size2)
    82  	case size1 == size2:
    83  		if len(proof) > 0 {
    84  			return errors.New("size1=size2, but proof is not empty")
    85  		}
    86  		return verifyMatch(root1, root2)
    87  	case size1 == 0:
    88  		// Any size greater than 0 is consistent with size 0.
    89  		if len(proof) > 0 {
    90  			return fmt.Errorf("expected empty proof, but got %d components", len(proof))
    91  		}
    92  		return nil // Proof OK.
    93  	case len(proof) == 0:
    94  		return errors.New("empty proof")
    95  	}
    96  
    97  	inner, border := decompInclProof(size1-1, size2)
    98  	shift := bits.TrailingZeros64(size1)
    99  	inner -= shift // Note: shift < inner if size1 < size2.
   100  
   101  	// The proof includes the root hash for the sub-tree of size 2^shift.
   102  	seed, start := proof[0], 1
   103  	if size1 == 1<<uint(shift) { // Unless size1 is that very 2^shift.
   104  		seed, start = root1, 0
   105  	}
   106  	if got, want := len(proof), start+inner+border; got != want {
   107  		return fmt.Errorf("wrong proof size %d, want %d", got, want)
   108  	}
   109  	proof = proof[start:]
   110  	// Now len(proof) == inner+border, and proof is effectively a suffix of
   111  	// inclusion proof for entry |size1-1| in a tree of size |size2|.
   112  
   113  	// Verify the first root.
   114  	mask := (size1 - 1) >> uint(shift) // Start chaining from level |shift|.
   115  	hash1 := chainInnerRight(hasher, seed, proof[:inner], mask)
   116  	hash1 = chainBorderRight(hasher, hash1, proof[inner:])
   117  	if err := verifyMatch(hash1, root1); err != nil {
   118  		return err
   119  	}
   120  
   121  	// Verify the second root.
   122  	hash2 := chainInner(hasher, seed, proof[:inner], mask)
   123  	hash2 = chainBorderRight(hasher, hash2, proof[inner:])
   124  	return verifyMatch(hash2, root2)
   125  }
   126  
   127  // decompInclProof breaks down inclusion proof for a leaf at the specified
   128  // |index| in a tree of the specified |size| into 2 components. The splitting
   129  // point between them is where paths to leaves |index| and |size-1| diverge.
   130  // Returns lengths of the bottom and upper proof parts correspondingly. The sum
   131  // of the two determines the correct length of the inclusion proof.
   132  func decompInclProof(index, size uint64) (int, int) {
   133  	inner := innerProofSize(index, size)
   134  	border := bits.OnesCount64(index >> uint(inner))
   135  	return inner, border
   136  }
   137  
   138  func innerProofSize(index, size uint64) int {
   139  	return bits.Len64(index ^ (size - 1))
   140  }
   141  
   142  // chainInner computes a subtree hash for a node on or below the tree's right
   143  // border. Assumes |proof| hashes are ordered from lower levels to upper, and
   144  // |seed| is the initial subtree/leaf hash on the path located at the specified
   145  // |index| on its level.
   146  func chainInner(hasher merkle.LogHasher, seed []byte, proof [][]byte, index uint64) []byte {
   147  	for i, h := range proof {
   148  		if (index>>uint(i))&1 == 0 {
   149  			seed = hasher.HashChildren(seed, h)
   150  		} else {
   151  			seed = hasher.HashChildren(h, seed)
   152  		}
   153  	}
   154  	return seed
   155  }
   156  
   157  // chainInnerRight computes a subtree hash like chainInner, but only takes
   158  // hashes to the left from the path into consideration, which effectively means
   159  // the result is a hash of the corresponding earlier version of this subtree.
   160  func chainInnerRight(hasher merkle.LogHasher, seed []byte, proof [][]byte, index uint64) []byte {
   161  	for i, h := range proof {
   162  		if (index>>uint(i))&1 == 1 {
   163  			seed = hasher.HashChildren(h, seed)
   164  		}
   165  	}
   166  	return seed
   167  }
   168  
   169  // chainBorderRight chains proof hashes along tree borders. This differs from
   170  // inner chaining because |proof| contains only left-side subtree hashes.
   171  func chainBorderRight(hasher merkle.LogHasher, seed []byte, proof [][]byte) []byte {
   172  	for _, h := range proof {
   173  		seed = hasher.HashChildren(h, seed)
   174  	}
   175  	return seed
   176  }
   177
View as plain text