{{ 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.