Skip to content

Latest commit

 

History

History
343 lines (297 loc) · 19.5 KB

bip-tap-proof-file.mediawiki

File metadata and controls

343 lines (297 loc) · 19.5 KB
Raw

 BIP: ???
  Layer: Applications
  Title: Taproot Asset Flat File Proof Format
  Author: Olaoluwa Osuntokun <laolu32@gmail.com>
  Comments-Summary: No comments yet.
  Comments-URI: https://git
  Status: Draft
  Type: Standards Track
  Created: 2021-12-10
  License: BSD-2-Clause

Table of Contents

Abstract

This document defines a flat file proof format as a standardized way to package Taproot Asset proofs. The proof format itself is an append-only log of the prior lineage of a given asset. Proofs are anchored at the initial "genesis output" for a given asset. A proof of a single Taproot Asset state transition includes a Bitcoin merkle proof, a Taproot Asset merkle-sum sparse merkle tree (MS-SMT) inclusion proof, and finally a set of valid witnesses for the state transition.

Copyright

This document is licensed under the 2-clause BSD license.

Motivation

The Taproot Asset protocol is an overlay protocol that enables the representation and transfer of assets on the base Bitcoin blockchain. As Bitcoin is a UTXO-based system each asset is itself rooted at an initial "genesis" transaction, which marks the creation of said asset. An asset is therefore defined by its genesis output, as this marks its lineage. To ensure implementations are able to verify provenance proofs across the ecosystem, a standardized proof format is proposed. The proof format is a linear log of state transitions, allowing new transfers/transition to simply be append to the end of the fail.

Design

Proving provenance of an asset requires the following arguments at each point in the past history of the asset:

  • The very first snapshot of an asset is rooted at the genesis outpoint as dictated by the canonical Universe.
  • A valid merkle proof that proves the inclusion of the genesis outpoint and resulting created asset.
  • At each step/transition beyond the genesis outpoint:
    • A valid merkle proof of a transaction which spends the outpoint referenced in the prior step.
    • A valid MS-SMT opening proving the commitment of the new location of the asset.
    • A valid asset witness state transition from the prior outpoint to the new location.
    • A valid canonical Taproot Asset commitment exists for the given asset.
    • If the transaction anchoring the state transition has other Taproot (P2TR) outputs, then a valid tapscript exclusion proof to prove that the commitment isn't duplicated elsewhere.

Specification

The Taproot Asset proof file is a flat file that records each relevant state transition for a given asset to be verified. The file is verified incrementally, with verification halting if an invalid state transition or proof is encountered.

A file is a series of inclusion and state transition proofs rooted at a given genesis outpoint.

File Serialization

A single inclusion and state transition proof has the following format is a TLV blob with the following format:

  • type: 0 (version)
    • value:
      • [uint32:version]
  • type: 1 (prev_out)
    • value:
      • [36*byte:txid || output_index]
  • type: 2 (block_header)
    • value:
      • [80*byte:bitcoin_header]
  • type: 3 (anchor_tx)
    • value:
      • [...*byte:serialized_bitcoin_tx]
  • type: 4 (anchor_tx_merkle_proof)
    • value:
      • [...*byte:merkle_inclusion_proof]
  • type: 5 (taproot_asset_asset_leaf)
    • value:
      • [tlv_blob:serialized_tlv_leaf]
  • type: 6 (taproot_asset_inclusion_proofs)
    • value:
      • [...*byte:taproot_asset_taproot_proof]
        • type: 0 (output_index
          • value: [int32:index]
        • type: 1 (internal_key
          • value: [33*byte:y_parity_byte || schnorr_x_only_key]
        • type: 2 (taproot_asset_proof)
          • value: [...*byte:asset_proof]
            • type: 0 (taproot_asset_proof)
              • value: [...*byte:asset_inclusion_proof]
              • type: 0
                • value: [uint32:proof_version]
              • type: 1
                • value: [32*byte:asset_id]
              • type: 2
                • value: [...*byte:ms_smt_inclusion_proof]
            • type: 1 (taproot_asset_inclusion_proof)
              • value: [...*byte:taproot_asset_inclusion_proof]
              • type: 0
                • value: [uint32:proof_version]
              • type: 1
                • value: [...*byte:ms_smt_inclusion_proof]
              • type: 2 (taproot_sibling_preimage)
                • value: [byte:sibling_type][varint:num_bytes][...*byte:tapscript_preimage]
        • type: 3 (taproot_asset_commitment_exclusion_proof
          • value: [...*byte:taproot_exclusion_proof]
            • type: 0 (tap_image_1)
              • value: [...*byte:tapscript_preimage]
            • type: 1 (tap_image_2)
              • value: [...*byte:tapscript_preimage]
            • type: 2 (bip_86)
              • value: [byte 0x00/0x01:bip_86]
  • type: 7 (taproot_exclusion_proofs)
    • value:
      • [uint16:num_proofs][...*byte:taproot_asset_taproot_proof]
  • type: 8 (split_root_proof)
    • value:
      • [...*byte:taproot_asset_taproot_proof]
  • type: 9 (meta_reveal)
    • value:
      • [...*byte:asset_meta_reveal]
        • type: 0 (meta_type
          • value: [uint8:type]
        • type: 1 (meta_data
          • value: [*byte:meta_data_bytes]
  • type: 10 (taproot_asset_input_splits)
    • value:
      • [...*byte:nested_proof_map]
  • type: 11 (challenge_witness)
    • value:
      • [...*byte:challenge_witness]
  • type: 12 (block_height)
    • value:
      • [uint32:block_height]
  • type: 12 (asset_genesis)
    • value:
      • [32*byte:first_prev_out_hash]
      • [u32:first_prev_out_index]
      • [BigSize:tag_len]
      • [tag_len*byte:tag]
      • [BigSize:metadata_len]
      • [metadata_len*byte:metadata]
      • [u32:output_index]
      • [u8:type]
  • type: 13 (asset_group_key_reveal)
    • value:
      • [64*byte:pub_key || asset_group_script_root]
where:
  • version: is the version of the single mint or transition proof, currently fixed to value 0.
  • prev_out: is the 36-byte outpoint of the Taproot Asset committed output being spent. If this is the very first proof, then this value will be the "genesis outpoint" for the given asset.
  • block_header: is the 80-byte block header that includes a spend of the above outpoint.
  • merkle_inclusion_proof: is the merkle inclusion proof of the transaction spending the previous_outpoint. This is serialized with a BigSize length prefix as:
    • proof_node_count || serialized_proof || proof_direction_bits
    • where:
      • proof_node_count is a BigSize integer specifying the number of nodes in the proof.
      • serialized_proof is proof_node_count*32 bytes for the proof path.
      • proof_direction_bits is a bitfield of size length_of_proof with a value of 0 indicating a left direction, and 1 indicating a right direction.
  • anchor_tx: is the transaction spending the previous_outpoint. This transaction commits to at least a single Taproot Asset tree within one of its outputs.
  • taproot_asset_taproot_proof: is a nested TLV that can be used to prove either inclusion or a Taproot Asset, or the lack of a Taproot Asset commitment via the taproot_asset_commitment_exclusion_proof.
  • taproot_exclusion_proofs: is a series of _exclusion_ proofs that prove that the other outputs in a transaction don't commit to a valid Taproot Asset. This re-uses the taproot_asset_taproot_proof structure, but will only contain an taproot_asset_commitment_exclusion_proof value and not also a taproot_asset_taproot_proof value.
  • split_root_proof: is an optional taproot_asset_taproot_proof that proves the inclusion of the split commitment's root asset in case of an asset split.
  • taproot_asset_input_splits: is an optional list of nested full proofs for any additional inputs found within the resulting asset.
  • asset_meta_reveal: is an mandatory field (for genesis assets) that reveals the pre-image of the asset_meta_hash contained in the asset TLV.
    • The meta_type field can be used to indicate how to parse/render the meta data pre-image.
      • The meta type currently defined are:
        • 0: no true type, just designates an opaque data blob.
    • The meta_data is the raw meta data itself.
      • If the contained asset is a genesis asset (has a valid genesis witness), then a verifier SHOULD verify that: `sha256(tlv_encode(meta_reveal)) == asset_meta_hash`.
      • This field MUST only be present for genesis asset proofs.
  • challenge_witness is an optional asset witness over a well-defined asset state transition that proves ownership of the script_key the asset currently resides at.
  • block_height: is the block height of the block that includes a spend of the prev_out outpoint.
  • asset_genesis: is a mandatory field for genesis assets. The asset_genesis represents the preimage of the asset_id.
    • This field MUST only be present for genesis asset proofs.
  • asset_group_key_reveal: is a mandatory field (for genesis assets having a group key) that reveals the raw internal signing key and script root needed to derive the asset group key: asset_raw_group_key = asset_group_key_reveal[0:32], asset_group_script_root = asset_group_key_reveal[32:64].
    • asset_raw_group_key: is a 32-byte public key as defined by BIP-340. The raw public key is revealed at genesis in order for verifiers to to check the group key derivation. The owner of the corresponding private key is able to sign for the group key using the key spend path when minting an asset.
    • asset_group_script_root: is a 32-byte tapscript root as defined by BIP-341. The root is revealed at genesis in order for verifiers to to check the group key derivation. The root can hold arbitrary scripts that enforces conditions for minting the asset.
    • If the contained asset is a genesis asset (has a valid genesis witness), then a verifier SHOULD verify that: asset_group_key == GroupKey(asset_id, asset_raw_group_key, asset_group_script_root) according to [bip-tap].
    • This field MUST only be present for genesis asset proofs having a group key.
The final flat proof file has the following format:
  • [u32:file_version] version of proof file format, currently fixed to 0.
  • [BigSize:num_proofs] number of proofs contained in the file
  • [num_proof*proof:proofs] encoded proofs
    • [BigSize:proof_len] length of encoded proof
    • [proof_len*byte:proof_tlv_bytes] a single proof encoded as a TLV stream as defined above
    • [32*byte:proof_checksum] the checksum of the proof, which is SHA256(prev_hash || proof_tlv_bytes) where prev_hash is the checksum of the previous proof or a zero hash for the first proof.

Proof Verification

Verification of a proof file starts at the first entry (the genesis output creation) and walks forward, validating each state transition and inclusion proof in series. If any state transition is found to be invalid, then the asset proof is invalid. Otherwise, if the file is consumed in full without any violations, the proof is said to be valid.

Given a proof file for a given asset f_proof, genesis outpoint g verification is defined as follows:

  1. Verify the integrity of the proof file:
    1. For each proof, extract the proof_len, proof_len number of bytes as proof_tlv_bytes and 32 bytes proof_checksum.
    2. Compute SHA256(prev_hash || proof_tlv_bytes) where prev_hash is the proof_checksum of the previous proof or a 32-byte zero hash for the first proof in a file.
    3. If this computed value doesn't match proof_checksum, verification fails.
  2. Verify each inclusion proof and state transition:
    1. Parse the next proof block from the flat file.
    2. If this is the first proof to be verified:
      1. Store the previous_outpoint as the genesis outpoint.
    3. Otherwise, verify that the anchor_transaction has an inputs that spends the prior previous_outpoint
    4. Given the anchor_transaction verify that the included merkle_inclusion_proof rooted at the merkle root of the block_header is valid.
    5. Parse the tlv_proof_map.
    6. If the anchor_transaction does not have at least asset_output_pos outputs, verification fails.
    7. Verify that the asset_leaf_proof embeds the taproot_asset_leaf at the outpout rooted at the asset_output_pos using the specified internal_key to compute the taproot commitment.
    8. Verify that the asset witness included at the prev_asset_witness field of the taproot_asset_leaf is valid based on the specific asset_script_version
    9. If a split_commitment_opening is present, verify that the included leaf is a valid opening rooted at the taproot_asset_leaf's split_commitment_root field.
    10. If a split_commitment_opening is present, verify that an inclusion proof for the split_commitment_root's leaf is present in split_root_proof.
    11. If the asset is a genesis asset, and the asset_meta field is present, then verify that sha256(asset_meta) == asset.asset_meta_hash
A pseudo-code routine for flat file verification follows: 

verify_asset_file_proof(file_proof []byte, genesis_outpoint OutPoint, 
    assetID [32]byte) -> bool

    genesis_outpoint, prev_outpoint = None
    file_reader = new_bytes_reader(file_proof)
    prev_hash = bytes(32)
    while file_reader.len() != 0:
        proof_block = parse_proof_block(file_reader)

        sha_sum = sh256(prev_hash + proof_block.bytes())
        if proof_block.proof_checksum != sha_sum:
            return false

        if genesis_outpoint is None:
            genesis_outpoint = proof_block.previous_outpoint

        txn = proof_block.txn
        if genesis_outpoint is not None:
           if !spends_prev_out(txn):
               return false

        if !verify_merkle_proof(
            proof_block.block_header, proof_block.merkle_inclusion_proof, txn,
        ):
            return false

        proof_tlv_map = proof_block.tlv_map

        if len(txn.outputs) < proof_tlv_map.asset_output_pos:
            return false

        if !verify_asset_tree_proof(
            txn, proof_tlv_map.taproot_asset_leaf, proof_tlv_map.asset_leaf_proof,
        ):
            return false

        if !verify_taproot_asset_state_transition(proof_tlv_map.taproot_asset_leaf):
            return false
        
        if proof_tlv_map.challenge_witness is not None:
            new_leaf = clone_unique_leaf(proof_tlv_map.taproot_asset_leaf)
            new_leaf.script_key = NUMS_key
            new_leaf.prev_witnesses = {{
                prev_id: {
                    asset_id:   proof_tlv_map.taproot_asset_leaf.asset_id
                    outpoint:   00000000...0000000:0
                    script_key: proof_tlv_map.taproot_asset_leaf.script_key
                }
                tx_witness: proof_tlv_map.challenge_witness
            }}
            
            if !verify_taproot_asset_state_transition(new_leaf):
                return false

        if proof_tlv_map.split_commitment_opening is not None:
            if !verify_split_commitment(
                proof_tlv_map.taproot_asset_leaf, 
                proof_tlv_map.split_commitment_opening,
            ):
                return false
            
            if !verify_asset_tree_proof(
                txn,
                proof_tlv_map.split_commitment_opening.split_commitment_root,
                proof_tlv_map.split_root_proof,
            ):
                return false

        has_meta_reveal = proof_tlv_map.meta_reveal is not None
        has_meta_hash = proof_tlv_map.asset.meta_hash is not None
        is_genesis_asset = is_genesis_asset(proof_tlv_map.asset)
        match:
            case has_meta_reveal && !is_genesis_asset:
                return false

            case has_meta_reveal && is_genesis_asset:
                meta_hash := sha256(meta_reveal)
                if meta_hash != proof_tlv_map.asset.meta_hash:
                    return false

            case has_meta_hash && is_genesis_asset && !has_meta_reveal:
                return false

            case !has_meta_reveal && is_genesis_asset:
                return false

    return true
Ownership proof

An optional ownership proof can be added to a proof through the challenge_witness field. That witness must be a valid asset tx_witness over a well-defined asset state transition that spends the full amount of the asset to the NUMS key. The state transition can be created with the following steps:

  1. Create a deep copy of the asset to prove ownership of.
  2. Truncate the prev_witnesses list to just a single element.
  3. Set the prev_witnesses[0].prev_id.out_point to the empty outpoint (all zero hash and zero index).
  4. Set the prev_witnesses[0].prev_id.script_key to the asset's script key.
  5. Set the asset's script_key to the NUMS key.
  6. Create a signature for the asset state transition, using the interactive flow (no split tomb stone).
  7. Extract just the prev_witnesses[0].tx_witness from the signed state transition and append that to the proof as the challenge_witness.

Test Vectors

Test vectors for the File Serialization can be found here:

Some of the test vectors are automatically generated by unit tests in the Taproot Assets GitHub repository.

Backwards Compatibility

Reference Implementation

github.com/lightninglabs/taproot-assets/tree/main/proof