Re: [bitcoin-dev] [Lightning-dev] Taro: A Taproot Asset Representation Overlay

From: Olaoluwa Osuntokun <laolu32@gmail•com>
To: Hiroki Gondo <hiroki.gondo@nayuta•co>
Cc: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] Taro: A Taproot Asset Representation Overlay
Date: Tue, 18 Oct 2022 19:40:13 -0700	[thread overview]
Message-ID: <CAO3Pvs-2DXYT7PW-KfHcyrzWSya55w57MfKqtxq5HuAFcj3etw@mail.gmail.com> (raw)
In-Reply-To: <CAO6oAq2nC9_0GdoOQbmX3Qt4OsSYzMVBy-vyGczwn1GhLHN2Kw@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 8750 bytes --]

Hi Hiroki,

(inserting the bitcoin-dev mailing list as this question is mainly
concerning on-chain interaction)

Thanks for taking the time to really dig into things!

> When trying to verify the provenance of a given UTXO, it is necessary to
> verify the state transitions of all transaction graphs without gaps from
> the genesis transaction of the asset to the current location

> It is necessary to prove and verify that “the UTXO has not changed” at
> that point.

Correct!

> As far as I can see, the specs don't mention it.

You're correct that today the main BIP draft focuses mainly on transfers [1]
to specify how exactly an asset moves from one output to another. The
requirement that a "no-op" state transition also be created/verified is an
implicit assumption in the current spec that we aim to remedy. The current
alpha code [2] is a bit ahead of the spec, but we aim to start to catch up
the spec, and also begin to add test vectors now that we have a working
implementation.

> The proofs for directly proving that a UTXO has not changed are its
> inclusion proof in the input asset tree and its inclusion and
> non-inclusion proofs in each of the output asset trees

Correct, the set of inclusion and non-inclusion proofs necessary for a valid
state transition are currently documented in `bip-taro-proof-file.md` [3].
We've also made a few updates to the proof file format to properly include a
field for the inclusion proof of a split asset's _root_ asset. This allows
verifiers to properly verify the authenticity of the split (root is in the
transaction, uniquely, which commits to the split, which has a proof
anchored in that spit root).

> Instead, it's better to set a constraint that no part of the asset tree
> except the explicitly changed UTXOs should change, and verify that.

Interesting, so rather than present/maintain a distinct state transition for
each asset unaffected, you propose that instead we present a _single_ proof
for all non-modified assets that shows that a sub-tree/branch is unchanged?
That's a very cool idea.

Generally we have a lot of low hanging fruits re optimizing the proof file
format itself. As an example, all assets in a tree will share the same
Bitcoin-level proof prefix (merkle proof and block header of the anchor
transaction), but the spec/implementation will currently duplicate those
values several times over for each asset. If we go down another level, then
the main inclusion proof for an asset ID tree is also duplicated for each
asset sharing that asset ID.

Restating things a bit: right now proofs are oriented from the PoV of an
asset leaf in question. Instead, if we zoom out a bit and orient them at the
_taproot output_ level, then we can remove a lot of redundant data in the
current proof format, then sort of "prune" the output level proof to
generate a proof for a single leaf.

-- Laolu

[1]:
https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro.mediawiki#asset-transfers
[2]: https://github.com/lightninglabs/taro
[3]:
https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-proof-file.mediawiki#specification

On Fri, Oct 7, 2022 at 2:33 AM Hiroki Gondo <hiroki.gondo@nayuta•co> wrote:

