{{ message }}

Instantly share code, notes, and snippets.

# phyro/flowjoin.md Secret

Last active Jul 21, 2020
FlowJoin anchor proofs

# Proving output attachment to anchor graph

The idea is to be able to verify that your outputs are connected to an anchor and hence safe from replays.

## Deterministic output chain

Let's a user is building a linear chain of 0 valued outputs deterministically (e.g. from some derivation path) where each output has a form 0*H + r*G. So we end up with a chain of 0-value outputs O1->O2->O3->O4->O5...->On, let's call this a flow chain.

Now let's say that each edge in this chain represents a PayJoin transaction, so the first edge in this case represents a PayJoin where O1 is used as an input and O2 output is created. Remember that they both have 0*H + r*G. Since these outputs (e.g. O2) are 0*H, we will need some other output to hold our coins. Let's define a derivation of such an output as a function

F(O1, O2) ->
(O2.r - O1.r) * secret_seed

where secret_seed could be some private key e.g. anchor.r blinding factor. This gives us the property that given a pair O1,O2 (an edge in the flow chain) we can know which r value we would give to the output Ri that would hold our coins in the transaction. It also means that if we find an output Rn in a wallet (e.g. after a wallet restore), we can, given that flow chain can be computed because it is a derived chain, compute on which edge Rn would be present.

Below is a visual representation of our flow chain with our a "coin holding output" for each edge:

O1 -> O2 -> O3 -> ... -> On
|     |             |
R1    R2            Rn

## FlowJoin - a variant of PayJoin with a specific structure

If we assume we are constructing the transaction following the flow above, we can see that a participant that is building their flow chain will contribute a 1-1 with 0*H outputs. This means that if both participants are building the flow chain we would end up with a transaction that can be thought of as 2-2 (continuation of 2 flow chains) + 1-2 (regular MW tx) = 3-4 (tx with flow continuations). So a transaction where both parties follow these rules has 3 inputs and 4 outputs. Let's named these transactions FlowJoin due to it's specific properties of having derived flow output of form 0*H and a derived Rn output.

## Checking a subset of a FlowJoin transaction was present in a block

By now, we know that we can rebuild the flow chain and the outputs that were present on the 'edge' transactions. Say we want to check if a transaction (an edge) that contained O2, O3, R2 outputs was present on the chain. Given:

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

we can compute if this triplet was a part of the block. We can do this by construction a partial FlowJoin transaction T:

-> R2
O2     -> O3
kernel = 0*G
offset = (O3.r + R2.r) - O2.r

which consists only of our outputs. Now, if we subtract transaction T from B which would mean we subtract the offset from B.total_kernel_offset and also subtract the outputs: total_utxo_set = total_utxo_set - R2 - O3 + O2 to make sure our outputs are the same as before the FlowJoin tx, we should get to a new state of outputs that was without our outputs. However, this does not give us a valid chain state because the v*H values don't match so we need to also add a fake output R2.v + 0*G to the total_utxo set total_utxo_set += R2.v + 0*G. If this produces a state of the blockchain that is valid, it should prove to us that our part of the FlowJoin transaction was in fact included in block B.

So if we do a wallet restore, we can:

1. compute the flow chain to some distant n and for each edge know which blinding factors we used in that transaction
2. scan our outputs and find out based on their r values in which edge (transaction) the outputs were used
3. do a linear scan though block headers to check if such a partial FlowJoin transactions were included in a block (a linear pass is enough because we know they must come on the chain in this order)

This idea assumed that a block header commits to the sum of the utxo set total_utxo_set. Right now, we don't have this data available.

NOTE: This likely has some flaws and potential drawbacks e.g. I've not addressed how to do concurrent txs.