Switch to a constant-space Merkle root/branch algorithm. #6508

pull sipa wants to merge 2 commits into bitcoin:master from sipa:constmerkle changing 13 files +353 −75
  1. sipa commented at 5:08 pm on August 3, 2015: member

    This switches the Merkle tree logic for blocks to one that runs in logspace (effectively constant space, with a limit of 2^32 leaves). The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations:

    • Verifies that the old code and new code agree for the Merkle root.
    • Verifies that the old code and new code agree for the Merkle branch.
    • Verifies that the computed Merkle branch is valid.
    • Verifies that mutations don’t change the Merkle root.
    • Verifies that mutations are correctly detected.

    Advantages:

    • Removes the need for vMerkleTree (a validation-related data structure) from CBlock (a primitive data structure).
    • Is slightly faster due to better memory locality and avoiding all heap overhead.

    Disadvantages:

    • Requires recomputing the Merkle tree any time a Merkle branch is needed. The wallet depends on this any time a transaction is added. This is not technically necessary, however.
    • Longer and harder to read code.

    The code remains in primitives/block for now. This is not optimal, as one of the purposes is disentangling the Merkle calculation logic from the primitive data structures. TBD.

  2. sipa force-pushed on Aug 3, 2015
  3. dgenr8 commented at 10:08 pm on August 3, 2015: contributor
    Great improvement over current space requirement which is O(n), yes?
  4. sipa commented at 10:34 pm on August 3, 2015: member
    @dgenr8 Yes, but the current code requires around 96 bytes per transaction, which is insignificant compared to the ~1 kB each transaction already requires in memory on average. Still, this PR improves it to ~1 kB total (but more importantly: entirely continuous and on the stack).
  5. laanwj added the label Validation on Aug 5, 2015
  6. laanwj commented at 10:39 am on August 5, 2015: member
    Concept ACK. Needs to be reviewed very carefully as to not change the behavior in subtle edge cases.
  7. sipa commented at 1:17 pm on August 5, 2015: member

    Of course.

    Note that the unit test creates merkle trees of all sizes up to 16, and for each all known malleabilities and all branches.

    On the other side, the performance and memory usage benefit are not significant, but getting rid of vMerkleTree in CBlock may be worth it.

  8. cozz commented at 9:03 am on August 8, 2015: contributor
    Does this mean that all transactions in a block have to be hashed together again, every time a transaction gets added to the wallet? So if there are 10 transactions in a block for the wallet, we hash it again 10 times?
  9. sipa commented at 9:12 am on August 8, 2015: member
    @cozz: with the current code, yes. But I don’t think we actually need to store those…
  10. cozz commented at 9:42 am on August 8, 2015: contributor
    Yes, I wouldnt store them either. But as long as we do, I do not like, that this pull decreases wallet performance. So I would like to see that fixed. Either by some temp-cache for the wallet, or just by removing those merkle-branches.
  11. sipa commented at 8:52 am on August 11, 2015: member

    There is definitely a wallet performance downside, as you need to recompute the merkle tree for every wallet transaction. If it looked like I claimed otherwise, sorry. It’s only an individual merkle root/branch computation that is made faster.

    I’ll delay this until we remove the call from the wallet to conpute branches.

  12. sipa force-pushed on Aug 11, 2015
  13. sipa commented at 7:27 pm on August 11, 2015: member
    Rebased on top of #6550, to address the issue that @cozz raised.
  14. dcousens commented at 1:01 am on August 12, 2015: contributor

    utACK

    Diff comparison for those who want to check without including the rebased commits.

  15. laanwj commented at 8:55 am on October 6, 2015: member
    Needs rebase (after #6550, I think)
  16. sipa force-pushed on Nov 2, 2015
  17. sipa commented at 4:41 am on November 2, 2015: member
    Rebased.
  18. gmaxwell added this to the milestone 0.12.0 on Nov 11, 2015
  19. sipa force-pushed on Nov 17, 2015
  20. sipa commented at 4:38 pm on November 17, 2015: member
    Moved the Merkle computation code to a separate file (independent of CBlock and CTransaction), and used that in a thin wrapper caller in primitives/block.h.
  21. dcousens commented at 0:37 am on November 18, 2015: contributor

    re-ACK

    Also, awesome on moving merkle.cpp out :+1:

  22. jtimon commented at 10:07 am on November 23, 2015: contributor
    If we make it consensus/merkle.o, that would be less code to move again later…
  23. sipa commented at 0:46 am on November 26, 2015: member
    @jtimon Hmm, I was seeing this more as generic data structure code, like limitedmap.h is for example, but it’s probably not useful to anything that doesn’t also need the consensus logic anyway.
  24. laanwj commented at 9:53 am on November 26, 2015: member
    Agree that Merkle trees are a general data structure - however, the specific way of doing a Merkle-tree is very bitcoin-consensus-specific, and there is the big warning that this is not recommended to use this as-is outside of bitcoin.
  25. jtimon commented at 11:09 am on November 26, 2015: contributor
    General data structure or not, this is used in checkBlock and will therefore be part of VerifyBlock and the complete libconsensus too. Once it is complete, if we want to separate it as a subtree with its own repo, we will have to put all the files in the same dir (ie src/consensus) first.
  26. laanwj commented at 11:13 am on November 26, 2015: member
    @jtimon I agree
  27. sipa force-pushed on Nov 26, 2015
  28. sipa commented at 12:18 pm on November 26, 2015: member

    Done.

    I had to move more things around, because otherwise primitives and consensus would end up with a circular dependency on each other. Now all logic (both generic Merkle logic, and the block-specific code) are in consensus, which is better as none of it really belonged in primitives anyway.

  29. jtimon commented at 12:32 pm on November 26, 2015: contributor
    Thank you. I wouldn’t worry about consensus/merkle depending on primitives/transaction while primitives/block depends on consensus/merkle. primitives is not a building package and they all three belong in the consensus building package (see WIP #7091) and eventually they should all be in the consensus dir anyway. A circular dependency between consensus/merkle and primitives/block is another thing though. I can’t remember how the includes were before, but they look good to me now.
  30. sipa force-pushed on Nov 26, 2015
  31. sipa force-pushed on Nov 26, 2015
  32. in src/test/main_tests.cpp: in d5a4e81304 outdated 
    73@@ -73,4 +74,127 @@ BOOST_AUTO_TEST_CASE(test_combiner_all)
74     BOOST_CHECK(Test());
75 }
76 
77+// Older version of the merkle root computation code, for comparison.
    jtimon commented at 3:57 pm on November 26, 2015:
    minor nit, is main_tests.cpp really the right place for this?
    sipa commented at 2:19 pm on November 27, 2015:
    Have a better suggestion? :)
    jtimon commented at 2:26 pm on November 27, 2015:
    I don’t know, checkblock_tests.cpp? maybe its own merkle_test.cpp ? The only use in main.cpp is in CheckBlock(), which should eventually move to the consensus dir…
    sipa commented at 2:38 pm on November 27, 2015:
    Moved!
  33. laanwj commented at 11:20 am on November 27, 2015: member
    utACK
  34. Add merkle.{h,cpp}, generic merkle root/branch algorithm ee60e5625b
  35. Switch blocks to a constant-space Merkle root/branch algorithm. 
    This switches the Merkle tree logic for blocks to one that runs in constant (small) space.
