On Tue, Jun 23, 2020 at 09:41:56AM +0300, Stanga via bitcoin-dev wrote: > Hi all, > > 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: > > * 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 − 1 rounds, that miner would > include Alice’s transaction and Bob’s bribery attempt would > have failed. > In such scenarios the attack succeeds only with a certain > probability – only if a myopic miner does not create a block > in the first T − 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: 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’s 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.