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

Research
1

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.

2

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.