Date: Wed, 01 Jul 2020 16:58:24 +0000
To: Tejaswi Nadahalli <nadahalli@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com>
In-Reply-To: <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>
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>
 <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
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
Precedence: list

Good morning Tejaswi,

> 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.=C2=A0
>

By my reading, it seems to me that you divide miners into "weak" and "power=
ful".
Weak miners have lower hashrate than powerful ones.
The dividing point depends on how much Alice and Bob fees are.
If the hashrate share of a miner is less than the ratio of Alice (honest) f=
ee to Bob (bribing) fee, then the miner is weak.

And your paper posits that if a miner is weak, its best strategy is to take=
 the myopic strategy and include the currently-valid Alice transaction.

Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is =
1.0 implying a miner can only be powerful if it has already 51%-attacked Bi=
tcoin (which tends to invalidate all our security assumptions of higher-lay=
er protocols anyway, since a 51% attacker can censor anything with impunity=
).

Of course, Bob can offer up to the entire fund amount, for free, to miners =
as a bribe, without loss to Bob.

For more realistic scenarios where no miner has 100% hashrate, then Alice c=
an make all miners weak by being willing to pay up to 50% of the fund as fe=
e, as a miner that achieves greater than 50% hashrate share would already e=
ffectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway.

So it looks to me that scorched-earth is a possible mitigation against this=
 attack.

--

Another analysis, similar but a little off-tangent to yours, would be to co=
nsider miners as a breeding group with various strategies, and see which on=
e is able to gain more utilons (with which it creates more miners) and outb=
reed the other miners.

This models the fact that miners can use their earnings to reinvest into th=
eir mining operations and increase their mining hashrate, and the amount th=
ey can reinvest is proportional to their earnings.
A miner that "gives birth" to a child miner with the same strategy is, in t=
he so-called "real world", simply a miner that has earned enough and reinve=
sted those earnings to double the hashrate of their business (which, logica=
lly speaking, would use the same strategy throughout the entire business).

Let us start with a population of 4 miners, 3 of which follow the non-myopi=
c strategy, and the remaining following the myopic strategy.
Let us postulate that all miners have the same unit hashrate.
Thus, this starting population is 75% non-myopic, 25% myopic.

If there exists a timelocked bribe, then if non-myopic miner is chosen at a=
 block, it will have to sacrifice the Alice fee minus whatever lesser trans=
action fee it can replace in its block.
If the Alice transaction is successfully delayed until the Bob transaction =
is valid, then the non-myopic miners can get the Bob transaction confirmed.

However, even in the case that the Alice transaction is delayed, the myopic=
 miner still has its 25% chance --- equal to the 25% chance of the three no=
n-myopic miners --- to confirm the Bob transaction and earn the increased b=
ribe that Bob offers.

Thus, the non-myopic miners can end up sacrificing fee earnings, and in the=
 end the myopic miner still has the 25% chance to get the Bob transaction f=
ee later when it becomes valid.
So the non-myopic miners do not impose any loss on myopic miners.

On the other hand, if the non-myopic miners sacrificed their chances to inc=
lude the Alice transaction in the hope of getting the later 25% chance to g=
et the Bob higher-fee timelocked transaction, and then the myopic miner get=
s the next block, the myopic miner gets the Alice transaction confirmed and=
 the 25% chance to get the Bob higher fee is lost by the non-myopic miners.
Thus, the myopic miner is able to impose costs on their non-myopic competit=
ors.

So even if by chance for the entire locktime, only the non-myopic miners ar=
e selected, the myopic miner still retains its 25% chance of getting the bl=
ock at locktime + 1 and confirming and earning the bigger Bob fee.

Thus, we expect that the myopic miner will earn more than 25% of subsidies =
and fees than the non-myopic miners, in such a mixed environment.

We can then consider that the myopic miner, being able to earn more, is abl=
e to increase its progeny (i.e. expand its mining business and inspire new =
miners to follow its strategy towards success) faster than the non-myopic m=
iners.