> Hi Laolu,
>
> I've read Taro's specs, but I'm afraid there's not enough verification of
> the provenance of the asset UTXOs.
>
> When trying to verify the provenance of a given UTXO, it is necessary to
> verify the state transitions of all transaction graphs without gaps from
> the genesis transaction of the asset to the current location. At some point
> in the transaction, the target UTXO itself may not change (only changes to
> other assets or other UTXOs in the asset tree). It is necessary to prove
> and verify that “the UTXO has not changed” at that point. As far as I can
> see, the specs don't mention it.
>
> Without this validation, asset inflation (double spending) is possible. In
> a transaction, there is a UTXO in the input asset tree. If this UTXO does
> not change in this transaction, it will remain in the output asset tree.
> However, if a full copy of this UTXO is illicitly created in the asset tree
> of another output, the asset will be inflated (even duplicating the lowest
> MS-SMT entirely). Both UTXOs will arbitrarily claim to be the same as the
> input UTXO.
>
> The proofs for directly proving that a UTXO has not changed are its
> inclusion proof in the input asset tree and its inclusion and non-inclusion
> proofs in each of the output asset trees. However, generating these proofs
> for every unchanging UTXO present in the input asset tree when a
> transaction occurs may not be very practical. Instead, it's better to set a
> constraint that no part of the asset tree except the explicitly changed
> UTXOs should change, and verify that.
>
> Please let me know if I'm wrong or have overlooked any specs. Also, let me
> know if there's anything about this that hasn't been mentioned in the specs
> yet.
>
> –
> Hiroki Gondo
>
>
> 2022年4月6日(水) 0:06 Olaoluwa Osuntokun <laolu32@gmail•com>:
>
>> Hi y'all,
>>
>> I'm excited to publicly publish a new protocol I've been working on over
>> the
>> past few months: Taro. Taro is a Taproot Asset Representation Overlay
>> which
>> allows the issuance of normal and also collectible assets on the main
>> Bitcoin
>> chain. Taro uses the Taproot script tree to commit extra asset structured
>> meta
>> data based on a hybrid merkle tree I call a Merkle Sum Sparse Merkle Tree
>> or
>> MS-SMT. An MS-SMT combined the properties of a merkle sum tree, with a
>> sparse
>> merkle tree, enabling things like easily verifiable asset supply proofs
>> and
>> also efficient proofs of non existence (eg: you prove to me you're no
>> longer
>> committing to the 1-of-1 holographic beefzard card during our swap). Taro
>> asset
>> transfers are then embedded in a virtual/overlay transaction graph which
>> uses a
>> chain of asset witnesses to provably track the transfer of assets across
>> taproot outputs. Taro also has a scripting system, which allows for
>> programmatic unlocking/transfer of assets. In the first version, the
>> scripting
>> system is actually a recursive instance of the Bitcoin Script Taproot VM,
>> meaning anything that can be expressed in the latest version of Script
>> can be
>> expressed in the Taro scripting system. Future versions of the scripting
>> system
>> can introduce new functionality on the Taro layer, like covenants or other
>> updates.
>>
>> The Taro design also supports integration with the Lightning Network
>> (BOLTs) as
>> the scripting system can be used to emulate the existing HTLC structure,
>> which
>> allows for multi-hop transfers of Taro assets. Rather than modify the
>> internal
>> network, the protocol proposes to instead only recognize "assets at the
>> edges",
>> which means that only the sender+receiver actually need to know about and
>> validate the assets. This deployment route means that we don't need to
>> build up
>> an entirely new network and liquidity for each asset. Instead, all asset
>> transfers will utilize the Bitcoin backbone of the Lightning Network,
>> which
>> means that the internal routers just see Bitcoin transfers as normal, and
>> don't
>> even know about assets at the edges. As a result, increased demand for
>> transfers of these assets as the edges (say like a USD stablecoin), which
>> in
>> will turn generate increased demand of LN capacity, result in more
>> transfers, and
>> also more routing revenue for the Bitcoin backbone nodes.
>>
>> The set of BIPs are a multi-part suite, with the following breakdown:
>>  * The main Taro protocol:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro.mediawiki
>>  * The MS-SMT structure:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-ms-smt.mediawiki
>>  * The Taro VM:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-vm.mediawiki
>>  * The Taro address format:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-addr.mediawiki
>>  * The Taro Universe concept:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-universe.mediawiki
>>  * The Taro flat file proof format:
>> https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-proof-file.mediawiki
>>
>> Rather than post them all in line (as the text wouldn't fit in the
>> allowed size
>> limit), all the BIPs can be found above.
>>
>> -- Laolu
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 10507 bytes --]