Bad faith taker spy not filling orders so that it learns which UTXOs belong to which maker, allowing future unmixing

[chris-belcher]

Here is a way a malicious taker could unmix every coinjoin.

• Sit in the marketplace and partially-fill every order with the maximum amount. Stop responding once it learns the UTXOs that belong to each maker.
• Every time a broadcast tx containing a UTXO is seen, repeat the process to get everyone's UTXOs again.
• Use the knowledge to unmix every coinjoin.

Essentially this works by breaking the assumption that the taker cares about privacy.

Firstly this does nothing for passive observers of the blockchain.

It would be quite easy to detect this and raise the alarm. Look out for repeated unfilled orders for coinjoin amounts equal to your maxsize.

There could even be decoy bots which announce a large fee that no rational taker would fill, but that the spy taker would have to partially fill.

It could be defeated by radially changing the protocol to involve something like coinshuffle which would result in no single party knowing the mapping between inputs and outputs.

A third way is to write the yield generator algorithm so that it's very hard to find all the UTXOs.

Fourth way is to use that kind of blinded signatures described by gmaxwell in the coinjoin thread on bitcointalk

[AdamISZ]

Yes.

Does Coinshuffle address it? I think not; if you're able to figure out that all-bar-1 of the join outputs are from makers, it doesn't matter what order they're in.

Just dropping the note here now, but continuing to think about it.

[AdamISZ]

Forgive me in advance if this is a bit rambling, but I want to record what I understand about it right now.

The fundamental issue is that makers announce their utxos to anyone who (pretends to) start a transaction with them; whether this can be avoided without creating hideous DOS issues I don't know.

Coinshuffle does not help, since its only purpose is to make the ownership of all the coinjoin outputs hidden from all participants (thus avoiding the current situation where there is a single coordinator, namely the taker, knowing all the linkages). This attack, to the extent that it works, sidesteps that.

Chaumian blinding does not help either. You can think of it as a lower-tech version of Coinshuffle (because, to achieve the same result, it requires the additional step of breaking the network linkage between input and output, i.e. you have to anonymously reconnect during the protocol, which is .. icky).

Possible Mitigations:

1. Punishment for non-completion: a taker who does not respond after receiving !ioauth has his btc utxo blacklisted (and remember he had to prove ownership of it in the !auth message before getting the information). This is quite harsh considering people can have connectivity problems, and also not very effective considering how easy it is to create a new utxo with a trivial transaction. But at least, it is not totally costless.
2. Proof of work and other anti-DOS: if we work on the assumption that it requires creating a lot of incomplete messages and transactions, there could be a way of at least slowing down snoopers.
3. Falling back to the earlier model of authentication: if NaCl pubkeys were persistent anti-DOS measures might be feasible and we could create levels of trust for counterparties. This is problematic though, and could result in more friction (if you can't just come out of nowhere and start joining, the system gets a lot less attractive).

I don't think anonymity can help at all; the attacker doesn't care what your IRC nick is, only the linkages on the blockchain.

[chris-belcher]

I agree with you.

I think the only way that will work and is practical is to code makers to raise the alarm if they detect this behavior. Each UTXO has a marker on it (boolean or integer type) which describes whether it's been broadcast to the network and then not consumed. If a large majority of a maker's UTXOs get marked in this way it should raise the alarm.

I think there's enough altruism in the community that this could work despite not being financially incentivized.

[chris-belcher]

The algorithm used by yield generators has an important effect on this.

The old original yield generator just announces one relorder, the spy taker will have to fill many orders to get all the UTXOs from each mixdepth.
The algorithm I've been working on, in the new-yield-algo branch has a separate relorder for each mixdepth which makes it much easier for the spy.
I know there are other yield generator algorithms out there, this spy taker would have to analyse each one including all the closed-sourced unreleased ones. It would be enough for privacy if the spy missed just a few UTXOs.

So maybe part of the solution is a polyculture of maker algorithms ?

[cqv2]

I might have a solution for this problem. The maker would send a new empty address to the taker. The taker would have to sign the coinjoin transaction with this address and send it to the maker. Now the maker verifies it and if it's acceptable he sends his coins to his new empty address. He then would have to broadcast the coinjoin transaction as fast as possible so that a bad taker couldn't move his coins. With this protocol the bad taker would have at least to bring own coins into the system.
I know there are a few problems:
-The taker's coins can be identified by the maker because these are the coins that don't move instantly before the coinjoin.
-The taker could quickly move his coins.
-The procedure is more complex, slower and requires more tx fees.
-The makers have to trust each other because they all have to move their coins at the same time (to the exposed addresses).

This is not a finished solution but it could be developed further or be used to give new ideas.

[AdamISZ]

@cqv2
I'm struggling to understand your idea.
[This paragraph prob. not needed, but just to flesh out discussion]
The attack being discussed here consists of the taker stopping after he receives the !ioauth message from the maker, which contains the maker's proposed utxos (this is under E2E encryption of course), and not responding with a proposed transaction for signing. See encryption_protocol.txt for the sequence of messages that the two sides send (if you haven't already).

