Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 79383C002C for ; Sat, 16 Apr 2022 02:43:23 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 5198D41A6B for ; Sat, 16 Apr 2022 02:43:23 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.847 X-Spam-Level: X-Spam-Status: No, score=-1.847 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, FUZZY_CPILL=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fZ6TF9qvS2OE for ; Sat, 16 Apr 2022 02:43:21 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by smtp4.osuosl.org (Postfix) with ESMTPS id 61ABD41A5F for ; Sat, 16 Apr 2022 02:43:21 +0000 (UTC) Received: by mail-wr1-x429.google.com with SMTP id q3so11806186wrj.7 for ; Fri, 15 Apr 2022 19:43:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=jRQu5cO+8lQo4zGKRTR0yUFNrJjZv3Ae+3ZHzBxeh+g=; b=WCyHTSYfO0Y5cYCFwyTdJc/8/7FqtCpU6o9zdxGSOIvruInfu0kQR7h63F7PI2rY/p 8+rGfL1ADRYvgJgqQVUyWpPHUi7Vm6N6qUj+IwDyNIjmoTVfCkUT0FnHjCjCKKwgiBSv WMSFd1PXMYCknBMywrUVRRALGVDUjamrYftRogg9kPCkmomoDKOz1wRDVA4ZvPY0dGbM 8qQsnOEq6kDqYvBy7voLJTeeswBTpPW/ND04kGUb6MzS9TaJoydCP6MGqdnd5tKmlzrF BB2kAjIlV8SbgXDEBsk1inNZt4S2sHE2WwtBH4mf4V9u3o8bWkeZz5+QJo9tH7f2r5fj ZGkA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=jRQu5cO+8lQo4zGKRTR0yUFNrJjZv3Ae+3ZHzBxeh+g=; b=C24kjhqlWjOFnQRAzfKUXNQKRPf4Mh9PJRe2ubusawJwLR7gQIFKR+2VDXS7JyAWhE wSbGrXl8lD76+7P1DX+DcsWJaGHwDxx6jscr5IcmBR23ZG2NYE76n3flc3TVEctCJh6b ObFWCb78pz8AdtqTg9iL3dZyxfO1Ptgv/B1vEH7hG3tyU30cutqhFK1YO1DRG0NfRwaA BWnoSwJ7auX9NAj+cJqQRWxOrfcjQsrfPF5IiSCivWv3U5hUjtKhnCICXRr/Vinx+4e/ LEKwv57rAd/OT60iWsSdbnObafg5bZKYiu2BCwPU7KDGW6RYDglsencY+tmYUkHOxptM 513g== X-Gm-Message-State: AOAM531vBMpm3oBaU7xoHGeUcdA2hMqCOw7gbUeUz2RlhN/CYGa4OEY7 ZNM3BL48KatJ16ihxOHR97YfTDABXTWQyIWq8pntUmIZiqo= X-Google-Smtp-Source: ABdhPJx5Qu/He7CcM0c6w1SYj4Q9uGygQNLzW/HbVPv31Cm4bDx4PooMvPWTvr8u5Ykm93ilBvgEH7wtfkioweX3NNI= X-Received: by 2002:adf:914f:0:b0:1ed:bb92:d0cc with SMTP id j73-20020adf914f000000b001edbb92d0ccmr1102133wrj.297.1650076999240; Fri, 15 Apr 2022 19:43:19 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Olaoluwa Osuntokun Date: Fri, 15 Apr 2022 19:43:08 -0700 Message-ID: To: Ruben Somsen Content-Type: multipart/alternative; boundary="00000000000064523705dcbc7d9c" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Taro: A Taproot Asset Representation Overlay X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 16 Apr 2022 02:43:23 -0000 --00000000000064523705dcbc7d9c Content-Type: text/plain; charset="UTF-8" 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 --00000000000064523705dcbc7d9c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi y'all,

> In terms of achieving this leve= l of binding within the Taro tree itself, I
> can think of three opti= ons:

The earlier BIP draft just sort of said "the commitment sh= ould be unique"
and hand waved away the exact algorithm used to ver= ify this key property. I
thought about a few ways to do this, but most o= f them can't work, as the
taproot tree is always sorting the sibling= s before hashing them into a parent.
This sorting means that all orderin= g information is lost, and can't be
obtained again afaict.

To= get around this limitation, I've proposed a concrete scheme here to bo= th
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 pr= operty. At a high level the scheme takes advantage of the tagged hash
sc= heme used in taproot: leaves use "TapLeaf" as the tag, and branch= es use
"TapBranch" as the tag. Building upon this, we then req= uire the Taro
commitment to be in the leftmost/rightmost (remember order= ing info is lost)
of the tree. From here we can decompose things into a = few different cases:

=C2=A0 * The control block proof is 32 bytes, m= eaning there's only a single
=C2=A0 =C2=A0 element, so verify the ta= ro commitment and the taproot commitment is
=C2=A0 =C2=A0 correct.
=C2=A0 * The proof is instead 64 bytes, meaning there's a leaf at dep= th 1 with a
=C2=A0 =C2=A0 sibling:
=C2=A0 =C2=A0 * If the sibling is = a leaf, then verify the pre-image is 32 bytes and
=C2=A0 =C2=A0 =C2=A0 t= he tagged hash calc matches up.
=C2=A0 =C2=A0 * If the sibling is a bran= ch, then verify that hashing the two opaque
=C2=A0 =C2=A0 =C2=A0 sibling= s 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
stand= ardized 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 mor= e
common things higher up in the tree, or always try to make the tree un= iform,
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 me= rged with the final branch.
After that you just keep on merging. It'= s not the most optimized/efficient
routine but it's simple which cou= nts 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 im= pact for items in the script tree
itself isn't too bad as it just me= ans an extra 32 byte hash in the control
block proof when it comes to re= veal 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 m= ake sense to roll out
a distinct BIP that carves out an explicit structu= re/split. As an example, a
new standard could be created that pushes all= the actual scripts to the
"left" and everything else to the &= quot;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),
t= hen 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 (u= txo
commitments, etc, etc)?

-- Laolu

[1]: https://github.com/btcsuite/btcd/blob/99e4e0034501= 7a70eadc4e1d06353c56b23bb15c/txscript/taproot.go#L618
--00000000000064523705dcbc7d9c--