protocol/bc/types/merkle_test.go

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