path: root/c9/9700d1bf561882ac00a56fb1df08e751ba6ea8

Return-Path: <stanga@gmail.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 148E3C016E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:29:13 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by silver.osuosl.org (Postfix) with ESMTP id E8268203A8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:29:12 +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 4ZaNgnyFVjfz
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:29:10 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-oi1-f193.google.com (mail-oi1-f193.google.com
 [209.85.167.193])
 by silver.osuosl.org (Postfix) with ESMTPS id B805A20198
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:29:10 +0000 (UTC)
Received: by mail-oi1-f193.google.com with SMTP id e4so8402112oib.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 29 Jun 2020 23:29:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=bccR3NmW6LZO2LHhIHmZJZCXEk7uj+cXW1TTNKy1dfo=;
 b=ZCMhGjLegMrcMMc7m87r0Uj9oydWiunLSwHJtFS+AEXG4j0S3A08+BfyUbWOJkFt6d
 ewPJcDsRLs4RVcF1SkIzldP3aton8ILCd5p/HjU1d73wsVQAn9yYL0gDDm1MMpD/gRQ9
 7O13MkjiVCkjhvOwGX7KyRjoRiFLGkr1RqCFdirXBLh7EagL8qf5hf61AmXAuPYUkl5a
 tX3aKVX88GpnHL0QL8sD9qSXzM1QQDMTJxEm79W6hbqjm7VPKKIwtOcgtdHIWpsLTkQG
 b+wXqnA13e654E3/oIIJqIqvWMD8S9g6uG+wpY20r3ar9dOE8TfL1l0R5vdeE1/56B18
 6bnQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=bccR3NmW6LZO2LHhIHmZJZCXEk7uj+cXW1TTNKy1dfo=;
 b=k1f16PAgYwP1mJHnm9njp4vuAeztHnc/9GqSHvSc3BCT7f53Wyndjg8wGYmCQ12mjb
 fzuVqQg56tfMyhmxNVUqeRvq+8X5z6ySRfqVjYIYzvhMySnBNs8XViotW/EW0fayeZq+
 31JJ5yg88LcOy+BIULe2PzUNXIepoHxKbOAUteu0DQvfdFN2Ptpl/h/hFwP4g60BNLYF
 /4QD700m7TJOVIMZf75iKqtohXCIdOA7zglvfyB8/7pmCNgAwMuq3Sc2l6D5Sr72UZIP
 H2odMP2VuAv45ZilNXfLAXOfm0uZ2dmUKsnj7uo3f5lpbfdqKePhZWyHtqX5xxgxbEzh
 dv+Q==
X-Gm-Message-State: AOAM532DM3VWJEj6E7uyqmCz2CO9IaMnTpthEnCCrJCpKduJy22FjUbD
 g5LpQVxwZH5mMwvcFzdJco2oZ87e2kXZWvOUrMo=
X-Google-Smtp-Source: ABdhPJxvvS7Tmmmw31iuBkYkbfxRW2hOw9U0SVmWFphZTY0vs9yrfjSN/fy6XBiahldFCV+E3obWXTYMOSfhuz80eFw=
X-Received: by 2002:aca:3b85:: with SMTP id i127mr13487616oia.33.1593498549903; 
 Mon, 29 Jun 2020 23:29:09 -0700 (PDT)
MIME-Version: 1.0
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
 <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
 <20200628121517.f3l2mjcy7x4566v3@ganymede>
 <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>
In-Reply-To: <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>
From: Stanga <stanga@gmail.com>
Date: Tue, 30 Jun 2020 09:28:58 +0300
Message-ID: <CABT1wWnR8bwUbJRPRuuGkh4-Tf6VpPRVbU4dSBtB1_y6QM9R4A@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="00000000000004668005a9474b6f"
X-Mailman-Approved-At: Tue, 30 Jun 2020 07:30:03 +0000
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Itay Tsabary <sitay@campus.technion.ac.il>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 30 Jun 2020 06:29:13 -0000

--00000000000004668005a9474b6f
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi ZmnSCPxj,

That's a good point. Basically there are two extremes, if everyone is
non-myoptic (rational), they should wait even for a small fee (our mad-htlc
result), and if everyone else is myopic (rational), a non-myopic miner
should only wait for a fairly large fee, depending on miner sizes and the
timeout -- this is analyzed in an earlier paper by Winzer, Herd and Faust
[1]. In a mixed situation the calculation becomes slightly more involved,
but qualitatively it's closer to the Wizner et al. result, namely the bribe
should grow exponentially with the timeout, which is bad for the attacker.
But mad-htlc avoids myopic assumptions, allowing you to keep your contracts
safe either way.

Best,
Ittay

