BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY; Tail Call Execution Semantics #610

1. 
   kallewoof commented at 3:37 am on November 15, 2017: member
2. kallewoof force-pushed on Nov 15, 2017
3. kallewoof force-pushed on Nov 15, 2017
4. kallewoof force-pushed on Nov 15, 2017
5. luke-jr changes_requested
6. 
   luke-jr commented at 2:09 pm on November 15, 2017: member

   These are missing a section addressing backward compatibility (it can be brief), as well as the Copyright section.
7. luke-jr added the label New BIP on Nov 15, 2017
8. luke-jr renamed this:
   BIP-98, 116, 117
   BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY (Consensus layer); Tail Call Execution Semantics
   on Nov 15, 2017
9. 
   luke-jr commented at 2:10 pm on November 15, 2017: member

   “(Consensus layer)” in the title of BIP 116 might be redundant with the Layer header, considering there’s only one MERKLEBRANCHVERIFY BIP.
10. kallewoof force-pushed on Nov 16, 2017
11. kallewoof renamed this:
    BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY (Consensus layer); Tail Call Execution Semantics
    BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY; Tail Call Execution Semantics
    on Nov 16, 2017
12. 
    kallewoof commented at 3:43 am on November 16, 2017: member

    Added copyright sections. Will work out backwards compatibility and push changes.
13. BIP-0098: Fast Merkle Trees e61b25087d
14. BIP-0116: MERKLEBRANCHVERIFY (Consensus layer) 5dc731292d
15. BIP-0117: Tail Call Execution Semantics (Consensus layer) 689f2a5d02
16. Updated README to include BIPs 98, 116, 117. 5df90e1ae8
17. kallewoof force-pushed on Nov 16, 2017
18. 
    kallewoof commented at 6:49 am on November 16, 2017: member

    Added compatibility sections.
19. luke-jr approved
20. luke-jr merged this on Nov 16, 2017
21. luke-jr closed this on Nov 16, 2017

    ---

22. 
    alexanderkjeldaas commented at 3:44 pm on June 25, 2018: none

    A quick read-through… there are a few things I would like to see in this BIP. At least they would make it clearer to me. There should be a more comprehensive section on what this is NOT about. For example:

    1. Who will be interpreting the proofs? It seems like this is for the specific case where the receiver has no context or existing hashes. This should be clarified. If the receiver has a database of existing hashes, then much more efficient encodings are available (as used by git when displaying hashes for example).
    2. The encoding seems to be focusing on defining multiple items in a set. How about the single item case?
    3. SKIP, DESCEND, and VERIFY are not defined.
    4. I’m not sure, but it seems like some of the tree layouts are impossible in certain cases, for example when N-1 nodes have been defined, then the Nth node can’t have any shape.

    All in all, for various more focused cases, I’m guessing that the encoding could be significantly smaller than this.

    On generic way of compressing the encoding would be to slice the hashes so 1 bit is encoded on each hash throughout the tree before the next bit is encoded. This makes it possible to truncate the tree at some arbitrary point in order to use truncated hashes that can still be unique given some semantic rule as to how to order hashes.

Contributors
kallewoof luke-jr alexanderkjeldaas

Labels
New BIP