protocol/bc/types/merkle_test.go

   1 package types
   2
   3 import (
   4         "encoding/hex"
   5
   6         "math/rand"
   7         "testing"
   8         "time"
   9
  10         "github.com/vapor/protocol/bc"
  11         "github.com/vapor/protocol/vm"
  12         "github.com/vapor/testutil"
  13 )
  14
  15 func TestMerkleRoot(t *testing.T) {
  16         cases := []struct {
  17                 witnesses [][][]byte
  18                 want      bc.Hash
  19         }{{
  20                 witnesses: [][][]byte{
  21                         {
  22                                 {1},
  23                                 []byte("00000"),
  24                         },
  25                 },
  26                 want: testutil.MustDecodeHash("011a6b552cc8eced01c403b138c51f906d0ccd0bbdf986d2b3e0cc69a4291737"),
  27         }, {
  28                 witnesses: [][][]byte{
  29                         {
  30                                 {1},
  31                                 []byte("000000"),
  32                         },
  33                         {
  34                                 {1},
  35                                 []byte("111111"),
  36                         },
  37                 },
  38                 want: testutil.MustDecodeHash("64cef8abecac041b87110309dd9068d4935a31fb1bd1572144d11ead9da91dba"),
  39         }, {
  40                 witnesses: [][][]byte{
  41                         {
  42                                 {1},
  43                                 []byte("000000"),
  44                         },
  45                         {
  46                                 {2},
  47                                 []byte("111111"),
  48                                 []byte("222222"),
  49                         },
  50                 },
  51                 want: testutil.MustDecodeHash("64cef8abecac041b87110309dd9068d4935a31fb1bd1572144d11ead9da91dba"),
  52         }}
  53
  54         for _, c := range cases {
  55                 var txs []*bc.Tx
  56                 for _, wit := range c.witnesses {
  57                         txs = append(txs, NewTx(TxData{
  58                                 Inputs: []*TxInput{
  59                                         &TxInput{
  60                                                 AssetVersion: 1,
  61                                                 TypedInput: &SpendInput{
  62                                                         Arguments: wit,
  63                                                         SpendCommitment: SpendCommitment{
  64                                                                 AssetAmount: bc.AssetAmount{
  65                                                                         AssetId: &bc.AssetID{V0: 0},
  66                                                                 },
  67                                                         },
  68                                                 },
  69                                         },
  70                                 },
  71                         }).Tx)
  72                 }
  73                 got, err := TxMerkleRoot(txs)
  74                 if err != nil {
  75                         t.Fatalf("unexpected error %s", err)
  76                 }
  77                 if got != c.want {
  78                         t.Log("witnesses", c.witnesses)
  79                         t.Errorf("got merkle root = %x want %x", got.Bytes(), c.want.Bytes())
  80                 }
  81         }
  82 }
  83
  84 func TestDuplicateLeaves(t *testing.T) {
  85         trueProg := []byte{byte(vm.OP_TRUE)}
  86         assetID := bc.ComputeAssetID(trueProg, 1, &bc.EmptyStringHash)
  87         txs := make([]*bc.Tx, 6)
  88         for i := uint64(0); i < 6; i++ {
  89                 now := []byte(time.Now().String())
  90                 txs[i] = NewTx(TxData{
  91                         Version: 1,
  92                         Inputs:  []*TxInput{NewIssuanceInput(now, i, trueProg, nil, nil)},
  93                         Outputs: []*TxOutput{NewTxOutput(assetID, i, trueProg)},
  94                 }).Tx
  95         }
  96
  97         // first, get the root of an unbalanced tree
  98         txns := []*bc.Tx{txs[5], txs[4], txs[3], txs[2], txs[1], txs[0]}
  99         root1, err := TxMerkleRoot(txns)
 100         if err != nil {
 101                 t.Fatalf("unexpected error %s", err)
 102         }
 103
 104         // now, get the root of a balanced tree that repeats leaves 0 and 1
 105         txns = []*bc.Tx{txs[5], txs[4], txs[3], txs[2], txs[1], txs[0], txs[1], txs[0]}
 106         root2, err := TxMerkleRoot(txns)
 107         if err != nil {
 108                 t.Fatalf("unexpected error %s", err)
 109         }
 110
 111         if root1 == root2 {
 112                 t.Error("forged merkle tree by duplicating some leaves")
 113         }
 114 }
 115
 116 func TestAllDuplicateLeaves(t *testing.T) {
 117         trueProg := []byte{byte(vm.OP_TRUE)}
 118         assetID := bc.ComputeAssetID(trueProg, 1, &bc.EmptyStringHash)
 119         now := []byte(time.Now().String())
 120         issuanceInp := NewIssuanceInput(now, 1, trueProg, nil, nil)
 121
 122         tx := NewTx(TxData{
 123                 Version: 1,
 124                 Inputs:  []*TxInput{issuanceInp},
 125                 Outputs: []*TxOutput{NewTxOutput(assetID, 1, trueProg)},
 126         }).Tx
 127         tx1, tx2, tx3, tx4, tx5, tx6 := tx, tx, tx, tx, tx, tx
 128
 129         // first, get the root of an unbalanced tree
 130         txs := []*bc.Tx{tx6, tx5, tx4, tx3, tx2, tx1}
 131         root1, err := TxMerkleRoot(txs)
 132         if err != nil {
 133                 t.Fatalf("unexpected error %s", err)
 134         }
 135
 136         // now, get the root of a balanced tree that repeats leaves 5 and 6
 137         txs = []*bc.Tx{tx6, tx5, tx6, tx5, tx4, tx3, tx2, tx1}
 138         root2, err := TxMerkleRoot(txs)
 139         if err != nil {
 140                 t.Fatalf("unexpected error %s", err)
 141         }
 142
 143         if root1 == root2 {
 144                 t.Error("forged merkle tree with all duplicate leaves")
 145         }
 146 }
 147
 148 func TestTxMerkleProof(t *testing.T) {
 149         cases := []struct {
 150                 txCount          int
 151                 relatedTxIndexes []int
 152                 expectHashLen    int
 153                 expectFlags      []uint8
 154         }{
 155                 {
 156                         txCount:          10,
 157                         relatedTxIndexes: []int{0, 3, 7, 8},
 158                         expectHashLen:    9,
 159                         expectFlags:      []uint8{1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 2, 0},
 160                 },
 161                 {
 162                         txCount:          10,
 163                         relatedTxIndexes: []int{},
 164                         expectHashLen:    1,
 165                         expectFlags:      []uint8{0},
 166                 },
 167                 {
 168                         txCount:          1,
 169                         relatedTxIndexes: []int{0},
 170                         expectHashLen:    1,
 171                         expectFlags:      []uint8{2},
 172                 },
 173                 {
 174                         txCount:          19,
 175                         relatedTxIndexes: []int{1, 3, 5, 7, 11, 15},
 176                         expectHashLen:    15,
 177                         expectFlags:      []uint8{1, 1, 1, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 0},
 178                 },
 179         }
 180         for _, c := range cases {
 181                 txs, bcTxs := mockTransactions(c.txCount)
 182
 183                 var nodes []merkleNode
 184                 for _, tx := range txs {
 185                         nodes = append(nodes, tx.ID)
 186                 }
 187                 tree := buildMerkleTree(nodes)
 188                 root, err := TxMerkleRoot(bcTxs)
 189                 if err != nil {
 190                         t.Fatalf("unexpected error %s", err)
 191                 }
 192                 if tree.hash != root {
 193                         t.Error("build tree fail")
 194                 }
 195
 196                 var relatedTx []*Tx
 197                 for _, index := range c.relatedTxIndexes {
 198                         relatedTx = append(relatedTx, txs[index])
 199                 }
 200                 proofHashes, flags := GetTxMerkleTreeProof(txs, relatedTx)
 201                 if !testutil.DeepEqual(flags, c.expectFlags) {
 202                         t.Error("The flags is not equals expect flags", flags, c.expectFlags)
 203                 }
 204                 if len(proofHashes) != c.expectHashLen {
 205                         t.Error("The length proof hashes is not equals expect length")
 206                 }
 207                 var ids []*bc.Hash
 208                 for _, tx := range relatedTx {
 209                         ids = append(ids, &tx.ID)
 210                 }
 211                 if !ValidateTxMerkleTreeProof(proofHashes, flags, ids, root) {
 212                         t.Error("Merkle tree validate fail")
 213                 }
 214         }
 215 }
 216
 217 func TestStatusMerkleProof(t *testing.T) {
 218         cases := []struct {
 219                 statusCount    int
 220                 relatedIndexes []int
 221                 flags          []uint8
 222                 expectHashLen  int
 223         }{
 224                 {
 225                         statusCount:    10,
 226                         relatedIndexes: []int{0, 3, 7, 8},
 227                         flags:          []uint8{1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 2, 0},
 228                         expectHashLen:  9,
 229                 },
 230                 {
 231                         statusCount:    10,
 232                         relatedIndexes: []int{},
 233                         flags:          []uint8{0},
 234                         expectHashLen:  1,
 235                 },
 236                 {
 237                         statusCount:    1,
 238                         relatedIndexes: []int{0},
 239                         flags:          []uint8{2},
 240                         expectHashLen:  1,
 241                 },
 242                 {
 243                         statusCount:    19,
 244                         relatedIndexes: []int{1, 3, 5, 7, 11, 15},
 245                         flags:          []uint8{1, 1, 1, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 0},
 246                         expectHashLen:  15,
 247                 },
 248         }
 249         for _, c := range cases {
 250                 statuses := mockStatuses(c.statusCount)
 251                 var relatedStatuses []*bc.TxVerifyResult
 252                 for _, index := range c.relatedIndexes {
 253                         relatedStatuses = append(relatedStatuses, statuses[index])
 254                 }
 255                 hashes := GetStatusMerkleTreeProof(statuses, c.flags)
 256                 if len(hashes) != c.expectHashLen {
 257                         t.Error("The length proof hashes is not equals expect length")
 258                 }
 259                 root, _ := TxStatusMerkleRoot(statuses)
 260                 if !ValidateStatusMerkleTreeProof(hashes, c.flags, relatedStatuses, root) {
 261                         t.Error("Merkle tree validate fail")
 262                 }
 263         }
 264 }
 265
 266 func TestUglyValidateTxMerkleProof(t *testing.T) {
 267         cases := []struct {
 268                 hashes        []string
 269                 flags         []uint8
 270                 relatedHashes []string
 271                 root          string
 272                 expectResult  bool
 273         }{
 274                 {
 275                         hashes:        []string{},
 276                         flags:         []uint8{},
 277                         relatedHashes: []string{},
 278                         root:          "",
 279                         expectResult:  false,
 280                 },
 281                 {
 282                         hashes:        []string{},
 283                         flags:         []uint8{1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 2, 0},
 284                         relatedHashes: []string{},
 285                         root:          "",
 286                         expectResult:  false,
 287                 },
 288                 {
 289                         hashes: []string{
 290                                 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
 291                                 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
 292                         },
 293                         flags:         []uint8{},
 294                         relatedHashes: []string{},
 295                         root:          "",
 296                         expectResult:  false,
 297                 },
 298                 {
 299                         hashes: []string{},
 300                         flags:  []uint8{},
 301                         relatedHashes: []string{
 302                                 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
 303                                 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
 304                         },
 305                         root:         "",
 306                         expectResult: false,
 307                 },
 308                 {
 309                         hashes: []string{},
 310                         flags:  []uint8{1, 1, 0, 2, 1, 2, 1, 0, 1},
 311                         relatedHashes: []string{
 312                                 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
 313                                 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
 314                         },
 315                         root: "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
 316                 },
 317                 {
 318                         hashes: []string{
 319                                 "68f03ea2b02a21ad944d1a43ad6152a7fa6a7ed4101d59be62594dd30ef2a558",
 320                         },
 321                         flags: []uint8{},
 322                         relatedHashes: []string{
 323                                 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
 324                                 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
 325                         },
 326                         root:         "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
 327                         expectResult: false,
 328                 },
 329                 {
 330                         hashes: []string{
 331                                 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
 332                                 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
 333                                 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
 334                         },
 335                         flags: []uint8{1, 1, 0, 2, 0},
 336                         relatedHashes: []string{
 337                                 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
 338                         },
 339                         root:         "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
 340                         expectResult: true,
 341                 },
 342                 // flags and hashes is correct, but relatedHashes has hash that does not exist
 343                 {
 344                         hashes: []string{
 345                                 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
 346                                 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
 347                                 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
 348                         },
 349                         flags: []uint8{1, 1, 0, 2, 0},
 350                         relatedHashes: []string{
 351                                 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
 352                                 "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
 353                         },
 354                         root:         "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
 355                         expectResult: false,
 356                 },
 357                 // flags and hashes is correct, but relatedHashes is not enough
 358                 {
 359                         hashes: []string{
 360                                 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
 361                                 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
 362                                 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
 363                         },
 364                         flags:         []uint8{1, 1, 0, 2, 0},
 365                         relatedHashes: []string{},
 366                         root:          "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
 367                         expectResult:  false,
 368                 },
 369                 // flags is correct, but hashes has additional hash at the end
 370                 {
 371                         hashes: []string{
 372                                 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
 373                                 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
 374                                 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
 375                                 "5a06c90136e81c0f9cad29725e69edc6d21bd6fb0641265f9c4b6bb6840b37dd",
 376                         },
 377                         flags: []uint8{1, 1, 0, 2, 0},
 378                         relatedHashes: []string{
 379                                 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
 380                         },
 381                         root:         "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
 382                         expectResult: true,
 383                 },
 384         }
 385
 386         for _, c := range cases {
 387                 var hashes, relatedHashes []*bc.Hash
 388                 var hashBytes, rootBytes [32]byte
 389                 var err error
 390                 for _, hashStr := range c.hashes {
 391                         if hashBytes, err = convertHashStr2Bytes(hashStr); err != nil {
 392                                 t.Fatal(err)
 393                         }
 394
 395                         hash := bc.NewHash(hashBytes)
 396                         hashes = append(hashes, &hash)
 397                 }
 398                 for _, hashStr := range c.relatedHashes {
 399                         if hashBytes, err = convertHashStr2Bytes(hashStr); err != nil {
 400                                 t.Fatal(err)
 401                         }
 402
 403                         hash := bc.NewHash(hashBytes)
 404                         relatedHashes = append(relatedHashes, &hash)
 405                 }
 406                 if rootBytes, err = convertHashStr2Bytes(c.root); err != nil {
 407                         t.Fatal(err)
 408                 }
 409
 410                 root := bc.NewHash(rootBytes)
 411                 if ValidateTxMerkleTreeProof(hashes, c.flags, relatedHashes, root) != c.expectResult {
 412                         t.Error("Validate merkle tree proof fail")
 413                 }
 414         }
 415 }
 416
 417 func convertHashStr2Bytes(hashStr string) ([32]byte, error) {
 418         var result [32]byte
 419         hashBytes, err := hex.DecodeString(hashStr)
 420         if err != nil {
 421                 return result, err
 422         }
 423         copy(result[:], hashBytes)
 424         return result, nil
 425 }
 426
 427 func mockTransactions(txCount int) ([]*Tx, []*bc.Tx) {
 428         var txs []*Tx
 429         var bcTxs []*bc.Tx
 430         trueProg := []byte{byte(vm.OP_TRUE)}
 431         assetID := bc.ComputeAssetID(trueProg, 1, &bc.EmptyStringHash)
 432         for i := 0; i < txCount; i++ {
 433                 now := []byte(time.Now().String())
 434                 issuanceInp := NewIssuanceInput(now, 1, trueProg, nil, nil)
 435                 tx := NewTx(TxData{
 436                         Version: 1,
 437                         Inputs:  []*TxInput{issuanceInp},
 438                         Outputs: []*TxOutput{NewTxOutput(assetID, 1, trueProg)},
 439                 })
 440                 txs = append(txs, tx)
 441                 bcTxs = append(bcTxs, tx.Tx)
 442         }
 443         return txs, bcTxs
 444 }
 445
 446 func mockStatuses(statusCount int) []*bc.TxVerifyResult {
 447         var statuses []*bc.TxVerifyResult
 448         for i := 0; i < statusCount; i++ {
 449                 status := &bc.TxVerifyResult{}
 450                 fail := rand.Intn(2)
 451                 if fail == 0 {
 452                         status.StatusFail = true
 453                 } else {
 454                         status.StatusFail = false
 455                 }
 456                 statuses = append(statuses, status)
 457         }
 458         return statuses
 459 }