13/7/2019
JoinMarket can be sybil attacked today at relatively low cost which can destroy its privacy. Bitcoins can be sacrificed with burner outputs and time-locked addresses (also called fidelity bonds), and this can be used to greatly improve JoinMarket's resistance to sybil attacks.
With real-world data and realistic assumptions we calculate that under such a fidelity bond system an adversary would need to lock up 30,000-80,000 bitcoins for months, or send 45-120 bitcoins to burner addresses to have a good chance of sybil attacking the system if it were added to JoinMarket.
This increased resistance to sybil attacks would most likely cause coinjoin fees to rise. I think the added cost is worth it for the greatly improved privacy, because today miner fees are the biggest cost to JoinMarket takers not coinjoin fees which are very low. Users should definitely share their opinion on fees after reading the document.
JoinMarket creates a market for coinjoins, allowing anyone to create equal-amount coinjoins for any amount they want at any time they want. In return they pay a fee for the liquidity made available to them. The project has existed since 2015 and has probably created hundreds of thousands of coinjoins since then. Today there is available liquidity for creating coinjoins with amounts up to about 400 btc per coinjoin output.
JoinMarket, like many other schemes where participants are free to anonymously enter, can be targetted by sybil attacks. In JoinMarket this would work by an attacker running lots of maker bots which attempt to be all the makers in every coinjoin. If successful the attacker would have enough information unmix every coinjoin.
One way to solve the problem of sybil attacks is centralization. For example coinjoins could be constructed on a centralized server. Then random anonymous participants cant sybil attack because they can't control the coinjoin construction, but this comes at the cost that the server can sybil attack very easily. So this solution is probably a bad tradeoff.
In general, sybil attacks are solved by making them expensive. For example, bitcoin mining resists sybil attacks because it requires a provable sacrifice of electricity to mine. A bitcoin user can calculate the actual monetary value that an attacker must spend in order to reverse their transaction.
Likewise in JoinMarket such a sybil attack is not free either as the attacker needs to own enough bitcoins to run enough maker bots for all the coinjoins.
A paper on JoinMarket [Möser, Malte and Rainer Böhme. “Join Me on a Market for Anonymity.” (2016).] calculates the requirement of such a sybil attack in 2016 to be just 32,000 USD. According to the paper such an attack would succeed 90% of the time and the investment is recoverable afterwards so that figure for the requirement isn't even a true cost.
JoinMarket has been improved since 2016 and more makers have joined, so the true requirement is perhaps 2x or 3x higher today, but it is still relatively low.
Even with future improvements like fixing issue #693 the requirement of a sybil attack would probably only rise another 2x.
Apart from the cost to sybil attack being low, there is also the odd situation that smaller coinjoin amounts receive less sybil protection than large ones. It costs 100x less to sybil attack a transaction of 0.1 btc than one of 10 btc. Why should smaller amounts receive less sybil-resistance and therefore less privacy?
When creating this project, it was expected that many more people would enter the market as makers and so the cost of a sybil attack would be very high. That has not happened. One reason is that everyone who wants to create a coinjoin is able to even for large amounts. The fundamental problem is that takers are paying-for and getting liquidity, but not necessarily sybil-resistance.
Another smaller reason for the low cost of sybil attacks is that many people don't want to store too many bitcoins on an computer connected to the internet.
What is needed is a way to increase the cost of running in a maker in a way that retains the anonymity and is attractive to long-term holders of bitcoin. This can be done using time-locked addresses.
In bitcoin, a fidelity bond is a mechanism where bitcoin value is deliberately sacrificed to make a cryptographic identity expensive to obtain. The sacrifice is done in a way that can be proven to a third party.
A way to create a fidelity bond is to burn an amount of bitcoins by sending to a OP_RETURN output. Another kind is time-locked addresses created using OP_CHECKLOCKTIMEVERIFY where the valuable thing being sacrificed is time rather than money, but the two are related because of the time-value-of-money.
Under this system, makers would sacrifice an amount of bitcoins and publish a proof along with their coinjoin offers. Takers would choose maker offers based on the sacrificed amount (as well as other factors), knowing that a sybil attacker would also have to sacrifice a certain amount of coins in order to unmix the taker's coinjoins. The sacrifice would be an objective measurement that can't be faked and which can be verified by anybody (just like, for example PoW mining)
Note that a long-term holder (or hodler) of bitcoins can buy time-locked fidelity bonds essentially for free, assuming they never intended to transact with their coins much anyway. A long-term holder probably won't want to attack a system like JoinMarket which makes his own investment coins more private and more fungible.
The private keys of fidelity bonds can be kept offline. Signatures potentially only need to be made when the timelock expires (every 6 months for example), or only once in the case of OP_RETURN burned coins. This allows JoinMarket's sybil resistance to increase without the hot wallet risk.
Burned coin signatures should still have a lifetime, in case the private key associated with the IRC nick (which is online) is stolen, so that the thief of that privkey can't impersonate the maker indefinitely. The signature linking the burned coins and IRC nick could expire after perhaps 6 months.
Under this scheme makers would need to publish the transactions of their fidelity bonds to the entire world. Those transactions could be subject to blockchain analysis. So before makers do this they should make sure their coins are anonymous (possibly by mixing with JoinMarket). Also if they ever want to use their coins for something else apart from fidelity bonds they should mix them.
See the other document Financial mathematics of joinmarket fidelity bonds for a formula expressing the value of a fidelity bond.
The value of a fidelity bond made by sending V bitcoins to a burner address is:
V^2
The amount of bitcoins is squared to get the fidelity bond value. This has the effect that economic-rational makers have a strong incentive to lump up all their coin sacrifices together into one maker bot, not to split it up over several bots.
The value of a fidelity bond made by locking up V bitcoins in a time-locked address for time period T is:
V^2 (exp(rT) - 1)^2
To get an idea of the numbers, if we burn 2 btc then the value of the fidelity bond is 4 BTC^2. If we lock up 100 BTC for one year, and have a bitcoin interest rate r = 0.001 (0.1%) per year, then the value of that fidelity bond is 0.01 BTC^2 which is the same as burning 0.1 BTC. That is a relatively small valued bond. It can be increased by locking up more bitcoins for longer (up to and including permanant locking via a burner transaction).
I suggest the following taker peer choosing algorithm: obtain the list of offers and discard offers which the taker's user deems are too expensive. One of the remaining offers is randomly chosen with weighting determined by the fidelity bond value. Once an offer is chosen it is removed from the list, and another offer is again randomly chosen, this is repeated until the taker has chosen the desired number of fidelity-bonded maker's offers.
Some people run makers not for profit but for their own privacy. Therefore not all makers should be required to have bonds, because such privacy-makers are useful to include in coinjoins too. We could have taker allow say, an eighth (12.5%), of their coinjoin peers to be makers without bonds. They can be chosen randomly from the orderbook without any weighting based on fidelity bond values. Of course these are easy to fake by an adversary so they dont contribute much to sybil resistance.
See the other document Cost of sybil attacks for discussion and calculations on the sybil resistance given by the above maker-choosing algorithm.
It can be calculated that the fidelity bond system dramatically increases the cost of a sybil attack. With real-world data and realistic assumptions we can calculate that a sybil attacker would need to lock up 30,000-80,000 bitcoins for 6 months, or send 45-120 bitcoins to burner addresses to have a good chance of attacking the system by being all the counterparties in everyone's coinjoin.
Someone might ask "why would anyone lock up coins for months or more, let alone burn coins forever, just to run a maker bot". The only way this would even happen is if makers can generate a higher income that justifies the fidelity bond sacrifice. That higher income can only come from taker's coinjoin fees (or possibly coinswap fees one day). We can expect that makers with higher valued fidelity bonds will demand higher coinjoin fees. So a big question is whether takers will accept paying higher coinjoin fees. I think they will, because right now coinjoin fees are only 10-1000 satoshi, and a far biggest cost of coinjoins is the miner fee not the coinjoin fee. I'm pretty sure takers will recognize that they get what they pay for, and that additional privacy is well worth the cost. Any other takers reading this should definitely let me know what they think.
See the other document Using CAPM model to figure out how much fees have to rise for a certain sacrifice to see how much fees would have to rise by.
JoinMarket's wallet could also create time-locked addresses. Locktimes should be fixed to be midnight on the first day of each month, then each public key corresponds to 12 addresses per year (1200 addresses per century) which is very practical to all be monitored as watch-only addresses. These wallets can be created offline and could safely hold time-locked bitcoins.
The timelocked addresses public key can be used to sign an IRC nickname proving that the nickname is the real owner of the TXO. OP_RETURN outputs used for burning coins can include a pubkey hash used for the same thing.
We don't want the cold storage keypairs to be held online. We can design the system that the time-locked address keypair is held offline but it signs another key pair which is held online. Every time the IRC bot connects it can use this intermediate keypair to sign the IRC nickname proving ownership. The signature from the time-locked address to the intermediate keypair can be made to have an expiry date (for example 6 months). This all means that the time-locked bitcoins can be held offline but still be used to prove ownership of an IRC nickname.
The existance of the UTXO of a time-locked coin can be proved by revealing the TXID and vout, which full nodes can use to query the UTXO set to check that the coin exists. SPV clients would need a merkle proof as well. Burned coins and spent time-locked coins could have their existence proved by sharing the transaction which created them along with a block height and transaction position for an unpruned node, or a merkle proof for a pruned node or SPV client. Note that from the point of view of a pruned node, a merkle proof is a fully-verified proof of existance of a transaction. It is not a proof with just SPV-security.
- First ever mention of fidelity bonds I found. The idea is basically invented by Peter Todd: https://bitcointalk.org/index.php?topic=134827.0
- Old idea for combining fidelity bonds with mixers: https://bitcointalk.org/index.php?topic=172047.0
- Suggestion that is very close to the fidelity bonds idea. He talks about requiring a deposit from makers, but nobody is able to come up with a way to make such a deposit decentralized and trustless: https://www.reddit.com/r/Bitcoin/comments/2zc5tc/joinmarket_increase_the_privacy_of_bitcoin_and/ctk37hn/?context=1
Just to add that here's another guy admitting to running multiple yield generators: https://www.reddit.com/r/joinmarket/comments/cyqb6a/failed_to_get_change_address/