10 "github.com/vapor/protocol/bc"
11 "github.com/vapor/protocol/vm"
12 "github.com/vapor/testutil"
15 func TestMerkleRoot(t *testing.T) {
20 witnesses: [][][]byte{
26 want: testutil.MustDecodeHash("011a6b552cc8eced01c403b138c51f906d0ccd0bbdf986d2b3e0cc69a4291737"),
28 witnesses: [][][]byte{
38 want: testutil.MustDecodeHash("64cef8abecac041b87110309dd9068d4935a31fb1bd1572144d11ead9da91dba"),
40 witnesses: [][][]byte{
51 want: testutil.MustDecodeHash("64cef8abecac041b87110309dd9068d4935a31fb1bd1572144d11ead9da91dba"),
54 for _, c := range cases {
56 for _, wit := range c.witnesses {
57 txs = append(txs, NewTx(TxData{
61 TypedInput: &SpendInput{
63 SpendCommitment: SpendCommitment{
64 AssetAmount: bc.AssetAmount{
65 AssetId: &bc.AssetID{V0: 0},
73 got, err := TxMerkleRoot(txs)
75 t.Fatalf("unexpected error %s", err)
78 t.Log("witnesses", c.witnesses)
79 t.Errorf("got merkle root = %x want %x", got.Bytes(), c.want.Bytes())
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{
92 Inputs: []*TxInput{NewIssuanceInput(now, i, trueProg, nil, nil)},
93 Outputs: []*TxOutput{NewTxOutput(assetID, i, trueProg)},
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)
101 t.Fatalf("unexpected error %s", err)
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)
108 t.Fatalf("unexpected error %s", err)
112 t.Error("forged merkle tree by duplicating some leaves")
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)
124 Inputs: []*TxInput{issuanceInp},
125 Outputs: []*TxOutput{NewTxOutput(assetID, 1, trueProg)},
127 tx1, tx2, tx3, tx4, tx5, tx6 := tx, tx, tx, tx, tx, tx
129 // first, get the root of an unbalanced tree
130 txs := []*bc.Tx{tx6, tx5, tx4, tx3, tx2, tx1}
131 root1, err := TxMerkleRoot(txs)
133 t.Fatalf("unexpected error %s", err)
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)
140 t.Fatalf("unexpected error %s", err)
144 t.Error("forged merkle tree with all duplicate leaves")
148 func TestTxMerkleProof(t *testing.T) {
151 relatedTxIndexes []int
157 relatedTxIndexes: []int{0, 3, 7, 8},
159 expectFlags: []uint8{1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 2, 0},
163 relatedTxIndexes: []int{},
165 expectFlags: []uint8{0},
169 relatedTxIndexes: []int{0},
171 expectFlags: []uint8{2},
175 relatedTxIndexes: []int{1, 3, 5, 7, 11, 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},
180 for _, c := range cases {
181 txs, bcTxs := mockTransactions(c.txCount)
183 var nodes []merkleNode
184 for _, tx := range txs {
185 nodes = append(nodes, tx.ID)
187 tree := buildMerkleTree(nodes)
188 root, err := TxMerkleRoot(bcTxs)
190 t.Fatalf("unexpected error %s", err)
192 if tree.hash != root {
193 t.Error("build tree fail")
197 for _, index := range c.relatedTxIndexes {
198 relatedTx = append(relatedTx, txs[index])
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)
204 if len(proofHashes) != c.expectHashLen {
205 t.Error("The length proof hashes is not equals expect length")
208 for _, tx := range relatedTx {
209 ids = append(ids, &tx.ID)
211 if !ValidateTxMerkleTreeProof(proofHashes, flags, ids, root) {
212 t.Error("Merkle tree validate fail")
217 func TestStatusMerkleProof(t *testing.T) {
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},
232 relatedIndexes: []int{},
238 relatedIndexes: []int{0},
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},
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])
255 hashes := GetStatusMerkleTreeProof(statuses, c.flags)
256 if len(hashes) != c.expectHashLen {
257 t.Error("The length proof hashes is not equals expect length")
259 root, _ := TxStatusMerkleRoot(statuses)
260 if !ValidateStatusMerkleTreeProof(hashes, c.flags, relatedStatuses, root) {
261 t.Error("Merkle tree validate fail")
266 func TestUglyValidateTxMerkleProof(t *testing.T) {
270 relatedHashes []string
277 relatedHashes: []string{},
283 flags: []uint8{1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 2, 0},
284 relatedHashes: []string{},
290 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
291 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
294 relatedHashes: []string{},
301 relatedHashes: []string{
302 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
303 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
310 flags: []uint8{1, 1, 0, 2, 1, 2, 1, 0, 1},
311 relatedHashes: []string{
312 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
313 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
315 root: "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
319 "68f03ea2b02a21ad944d1a43ad6152a7fa6a7ed4101d59be62594dd30ef2a558",
322 relatedHashes: []string{
323 "0093370a8e19f8f131fd7e75c576615950d5672ee5e18c63f105a95bcab4332c",
324 "c9b7779847fb7ab74cf4b1e7f4557133918faa2bc130042753417dfb62b12dfa",
326 root: "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
331 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
332 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
333 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
335 flags: []uint8{1, 1, 0, 2, 0},
336 relatedHashes: []string{
337 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
339 root: "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
342 // flags and hashes is correct, but relatedHashes has hash that does not exist
345 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
346 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
347 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
349 flags: []uint8{1, 1, 0, 2, 0},
350 relatedHashes: []string{
351 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
352 "281138e0a9ea19505844bd61a2f5843787035782c093da74d12b5fba73eeeb07",
354 root: "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
357 // flags and hashes is correct, but relatedHashes is not enough
360 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
361 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
362 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
364 flags: []uint8{1, 1, 0, 2, 0},
365 relatedHashes: []string{},
366 root: "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
369 // flags is correct, but hashes has additional hash at the end
372 "8ec3ee7589f95eee9b534f71fcd37142bcc839a0dbfe78124df9663827b90c35",
373 "011bd3380852b2946df507e0c6234222c559eec8f545e4bc58a89e960892259b",
374 "c205988d9c864083421f1bdb95e6cf8b52070facfcc87e46a6e8197f5389fca2",
375 "5a06c90136e81c0f9cad29725e69edc6d21bd6fb0641265f9c4b6bb6840b37dd",
377 flags: []uint8{1, 1, 0, 2, 0},
378 relatedHashes: []string{
379 "504af455e328e7dd39bbc059529851946d54ee8b459b11b3aac4a0feeb474487",
381 root: "aff81a46fe79204ef9007243f374d54104a59762b9f74d80d56b5291753db6fb",
386 for _, c := range cases {
387 var hashes, relatedHashes []*bc.Hash
388 var hashBytes, rootBytes [32]byte
390 for _, hashStr := range c.hashes {
391 if hashBytes, err = convertHashStr2Bytes(hashStr); err != nil {
395 hash := bc.NewHash(hashBytes)
396 hashes = append(hashes, &hash)
398 for _, hashStr := range c.relatedHashes {
399 if hashBytes, err = convertHashStr2Bytes(hashStr); err != nil {
403 hash := bc.NewHash(hashBytes)
404 relatedHashes = append(relatedHashes, &hash)
406 if rootBytes, err = convertHashStr2Bytes(c.root); err != nil {
410 root := bc.NewHash(rootBytes)
411 if ValidateTxMerkleTreeProof(hashes, c.flags, relatedHashes, root) != c.expectResult {
412 t.Error("Validate merkle tree proof fail")
417 func convertHashStr2Bytes(hashStr string) ([32]byte, error) {
419 hashBytes, err := hex.DecodeString(hashStr)
423 copy(result[:], hashBytes)
427 func mockTransactions(txCount int) ([]*Tx, []*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)
437 Inputs: []*TxInput{issuanceInp},
438 Outputs: []*TxOutput{NewTxOutput(assetID, 1, trueProg)},
440 txs = append(txs, tx)
441 bcTxs = append(bcTxs, tx.Tx)
446 func mockStatuses(statusCount int) []*bc.TxVerifyResult {
447 var statuses []*bc.TxVerifyResult
448 for i := 0; i < statusCount; i++ {
449 status := &bc.TxVerifyResult{}
452 status.StatusFail = true
454 status.StatusFail = false
456 statuses = append(statuses, status)