Re: [bitcoin-dev] MAD-HTLC

From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: Tejaswi Nadahalli <nadahalli@gmail•com>
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
Date: Wed, 01 Jul 2020 16:58:24 +0000	[thread overview]
Message-ID: <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com> (raw)
In-Reply-To: <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>

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. 
>

By my reading, it seems to me that you divide miners into "weak" and "powerful".
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) fee 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 Bitcoin (which tends to invalidate all our security assumptions of higher-layer 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 can make all miners weak by being willing to pay up to 50% of the fund as fee, as a miner that achieves greater than 50% hashrate share would already effectively 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 consider miners as a breeding group with various strategies, and see which one is able to gain more utilons (with which it creates more miners) and outbreed the other miners.

This models the fact that miners can use their earnings to reinvest into their mining operations and increase their mining hashrate, and the amount they can reinvest is proportional to their earnings.
A miner that "gives birth" to a child miner with the same strategy is, in the so-called "real world", simply a miner that has earned enough and reinvested those earnings to double the hashrate of their business (which, logically 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-myopic 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 transaction 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 non-myopic miners --- to confirm the Bob transaction and earn the increased bribe 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 fee 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 include the Alice transaction in the hope of getting the later 25% chance to get the Bob higher-fee timelocked transaction, and then the myopic miner gets 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 competitors.

So even if by chance for the entire locktime, only the non-myopic miners are selected, the myopic miner still retains its 25% chance of getting the block 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 able 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 miners.

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

It is helpful to remember that rationality is about success *in the universe 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 is that each miner works for themselves, and themselves alone, in a highly competitive 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 synchronized mind-clones of each other, that the other miners will rather be selfish 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 ensure 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 phenomenon 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-myopic miners), improved security of their HTLCs without requiring slashable fidelity bonds or such-like that MAD-HTLC proposes.

Using this model, it seems to me that non-myopic miners can only maintain hold 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 decentralization.

Regards,
ZmnSCPxj

> 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