motorina0/stateful_taptree.md

## stateful_taptree.md

      
    Raw
  

              stateful_taptree.md
            
          
    Yet Another Shared UTXO Model

Prerequisites: basic understanding of BIP341.
The idea is similar with the TAPLEAF_UPDATE_VERIFY described by Anthony Towns on the Bitcoin-Dev Mailing List. However, this approach uses the concept of Stateful Tap-Tree in order to exclude certain tap-tree paths from being spent.
Overview


the tap-tree represents the funds of multiple participants (shared UTXO).
each tap-leaf in the tap-tree has its own "owner". One entity can "own" multiple tap-leafs.
before entering the "shared-utxo", each participant must check that the tap-tree is correctly constructed

each tap-leaf can be spent only once
the total amount the tap-leafs can spend is equal to the UTXO amount


when a tap-leaf is spent (exits the shared UTXO):

the funds for the rest of the participants are sent to an output on the same position (same output)
this tap-leaf is blocked from being spent (on the newly created same output)
the funds corresponding to the spent tap-leaf can be distributed to any number of outputs (and for paying fees)


Tap-Tree

Below there is a tap-tree identical with the one in BIP341:

Figure1: tap-tree
There are 5 possible spending conditions (A, B, C, D and E). Only one of them can be taken under the existing spending conditions.
Note 1: each tap-leaf has an index next to it ([0], [1] ... [5]). This index can easily be computed based on the path taken from the root to the leaf (0 - for left, 1 - for right). Eg: for getting to C, the 100 binary value is computed (which in base 10 is 4). Since each path is unique, no collisions exist.
Note 2: the index value can also be computed from the script-path spend provided in the control-block (the tap-tree is not required).
Stateful Tap-Tree

The proposed change is to take the existing tap-tree and transform it into an internal tap-tree by adding a sibling to the current tap-tree root level and deriving a new tap-tree root:

Figure2: stateful tap-tree
This new top-level node (orange square) is not a scrip-path spend. The hash value for it is not computed from a tap-leaf, but instead it is initialized with zeros. Each bit in this 256 bit array represents the state of the tap-leaf at that respective index (1 - spent, 0 - not spent).
Note: it is not required for the internal tap-tree structure to be altered in any way.
Spending a Stateful Tap-tree Leaf

Broadly speaking this is what needs to happen when spending:

check that the tap-leaf has not been spent already (is spent if a value of 1 is present on the corresponding index of the tap-tree state)
set the tap-leaf index to 1 in the tap-tree state
check the transaction output corresponding to this transaction input. The same output MUST:

exist. This is the output where the rest of the payments in the "shared-utxo" will be sent
have the right amount
commit to the same internal public key
commit to a tap-tree that has:

on one branch the root of the internal tap-tree
on the other brach the updated state (the current tap-leaf is marked as spent)


Code Changes

These are some hypothetical code changes that would introduce two new op codes.
IN_OUT_AMOUNT


originally defined here
pushes two items onto the stack: the amount from this input's utxo, and the amount in the corresponding output

The spender must create an output that has the correct amount.
Correct Amount = UTXO Amount - <leaf_amount>
Script:
IN_OUT_AMOUNT OP_SUB <leaf_amount> OP_NUMEQUALVERIFY
TAPLEAF_PATH_VERIFY

Checks that:

the tap-leaf has not already been spent
the scriptPubKey for same output is correctly constructed

The data required to perform these checks can be extracted entirely from the transaction data. No extra context is required.
The performed computations are:  hash_TapLeaf(), hash_TapBranch,  hash_TapTweak

Tap-Leaf Not Spent Check

