From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 29E32C002C for ; Fri, 8 Apr 2022 17:48:17 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 167AF40190 for ; Fri, 8 Apr 2022 17:48:17 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.848 X-Spam-Level: X-Spam-Status: No, score=-1.848 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, 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: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pcWGy-dg1TuH for ; Fri, 8 Apr 2022 17:48:15 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by smtp2.osuosl.org (Postfix) with ESMTPS id 4F97140169 for ; Fri, 8 Apr 2022 17:48:15 +0000 (UTC) Received: by mail-wr1-x42a.google.com with SMTP id d29so13968231wra.10 for ; Fri, 08 Apr 2022 10:48:15 -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=oxUegwesIaz78Oadc1EN8Pe8aUA/puWbNVt50OYz5Sw=; b=AoAxI0V6xx7N9Q7yhDtxriimylMfKVzRb/poGz/bOoZ2xjMIr9e3VYbSEnh8NF/kaS flJyBpq5N7kMdkCeKlVHIrqcO8WbxNgJLOzuRGLfkzHoQJKikQ2qw9c4HJqN0nbVJgbg 0FPr9qPj22FWW+YtVz54Mv5/zTJzwnSNZfYQ5J761KPJspl0+tCINOLFS1iAcAFURyRj jKAN17E88v9tzTdmYqdvVx4ZimYvgdE4kMyE4jaiV9RCIGOqeVrwKQq0Obk6YIVpXQbW tgMhl3x6GjCRJHFD+/Lugxt4zsKPXnvCwfwUEon8Zu2rvXmlUZuCJAQ5webLojLWuhDL 0ISw== 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=oxUegwesIaz78Oadc1EN8Pe8aUA/puWbNVt50OYz5Sw=; b=Tl08MaFQ20LuXC9MaylQ28lTDIoBWb4gJkD0G3FT73bD/5cJ4DmssunCdpTZWgiZfa AQh0KrHrjP1vL0jArQRYtIhkteLekA44zyKkrwMb8yXkefAt24ij+mXjXBDmH9gNqKEY M0vof+bh2vJbXZ/GN+9oYmXrOTpS+5dHWnvcV+YvkO2ErDXAAiaS6OWSvBZMax6QDDEr 42BMWljImTucRJeUX5KC6Zbe/K+UjBGNSQAiLLkoZOiEEIvA7vOBaA2AKRVspSF17Y7U ES5Ef8SDplInhOACUrYrWqUl55UmeehI2qGCKruCYx8X62tbSFmCjTtRR14pgnnV+tzq wivQ== X-Gm-Message-State: AOAM533hxDQGT+C7oOAm8Y8Zbaf/jtLCFFfEoDEiGMsgffPouV5LFer9 55awhC5UvmBvsZ6CaMN5JeFkcJEqjaEY5ySCypvu1oXsJCs= X-Google-Smtp-Source: ABdhPJxQp3+36ITQ65Tun6O1e46T+uEUpSptJMlyqHr6jnv/FcwVr2QgBH2RVSz9fDslhibsCPUxNm6HxXRUZYgF724= X-Received: by 2002:adf:f84d:0:b0:206:1098:dede with SMTP id d13-20020adff84d000000b002061098dedemr15875286wrq.677.1649440093338; Fri, 08 Apr 2022 10:48:13 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Olaoluwa Osuntokun Date: Fri, 8 Apr 2022 13:48:02 -0400 Message-ID: To: Ruben Somsen Content-Type: multipart/alternative; boundary="000000000000d7823105dc283290" 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: Fri, 08 Apr 2022 17:48:17 -0000 --000000000000d7823105dc283290 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable (this might be a double post as it ran into the size limit) Hi Ruben, Thanks! I don't really consider things final until we have a good set of test vectors in the final set, after which we'd start to transition the set of documents beyond the draft state. > Seeing as there's a large amount of overlap with RGB, a protocol which I have > examined quite extensively, I believe some of the issues I uncovered in that > project also apply here. I'm happy to hear that someone was actually able to extract enough details from the RGB devs/docs to be able to analyze it properly! In the past I tried to ask their developers questions about how things like transfers worked[1][2], but it seemed either people didn't know, or they hadn't finished the core design (large TBD sections) as they were working on adding other components to create a "new new Internet". > Furthermore, the Taro script is not enforced by Bitcoin, meaning those wh= o > control the Bitcoin script can always choose to ignore the Taro script an= d > destroy the Taro assets as a result. This is correct, as a result in most contexts, an incentive exists for the holder of an asset to observe the Taro validation rules as otherwise, their assets are burnt in the process from the PoV of asset verifiers. In the single party case things are pretty straight forward, but more care needs to be taken in cases where one attempts to express partial application and permits anyone to spend a UTXO in question. By strongly binding all assets to Bitcoin UTXOs, we resolve issues related to double spending or duplicate assets, but needs to mind the fact that assets can be burnt if a user doesn't supply a valid witness. There're likely ways to get around this by lessening the binding to Bitcoin UTXO's, but then the system would need to be able to collect, retain and order all the set of possible spends, essentially requiring a parallel network. The core of the system as it stands today is pretty simple (which was an explicit design goal to avoid getting forever distracted by the large design space), with a minimal implementation being relatively compact given all the Bitcoin context/desig= n re-use. Also one cool trait of the way commitments are designed is that the Taro commitment impact the final derived taproot output key. As a result, potential Script extensions like TAPLEAF_UPDATE_VERIFY can actually be used to furthe= r _bind_ Taro transitions at the Bitcoin level, without Bitcoin explicitly needing to be aware of the Taro rules. In short, covenants can allow Bitcoi= n Script to bind Taro state transitions, without any of the logic bleeding over, as the covenant just checks for a certain output key, which is a function o= f the Taro commitment being present. > There are two possible designs here: a.) The token history remains separate =E2=80=93 > Dave receives Alice's 2 tokens, Bob's tokens are split and he receives 2 (or > 3 from Bob 1 from Alice). b.) The token history gets merged =E2=80=93 Da= ve receives > 4 tokens (linking the new output with both Alice and Bob's history). Mechanically, with respect to the way the change/UTXOs work in the system, both are expressible: Dave can chose to merge them into a single UTXO (with the appropriate witnesses included for each of them), or Dave can keep them distinct in the asset tree. You're correct in that asset issuers may opt to issue assets in denominations vs allowing them to be fully divisible. Ultimately, the compatibility with the LN layer will be the primary way to keep asset histories compressed, without relying on another trust model, or relying on the incentive of an asset issuer to do a "re-genesis" which would effectively re-create assets in a supply-preserving manner (burn N units, then produce a new genesis outpoint for N units). Alternatively, implementations can also chose to utilize a checkpointing system similar to what some Bitcoin full node clients do today. > is that you end up with a linked transaction graph, just like in Bitcoin This is correct, the protocol doesn't claim to achieve better privacy guarantees than the base chain. However inheriting this transaction graph model imo makes it easier for existing Bitcoin developers to interact with the system, and all the data structures are very familiar tooling wise. However any privacy enhancing protocol used for on-chain top-level Bitcoin UTXOs can also be applied to Taro, so people can use things like coinswap and coinjoin, along with LN to shed prior coin lineages. > This implies the location of the Taro tree inside the taproot tree is not > fixed. What needs to be prevented here is that a taproot tree contains more > than one Taro tree, as that would enable the owner of the commitment to show > different histories to different people. Great observation, I patched a similar issue much earlier in the design process by strongly binding all signatures to a prevOut super-set (so the outpoint along with the unique key apth down into the tree), which prevents duplicating the asset across outputs, as signature verification would fail. In terms of achieving this level of binding within the Taro tree itself, I can think of three options: 1. Require the Taro commitment to be in the first/last position within th= e (fully sorted?) Tapscript tree, and also require its sibling to be the hash of some set string (all zeroes or w/e). We'd require the sibling to the empty as the tapscript hashes are sorted before hashing so you sort of lose tha= t final ordering information. 2. Include the position of the Taro commitment within the tapscript tree within the sighash digest (basically the way the single input in the virtual transaction is created from the TLV structure). 3. Include the position of the Taro commitment within the tapscript tree as part of the message that's hashed to derive asset IDs. AFAICT, #1 resolves the issue entirely, #2 renders transfers outside of the canonical history invalid, and #2 minds hte asset ID to the initial positio= n meaning you can track a canonical lineage from the very start. > Finally, let me conclude with two questions. Could you clarify the purpose of > the sparse merkle tree in your design? Sure, it does a few things: * Non-inclusion proofs so I can do things like prove to your I'm no longe= r committing to my 1-of-1 holographic beefzard card when we swap. * The key/tree structure means that the tree is history independent, meaning that if you and I insert the same things into the tree in a different order, we'll get the same root hash. This is useful for things like tracking all the issuance events for a given asset, or allowing two entities to sync their knowledge/history of a single asset, or a set of assets. * Each asset/script mapping to a unique location within the tree means it's easy to ensure uniqueness of certain items/commitments (not possible to commit to the same asset ID twice in the tree as an example). * The merkle-sum trait means I that validation is made simpler, as you just check that the input+output commitment sum to the same value, and I can also verify that if we're swapping, then you aren't committing to more units that exist (so I make sure I don't get an invalid split). > And the second question =E2=80=93 when transferring Taro token ownership = from one > Bitcoin UTXO to another, do you generate a new UTXO for the recipient or do > you support the ability to "teleport" the tokens to an existing UTXO like how > RGB does it? If the latter, have you given consideration to timing issues > that might occur when someone sends tokens to an existing UTXO that > simultaneously happens to get spent by the owner? So for interactive transfers, the UTXOs generated as just the ones part of the MIMO transaction. When sending via the address format, a new non-dust output is created which holds the new commitment, and uses an internal key provided b= y the receiver, so only they can move the UTXO. Admittedly, I'm not familiar with how the RGB "teleport" technique works, I checked out some slide decks a while back, but they were mostly about all the new components they were creating and their milestone of 1 million lines of code. Can you point me to a coherent explanation of the technique? I'd love to compare/contrast so we can analyz= e the diff tradeoffs being made here. Thanks for an initial round of feedback/analysis, I'll be updating the draf= t over the next few days to better spell things out and particularly that commitment/sighash uniqueness trait. -- Laolu [1]: https://twitter.com/roasbeef/status/1330654936074371073?s=3D20&t=3DfeV0kWAj= J6MTQlFm06tSxA [2]: https://twitter.com/roasbeef/status/1330692571736117249?s=3D20&t=3DfeV0kWAj= J6MTQlFm06tSxA --000000000000d7823105dc283290 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
(this might be a double post as it ran into the size limit= )

