diff options
| author | ZmnSCPxj <ZmnSCPxj@protonmail.com> | 2020-07-01 16:58:24 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2020-07-01 16:58:38 +0000 |
| commit | bb60e5c58c2d0e7f23a8e3631c66a57067ffa028 (patch) | |
| tree | f87993949fc53fccee75a59e52f8ee8263b5e682 | |
| parent | 42c3957f92aedb313981987b693fc185c5ce3b97 (diff) | |
| download | pi-bitcoindev-bb60e5c58c2d0e7f23a8e3631c66a57067ffa028.tar.gz pi-bitcoindev-bb60e5c58c2d0e7f23a8e3631c66a57067ffa028.zip | |
Re: [bitcoin-dev] MAD-HTLC
| -rw-r--r-- | cd/35bcecbbd16aa46d4f9bcf6de81597444d1acc | 305 |
1 files changed, 305 insertions, 0 deletions
diff --git a/cd/35bcecbbd16aa46d4f9bcf6de81597444d1acc b/cd/35bcecbbd16aa46d4f9bcf6de81597444d1acc new file mode 100644 index 000000000..7637cb7f7 --- /dev/null +++ b/cd/35bcecbbd16aa46d4f9bcf6de81597444d1acc @@ -0,0 +1,305 @@ +Return-Path: <ZmnSCPxj@protonmail.com> +Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 951CAC0733 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <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 +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.15 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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 + + + |