From: "David A. Harding" <dave@dtrt•org>
To: Stanga <stanga@gmail•com>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Cc: Matan Yehieli <matany@campus•technion.ac.il>,
Itay Tsabary <sitay@campus•technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Date: Sun, 28 Jun 2020 08:15:17 -0400 [thread overview]
Message-ID: <20200628121517.f3l2mjcy7x4566v3@ganymede> (raw)
In-Reply-To: <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 6242 bytes --]
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.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
next prev parent reply other threads:[~2020-06-28 12:16 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
2020-06-23 6:41 ` Stanga
2020-06-23 9:48 ` ZmnSCPxj
2020-06-23 12:47 ` Stanga
2020-06-23 13:18 ` Stanga
2020-06-25 1:38 ` ZmnSCPxj
2020-06-25 3:26 ` Nadav Ivgi
2020-06-25 4:04 ` ZmnSCPxj
2020-06-25 4:35 ` Nadav Ivgi
2020-06-25 13:12 ` Bastien TEINTURIER
2020-06-28 16:41 ` David A. Harding
2020-07-04 21:05 ` ZmnSCPxj
2020-06-28 12:15 ` David A. Harding [this message]
2020-06-29 11:57 ` Tejaswi Nadahalli
2020-06-29 18:05 ` ZmnSCPxj
2020-06-30 6:28 ` Stanga
2020-06-30 6:45 ` Tejaswi Nadahalli
2020-07-01 16:58 ` ZmnSCPxj
2020-07-02 12:22 ` Tejaswi Nadahalli
2020-07-02 16:06 ` ZmnSCPxj
2020-07-03 9:43 ` Tejaswi Nadahalli
2020-07-03 10:16 ` ZmnSCPxj
2020-07-03 10:44 ` Tejaswi Nadahalli
[not found] ` <CAF-fr9Z7Xo8JmwtuQ7LE3k1=er+p7s9zPjH_8MNPwbxAfT1z7Q@mail.gmail.com>
2020-07-03 12:38 ` ZmnSCPxj
[not found] ` <CAF-fr9YhiOFD4n8rGF-MBkWeZmzBWfOJz+p8ggfLuDpioVRvyQ@mail.gmail.com>
2020-07-04 20:58 ` ZmnSCPxj
2020-07-05 9:03 ` Stanga
2020-07-06 11:13 ` Tejaswi Nadahalli
2020-07-02 12:39 ` Tejaswi Nadahalli
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200628121517.f3l2mjcy7x4566v3@ganymede \
--to=dave@dtrt$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=matany@campus$(echo .)technion.ac.il \
--cc=sitay@campus$(echo .)technion.ac.il \
--cc=stanga@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox