Re: [bitcoin-dev] MAD-HTLC

From: Tejaswi Nadahalli <nadahalli@gmail•com>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Cc: Matan Yehieli <matany@campus•technion.ac.il>,
	Itay Tsabary <sitay@campus•technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Date: Tue, 30 Jun 2020 08:45:09 +0200	[thread overview]
Message-ID: <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com> (raw)
In-Reply-To: <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>

[-- Attachment #1: Type: text/plain, Size: 5247 bytes --]

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 − 1 rounds, that miner would
> > > include Alice’s transaction and Bob’s bribery attempt would
> > > have failed.
> > > In such scenarios the attack succeeds only with a certain
> > > probability – only if a myopic miner does not create a block
> > > in the first T − 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.)
>
> 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 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 easy 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 dominate over non-myopic
> 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 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
> 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 will
> 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
>

[-- Attachment #2: Type: text/html, Size: 6232 bytes --]