merkle_test.go raw

   1  package merkle
   2  
   3  import (
   4  	"encoding/hex"
   5  	"testing"
   6  )
   7  
   8  // The roots below were computed by an independent implementation (Python's hashlib) over
   9  // transaction ids that are each 32 copies of their index, so they pin the pairing rule at every
  10  // block size instead of only the powers of two.
  11  var vectors = []struct {
  12  	count int
  13  	root  string
  14  }{
  15  	{1, "0000000000000000000000000000000000000000000000000000000000000000"},
  16  	{2, "705ede9d42476fc3e5a978b042ce790a193678f46d19f47ec4ab46539c47b76d"},
  17  	{3, "d6384640762f797ede7e7f13839222f9452272809932cc6089f701331df4552d"},
  18  	{4, "ac41efca4951b1260054e1155fd8f6c3f42a5b521f1161b20f3c053d3159816c"},
  19  	{5, "c855157c6d4dda84ba48e08dd32cc7ba1672665610f19d0f8899aee59209e2de"},
  20  	{7, "6063cac3fc7219cdbe4552783852c347919ea72795730214f8e841d31922cf75"},
  21  }
  22  
  23  // TestRootMatchesAnIndependentImplementation: the pairing rule, at every count.
  24  func TestRootMatchesAnIndependentImplementation(t *testing.T) {
  25  	for _, vector := range vectors {
  26  		txids := make([][32]byte, vector.count)
  27  
  28  		for index := range txids {
  29  			for byteIndex := range txids[index] {
  30  				txids[index][byteIndex] = byte(index)
  31  			}
  32  		}
  33  
  34  		root, err := Root(txids)
  35  
  36  		if err != nil {
  37  			t.Fatal(err)
  38  		}
  39  
  40  		if got := hex.EncodeToString(root[:]); got != vector.root {
  41  			t.Fatalf("%d transactions: the root is %s, want %s", vector.count, got, vector.root)
  42  		}
  43  	}
  44  }
  45  
  46  // TestOddCountsPairTheLastWithItself: the case a naive implementation gets wrong.
  47  func TestOddCountsPairTheLastWithItself(t *testing.T) {
  48  	three := make([][32]byte, 3)
  49  
  50  	for index := range three {
  51  		for byteIndex := range three[index] {
  52  			three[index][byteIndex] = byte(index)
  53  		}
  54  	}
  55  
  56  	root, err := Root(three)
  57  
  58  	if err != nil {
  59  		t.Fatal(err)
  60  	}
  61  
  62  	if root == [32]byte{} {
  63  		t.Fatal("a three-transaction block has no root")
  64  	}
  65  
  66  	// Three transactions must not hash the way two do.
  67  	two, err := Root(three[:2])
  68  
  69  	if err != nil {
  70  		t.Fatal(err)
  71  	}
  72  
  73  	if root == two {
  74  		t.Fatal("three transactions produced two transactions' root")
  75  	}
  76  }
  77  
  78  // TestNoTransactionsIsAnError: a block with no coinbase is not a block.
  79  func TestNoTransactionsIsAnError(t *testing.T) {
  80  	if _, err := Root(nil); err != ErrNoTransactions {
  81  		t.Fatalf("an empty block: %v", err)
  82  	}
  83  }
  84