reference_test.go

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

     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 testonly
    16  
    17  import (
    18  	"fmt"
    19  	"math/bits"
    20  	"testing"
    21  
    22  	"github.com/google/go-cmp/cmp"
    23  	"github.com/transparency-dev/merkle"
    24  	"github.com/transparency-dev/merkle/rfc6962"
    25  )
    26  
    27  // The reference Merkle tree hashing and proof algorithms in this file directly
    28  // implement the definitions from RFC 6962 [1]. We use this implementation only
    29  // for testing correctness of other more flexible and performant algorithms,
    30  // such as the in-memory Tree type and compact ranges.
    31  //
    32  // [1] https://datatracker.ietf.org/doc/html/rfc6962#section-2
    33  
    34  // refRootHash returns the root hash of a Merkle tree with the given entries.
    35  // This is a reference implementation for cross-checking.
    36  func refRootHash(entries [][]byte, hasher merkle.LogHasher) []byte {
    37  	if len(entries) == 0 {
    38  		return hasher.EmptyRoot()
    39  	}
    40  	if len(entries) == 1 {
    41  		return hasher.HashLeaf(entries[0])
    42  	}
    43  	split := downToPowerOfTwo(uint64(len(entries)))
    44  	return hasher.HashChildren(
    45  		refRootHash(entries[:split], hasher),
    46  		refRootHash(entries[split:], hasher))
    47  }
    48  
    49  // refInclusionProof returns the inclusion proof for the given leaf index in a
    50  // Merkle tree with the given entries. This is a reference implementation for
    51  // cross-checking.
    52  func refInclusionProof(entries [][]byte, index uint64, hasher merkle.LogHasher) [][]byte {
    53  	size := uint64(len(entries))
    54  	if size == 1 || index >= size {
    55  		return nil
    56  	}
    57  	split := downToPowerOfTwo(size)
    58  	if index < split {
    59  		return append(
    60  			refInclusionProof(entries[:split], index, hasher),
    61  			refRootHash(entries[split:], hasher))
    62  	}
    63  	return append(
    64  		refInclusionProof(entries[split:], index-split, hasher),
    65  		refRootHash(entries[:split], hasher))
    66  }
    67  
    68  // refConsistencyProof returns the consistency proof for the two tree sizes, in
    69  // a Merkle tree with the given entries. This is a reference implementation for
    70  // cross-checking.
    71  func refConsistencyProof(entries [][]byte, size2, size1 uint64, hasher merkle.LogHasher, haveRoot1 bool) [][]byte {
    72  	if size1 == 0 || size1 > size2 {
    73  		return nil
    74  	}
    75  	// Consistency proof for two equal sizes is empty.
    76  	if size1 == size2 {
    77  		// Record the hash of this subtree if it's not the root for which the proof
    78  		// was originally requested (which happens when size1 is a power of 2).
    79  		if !haveRoot1 {
    80  			return [][]byte{refRootHash(entries[:size1], hasher)}
    81  		}
    82  		return nil
    83  	}
    84  
    85  	// At this point: 0 < size1 < size2.
    86  	split := downToPowerOfTwo(size2)
    87  	if size1 <= split {
    88  		// Root of size1 is in the left subtree of size2. Prove that the left
    89  		// subtrees are consistent, and record the hash of the right subtree (only
    90  		// present in size2).
    91  		return append(
    92  			refConsistencyProof(entries[:split], split, size1, hasher, haveRoot1),
    93  			refRootHash(entries[split:], hasher))
    94  	}
    95  
    96  	// Root of size1 is at the same level as size2 root. Prove that the right
    97  	// subtrees are consistent. The right subtree doesn't contain the root of
    98  	// size1, so set haveRoot1 = false. Record the hash of the left subtree
    99  	// (equal in both trees).
   100  	return append(
   101  		refConsistencyProof(entries[split:], size2-split, size1-split, hasher, false),
   102  		refRootHash(entries[:split], hasher))
   103  }
   104  
   105  // downToPowerOfTwo returns the largest power of two smaller than x.
   106  func downToPowerOfTwo(x uint64) uint64 {
   107  	if x < 2 {
   108  		panic("downToPowerOfTwo requires value >= 2")
   109  	}
   110  	return uint64(1) << (bits.Len64(x-1) - 1)
   111  }
   112  
   113  func TestDownToPowerOfTwo(t *testing.T) {
   114  	for _, inOut := range [][2]uint64{
   115  		{2, 1}, {7, 4}, {8, 4}, {63, 32}, {28937, 16384},
   116  	} {
   117  		if got, want := downToPowerOfTwo(inOut[0]), inOut[1]; got != want {
   118  			t.Errorf("downToPowerOfTwo(%d): got %d, want %d", inOut[0], got, want)
   119  		}
   120  	}
   121  }
   122  
   123  func TestRefInclusionProof(t *testing.T) {
   124  	for _, tc := range []struct {
   125  		index uint64
   126  		size  uint64
   127  		want  [][]byte
   128  	}{
   129  		{index: 0, size: 1, want: nil},
   130  		{index: 0, size: 2, want: [][]byte{
   131  			hd("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7"),
   132  		}},
   133  		{index: 1, size: 2, want: [][]byte{
   134  			hd("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"),
   135  		}},
   136  		{index: 2, size: 3, want: [][]byte{
   137  			hd("fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125"),
   138  		}},
   139  		{index: 1, size: 5, want: [][]byte{
   140  			hd("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"),
   141  			hd("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e"),
   142  			hd("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"),
   143  		}},
   144  		{index: 0, size: 8, want: [][]byte{
   145  			hd("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7"),
   146  			hd("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e"),
   147  			hd("6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"),
   148  		}},
   149  		{index: 5, size: 8, want: [][]byte{
   150  			hd("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"),
   151  			hd("ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0"),
   152  			hd("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"),
   153  		}},
   154  	} {
   155  		t.Run(fmt.Sprintf("%d:%d", tc.index, tc.size), func(t *testing.T) {
   156  			entries := LeafInputs()
   157  			got := refInclusionProof(entries[:tc.size], tc.index, rfc6962.DefaultHasher)
   158  			if diff := cmp.Diff(got, tc.want); diff != "" {
   159  				t.Errorf("refInclusionProof: diff (-got +want)\n%s", diff)
   160  			}
   161  		})
   162  	}
   163  }
   164  
   165  func TestRefConsistencyProof(t *testing.T) {
   166  	for _, tc := range []struct {
   167  		size1 uint64
   168  		size2 uint64
   169  		want  [][]byte
   170  	}{
   171  		{size1: 1, size2: 1, want: nil},
   172  		{size1: 1, size2: 8, want: [][]byte{
   173  			hd("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7"),
   174  			hd("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e"),
   175  			hd("6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"),
   176  		}},
   177  		{size1: 2, size2: 5, want: [][]byte{
   178  			hd("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e"),
   179  			hd("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"),
   180  		}},
   181  		{size1: 6, size2: 8, want: [][]byte{
   182  			hd("0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a"),
   183  			hd("ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0"),
   184  			hd("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"),
   185  		}},
   186  	} {
   187  		t.Run(fmt.Sprintf("%d:%d", tc.size1, tc.size2), func(t *testing.T) {
   188  			entries := LeafInputs()
   189  			got := refConsistencyProof(entries[:tc.size2], tc.size2, tc.size1, rfc6962.DefaultHasher, true)
   190  			if diff := cmp.Diff(got, tc.want); diff != "" {
   191  				t.Errorf("refConsistencyProof: diff (-got +want)\n%s", diff)
   192  			}
   193  		})
   194  	}
   195  }
   196
View as plain text