PayJoin (P2EP) in Grin

Development and Technical Discussion
1

Say Alice wants to send 2 Grin to Bob.
A simple transaction looks like the following. Alice spends a 5 Grin output, Bob receives 2 Grin and Alice receives 3 Grin in change.

5 Grin -> 2 Grin 
          3 Grin

Even with hidden values the structure leaks “direction” with one output presumably a “change” output.
Alice has ownership of the spent output and the new change output and further analysis may reveal this shared ownership.
If the change output is identified then the direction of flow of value is also known based on the other output.

Thinking about “payment channels” got me wondering if we could make a relatively small adjustment to the structure of the transaction.
Bob (recipient) provides an additional output to be spent and consolidated with the new output. Alice receives change as before.

5 Grin -> 3 Grin 
1 Grin    3 Grin

Bob receives 2 Grin as before but consolidated with an additional spent output.
This new transaction no longer leaks any information about “direction” and we cannot infer anything about who paid who.
Alice and Bob both spend a single output and receive a single output in return.

If this was in fact reversed and Bob were paying Alice the structure (and ownership of inputs and outputs) of the transaction would be identical.

This is conceptually similar to a “payment channel” being funded and subsequently closed.
Note: This is not a payment channel and is simply a single transaction.

Then I read about PayJoin and P2EP and it clicked that this is exactly the same thing.

tl;dr PayJoin is a limited form of CoinJoin with only two participants.


https://en.bitcoin.it/wiki/PayJoin

What would be involved in supporting this in Grin?
We already need both parties to interact to build the transaction via a shared slate.
It does not appear to be a significant change to the process if we were to allow Bob to (optionally) add this additional input.
This would result in a minimal increase in the size of a transaction (one additional input) and in fact a reduction in the transaction fee due to output consolidation.
Is there any reason Bob would not want to consolidate with an existing output (assuming this was not done naively)?

I’m not aware of this being discussed previously in the context of Grin/MW, but could be mistaken.

8 Likes
2

Thanks for posting this! Funny, when I saw the blockstream announcement yesterday, I was actually wondering about the same, whether it could be used in Grin, and why it’s never been discussed, the PayJoin concept has been around for a while after all. :slight_smile:

Is there any reason Bob would not want to consolidate with an existing output (assuming this was not done naively)?

The only thing I could think of, is that by adding an extra input Ib into the mix, Alice now can identify Ib as belonging to Bob. Depending on the input, that might not be something Bob wants. This however, seems like a pretty low cost to pay for the benefit of having the rest of the world unable to follow the transaction graph as well.

What would happen if Ib is of amount 0 here, i.e. a complete dummy, generated as part of some self-spend transaction perhaps, and is then spent at some point in the future alongside real outputs?

It does not appear to be a significant change to the process if we were to allow Bob to (optionally) add this additional input.

If it’s optional, it makes it easier to intersect (equally balanced) transactions as PayJoins, but if all transactions are like that, it’s much harder to do. So let me take that a step further and ask why this should not become a mandatory requirement for transacting in Grin?

This would result in a minimal increase in the size of a transaction (one additional input) and in fact a reduction in the transaction fee due to output consolidation.

Side-point, but we ought to take a pass on the transaction fee logic before HF4 to ensure that whatever formula we end up having is not only encouraging output consolidation, but also tx graph obfuscation.

1 Like
3

I think, if I understood well the proposal, it is a nice idea.
The only potential drawback is that, iiuc, due to having to pick an utxo of his own, Bob, by picking it, may leak extra information about him.

But I don’t see any drawback if you would alternate this scheme with the normal scheme randomly (in average 1 times out of 2).

in that case, without further chain analysis, people cant always know if the tx’s inputs contained sender’s utxo only (normal tx) or sender’s and receiver’s utxos (the proposal)

4

Yes this is a good point.
This would be analogous to Bob subsequently consolidating the old and new outputs by spending them together (and linking them) in a new transaction.
Bob may not necessarily want this to happen during the transaction with Alice (or at all).

5

Yes, seems like it could be added in something like “advanced features” in wallets, otherwise receivers that do not want to be linked to something of their history on the past on the chain, may not be happy with that

1 Like
6

Very cool.
Let me know if I get this wrong.
Following @Kurt & @lehnberg 's remarks, It seems to somewhat obscure two new outputs, but sheds a big light on an older output so that it’s basically situation dependent; It’s no absolute gain or loss in privacy,
If so, Bob and Alice decide which way is best for them retain privacy in this specific transaction and point in time (keeping in mind their past and future footprints)?

7

So let me take that a step further and ask why this should not become a mandatory requirement for transacting in Grin?

We might not want to require all transactions to be PayJoins because we lose an opportunity to force further complications in analysis heuristics: rather than heuristics based on inherent properties of Grin like ‘all inputs in a transaction belong to same entity’ or ‘all inputs in a transaction are PayJoins’ we can force related heuristics to be based on idioms of use instead. Developing a useful heuristic for this would be more costly than developing a heuristic solely for PayJoin. Additional techniques to populate inputs for transactions could be added in the future to further complicate analysis heuristics.

It’s no absolute gain or loss in privacy…

The big picture seems to be less about Alice and Bob’s privacy in a vacuum and more about the collective privacy in general, as this would invalidate an existing chain analysis heuristic that could be used against any entity using the network, including Alice or Bob (that all inputs to a transaction belong to the same entity).

I’m curious to see how the flow of transaction building could be adjusted to accommodate this feature, especially how it could solve for the UTXO snooping problem.

4 Likes
8

Well put.

We might not want to require all transactions to be PayJoins because we lose an opportunity to force further complications in analysis heuristics

Over the weekend, I was thinking about the key “edge-case” situations discussed above where:

  • Bob opts out of PayJoin, for whatever the reason, perhaps he doesn’t want to share any additional UTXO info with Alice;
  • Bob cannot do a PayJoin, because he doesn’t have any available UTXOs, perhaps he just created his wallet etc.

If we were mechanically forcing every/most transactions to look like the structure described originally (2 x in → 2 x out), it would be quite easy to pick those edge-cases out from the transaction graph. If instead we recommended the transaction structure follow some kind of random distribution (with a reasonable floor and ceiling in terms of number of inputs and outputs used), it would be harder to discern a pattern, and you could not single out specific subsets of transactions as easily.

Wallets could be encouraged/advised to maintain “a lot” of outputs, which would do good for UX as well (the more outputs of various amounts are in a wallet, the less balance needs to be locked during tx building beyond the transacting amount).

1 Like
10

I like this idea, but I’m not comfortable (yet) with the privacy tradeoffs.

This however, seems like a pretty low cost to pay for the benefit of having the rest of the world unable to follow the transaction graph as well.

I’m not sure this can be written off as a “low cost”. This gives Alice the ability to query Bob’s wallet see if he participated in a previous transaction. This could have serious consequences for Bob. For example, if Bob creates a transaction in the past that is discovered to be linked to “political faction B”, then Alice my learn that Bob owns that output if Bobs wallet provides that output for PayJoin. If Alice is part of an opposing faction, she may choose to expose Bob (or threaten to expose him), or perhaps refuse to do business with Bob.

Whats more, does this only affect Bob? What if Bob doesn’t care if Alice can learn his involvement in a transaction, but the other participant in that transaction (say, Charlie) would prefer not to have that output associated with Bob? Now if Alice already knows about Charlie’s output, she may be able to learn from Bob, that Bob sent that money to Charlie. This could be equally serious for Charlie, and Charlie has no defense against Bob recklessly payjoining with Alice.

What would happen if Ib is of amount 0 here, i.e. a complete dummy, generated as part of some self-spend transaction perhaps, and is then spent at some point in the future alongside real outputs?

This is interesting. To generalize a bit, this requires Bob to have a pool of outputs that are safe to payjoin (perhaps 0 value decoys, perhaps not). Then it is of no consequence if Alice learns Bobs ownership of those outputs.

I think the challenge here is doing this in a way that is simple for even a novice user to mark a transaction as “unsafe for payjoin”. I can imagine a scenario where a novice user does not realize their “super secret” transactions may get exposed via payjoin.

11

If it’s optional, it makes it easier to intersect (equally balanced) transactions as PayJoins, but if all transactions are like that, it’s much harder to do. So let me take that a step further and ask why this should not become a mandatory requirement for transacting in Grin?

Keep in mind that the objective of PayJoin is to break the “common input ownership heuristic” used in chain analysis. Even if only 10% of transactions perform PayJoin, this may be enough to break that assumption and make chain analysis fruitless. Perhaps it is sufficient to leave this as an advanced wallet feature and provide some incentive for people to occasionally payjoin (perhaps host payjoin competitions? :upside_down_face:)

1 Like
12

In the most reckless of implementations, yes, Alice could spam Bob’s wallet with transaction requests and get outputs back. But that would be very poor design.

I imagine any serious wallet would not share Bob’s outputs with other parties without his consent.

1 Like
13

I was playing around with a similar idea now and realized that payjoin transaction can be cheaper to store if represented a bit differently.

First we observe that if we have an input A and an output B then the private key of the B-A point does not seem to leak information about either private key of A or B. This has been mentioned a few times before on keybase and other posts.

Since both sender and receiver have their own pair (input, output) in a payjoin transaction, it means that they could both share the difference in their private keys without leaking information. This means
that a payjoin transaction could theoretically consist of:

  1. A set of inputs
  2. A set of outputs
  3. A private key for the kernel

Note that such a transaction does not have a kernel only the private key that can be merged to a kernel offset.

What’s important is that this structure keeps the monoidal property of the regular MW transaction aggregation and comes at a benefit that aggregating two payjoin transactions in such form does not add any size to the kernels because they are represented as private keys that can be merged as opposed to regular kernels.

The issue here is of course that such transactions can’t have a lock height and more importantly have no fees. @tromp mentioned that one could use this private key trick to move ‘tainted’ transaction that have 1 input and 1 output -> ObscuroJoin transaction

Payjoin has a form of 2-2 and can actually be though of as two 1-1 transactions (for which we assume sharing kernel private key is safe) that have been aggregated into a single 2-2 payjoin.

I think this means that one could create a payjoin transaction and add it to a transaction that passes by and has high fee (the strategy that John mentioned in the thread I linked) or one could share such a transaction with someone other node that is willing to pay the fees in order to gain a 2-2 obfuscation. It’s a win-win.

The benefits I see:

  • can help those that need transaction obfuscation by waiting with their payjoin transaction to catch a transaction passing by with a high fee
  • can be sold off to random people if they pay the fee for that transaction
  • theoretical maxima is a block having 1 kernel that pays for the fees and everything else is an aggregated payjoin transaction of the above form (assuming no one needed a lock height) which
    results not only in smaller chain but also better privacy because the information about the number of
    transactions is no longer that accurate due to kernels not being present.
  • it doesn’t seem to need any change to the consensus rules

The drawbacks:

  • as mentioned, Bob gives more information to Alice but makes everyone else benefit - possibly including the chain if such transaction get merged.
  • payment proofs can’t be done in the form they are done now. I suspect Alice and Bob could sign something and embed a hash in their outputs, but that would be a bit more complicated and might require them to store the UTXO and merkle proof, but I don’t really know that.

Edit: this has a fatal flaw, read the answer below

1 Like
14

That would not be safe. If Alice shares private excess xA with Bob, with A_out - A_in = xA * G - v * H, in order to pay Bob v Grin, then it’s not really different from Alice having an input A_in of value exactly v, and giving Bob its blinding factor.
At that point you have in essence a 1-of-2 output, spendable by either, and when spent, both sides can accuse the other of being the spender, with no way for 3rd parties to tell who’s lying (and obviously no payment proof).

2 Likes
15

damn, nice catch. I knew it sounded too good!

16

Btw, is the underlying issue that makes the attack possible the fact that the private key that is shared does not describe something that would completely seal its context because it leaves some v*H?

Would for instance separating it in the form 1-2 that is done by Alice and then 2-1 done by Bob forming a 3-3 tx be resilient to this attack? So Alice shared her kernel pk for 1-2 and Bob for 2-1 which is essentially creating two separate txs and aggregating their kernel private keys.

17

The underlying issue is sharing private keys for a transfer of value between different users.

Increasing number of inputs/outputs makes no difference?!

1 Like
18

Something that crossed my mind. I think if grin had full blocks (1.5MB block), a “nimble” node would require only a constant space if we had only 2-2 transactions due to merging of kernel curve points and never creating more outputs than were spent. This would mean that with a “nimble” node and a smart IBD anyone would be able to verify the chain even if there were full blocks at all times (anyone could have such a nimble node running at home similarly as we have routers).

Which makes me think that PayJoin transactions also save space. Because there is no new output created for the receiver, it can be thought as just replacing an existing output of the receiver with a new one that holds more value. Likewise, replacing the output of the sender with a new one that holds less value. It’s like an inplace mutation of balance so there’s no hit on the chain regarding the outputs.
It might also make sense that regular transactions are represented as 2-2 where the sender adds two inputs (if that’s possible e.g. sender has > 1 outputs). This might help make regular 1-2 txs indistinguishable from 2-2 PayJoin transactions and chain analysis no longer guarantees that the receiver added an input. The sender did add an input, but they need to add it in any case. This would also mean that that it would be harder to identify the anchor outputs.

1 Like
19

technically every block has a new output so i dont think it would require constant space.

20

Correct. As it is right now, you can’t escape new outputs for coinbases. Having coinbase outputs be indistinguishable would allow this to be the case in most scenarios as new coins could be created through a 1-1 or 2-2, but this shouldn’t be the reason to go for that :slight_smile: i was talking merely theoretically, limiting to 2-2 is imo not a good idea, but making 2-2 the default to avoid creating a new output for every transaction could be very beneficial in the long run.

21

Yeah, that aspect is pretty cool. You also link that UTXO input with the new UTXO output, which would otherwise not be linked. Lots of pros and cons all around. If the sacrifice of privacy was seen as acceptable, wouldnt the original grin-wallet implementations of spending all UTXOs, which consolidate all outputs to a single UTXO change output for the wallet the most scalable and also prevent replay attack?