No description provided.
BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY; Tail Call Execution Semantics #610
pull kallewoof wants to merge 4 commits into bitcoin:master from kallewoof:bip-fmt-mbv-tcs changing 13 files +814 −0-
kallewoof commented at 3:37 AM on November 15, 2017: member
- kallewoof force-pushed on Nov 15, 2017
- kallewoof force-pushed on Nov 15, 2017
- kallewoof force-pushed on Nov 15, 2017
- luke-jr changes_requested
-
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.
- luke-jr added the label New BIP on Nov 15, 2017
- 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 -
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.
- kallewoof force-pushed on Nov 16, 2017
- 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 -
kallewoof commented at 3:43 AM on November 16, 2017: member
Added copyright sections. Will work out backwards compatibility and push changes.
-
BIP-0098: Fast Merkle Trees e61b25087d
-
BIP-0116: MERKLEBRANCHVERIFY (Consensus layer) 5dc731292d
-
BIP-0117: Tail Call Execution Semantics (Consensus layer) 689f2a5d02
-
Updated README to include BIPs 98, 116, 117. 5df90e1ae8
- kallewoof force-pushed on Nov 16, 2017
-
kallewoof commented at 6:49 AM on November 16, 2017: member
Added compatibility sections.
- luke-jr approved
- luke-jr merged this on Nov 16, 2017
- luke-jr closed this on Nov 16, 2017
-
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:
- 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).
- The encoding seems to be focusing on defining multiple items in a set. How about the single item case?
- SKIP, DESCEND, and VERIFY are not defined.
- 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
Labels