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.
An overview of pros and cons can be found here
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 T where anchor and 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 O1 because anchor output exists on the blockchain. This means that an
attacker can't replay the transaction T and thus can't create O1.
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.
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.
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
]
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 anchor.
- 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, the 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?
An 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 G.
John Tromp observed that you can represent the secp256k1 wallet pubkey in a mere 32 bits by referencing TXO MMR leaf index!