From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 995BEC5D for ; Fri, 26 Jul 2019 08:10:21 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f48.google.com (mail-wr1-f48.google.com [209.85.221.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2A052896 for ; Fri, 26 Jul 2019 08:10:19 +0000 (UTC) Received: by mail-wr1-f48.google.com with SMTP id r1so53410146wrl.7 for ; Fri, 26 Jul 2019 01:10:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:mime-version:subject:date:references:to:in-reply-to:message-id; bh=B83VgRdNcxDJ9Xx/DCJ+17aKiQRQTzBVOF6R/CmiW6Q=; b=KZPYTo0DIRYr3S3qk3ijXj1VGl+H9WKrwt4diIcu38obv4L85owRD3gJMQhsRRF8zu xaBxeJf7dFTwoBuJedIv6U/SS9Dsk+L35a95YkbHLPXKefVbppzTptz2Dyo+agxU/ZTr 0Be20JVNm9keCcH54LitueTff4ZDOoHCTHBhTi6W+CJxdfVIFTr3beKBsLodj4/J8qhS sm1W943XeHwXLaBi+UEkzEA867vlm2PA8okUFkRGFG0rGZ9venvBOA49uqaFelsJRP0B Zn8qay3gMfAk3iFjtE/wD0sysEdYVr/XS1X7X5s/bucOs/itBgGbSmD+V5zVFFI8Nroo BdHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:mime-version:subject:date:references:to :in-reply-to:message-id; bh=B83VgRdNcxDJ9Xx/DCJ+17aKiQRQTzBVOF6R/CmiW6Q=; b=FVigWdoNq6DMVZm5VFP5qh+LMvgGEOvNvBkpQ+tE+guZZ0D5C4GtxaPjoWEnpo+Qij Q7d1xv/PBCtD2R/gSTcCVH2+GFroojodOniuZBSUpvUEDR5Uxxv298oCxJvq4FXvTEz9 J5ab7TEqKQ+lQyKnxdVHGJx0xWIXpq8xTUbkm0FElcj3fitaYsqWIo4XBmei9lltczsF IEhBa1Yi+Si6u8cT6vmfw5QhsC84hzksdy64lIorffr7iTuWK0Omwk7LupV7Hme99Tgm gaVe/G5UNmpSk2dbSmYKdH6I8vO1KoeoDv0J7YCgYckHszzLPumEPu5UnskUTRbhrvlR IOAw== X-Gm-Message-State: APjAAAVeZqGan6w9nhQwOxNbSgrCvh6atZLaNe8LKmB7bupPHw4v8d/S vmlAIi8Wo52JMVlAj8K2P3cyH6EY X-Google-Smtp-Source: APXvYqyf0tnKjFbwjj/mSWuiLwD/QAFqyS52GiqaQR+PVJ2TVvqyr652lsMtRdGOFPBppPX1DyYvbA== X-Received: by 2002:adf:dcc2:: with SMTP id x2mr87084776wrm.55.1564128617568; Fri, 26 Jul 2019 01:10:17 -0700 (PDT) Received: from p200300dd67126497fc64860aba0ec4ab.dip0.t-ipconnect.de (p200300DD67126497FC64860ABA0EC4AB.dip0.t-ipconnect.de. [2003:dd:6712:6497:fc64:860a:ba0e:c4ab]) by smtp.gmail.com with ESMTPSA id o6sm102414567wra.27.2019.07.26.01.10.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 26 Jul 2019 01:10:16 -0700 (PDT) From: Tamas Blummer 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 , Bitcoin Protocol Discussion In-Reply-To: <985792b1-e7aa-677b-a7a1-6a5f672da884@riseup.net> Message-Id: <94534006-D560-4C90-9D5D-A3A64B698518@gmail.com> X-Mailer: Apple Mail (2.3273) X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 26 Jul 2019 09:02:45 +0000 Subject: Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 26 Jul 2019 08:10:21 -0000 --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 = 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--