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 8C280C0051 for ; Wed, 7 Oct 2020 20:20:11 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 7C7F0272BB for ; Wed, 7 Oct 2020 20:20:11 +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 ix5G+55W-9-C for ; Wed, 7 Oct 2020 20:20:08 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wm1-f43.google.com (mail-wm1-f43.google.com [209.85.128.43]) by silver.osuosl.org (Postfix) with ESMTPS id F03C327A61 for ; Wed, 7 Oct 2020 20:20:07 +0000 (UTC) Received: by mail-wm1-f43.google.com with SMTP id d81so3838105wmc.1 for ; Wed, 07 Oct 2020 13:20:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ib.tc; s=google; h=mime-version:from:date:message-id:subject:to; bh=+LrJiU2lkdEU+mtbuivSn3CeG8eYzRq3MegMUVVUm5w=; b=o8EVHU/dQFhDgrP2r2q4Js+rgIl6xOO7j78QornTvNRZnuLz7StUIPmS5LLWENInnd AFrKwwlIGHZ0CwDpYGiUayWVajLzry+uXVsg+1rX17g4o4bJJDrFc6si/uBQJypCTvJY aRJnX/gQ52+lGDj51V0Cel09L8lqKXnyq/BQTdou8bck9D+T6Omh8JHI/DyRKWNnKY6O Y5K1eoKBpcNhW/SgCbxq5Sl19kOXx71IicStreL2gzZ6r10yRKsMNjSXjrrCtkDClben NDv52YoXmhGsWcsE94/IEcAfBgY7mTLD6BntSE3+9vy/WGu21NxixqGkOS/C3VfKWwJY 2vFQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=+LrJiU2lkdEU+mtbuivSn3CeG8eYzRq3MegMUVVUm5w=; b=OHLQLE5NJfuMicv5IYEKbqIdvkdcCCcymoFLbmVJyIH/b7Bo/Ki2s/TRcDp/n04gp+ SkBwrkeF1BR2yuMhJpVylDm4wc/fPzszonQfPiQlg5x1m1RIUR/z9rbPgKuGU7qw5/S/ 6MDTgEnD4ZNnNWijxKek6XBzB8HkGC+3NGXFJXHdsMCU3G3LY+sYM+Uni09Zxv5cto40 RwDaHDHM6eBq7NB1CqI0l43iQ8b3Em6NwUypZ3O99LLx8xkbGroLdi+fx52gVWVmUb66 BWQz0Cn43Ee+O4gTHd/HFLDs4lNa6NMoTPiUdBEhXFr5+yPtlSuE33P89wClUWQHwu51 T9QQ== X-Gm-Message-State: AOAM533VUENIr8uNL2A7oWNwmt5uE87su7WAtk1GdjdSpZ517yOXb9Pu QYOx7qZi6tZIdP4u930b5PKJ0DVAwUPLX5s5loxi7wc3N6fBrQ== X-Google-Smtp-Source: ABdhPJwKwOWxf6mJfqw5qidSK4CLNQmXyRbKVWuNfoWIMIjNFgC8PfLhzs6TZQtFltjlauw8MKVUDAFe9D/8k9P39Qg= X-Received: by 2002:a1c:9a0c:: with SMTP id c12mr5201743wme.85.1602102005533; Wed, 07 Oct 2020 13:20:05 -0700 (PDT) MIME-Version: 1.0 From: Mike Brooks Date: Wed, 7 Oct 2020 21:04:08 -0700 Message-ID: To: bitcoin-dev Content-Type: multipart/alternative; boundary="000000000000ef25a705b11a70b9" X-Mailman-Approved-At: Wed, 07 Oct 2020 20:30:55 +0000 Subject: [bitcoin-dev] Progress on Miner Withholding - FPNC 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, 07 Oct 2020 20:20:11 -0000 --000000000000ef25a705b11a70b9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello Everyone, Below is a novel discussion on block-withholding attacks and FPNC. These are two very simple changes being proposed here that will dramatically impact the network for the better. But first of all, I'd like to say that the idea for FPNC came out of a conversation with ZmnSCPxj's in regards to re-org stability. When I had proposed blockchain pointers with the PubRef opcode, he took the time to explain to me concerns around re-orgs and why it is a bigger problem than I initially had thought =E2=80=94 and I greatly appreciate this detail. Aft= er touching base with ZmnSCPxj and Greg Maxwell there is an overwhelming view that the current problems that face the network outweigh any theoretical ones. Currently the elephant in the room is the miner withholding attack. There is an unintended incentive to hold onto blocks because keeping knowledge of this coinbase private gives a greedy miner more time to calculate the next block. Major mining pools are actively employing this strategy because winning two blocks in a row has a much greater payoff than common robbery. This unfair advantage happens each time a new block is found, and provides a kind of home-field advantage for large pools, and contributes to a more centralized network. This odd feature of the bitcoin protocol provides a material incentive to delay transactions and encourages the formation of disagreements. In a sense, withholding is a deception of the computational power of a miner, and by extension a deception of their influence within the electorate. In effect, other miners are forced to work harder, and when they are successful in finding a 2nd solution of the same height =E2= =80=94 no one benefits. Disagreement on the bitcoin network is not good for the environment, or for the users, or for honest miners, but is ideal for dishonest miners looking for an advantage. Currently, there is no way to resolve disagreements of the same block height in Bitcoin protocol. Floating-point Nakamoto Consensus ( https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floa= ting-Point%20Nakamoto%20Consensus.pdf) address ambiguity in the consensus formation process so that disagreements can be empirically resolved without wasted effort. With FPNC every block has a non-zero element which provides the basis for a floating-point fitness value. Nodes are already incentivised to choose the solution that represents the most amount of work, FPNC allows for this same calculation to happen for two solutions of the same height. With FPNC the higher fitness-value carries forward, and all children of this higher value block will be stronger from having a higher fitness value, this is to make sure that winning blocks stay as the winner. If a rogue client chooses to mine a low value disagreement, they will have to make-up the difference in fitness score with their next solution =E2=80=94 This is the genetic algorithm supported by FPNC which ensures that the child blocks from a loser will also be losers. Using FPNC as a method of disagreement resolution enables two features that provide better incentives over "first seen." For one, FPNC introduces risk into holding onto low-value solutions, which de-incentivises 1/2 of all withholding attacks. Additionally, FPNC can be used to increase the rate of block formation which will reduce the amount of time that a miner can hold onto private blocks. With FPNC, a node will only accept the highest-value chain. With the added threat of another miner finding a higher-FPNC value solution, any unscrupulous miner who has mined a low-value block (less than 50% value) is greatly incentives to broadcast out this block before a more valuable solution is found. It is important to note that replacing a low-FPNC value block is more expensive than simply finding a new block, so even if the lowest value is broadcast it is the winner, until proven otherwise. These greedy miners are holding onto 100% of solution blocks - but FPNC creates a class of block that isn't incentivised on holding. The threat of being replaced by a fair disagreement-resolution process, keeps all miners honest= . With 1/2 of the blocks being withheld, and 1/2 not being broadcast immediately, you could eventually identify malicious miners based on this timing difference. With the current system it isn't as clear, but with a split incentive you the network can observe unfair treatment of high-valued blocks. FPNC makes the silent process of withholding into one that must show a value-bias, and this unethical behavior can be observed and acted upon. The question that is on everyone's mind: Does FPNC create new bad incentives? No, it only limits the bad incentives that already exist in the protocol. -> Any miner holding onto a high FPNC-value block would have a slight advantage only for the immediate next block. The hopes of generating future blocks and armed with a slight advantage, would need at-least 50% processing power to maintain. At-least 50% is needed because the miners on the private chain would have out-race the network as a whole. This means that getting three in a row is time boxed with FPNC. Whereas "first seen" gives dishonesty a home-field advantage every time. The bitcoin protocol uses a mining difficulty that depends on a zero-prefix. As a result, this difficulty function consists of discrete jumps that grow exponentially, and there are some very good reasons not to rely on this construct. Instead of zeros, a range of floating-point values, or fractional parts of whole numbers can be used as the difficulty cut-off, where any solution more difficult than the cut-off is still accepted. Because the proof-of-work is no longer dependent on an arbitrary 0, moving to an floating-point value range would allow block-formation to be on an arbitrary time-schedule, which could be made slower or faster. The amount of time that a block can be withheld is proportional to the amount of time it takes to generate, therefore a faster block formation time inturn limits the amount of time that a block can be withheld. If block formation is on average 30 seconds to 1 minute, then the amount of time a miner can impact the network is capped at seconds instead of minutes. Although it doesn't stop withholding attacks, speeding up the dramatically limits the amount of time that any attacker can withhold a block, thus mitigating the impact of malignant miners. Speeding up block formation time while keeping inflation targets the same adds value to users of the network. Currently on the BItcoin network, any malicious miner performing a withholding attack does not need to be at the mercy of network conditions, and would be more successful if they preemptively spread their delayed solution. With an artificially-increased connection capacity a node can gain a visibility advantage on the bitcoin network. When this greedy miner sees that a competing miner has released a block =E2=80=94 then the greedy = miner can pre-empt the spread of their delayed solution and beat out any honest solution. A miner using pre-emption to artificially spread their side of the consensus can ensure the adoption of their block because honest miners are dependent on natural topography of the network to spread their messages =E2=80=94 a topography which is not optimized for speed. It isn't that the = attacker is all powerful, it is that p2p networks have an inherent higher-latency than centralized systems. A miner can have a pre-computed map of the bitcoin network and then reach out and inform each node of the delayed block before the honest block has a chance to arrive. Thus shaping the disagreement in the favor of the malicious miner. So long as a malicious miner has sufficient visibility, they unlock a luxury of subjecating would-be dissent and guaranteeing that their solution is the one that always wins. An attacker cannot choose their FPNC fitness value, but they can choose when their block arrives and to whom. The "first seen" approach to block adoption pressures malicious miners into a race of message propagation that convinces undecided nodes to work for the dishonest chain. The race-condition in block arrival is fundamentally resolved because the order in which blocks arrive doesn't influence the block's FPNC value. Therefore having clear disagreement resolution with FPNC removes a feature of the network that can be leveraged to make sure that a block-withholding attack supplants honest blocks. By clarifying the rules in which blocks will be replaced =E2=80=94 fewer disagreements will form. Without having a form of disagreement resolution and leaving the process up to time, then nodes can be deputized by malicious miners and aid in the mining of withheld blocks. All the best, -Michael --000000000000ef25a705b11a70b9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello Everyone,

