Skip to content

Latest commit

 

History

History
292 lines (226 loc) · 14 KB

bip-tap-vm.mediawiki

File metadata and controls

292 lines (226 loc) · 14 KB
Raw

 BIP: ???
  Layer: Applications
  Title: Taproot Asset Script v1
  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 describes the virtual machine execution environment used to validate Taproot Asset transfers that utilize an asset_script_version of 1. The execution environment described in this document is a slight twist on the taproot validation rules defined in BIPs 341 and 342. Given a Taproot Asset one or more Taproot Asset leaves to be spent (inputs) and asset leaves to be created, a "virtual" taproot Bitcoin transaction is created. This transaction is a 1-input-1-output transaction that commits to the inputs and output set using a merkle sum tree. With this mapping complete, validation takes place as normal.

Copyright

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

Motivation

The Taproot Asset overlay permits the usage of a nearly arbitrary virtual machine for validation of transfers within the system. In order to reduce the scope of the initial version of the protocol, we describe a way to leverage the existing Bitcoin Script virtual machine, allowing us to inherit a baseline set of expressibility, while allowing implementers re-use existing tools and libraries.

Design

The Taproot Asset asset_script_version 1 maps a Taproot Asset input and output set to a "virtual" Bitcoin transaction. The input and output sets are committed to within a single 1-input-1-output transaction using a normal merkle sum tree (TODO(roasbeef): non-inclusion useful at all here??). Via the merkle-sum invariant of the augmented merkle tree, a validator is able to enforce non-inflation of assets by asserting that the committed input sum is equal to the committed output sum. Once this invariant is verified, execution resumes as normal using the BIP 341+342 validation rules, with additional pre-execution checks that may fail validation early.

Specification

A single 1-input-1-output transaction is used to compress the Taproot Asset state transition state into a constant size transaction. Given a Taproot Asset commitment (which lives in a taproot output), and its valid opening, the set the previous asset ID are compressed into a single input, and the present split_commitment is used to compress the output state.

State transition validation may take one or multiple asset leaves within a single transaction (with the leaves living in different outputs). When a single leaf is present, no splits occurred in the state transition, or the asset is a collectible. When two or more leaves are specified, then all but one of the leaves were splits resulting from a split event at the Taproot Asset layer. In this case, the split commitment proof, as well as the validity of the state transition creating the splits are validated.

Mapping Inputs

Input mapping is only executed for state transitions that specify prev_asset_witnesses.

Given a set of inputs, each identified by a prev_asset_input, the input commitment (which is used as the previous output) is constructed as follows:

  1. Initialize a new empty MS-SMT tree as specified in bip-tap-ms-smt.
  2. For each Taproot Asset input c_i, identified in the prev_asset_witnesses field:
    1. If the asset input has a split_commitment in the witness, that needs to be removed before the serialization step.
    2. Serialize the referenced previous asset leaf (identified by prev_outpoint || prev_asset_id || prev_asset_script_key) in TLV format.
      1. For a minting transaction, a copy of the output leaf with emptied prev_asset_witnesses is used, in addition to these modifications:
        1. If the minted asset has a group key, the asset_script_key of the copied leaf should be set equal to the group key. This enforces that the state transition verification uses the group key when validating the spend.
        2. If the asset has no group key, the asset_script_key field should be blank. This will short-circuit the state transition verification, allowing minting an asset that does not support emission.
      2. This is to ensure we can get a complete virtual tx mapping also for minting transactions.
    3. Insert this leaf into the MS-SMT tree, with a key of the prev_id_identifier, a value of the serialized leaf, and sum value of the asset amount contained in the leaf.
  3. Obtain the root hash input_root and sum value input_asset_sum resulting from the tree creation and root digest computation.
  4. Let the hash of the serialized 36-byte MS-SMT root be the sole previous outpoint (the txid) of the virtual execution transaction.
With the above routine, we map the input set into a MS-SMT tree, which also commits to the total amount being spent of any given asset. During verification, as there may be multiple input witnesses, during validation, the asset_witness for each input is used as the initial witness stack.

Notice that we don't map the relative_lock_time field here within this unified input commitment. Instead we'll map this during the verification/signing process, which enables the existence of per-input relative and absolute lock time.

The following algorithm implements the input mapping required for full state transition verification: 

make_virtual_input(prev_inputs: map[PrevOut]TaprootAssetLeaf) -> (MerkleSumRoot, TxIn):
    input_smt = new_ms_smt()

    for prev_out, taproot_asset_leaf in prev_inputs:
        leaf_bytes = taproot_asset_leaf.serialize_tlv()

        input_smt.insert(key=prev_out, value=leaf_bytes, sum_value=taproot_asset_leaf.amt)

    input_root = input_smt.root()

    virtual_txid = sha256(input_root.hash || input_root.sum_value)

    # We only only bind the virtual txid here. Below we'll modify the input
    # index based on the ordering of this SMT.
    return input_root, NewTxIn(NewOutPoint(txid=virtual_txid), nil)

Mapping Outputs

Output mapping is only executed for state transitions that specify prev_asset_witnesses.

Given a Taproot Asset output, and any associated outputs contained within its split_commitment_root, the output commitment is constructed as follows:

  1. For normal asset transfers:
    1. Let the output value be the sum of all the amt fields on the top level as well as the split commitment cohort set, in other words the last 4-bytes of the split_commitment_root.
    2. Let the output script be the first 32-bytes of the split_commitment_root value converted to a segwit v1 witness program (taproot).
  2. For collectible asset transfers
    1. Let the output value be exactly 1 (as each TLV leaf related to a collectible can only ever transfer that same collectible to another leaf).
    2. Let the output script be the first 32-bytes of an MS-SMT tree with a single element of the serialized TLV leaf of the collectible.
      1. The key for this single value is sha256(asset_group_key || asset_id || asset_script_key). If a asset_group_key field isn't specified, then 32-bytes of zeroes should be used in place.