The old code is moved to tests, and a new test is added that for various combinations of
block sizes, transaction positions to compute a branch for, and mutations:
 * Verifies that the old code and new code agree for the Merkle root.
 * Verifies that the old code and new code agree for the Merkle branch.
 * Verifies that the computed Merkle branch is valid.
 * Verifies that mutations don't change the Merkle root.
 * Verifies that mutations are correctly detected.
    eece63fa72
  36. sipa force-pushed on Nov 27, 2015
  37. jtimon commented at 2:53 pm on November 27, 2015: contributor
    Oh, thought I had done it already…concept ACK
  38. sipa merged this on Nov 28, 2015
  39. sipa closed this on Nov 28, 2015
  40. sipa referenced this in commit 61457c29d7 on Nov 28, 2015
  41. jgarzik commented at 9:28 pm on November 28, 2015: contributor
    utACK
  42. Warrows referenced this in commit 5e602b6215 on Jul 20, 2019
  43. Warrows referenced this in commit 5304fdff25 on Jul 28, 2019
  44. Warrows referenced this in commit a9c9790cf0 on Aug 4, 2019
  45. Warrows referenced this in commit bed7c034f6 on Sep 11, 2019
  46. Warrows referenced this in commit 0e75b62081 on Sep 23, 2019
  47. Warrows referenced this in commit ab9efb8a69 on Oct 9, 2019
  48. random-zebra referenced this in commit 0f1764a3db on Oct 9, 2019
  49. CaveSpectre11 referenced this in commit 9cf23986ea on Dec 14, 2019
  50. wqking referenced this in commit da99d95425 on May 24, 2020
  51. Kokary referenced this in commit 2273a477f6 on May 26, 2020
  52. Kokary referenced this in commit 9bb5cd64da on Nov 13, 2020
  53. Kokary referenced this in commit 9bdd8c0f7c on Nov 17, 2020
  54. Kokary referenced this in commit 59fb56cce3 on Nov 17, 2020
  55. KolbyML referenced this in commit d192a9cd62 on Nov 21, 2020
  56. Kokary referenced this in commit 01b21fc1f0 on Nov 24, 2020
  57. Cryptarchist referenced this in commit ceaeeed572 on Nov 30, 2020
  58. zkbot referenced this in commit 79c785d1f9 on Apr 20, 2021
  59. lyricidal referenced this in commit 178dfeb8a4 on Jul 23, 2021
  60. lyricidal referenced this in commit dab16b12ea on Jul 23, 2021
  61. MarcoFalke locked this on Sep 8, 2021


sipa dgenr8 laanwj cozz dcousens jtimon jgarzik

Labels
Validation

Milestone
0.12.0

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2025-02-02 06:13 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me