Below is a novel discussion=C2=A0on block-withholdin= g=C2=A0attacks and FPNC. These are=C2=A0two very simple changes being propo= sed here that will dramatically=C2=A0impact the network for the better.

But first of all, I'd like to say that the idea f= or FPNC came out of a conversation=C2=A0with ZmnSCPxj's in regards to= =C2=A0re-org stability.=C2=A0 When I had proposed blockchain pointers with = the PubRef opcode, he took the time to explain to me concerns around re-org= s and why it is a bigger problem than I initially had thought=C2=A0=E2=80= =94 and I greatly appreciate this detail.=C2=A0 =C2=A0After touching base w= ith ZmnSCPxj and Greg Maxwell there is an overwhelming view that the curren= t problems that face the network outweigh any theoretical ones.
<= br>
Currently the elephant in the room is the miner withholding a= ttack.=C2=A0There is an unintended incentive to hold onto blocks because ke= eping knowledge of this coinbase private gives a greedy miner more time to = calculate the next block.=C2=A0 Major mining pools are actively employing t= his strategy because winning two blocks in a row has a much greater payoff = than common robbery. This unfair advantage=C2=A0happens each time a=C2=A0ne= w block is found, and provides a kind of home-field advantage for large poo= ls, and contributes to a more centralized network. This odd feature of the = bitcoin protocol provides a material incentive to delay transactions and en= courages the formation of disagreements. In a sense, withholding is a decep= tion of the computational power of a miner, and by extension a deception of= their influence within the electorate.=C2=A0 In effect, other miners are f= orced to work harder,=C2=A0and when they are successful in finding a 2nd so= lution of the same height=C2=A0=E2=80=94 no one benefits. Disagreement on t= he bitcoin network is not good for the environment, or for the users, or fo= r honest miners, but is ideal for dishonest miners looking for an advantage= .

