JoinMarket[1] 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.

## Introduction

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.

### Sybil attacks

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.

### Today's low cost for sybil attacks

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 [2] 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?

### Liquidity

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.

## Fidelity bonds

In bitcoin, a fidelity bond [3] 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.

### Fidelity bonds in cold storage

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.

### Anonymity

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.

### Value of a fidelity bond

See the other document (Financial mathematics of joinmarket fidelity
bonds)[4] 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).

## Taker algorithm for choosing makers

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.

### Cost of sybil attacks

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.

## Effect of fidelity bonds on CoinJoin fees

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.

## Technical ideas

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.

## Links / References
[1] https://github.com/JoinMarket-Org/joinmarket-clientserver
[2] https://github.com/JoinMarket-Org/joinmarket/issues/693
[3] https://en.bitcoin.it/wiki/Fidelity_bonds
[4] https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b
[5]
https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b#cost-of-sybil-attacks
[6] First ever mention of fidelity bonds I found. The idea is basically
invented by Peter Todd: https://bitcointalk.org/index.php?topic=134827.0
[7] Old idea for combining fidelity bonds with mixers:
https://bitcointalk.org/index.php?topic=172047.0
[8] 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
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev