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