btcpayserver / btcpayserver-doc

BTCPay Server Official Documentation
https://docs.btcpayserver.org
379 stars 257 forks source link

Queries on possible changes to payjoin-spec #486

Closed AdamISZ closed 4 years ago

AdamISZ commented 4 years ago

The following refers to this version of the doc.

First a thanks to @Kukks for bringing this to my attention, and to the whole project for implementing this, it looks like a major step forward. I wanted to review a little bit by comparing with what I did in Joinmarket a year or two back. Also apologies for not reviewing the code itself, but that would be very difficult for me.

Here's what I came up with:

There are several additional points you make here that I didn't consider, that are excellent, but no need to detail them I guess :)

Kukks commented 4 years ago

Hey @AdamISZ , thanks for the feedback! The specification document covers the code in quite a detailed manner( most of the technicalities were written following the code line by line) so it's fine to skip code review, especially if you don't know how NBitcoin (and C# syntax in general) works in detail.

The spec does not mention input/output ordering. This is mentioned in the original BIP79 but I think could be clearer. I can see an argument for just enforcing BIP69 everywhere, as it makes it easy for both sides to reason about.

BIP69 is applied from what I remember. We tried to only mention where we deviate from the original BIP to keep it short. We'll probably go into more detail if we decide to propose an amendment to the original BIP or create a new BIP entirely.

I already mentioned this in earlier discussions, and people don't seem to agree with me, but just for the record: in JM i have the sender specify a (payjoin) version range and the receiver responds with a choice from within that range (in JM only a version 01 exists for now). Although one can retrofit versioning (no version = version 0 so to speak), I don't see an advantage in not being explicit.

As this payjoin protocol uses BIP21, we can easily expand on this later, if needed. We're currently using the key pj to signal payjoin support with the value being the url of the endpoint.

If for some reason, we need to commit breaking changes to the protocol after it has been sufficiently adopted, we could always try one of the following options:

If for some reason, we notice servers start offering partial support of the specification, there are the following options:

You don't mention the UIH1 or UIH2 heuristics that were discussed here. Does that mean the receiver utxo selection doesn't pay attention to that? To be clear, I don't think that's necessarily a problem, but one can argue it's useful to address it. In the JM implementation the approach can be summarized "try to avoid UIH2 but go ahead anyway even if you can't". I guess if you had included this in the code it would have been mentioned here.

We currently have a very basic implementation of utxo selection based on UIH1 & UIH2 with a limitation that it has only been checked against the contributed input. I'm working on making it a proper check on all inputs and should come soon. That said, if a desirable input ( or inputs, as we can maybe find multiple utxos that do fit better than a single utxo) is not found, we grab a utxo deterministic manner. Here is the code comment on that deterministic selector:

        /// This comparer sorts utxo in a deterministic manner
        /// based on a random parameter.
        /// When a UTXO is locked because used in a coinjoin, in might be unlocked
        /// later if the coinjoin failed.
        /// Such UTXO should be reselected in priority so we don't expose the other UTXOs.
        /// By making sure this UTXO is almost always coming on the same order as before it was locked,
        /// it will more likely be selected again.

The snowball effect and whether the receiver chooses utxos "greedily" or not: in extreme a merchant can end up with only having 1 utxo if they do payjoin with every tx, because they always consume the last payment they received in the next payment. Obviously this is not a realistic scenario but notice how it's undesirable, almost certainly: first, because the growing size of the utxo flags what is happening, and second, it's undesirable if every transaction is a payjoin, since that makes the blockchain analyst's job easier, at least potentially, than if there is a mixture of payjoin/non-payjoin. So I guess this is just the same as my UIH comment above. To the extent you are deciding on a standard, you don't want to be completely restrictive on utxo selection algorithms, but it may be worth specifying what should be avoided in utxo selection, at least.

It is very unlikely that a payjoin will happen so often to cause such an obvious snowball, due to the many restrictive factors of doing a payjoin:

Will fix the typos for the rest, thanks!

NicolasDorier commented 4 years ago

I can see an argument for just enforcing BIP69 everywhere, as it makes it easy for both sides to reason about.

We can't do this. Because it would mean that transactions without BIP69 are not payjoin. So instead, we just randomize.

What we could do though is detecting whether the sender is using BIP69, and use it instead of randomization in this case. This would be a net improvement on the privacy for sender's implementing BIP69.

AdamISZ commented 4 years ago

Doh, yes of course. But glad I raised it now because that is a good solution :) Yes we should probably stop using bip69 anywhere because of this, even though there are arguments for it, none of them overcome the problem that we really can't have a fractured set of behaviours.

