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.
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
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
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:
- the sum of kernels at block B
we can compute the sum based on the
- the total kernel offset at block B
blocks have a header
- the total UTXO set sum
we don’t have this available so lets imagine a block header commits to the
we can compute if this triplet was a part of the block. We can do this by construction a partial FlowJoin transaction
-> R2 O2 -> O3 kernel = 0*G offset = (O3.r + R2.r) - O2.r
which consists only of our outputs. Now, if we subtract transaction
B which would mean we subtract the
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
So if we do a wallet restore, we can:
- compute the flow chain to some distant
nand for each edge know which blinding factors we used in that transaction
- scan our outputs and find out based on their
rvalues in which edge (transaction) the outputs were used
- 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.