This is another possible attempt to prevent replay attacks. It is a solution on the ‘wallet’ level with a bit different properties than the previous ideas. Big thanks to @tromp for simplifying the idea.
PayJoins for Replay Protection
This describes a simplified version (thanks to John Tromp) of a previous attempt to protect against replay attack described here ProtegoTX. As can be seen in the previous attempts, it turns out a user can create transactions that are irreplayable regardless whether they are on the sending or receiving side. The end result is a transaction that could only be replayed if all the parties interacted. It can thus be interpreted that it has a unique kernel unless all parties interact to recreate it.
Assumption: An attacker can only perform a replay attack if they can recreate the inputs of the transaction (they have all the tx information). Note that an input
P could also be ‘recreated’ as more inputs e.g.
P1, P2 where
P1.r + P2.r = P.r.
Every output is created by a transaction. This output can either be:
- recreated by its owner
- recreated through a transaction replay attack
Transaction replay attacks is a family of attacks that has been discovered by a community member Kurt and have been a hot topic lately in the Grin community.
For simplicity, assume we have a single ‘protected’ output that can’t be recreated through a transaction replay. Let’s call this output
anchor (we will later show how such an output can be created).
Let’s assume a transaction
O1 outputs were created which we own was sealed in a block.
O1 is just a regular output.
The idea is to keep building a transaction graph starting from the same transaction on which
anchor output was included and keep contributing at least one input in every transaction we participate in. If we keep keep adding inputs for every transaction we make it so that every transaction has a history back to
T which created
anchor, then all these transactions can’t be replayed by anyone.
If the above bold statement is unclear for now, don’t worry, it will be explained in details below.
Problem: The sender can recreate all the inputs in the transaction
The only way Bob can protect himself is if he contributes an input as well. If Bob contributes a single input, this makes it a PayJoin transaction. While PayJoin transactions might look like they are protected from replay attacks, they are really not. If Alice manages to recreate the output that Bob used as an Input, she could replay the transaction. Here comes the
anchor trick in play. What does it mean to recreate Bob’s output? Let’s say Bob’s output is
O1 that we created along with
anchor output. It is impossible to replay a transaction that created
anchor output exists on the blockchain. This means that an attacker can’t replay the transaction
T and thus can’t create
Problem: The receiver could recreate all the inputs in the transaction
Alice already contributed her input from which she is sending money to Bob. Let’s now image this input is
O1. If Bob wanted to make a replay attack on this transaction he would first need to recreate
O1 and would hit the same brick as in the “receiver protection” example because they can’t recreate
T because Alice’s
anchor output exists on the blockchain.
A PayJoin transaction looks symmetrical and as such doesn’t leak the information about its direction.
An example of PayJoin transaction:
inputs = [ Alice_O1, Bob_O1 ] outputs = [ Alice_output, Bob_output ]
If we imagine that Alice_O1 is her
O1 output and Bob_input is Bob’s
O1 output, then it means that neither Alice nor Bob can replay such a transaction because Alice can’t recreate
Bob_input as explained in the Receiver protection section and similarly, Bob can’t replay because he can’t recreate
Alice_input as explained in the Sender protection section. This transaction is protected by replay attacks from the participants of the transaction. It’s easy to show that any outsider would
also not be able to replay the transaction because they would hit the same
anchor outputs that would not be possible to recreate through replay attack.
Nested PayJoin transactions
But what if we don’t use
O1 outputs? Turns out as long as we are tied to an anchor and we contribute an input in every transaction we seem to be safe. Imagine we are Bob and we have a transaction
T which creates Bob’s
anchor. We then make a PayJoin transaction
T2 as described above. This means we now have
Bob_output available as an output. We then create another PayJoin transaction
T3 to which adds
Bob_output as an input. In order for anyone to replay this transaction, they would need to recreate
Bob_output which means they would need to replay
T2. But to replay
T2 they would need to recreate
Bob_O1 which we have shown is impossible.
As long as we continue the transaction graph from
anchor and contribute an input, our transaction are safe from replays by other parties. A PayJoin makes it safe from any party.
Non PayJoin transaction
Someone might not want to use PayJoin transaction and in some cases it could make sense not to use them e.g. if they are afraid that this transaction scheme would leak too much information (it’s still unclear how much it leaks really).
Any transaction can be protected from replay attacks. Protection is very simple, one just needs to add a
anchor output to the transaction outputs. For example if we have a regular MW transaction:
inputs = [Alice_input] outputs = [ Alice_output, Bob_output ]
we can see that Alice is already protected from a replay attack if she follows the rules of transaction building we defined above. If Bob also wanted to protect himself from a replay, he could simply add a
Bob_anchor to the outputs which would make the transaction look like:
inputs = [Alice_input] outputs = [ Alice_output, Bob_output, Bob_anchor ]
How does one create an ‘anchor’ output?
At the beginning we said we will later show how an
anchor output can be created.
It’s the same as in the previous version:
Quoting John Tromp from a comment below:
You can create a protected output just by doing S00 -> S01,NS, where NS is an output you never spend. Since we don’t allow duplicate outputs, this can never be replayed.
We first need to know that Grin does not allow duplicate outputs. This means that if an output exists on the blockchain, it’s invalid for a transaction to create a new output which is the same. If we create an output that we never intend to spend, this is good enough and we can call this output
- But doesn’t this leak privacy?
This approach leverages PayJoin transaction all the way - PayJoin on steroids. It leaks as much as a PayJoin does, but we need to also know that PayJoin transaction adds some other privacy properties that are not found in regular MW transactions. Everyone doing a PayJoin transaction might also have synergistic privacy/obfuscation properties. It’s not yet clear exactly what the tradeoffs are.
- Does it come with a cost to the user?
No, user keeps creating transactions as before. I believe a PayJoin transaction is even cheaper right now because it contributes one more input compared to a regular MW transaction.
- What are the UX concerns here?
If ‘anchor’ outputs are generated from a special key derivation path (kudos to antioch for the idea), then they could be identified by the wallet in the background and perhaps the user would not even need to know that they exist. A wallet could perhaps do the initial
anchor bootstrap in the background without the user knowing.
- How do you handle wallet restore or having seed on multiple devices in this case?
I think it “just works”. If you were creating PayJoin transaction that were tied to an
anchor output, then you can be sure nobody can replay them so the outputs you get from a fresh restore should in theory be safe (unless I missed something).
- What about ‘play’ attacks?
This solves (I hope) only replay attacks. Play attacks might be prevented with other mitigations e.g. specific input selection mechanism.
- What about transactions that have already happened?
I’m not sure there’s anything that can be done about past transactions since if you restore a wallet today, you don’t really know which transactions you made in the past.
- Anything else?
anchor output could also be used as an identity if it had a form
0*H + r*G where the owner could provide a signature with generator
John Tromp observed that you can represent the secp256k1 wallet pubkey in a mere 32 bits by referencing TXO MMR leaf index!