Hi Ruben,

Thanks! I don't really consi= der things final until we have a good set of test
vectors in the final s= et, after which we'd start to transition the set of
documents beyond= the draft state.

> Seeing as there's a large amount of overl= ap with RGB, a protocol which I have
> examined quite extensively, I = believe some of the issues I uncovered in that
> project also apply h= ere.

I'm happy to hear that someone was actually able to extrac= t enough details from
the RGB devs/docs to be able to analyze it properl= y! In the past I tried to ask
their developers questions about how thing= s like transfers worked[1][2], but it
seemed either people didn't kn= ow, or they hadn't finished the core design
(large TBD sections) as = they were working on adding other components to create
a "new new I= nternet".

> Furthermore, the Taro script is not enforced by = Bitcoin, meaning those who
> control the Bitcoin script can always ch= oose to ignore the Taro script and
> destroy the Taro assets as a res= ult.

This is correct, as a result in most contexts, an incentive exi= sts for the
holder of an asset to observe the Taro validation rules as o= therwise, their
assets are burnt in the process from the PoV of asset ve= rifiers. In the single
party case things are pretty straight forward, bu= t more care needs to be taken
in cases where one attempts to express par= tial application and permits anyone
to spend a UTXO in question.
By strongly binding all assets to Bitcoin UTXOs, we resolve issues related= to
double spending or duplicate assets, but needs to mind the fact that= assets can
be burnt if a user doesn't supply a valid witness. There= 're likely ways to get
around this by lessening the binding to Bitco= in UTXO's, but then the system
would need to be able to collect, ret= ain and order all the set of possible
spends, essentially requiring a pa= rallel network. The core of the system as it
stands today is pretty simp= le (which was an explicit design goal to avoid
getting forever distracte= d by the large design space), with a minimal
implementation being relati= vely compact given all the Bitcoin context/design
re-use.

Also on= e cool trait of the way commitments are designed is that the Taro
commit= ment impact the final derived taproot output key. As a result, potentialScript extensions like TAPLEAF_UPDATE_VERIFY can actually be used to furth= er
_bind_ Taro transitions at the Bitcoin level, without Bitcoin explici= tly
needing to be aware of the Taro rules. In short, covenants can allo= w Bitcoin
Script to bind Taro state transitions, without any of the logi= c bleeding over,
as the covenant just checks for a certain output key, w= hich is a function of
the Taro commitment being present.

> The= re are two possible designs here: a.) The token history remains separate = =E2=80=93
> Dave receives Alice's 2 tokens, Bob's tokens are = split and he receives 2 (or
> 3 from Bob 1 from Alice). =C2=A0b.) The= token history gets merged =E2=80=93 Dave receives
> 4 tokens (linkin= g the new output with both Alice and Bob's history).

Mechanicall= y, with respect to the way the change/UTXOs work in the system, both
are= expressible: Dave can chose to merge them into a single UTXO (with the
= appropriate witnesses included for each of them), or Dave can keep them
= distinct in the asset tree. You're correct in that asset issuers may op= t to
issue assets in denominations vs allowing them to be fully divisibl= e.
Ultimately, the compatibility with the LN layer will be the primary w= ay to keep
asset histories compressed, without relying on another trust = model, or relying
on the incentive of an asset issuer to do a "re-g= enesis" which would
effectively re-create assets in a supply-preser= ving manner (burn N units, then
produce a new genesis outpoint for N uni= ts). Alternatively, implementations can
also chose to utilize a checkpoi= nting system similar to what some Bitcoin full
node clients do today.
> =C2=A0is that you end up with a linked transaction graph, just li= ke in Bitcoin

This is correct, the protocol doesn't claim to ach= ieve better privacy
guarantees than the base chain. However inheriting t= his transaction graph model
imo makes it easier for existing Bitcoin dev= elopers to interact with the
system, and all the data structures are ver= y familiar tooling wise. However any
privacy enhancing protocol used for= on-chain top-level Bitcoin UTXOs can also
be applied to Taro, so people= can use things like coinswap and coinjoin, along
with LN to shed prior = coin lineages.

> This implies the location of the Taro tree insid= e the taproot tree is not
> fixed. What needs to be prevented here is= that a taproot tree contains more
> than one Taro tree, as that woul= d enable the owner of the commitment to show
> different histories to= different people.

Great observation, I patched a similar issue much= earlier in the design process
by strongly binding all signatures to a p= revOut super-set (so the outpoint
along with the unique key apth down in= to the tree), which prevents duplicating
the asset across outputs, as si= gnature verification would fail.

In terms of achieving this level of= binding within the Taro tree itself, I can
think of three options:
<= br>=C2=A0 1. Require the Taro commitment to be in the first/last position w= ithin the
=C2=A0 (fully sorted?) Tapscript tree, and also require its si= bling to be the hash
=C2=A0 of some set string (all zeroes or w/e). We&#= 39;d require the sibling to the empty
=C2=A0 as the tapscript hashes are= sorted before hashing so you sort of lose that
=C2=A0 final ordering in= formation.

=C2=A0 2. Include the position of the Taro commitment wit= hin the tapscript tree
=C2=A0 within the sighash digest (basically the w= ay the single input in the virtual
=C2=A0 transaction is created from th= e TLV structure).

=C2=A0 3. Include the position of the Taro commitm= ent within the tapscript tree as
=C2=A0 part of the message that's h= ashed to derive asset IDs.

AFAICT, #1 resolves the issue entirely, #= 2 renders transfers outside of the
canonical history invalid, and #2 min= ds hte asset ID to the initial position
meaning you can track a canonica= l lineage from the very start.

> Finally, let me conclude with tw= o questions. Could you clarify the purpose of
> the sparse merkle tre= e in your design?

Sure, it does a few things:

=C2=A0 * Non-i= nclusion proofs so I can do things like prove to your I'm no longer
= =C2=A0 =C2=A0 committing to my 1-of-1 holographic beefzard card when we swa= p.

=C2=A0 * The key/tree structure means that the tree is history in= dependent, meaning
=C2=A0 =C2=A0 that if you and I insert the same thing= s into the tree in a different
=C2=A0 =C2=A0 order, we'll get the sa= me root hash. This is useful for things like
=C2=A0 =C2=A0 tracking all = the issuance events for a given asset, or allowing two
=C2=A0 =C2=A0 ent= ities to sync their knowledge/history of a single asset, or a set of
=C2= =A0 =C2=A0 assets.

=C2=A0 * Each asset/script mapping to a unique lo= cation within the tree means it's
=C2=A0 =C2=A0 easy to ensure uniqu= eness of certain items/commitments (not possible to
=C2=A0 =C2=A0 commit= to the same asset ID twice in the tree as an example).

=C2=A0 * The= merkle-sum trait means I that validation is made simpler, as you just
= =C2=A0 =C2=A0 check that the input+output commitment sum to the same value,= and I can
=C2=A0 =C2=A0 also verify that if we're swapping, then yo= u aren't committing to more
=C2=A0 =C2=A0 units that exist (so I mak= e sure I don't get an invalid split).

> And the second questi= on =E2=80=93 when transferring Taro token ownership from one
> Bitcoi= n UTXO to another, do you generate a new UTXO for the recipient or do
&g= t; you support the ability to "teleport" the tokens to an existin= g UTXO like how
> RGB does it? If the latter, have you given consider= ation to timing issues
> that might occur when someone sends tokens t= o an existing UTXO that
> simultaneously happens to get spent by the = owner?

So for interactive transfers, the UTXOs generated as just the= ones part of the
MIMO transaction. When sending via the address format,= a new non-dust output is
created which holds the new commitment, and us= es an internal key provided by
the receiver, so only they can move the U= TXO. Admittedly, I'm not familiar with
how the RGB "teleport&qu= ot; technique works, I checked out some slide=C2=A0decks a while
back, b= ut they were mostly about all the new components they were creating and
= their milestone of 1 million lines of code. Can you point me to a coherent<= br>explanation of the technique? I'd love to compare/contrast so we can= analyze
the diff tradeoffs being made here.

Thanks for an initia= l round of feedback/analysis, I'll be updating the draft
over the ne= xt few days to better spell things out and particularly that
commitment/= sighash uniqueness trait.

-- Laolu

[1]: https://twitter.com/roasbeef/status/1330654936074371073?s=3D20&am= p;t=3DfeV0kWAjJ6MTQlFm06tSxA
[2]: htt= ps://twitter.com/roasbeef/status/1330692571736117249?s=3D20&t=3DfeV0kWA= jJ6MTQlFm06tSxA
--000000000000d7823105dc283290--