Currently, there is no way to = resolve disagreements of the same block height in Bitcoin protocol.=C2=A0 F= loating-point Nakamoto Consensus (https://github.com/in-st/Floating-Point-Nakamoto= -Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf) addre= ss ambiguity in the consensus formation process so that disagreements can b= e empirically resolved without wasted effort. With FPNC every block has a n= on-zero element which provides the basis=C2=A0for a floating-point fitness = value. Nodes are already incentivised to choose the solution that represent= s the most amount of work, FPNC allows for this same calculation to happen = for two solutions of the same height. With FPNC the higher fitness-value ca= rries forward, and all children of this higher value block will be stronger= from having a higher fitness value, this is to make sure that=C2=A0 winnin= g blocks stay as the winner.=C2=A0 If a rogue client chooses to mine a low = value disagreement, they will have to make-up the difference in fitness sco= re with their next solution =E2=80=94 This is the genetic algorithm=C2=A0su= pported by FPNC which ensures that the child blocks from a loser will also = be losers.

Using FPNC as= a method of disagreement resolution enables two features that provide bett= er incentives over "first seen." For one,=C2=A0 FPNC introduces risk into holding onto low-value solutions, which de-incent= ivises 1/2 of all withholding attacks.=C2=A0 Additionally, FPNC can be used= to increase the rate of block formation which will reduce the amount of ti= me that a miner can hold onto private=C2=A0blocks.

With FPNC, a node will only accept the highest-value chain.=C2=A0 Wi= th the added threat of another miner finding a higher-FPNC value solution, = any unscrupulous miner who has mined a low-value block (less than 50% value= ) is greatly incentives to broadcast out this block before a more valuable = solution is found.=C2=A0 It is important to note that replacing a low-FPNC = value block is more expensive than simply finding a new block, so even if t= he lowest value is broadcast it is the winner, until proven otherwise.=C2= =A0 These greedy miners are holding onto 100% of solution blocks - but FPNC= creates a class of block that isn't incentivised on holding. The threa= t of being replaced by a fair disagreement-resolution process, keeps all mi= ners honest.

With 1/2 of the blocks being wit= hheld, and 1/2 not being broadcast=C2=A0immediately, you could eventually i= dentify malicious miners based on this timing difference. With the current = system it isn't as clear, but with a split incentive you the network ca= n observe unfair treatment of high-valued blocks.=C2=A0 FPNC makes the sile= nt process of withholding into one that must show a value-bias, and this un= ethical behavior can be observed=C2=A0and acted upon.=C2=A0
The question that is on everyone's mind: Does FPNC create = new=C2=A0bad incentives? No, it only limits the bad incentives that already= exist in the protocol.
->
Any miner holding onto a = high FPNC-value block would=C2=A0have=C2=A0a slight advantage only for the = immediate next block.=C2=A0 The hopes of generating future blocks and armed= with a slight advantage, would need at-least 50% processing power to maint= ain. At-least 50% is needed because the miners on the private chain would h= ave out-race the network as a whole.=C2=A0 This means that getting three in= a row is time boxed with FPNC.=C2=A0 Whereas "first seen" gives = dishonesty a home-field advantage every time.

The bitcoin protocol uses a mining difficulty that depends on a zer= o-prefix. As a result, this difficulty function consists of discrete jumps = that grow exponentially, and there are some very good reasons not to rely o= n this construct.=C2=A0 =C2=A0Instead of zeros, a range of floating-point v= alues, or fractional parts of whole numbers can be used as the difficulty c= ut-off,=C2=A0where any solution more difficult than the cut-off is still ac= cepted. Because the proof-of-work is no longer dependent on an arbitrary 0,= moving to an floating-point value range would allow block-formation to be = on an arbitrary time-schedule, which could be made slower or faster.=C2=A0 = The amount of time that a block can be withheld is proportional to the amou= nt of time it takes to generate,=C2=A0 therefore a faster block formation t= ime inturn limits the amount of time that a block can be withheld.=C2=A0 = =C2=A0If block formation is on average 30 seconds to 1 minute, then the amo= unt of time a miner can impact the network is capped at seconds instead of = minutes.=C2=A0 =C2=A0Although it doesn't stop withholding attacks, spee= ding up the dramatically limits the amount of time that any attacker can wi= thhold a block, thus mitigating the impact of malignant miners.=C2=A0 Speed= ing up block formation time while keeping inflation targets the same adds v= alue to users of the network.

Currently on the= BItcoin network, any malicious miner performing a withholding attack does = not need to be at the mercy of network conditions, and would be more succes= sful if they preemptively spread their delayed solution. With an artificial= ly-increased connection capacity a node can gain a visibility advantage on = the bitcoin network.=C2=A0 When this greedy miner sees that a competing min= er has released a block=20 =E2=80=94=20 then the greedy miner can pre-empt the spread of their=C2=A0delayed soluti= on and beat out any honest solution.=C2=A0 A miner using pre-emption to art= ificially spread their side of the consensus can ensure the=C2=A0adoption o= f their block because honest miners are=C2=A0dependent on natural topograph= y of the network to spread their messages =E2=80=94=20 a topography which is not optimized for speed. It isn't that the attac= ker is all powerful, it is that p2p networks have an inherent higher-latenc= y than centralized systems.=C2=A0 A miner can have a pre-computed map of th= e bitcoin network and then reach out and inform=C2=A0each node of the delay= ed block before the honest block has a chance to arrive.=C2=A0 Thus shaping= the disagreement in the favor of the malicious miner.=C2=A0 So long as a malicious miner has sufficient visibility, they unlock a luxur= y of subjecating=C2=A0would-be dissent and guaranteeing that their solution= is the one that always wins.=20

An attacker cannot choose their FPNC fitness valu= e, but they=C2=A0can choose when their block arrives and to whom. The "= ;first seen" approach to block adoption pressures malicious miners int= o a race of message propagation that convinces undecided nodes to work for = the=C2=A0dishonest chain. The race-condition in block arrival is fundamenta= lly resolved because the order in which=C2=A0blocks arrive doesn't influence the blo= ck's FPNC value. Therefore having clear disagreement resolution with FP= NC removes a feature of the network that can be leveraged to make sure that= a block-withholding attack supplants honest blocks.

By clarifying=C2=A0the rules in which blocks will be replaced=C2=A0 =E2=80=94 fewer disagreements will form. Without having a form of disagreem= ent resolution and leaving the process up to time, then nodes can be deputi= zed by malicious miners and aid in the mining of withheld blocks.
=

All the best,
-Michael
<= br>


--000000000000ef25a705b11a70b9--