verify_test.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  	"encoding/hex"
    20  	"fmt"
    21  	"strings"
    22  	"testing"
    23  
    24  	"github.com/transparency-dev/merkle"
    25  	"github.com/transparency-dev/merkle/rfc6962"
    26  )
    27  
    28  type inclusionProofTestVector struct {
    29  	leaf  uint64
    30  	size  uint64
    31  	proof [][]byte
    32  }
    33  
    34  type consistencyTestVector struct {
    35  	size1 uint64
    36  	size2 uint64
    37  	proof [][]byte
    38  }
    39  
    40  var (
    41  	hasher              = rfc6962.DefaultHasher
    42  	sha256SomeHash      = dh("abacaba000000000000000000000000000000000000000000060061e00123456", 32)
    43  	sha256EmptyTreeHash = dh("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32)
    44  
    45  	inclusionProofs = []inclusionProofTestVector{
    46  		{0, 0, nil},
    47  		{1, 1, nil},
    48  		{1, 8, [][]byte{
    49  			dh("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32),
    50  			dh("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32),
    51  			dh("6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4", 32),
    52  		}},
    53  		{6, 8, [][]byte{
    54  			dh("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32),
    55  			dh("ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32),
    56  			dh("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32),
    57  		}},
    58  		{3, 3, [][]byte{
    59  			dh("fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32),
    60  		}},
    61  		{2, 5, [][]byte{
    62  			dh("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32),
    63  			dh("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32),
    64  			dh("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32),
    65  		}},
    66  	}
    67  
    68  	consistencyProofs = []consistencyTestVector{
    69  		{1, 1, nil},
    70  		{1, 8, [][]byte{
    71  			dh("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32),
    72  			dh("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32),
    73  			dh("6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4", 32),
    74  		}},
    75  		{6, 8, [][]byte{
    76  			dh("0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 32),
    77  			dh("ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32),
    78  			dh("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32),
    79  		}},
    80  		{2, 5, [][]byte{
    81  			dh("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32),
    82  			dh("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32),
    83  		}},
    84  		{6, 7, [][]byte{
    85  			dh("0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 32),
    86  			dh("b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f", 32),
    87  			dh("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32),
    88  		}},
    89  	}
    90  
    91  	roots = [][]byte{
    92  		dh("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32),
    93  		dh("fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32),
    94  		dh("aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32),
    95  		dh("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32),
    96  		dh("4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32),
    97  		dh("76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32),
    98  		dh("ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32),
    99  		dh("5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32),
   100  	}
   101  
   102  	leaves = [][]byte{
   103  		dh("", 0),
   104  		dh("00", 1),
   105  		dh("10", 1),
   106  		dh("2021", 2),
   107  		dh("3031", 2),
   108  		dh("40414243", 4),
   109  		dh("5051525354555657", 8),
   110  		dh("606162636465666768696a6b6c6d6e6f", 16),
   111  	}
   112  )
   113  
   114  // inclusionProbe is a parameter set for inclusion proof verification.
   115  type inclusionProbe struct {
   116  	leafIndex uint64
   117  	treeSize  uint64
   118  	root      []byte
   119  	leafHash  []byte
   120  	proof     [][]byte
   121  
   122  	desc string
   123  }
   124  
   125  // consistencyProbe is a parameter set for consistency proof verification.
   126  type consistencyProbe struct {
   127  	size1 uint64
   128  	size2 uint64
   129  	root1 []byte
   130  	root2 []byte
   131  	proof [][]byte
   132  
   133  	desc string
   134  }
   135  
   136  func corruptInclusionProof(leafIndex, treeSize uint64, proof [][]byte, root, leafHash []byte) []inclusionProbe {
   137  	ret := []inclusionProbe{
   138  		// Wrong leaf index.
   139  		{leafIndex - 1, treeSize, root, leafHash, proof, "leafIndex - 1"},
   140  		{leafIndex + 1, treeSize, root, leafHash, proof, "leafIndex + 1"},
   141  		{leafIndex ^ 2, treeSize, root, leafHash, proof, "leafIndex ^ 2"},
   142  		// Wrong tree height.
   143  		{leafIndex, treeSize * 2, root, leafHash, proof, "treeSize * 2"},
   144  		{leafIndex, treeSize / 2, root, leafHash, proof, "treeSize / 2"},
   145  		// Wrong leaf or root.
   146  		{leafIndex, treeSize, root, []byte("WrongLeaf"), proof, "wrong leaf"},
   147  		{leafIndex, treeSize, sha256EmptyTreeHash, leafHash, proof, "empty root"},
   148  		{leafIndex, treeSize, sha256SomeHash, leafHash, proof, "random root"},
   149  		// Add garbage at the end.
   150  		{leafIndex, treeSize, root, leafHash, extend(proof, []byte{}), "trailing garbage"},
   151  		{leafIndex, treeSize, root, leafHash, extend(proof, root), "trailing root"},
   152  		// Add garbage at the front.
   153  		{leafIndex, treeSize, root, leafHash, prepend(proof, []byte{}), "preceding garbage"},
   154  		{leafIndex, treeSize, root, leafHash, prepend(proof, root), "preceding root"},
   155  	}
   156  	ln := len(proof)
   157  
   158  	// Modify single bit in an element of the proof.
   159  	for i := 0; i < ln; i++ {
   160  		wrongProof := prepend(proof)                          // Copy the proof slice.
   161  		wrongProof[i] = append([]byte(nil), wrongProof[i]...) // But also the modified data.
   162  		wrongProof[i][0] ^= 8                                 // Flip the bit.
   163  		desc := fmt.Sprintf("modified proof[%d] bit 3", i)
   164  		ret = append(ret, inclusionProbe{leafIndex, treeSize, root, leafHash, wrongProof, desc})
   165  	}
   166  
   167  	if ln > 0 {
   168  		ret = append(ret, inclusionProbe{leafIndex, treeSize, root, leafHash, proof[:ln-1], "removed component"})
   169  	}
   170  	if ln > 1 {
   171  		wrongProof := prepend(proof[1:], proof[0], sha256SomeHash)
   172  		ret = append(ret, inclusionProbe{leafIndex, treeSize, root, leafHash, wrongProof, "inserted component"})
   173  	}
   174  
   175  	return ret
   176  }
   177  
   178  func corruptConsistencyProof(size1, size2 uint64, root1, root2 []byte, proof [][]byte) []consistencyProbe {
   179  	ln := len(proof)
   180  	ret := []consistencyProbe{
   181  		// Wrong size1.
   182  		{size1 - 1, size2, root1, root2, proof, "size1 - 1"},
   183  		{size1 + 1, size2, root1, root2, proof, "size1 + 1"},
   184  		{size1 ^ 2, size2, root1, root2, proof, "size1 ^ 2"},
   185  		// Wrong tree height.
   186  		{size1, size2 * 2, root1, root2, proof, "size2 * 2"},
   187  		{size1, size2 / 2, root1, root2, proof, "size2 / 2"},
   188  		// Wrong root.
   189  		{size1, size2, []byte("WrongRoot"), root2, proof, "wrong root1"},
   190  		{size1, size2, root1, []byte("WrongRoot"), proof, "wrong root2"},
   191  		{size1, size2, root2, root1, proof, "swapped roots"},
   192  		// Empty proof.
   193  		{size1, size2, root1, root2, [][]byte{}, "empty proof"},
   194  		// Add garbage at the end.
   195  		{size1, size2, root1, root2, extend(proof, []byte{}), "trailing garbage"},
   196  		{size1, size2, root1, root2, extend(proof, root1), "trailing root1"},
   197  		{size1, size2, root1, root2, extend(proof, root2), "trailing root2"},
   198  		// Add garbage at the front.
   199  		{size1, size2, root1, root2, prepend(proof, []byte{}), "preceding garbage"},
   200  		{size1, size2, root1, root2, prepend(proof, root1), "preceding root1"},
   201  		{size1, size2, root1, root2, prepend(proof, root2), "preceding root2"},
   202  		{size1, size2, root1, root2, prepend(proof, proof[0]), "preceding proof[0]"},
   203  	}
   204  
   205  	// Remove a node from the end.
   206  	if ln > 0 {
   207  		ret = append(ret, consistencyProbe{size1, size2, root1, root2, proof[:ln-1], "truncated proof"})
   208  	}
   209  
   210  	// Modify single bit in an element of the proof.
   211  	for i := 0; i < ln; i++ {
   212  		wrongProof := prepend(proof)                          // Copy the proof slice.
   213  		wrongProof[i] = append([]byte(nil), wrongProof[i]...) // But also the modified data.
   214  		wrongProof[i][0] ^= 16                                // Flip the bit.
   215  		desc := fmt.Sprintf("modified proof[%d] bit 4", i)
   216  		ret = append(ret, consistencyProbe{size1, size2, root1, root2, wrongProof, desc})
   217  	}
   218  
   219  	return ret
   220  }
   221  
   222  func verifierCheck(hasher merkle.LogHasher, leafIndex, treeSize uint64, proof [][]byte, root, leafHash []byte) error {
   223  	// Verify original inclusion proof.
   224  	got, err := RootFromInclusionProof(hasher, leafIndex, treeSize, leafHash, proof)
   225  	if err != nil {
   226  		return err
   227  	}
   228  	if !bytes.Equal(got, root) {
   229  		return fmt.Errorf("got root:\n%x\nexpected:\n%x", got, root)
   230  	}
   231  	if err := VerifyInclusion(hasher, leafIndex, treeSize, leafHash, proof, root); err != nil {
   232  		return err
   233  	}
   234  
   235  	probes := corruptInclusionProof(leafIndex, treeSize, proof, root, leafHash)
   236  	var wrong []string
   237  	for _, p := range probes {
   238  		if err := VerifyInclusion(hasher, p.leafIndex, p.treeSize, p.leafHash, p.proof, p.root); err == nil {
   239  			wrong = append(wrong, p.desc)
   240  		}
   241  	}
   242  	if len(wrong) > 0 {
   243  		return fmt.Errorf("incorrectly verified against: %s", strings.Join(wrong, ", "))
   244  	}
   245  	return nil
   246  }
   247  
   248  func verifierConsistencyCheck(hasher merkle.LogHasher, size1, size2 uint64, proof [][]byte, root1, root2 []byte) error {
   249  	// Verify original consistency proof.
   250  	if err := VerifyConsistency(hasher, size1, size2, proof, root1, root2); err != nil {
   251  		return err
   252  	}
   253  	// For simplicity test only non-trivial proofs that have root1 != root2,
   254  	// size1 != 0 and size1 != size2.
   255  	if len(proof) == 0 {
   256  		return nil
   257  	}
   258  
   259  	probes := corruptConsistencyProof(size1, size2, root1, root2, proof)
   260  	var wrong []string
   261  	for _, p := range probes {
   262  		if err := VerifyConsistency(hasher, p.size1, p.size2, p.proof, p.root1, p.root2); err == nil {
   263  			wrong = append(wrong, p.desc)
   264  		}
   265  	}
   266  	if len(wrong) > 0 {
   267  		return fmt.Errorf("incorrectly verified against: %s", strings.Join(wrong, ", "))
   268  	}
   269  	return nil
   270  }
   271  
   272  func TestVerifyInclusionSingleEntry(t *testing.T) {
   273  	data := []byte("data")
   274  	// Root and leaf hash for 1-entry tree are the same.
   275  	hash := hasher.HashLeaf(data)
   276  	// The corresponding inclusion proof is empty.
   277  	proof := [][]byte{}
   278  	emptyHash := []byte{}
   279  
   280  	for i, tc := range []struct {
   281  		root    []byte
   282  		leaf    []byte
   283  		wantErr bool
   284  	}{
   285  		{hash, hash, false},
   286  		{hash, emptyHash, true},
   287  		{emptyHash, hash, true},
   288  		{emptyHash, emptyHash, true}, // Wrong hash size.
   289  	} {
   290  		t.Run(fmt.Sprintf("test:%d", i), func(t *testing.T) {
   291  			err := VerifyInclusion(hasher, 0, 1, tc.leaf, proof, tc.root)
   292  			if got, want := err != nil, tc.wantErr; got != want {
   293  				t.Errorf("error: %v, want %v", got, want)
   294  			}
   295  		})
   296  	}
   297  }
   298  
   299  func TestVerifyInclusion(t *testing.T) {
   300  	proof := [][]byte{}
   301  
   302  	probes := []struct {
   303  		index, size uint64
   304  	}{{0, 0}, {0, 1}, {1, 0}, {2, 1}}
   305  	for _, p := range probes {
   306  		t.Run(fmt.Sprintf("probe:%d:%d", p.index, p.size), func(t *testing.T) {
   307  			if err := VerifyInclusion(hasher, p.index, p.size, sha256SomeHash, proof, []byte{}); err == nil {
   308  				t.Error("Incorrectly verified invalid root/leaf")
   309  			}
   310  			if err := VerifyInclusion(hasher, p.index, p.size, []byte{}, proof, sha256EmptyTreeHash); err == nil {
   311  				t.Error("Incorrectly verified invalid root/leaf")
   312  			}
   313  			if err := VerifyInclusion(hasher, p.index, p.size, sha256SomeHash, proof, sha256EmptyTreeHash); err == nil {
   314  				t.Error("Incorrectly verified invalid root/leaf")
   315  			}
   316  		})
   317  	}
   318  
   319  	// i = 0 is an invalid path.
   320  	for i := 1; i < 6; i++ {
   321  		p := inclusionProofs[i]
   322  		t.Run(fmt.Sprintf("proof:%d", i), func(t *testing.T) {
   323  			leafHash := rfc6962.DefaultHasher.HashLeaf(leaves[p.leaf-1])
   324  			if err := verifierCheck(hasher, p.leaf-1, p.size, p.proof, roots[p.size-1], leafHash); err != nil {
   325  				t.Errorf("verifierCheck(): %s", err)
   326  			}
   327  		})
   328  	}
   329  }
   330  
   331  func TestVerifyConsistency(t *testing.T) {
   332  	root1 := []byte("don't care 1")
   333  	root2 := []byte("don't care 2")
   334  	proof1 := [][]byte{}
   335  	proof2 := [][]byte{sha256EmptyTreeHash}
   336  
   337  	tests := []struct {
   338  		size1, size2 uint64
   339  		root1, root2 []byte
   340  		proof        [][]byte
   341  		wantErr      bool
   342  	}{
   343  		{0, 0, root1, root2, proof1, true},
   344  		{1, 1, root1, root2, proof1, true},
   345  		// Sizes that are always consistent.
   346  		{0, 0, root1, root1, proof1, false},
   347  		{0, 1, root1, root2, proof1, false},
   348  		{1, 1, root2, root2, proof1, false},
   349  		// Time travel to the past.
   350  		{1, 0, root1, root2, proof1, true},
   351  		{2, 1, root1, root2, proof1, true},
   352  		// Empty proof.
   353  		{1, 2, root1, root2, proof1, true},
   354  		// Roots don't match.
   355  		{0, 0, sha256EmptyTreeHash, root2, proof1, true},
   356  		{1, 1, sha256EmptyTreeHash, root2, proof1, true},
   357  		// Roots match but the proof is not empty.
   358  		{0, 0, sha256EmptyTreeHash, sha256EmptyTreeHash, proof2, true},
   359  		{0, 1, sha256EmptyTreeHash, sha256EmptyTreeHash, proof2, true},
   360  		{1, 1, sha256EmptyTreeHash, sha256EmptyTreeHash, proof2, true},
   361  	}
   362  	for i, p := range tests {
   363  		t.Run(fmt.Sprintf("test:%d:size:%d-%d", i, p.size1, p.size2), func(t *testing.T) {
   364  			err := verifierConsistencyCheck(hasher, p.size1, p.size2, p.proof, p.root1, p.root2)
   365  			if p.wantErr && err == nil {
   366  				t.Errorf("Incorrectly verified")
   367  			} else if !p.wantErr && err != nil {
   368  				t.Errorf("Failed to verify: %v", err)
   369  			}
   370  		})
   371  	}
   372  
   373  	for i, p := range consistencyProofs {
   374  		t.Run(fmt.Sprintf("proof:%d", i), func(t *testing.T) {
   375  			err := verifierConsistencyCheck(hasher, p.size1, p.size2, p.proof,
   376  				roots[p.size1-1], roots[p.size2-1])
   377  			if err != nil {
   378  				t.Fatalf("Failed to verify known good proof: %s", err)
   379  			}
   380  		})
   381  	}
   382  }
   383  
   384  // extend explicitly copies |proof| slice and appends |hashes| to it.
   385  func extend(proof [][]byte, hashes ...[]byte) [][]byte {
   386  	res := make([][]byte, len(proof), len(proof)+len(hashes))
   387  	copy(res, proof)
   388  	return append(res, hashes...)
   389  }
   390  
   391  // prepend adds |proof| to the tail of |hashes|.
   392  func prepend(proof [][]byte, hashes ...[]byte) [][]byte {
   393  	return append(hashes, proof...)
   394  }
   395  
   396  func dh(h string, expLen int) []byte {
   397  	r, err := hex.DecodeString(h)
   398  	if err != nil {
   399  		panic(err)
   400  	}
   401  	if got := len(r); got != expLen {
   402  		panic(fmt.Sprintf("decode %q: len=%d, want %d", h, got, expLen))
   403  	}
   404  	return r
   405  }
   406
View as plain text