Re:

BIP69 is applied from what I remember. We tried to only mention where we deviate from the original BIP to keep it short. We'll probably go into more detail if we decide to propose an amendment to the original BIP or create a new BIP entirely.

But, as I said, from my reading of BIP79, it is not clear, it considers this an implementation-specific detail, which doesn't seem right. To quote: "Check if the transaction was already sorted according to BIP69, if so ensure the result stays that way. Otherwise probably just shuffle the inputs/outputs" and in the Sender Validation section says basically "different ordering is allowed". So nothing specific is required.

Anyway, I think @NicolasDorier 's suggestions seems right.

6102bitcoin commented 4 years ago

Moving my discussion with @Kukks over to here.

Suggestions for improvement:

Increasing Cost of Spying

If the original transaction is broadcast, the merchant will have been spied upon (window shopper). There is some inbuilt financial cost (the user doing the spying must spend an amount equal to the least expensive item in the store) however depending on the store this could be a low price to pay.

Proposal: The merchant sets a threshold under which a PayJoin is not offered to the customer, increasing the cost of spying to this threshold.

Breaking the PayJoin Heuristic

It may be possible to compute which side of a PayJoin a merchant is on my performing statistical analysis on the amounts transacted in each scenario. If a merchant can generate fake PayJoins then they can confuse this statistical analysis.

Proposal: Enable the merchant to construct transactions with redundant inputs to create false PayJoins which throw off any statistical analysis of the PayJoins.

Breaking 'Next PayJoin' Heuristic

Currently, in the case where the merchant an 'exposed' utxo (the customer broadcasts the original transaction after having seen the modified transaction) they put the exposed utxo into in a prioritized pool so that it is used in the next payjoin instead.

Now suppose a chain analysis company partakes in a PayJoin with the merchant, broadcasts the original transaction and logs the exposed utxo belonging to the merchant. If it is guaranteed that the this utxo will be used in the next payjoin then you have introduced the possibility for a heuristic - that the next transaction involving that utxo is a payjoin on the recieving side.

Depending on the complexity of the subsequent payjoin this could be enough information to completely map the subsequent payjoin which a different customer makes with the merchant.

Proposal: Randomly assign this exposed utxo into one of three groups 1) To be used in a PayJoin on the receiving side to be used no sooner than 24h 2) To be used in a PayJoin on the sending side to be used no sooner than 24h 3) To be used in a Fake Payjoin no sooner than 24h

By doing this you break the ability for the chain analysis company to develop a useful heuristic. I think you need a time here (24h) to account for the fact that merchants typically receive far more frequently than they spend, thus the delay acts to balance the chance that they are on the sending side of a PayJoin.

2in2out Data Leak

An additional risk is a 2in2out PayJoin. A chain analysis company who broadcasts the modified transaction will be able to identify which output belongs to the merchant (by elimination) and if this is only used in another PayJoin on the receiving side they can deduce how much is transferred by the user who subsequently PayJoins with the merchant. (I explain this in more detail here)

The above proposal also resolves this issue.

Kukks commented 4 years ago

Good feedback @6102bitcoin

The merchant sets a threshold under which a PayJoin is not offered to the customer, increasing the cost of spying to this threshold.

ACK, we currently have a setting to not show on-chain payment methods if below a specific amount so there is a current way to do this but i do think we should add a specific payjoin threshold property.

In your opinion, what would be the sweet spot for a default value? Keep in mind each attack is a payment to the store.

Enable the merchant to construct transactions with redundant inputs to create false PayJoins which throw off any statistical analysis of the PayJoins.