[1] F. Winzer, B. Herd and S. Faust, "Temporary Censorship Attacks in the
Presence of Rational Miners
<https://ieeexplore.ieee.org/abstract/document/8802377>," *2019 IEEE
European Symposium on Security and Privacy Workshops (EuroS&PW)*,
Stockholm, Sweden, 2019, pp. 357-366, doi: 10.1109/EuroSPW.2019.00046.

On Mon, Jun 29, 2020 at 9:05 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Dave, et al.,
>
>
> > >      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 woul=
d
> > > include Alice=E2=80=99s transaction and Bob=E2=80=99s bribery attempt=
 would
> > > 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 case=
s
> > 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 i=
f
> > 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.)
>
> A thought occurs to me, that we should not be so hasty to call non-myopic
> strategy "rational".
> Let us consider instead "myopic" and "non-myopic" strategies in a
> population of miners.
>
> I contend that in a mixed population of "myopic" and "non-myopic" miners,
> the myopic strategy is dominant in the game-theoretic sense, i.e. it migh=
t
> earn less if all miners were myopic, but if most miners were non-myopic a=
nd
> a small sub-population were myopic and there was no easy way for non-myop=
ic
> miners to punish myopic miners, then the myopic miners will end up earnin=
g
> more (at the expense of the non-myopic miners) and dominate over non-myop=
ic
> miners.
> Such dominant result should prevent non-myopic miners from arising in the
> first place.
>
> The dominance results from the fact that by accepting the Alice
> transaction, myopic miners are effectively deducting the fees earned by
> non-myopic miners by preventing the Bob transaction from being confirmabl=
e.
> On the other hand, even if the non-myopic miners successfully defer the
> Alice transaction, the myopic miner still has a chance equal to its
> hashrate of getting the Bob transaction and its attached fee.
> Thus, myopic miners impose costs on their non-myopic competitors that
> non-myopic miners cannot impose their myopic competitors.
> If even one myopic miner successfully gets the Alice transaction
> confirmed, all the non-myopic miners lose out on the Bob bribe fee.
>
> So I think the myopic strategy will be dominant and non-myopic miners wil=
l
> not arise in the first place.
>
>
> Regards,
> ZmnSCPxj
>

--00000000000004668005a9474b6f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi=C2=A0ZmnSCPxj,=C2=A0<div><br></div><div>That&#39;s a go=
od point. Basically there are two extremes, if everyone is non-myoptic (rat=
ional), they should wait even for a small fee (our mad-htlc result), and if=
 everyone else is myopic (rational), a non-myopic miner should only wait fo=
r a fairly large fee, depending on miner sizes and the timeout -- this is a=
nalyzed in an earlier paper by=C2=A0Winzer, Herd and Faust [1]. In a mixed =
situation the calculation becomes slightly more involved, but qualitatively=
 it&#39;s closer to the Wizner et al. result, namely the bribe should grow =
exponentially with the timeout, which is bad for the attacker. But mad-htlc=
 avoids myopic assumptions, allowing you to keep your contracts safe either=
 way.=C2=A0</div><div><br></div><div>Best,=C2=A0</div><div>Ittay=C2=A0</div=
