MIME-Version: 1.0
From: Mike Brooks <m@ib.tc>
Date: Wed, 7 Oct 2020 21:04:08 -0700
Message-ID: <CALFqKjTY6d2nQtUe-NyyKJEYcWKEj1mfdQfAzKkB-NRDwYD5JQ@mail.gmail.com>
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ef25a705b11a70b9"
Subject: [bitcoin-dev] Progress on Miner Withholding - FPNC
Precedence: list

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

<div dir=3D"ltr"><div dir=3D"auto"><div dir=3D"ltr"><div>Hello Everyone,</d=
iv><div><br></div><div>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.</di=
v><div><br></div><div>But first of all, I&#39;d like to say that the idea f=
or FPNC came out of a conversation=C2=A0with ZmnSCPxj&#39;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.</div><div><=
br></div><div>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=
.</div><div><br></div><div><div dir=3D"auto">Currently, there is no way to =
resolve disagreements of the same block height in Bitcoin protocol.=C2=A0 F=
loating-point Nakamoto Consensus (<a href=3D"https://github.com/in-st/Float=
ing-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consen=
sus.pdf" target=3D"_blank">https://github.com/in-st/Floating-Point-Nakamoto=
-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf</a>) 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.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Using FPNC as=
 a method of disagreement resolution enables two features that provide bett=
er incentives over &quot;first seen.&quot; 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.</div></div><div><br></di=
v><div>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&#39;t incentivised on holding. The threa=
t of being replaced by a fair disagreement-resolution process, keeps all mi=
ners honest.</div><div><div><br></div><div>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&#39;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<br><div><div><b=
r></div><div>The question that is on everyone&#39;s mind: Does FPNC create =
new=C2=A0bad incentives? No, it only limits the bad incentives that already=
 exist in the protocol.</div><div>-&gt;</div><div>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 &quot;first seen&quot; gives =
dishonesty a home-field advantage every time.</div></div></div><div><br></d=
iv><div>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&#39;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.<br></div><div><br></div><div>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&#39;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

</div><div><br></div><div>An attacker cannot choose their FPNC fitness valu=
e, but they=C2=A0can choose when their block arrives and to whom. The &quot=
;first seen&quot; 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&#39;t influence the blo=
ck&#39;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.</div><div><br></div><d=
iv>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.<br></div>=
<div><br></div><div><div>All the best,</div></div><div>-Michael</div><div><=
br></div><div><br><br></div></div></div></div>
</div>

--000000000000ef25a705b11a70b9--