Hi y'all, > In terms of achieving this level of binding within the Taro tree itself, I > can think of three options:
The earlier BIP draft just sort of said "the commitment should be unique" and hand waved away the exact algorithm used to verify this key property. I thought about a few ways to do this, but most of them can't work, as the taproot tree is always sorting the siblings before hashing them into a parent. This sorting means that all ordering information is lost, and can't be obtained again afaict. To get around this limitation, I've proposed a concrete scheme here to both verify that the commitment is in a unique place within the tree, and also that it doesn't exist anywhere else in the transaction (assumes widespread usage of BIP 86): https://github.com/Roasbeef/bips/pull/21. A series of inclusion and non-inclusion proofs are used to construct+verify this property. At a high level the scheme takes advantage of the tagged hash scheme used in taproot: leaves use "TapLeaf" as the tag, and branches use "TapBranch" as the tag. Building upon this, we then require the Taro commitment to be in the leftmost/rightmost (remember ordering info is lost) of the tree. From here we can decompose things into a few different cases: * The control block proof is 32 bytes, meaning there's only a single element, so verify the taro commitment and the taproot commitment is correct. * The proof is instead 64 bytes, meaning there's a leaf at depth 1 with a sibling: * If the sibling is a leaf, then verify the pre-image is 32 bytes and the tagged hash calc matches up. * If the sibling is a branch, then verify that hashing the two opaque siblings that make it up gives the same branch (tap hash branch). >From the PoV of wallets, this isn't too hard to manage as a Taro library can just take the existing root of the wallet's scripts, and merge that into a new root with the Taro leaf hanging off to the side. As an aside, one thing that's missing in the ecosystem today is a standardized algorithm for constructing a taproot tree given a set of script leaves. The tree constructor has a lot of freedom to do things like put more common things higher up in the tree, or always try to make the tree uniform, etc, etc. The btcsuite libraries use a simple algo [1] I came up with that just merges leaves into branches until there're no leaves left (even number) or there's one leaf, with that last leaf being merged with the final branch. After that you just keep on merging. It's not the most optimized/efficient routine but it's simple which counts for a lot IMO. Admittedly as is defined in my PR above, Taro is a bit demanding w.r.t commitment space: it wants the highest position in the tree as that's easy to verify and makes a smaller proof. The impact for items in the script tree itself isn't too bad as it just means an extra 32 byte hash in the control block proof when it comes to reveal time, and that's witness data which is discounted at the block size level. Zooming out a bit, assuming that applications/protocols start making more structured commitments in the tapscript tree, it may make sense to roll out a distinct BIP that carves out an explicit structure/split. As an example, a new standard could be created that pushes all the actual scripts to the "left" and everything else to the "right". In the "right" part of the tree, we can use w/e tree structure we want, so we aren't bound by the sorting quirk. If each project picks some 32-byte value (a hash of the name or w/e), then another SMT (or w/e other merklalized k-v map) can be used to place each root commitment in a unique location in the tree. Maybe something like this also becomes the basis of future consensus-critical commitments (utxo commitments, etc, etc)? -- Laolu [1]: https://github.com/btcsuite/btcd/blob/99e4e00345017a70eadc4e1d06353c56b23bb15c/txscript/taproot.go#L618
_______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
