leaf version
This commit adds a python reference example for construction of BIP-360 outputs and control blocks.
This commit also updates the test vectors.
Looks reasonable at first glance.
cc: @cryptoquick, @EthanHeilman, @Isabelfoxenduke for owner review/sign-off.
This refactors `compute_control_block` to improve performance, and make
the function simpler to read (to me at least).
The previous version walked the entire script tree searching for the
first matching instance of the leaf node.
The new version expects the caller to pass in an explicit `path`
parameter, which tells us exactly where the leaf node lives, with
left/right steps encoded as bits in an integer. We walk down the
tree straight to that leaf node, and build the control block as we go.
This might not be the best DX for a real-world API or library, but this
is just reference code, so we can accept poor usage ergonomics if it makes
the code clearer and more explicit.
46 | + return binascii.unhexlify(h) 47 | + 48 | + 49 | +def s2w(script: str) -> List[int]: 50 | + """Convert a script/witprog hex string to a List[int] of its bytes""" 51 | + return [int(f"{script[i:i + 2]}", 16) for i in range(0, len(script), 2)]
return list(bytes.fromhex(script))
Corrected.
41 | + return sha256(tag_hash + tag_hash + data) 42 | + 43 | + 44 | +def h2b(h: str) -> bytes: 45 | + """hex-to-byte converter""" 46 | + return binascii.unhexlify(h)
Nit: It's a bit weird that you sometimes use unhexlify, and other times (L83) you use bytes.fromhex.
I agree. Several of these functions lived in different files in a larger, more general codebase I'd written. In that, I did switch between ways of doing the same thing and that turned out to be a pretty bad idea. I'll give it another once over and try to correct this.
180 | + 181 | +# 182 | +# Bech32/Bech32m Encoding 183 | +# 184 | +# Bech32 encoding code is taken from sipa (BIP-0350), and has been tested against the test vectors therein: 185 | +# https://github.com/sipa/bech32/blob/master/ref/python/tests.py
Most of this code already exists in the BIPs repository, under the reference code of BIP352 (silent payments).
https://github.com/bitcoin/bips/blob/master/bip-0352/bech32m.py @murchandamus What are your thoughts on the bech32m code duplication here? is it better to duplicate for the sake of compartmentalization, or should we update the existing code and reference it here?
I’d prefer it to be compartmentalized. This is not a software project, so I would prefer if we don’t slip into starting to maintain the reference implementations of all the BIPs here.
Would it be more convenient if we move the BIP360 reference implementations into an external repository?
That sounds great to me.
OK, i'll see about closing this PR out and moving the code to a new repository. Please give us some time to get the new repo set up and the code moved over
Should the test vectors stay in the bips repo? Test-vectors and reference implementations are inter-connected: reference implementations are tested against test-vectors and test-vectors can be updated (canonized) using a reference implementation.
Either is acceptable. Especially for small reference implementations, both are often supplied with the BIP in the auxiliary files. Especially for larger endeavors, the BIPs often just link to the reference implementation, and test vectors may be provided with the BIP or also linked to.
110 | + 111 | + 112 | +def compute_merkle_root(tree: ScriptTree) -> str: 113 | + """Recursively compute script tree merkle root""" 114 | + if isinstance(tree, dict): # Leaf 115 | + version = f"{tree['leafVersion']:x}"
It seems a bit redundant to convert the leaf version number to a hex string, only to convert it right back to bytes in the tapleaf_hash function. Maybe instead just pass the leaf version as an integer to tapleaf_hash?
Fixed in 94b0f9d. Should be g2g now.
90 | + if left < right: 91 | + return tagged_hash("TapBranch", h2b(left) + h2b(right)) 92 | + return tagged_hash("TapBranch", h2b(right) + h2b(left)) 93 | + 94 | + 95 | +def collect_leaf_hashes(tree: ScriptTree) -> List[str]:
This function seems like it is only a test helper function. Maybe it would be best to move it away from the core P2MR reference code?
Moved collect_leaf_hashes down to the "BIP-360 Test Code" section.
87 | + 88 | +def tapbranch_hash(left: str, right: str) -> bytes: 89 | + """Hash function for tree branches""" 90 | + if left < right: 91 | + return tagged_hash("TapBranch", h2b(left) + h2b(right)) 92 | + return tagged_hash("TapBranch", h2b(right) + h2b(left))
Optional suggestion:
return tagged_hash("TapBranch", b"".join(sorted((h2b(right) + h2b(left)))))
Oops, my suggestion was mistaken.
Should be:
return tagged_hash("TapBranch", b"".join(sorted((h2b(right), h2b(left)))))
122 | + # more than 2 children sequentially would not produce a valid 123 | + # P2MR merkle root. It would also break here on a type mismatch. 124 | + # `tapbranch_hash` returns bytes, not the hex str this loop expects. 125 | + assert len(tree) == 2, f"expected binary branch, got {len(tree)} children" 126 | + left, right = compute_merkle_root(tree[0]), compute_merkle_root(tree[1]) 127 | + return tapbranch_hash(left, right).hex()
Some of these functions accept or return hex-strings, while others use bytes for the same conceptual objects. Consistency is better: Either use hex strings for everything, or use bytes for everything. Input from test vectors (or output from the code) can be converted as needed in the tests.
Took a stab at this in 94b0f9d. It also cleaned up the code quite a bit in places.
130 | + raise ValueError("Invalid tree node") 131 | + 132 | + 133 | +def compute_control_block( 134 | + leaf: Dict[str, Any], tree: ScriptTree, path: Optional[List[str]] = None 135 | +) -> Optional[str]:
This function seems a bit overcomplicated. I'd like to suggest a non-recursive alternative, which uses the bits of an int to explicitly encode the position of a target spending leaf in the script tree, without any ambiguity: https://github.com/notmike-5/bips/pull/1
Merged in above referenced PR.
bip360: simplify computing control blocks using explicit traversal paths
Implements @conduitions improvement on tapbranch_hash()
Co-authored-by: conduition <conduition@proton.me>
Standardizes all P2MR-specific functions to use bytes uniformly for
input/output. Hex conversions are now confined to two boundaries:
reading `script` field out of ScriptTree input, and comparing against
hex-encoded test vector data in `run_single_test`.
bech32 functions and s2w are left unchanged.
I think this should be renamed to "p2tr_using_v2_witness_version_error" to follow the test vector renaming.
Currently cargo test fails with:
called `Option::unwrap()` on a `None` value
After renaming it passed.
77 | +# 78 | +def tapleaf_hash(script: bytes, tapleaf_ver: int = 0xc0) -> bytes: 79 | + """Hash function for tree leaves""" 80 | + if not script: 81 | + raise ValueError("tapleaf_hash: script is required") 82 | + leaf = bytes([tapleaf_ver]) + serialize_varbytes(script)
Should we mask the version number here, as per the BIP text?
Let v = c[0] & 0xfe be the leaf version (as defined in BIP 341).
Yeah, good call.
Thanks for this work. I'm a little confused as to where it's going to land though. Is there a decision being made regarding reference implementations? Will they all be stripped from the BIPs repository? Will they be fragmented or live in a separate repository? Where is this policy and decision making documented? Who is being consulted in this decision and who are the stakeholders?
Providing the reference implementation with the BIP or linking to a branch that contains it are acceptable. @cryptoquick: If you expect that BIP360 is going to continue to evolve, it would be preferable for the reference implementation to be maintained outside of this repository to allow you to move independently of pull requests to the BIPs repository. If this PR wraps up planned work on BIP360’s reference implementation, or you are just going to PR a small count of further updates from a development branch it might as well stay here.
If you do plan on completely revamping the ideas behind BIP360 another time, it might make sense to publish the result as a separate BIP, since P2MR has been getting quite a bit of discussion already.
I can't speak to what @cryptoquick is working on, but within my sphere of knowledge I expect at least one more major change will be filed towards BIP360 in the near future, which will be to apply @starius's EC key recovery idea to get shorter EC spend witnesses (background).
I believe @starius is currently working on a separate BIP specifically for the signature scheme and plans to file a pull request to change BIP360 later once that spec is more complete. This change would not affect the core functionality or features of BIP360 - it would merely change the order of validation operations slightly. I don't believe the BIP360 python reference code would need to change (IDK about the Rust/JS code). The bulk of the complexity will live in a separate BIP.