Skip to content

Instantly share code, notes, and snippets.


phyro/ Secret

Last active Jul 21, 2020
What would you like to do?
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment