PayJoins for Replay Protection

Development and Technical Discussion
#21

There is a sort of anmoying play attack vulnerability in payjoin.

If I am Alice and I want to send coins to Bob, Bob will contribute one of his outputs to the tx inputs. At some point Bob needs to provide his full partial offset to Alice (The opposite, Alice sending her partial offset to Bob, is not secure at all). She can stop at that point the transaction.

And she can use Bob input later and play the partial excess of Bob. The values of this play transaction will not balance out since Bob contributed less coins than what he wanted to receive (from Alice) but Alice can use any of her utxos, add it to her tx inputs, and adjust the partial offset of Bob by the blinding factor of this utxo and she can play Bob orginal tx input.

This does not allow the theft of coins but that concretely and directly put the weight on users and wallet developers by providing them a bad and not relaxing potential experience

Basically each time Alice aborts the transaction, Bob would need to spend his utxo to make sure Alice doesn’t play it using Bob’s partial excess and partial offset.

Important note:
This vulnerability does not exist in case of multi party transactions where the number of parties is equal or greater than 3. The reason is that there is in this case an easy method to exchange partial offsets without any party learns about any other party’s partial offset, making the play vulnerability discribed above impossible if no parties are colluding

#22

I’m not sure I understand exactly what you mean. Are you saying that Alice can swap her outputs?
If that’s not it and you meant something else, could you please give a concrete example so I can see it - e.g. stating what each party knows at each point and what is then abused

#23

Ah bug, everything got deleted. So if Alice sends coins to Bob through the tx1 = (I_alice, I_bob, kernel, O_alice, O_bob, offset) she can abort the tx as described above when she gains knowledge of all bob spending info, including his partial offset. By adjusting offset of tx1 she can in fact play tx1 with tx2 = (I’_alice, I_bob, kernel, O_bob, offset’) where I’_alice can be an input different from I_alice.
It is annoying for the receiver that his tx input can be played, but it can in fact be played through a different transaction, potentially creating problems with payment proofs, but more generally ux

#24

So yes, if I understand correctly this is about a participant swapping outputs they used in a transaction because they have enough information to do that. I think this can be done by any participant that sees a transaction since they know what offset they contributed and they can swap their parts by adjusting the offset accordingly. This is true even for a regular MW transaction where Alice can swap her input/output if she wanted. Similarly, Bob could in theory replace his output with a different one once he sees the transaction to obtain another valid transaction.

Can you confirm I’m understanding this right?

Regarding:

Basically each time Alice aborts the transaction, Bob would need to spend his utxo to make sure Alice doesn’t play it using Bob’s partial excess and partial offset.

It might make sense in MW to take special care of outputs a party signed for spending and did not arrive on the chain.

#25

Yea it also exists in traditional mimblewimble, the difference being that the receiver doesn’t contribute input in tx.

My biggest worry, with the privacy and scalability questions, in this proposal is the necessity to cope with censorship of transactions

1 Like
#26

Indeed he can do that if he can censor the first transaction

#27

I wouldn’t call this an attack because it is a much more general thing that is inherent to the ‘modified mimblewimble’ I think. The thing here is that a kernel in Grin signs for the difference in outputs-inputs and not specific inputs and outputs. This means that the same kernel describes infinitely many transaction possibilities with regards to inputs and outputs. I believe this is a consequence of the introduction of the kernel offset. I’m not sure such swaps would be possible if a transaction had only a kernel curve point and no offset.

Edit: Above assumption that offsets introduce this is wrong. This is possible also in the original MW paper that did not have offset.

This is a valid point. I was searching for a way to create an achor with allowing duplicate outputs at first since right now I think that any new replay attack that is introduced by allowing duplicate outputs also gains the same protection. If you find any way to start tx graph when duplicate outputs are allowed, let me know as I had no luck :confused:
And yes, we should discuss about this. What leaves me more at ease with this solution is that if this were to be implemented and later it turns out that it’s not cool to have this and we want to implement your kernel_uniqueness+duplicate_outputs, it would I think be possible and without much cost (I think).

There will always be ways to replace outputs. If nothing else, Bob could get tx info before others with an eclipse attack on the sender or similar will always be possible.

#28

Disagree. Eclipse attack are essentially impossible with a proper network and certainly don’t allow to steal any coin in a serious network like bitcoin as of today.

Censorship of tx is something that should not be accommodated with, but battled. Ask all the bitcoin OGs what they will say to you about this and what they did to fix these issues or similar (malleability) in bitcoin along the way :wink:

It is certainly antagonistic to a clean and secure design to accommodate with censorship and give more room to it.

#29

There are 2 parts to this solution, and I described a set of privacy-related problems for each in keybase. I’m repeating them here for posterity.

  1. Anchor outputs -

So here’s the difference, as I see it. Today, you can receive input A and input B from 2 different sources. You can send input A to Alice and input B to Bob in 2 different transactions. There is no link.

However, with anchor outputs, you would be required to tie both outputs back to a common anchor.

So every transaction has to be linked to every other transaction you made.

To make matters worse, you have a single output that never moves that says “Hey, I’m the start of a long chain of transactions involving a single party.”

Of course, privacy leaks exist today, but I think we have to be honest with ourselves and admit that if using anchors, there’s a very real leak of privacy that doesn’t already exist. We give chainalysis much more metadata. It seems not-too-difficult to develop an algorithm that looks for these heuristics and identifies with decent probability which transactions a user is involved with.

  1. PayJoin -

If multiple people try to send me coins, but then don’t broadcast, I have 1 of 2 choices:

  • Always use the same input until it’s spent.
    This is problematic because anyone who wants to monitor my transactions can just initiate a send to me, and then cancel and then look for the same input to show up in a transaction.
    It also makes it so there are race conditions

  • Always use different inputs.
    Then it’s trivial to see all of my outputs. Just initiate a bunch of sends

3 Likes
#30

This is a good point. A partial tx will potentially leak the input that would be used.
But is this really much different from actually completing the send, looking for the tx on-chain and identifying the input that way?
And is this materially different from a regular tx which might leak an output rather than the input? I guess the output lets you monitor future txs, whereas the input potentially gives you information about the prior tx.

#31

Yes. 2 differences with the PayJoin attack:

  1. You can learn inputs about anyone whom you know the grin1 address, whereas currently you only learn inputs if someone actually sends to you.
  2. You don’t just identify the input. You can also see how it is used in a later transaction.

Now, that latter point might seem like it’s similar to just completing the send and then watching to see how the new output is used. But the difference is if Alice just completes a bunch of small sends (dust) to Bob, he has the option to ignore/filter out those dust /untrusted coins. But in the payjoin case where Alice learns Bob’s input but then cancels the transaction, Bob won’t have the option to just not use the input that was exposed to Alice.

1 Like
#32

You can also do txs in which you provide no input (so they can be replayed), but whose output you only spend as additional input to a payjoin (which cannot be replayed). This opens up new possibilities.

4 Likes
#33

So if Bob has an existing MW transaction T

inputs = [I_Alice]
outputs = [O_Alice, O_Bob]

Bob can’t protect T from replays but he can merge its graph to Bob’s anchor graph by adding O_Bob as a third input to one of the PayJoin transactions that are protected by his anchor output?
If that’s correct, this might be an easy way to protect existing outputs that are not attached to an anchor. That’s very interesting because it means you don’t need to use all your inputs to a single output when you’re creating an anchor.

#34

Aside from the concerns on censorability of transactions (which can lead to critical vulnerabilities of ”plays” of kernels and reject security and responsibility on users doing a set of tasks, that they may fail to do, to prevent them from having their coins stolen) due to not allowing DO, and the concerns on privacy outlined by David, I also have concerns with scalability:

  1. Ever-growing list of unspendable outputs, taking 700 bytes of data each if we assign bulletproofs to them.
  2. Ever-growing list of utxos to verify the uniqueness of, which is particularly bad, as Antioch underlined several times for the case of the naive solution of checking kernel uniqueness.

The censorship ability that the solution implies seems to me antagonistic to one of the core fundamentals of blockchain (uncensorability of txs, which also turns out to provide both security and good ux), and the scalability blow seems to me in opposition of the Mimblewimble premise.

#35

I suspect we want to make ‘anchor’ outputs regular outputs because existing unmoving outputs obfuscate them. Since they don’t move, they could be thought of as easy to identify, but anchors are strictly a subset of all outputs that have not moved. Very likely that in the long run, more will be lost or unused than created as an anchor.

I might be misunderstanding what you mean, but I think this comes at no cost.

Let’s say I’m a running a node and a new block B comes. To validate it, I need to confirm that for all inputs I in B, there must exist I in the UTXO set. So I need to have a fast check that I ∈ UTXO_set. This must exist today and be fast enoguh in order for the validation to work reasonably. Now to validate one does not create a duplicate output O you need the same check but with a negation. is_duplicate = O ∈ UTXO_set which means we already have this solved because we will always need a check I ∈ UTXO_set regardless whether we allow duplicate outputs or not.

#36

for checking tx input, if x is the array of leaves of the output mmr you just need to check if x(i) is the input of the sender, where the sender told you that the index is i. For checking uniqueness the time and i guess memory needed grows bigger as array gets bigger. In kernel uniqueness the size of such array is capped at all time, (and Antioch was worried it needed all the historical kernels) which is extremely useful for scalability, especially mobile nodes in years and decades to come, especially that the cap is a small number

#37

Senders don’t specify inputs by MMR index.
They’re specified by commitment.

#38

For migration of old outputs, a future wallet could offer some anchor initializing command that

  1. creates an anchor along with some number of protected outputs
  2. marks all remaining outputs as unprotected

Of course the user could choose to spend all old outputs in 1) if they prefer, and have zero unprotected balance.

Afterwards, the wallet can use either

  • payjoins on protected outputs (possibly adding additional protected or unprotected outputs as input)
  • non-payjoins that create further anchors

It should never spend 0-valued outputs.

The wallet could show how much of its balance is unprotected (if any).

In the rare event that the wallet has to be restored while it had unprotected balance, it could mark all larger outputs as protected.

2 Likes
#39

Do I understand right that both play and replay attacks are only possible if a victim lost their transaction history (no backups or wallet restored form the seed)? If this right why not to solve it with some sort of backup servers similar with Olympus servers in Bitcoin Lightning Wallet? Something like that will be needed for payment channels anyway and better correspond to a lesser on-chain data approach.

1 Like
#40

Maybe that’s also an option. I’m not familiar with Olympus. Something that comes to mind is how do you handle child wallets? If a child makes a tx that the parent didn’t see, they can’t know which kernel was attached to it. Not sure if this is a problem or not. Does Olympus handle the situation where a seed is used on multiple devices? How does one share the history of kernels with the other one?