path: root/0e/63b6ee72eec1a819b6428d2ac4756fa5cc8a43

Return-Path: <nadahalli@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 21BBDC016E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:45:23 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id 11C508834D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:45:23 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 16LaQfJJXk0V
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:45:22 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-pg1-f175.google.com (mail-pg1-f175.google.com
 [209.85.215.175])
 by hemlock.osuosl.org (Postfix) with ESMTPS id EBBAE87A77
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 Jun 2020 06:45:21 +0000 (UTC)
Received: by mail-pg1-f175.google.com with SMTP id t6so9498139pgq.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 29 Jun 2020 23:45:21 -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=TYaclI+D9b7UzZQUdZgy9H/TegoHhx3Ixp5q4tiu3EE=;
 b=jARwpty74f/Y0RuR1FiFJ52iEybLk+SrXw7KSa3kF/D3b0YSDXoLlGNgSyXJs/8/ZT
 kmUNk6yoAUyTyoc0O8IV9E+oZTqVJ4OMj+RP+u5LgD0E3gBCjN/DMv77FlY0w+TtHFw9
 FNwi6qPCihyH+kjAihejMcaXD/GFl33z88rHt7IfcKW7mOsavEoJyEVWAJ2xUwrlcn1I
 NI2lq+En3lzhZo9SG9yhSivt5+j1ZvIDlOOSZNhEy9B6wMpFi6M67czlzHS4vi/9aIiy
 wKQDTIEUobSvdZybY4x9zQCmw9S0l9CkqWQpES0xsdnH1PtvaMVgHXt1fT/NYRq2bq1O
 gy/Q==
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=TYaclI+D9b7UzZQUdZgy9H/TegoHhx3Ixp5q4tiu3EE=;
 b=hSh2xLCbf7tpDsrTALOHMMBHufVy0IOQmwtGXAH1n44voDukJhcCPOmGe/vooSHioo
 zzTtJnrYoejpBJpq3nUpEMfZ9IPWucCBSEzV4AqbxAP4mdqTyAS7XUPWFv+3maYaR1c0
 EjXyqPuX31PfCKdSGhGp8zBNcHKwMTFmA95vWUF76ol0DKCNfOicXYq6euDF/8lPJBb6
 HLIT0up9TdJjVzexHGB90G8bLfdofyssShetVxUHpi69vRQLk9cHbrxjBkxQH9sbSfpW
 en4/Hge1ThOqQvRfqBDPocEdiSOsMauG0E54ArYpKN++qFgoO1CbmmDBpsocyN9uTK5B
 HhgA==
X-Gm-Message-State: AOAM533LyNfDyMhRV57ymnFVRCPrjAmxlsq8aoEkuPddbL+MGfypb4Mw
 WJslox3ydd2PPETkYKeZRQg2sRWwxihPy093Cg8=
X-Google-Smtp-Source: ABdhPJyzE0YIbnvYlidhcC5wWwSrBmk9Beh0d8oItYsYh3yfNmE023Ff0O2zz/99zGblurJUzMGc2DcFZp0T/IOTm2k=
X-Received: by 2002:aa7:9736:: with SMTP id k22mr17132396pfg.62.1593499521415; 
 Mon, 29 Jun 2020 23:45:21 -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: Tejaswi Nadahalli <nadahalli@gmail.com>
Date: Tue, 30 Jun 2020 08:45:09 +0200
Message-ID: <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ec7f5305a9478415"
X-Mailman-Approved-At: Tue, 30 Jun 2020 07:30:03 +0000
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
 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:45:23 -0000

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

Hello ZmnSCPxj (as there would be no better way to start an email to you
:-),

I posted a reply to Dave in the other sub-thread of this main thread. We
have a paper about something similar to what you have said - where we look
at "weak" and "strong" miners, and how even if there are a few weak miners,
they have a dominating strategy, etc.

On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr">Hello ZmnSCPxj (as there would be no better way to start a=
n email to you :-),<div><br></div><div>I posted a reply to Dave in the othe=
r sub-thread of this main thread. We have a paper about something similar t=
o what you have said - where we look at &quot;weak&quot; and &quot;strong&q=
uot; miners, and how even if there are a few weak miners, they have a domin=
ating strategy, etc.=C2=A0</div></div><br><div class=3D"gmail_quote"><div d=
ir=3D"ltr" class=3D"gmail_attr">On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj vi=
a bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">=
bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px soli=
d rgb(204,204,204);padding-left:1ex">Good morning Dave, et al.,<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>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000ec7f5305a9478415--