Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 21BBDC016E for ; 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 ; 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 ; 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 ; Tue, 30 Jun 2020 06:45:21 +0000 (UTC) Received: by mail-pg1-f175.google.com with SMTP id t6so9498139pgq.1 for ; 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: <20200628121517.f3l2mjcy7x4566v3@ganymede> In-Reply-To: From: Tejaswi Nadahalli Date: Tue, 30 Jun 2020 08:45:09 +0200 Message-ID: To: ZmnSCPxj , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000ec7f5305a9478415" X-Mailman-Approved-At: Tue, 30 Jun 2020 07:30:03 +0000 Cc: Matan Yehieli , Itay Tsabary 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Hello ZmnSCPxj (as there would be no better way to start a= n email to you :-),

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 "weak" and "strong&q= uot; miners, and how even if there are a few weak miners, they have a domin= ating strategy, etc.=C2=A0

On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj vi= a bitcoin-dev <= bitcoin-dev@lists.linuxfoundation.org> wrote:
Good morning Dave, et al.,


> >=C2=A0 =C2=A0 =C2=A0 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 att= empt 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 bl= ock
> > in the first T =E2=88=92 1 rounds. The success probability theref= ore
> > 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 fo= r
> 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 th= e
> 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<= br> > blocks until timeout and `h` is a percentage of the hashrate controlle= d
> 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&quo= t; hashrate
> and long timeouts---or modest amounts of hashrate and short
> timeouts---makes this attack unlikely to succeed (and, even in the cas= es
> 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 distrib= ution
> of "myopic" hashrate versus "rational" hashrate. &= quot;Rational" miners need
> to do this in order to ensure they only accept Bob's timelocked br= ibe if
> it pays a sufficiently high fee. However, different miners who try to<= br> > track what bribes were relayed versus what transactions got mined may<= br> > come to different conclusions about the relative hashrate of "myo= pic"
> miners, leading some of them to require higher bribes, which may lead<= br> > those those who estimated a lower relative hash rate to assume the rat= e
> 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 s= trategy "rational".
Let us consider instead "myopic" and "non-myopic" strat= egies in a population of miners.

I contend that in a mixed population of "myopic" and "non-my= opic" 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.
Such dominant result should prevent non-myopic miners from arising in the f= irst place.

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.
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.
Thus, myopic miners impose costs on their non-myopic competitors that non-m= yopic 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 will = not arise in the first place.


Regards,
ZmnSCPxj
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000ec7f5305a9478415--