Date: Sun, 28 Jun 2020 08:15:17 -0400
From: "David A. Harding" <dave@dtrt.org>
To: Stanga <stanga@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20200628121517.f3l2mjcy7x4566v3@ganymede>
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
 <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="r7ohapeyprb3ykk3"
Content-Disposition: inline
In-Reply-To: <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
User-Agent: NeoMutt/20180716
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
 Itay Tsabary <sitay@campus.technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Precedence: list


--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--