This is reminiscent of the research from @nopara73 for the clusterfuck wallet concept (links: https://medium.com/@nopara73/new-bitcoin-anonymity-technique-the-clusterfuck-wallet-d48aa1787324 https://medium.com/@nopara73/pay-to-endpoint-56eb05d3cac6 https://github.com/nopara73/ZeroLink/issues/42)

I'm not sure how to fake a payjoin, would it just be doing a transaction with 2+ inputs used in previous payjoins and paying to self with 2 outputs? I think a better solution is to go all out and just fake a transaction of any type, full input transfer, coinjoin simulation, etc.

This incurs cost and disincentives merchants from enabling payjoin though.

Breaking 'Next PayJoin' Heuristic If it is guaranteed that the this utxo will be used in the next payjoin then you have introduced the possibility for a heuristic - that the next transaction involving that utxo is a payjoin on the recieving side

This is a valid concern. Initially I wanted a pool of utxos to prioritize in the case of failed payjoins but it definitely creates the possibility of a new payjoin specific heuristic. The good side of this is that it limits the damage of spying by making the sender end up getting the same exposed utxos over and over, while spending money on payments( and in the case of using RBF/double spends to cancel out, transaction fees).

Even a successful payjoin allows this heuristic to form, if there are not enough utxos for liquidity as the snowball effect starts happening.

The solution is again similar to the clusterfuck wallet so I would group it with it.

As mentioned before, we want to (in the future) allow merchants to schedule low-priority transactions they wish to make to be made later. Since the payjoin specification does not require a proposed payjoin to pay the original BIP21 address, we can cause chaos by using the payjoin to pay the schedule transaction(s). This means that the Sender ends up coordinating with the receiver, who contributes inputs, and pays a third party( or parties!), completely raping any gathered assumption of input ownership based on payjoin history of a merchant. This would break the spying issue along with next payjoin heuristic due to the outputs not being guaranteed to go to the receiver anymore.

AdamISZ commented 4 years ago

ACK, we currently have a setting to not show on-chain payment methods if below a specific amount so there is a current way to do this but i do think we should add a specific payjoin threshold property.

In your opinion, what would be the sweet spot for a default value? Keep in mind each attack is a payment to the store.

In my opinion @6102bitcoin it's probably true that the on-chain payment threshold is similar to the payjoin threshold in practice. I noticed that when trivial "cost" (in terms of utxo ownership) was applied in JM the snooping attacks stopped. In this case it's even a much better defence, as bitcoin network fees must be paid (remembering we have non-payjoin fallback in case of failure to complete protocol). Now of course the attackers may have been very weakly motivated in the JM case, but still I think the evidence favours the idea that even a small on-chain cost strongly demotivates attackers.

I don't think the idea of faking PayJoins makes sense, if they are properly constructed they are at least mostly, if not entirely, steganographic. On the more general topic of faking tx types, I'm certainly a supporter, but it is always a kind of weak measure, since it costs chain space and doesn't obviate the problem of recombining utxos in future spends, which still has to be dealt with somehow.

If it is guaranteed that the this utxo will be used in the next payjoin then you have introduced the possibility for a heuristic - that the next transaction involving that utxo is a payjoin on the recieving side.

To me, the key phrase here is "If it is guaranteed.." - exactly because we have a steganographic property, this caveat is strongly needed in the sentence (notice, how strictly, some similar caveat is needed with equal out coinjoins since you never know 100% that it is coinjoin, it's just this is so unlikely to be an issue that everyone ignores it). Which to me means, we just need it not to be guaranteed. And indeed it isn't guaranteed, and there isn't much reason for this implementation or any other implementation to create that guarantee (that payjoins follow payjoins), which means such an assumption will never be safe, even with completely heterogeneous implementations.

This relates back to a worry I had from seeing public discourse around this issue - customers may "get religion" about this technique and insist that every payment they do to a merchant is a payjoin, else they'll be upset that they weren't given proper privacy. This is really a tricky point, because (a) I think the effect of payjoin is considerably better if not all merchant on-chain payments are payjoin, but (b) such customers do have a point - the non-payjoin at least makes the payment amount a bit more obvious (just because it's plaintext on-chain), but I fear they didn't understand that the payment amount is in any case only one out of a small set of possibilities. I kind of ranted about this a bit here.

nopara73 commented 4 years ago

Any chance someone can writeup a summary of this conversation? You're writing a book here 😄

NicolasDorier commented 4 years ago

Breaking 'Next PayJoin' Heuristic

@6102bitcoin the way we implement it, the attacker can't be exactly sure that the next pj will use the same UTXO.

What we are doing is this: (this is not documented)

Now, if an attacker broadcast the original transaction, the used UTXOs get unlocked. The used UTXOs are not guaranteed to be used next, because the merchant may have received another UTXO meanwhile which is sorted first the unlocked UTXOs.

About the fake Payjoin idea, while I agree it would work, there is severe difficulties UX wise. This is not easy to understand for a merchant, and cost him money (for something he likely doesn't understand), so I am not too fan.

AdamISZ commented 4 years ago

Any chance someone can writeup a summary of this conversation? You're writing a book here smile

I think we're trying to make sure that what is in this document, as a delta to BIP79, is what we want everyone to agree on. I think either an updated BIP79 or a new BIP is kinda necessary, because we're going to have multiple wallets doing this, and I'm fully in support of btcpayserver leading that effort, as their support for the protocol is the most important element of it actually getting any usage.

I can try to summarize what I understand so far, but others may disagree:

nopara73 commented 4 years ago

We seem in agreement that we don't want BIP69, but we might have to account for it if the sender uses it, see further here.

ACK. I could make my case, but since you're in agreement, I think it's unnecessary.

Should we support Fake Payjoins? My answer is that I don't see how it even makes sense, and no, and also I don't think that's a matter for discussion in a protocol-defining document for standardization.

ACK, from a privacy point of view it may does more harm than good, like stonewall, as it merges UTXOs before time and economically also bad as it also unmerges them in the same tx.

Sidenote. Not sure if you examined it (I did) and PJ is less economical than normal txs. While it isn't that significant to keep mentioning it market facing conversations, but it's important for us to know.

Much of the remaining discussion can be categorized as "how are utxos to be selected for payjoins by the receiver/merchant"?

I will not chime into this discussion, just give some points to consider:

Anyhow, these are just my quick thoughts on coin selection, I can be utterly wrong as I did not read the conversation before, thus I did not see the great points made on this.

NicolasDorier commented 4 years ago

@AdamISZ our doc in btcpayserver-doc is giving too much details for a BIP.

I think the BIP can be focused only on the protocol aspect, and not on considerations which does not impact protocols. (for example, best practices in UTXO selection should not be part of the BIP)

The reason is that the protocol will unlikely change, why the best practices might as we learn.

However, we should include what the receiver and the sender are expecting to accept or to reject.

I can write a BIP, but I will wait 1 or 2 months, the time that we all dog food a bit on what is out and are sure the protocol is not too restrictive (missing potential use cases) or too permissive (introducing vulnerabilities).

AdamISZ commented 4 years ago

(for example, best practices in UTXO selection should not be part of the BIP)

That point seems debatable, although after thinking about it carefully I mostly agree. The original BIP79 suggests that utxos of the same scriptPubKey type should be used ('strongly preferable' is the phrase) but if there are other utxo selection algorithm elements that could screw up the steganographic effect, or privacy effect (both, separately) then we might want to consider a "strongly disadvised" in the protocol/BIP doc. I honestly think "prefer to not violate UIH2" as per previous discussions is a desirable addition, but I am fine with that not being done, as long as it has been considered. There are even other points - what if the receiver contribution is 2 orders of magnitude bigger than any normal consumer wallet? Input 1 is $50 and input 2 is $500,000? - though, again, I am fine with this being considered, but not included. Are there other bad utxo selection practices I am ignoring? An obvious one of reusing addresses in input/output :) There may well be others.

I can write a BIP, but I will wait 1 or 2 months, the time that we all dog food a bit on what is out and are sure the protocol is not too restrictive

This is extremely reasonable, but - it seems that more than 1 or 2 wallets are already actively considering, and even coding, support for this protocol. That's really why I opened this issue, even though it's a bit vague and perhaps not an ideal github issue. To be fair, what we have here is already detailed enough for people to work with. Let's see if they come up with compatible sender implementations :)

There are other points I would like addressed, although not in a BIP: (1) @nopara73 's statement above that payjoins are less economical, which I believe needs a lot of fleshing out (it's not obvious to me - receiver is making extra on-chain load, but may get second order benefits later that counteract; consolidating/batching), and what implications it may have for payjoin tx construction or (2) a detailed analysis of whether active snooping attacks are sufficiently defended by the mechanism as laid out in BIP79.

nopara73 commented 4 years ago

payjoins are less economical, which I believe needs a lot of fleshing out

Get a whiteboard, come up with scenarios, write down PJ and non-PJ alternatives and count the number of outputs in all scenarios. If you go far enough the txchan you'll realize that at best it's equal. Look at the total network load and not how the receiver or the sender individually benefit from it.

Kukks commented 4 years ago

Some discussion on Twitter re. spying attacks: https://twitter.com/n1ckler/status/1252923202390634496 with one proposal to only accept an original tx at the endpoint with a specific minimum fee rate

@NicolasDorier We should look into adding some reporting for merchants to see if spying attacks via double spends becomes an issue

NicolasDorier commented 4 years ago

@Kukks this is the right approach to do it https://github.com/btcpayserver/btcpayserver/pull/1499

LaurentMT commented 4 years ago

As per AdamISZ s' suggestion, here's a collection of random (high-level) thoughts that may have some utility (or not) in the context of this discussion. I've put them into a gist to avoid the pollution of this thread. https://gist.github.com/LaurentMT/c38794ef6a62b2f8c76d7f694a3e7777

NicolasDorier commented 4 years ago

@AdamISZ in a nutshell, I have been a bit lost in all of this thread, at the end of the day, is there something specific you want us to change?

@LaurentMT I think there is another approach to get privacy than having all wallet behaving the same way: Analysis poisoning. The protocol we implemented allows for the payjoin receiver to poison analysis by using heuristic in their advantage.

For example we can change the output scriptPubKey type in order to make analyst believe that it is a change, when it is not. This make analysis reach tea leaf reading level of accuracy. Maybe tea leaf is good enough reason for exchange to freeze the coins, but it would not hold in court.

Another example is round outputs which are in reality a change address.

How those heuristic or poisoning will change over time is quite unpredictable by itself. There is enough flexibility in the protocol to change it without breaking clients.

nopara73 commented 4 years ago

Another example is round outputs which are in reality a change address.

You meant the opposite, right? The round output is the active, non-change output.

NicolasDorier commented 4 years ago

@nopara73 a round output is normally identified as the non-change output yet. But with analysis poisoning, the payjoin receiver can round the amount sent to the change address of the sender. It would cost some money to the receiver, but the sender would not reject it. This would cause an analyst basing himself on heuristics to take the wrong conclusion.

Or, in the case of "spare change", fake round amount so the analyst think it is a direct payment. (we already do this)

nopara73 commented 4 years ago

Wait a moment. I didn't think of it before: Could a PayJoin transaction be potentially identified by round amount? Let's see.

Take the normal transaction 2.5 -> 1, 1.5, where 1 is the round amount, so that's "likely the payment."

Then make it a PayJoin: 2.5, 3.123 -> 4.123, 1.5, where potentially both output can be interpreted as the round amount as the first output gets the precision of the second input and the second output gets the precision of the first input.

Based on this quick thinkthrough a PayJoin transaction not only cannot be identified by round amount, but even better as it nullifies the round amount heuristic.

NicolasDorier commented 4 years ago

@nopara73 there is two cases in the spare change case

A sender a whole UTXO 2.5 -> 2.5, the receiver payjoin transform it into 2.5, 0.5 -> 2.0, 0.4938264. The analyst will think that the payment is the 2.0 UTXO and that 0.4938264 is back to the sender. However, he would be wrong. Both UTXO belongs to the receiver!

There is also another case:

Sender 2.5 -> 1.245, 1.255 with 1.245 being the payment output. Now what if a receiver transform that to 2.5, 0.5 -> 1.245 , 1.7? The analyst would now think 1.7 is the payment output.... nop, this is the change :) Of course in this example, it means the receiver give 0.5 to the sender, but that's for the purpose of the example. We can imagine smaller UTXO with similar trick. (or similar result by modifying both outputs in order to round the change)

I plan in the future to make the receiver smarter about poisoning analysis, which is why, in the spec, I tried to make the sender not be too strict about what it needs to check for.

Kukks commented 4 years ago

I'll be closing this issue since BIP78 is now out there in the wild! If there's anything new to look into regarding the discussion above, feel free to comment again here.