proof_test.go

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

     1  // Copyright 2022 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  	"fmt"
    19  	"testing"
    20  
    21  	"github.com/google/go-cmp/cmp"
    22  	"github.com/transparency-dev/merkle/compact"
    23  	"github.com/transparency-dev/merkle/rfc6962"
    24  )
    25  
    26  // TestInclusion contains inclusion proof tests. For reference, consider the
    27  // following example of a tree from RFC 6962:
    28  //
    29  //	           hash              <== Level 3
    30  //	          /    \
    31  //	         /      \
    32  //	        /        \
    33  //	       /          \
    34  //	      /            \
    35  //	     k              l        <== Level 2
    36  //	    / \            / \
    37  //	   /   \          /   \
    38  //	  /     \        /     \
    39  //	 g       h      i      [ ]   <== Level 1
    40  //	/ \     / \    / \    /
    41  //	a b     c d    e f    j      <== Level 0
    42  //	| |     | |    | |    |
    43  //	d0 d1   d2 d3  d4 d5  d6
    44  //
    45  // Our storage node layers are always populated from the bottom up, hence the
    46  // gap at level 1, index 3 in the above picture.
    47  func TestInclusion(t *testing.T) {
    48  	id := compact.NewNodeID
    49  	nodes := func(ids ...compact.NodeID) Nodes {
    50  		return Nodes{IDs: ids}
    51  	}
    52  	rehash := func(begin, end int, ids ...compact.NodeID) Nodes {
    53  		return Nodes{IDs: ids, begin: begin, end: end}
    54  	}
    55  	for _, tc := range []struct {
    56  		size    uint64 // The requested past tree size.
    57  		index   uint64 // Leaf index in the requested tree.
    58  		want    Nodes
    59  		wantErr bool
    60  	}{
    61  		// Errors.
    62  		{size: 0, index: 0, wantErr: true},
    63  		{size: 0, index: 1, wantErr: true},
    64  		{size: 1, index: 2, wantErr: true},
    65  		{size: 0, index: 3, wantErr: true},
    66  		{size: 7, index: 8, wantErr: true},
    67  
    68  		// Small trees.
    69  		{size: 1, index: 0, want: Nodes{IDs: []compact.NodeID{}}},
    70  		{size: 2, index: 0, want: nodes(id(0, 1))},                  // b
    71  		{size: 2, index: 1, want: nodes(id(0, 0))},                  // a
    72  		{size: 3, index: 1, want: rehash(1, 2, id(0, 0), id(0, 2))}, // a c
    73  
    74  		// Tree of size 7.
    75  		{size: 7, index: 0, want: rehash(2, 4, // l=hash(i,j)
    76  			id(0, 1), id(1, 1), id(0, 6), id(1, 2))}, // b h j i
    77  		{size: 7, index: 1, want: rehash(2, 4, // l=hash(i,j)
    78  			id(0, 0), id(1, 1), id(0, 6), id(1, 2))}, // a h j i
    79  		{size: 7, index: 2, want: rehash(2, 4, // l=hash(i,j)
    80  			id(0, 3), id(1, 0), id(0, 6), id(1, 2))}, // d g j i
    81  		{size: 7, index: 3, want: rehash(2, 4, // l=hash(i,j)
    82  			id(0, 2), id(1, 0), id(0, 6), id(1, 2))}, // c g j i
    83  		{size: 7, index: 4, want: rehash(1, 2, id(0, 5), id(0, 6), id(2, 0))}, // f j k
    84  		{size: 7, index: 5, want: rehash(1, 2, id(0, 4), id(0, 6), id(2, 0))}, // e j k
    85  		{size: 7, index: 6, want: nodes(id(1, 2), id(2, 0))},                  // i k
    86  
    87  		// Smaller trees within a bigger stored tree.
    88  		{size: 4, index: 2, want: nodes(id(0, 3), id(1, 0))},                  // d g
    89  		{size: 5, index: 3, want: rehash(2, 3, id(0, 2), id(1, 0), id(0, 4))}, // c g e
    90  		{size: 6, index: 3, want: rehash(2, 3, id(0, 2), id(1, 0), id(1, 2))}, // c g i
    91  		{size: 6, index: 4, want: nodes(id(0, 5), id(2, 0))},                  // f k
    92  		{size: 7, index: 1, want: rehash(2, 4, // l=hash(i,j)
    93  			id(0, 0), id(1, 1), id(0, 6), id(1, 2))}, // a h j i
    94  		{size: 7, index: 3, want: rehash(2, 4, // l=hash(i,j)
    95  			id(0, 2), id(1, 0), id(0, 6), id(1, 2))}, // c g j i
    96  
    97  		// Some rehashes in the middle of the returned list.
    98  		{size: 15, index: 10, want: rehash(2, 4,
    99  			id(0, 11), id(1, 4),
   100  			id(0, 14), id(1, 6),
   101  			id(3, 0),
   102  		)},
   103  		{size: 31, index: 24, want: rehash(2, 4,
   104  			id(0, 25), id(1, 13),
   105  			id(0, 30), id(1, 14),
   106  			id(3, 2), id(4, 0),
   107  		)},
   108  		{size: 95, index: 81, want: rehash(3, 6,
   109  			id(0, 80), id(1, 41), id(2, 21),
   110  			id(0, 94), id(1, 46), id(2, 22),
   111  			id(4, 4), id(6, 0),
   112  		)},
   113  	} {
   114  		t.Run(fmt.Sprintf("%d:%d", tc.size, tc.index), func(t *testing.T) {
   115  			proof, err := Inclusion(tc.index, tc.size)
   116  			if tc.wantErr {
   117  				if err == nil {
   118  					t.Fatal("accepted bad params")
   119  				}
   120  				return
   121  			} else if err != nil {
   122  				t.Fatalf("Inclusion: %v", err)
   123  			}
   124  			// Ignore the ephemeral node, it is tested separately.
   125  			proof.ephem = compact.NodeID{}
   126  			if diff := cmp.Diff(tc.want, proof, cmp.AllowUnexported(Nodes{})); diff != "" {
   127  				t.Errorf("paths mismatch:\n%v", diff)
   128  			}
   129  		})
   130  	}
   131  }
   132  
   133  // TestConsistency contains consistency proof tests. For reference, consider
   134  // the following example:
   135  //
   136  //	           hash5                         hash7
   137  //	          /    \                        /    \
   138  //	         /      \                      /      \
   139  //	        /        \                    /        \
   140  //	       /          \                  /          \
   141  //	      /            \                /            \
   142  //	     k             [ ]    -->      k              l
   143  //	    / \            /              / \            / \
   144  //	   /   \          /              /   \          /   \
   145  //	  /     \        /              /     \        /     \
   146  //	 g       h     [ ]             g       h      i      [ ]
   147  //	/ \     / \    /              / \     / \    / \    /
   148  //	a b     c d    e              a b     c d    e f    j
   149  //	| |     | |    |              | |     | |    | |    |
   150  //	d0 d1   d2 d3  d4             d0 d1   d2 d3  d4 d5  d6
   151  //
   152  // The consistency proof between tree size 5 and 7 consists of nodes e, f, j,
   153  // and k. The node j is taken instead of its missing parent.
   154  func TestConsistency(t *testing.T) {
   155  	id := compact.NewNodeID
   156  	nodes := func(ids ...compact.NodeID) Nodes {
   157  		return Nodes{IDs: ids}
   158  	}
   159  	rehash := func(begin, end int, ids ...compact.NodeID) Nodes {
   160  		return Nodes{IDs: ids, begin: begin, end: end}
   161  	}
   162  	for _, tc := range []struct {
   163  		size1   uint64 // The smaller of the two tree sizes.
   164  		size2   uint64 // The bigger of the two tree sizes.
   165  		want    Nodes
   166  		wantErr bool
   167  	}{
   168  		// Errors.
   169  		{size1: 5, size2: 0, wantErr: true},
   170  		{size1: 9, size2: 8, wantErr: true},
   171  
   172  		{size1: 1, size2: 2, want: nodes(id(0, 1))},                            // b
   173  		{size1: 1, size2: 4, want: nodes(id(0, 1), id(1, 1))},                  // b h
   174  		{size1: 1, size2: 6, want: rehash(2, 3, id(0, 1), id(1, 1), id(1, 2))}, // b h i
   175  		{size1: 2, size2: 3, want: rehash(0, 1, id(0, 2))},                     // c
   176  		{size1: 2, size2: 8, want: nodes(id(1, 1), id(2, 1))},                  // h l
   177  		{size1: 3, size2: 7, want: rehash(3, 5, // l=hash(i,j)
   178  			id(0, 2), id(0, 3), id(1, 0), id(0, 6), id(1, 2))}, // c d g j i
   179  		{size1: 4, size2: 7, want: rehash(0, 2, // l=hash(i,j)
   180  			id(0, 6), id(1, 2))}, // j i
   181  		{size1: 5, size2: 7, want: rehash(2, 3,
   182  			id(0, 4), id(0, 5), id(0, 6), id(2, 0))}, // e f j k
   183  		{size1: 6, size2: 7, want: rehash(1, 2,
   184  			id(1, 2), id(0, 6), id(2, 0))}, // i j k
   185  		{size1: 7, size2: 8, want: nodes(
   186  			id(0, 6), id(0, 7), id(1, 2), id(2, 0))}, // j leaf#7 i k
   187  
   188  		// Same tree size.
   189  		{size1: 1, size2: 1, want: Nodes{IDs: []compact.NodeID{}}},
   190  		{size1: 2, size2: 2, want: Nodes{IDs: []compact.NodeID{}}},
   191  		{size1: 3, size2: 3, want: Nodes{IDs: []compact.NodeID{}}},
   192  		{size1: 4, size2: 4, want: Nodes{IDs: []compact.NodeID{}}},
   193  		{size1: 5, size2: 5, want: Nodes{IDs: []compact.NodeID{}}},
   194  		{size1: 7, size2: 7, want: Nodes{IDs: []compact.NodeID{}}},
   195  		{size1: 8, size2: 8, want: Nodes{IDs: []compact.NodeID{}}},
   196  
   197  		// Smaller trees within a bigger stored tree.
   198  		{size1: 2, size2: 4, want: nodes(id(1, 1))}, // h
   199  		{size1: 3, size2: 5, want: rehash(3, 4,
   200  			id(0, 2), id(0, 3), id(1, 0), id(0, 4))}, // c d g e
   201  		{size1: 3, size2: 6, want: rehash(3, 4,
   202  			id(0, 2), id(0, 3), id(1, 0), id(1, 2))}, // c d g i
   203  		{size1: 4, size2: 6, want: rehash(0, 1, id(1, 2))}, // i
   204  		{size1: 1, size2: 7, want: rehash(2, 4, // l=hash(i,j)
   205  			id(0, 1), id(1, 1), id(0, 6), id(1, 2))}, // b h j i
   206  
   207  		// Some rehashes in the middle of the returned list.
   208  		{size1: 10, size2: 15, want: rehash(2, 4,
   209  			id(1, 4), id(1, 5), id(0, 14), id(1, 6), id(3, 0))},
   210  		{size1: 24, size2: 31, want: rehash(1, 4,
   211  			id(3, 2),
   212  			id(0, 30), id(1, 14), id(2, 6),
   213  			id(4, 0),
   214  		)},
   215  		{size1: 81, size2: 95, want: rehash(4, 7,
   216  			id(0, 80), id(0, 81), id(1, 41), id(2, 21),
   217  			id(0, 94), id(1, 46), id(2, 22),
   218  			id(4, 4), id(6, 0),
   219  		)},
   220  	} {
   221  		t.Run(fmt.Sprintf("%d:%d", tc.size1, tc.size2), func(t *testing.T) {
   222  			proof, err := Consistency(tc.size1, tc.size2)
   223  			if tc.wantErr {
   224  				if err == nil {
   225  					t.Fatal("accepted bad params")
   226  				}
   227  				return
   228  			} else if err != nil {
   229  				t.Fatalf("Consistency: %v", err)
   230  			}
   231  			// Ignore the ephemeral node, it is tested separately.
   232  			proof.ephem = compact.NodeID{}
   233  			if diff := cmp.Diff(tc.want, proof, cmp.AllowUnexported(Nodes{})); diff != "" {
   234  				t.Errorf("paths mismatch:\n%v", diff)
   235  			}
   236  		})
   237  	}
   238  }
   239  
   240  func TestInclusionSucceedsUpToTreeSize(t *testing.T) {
   241  	const maxSize = uint64(555)
   242  	for ts := uint64(1); ts <= maxSize; ts++ {
   243  		for i := ts; i < ts; i++ {
   244  			if _, err := Inclusion(i, ts); err != nil {
   245  				t.Errorf("Inclusion(ts:%d, i:%d) = %v", ts, i, err)
   246  			}
   247  		}
   248  	}
   249  }
   250  
   251  func TestConsistencySucceedsUpToTreeSize(t *testing.T) {
   252  	const maxSize = uint64(100)
   253  	for s1 := uint64(1); s1 < maxSize; s1++ {
   254  		for s2 := s1 + 1; s2 <= maxSize; s2++ {
   255  			if _, err := Consistency(s1, s2); err != nil {
   256  				t.Errorf("Consistency(%d, %d) = %v", s1, s2, err)
   257  			}
   258  		}
   259  	}
   260  }
   261  
   262  func TestEphem(t *testing.T) {
   263  	id := compact.NewNodeID
   264  	for _, tc := range []struct {
   265  		index uint64
   266  		size  uint64
   267  		want  compact.NodeID
   268  	}{
   269  		// Edge case: For perfect trees the ephemeral node is the sibling of the
   270  		// root. However, it will not be used in the proof, as the corresponding
   271  		// subtree is empty.
   272  		{index: 3, size: 32, want: id(5, 1)},
   273  
   274  		{index: 0, size: 9, want: id(3, 1)},
   275  		{index: 0, size: 13, want: id(3, 1)},
   276  		{index: 7, size: 13, want: id(3, 1)},
   277  		{index: 8, size: 13, want: id(2, 3)},
   278  		{index: 11, size: 13, want: id(2, 3)},
   279  		// More edge cases when the computed ephemeral node is not used in the
   280  		// proof, because it is fully outside the tree border.
   281  		{index: 12, size: 13, want: id(0, 13)},
   282  		{index: 13, size: 14, want: id(1, 7)},
   283  
   284  		// There is only one node (level 0, index 1024) in the right subtree, but
   285  		// the ephemeral node is at level 10 rather than level 0. This is because
   286  		// for the purposes of the proof this node is *effectively* at level 10.
   287  		{index: 123, size: 1025, want: id(10, 1)},
   288  
   289  		{index: 0, size: 0xFFFF, want: id(15, 1)},
   290  		{index: 0xF000, size: 0xFFFF, want: id(11, 0x1F)},
   291  		{index: 0xFF00, size: 0xFFFF, want: id(7, 0x1FF)},
   292  		{index: 0xFFF0, size: 0xFFFF, want: id(3, 0x1FFF)},
   293  		{index: 0xFFFF - 1, size: 0xFFFF, want: id(0, 0xFFFF)},
   294  	} {
   295  		t.Run(fmt.Sprintf("%d:%d", tc.index, tc.size), func(t *testing.T) {
   296  			nodes, err := Inclusion(tc.index, tc.size)
   297  			if err != nil {
   298  				t.Fatalf("Inclusion: %v", err)
   299  			}
   300  			got, _, _ := nodes.Ephem()
   301  			if want := tc.want; got != want {
   302  				t.Errorf("Ephem: got %+v, want %+v", got, want)
   303  			}
   304  		})
   305  	}
   306  }
   307  
   308  func TestRehash(t *testing.T) {
   309  	th := rfc6962.DefaultHasher
   310  	h := [][]byte{
   311  		th.HashLeaf([]byte("Hash 1")),
   312  		th.HashLeaf([]byte("Hash 2")),
   313  		th.HashLeaf([]byte("Hash 3")),
   314  		th.HashLeaf([]byte("Hash 4")),
   315  		th.HashLeaf([]byte("Hash 5")),
   316  	}
   317  
   318  	for _, tc := range []struct {
   319  		desc   string
   320  		hashes [][]byte
   321  		nodes  Nodes
   322  		want   [][]byte
   323  	}{
   324  		{
   325  			desc:   "no-rehash",
   326  			hashes: h[:3],
   327  			nodes:  inclusion(t, 3, 8),
   328  			want:   h[:3],
   329  		},
   330  		{
   331  			desc:   "rehash",
   332  			hashes: h[:5],
   333  			nodes:  inclusion(t, 9, 15),
   334  			want:   [][]byte{h[0], h[1], th.HashChildren(h[3], h[2]), h[4]},
   335  		},
   336  		{
   337  			desc:   "rehash-at-the-end",
   338  			hashes: h[:4],
   339  			nodes:  inclusion(t, 2, 7),
   340  			want:   [][]byte{h[0], h[1], th.HashChildren(h[3], h[2])},
   341  		},
   342  	} {
   343  		t.Run(tc.desc, func(t *testing.T) {
   344  			h := append([][]byte{}, tc.hashes...)
   345  			got, err := tc.nodes.Rehash(h, th.HashChildren)
   346  			if err != nil {
   347  				t.Fatalf("Rehash: %v", err)
   348  			}
   349  			if want := tc.want; !cmp.Equal(got, want) {
   350  				t.Errorf("proofs mismatch:\ngot: %x\nwant: %x", got, want)
   351  			}
   352  		})
   353  	}
   354  }
   355  
   356  func inclusion(t *testing.T, index, size uint64) Nodes {
   357  	t.Helper()
   358  	n, err := Inclusion(index, size)
   359  	if err != nil {
   360  		t.Fatalf("Inclusion: %v", err)
   361  	}
   362  	return n
   363  }
   364
View as plain text