From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id C4088C016E for ; Sun, 28 Jun 2020 12:16:35 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 94B5C20432 for ; Sun, 28 Jun 2020 12:16:35 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gq0GiRalJFXr for ; Sun, 28 Jun 2020 12:16:33 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from newmail.dtrt.org (li1228-87.members.linode.com [45.79.129.87]) by silver.osuosl.org (Postfix) with ESMTPS id 6858B20417 for ; Sun, 28 Jun 2020 12:16:33 +0000 (UTC) Received: from harding by newmail.dtrt.org with local (Exim 4.92) (envelope-from ) id 1jpWEZ-0002bq-95; Sun, 28 Jun 2020 08:16:31 -0400 Date: Sun, 28 Jun 2020 08:15:17 -0400 From: "David A. Harding" To: Stanga , Bitcoin Protocol Discussion Message-ID: <20200628121517.f3l2mjcy7x4566v3@ganymede> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="r7ohapeyprb3ykk3" Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20180716 Cc: Matan Yehieli , Itay Tsabary Subject: Re: [bitcoin-dev] MAD-HTLC X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 28 Jun 2020 12:16:35 -0000 --r7ohapeyprb3ykk3 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Jun 23, 2020 at 09:41:56AM +0300, Stanga via bitcoin-dev wrote: > Hi all, >=20 > We'd like to bring to your attention our recent result concerning HTLC. > Here are the technical report and a short post outlining the main points: >=20 > * https://arxiv.org/abs/2006.12031 > * https://ittayeyal.github.io/2020-06-22-mad-htlc Thank you for your interesting research! Further quotes are from your paper: > Myopic Miners: This bribery attack relies on all miners > being rational, hence considering their utility at game conclu- > sion instead of myopically optimizing for the next block. If > a portion of the miners are myopic and any of them gets to > create a block during the first T =E2=88=92 1 rounds, that miner would > include Alice=E2=80=99s transaction and Bob=E2=80=99s bribery attempt wou= ld > have failed. > In such scenarios the attack succeeds only with a certain > probability =E2=80=93 only if a myopic miner does not create a block > in the first T =E2=88=92 1 rounds. The success probability therefore > decreases exponentially in T . Hence, to incentivize miners > to support the attack, Bob has to increase his offered bribe > exponentially in T . This is a good abstract description, but I think it might be useful for readers of this list who are wondering about the impact of this attack to put it in concrete terms. I'm bad at statistics, but I think the probability of bribery failing (even if Bob offers a bribe with an appropriately high feerate) is 1-exp(-b*h) where `b` is the number of blocks until timeout and `h` is a percentage of the hashrate controlled by so-called myopic miners. Given that, here's a table of attack failure probabilities: "Myopic" hashrate B 1% 10% 33% 50% l +--------------------------------- o 6 | 5.82% 45.12% 86.19% 95.02% c 36 | 30.23% 97.27% 100.00% 100.00% k 144 | 76.31% 100.00% 100.00% 100.00% s 288 | 94.39% 100.00% 100.00% 100.00% So, if I understand correctly, even a small amount of "myopic" hashrate and long timeouts---or modest amounts of hashrate and short timeouts---makes this attack unlikely to succeed (and, even in the cases where it does succeed, Bob will have to offer a very large bribe to compensate "rational" miners for their high chance of losing out on gaining any transaction fees). Additionally, I think there's the problem of measuring the distribution of "myopic" hashrate versus "rational" hashrate. "Rational" miners need to do this in order to ensure they only accept Bob's timelocked bribe if it pays a sufficiently high fee. However, different miners who try to track what bribes were relayed versus what transactions got mined may come to different conclusions about the relative hashrate of "myopic" miners, leading some of them to require higher bribes, which may lead those those who estimated a lower relative hash rate to assume the rate of "myopic" mining in increasing, producing a feedback loop that makes other miners think the rate of "myopic" miners is increasing. (And that assumes none of the miners is deliberately juking the stats to mislead its competitors into leaving money on the table.) By comparison, "myopic" miners don't need to know anything special about the past. They can just take the UTXO set, block height, difficulty target, and last header hash and mine whatever available transactions will give them the greatest next-block revenue. In conclusion, I think:=20 1. Given that all known Bitcoin miners today are "myopic", there's no short-term issue (to be clear, you didn't claim there was). 2. A very large percentage of the hashrate would have to implement "rational" mining for the attack to become particularly effective. Hopefully, we'd learn about this as it was happening and could adapt before it became an issue. 3. So-called rational mining is probably a lot harder to implement effectively than just 150 loc in Python; it probably requires a lot more careful incentive analysis than just looking at HTLCs.[1] 4. Although I can't offer a proof, my intuition says that "myopic" mining is probably very close to optimal in the current subsidy-fee regime. Optimizing transaction selection only for the next block has already proven to be quite challenging to both software and protocol developers[2] so I can't imagine how much work it would take to build something that effectively optimizes for an unbounded future. In short, I think so-called myopic mining might actually be the most rational mining we're capable of. Nevertheless, I think your results are interesting and that MAD-HTLC is a useful tool that might be particularly desirable in contracts that involve especially high value or especially short timeouts (perhaps asset swaps or payment channels used by traders?). Thank you again for posting! -Dave [1] For example, your paper says "[...] the bribing cost required to attack HTLC is independent in T, meaning that simply increasing the timeout does contribute to HTLC=E2=80=99s security." This implies that Alice, after she sees Bob's attempted bribe, could offer a counter bribe that spends all output value to fees (the scorched earth policy ZmnSCPxj describes) with a timelock set to the maximum single-transaction value (block 500 million, due to be mined in about 10 millennia, give or take a few centuries) and miners would hold on to it until then, never mining Bob's lower-feerate bribe. That's ridiculous, but it's understandable in your paper because you're mainly analyzing time periods so short that you don't need to worry much about the time-value-of-money discount (also mentioned by ZmnSCPxj); however, your paper also says that your Python implementation uses the same formulas in your paper to determine whether or not a bribe will profitable, which would obviously be wrong for a 10,000-year timelock. [2] See the never ending discussions on this list and Lightning-Dev about ancestor mining package size/depth limits and BIP125 opt-in RBF rule #3. --r7ohapeyprb3ykk3 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCgAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAl74idQACgkQ2dtBqWwi adNmShAAmtcTRYxjozDgv/n6j1Hlq40lrNucJOYA/abRvDKTU/dXN1RmrpslzK0X w2Piw0fI1mNRdX2MAnl8/PcBBmR4UNdg3hlZrTEDPtoJntp7trVKVwtZ47yQxaHE zs4OtGHVereNJvexFtrPxYnzahGlQX3aDqblDaTR9ghgy70MZkw/k/LOTPekjz9w KhVvjHJuFiGnD1d5FzCeJmCwQLmPW1gvqAFiO1CtP29wslUtyLhU6lJU561U34Kl UQpSUZmK1CNnHiIiutNorxwFi/mwWN7zOYozTos6rMoZco9JYoOiH+Pkgta8HkjE F/k0DrM5zZQfHPGF4amqhodhk2P+/9GdXXeeNIZuU4uR9JIML4RZ99OD16lJh1y+ 3hiwTbsVKXbgd5Ce3gz1wm1rXQazxVxTK0uNj/a7PqshdVne3gYYFKlos9nLroei sfQ4LoxsUaNiiokI0hzWiSZUMBL32z/+rUWd5cR10CMup/Nc2XvrOBBXXxTQHrwN wPQjvkB1XduUOyvQbFgRhSu4mfMJOatgZ1lZNspVT00FPJx75a/ysaPoQxKiqztF lFwaonUjt8jISThnIaopfiBP188jTVKCzYmEpHtrF9S/5IEsy/GmRAHrTeVX05oJ to+pmCrSjnmCIde+eoohMUtvhQfcQ/RwyxINvN8ZAQ3PiqPWJjo= =OplS -----END PGP SIGNATURE----- --r7ohapeyprb3ykk3--