Page MenuHomePhabricator

[test framework] add a python implementation for merkle trees
ClosedPublic

Authored by PiRK on Sep 13 2024, 11:31.

Details

Summary

This will be used in D16569 to verify the results returned by chronik in the functional test.

Test Plan

ninja check-functional

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

PiRK requested review of this revision.Sep 13 2024, 11:31
PiRK planned changes to this revision.Sep 13 2024, 11:42

let's move hex_to_be_bytes to util.py

move hex_to_be_bytes to util.py and remove unused be_bytes_to_hex

Fabien requested changes to this revision.Sep 16 2024, 08:09
Fabien added a subscriber: Fabien.
Fabien added inline comments.
test/functional/test_framework/merkle.py
49 ↗(On Diff #49618)

This can only happen once, no need to check it in the loop

53 ↗(On Diff #49618)

I don't understand the XOR here, can you explain ?
Also if I have a list of 4 hashes and index = 4, this will pass the assert (4 <= 4), not duplicate the last hash because 4 % 2 == 0, and the first loop iteration will access working_hashes[5] which is out of bounds

58 ↗(On Diff #49618)

You may also want to check len(hashes) > 0 at the beginning of the function, and special case the returned value

This revision now requires changes to proceed.Sep 16 2024, 08:09
test/functional/test_framework/merkle.py
49 ↗(On Diff #49618)

Actually it needs to be done in each iteration of the loop. For instance you start with 6 hashes you will not need to duplicate a hash in the first step, but in the second step you will be left with 3 hashes and you will need to duplicate the last one to make it 4.

53 ↗(On Diff #49618)

The XOR tells us which intermediate hash in a given level we want to remember so we can verify that a specific block hash is in a particular merkle tree.

For instance with the merkle root for the first 6 hashes of the chain:

                    root = h01234545
         h0123                    h4545
  h01           h23          h45        h45
bh0  bh1       bh2 bh3      bh4 bh5

If you want to verify that bh2 is part of the chain knowing root, you need branch = [bh3, h01, h4545]
2^1 = 3 (pick the 4th hash in level 0, bh3)
2>>1 = 1
1 ^ 1 = 0 (pick the 1st hash in level 1, h01)
1 >> 1 = 0
0^1 = 1 (pick the 2nd hash in level 2, h4545)

ìndex is 0 based, so If you have a list of 4 hashes index can not be more than 3.

test/functional/test_framework/merkle.py
53 ↗(On Diff #49618)

So i think my assertion assert index <= len(hashes) should probably be assert index < len(hashes)

fix assertion for index vs len(hashes), and also assert that len(hashes) is strictly larger than 0

Fabien requested changes to this revision.Sep 16 2024, 12:04
Fabien added inline comments.
test/functional/test_framework/merkle.py
58 ↗(On Diff #49618)

This still holds

This revision now requires changes to proceed.Sep 16 2024, 12:04
PiRK requested review of this revision.Sep 16 2024, 14:58
PiRK added inline comments.
test/functional/test_framework/merkle.py
58 ↗(On Diff #49618)

We know have assert 0 < len(hashes) at the begining of the function. I can maybe put a more explicit error, but returning something in this case seems pointless.

Fabien added inline comments.
test/functional/test_framework/merkle.py
58 ↗(On Diff #49618)

Oh I see, I was confused by the notation

This revision is now accepted and ready to land.Sep 16 2024, 17:53