PayJoins for Replay Protection

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.

‘Never-spend’ outputs

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:

  1. recreated by its owner
  2. 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.

Receiver protection

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.

Sender protection

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.

PayJoin transaction

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

FAQ

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

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

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

  1. 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).

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

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

  1. 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!

7 Likes

In summary:

You’re protected from replay attacks if you only do PayJoins, or txs with a (zero-valued) output of yours that you never spend.

The latter would be necessary to fund a wallet.

Once your wallet has n regular outputs plus a never-spent “anchor”,
all your sending and receiving of payments is done with PayJoin txs that consume one of your regular outputs and produce another. n would be chosen according to how many txs you may have awaiting finalization and confirmation. A few dozen would suffice for most users.

In some sending cases, you may need to use multiple inputs to provide enough value, and would then also have that many outputs.

2 Likes

Great! at least this solution seems secure unlike other wallet solutions. Well done.

You need to do a uniqueness check on all the UTXOs to preserve the protection of replay, is it correct? So it is a combination of wallet solution and consensus solution. it is also a uniqueness check, but on Utxos, rather than kernels. And you have no way I think to make it scalable.

A bit worrying for light nodes in the future because of that. the scalability blow is non negligible. The worry is in live transaction verification where you would need to do a uniqueness check against all utxo history for each new utxos that comes to you… And there are more new utxos than new kernels and of course you cannot keep a small list of them unlike in kernel uniqueness.

Also, waste of outputs (around one per wallet) which is 700 bytes of data. wastes that also accumulate for the uniqueness check.

But the Ux seems non-affected, which is good too.
So at least, if the counsil likes this solution, we are good to go for a proper ux and security solution, which is good for grin.

edit: read quickly the above, I think uniqueness check may only be needed on the unspendable utxos, which is an ever-growing list, but at least can probably made detectable by having a schnorr sig on them and not a bp (0 value).

edit2: this solution leaves the outputs on the chain pre-implementation of this solution at risk of replays. unlike kernel uniqueness.

2 Likes

Yes, the rule that needs to exist is not to allow duplicate outputs which already exists. If we decide to go towards allowing duplicate outputs, then we would need to find a new way to bootstrap initial condition.

I think the recommendation would be 1 anchor output per wallet. If we decide in the end we want to force kernel uniqueness at consensus level, they could be spent afterwards. If they actually end up being used in a way to provide an identity or something else (how we could use them is still not researched) they might not be a waste. This is unclear and right now though and you’re right, they are a waste as of now.

Yes, only on UTXOs. Correct, these could be optimized to be much smaller as they don’t really need a range proof. This will likely depend on the complexity involved behind the scene and possible privacy tradeoffs.

Indeed! This solution can protect all the future transactions, but not the past ones! The actual kernel uniqueness check would be more powerful here. This is also in the FAQ #6 question.

Thanks for reading it Kurt and for the feedback! I think your description of it is very precise and aligned with my current understanding. I’m sure this could be improved further in some way or we might find new ways to leverage/extend the idea.

Btw, do you agree that a transaction is protected by a kernel uniqueness unless all the parties participate to build a new kernel/replay it? The claim that I make at the beginning:

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.

I think this is true, but would like others to verify it.

2 Likes

At first sight, I do think so yes. Will try to think in more details

2 Likes

I really like this proposal. Only challange I can think is how to know the payjoin actually involves different parties? I mean if you join a PayJoin of 10 people and 9 are actually the same guy, he can replay your transaction. Also, I do not understand why you need to have different input values. A normal CoinJoin for Bitcoin is obvious to detect because all inputs and outputs are the same value but I thought the transfer amounts were not possible to detect for Grin transactions unless you were involved in the transfer. Anyhow, just wondering why, not that it hurts to use a CoinJoin on steroids, sounds great to me :wink:

No, they cannot, because your input cannot be recreated.

3 Likes

The security of this relies entirely on the assumption that the “anchor” output is never spent, accidentally or otherwise.
Would one way of achieving this be the use of an “ephemeral” private key. i.e. not from a deterministic derivation path on a wallet, but simply having the wallet generate a random private key, discarding it once the anchor output, rangeproof and transaction kernel had been built?

This would presumably complicate wallet restore given there would be literally no way to identify this anchor output?

Edit: Alternatively a 2-2 multi-party output would also be hard to accidentally spend?

1 Like

A nice property of this scheme is that the transaction is protected if either party contributes a protected input. It does not require cooperation of both parties.

I’ve already previously expressed serious concerns with the privacy implications of PayJoins. I similarly have serious concerns about linking all of my transactions back to a single anchor output. Assuming all wallets have a single anchor, and you know an individual’s anchor output, it’s possible to conclude decisively that they are not involved in many transactions. In fact, I suspect it leaks way more information than even bitcoin does, since it weakly links all of a user’s transactions together, though further study is obviously required.

2 Likes

Sort of. A participant in a transaction is protected if at least one of the two is true:

  1. They contributed an input (assuming following the scheme)
  2. Added an anchor output to the transaction

So if one participant adds an input it is not that the whole transaction is safe, that participant is safe. For schemes with multiple parties involved I think it’s enough to have 2 contribute an input (if they dont collude). But it’s best to contribute an input and be safe.

Sorry yes - I was talking in the context of (1).
If either party follows the scheme and contributes a protected input then the whole transaction is protected from replay, right? As its all-or-nothing.

Alice and Bob are transacting. Alice can protect the transaction by following the scheme, regardless of what Bob does.

As I said in my summary:
You are protected from replay attacks if you only do PayJoins, or txs with a (zero-valued) output of yours that you never spend.

Substitute Alice for you:-)

2 Likes

I think this is correct but one would need to know which are anchor outputs. A user could protect himself by creating an anchor output in a self-spend PayJoin. I agree that further study is required. While it does seem that privacy could get hurt, my intuition tells me that PayJoin should be beneficial if done right and by many parties. I guess this could be debated again and further researched in the PayJoin thread.

I have a hunch that all one kind of tx will always be bad. Same goes with majority or predicability of one kind of transaction.

Easy: Look for outputs that never move.

1 Like

Interesting, my hunch is that PayJoin might be more interesting than it looks at first. PayJoin transactions are still a bit of a mistery to me. If both parties contribute an input, then we know that 1 out of 2 is the sender. At the same time I question whether this is the same as everyone is a sender and everyone is a receiver if you want to do analysis (everyone here is both the sender and receiver). If this interpretation is needed for analysis over PayJoin transactions on the input side then I think it becomes exponential with the number of transactions if you have no data from the real world, just transactions from the mempool.

The sender could provide an exact amount input and have no output, right?

In theory you could do that yes, but I would not be recommend IMO. This makes you lose one output and outputs (when used as inputs) are your protections against transaction replays in the scheme above. You could create new anchor out of nothing if needed, but it’s likely beneficial for everyone to not do that unless needed.

Yeah, it wouldnt be recommended in the case of replay prevention. But I think we need careful consideration and analyses of having all txs linked to an anchor and all txs structured the same way. Both of these scenarios, especially combined, have the possibility of being very harmful to privacy.

1 Like