We can thus conclude that the myopic miners will eventually dominate over t=
he breeding population and drive the non-myopic miners to near-extinction.

It is helpful to remember that rationality is about success *in the univers=
e you exist in*.
While miners may step back and consider that, ***if*** all of them were to =
use non-myopic strategy, they would all earn more, the fact of the matter i=
s that each miner works for themselves, and themselves alone, in a highly c=
ompetitive environment.
Thus, even though they know *all of them* will benefit if they use the non-=
myopic strategy, they cannot be sure, unless they are all perfectly synchro=
nized mind-clones of each other, that the other miners will rather be selfi=
sh and mine for themselves, even if in the end every miner earns less
The standard for success is to earn more *than your competitors*, not ensur=
e that *every* miner earns more.

Fortunately, since miners are running a business, this competition leads to=
 better services to the the customers of the mining business, a known pheno=
menon of the free market, yay free market greed is good.
The user Alice is a customer of the mining business.
Alice gets, as a side effect of this competitiveness of miners (which leads=
 to miners adopting myopic strategies in order to gain an edge over non-myo=
pic miners), improved security of their HTLCs without requiring slashable f=
idelity bonds or such-like that MAD-HTLC proposes.


Using this model, it seems to me that non-myopic miners can only maintain h=
old over the blockchain if all miners agree to use non-myopic strategy.
This is basically all miners forming a cartel / monopoly, which we know is =
detrimental to customers of the monopoly, and is the reason why we prefer d=
ecentralization.


Regards,
ZmnSCPxj


> On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lis=
ts.linuxfoundation.org> wrote:
>
> > Good morning Dave, et al.,
> >
> > > >=C2=A0 =C2=A0 =C2=A0 Myopic Miners: This bribery attack relies on al=
l 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 wo=
uld
> > > > include Alice=E2=80=99s transaction and Bob=E2=80=99s bribery attem=
pt 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 bloc=
k
> > > > in the first T =E2=88=92 1 rounds. The success probability therefor=
e
> > > > 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 f=
or
> > > readers of this list who are wondering about the impact of this attac=
k
> > > 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 controll=
ed
> > > 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" hashra=
te
> > > and long timeouts---or modest amounts of hashrate and short
> > > timeouts---makes this attack unlikely to succeed (and, even in the ca=
ses
> > > 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 distributi=
on
> > > of "myopic" hashrate versus "rational" hashrate. "Rational" miners ne=
ed
> > > 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 ra=
te
> > > of "myopic" mining in increasing, producing a feedback loop that make=
s
> > > other miners think the rate of "myopic" miners is increasing. (And th=
at
> > > assumes none of the miners is deliberately juking the stats to mislea=
d
> > > its competitors into leaving money on the table.)
> >
> > A thought occurs to me, that we should not be so hasty to call non-myop=
ic strategy "rational".
> > Let us consider instead "myopic" and "non-myopic" strategies in a popul=
ation of miners.
> >
> > I contend that in a mixed population of "myopic" and "non-myopic" miner=
s, the myopic strategy is dominant in the game-theoretic sense, i.e. it mig=
ht 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 easy way for non-my=
opic miners to punish myopic miners, then the myopic miners will end up ear=
ning more (at the expense of the non-myopic miners) and dominate over non-m=
yopic miners.
> > Such dominant result should prevent non-myopic miners from arising in t=
he first place.
> >
> > The dominance results from the fact that by accepting the Alice transac=
tion, myopic miners are effectively deducting the fees earned by non-myopic=
 miners by preventing the Bob transaction from being confirmable.
> > 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 hashra=
te of getting the Bob transaction and its attached fee.
> > Thus, myopic miners impose costs on their non-myopic competitors that n=
on-myopic miners cannot impose their myopic competitors.
> > If even one myopic miner successfully gets the Alice transaction confir=
med, 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 w=
ill 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