The following algorithm implements the output mapping required for full state transition verification: 

make_virtual_txout(leaf: TaprootAssetLeaf) -> (MerkleSumRoot, TxOut):
    match leaf.asset_type:
        case Normal:
            tx_out = NewTxOut(
                pk_script=[OP_1 OP_DATA_32 leaf.split_commitment_root.hash], 
                value=leaf.split_commitment_root.sum_value,
            )

            return leaf.split_commitment_root, tx_out

        case Collectible:
            output_smt = new_ms_smt()
            output_smt.insert(
                key=sha256(leaf.asset_group_key || leaf.asset_id || leaf.asset_script_key)
                value=leaf.serialize_tlv(),
                sum_value=1,
            )

            witness_program = output_smt.root_hash()

            tx_out = NewTxOut(
                pk_script=[OP_1 OP_DATA_32 witness_program], 
                value=1,
            )

            return output_smt.root, tx_out

Validating a State Transition

If a state transition specifies a prev_asset_witnesses field, then once the set of inputs and outputs have been mapped to our virtual Bitcoin transaction (creating a v2 Bitcoin transaction with a single input and output), validation proceeds as normal according to BIP 341+342 with the following modifications:

  1. If the input_asset_sum is not exactly equal to the output_asset_sum validation MUST fail.
  2. For each prev_input within the set of referenced prev_asset_witnesses:
    1. If the asset_type of the referenced input leaf doesn't map the asset_type of the Taproot Asset leaf spending the input, validation MUST fail.
    2. Construct a single-input-single-output Bitcoin transaction based on the input and output mapping above.
      1. The prev out input index should be the lexicographical index of the prev_id_identifier field for each input.
      2. The previous public key script should be the asset_script_key for the current previous input, mapped to a v1 segwit witness program (taproot).
      3. The input value for each included input is to be the amt field of the previous Taproot Asset output being spent.
      4. Set the sequence number to the relative_lock_time field of the input, if it exists.
    3. Set the lock time of the transaction as the lock_time of the input TLV leaf being validated, if it exists.
    4. All signatures included in the witness MUST be exactly 64-bytes in length, which triggers SIGHASH_DEFAULT evaluation.
    5. If the asset_script_key is blank, then the asset_group_key MUST be blank, and ALL witnesses MUST be blank. In this case, verification succeeds as this is only a creation/minting transaction for an asset without emission.
    6. If the asset_id value is NOT the same for each Taproot Asset input and output, validation MUST fail.
      1. Alternatively, assert that each input and output references the same asset_group_key field.
    7. Perform external lock time and relative lock time validation:
      1. If a relative_lock_time field exists, if the input age of the referenced TLV leaf is less than relative_lock_time validation MUST fail.
      2. If a lock_time field exists, if the block height of the block that includes the transaction is less than lock_time validation MUST fail.
    8. Validate the transaction according to the BIP 341+342 rules.
We explicitly implement lock time semantics at this level, as the sequence and lock time fields in the context of Bitcoin itself are validated from the PoV of connecting a new block to the end of the main chain.

Otherwise, if a state transition only specifies a split_commitment_proof, then:

  1. If the Taproot Asset output to be validated only specifies a split_commitment_proof and no explicit inputs, then a valid inclusion proof for the output MUST be presented and valid.
    1. If the proof is invalid, then validation MUST fail.
  2. Given the "parent" split, execute the input+output mapping and verify the state transition using the logic above.
The following algorithm implements verification for top level Taproot Asset leaves, as well leaves created via split commitments: 

verify_taproot_asset_state_transition(leaf: TaprootAssetLeaf, leaf_split: TaprootAssetLeaf) -> bool
    if is_valid_issuance_txn_no_group_key(leaf):
        return true

    if leaf_split is not None:
        if leaf is None:
            return false

        if !verify_split_commitment(leaf.split_commitment_root, 
            leaf_split.split_commitment_proof):

            return false

    input_smt, tx_in = make_virtual_input(leaf.prev_inputs)
    output_smt, tx_out =  make_virtual_txout(leaf)

    if input_smt.sum_value != output_smt.sum_value:
        return false

    virtual_tx_template = NewTx([tx_in], [tx_out])
    for input in range leaf.prev_inputs:
       if input.asset_type != leaf.asset_type:
           return false
       
       match input.asset_id:
          case AssetID:
              if input.asset_id != leaf.asset_id:
                  return false
          case GroupKey:
              if input.asset_group_key != leaf.asset_group_key:
                  return false

       virtual_tx = virtual_tx_template.clone()

       if !parse_valid_schnorr_sigs(input.asset_witness):
           return false

       virtual_tx.tx_in[0].witness = input.asset_witness
       virtual_tx.tx_in[0].prev_out.index = input_smt.leaf_index_of(input)

       prev_pk_script = OP_1 OP_DATA_32 input.asset_script_key
       input_value = input.amt

       if input.relative_lock_time != 0:
           virtual_tx.tx_in[0].sequence = relative_lock_time

           input_age = conf_input_age(input)
           if num_confs(input) < input_age:
               return false

       if input.lock_time != 0:
           virtual_tx.lock_time = leaf.lock_time

           block_height = env.block_height()
           if block_height < virtual_tx.lock_time:
               return false

       vm = new_script_vm(
           prev_pk_script=prev_pk_script, tx=virtual_tx, input_index=0, 
           input_amt=input_value,
       )

       if !vm.Execute():
           return false

    return true

Test Vectors

Test vectors for Validating a State Transition can be found here:

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/vm