-
Notifications
You must be signed in to change notification settings - Fork 119
Duplication of offers from makers. Many makers one wallet #693
Comments
Wrote up an idea here for solving this using sorted merkle trees https://gist.github.com/chris-belcher/eb9abe417d74a7b5f20aabe6bff10de0 |
@adlai and I had a conversation in IRC earlier, we realised that the maker doesn't need to commit to his UTXO-count in public, they can reveal it later when they send their proof privately to the taker. So this particular privacy problem is gone. Edited the document to reflect this. |
There might be a scale problem for when the honest-makers-replaying-proofs-of-fraud. Only one honest maker is necessary but what could happen is every maker uploads all that data each time, which seems wasteful. |
(Bit of a side-note but worth saying:) I think it's important to distinguish two different behaviours here, and two (at least) different motivations:
This issue is about 1/ (I'm not 100% sure, but I don't think it'll be easy for it to address 2/ ? at least, not as described in the gist); it's worth noting that it was actually 2/ that was causing a mini-crisis for JM in the immediate aftermath of the 0.2 protocol update, and was only really resolved in the 0.2.2 update that allowed to fallback to less than the initially requested makers. I've read through the gist now, thanks for it, I'll doubtless have more questions about it later. |
Looking at someone else's thoughts on reddit made me remember writing this gist, see the third bullet point in that section, for convenience here:
This is part of @adlai 's taker sophistication approach; on the surface it seems like a cool amelioration of the problem, but it does have a pretty serious fly-in-the-ointment: any system that kicks two bots that duplicate utxos has to be aware that an adversary could use this to kick the competition if he knows their utxos. This could probably be addressed with signing, but has to be done carefully. Thought it was worth adding to the thread as another idea in case people weren't aware. |
Hmm looking at that idea again with fresh eyes, I see (1) a really cool feature of it, but (2) a reason why it's probably just not going to work against a sophisticated attacker.
So unless I missed something, this idea is not good enough to fend off reasonably motivated economic attackers. |
Sending to everyone else in the pit also wont work because the adversary can connect with another bot of theirs that never says anything. |
Yeah, lol, I was getting overexcited there! Still that transferrability property is something to consider if it's set up right (crypto-wise), even though of course you don't get that extra "in secret" feature which I was erroneously imagining. Further thoughts along these lines, which I still think are going nowhere but worth mentioning, would be to have some kind of "guard" bots that probed makers' utxos and then did the public reporting of bad behaviour, with the obvious and slightly amusing problem that this behaviour was made deliberately expensive by our solution to #156 . With a trust point you can avoid that cost, but then, you can do pretty much anything with a trust point. With that idea thrown out, I still don't have a good idea here. |
PODLE for committing to Maker utxosI'm not sure why I initially rejected this concept, but thinking about the problem again today, and remembering this reddit post made me re-examine it. It may be a good idea. Further chat on IRC brought up a tweak from @chris-belcher that may make it more practical. Outline of idea.The germ of the thinking is something like this: we need the maker to really publish their full list of utxos to avoid duplicates, but they need to be private -> note this sentence is not 'true' but a hypothetical assertion. We already have a primitive that provides the properties of a commitment (hiding, binding) but with the additional feature of uniqueness - the PoDLE as currently implemented for takers for rate-limiting. Note: in rate-limiting mode it's nice that we can use multiple NUMS base points, and hence different PoDLE values (or H(P2) values); see So an outline of a simple idea would be: Taker -> !orderbook The !hp2 values would be generated similarly to how they are currently generated by Takers for each utxo/pubkey, but with only a single globally agreed NUMS point (such as index 0). Taker needs to maintain a database of all !hp2 values he sees ( Then, in the In the simplest analysis, there is no possibility for a rogue maker to cause banning of another - because he cannot predict podle values in advance, he cannot pre-broadcast in such a way as to cause the honest maker to be banned. However, this analysis is wrong in practice: since Makers can and do re-connect regularly, and are offering utxos for long periods, they must re-announce the same podle values under new nicks(identities), which according to this simplistic rule, is banned behaviour. Correction due to @chris-belcher : use a Taker-generated nonce to tweak the hp2 value. Algebraically, I'd imagine it working like this: Taker: !orderbook [16 byte nonce] Maker: calculate H(P2) using the procedure here, but with the tweak that the nonce is fixed in the hash:
(I think this is the right way to do it; agree?) Thus, the podle values are deterministic from this Taker's point of view, so repeated utxos are disallowed, but repetitions for different transactions are allowed, unless the Taker deliberately re-uses a nonce, which serves no purpose as he is only attempting to enforce honesty on his counterparties. Also note that since Problems
One main reason such ideas don't immediately crop up is the bloating of message passing data. Here we could imagine ~ 30 utxos meaning 30 x 64 hex chars or 30 x 32 if we truncate hp2 values in half (should be fine security-wise, 16 byte entropy) being broadcast in the offer message, and by all makers. Then, in addition, we have a large chunk of 100-200 bytes per utxo-used-in-transaction added to the
It's probably not the case that adding these podle-style commitments to the offer message adds any important privacy leak. Note that the offer publication is before the Taker-provided rate-limiting commitment in
The nonce idea (which as a reminder, is a solution to the problem that if we banned repetitions without this randomizer, then re-connecting bots would be banned - same utxos) works in the interactive scenario. If bots are still to publish their offers to the public channel, for passive participants (e.g. long running Takers), then it precludes them publishing !hp2 values according to this scheme. One approach is just to abandon public announcement. I'm not clear on this yet. This was written as a comment rather than a gist because I'd like to canvas opinion about potential weaknesses before going further. |
Our IRC log of this conversation.
|
The taker needs to have access to the UTXO set, correct? They need to be able to know that a UTXO is truly unspent and what pubkeyhash it lives on. If so, that makes it harder to do #653 because that has the problem that it doesn't have trustless access to the UTXO set. #682 is a solution but just amounts to trusting makers, the very entity we're trying to stop cheating here. There might be a way to make it work but requires a bit of thinking about. |
At first it seems clearly right; but then I wondered about the fact that we have the pubkey in receiving If the thinking there is right, there might be an argument that: considering only economic incentives, lying about the podle by using an invalid pubkey can only lead to creating failed transactions, not economic advantage, even if the Taker just takes the pubkey in the sig as given (i.e. doesn't check via utxoset). That would involve only checking the podle after |
For economic incentives its easier because a coinjoin just won't be accepted by the network unless everything is valid. I'm more concerned about DOSers who want to deny service with a wider reach. For example, one way to detect an invalid UTXO is to notice that pushtx() always fails. Then the taker could ban all the makers, but that allows one DOS maker to get 5-6 other makers banned by that taker. |
Yes, seems fairly clear: you either check the validity of a commitment upfront, or you allow the blockchain to check it for you. In the latter case, you can't detect the cheater yourself, only that there has been cheating. Clearly the superior model is to actually check it oneself, to detect the origin of the bad behaviour, so it's a question of whether we make that a requirement of all participants. If not, one can hope that the absence of an economic incentive is enough. If absence of economic incentive isn't enough, we're solving a much harder problem. There are other DOS vectors than this. I would just say, forget it, Taker needs to be able to check utxo commitments, but I'm keenly aware that the possibility of an SPV mode is very important, and if this breaks it, that's not something to be brushed aside, not at all. Meanwhile, I'm leaning towards believing this is a valid approach, but I want the message channel to support the kind of bursty bandwidth we get in the orderbook return. Feels like we stretched IRC to its limit. |
That's a good point, that is someone wasn't economically motivated they could DOS joinmarket today. Regarding IRC, I just came up with #713 which might be good at smoothing out the traffic on !orderbook. Trying to think of any other places where IRC would be stretched the most, maybe the !sig and !tx replies are the biggest after !orderbook |
In the maker wallet utxo podle commitment idea, the taker should send the nonce it used to the makers when filling an order, to avoid the makers having to keep a record of every nonce. |
@chris-belcher I didn't understand that, I thought the idea was to add the nonce to the orderbook request so the makers can send their podles with their list of offers? ( |
@AdamISZ Yes, the taker uses |
@chris-belcher got it, thanks. |
I had an idea to massively cut down on the amount of data transmitted in the "podle for committing to maker's UTXOs" idea. Some background first: Bloom filters are a probabilistic data structure. They can be used to test whether an element is a member of set. If the test returns false then the element is for sure not in the set. If the test returns true the element is either a member of the set or is a false positive. So set-membership can return false positives but not false negatives. The false positive probability can be controlled. A bloom filter is a bit array. To add an element to the set, hash it and use that to set certain bits in the bit array to be 1. To test whether an element is in the set, hash it and check whether the bloom filter bit array has 1s in all the correct positions. Also, set intersections can be tested for by ANDing the two bloom filters. To apply this to the maker podle UTXO commitments, the maker would calculate all the UTXO podles and add them to a bloom filter. It would send that bloom filter to the taker who requested !orderbook. The taker would check for any set intersections of the bloom filters. If there are any intersections then that is a strong indication that those makers are using the same UTXO multiple times and the taker will discard them. When the taker chooses makers and sends !fill to them, the makers must send their podle hash along with the other proof for opening the commitment. The false positive rate of the bloom filters will be chosen so that a false positive intersection happens very rarely. Since the bloom filter is a fixed small number of bytes, this scheme reduces the data transmitted and makes it scale as O(1) with respect to the maker's UTXO count. Attacks / Mitigations A malicious maker could send a bloom filter set to all 1s which would match with everything. To solve this, the taker must be coded to first reject bloom filters that match many other bloom filters. In other words it must retain as many bloom filters as possible with the requirement that they don't intersect. I.E. If there are filters A, B, C, D and E. And E matches A and B but A,B,C,D dont match each other, then reject E, not A or B. It should be possible to find E in this case with a scalable algorithm by using a divide-and-conquer binary search style algorithm. For example batch verifying all the bloom filters by ANDing them together, and if there is a match then split them into two groups and AND all those, etc continue until you find the intersecting filters. Another attack is that a DOSer could connect with many many makers and send out lots of random bloom filters hoping to collide with genuine makers. To help against this, when faced with two bloom filters that intersect each other and don't intersect with any other filter, the taker should just randomly choose one to reject. Also it's worth noting that a very similar DOS to this is possible today by lots of fake makers just announcing offers and never filling them. Finally, a possible attack would be faking bloom filters after the fact. I.E. is it possible to come up with another podle commitment that still matches the advertised bloom filter. If a cryptographically-secure hash function is used in the bloom filter algorithm then I'm pretty sure the answer is no, because finding such a collision would involve partially bruteforcing sha256 or sha512. |
|
It would be great if someone else started looking at this apart from us 2 and chimed in. My feeling is that the bloom filter approach is adding complexity it'd be better to avoid. I wrote this some short while ago: Mar 01 22:31:44 back of envelope, for background: est. 30 utxo/wallet, est 25 bytes of truncated 16 byte commitment with encoding, est 150 counterparties: 112kB !orderbook response. It just seems to me the right solution is a message channel implementation that is more forgiving than a public IRC (which is explicitly designed for human chat) is the right thing to do. Adding compactification, and then having to deal with attacks, seems a bit against the spirit of the idea (which was to remove any doubts about getting fakes). None of these comments mean I'm sure one way or the other, it's just my feeling, currently. |
Questions before I write a longer reply: The communication order is:
(M|T)PCn: Maker/Taker PoDLE commitment After Taker gets MPP, Taker can decode MPCn, revealing the UTXO (TXID)? If that is correct and Taker can decode all of the MPCn, then the first problem I see is Taker gets access to all of Maker's UTXOs but only gives up one of its own. And !mhp2 is not like !hp2, because MPCn is only used by one Taker, for one transaction, right? It could be sent to Taker in private? |
The taker gets all the commitments but not all the parameters i.e. not every commitment is opened, so the taker only learns the UTXOs that will be used in the coinjoin. Yes, what you're calling !mph2 would be specific to that one !orderbook request because it involves the nonce, and therefore that information could be PM'd to the taker. |
More comments.
Overall I think this idea:
|
@eduard6 What they could do is DOS, you're right about that. That would use up some of the taker's UTXOs for commitments. As you mention the only help against that is to not interact with that maker again. From what I see, the proposal in this thread of requiring the maker's PoDLE commitments doesn't make this DOS any worse. That DOS already exists in joinmarket today. (Of course it's still bad, but doesn't affect this proposal) You are right about a malicious taker sending !fill to every single maker in an effort to obtain their UTXOs. I think we discussed this a bit in #156 and it is hoped that the 20% amount requirement and 5 confirmations would be enough to severely rate-limit this. This blog post also describes the taker's PoDLE commitment scheme as a race https://joinmarket.me/blog/blog/racing-against-snoopers-in-joinmarket-02/
Yes, only the UTXOs that the maker intends to coinjoin need to have their commitments opened as proof. |
Regarding the bloom filter. I also don't have strong feelings either way but here is some more analysis. Of course I agree that another messaging channel is a great idea, but the two ideas don't exclude each other. For the new messaging channel it has to be said that we don't know of an idea that works yet. The main advantage of the bloom filter idea is it converts O(N) scaling to O(1) scaling. Although that back-of-the-envelope calculation finds a reasonable value for bandwidth, its still subject to O(N) scaling in UTXO-count. Your calculation assumes 30 UTXOs but here are two situations where that number could be much higher:
I think focusing on the dealing with attacks is unfair against the bloom filter idea, most ideas have possible attacks, spending a lot of text on mitigating attacks doesn't mean the idea is vulnerable or complicated. If we go over the attacks I wrote about again: the third attack is not a problem and nothing needs to be done against it, the second attack requires a slight change (when faced with two intersecting filters, choose one randomly to discard instead of discarding the first-seen or second-seen) and the third attack requires someone to keep an idea in mind when writing the comparison code that would have been written anyway.
There won't be doubts. Bloom filters have false positives but not false negatives. So if two filters result in false when checked for set-intersection, then we can be 100% sure that the wallets do not have any UTXOs in common. False positives means that sometimes one maker will be (unfairly) discarded in favour of another just by chance, this can happen with probability 1% or 0.1% or whichever we choose. It will depend on the taker's nonce value so will change every time and will hurt every maker equally. This is my feeling for the best way to go from here
|
@eduard6 some brief response to your main Qs:
Indeed, the design as exists forces the taker to reveal one utxo, although it doesn't have to be connected to the transaction. I struggle to see an alternative, unless perhaps based on fair-exchange protocols (I get secret X iff you get secret Y) (I have a vague sense it's impossible without a TTP; in tumblebit, darkleaks and the like, the TTP is the blockchain). There are a lot of subtleties; in a complete JM tx run, the input utxos are all exposed due to the effectiveness of joinmarket-sudoku, the only claim is that fungibility is gained in the coinjoin outputs. If a maker aborts early, knowing the utxo, it's debatable what that gains; knowledge that a user wants to gain fungibility on utxo U, which is presumably not currently deemed sufficiently fungible; and that knowledge will in any case be gained in public if U is used in a future JM tx. But I agree, there is a privacy leak here of some sort in some scenarios. I don't (yet) see a better way.
Yes, they can do this. The question is, what kind of attack. From context it seems on this point you're still talking about the previous attack you mentioned, learning taker utxos. If you were talking about economic attack I tried to address that in the previously mentioned gist. So assuming the former, my previous response applies.
Indeed, this is also inherent in the current design (takers can get a few utxos from every Maker by filling all of them); in fact, @adlai was working up a taker-sophistication algorithm to use that to advantage (query a larger-than-needed set; try to do a tx, keep some in back pocket). And the design was specifically set up to allow it (so not the delay approach you mention). Remember, in the pre-podle design, requests were free and attackers used that to (attempt to) gain a very full picture of the maker utxo offer set, as it evolved over time. Podle rate-limiting can only increase the cost of that. I was originally worrying that it would be too cheap, but the attacks entirely stopped taker-side after it (my sneaking suspicion is because attackers don't want to reveal even one utxo).
Yes.
Yes, they can become multiple participants but only in the sense of using different subsets of their utxo set as "different participants", which reduces to multiple isolated wallets effectively. The basic proposal completely removes the possibility of offering the same utxo from 2 different maker bots, and thus gaining a probabilistic economic advantage.
To summarize the first response, it's questionable how much of an attack it is (fungibility of proposed U), and I don't see an alternative to impose cost on requests (which is definitely necessary). I for sure agree it is not perfect! |
@chris-belcher re:
I guess that is something I was just tacitly assuming; via #650 (or whatever), I couldn't see why it should be such a big deal, especially if we totally ignore an attempt to P2P it. It's not hard to either (a) set up an IRC server for the specific function, with throttling turned way down but other simple anti-DOS intact, or even just write a small tcp server. The functionality required is about as simple as it gets. The only thing that gives me pause is it's a little more difficult given that it must be Tor enabled. But even if I wouldn't be able to knock that together in 1 day, there are other people who surely could. |
The attack I was thinking of was being most or all of the Makers in a transaction. Assuming Sybil attacker has thousands of bots. Steps:
Now that I think about it the attacker could do this with !sig anyway. They always respond to !fill messages and then examine the !tx and see how many of their bots are included and then selectively send or not send !sig until they get a !tx with many of their bots included. Sending the !fill messages in serial would mean that the attacker would have to use some of their UTXOs which would be an improvement but wouldn't totally prevent the selective !sig method. |
Edit: This comment moved to new issue #724 |
@eduard6 (sorry for delayed response)
I realise this doesn't directly answer your question, but I think a tangent might be worthwhile at the start: This is the most fundamental critique of Joinmarket, and it applies outside of this issue specifically. In fact, some people pretty much immediately dismiss Joinmarket (at least in current design) because of it. @chris-belcher , I and others who were here from the start did not consider it a valid reason to reject the design (with anonymous participants making a market), because of a certain perspective: coinjoin is an opportunistic attempt to improve fungibility, which can't make it worse; attacking through Sybil only fully works when being all other participants; more than one actor trying to Sybil degrades the value of the attack to each attacker; random choice among participants means only a small number of honest counterparties stops the attack from working (if not 100%). You get the general idea. (Another thing that often crops up is "doesn't Coinshuffle fix this"? The answer is no, it doesn't. Coinshuffle prevents one party from gaining full knowledge of mappings, what it doesn't (and can't) do is prevent Sybil attacks where all counterparties are the attacker; in that case cryptography cannot help, it is just a process of elimination to find the "victim") Another aspect of the general Sybil issue is counterparty selection. The more deterministic the selection process is, the more an attacker can try to game the system to swamp honest participants. The basic approach to defending that is IMO just randomization; the current default weighted_order_choose is random, but heavily weighted by price. The paper that was written on Joinmarket argued that swamping the orderbook with cheap prices gives the attacker an opportunity to exploit this, but I don't consider it a big deal, not only because honest counterparties can also be cheap, but more importantly because we could have Takers be much more price insensitive: e.g., "random under a maximum". Although I haven't got round to doing it, it is very easy to code (and doesn't require consensus) to do this.
In this case completion-with-subset allows the Taker to complete anyway, he doesn't need to timeout (and with default settings, won't). I think complete-with-subset is pretty important, btw Coinshuffle has to go through a bunch of steps specifically to allow this (put another way, to prevent this DOS attack); for our "taker" concept, it's easy (ignoring some details).
This is indeed viable, but: with the defence described in this thread, the Taker will reject repeated utxos in the reveal in !ioauth, if there are repeats. Of course this doesn't prevent the general "swamp the orderbook" issue, but that's discussed at length above, not really to do with the defence against "copy" bots being discussed in this thread. |
This maybe seems like maybe an obvious insight, but why do the commitments have to use podle at all? Could makers just publish BTW I wrote this summary a few months ago here: https://www.reddit.com/r/joinmarket/comments/5wyfju/wallet_duplication_by_makers/ Everyone probably has already seen it but it's good to cross-link reddit/github both ways. |
Sometimes on the orderbook you see a few different makers all with the same minsize and maxsize. What's probably happening is somebody is running more than one instance of yield generator from the same joinmarket wallet. This increases their profits slightly at the expense of de-legitimizing the system because if a taker coinjoins with all those makers who are controlled by the same person, they can be spied on.
The taker code assumes every IRC nick is a different entity so treats them separately. This is a mistake because IRC nicks are free to produce.
The text was updated successfully, but these errors were encountered: