constants.go

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

     1  // Copyright 2019 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 contains code and data for testing Merkle trees, such as a
    16  // reference implementation of in-memory Merkle tree.
    17  package testonly
    18  
    19  import "encoding/hex"
    20  
    21  // LeafInputs returns a slice of leaf inputs for testing Merkle trees.
    22  func LeafInputs() [][]byte {
    23  	return [][]byte{
    24  		hd(""),
    25  		hd("00"),
    26  		hd("10"),
    27  		hd("2021"),
    28  		hd("3031"),
    29  		hd("40414243"),
    30  		hd("5051525354555657"),
    31  		hd("606162636465666768696a6b6c6d6e6f"),
    32  	}
    33  }
    34  
    35  // NodeHashes returns a structured slice of node hashes for all complete
    36  // subtrees of a Merkle tree built from LeafInputs() using the RFC 6962 hashing
    37  // strategy. The first index in the slice is the tree level (zero being the
    38  // leaves level), the second is the horizontal index within a level.
    39  func NodeHashes() [][][]byte {
    40  	return [][][]byte{{
    41  		hd("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"),
    42  		hd("96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7"),
    43  		hd("0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7"),
    44  		hd("07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7"),
    45  		hd("bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"),
    46  		hd("4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658"),
    47  		hd("b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f"),
    48  		hd("46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1"),
    49  	}, {
    50  		hd("fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125"),
    51  		hd("5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e"),
    52  		hd("0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a"),
    53  		hd("ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0"),
    54  	}, {
    55  		hd("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"),
    56  		hd("6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"),
    57  	}, {
    58  		hd("5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"),
    59  	}}
    60  }
    61  
    62  // RootHashes returns a slice of Merkle tree root hashes for all subsequent
    63  // trees built from LeafInputs() using the RFC 6962 hashing strategy. Hashes
    64  // are indexed by tree size starting from an empty tree.
    65  func RootHashes() [][]byte {
    66  	return [][]byte{
    67  		EmptyRootHash(),
    68  		hd("6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"),
    69  		hd("fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125"),
    70  		hd("aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77"),
    71  		hd("d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"),
    72  		hd("4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4"),
    73  		hd("76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef"),
    74  		hd("ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c"),
    75  		hd("5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"),
    76  	}
    77  }
    78  
    79  // CompactTrees returns a slice of compact.Tree internal hashes for all
    80  // subsequent trees built from LeafInputs() using the RFC 6962 hashing
    81  // strategy.
    82  func CompactTrees() [][][]byte {
    83  	nh := NodeHashes()
    84  	return [][][]byte{
    85  		nil, // Empty tree.
    86  		{nh[0][0]},
    87  		{nh[1][0]},
    88  		{nh[1][0], nh[0][2]},
    89  		{nh[2][0]},
    90  		{nh[2][0], nh[0][4]},
    91  		{nh[2][0], nh[1][2]},
    92  		{nh[2][0], nh[1][2], nh[0][6]},
    93  		{nh[3][0]},
    94  	}
    95  }
    96  
    97  // EmptyRootHash returns the root hash for an empty Merkle tree that uses
    98  // SHA256-based strategy from RFC 6962.
    99  func EmptyRootHash() []byte {
   100  	return hd("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855")
   101  }
   102  
   103  // hd decodes a hex string or panics.
   104  func hd(b string) []byte {
   105  	r, err := hex.DecodeString(b)
   106  	if err != nil {
   107  		panic(err)
   108  	}
   109  	return r
   110  }
   111
View as plain text