If I understood your idea correctly, I have a feeling it doesn't work. When someone wants to sniff out the linkages, they will just have to traverse back one step. Say maker has utxo U1, taker proposes and he pledges to send U1 -> U2 (this will be a 1in 1out tx). In later analysis, the linkage U1-U2 can be seen directly on the blockchain and so U1 is always recoverable, even if U2 varies per taker.

Problems with complexity, time, cost etc: agreed, but maybe the above point means it doesn't achieve much (again if I understood!).

[cqv2]

I understand the problem. I somehow initiated this discussion on reddit.
My suggestion was not to prevent the back-tracing of finished coinjoins but to prevent takers from asking out the makers for UTXOs. It would bring the maker in the position of broadcasting the transaction.

[AdamISZ]

The taker needs a utxo, not just an input address to construct a transaction.

(Another comment that may or may not be important: which maker?)

Also bear in mind one of the ideas of the handshake is to reduce complete faking on both side by requiring btc signatures with the addresses corresponding to the utxos that are proposed to be used for the transaction. If the maker doesn't have to provide the utxo, that breaks that property. As I said above "whether this can be avoided without creating hideous DOS issues I don't know."

[cqv2]

You are right, this doesn't work. I was missing the point that you need the utxo to sign a valid transaction.

[bulldozer2003]

What if the takers signed transactions with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY SIGHASH_ALL|SIGHASH_ANYONECANPAY. This requires them to sign their inputs and all the outputs. The maker can then add and sign their own inputs and broadcast the transaction.

Of course, this breaks the handshake as @AdamISZ commented.

Perhaps a middle ground can be reached; makers can create and sign transactions the same way. Clients can then configure their scripts to either offer a TX to a maker, or wait for a maker to offer up a TX to them. Fee structures could reflect this with lower or higher fees respectively.

[dcousens]

As a taker, all you care about is that all the outputs match some pre-agreed amount, split over N txOuts, and that a particular amount goes to somewhere you control.

My inputs are my inputs, so I'll sign them, and only them, and the outputs must be what I expect.
Looks like: SIGHASH_ALL|SIGHASH_ANYONECANPAY to me.
I have a decent cheat sheet for the SIGHASH templates if anyone is interested.

In principle, maybe the handshake helps, but, it doesn't really aid in privacy at all.
Proving the UTXO is only useful in avoiding fake makers, but, in the end, they could just refuse to sign the actual transaction.

[AdamISZ]

This description is a summary of some ideas discussed on IRC over the last week:

https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8P

@dcousens

In principle, maybe the handshake helps, but, it doesn't really aid in privacy at all.