Thanks to the way Merkle trees are constructed, the state tap-leaf will always be included in the path for any tap-leaf spend (inside the internal tap-tree).
For example if we have this tap-tree (the left/right notation is used for ease of reading) and the spent tap-leaf has the hash bc08b6c2da24d79c450f93a0ca39ce8f679cf07931852b66bb1954c08ac366e4, then the path is:
[
  '98ab18a0b7d6bb18eacca2e8741ce766855babe2812fc028f2f9a63d0e2fb37d',
  'c57fbfbf32b37d74bf18744ed7f4d954cb5ad813c9b94d82334d1afcdb375c8a',
  '60b742023822f442e7deb6925bd7e90c0241213758b9b2805b776fda57f28714',
  '2b3bbc598ae051d6fb5981b8b3673e071965a481329156b6561508c5171f4466',
  '0000000000000000000000000000000000000000000000000000000000000000'
]

And the control block value is:
c1ff6d1b15c70cdd215917b252298df0115990cf77e05bd4f4344c798ecd5a2fbd98ab18a0b7d6bb18eacca2e8741ce766855babe2812fc028f2f9a63d0e2fb37dc57fbfbf32b37d74bf18744ed7f4d954cb5ad813c9b94d82334d1afcdb375c8a60b742023822f442e7deb6925bd7e90c0241213758b9b2805b776fda57f287142b3bbc598ae051d6fb5981b8b3673e071965a481329156b6561508c5171f44660000000000000000000000000000000000000000000000000000000000000000

Since the tap-tree leafs and branches are sorted by their hash, computing the index of the tap-leaf is straightforward. In this case the index of the tap-leaf is 25, computed from less than / grater than values ([ 1, 1, 0, 0, 1 ])
Now that both the index of the tap-leaf and the state have been fetched, it can be checked if the tap-leaf has been spent (by cheking the value at index in state).

scriptPubKey Check

Check that the corresponding output is locked by a script that:

blocks ALL previous spent tap-leafs (including the current one)
allows ALL unspent tap-leafs to be spent

The following data can be extracted or derived from the witness stack:

path: extract from control block
internalPubKey: extract from control block
tapLeafHash: derive from the tap-leaf script. Second from the end on the witness stack
index: the tap-leaf index, computed based ontapLeafHash and path
state: the last element of path
internalTapTreeHash: the hash of the internal tap-tree, computed from  tapLeafHash and path (excluding the last element which is the state)

The following data can be computed:

newState: derived from the existing state, but with the bit at index flipped to 1
newTapTreeHash:  hash_TapBranch(newState, internalTapTreeHash)
newPublicKey: internalPubKey tweaked with newTapTreeHash (x-only)

The following checks must be performed against the scriptPubKey of the same output:

the witness version is OP_1
the data equals newPublicKey

Advantages


the participants only have to sign when entering and exiting the "shared utxo"
only the tap-leaf and the path to the tap-leaf need to be saved in order to spend later (not the full tap-tree)
only use the existing tweaking logic, no new constructs

Extensions

Increase State Size

the above example has only one tap-leaf for holding the state. This means that there is a limited number of tap-leafs (256 or less) for the internalTapTree
however, more state tap-leafs can be added. The first state tap-leaf can reserve the last byte for the count of total state tap-leafs
the cost is a witness size increase of 32 bytes for each extra state


Group Exit

normally only one tap-leaf can exit at a time. However, there is the case where all participants in a sub-tree agree to exit
in the below image, C and D can exit individually, or if C and D agree they can exit via E
this change requires for TAPLEAF_PATH_VERIFY to take an input:

OP_0 - normal behaviour
OP_1 - instead of flipping the flag for the tap-leaf position, flip the flag to 1 for the parent position


the amount and path checking logic would significantly change (not detailed here)


Limitations


no random group exit
easy to trace from creation to last spend (internalPubKey always shown)

Attack Vectors

255 + 1

If one entity controls 255of the tap-leafs, and 1 tap-leaf is honest, then the attacker can spend the tap-leafs in such an order that the state tap-leaf becomes a valid hash for some tap-script. If half (or some other %) of the state is initialised with 1, then this attack would become infeasible. But also the valid state size would have to be reduced.
Non-RBF transaction

If one of the participants decides to exit with a low fee, non-RBF transaction, then the other participants would have to wait for that transaction to get mined or they would have to do CPFP.
Other


the last tap-leaf is a special case, no restrictions should be set on it

last tap-leaf = all paths are spent except one