From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 951CAC0733 for ; Wed, 1 Jul 2020 16:58:38 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 579412916B for ; Wed, 1 Jul 2020 16:58:38 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5nkgyOJ0k15F for ; Wed, 1 Jul 2020 16:58:35 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40132.protonmail.ch (mail-40132.protonmail.ch [185.70.40.132]) by silver.osuosl.org (Postfix) with ESMTPS id 96C8426FA8 for ; Wed, 1 Jul 2020 16:58:34 +0000 (UTC) Date: Wed, 01 Jul 2020 16:58:24 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1593622711; bh=mvdGvjwH7nr+CB9muIYP2C4NHP6yl7ZXsc6BOipRAkA=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=li0TEW+WU1BiU//WNYftv5qcpT2nQfqpuNV+CxVM4a1H5BwH0DPy+RdFbY7cRN2Mr x6S1QVczJ6tS9voxNGQaws5Th8GWt1gWXrSmB3jwe1/GEu6Vg/SXiNd9NFkJPSxyZw tMxETUcPZdsz/qGWtcql3y9vhJsXudAn4odModfg= To: Tejaswi Nadahalli From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <20200628121517.f3l2mjcy7x4566v3@ganymede> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: Matan Yehieli , Bitcoin Protocol Discussion , 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: Wed, 01 Jul 2020 16:58:38 -0000 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 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