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 8B7F4EB7 for ; Thu, 25 Jul 2019 11:56:47 +0000 (UTC) X-Greylist: delayed 00:08:50 by SQLgrey-1.7.6 Received: from mx1.riseup.net (mx1.riseup.net [198.252.153.129]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 687D18AC for ; Thu, 25 Jul 2019 11:56:46 +0000 (UTC) Received: from capuchin.riseup.net (capuchin-pn.riseup.net [10.0.1.176]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (Client CN "*.riseup.net", Issuer "COMODO RSA Domain Validation Secure Server CA" (verified OK)) by mx1.riseup.net (Postfix) with ESMTPS id 7E0251A1E67 for ; Thu, 25 Jul 2019 04:47:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=riseup.net; s=squak; t=1564055276; bh=XygFZHheUNIpeB6EYJeS64VqeFpORG7sQ4ljQUA4YOs=; h=From:Subject:To:Date:From; b=Z4eSx3fQSsUKNHc42ZwxRsA37ON0jOqPIaJmA3HOBVu6AKhjzGbae0COzHHHVP05S WFPM2HtugUqPJHGo49E/y/gHu2WVg8A7NYm8Jgg3MG9L+gpwZ155QRyfDv4Cs7+cDo h9VT6pKxWTqnDuPET+QxAB7b6CnI4Zy1jLwZiWYY= X-Riseup-User-ID: FDD7340B54DA4CD6776994C0CFB2C2ED4FDD6A5C30FFFF30E18D5D48259C9E5A Received: from [127.0.0.1] (localhost [127.0.0.1]) by capuchin.riseup.net (Postfix) with ESMTPSA id CEE6A120967 for ; Thu, 25 Jul 2019 04:47:55 -0700 (PDT) From: Chris Belcher 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 X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_LOW 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: Thu, 25 Jul 2019 14:17:47 +0000 Subject: [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: Thu, 25 Jul 2019 11:56:47 -0000 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