(Assuming you're referring to the exchange in !fill - !pubkey - !auth - !ioauth (come to think of it, I should be clearer what I mean when I say 'handshake')): what's in place is designed to prevent MITM, so it's very relevant to privacy. And of course, the fact that it provides encryption. So basically I'm disagreeing and saying: it massively helps privacy by preventing non-participants from knowing what's going on. The hard part is how to gain privacy from, effectively, Sybil attacks, fake participants.

[dcousens]

Not seeing https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8P (Page not found)

[chris-belcher]

An issue with the SIGHASH methods is they would make joinmarket transactions stand out more compared to regular bitcoin transactions. But otherwise that could probably solve the problem.

[AdamISZ]

Apologies; https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8

[AdamISZ]

@dcousens I vaguely remember earlier discussions of SIGHASH flags, but I somehow don't remember if this specific idea was discussed. It's a good idea, thanks, but just trying to get clear the mechanics:

• taker pre-prepares the tx based on amounts: fixes outputs and reserves locations for his inputs
• taker sends this "inputs blanked" tx to makers, and tells them reserved spaces for their inputs (hmm)
• makers append inputs and sigs for their inputs, with _ALL|_ANYONECANPAY
• makers send these inputs and sigs to taker
• taker does the same for his inputs and pushtx()

In that sequence taker sees everything at the end because he's going to pushtx(). (Our recent spammer was mainly following this: do everything except pushtx).

Have I missed something (probably!) or isn't it the case that if taker pushes, taker must know all the maker's inputs (distinctly, because he reserved locations for their inputs)?
If pushtx() isn't necessarily done by taker, that's another thing.

[bulldozer2003]

@AdamISZ The goal of ALL|ACP is that once a transaction is offered, it cannot be backed out of, short of spending the UTXO immediately

As a taker:

1. Find maker with acceptable min, max, and fee
2. Ask maker for outputs
3. Create TX with my inputs, my outputs, AND maker outputs and sign with ALL|ACP
4. Send TX to maker
5. Maker verifies outputs, adds inputs, signs and broadcast the TX

• The taker cannot back out after step 4.

As a maker:

1. Sees a taker willing to pay an acceptable fee.
2. Ask taker for outputs.
3. Create TX with my inputs, my outputs, AND taker outpurts
4. Send TX to taker
5. Taker verifies outputs, adds inputs, signs, and broadcasts TX.

• Maker cannot back out after step 4.

I imagine that the party giving up their privacy first by sending their UTXOs should profit with lower/higher fees respectively.

The downside is that allowing both parties to offer TXs is either party can now be a spy: A taker advertising high fees just to get maker UTXOs and a maker offering low fees just to see taker UTXOs. This could possibly be combated during a tumble by switching between offering and accepting TX.

@chris-belcher mentioned these transactions will stand out by using exotic SIGHASH, and he is correct. Not sure if there is a way around that, but I don't know if there is any plausible deniability when doing coinjoin to begin with. Only a mixer can sever the link between coins.

[AdamISZ]

@bulldozer2003

Some fundamentals here: the taker pays, and he pays for two things: (1) the fact that no other counterparty knows the mapping (2) he gets to initiate the transaction he wants immediately, and not wait.

The second of the two scenarios you describe doesn't fit in Joinmarket because of that.

The first doesn't work as cleanly as you describe, because there is more than 1 maker. As described, it just flips the problem around (as you say), where the maker gets to learn the taker's inputs before committing to actually doing the transaction. But the reality is even worse, because JM is basically always > 1 maker (with only 1 counterparty, you by definition can't hide your output from the counterparty; not useless, but nearly so).

I suspect there are (much!) more complex variants involving passing the transaction around and obfuscating which inputs belong to who, but the pushtx() counterparty will always at least have the list of inputs and know which of them are not his. Even if such things worked I'd be reluctant; part of our model is that the taker is the one in control and knows the mapping, and the makers learn as little as possible.

[dcousens]

@chris-belcher to be fair, CoinJoin transactions already stand out.

I imagine that the party giving up their privacy first by sending their UTXOs should profit with lower/higher fees respectively.

This was exactly my thought.

Even if such things worked I'd be reluctant; part of our model is that the taker is the one in control and knows the mapping, and the makers learn as little as possible.

1. Taker asks N makers for some number of output values, where the sum of the output values is equal to T.
2. Taker creates transaction with outputs equating to total T, sends that to makers.
3. Makers sign their inputs and the outputs, sending back the signed UTXO. (leaving the maker/UTXO relationships unknown)
4. Taker adds signatures and broadcasts.

This does expose the makers privacy.
Perhaps a contract could be set up (equal to the twice the makers fee) which can be ransomed if the taker doesn't end up broadcasting the transaction? (not sure how that would work).
Or at least some kind of DOS prevention mechanism where it costs you to determine a makers UTXO.

Somehow I feel like this is what happens currently? (Soon to re-iterate learning the protocol)

[AdamISZ]

I imagine that the party giving up their privacy first by sending their UTXOs should profit with lower/higher fees respectively.

That is true today; the maker gives the utxos first (except for the taker giving one pubkey, which is effectively giving a utxo).

But I would argue that the order is not as important as it first appears, because if both sides have to give that information to the other, then there is the potential for both sides to fake and therefore snoop. Also please don't forget this is a 1-many relationship, that's part of the asymmetry. Takers learn the whole transaction mapping. Makers know only their own inputs/outputs and 1 taker input.

@dcousens

Yes, your 1-4 is along the lines of what happens currently. Except for (3), which could be impacted by SIGHASH flags, but at the end each maker is going to send their own set of inputs to the taker (in this model), and so the taker will know everything and can simply not pushtx() to snoop.

Re: adding costs/contracts, yes that's what's discussed here and in that gist.

(For the protocol sequence, I know it's easy to forget, I recommend my poorly formatted encryption_protocol.txt file (the only part it doesn't have is the content of !tx and !sig messages but that's pretty obvious). I always find myself going back to that when i forget the sequence of messages and what fields are in them.)

[dcousens]

but at the end each maker is going to send their own set of inputs to the taker (in this model), and so the taker will know everything and can simply not pushtx() to snoop.

Is that not the case currently?

[Giszmo]

@AdamISZ said

I suspect there are (much!) more complex variants involving passing the transaction around and obfuscating which inputs belong to who, but the pushtx() counterparty will always at least have the list of inputs and know which of them are not his. Even if such things worked I'd be reluctant; part of our model is that the taker is the one in control and knows the mapping, and the makers learn as little as possible.

I would object espacially this last sentence as it's a flaw with no immediate benefit.

It wasn't stated explicitly but what if the taker had to request unsigned partial transactions from a sequence of at least n makers according to min n provided via order book? Each maker would add its part and only the last one return the full list. Each maker should be able to extend the loop by further makers, eventually making the transaction bigger. In the second loop all would add their respective signatures.

[Giszmo]

Oops. Can't edit? The makers would in both of the loops contribute their part encrypted for the taker but in random order.

Ok in this model the makers can deliver garbage and nobody could know who's misbehaving.

[AdamISZ]

@dcousens

Is that not the case currently?

Yes, didn't mean to imply otherwise, trying to say that it doesn't change it.

[dcousens]

Makers will soon ban those 10btc UTXOs because the spy taker is not completing the joinmarket protocol coinjoins.

Couldn't you just then mix those UTXO's after the ban period... wait 10 minutes... and try again?

[chris-belcher]

That would still add a cost to the spy. It would mean they can only do one probe every block (and it would cost them miner fees)
I guess we could also code the makers to require the UTXOs have a certain number of confirmations (or amount*confirmations) to further increase the cost, although then legitimate takers might have an odd user experience where they cant spend a coin even though its confirmed as normal.
A third option could be to have the makers analyse the blockchain and check if a new UTXO is trivially linked to an older banned one. Though that would mean makers would have to run with -txindex=1 and cant prune the blockchain.

[chris-belcher]

Plus remember that one probing isn't enough to see all the maker's UTXOs because they are in different mixdepths. And depending on the algorithm it wont be trivial to actually get the maker to send you his UTXOs.

[AdamISZ]

"UTXO commitments" (which I think we shouldn't use as a term, as it refers to something else in Bitcoin) is what we discussed at length in various forms in ~ December, you probably remember the gist. That list of 3 ideas isn't exhaustive, no doubt.

All involve a protocol update as we've said. @chris-belcher did I miss some additional idea here?

Also, the "blacklist" PR #328 is one tentative piece of code around that, also I think I still have branch with a primitive PoDLE implementation.

And yes these ideas are just a "make it hard/expensive/slow"; indeed it could be very hard to snoop enough UTXOs to get good information, especially as the yg algos broaden out, making it really hard to get anywhere near to a "full" list of maker utxos. Is this enough of a defence in practice? Really don't know.

Arguably, for an attacker, it makes a lot more sense to try to swamp the yieldgenerators with lowball offers (although that's a different attack - trying to de-anonymize takers), although some taker-customers are always going to try to pick more randomly than the default with -P (I do), or in various other ways.

[chris-belcher]

Yes there's nothing new I've come up with in terms of technology, only some thoughts on incentives/cost.
I read the gist again yesterday, for the "committing to UTXOs" I meant defense 1# or 2#

JoinMarket itself relies on just making it hard/expensive anyway. It's mostly secured by game theory and incentives, we've always known that with a large amount of bitcoins owned you could be every maker in everyone's coinjoin.

I will try to write a short gist about how much it costs to be a spy taker like this and so whether this is a good enough defense in practice.

[AdamISZ]

we've always known that with a large amount of bitcoins owned you could be every maker in everyone's coinjoin.

Not completely true right; you can swamp the orderbook, but unless you censor the message channel, you can't stop other people taking part, and some takers might choose price insensitivity. It's not a big difference admittedly.

[chris-belcher]

So it looks like somebody is actually doing this. https://www.reddit.com/r/joinmarket/comments/4mqpre/someone_is_submitting_fake_orders_to_makers_over/

I've been thinking about running an automated bot that detects this behavior and then kicks out the spy nick. But that can be beaten easily with delays and multiple nicks.

I'm thinking the best thing to do now is to set an alert warning people not to use JoinMarket, with a link to a post explaining what's happening and what you can expect if you continue to use JoinMarket.

[bulldozer2003]

It would be a shame to scare users away from join market.

I have a thought on this. First takers must be forced to prove ownership of
a utxo in the amount they want to join. The maker verifies the utxo is
unspent and matches it with one or more utxos to be used in the join. Then
keep an internal database utxo maker taker matches. The taker utxo would be
the index; taker utxos could be matched to multiple makers.

The database would be used to only ever present the same utxo matches to
the taker. Yield generators could be given a paranoid mode where if they
spend their utxos matched previously they will never match that maker's
utxos with new utxos again.

[bulldozer2003]

Another option would be a distributed hash table of seen, verified utxos
from takers shared amongst makers. Maybe a new IRC public message. See a
utxo too many times and ignore the taker.

[chris-belcher]

I should clarify, I'm thinking only of having that alert until we create the fix to this, not forever. I'm thinking defense 2 from here https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8#defence-2-committing-to-a-utxo-in-publicplaintext-at-the-start-of-the-handshake which is similar to what @bulldozer2003 writes. It would at least add a cost to this attack, which right now happens for free.

I know it would be bad to scare users away from joinmarket but I think the scare is justified. JoinMarket provides them reduced privacy against this spy, we know about it luckily and it wouldn't be right to not raise the alarm. I saw today someone on IRC was mentioning it so the truth will out eventually whatever we do.

JoinMarket is still useful, its much better than without where everybody in the distant future can see the graph between addresses. But it has this vulnerability which we need to fix.

CoinSwap as in #335 is not vulnerable to this problem BTW.

[AdamISZ]

The PR #328 has a basic implementation of PoDLE here

Of course this was ages ago, but it might not be too hard to recreate and merge. The code already uses the libsecp256k1 binding. The hard thing is having consensus on the right way to implement the protocol update and how to decide on what rules to use to limit reuse.

[chris-belcher]

Linking to the PR #328 reminds me of the question of wallet providers. From what I see, creating a PoDLE can't be used to steal someone's coins so hardware wallets (or any wallets) could blindly create them without worry.

[chris-belcher]

I have just posted this to all forums https://gist.github.com/chris-belcher/00255ecfe1bc4984fcf7c65e25aa8b4b

A definite setback for JoinMarket. But there's no reason we can't recover from this and fix the exploit.

[jamesphillipturpin]

Another solution is to have the makers scan the blockchain for coinjoin-like UTXO's, and run a sybil attack against the snoop where sometimes they offer UTXO's that don't belong to them. A persistent snoop trying to compile all maker UTXO's would thus end up with a list off all UTXO's in the blockchain that are plausibly from coinjoins - and even some that aren't. The only way for the snoop to distinguish genuine maker UTXO's is to procede with signing a transaction that pays the coinjoin fees. But then the taker will only know maker UTXO's and will be paying to make JoinMarket happen, and makers can raise prices and the attack gets progressively more expensive.

[chris-belcher]

I saw your post on reddit. That is a very novel idea that nobody had thought of.

What would the maker do if the taker is actually genuine? Just back out of the coinjoin, but thats essentially a DOS.
Of course the taker can recover, so maybe it's worth it to trade a worse user experience for better privacy, if only for a while until we fix it properly with podle.

[jamesphillipturpin]

This has some similarity to an iterated prisoner's dilemma problem, so a
tit-for-tat or tit-for-two-tat strategy with self-determined threshold is
likely best. Makers could keep track of which UTXO's they have already
announced, and preferentially offer those up to newcomer takers with no
history, or takers with poor history. Makers could then remember and
optionally announce to other trusted makers when someone backs out of a
transaction. They can also optionally announce if they have retaliated,
whether for themselves or someone else. Retaliation would take the form of
announcing a coinjoin-like UTXO, from the blockchain but not belonging to
the maker, to a taker who previously backed out of a transaction. If the
taker signs off, the retaliating maker has no choice but to back out
because he doesn't possess the private keys to sign with. Then the
retaliation is complete. If the taker backs out again though, that is
another tally against him. Trust between makers can be inferred by
correlating maker announcements with taker behavior. Thresholds for
retaliation can be parameterized, typically with 1 or 2 violations being
necessary to trigger initial retaliation.
On Jul 5, 2016 12:45 PM, "chris-belcher" notifications@github.com wrote:

I saw your post on reddit. That is a very novel idea that nobody had
thought of.

What would the maker do if the taker is actually genuine? Just back out of
the coinjoin, but thats essentially a DOS.
Of course the taker can recover, so maybe it's worth it to trade a worse
user experience for better privacy, if only for a while until we fix it
properly with podle.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#156 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/AD1Ldwzio0iCWT_r4k0Pag5sO5AfQeS0ks5qSrRLgaJpZM4FcJLO
.

[jamesphillipturpin]

It wouldn't need to be implemented all at once. Unilateral action by makers
should be implemented first. Minimally I think this is the functionality we
need to defend against attack without hurting user experience:

1. Enable makers to remember the history of one's own dealings with the
   takers on the IRC channel, that is store a dictionary lookup {"nickname":
   [count_of_incomplete_requests, count_of_complete_transactions], ...} during
   the current session.
2. Enable makers to store a list of UTXO's disclosed but not spent during
   the current session. This would not need to be stored to the wallet
   (although that would be nice), it could just last for the duration of the
   session in RAM.
3. Enable of lookup of coinjoin-like recent UTXO's from the blockchain, for
   counter-attack.
4. nicknames would be sorted into three categories based on
   [count_of_incomplete_requests, count_of_complete_transactions]:
   A. green lighted nicknames would be those takers with a good reputation
   i. Possible Criteria: if (count_of_complete_transactions >
   count_of_incomplete_requests):
   ii. Maker behavior: Treat as usual - follow existing policies for
   selecting UTXOs.
   iii. Increment count_of_complete_transactions if taker goes through
   with transaction.
   iv. Otherwise increment count_of_incomplete_requests.
   B. amber lighted nicknames would be those takers new to the IRC with
   unknown or borderline reputation.
   i. Possible Criteria: elif: (count_of_complete_transactions >=
   int(count_of_incomplete_requests/2)):
   ii. Maker behavior: Give only low quality information. Change default
   policy to offer up UTXOs already disclosed to this or other takers.
   iii. Increment count_of_complete_transactions if taker goes through
   with transaction.
   iv. Otherwise increment count_of_incomplete_requests.
   C. red lighted nicknames would be those who are presumed to be
   uncooperative.
   i. Possible Criteria: elif (count_of_complete_transactions <
   int(count_of_incomplete_requests/2)):
   ii. Maker behavior: Counter-attack. Give erroneous information. Offer
   up UTXO's that don't even belong to maker.
   iii. Increment count_of_complete_transactions if taker calls the
   bluff. Based on past behavior of taker this is likely under 1/3 of the time.
   iv. Otherwise increment count_of_incomplete_requests.
   D. The exact criteria for categories could be parameterized and then trivially changed by users to give diverse behavior, making the community more robust.
5. More functionality could be added later if/as needed to address
   sophisticated attacks or ameliorate problems created from this defense.

Edit: Changed point 4.D because I didn't mean to send this yet.

[bulldozer2003]

You cannot really rely on nicknames because they're random by default on every run, and a spy can randomize it furthermore during a session. The only persistent IDs are UTXOs.

[jamesphillipturpin]

Newcomers wouldn't be automatically green-lighted though, but typically amber-lighted. A maker should be able to limit UTXO's disclosed to new comers and bad faith actors to one mix depth of his wallet, or equivalent. If one further capped offers to amber-lighted takers to a fraction of largest mix depth, then one could limit UTXO's disclosed to that fraction of the largest mix depth, and save the rest of the maker's UTXO's for demonstrated good faith actors. Without a public reputation system this would require takers to use the same maker a couple times each in order to protect themselves from the attack. Implementing a reputation system on top of this would mean a taker would just have to include a maker with good reputation in his first coinjoin, then that maker vouches for him and others disclose fresh UTXO's and he is protected from this attack. The red light category isn't strictly necessary, but I think it's value added because it offers up bad intelligence to the snoop, and that diminishes whatever value the attacker aims to get from snooping on JoinMarket UTXOs.

As I think about this more though I think there may be an even simpler way. Makers could just limit mix depth X of their wallet to those takers that have participated with them in at least Y coinjoins successfully.

Alternatively - and this is clever because it allows takers to verify that makers are defending against the attack as specified - makers could limit UTXO's offered to newcomers who have participated in Y coinjoins to those that satisfy ((amount+C) % M) <= Y for some integer M >= 2 and integer C<M which are announced. The "announcement" of integers M and C could just be appended to the nickname of a maker. Takers could adjust their expectations accordingly, as the value of M would involve a trade-off between security and user experience. Takers could verify that their first M coinjoins with a given maker under a given nickname involve UTXO's that satisfied ((amount+C) % M) <= Y, and even automatically reject the maker if that condition is ever not met. In case of some congestion of UTXO's from enforcing this policy, the maker can restart with a new random nick and choose a different M and C to avoid the congestion.

[chris-belcher]

1. Enable of lookup of coinjoin-like recent UTXO's from the blockchain, for
   counter-attack.

An issue with this is it breaks pruning. Makers today can run with a pruned full node.

However as a stopgap we could have one of us run a web server that scans for coinjoin UTXOs and uploads them by http to any maker who asks.

I think the podle method will be more fruitful long term.

[jamesphillipturpin]

My first reaction was to brainstorm quick fixes for a game theory solution using the existing rules of the information game implicit in an attack on JoinMarket by introducing strategy to the makers to replace the naive sharing of UTXO's, in a backwards compatible manner. After getting feedback and giving it some thought, I have concluded that all such solutions are only partial fixes - they will always leak some UTXO's to an attacker, and worse they will do so at no cost to the attacker, allowing repeat and continuous attacks to obtain a fractions of all JoinMarket UTXO's for free, while other market participants pay for any defense in the form of reduced liquidity or need for repeat coinjoins to build trust.

I concur now that a cryptographic solution to change the rules of the information game to add a cost to the attack is better. PODLE looks like an elegant solution. I gather that it won't be backwards compatible - both makers and takers will have to update their software to participate in a more secure JoinMarket. That is the only drawback I see. Is that correct?

[chris-belcher]

Yes it requires a protocol break. There are many things wrong with the current protocol so we'd like to do a protocol break for other reasons anyway. (see #171)

[AdamISZ]

Partially addressed by 0.2.0 release. Still not closing it though!