From: Chris Belcher <belcher@riseup.net>
Openpgp: preference=signencrypt
Autocrypt: addr=belcher@riseup.net; prefer-encrypt=mutual; keydata=
	mQINBFPk74oBEACzBLjd+Z5z7eimqPuObFTaJCTXP7fgZjgVwt+q94VQ2wM0ctk/Ft9w2A92
	f14T7PiHaVDjHxrcW+6sw2VI2f60T8Tjf+b4701hIybluWL8DntG9BW19bZLmjAj7zkgektl
	YNDUrlYcQq2OEHm/MGk6Ajt2RA56aRKqoz22e+4ZA89gDgamxUAadul7AETSsgqOEUDI0FKR
	FODzoH65w1ien/DLkG1f76jd0XA6AxrESJVO0JzvkTnJGElBcA37rYaMmDi4DhG2MY4u63VE
	8h6DyUXcRhmTZIAj+r+Ht+KMDiuiyQcKywCzzF/7Ui7YxqeAgjm5aPDU2E8X9Qd7cqHQzFM7
	ZCqc9P6ENAk5a0JjHw0d0knApboSvkIJUB0j1xDIS0HaRlfHM4TPdOoDgnaXb7BvDfE+0zSz
	WkvAns9oJV6uWdnz5kllVCjgB/FXO4plyFCHhXikXjm1XuQyL8xV88OqgDFXwVhKrDL9Pknu
	sTchYm3BS2b5Xq1HQqToT3I2gRGTtDzZVZV0izCefJaDp1mf49k2cokDEfw9MroEj4A0Wfht
	0J64pzlBYn/9zor5cZp/EAblLRDK6HKhSZArIiDR1RC7a6s7oTzmfn0suhKDdTzkbTAnDsPi
	Dokl58xoxz+JdYKjzVh98lpcvMPlbZ+LwIsgbdH4KZj7mVOsJwARAQABtB9DaHJpcyBCZWxj
	aGVyIDxmYWxzZUBlbWFpbC5jb20+iQI+BBMBAgAoBQJT5O+KAhsDBQkSzAMABgsJCAcDAgYV
	CAIJCgsEFgIDAQIeAQIXgAAKCRDvc06md/MRKS8jD/9P9fSYSIVjltL9brAMfIu7wJn0H0lX
	TbcuCM2uQitJ3BNxI3c7aq5dEby27u5Ud54otncDJuRPQVDKs6H7t1rInitgJ1MTQ9/aQGFA
	btKcgtVIMFbeClzTTfWr4W7fE45NI7E9EANgk5JfmWh3U+KINYLF5RtqynYocrsP6zOV+G9A
	HCpBemd9TN60CoMLMyMzTHEW1oQffaVAXY8DgthEYO/odWYIod7VTmEm0zU1aSysPqMwPWNm
	8XIl0f8SfKQyZlAU8e1eCFVCenkE44FKC5qQNYc2UxexEYtfCWChTGc4oHKxIyYmTCCefsQF
	LvgwtvlNHRXHSDKSPSNcRcpl8DFpNEKrmMlkJ8Mx+YR05CydlTQ0bI3FBohJC+UHrjD5I3hA
	wJUC1o+yVSOEd+zN3cG1EECIwkEQSmBgG5t/le2RdzfXOdpf9ku2/zoBpq00R54JxUKlfRM7
	OPTv7X+1AKHkxOySdCZwGgvdh2Whuqs4kTvtco00gCFM9fBd5oi1RJuHtxHsj8+/XU15UItb
	jeo96CIlM5YUeoRLPT5mxZYWgYAARFeSFReNq/Tuwq9d8EokUrtAyrPayznliy53UJfWDVzl
	925c0Cz0HWaP2fWj+uFcj/8K0bhptuWJQy0Poht1z3aJC1UjEgr1Xz8I7jeSJmIlA9plcJw2
	k4dhWbkCDQRT5O+KARAAyFxAM28EQwLctr0CrQhYWZfMKzAhCw+EyrUJ+/e4uiAQ4OyXifRr
	ZV6kLRul3WbTB1kpA6wgCShO0N3vw8fFG2Cs6QphVagEH8yfQUroaVxgADYOTLHMOb7INS8r
	KI/uRNmE6bXTX27oaqCEXLMycqYlufad7hr42S/T8zNh5m2vl6T/1Poj2/ormViKwAxM+8qf
	xd8FNI4UKmq2zZE9mZ5PiSIX0qRgM0yCvxV39ex/nhxzouTBvv4Lb1ntplR/bMLrHxsCzhyM
	KDgcX7ApGm+y6YEsOvzw9rRCRuJpE4lth8ShgjTtNTHfklBD6Ztymc7q7bdPWpKOEvO5lDQ6
	q8+KfENv862cOLlWLk7YR2+mHZ1PXGhWC7ggwEkfGJoXo0x8X+zgUKe2+9Jj4yEhfL0IbFYC
	z2J5d+cWVIBktI3xqkwLUZWuAbE3vgYA4h8ztR6l18NTPkiAvpNQEaL4ZRnAx22WdsQ8GlEW
	dyKZBWbLUdNcMmPfGi5FCw2nNvCyN6ktv5mTZE12EqgvpzYcuUGQPIMV9KTlSPum3NLDq8QI
	6grbG8iNNpEBxmCQOKz2/BuYApU2hwt2E44fL8e6CRK3ridcRdqpueg75my6KkOqm8nSiMEc
	/pVIHwdJ9/quiuRaeC/tZWlYPIwDWgb8ZE/g66z35WAguMQ+EwfvgAUAEQEAAYkCJQQYAQIA
	DwUCU+TvigIbDAUJEswDAAAKCRDvc06md/MRKaZwD/9OI3o3gVmst/mGx6hVQry++ht8dFWN
	IiASPBvD3E5EWbqWi6mmqSIOS6CxjU0PncxTBPCXtzxo/WzuHGQg/xtNeQ0T8b2lBScZAw93
	qm1IcHXLUe5w/Tap6YaDmSYCIZAdtbHzYfPW4JK7cmvcjvF8jhTFOBEOFVQkTi19G7caVot0
	+wL1e2DRHDXAe5CinEpaLBlwHeEu/5j6wc3erohUZlK9IbAclj4iZTQbaq3EyqUXl59dBOON
	xmL5edJxzVishIYQGIyA9WP1SylXt+kO82NEqZG2OxdXAlzjuJ8C2pAG+nbLtDo4hcsiN/MA
	aX9/JB7MXclT5ioerF4yNgKEdfq7LmynsTUd8w/Ilyp7AD+BWoujyO94i8h9eKvjf9PvSwxQ
	uAjRpxne7ZJD8vCsMNXBHSbeEK2LiwStHL/w473viXpDD53J6OLxX6a5RummR+rixbMH7dgK
	MJQ7FlyDphm3or6CSkGEir1KA0y1vqQNFtHhguFapAWMDKaJjQQNgvZUmOo6hbZqmvUF1OWc
	d6GA6j3WOUe3fDJXfbq6P9Jmxq64op887dYKsg7xjQq/7KM7wyRcqXXcbBdgvNtVDP+EnzBN
	HyYY/3ms4YIHE5JHxQ9LV4yPcWkYTvb1XpNIFVbrSXAeyGHVNT+SO6olFovbWIC3Az9yesaM
	1aSoTg==
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <985792b1-e7aa-677b-a7a1-6a5f672da884@riseup.net>
Date: Thu, 25 Jul 2019 12:47:54 +0100
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Subject: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks
 using fidelity bonds
Precedence: list

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