 # Proving a 'subset of transaction' was inserted in some specific block (and output is connected to an anchor)

Edit: I’ve tried to capture the whole idea here https://gist.github.com/phyro/ef42ce95cfbad05964f8be2f5d8f9466

Say we have a transaction `T` and we want to prove it was added in block `B`. We can do that by either:

1. Checking the `utxo_mmr_root` of the block `B` and then have a merkle proof for inclusion of the outputs of `T`. (Edit: I’ve been corrected that this does not prove inclusion of `T`)
2. Checking the position of the transaction kernel and computing from `kernel_mmr_size` in to get the block in which it was added (a bit weaker because it does not commit to utxos)

There’s another simple way to prove it which is basically the standard “global excess validation” where you subtract the transaction and check that the block is still valid (it should be if outputs were `0*H` and if they were not, you can adjust them by adding `v*H + 0*G` outputs and check it then).

Let’s assume we take part in a PayJoin transaction that adds one input and one output to it `I1->O1` but we don’t know the rest of the transaction. If `O1` was generated from `I1` AND both had a form `0*H + r*G` we could, given `O1`, compute also `I1` which means that we would know `O1.r - I1.r`. This means that if this ‘subset transaction’ was included in a block `B`, then if we have:

1. the sum of kernels at block `B`
we can compute the sum based on the `kernel_mmr_size`)
2. the total kernel offset
blocks have a header `total_kernel_offset`
3. the total UTXO set sum
we don’t have this, but imagine a block header commits to the `total_utxo_set`

We could check if `I1->O1` was a part of block `B` by adjusting the total_kernel_offset and the total_utxo_set at that block. If it can be validated as “a valid chain” after the change, then we know that the difference of these blinding factors was a part of the transaction (I think).

This could seem useless because why would you keep the subset of a transaction instead of keeping it all, but you might not need to keep even the subset if `O1` is derived from `I1`. Suppose you have a chain of PayJoin txs to which you added pairs `Ox->Oy`:

``````X -> A, O1  # + O1.r
O1 -> O2    # - O1.r + O2.r
O2 -> O3    # - O2.r + O3.r
O3 -> O4    # - O3.r + O4.r
O4 -> O5    # - O4.r + O5.r
``````

If we restore a wallet and see `O5`, then we can compute `O4` which means that we know `O5.r - O4.r` and can thus check every block from head towards genesis which block would be valid if this ‘subset transaction’ would be removed. Note that if it was included in a block, such a block MUST exist because the block would need to be valid without this 1-1 part as well because they had `0*H`.
Once we have found `O4` we can again figure out `O3` and then repeat the check for blocks prior to the block where `O4` was included.

This way, we can prove a subgraph (chain) from `O1->O2->O3->O4->O5` exists on the blockchain without the need to actually keep the transaction data around.

Whether this is useful or not is still not clear to me, but I thought I’d still share. I guess the outcome here is that if we had the `total_utxo_set` commitment on the header, some new options might be possible. I’m also sharing this in case someone else sees anything usefull that could come from this.

Note: A 2-2 PayJoin can be broken down into 2 transactions, 1 that is known to the sender (sender’s input and output) and 1 to receiver (receiver’s input and output), so we have a transaction a transaction we want. If input and output are generated deterministically, we can generate them and don’t really need to save them anywhere. We’ve shown above (hopefully) that only a transaction is needed to compute in which block it was added.

Above we show (unless wrong) that we can prove the chain `O1->O2->O3->O4->O5` is connected and on the blockchain.

Assume that real outputs we create (not `0*H + r*G` that we continuously connect in the chain above) are derived from difference of these two outputs that connect the chain e.g. if we have the following PayJoin:

``````
Alice_O1 -> Alice_O2
Alice    -> Bob_value
-> Alice_change
Bob_O1   -> Bob_O2
``````

Then we know we can show `Bob_O1 -> Bob_O2` transaction is on chain. If we define that `Bob_value` is derived from the `O1->O2` e.g. if `O2.r - O1.r = X` then `Bob_value.r = X*seed_value` whatever the seed value is (can be `y*anchor.r` or something).
This means that we can find out to which `O_i->O_i+1` transaction our observed output was. This also means that the following transaction should be valid in terms of `r` values:

``````       -> Bob_value
Bob_O1 -> Bob_O2
kernel = 0*G
offset = (Bob_O2.r + Bob_value.r) - Bob_O1.r
``````

We can check if a block has such “transaction” included the same way we checked for the above chain (again assuming block header has `total_utxo_set`) but after subtraction we have to add `Bob_value.v + 0*G ` to balance out the `v` parts.

This means that given a specific structure and deriviations (IF such derived & empty outputs were a part of the PayJoin) it would be possible to prove a UTXO is connected to an anchor without the need to keep any history of transactions.

Intuition behind this is:

1. to produce a deterministic chain of outputs that have a form `0*H + r*G`
2. Each edge (connection) in the chain represents a PayJoin tx where one vertex is used as input and one as output e.g. `O1->O2`
3. The actual output that holds value in the PayJoin tx `O_real` has `r` blinding factor derived from both O1 and O2 blinding factors so we can know to which `O1->O2` pair to add it and reconstruct this part of tx. Once we have a subset of tx we ca check if there exists a block that includes it.