Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

From: Adam Gibson <ekaggata@gmail•com>
To: Chris Belcher <belcher@riseup•net>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds
Date: Fri, 2 Aug 2019 15:24:11 +0100	[thread overview]
Message-ID: <CAN2_kKQGOoFz6tfrO7s9ULS61R5Hs+KVwFcShXXvSikFuSrirA@mail.gmail.com> (raw)
In-Reply-To: <985792b1-e7aa-677b-a7a1-6a5f672da884@riseup.net>

[-- Attachment #1: Type: text/plain, Size: 16888 bytes --]

reposted due to wrong email address:

I'd just like to repeat something I said years ago but is undoubtedly lost
now:

>
> ### 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.
>

I criticised this point from the Moser paper at the time, in particular
because it was the headline grabbing result and in my opinion was only half
the truth, at best:

The $32K figure came from the assumption that swamping the bottom of the
order book (in other words, making lots of bots offering prices lower than
all the other bots) would lead to taking most of the join volume.

At the time, this was true and false to some extent: it was true that the
default order choosing algorithm was exponentially weighted to lower fees.
But it was also true even then that Takers could simply manually choose any
counterparty bots they liked (-P).

Also at the time I complained that it was trivial to implement other order
choosing algorithms, in particular I advocated (for its simplicity) "choose
randomly under a user specified maximum fee", and indeed since the paper we
have implemented that algorithm and it's now the default.

Note that this algorithm is the crudest variant of what was loosely called
"quantization" in this discussion between belcher and gmaxwell on the topic
some years ago:

https://github.com/JoinMarket-Org/joinmarket/issues/14#issuecomment-143509788

To me the crucial point is that the Taker's price sensitivity should not be
too large, although of course it cannot be zero!

So independent of changes in the makeup of the users of Joinmarket, that
analysis from 2016 was in my opinion a bit skewed at the time, and
completely wrong today.

None of this is a critique of the fidelity bonds idea, since the Sybil
threat is real in any case (see issue 693 as mentioned), but price-based
Sybilling is less effective than it seems based on that.

I'll continue my thoughts on fidelity bonds, for what they're worth, in the
active thread:
https://github.com/JoinMarket-Org/joinmarket-clientserver/issues/371

(for those not in the know, Joinmarket-Org/joinmarket-clientserver is the
active repo, not Joinmarket-Org/joinmarket).

Adam Gibson / waxwing / AdamISZ

On Thu, Jul 25, 2019 at 3:18 PM Chris Belcher via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> 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
>

[-- Attachment #2: Type: text/html, Size: 19295 bytes --]