From: Tamas Blummer <tamas.blummer@gmail.com>
Content-Type: multipart/signed;
	boundary="Apple-Mail=_A9890106-C485-45F8-B3F0-CB248D3342D5";
	protocol="application/pgp-signature"; micalg=pgp-sha512
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Fri, 26 Jul 2019 10:10:15 +0200
References: <985792b1-e7aa-677b-a7a1-6a5f672da884@riseup.net>
To: Chris Belcher <belcher@riseup.net>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <985792b1-e7aa-677b-a7a1-6a5f672da884@riseup.net>
Message-Id: <94534006-D560-4C90-9D5D-A3A64B698518@gmail.com>
Subject: Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil
 attacks using fidelity bonds
Precedence: list


--Apple-Mail=_A9890106-C485-45F8-B3F0-CB248D3342D5
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

Hi Chris,

yes, fidelity bonds can impose cost to make sybill attacks more =
expensive therefore less likely.
I prefer the flavor with CHECKSEQUENCEVERIFY which imposes opportunity =
cost, just as effective
as burning, but is sustainable.

Imposing opportunity costs however requires larger time locked amounts =
than burning and the
user might not have sufficient funds to do so. This is however not a =
restriction but an opportunity
that can give rise to an additional market of locking UTXOs in exchange =
of a payment.

This would give rise to a transparent interest rate market for Bitcoin =
an additional huge benefit.

Regards,

Tamas Blummer

> On Jul 25, 2019, at 13:47, Chris Belcher via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> ## Introduction
>=20
> 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.
>=20
> ### Sybil attacks
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> ### Today's low cost for sybil attacks
>=20
> A paper on JoinMarket [M=C3=B6ser, Malte and Rainer B=C3=B6hme. =
=E2=80=9CJoin Me on a
> Market for Anonymity.=E2=80=9D (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.
>=20
> 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.
>=20
> Even with future improvements like fixing issue #693 [2] the =
requirement
> of a sybil attack would probably only rise another 2x.
>=20
> 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?
>=20
> ### Liquidity
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> ## Fidelity bonds
>=20
> 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.
>=20
> 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.
>=20
> 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)
>=20
> 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.
>=20
> ### Fidelity bonds in cold storage
>=20
> 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.
>=20
> 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.
>=20
> ### Anonymity
>=20
> 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.
>=20
> ### Value of a fidelity bond
>=20
> See the other document (Financial mathematics of joinmarket fidelity
> bonds)[4] for a formula expressing the value of a fidelity bond.
>=20
> The value of a fidelity bond made by sending V bitcoins to a burner
> address is:
>=20
>    V^2
>=20
> 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.
>=20
> The value of a fidelity bond made by locking up V bitcoins in a
> time-locked address for time period T is:
>=20
>    V^2 (exp(rT) - 1)^2
>=20
> 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 =3D 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).
>=20
> ## Taker algorithm for choosing makers
>=20
> 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.
>=20
> 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.
>=20
> ### Cost of sybil attacks
>=20
> See the other document (Cost of sybil attacks) for discussion and
> calculations on the sybil resistance given by the above maker-choosing
> algorithm.
>=20
> 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.
>=20
> ## Effect of fidelity bonds on CoinJoin fees
>=20
> 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.
>=20
> ## Technical ideas
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> ## 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#cos=
t-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=3D134827.0
> [7] Old idea for combining fidelity bonds with mixers:
> https://bitcointalk.org/index.php?topic=3D172047.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_p=
rivacy_of_bitcoin_and/ctk37hn/?context=3D1
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


--Apple-Mail=_A9890106-C485-45F8-B3F0-CB248D3342D5
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename=signature.asc
Content-Type: application/pgp-signature;
	name=signature.asc
Content-Description: Message signed with OpenPGP

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCgAdFiEE6YNJViYMM6Iv5f9e9nKRxRdxORwFAl06tWcACgkQ9nKRxRdx
ORwuHwf/frIN88TInKvtC0X/Hu0Ie2UhvmUFaOBppCUNOKjyCUQQTZ6WxX6bJGqN
CidurbXWaVl+lkDiobFqmTYdfXzbqbpYFEg7EJbGZun2sE2gTS62kriEuJEeQHwJ
u/uVRS4LO+NEcGqtqASQSrJbvCxJcJp3XRduSWkqX/BKCpz4rMqubx7i4Z7UweRG
Y9i7Qsg7gGVM/0U1etkmqR/ZyRJWluvtbnWfEjIGR+LShBdPdgR7MQE7CA1JICnz
p8pKUHqGQATVanOy4iO2CK8NMZ8zhpEaYnDqL078s3CfeX7TI/niZMKgWmHJmFzq
m8xbdS0xrroD46eHOnivi0o3WR/jOw==
=NhVP
-----END PGP SIGNATURE-----

--Apple-Mail=_A9890106-C485-45F8-B3F0-CB248D3342D5--