><div><br></div><div>[1]=C2=A0<span style=3D"color:rgb(51,51,51);font-famil=
y:sans-serif;font-size:13.6px">F. Winzer, B. Herd and S. Faust, &quot;<a hr=
ef=3D"https://ieeexplore.ieee.org/abstract/document/8802377">Temporary Cens=
orship Attacks in the Presence of Rational Miners</a>,&quot;=C2=A0</span><e=
m style=3D"color:rgb(51,51,51);font-family:sans-serif;font-size:13.6px">201=
9 IEEE European Symposium on Security and Privacy Workshops (EuroS&amp;PW)<=
/em><span style=3D"color:rgb(51,51,51);font-family:sans-serif;font-size:13.=
6px">, Stockholm, Sweden, 2019, pp. 357-366, doi: 10.1109/EuroSPW.2019.0004=
6.</span></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=
=3D"gmail_attr">On Mon, Jun 29, 2020 at 9:05 PM ZmnSCPxj &lt;<a href=3D"mai=
lto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; wrote:<br></di=
v><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left:1px solid rgb(204,204,204);padding-left:1ex">Good morning Dave, et a=
l.,<br>
<br>
<br>
&gt; &gt;=C2=A0 =C2=A0 =C2=A0 Myopic Miners: This bribery attack relies on =
all miners<br>
&gt; &gt;<br>
&gt; &gt;<br>
&gt; &gt; being rational, hence considering their utility at game conclu-<b=
r>
&gt; &gt; sion instead of myopically optimizing for the next block. If<br>
&gt; &gt; a portion of the miners are myopic and any of them gets to<br>
&gt; &gt; create a block during the first T =E2=88=92 1 rounds, that miner =
would<br>
&gt; &gt; include Alice=E2=80=99s transaction and Bob=E2=80=99s bribery att=
empt would<br>
&gt; &gt; have failed.<br>
&gt; &gt; In such scenarios the attack succeeds only with a certain<br>
&gt; &gt; probability =E2=80=93 only if a myopic miner does not create a bl=
ock<br>
&gt; &gt; in the first T =E2=88=92 1 rounds. The success probability theref=
ore<br>
&gt; &gt; decreases exponentially in T . Hence, to incentivize miners<br>
&gt; &gt; to support the attack, Bob has to increase his offered bribe<br>
&gt; &gt; exponentially in T .<br>
&gt;<br>
&gt; This is a good abstract description, but I think it might be useful fo=
r<br>
&gt; readers of this list who are wondering about the impact of this attack=
<br>
&gt; to put it in concrete terms. I&#39;m bad at statistics, but I think th=
e<br>
&gt; probability of bribery failing (even if Bob offers a bribe with an<br>
&gt; appropriately high feerate) is 1-exp(-b*h) where `b` is the number of<=
br>
&gt; blocks until timeout and `h` is a percentage of the hashrate controlle=
d<br>
&gt; by so-called myopic miners. Given that, here&#39;s a table of attack<b=
r>
&gt; failure probabilities:<br>
&gt;<br>
&gt; &quot;Myopic&quot; hashrate<br>
&gt; B 1% 10% 33% 50%<br>
&gt; l +---------------------------------<br>
&gt; o 6 | 5.82% 45.12% 86.19% 95.02%<br>
&gt; c 36 | 30.23% 97.27% 100.00% 100.00%<br>
&gt; k 144 | 76.31% 100.00% 100.00% 100.00%<br>
&gt; s 288 | 94.39% 100.00% 100.00% 100.00%<br>
&gt;<br>
&gt; So, if I understand correctly, even a small amount of &quot;myopic&quo=
t; hashrate<br>
&gt; and long timeouts---or modest amounts of hashrate and short<br>
&gt; timeouts---makes this attack unlikely to succeed (and, even in the cas=
es<br>
&gt; where it does succeed, Bob will have to offer a very large bribe to<br=
>
&gt; compensate &quot;rational&quot; miners for their high chance of losing=
 out on<br>
&gt; gaining any transaction fees).<br>
&gt;<br>
&gt; Additionally, I think there&#39;s the problem of measuring the distrib=
ution<br>
&gt; of &quot;myopic&quot; hashrate versus &quot;rational&quot; hashrate. &=
quot;Rational&quot; miners need<br>
&gt; to do this in order to ensure they only accept Bob&#39;s timelocked br=
ibe if<br>
&gt; it pays a sufficiently high fee. However, different miners who try to<=
br>
&gt; track what bribes were relayed versus what transactions got mined may<=
br>
&gt; come to different conclusions about the relative hashrate of &quot;myo=
pic&quot;<br>
&gt; miners, leading some of them to require higher bribes, which may lead<=
br>
&gt; those those who estimated a lower relative hash rate to assume the rat=
e<br>
&gt; of &quot;myopic&quot; mining in increasing, producing a feedback loop =
that makes<br>
&gt; other miners think the rate of &quot;myopic&quot; miners is increasing=
. (And that<br>
&gt; assumes none of the miners is deliberately juking the stats to mislead=
<br>
&gt; its competitors into leaving money on the table.)<br>
<br>
A thought occurs to me, that we should not be so hasty to call non-myopic s=
trategy &quot;rational&quot;.<br>
Let us consider instead &quot;myopic&quot; and &quot;non-myopic&quot; strat=
egies in a population of miners.<br>
<br>
I contend that in a mixed population of &quot;myopic&quot; and &quot;non-my=
opic&quot; miners, the myopic strategy is dominant in the game-theoretic se=
nse, i.e. it might earn less if all miners were myopic, but if most miners =
were non-myopic and a small sub-population were myopic and there was no eas=
y way for non-myopic miners to punish myopic miners, then the myopic miners=
 will end up earning more (at the expense of the non-myopic miners) and dom=
inate over non-myopic miners.<br>
Such dominant result should prevent non-myopic miners from arising in the f=
irst place.<br>
<br>
The dominance results from the fact that by accepting the Alice transaction=
, myopic miners are effectively deducting the fees earned by non-myopic min=
ers by preventing the Bob transaction from being confirmable.<br>
On the other hand, even if the non-myopic miners successfully defer the Ali=
ce transaction, the myopic miner still has a chance equal to its hashrate o=
f getting the Bob transaction and its attached fee.<br>
Thus, myopic miners impose costs on their non-myopic competitors that non-m=
yopic miners cannot impose their myopic competitors.<br>
If even one myopic miner successfully gets the Alice transaction confirmed,=
 all the non-myopic miners lose out on the Bob bribe fee.<br>
<br>
So I think the myopic strategy will be dominant and non-myopic miners will =
not arise in the first place.<br>
<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--00000000000004668005a9474b6f--