[bitcoin-dev] Progress on Miner Withholding

* [bitcoin-dev] Progress on Miner Withholding - FPNC
@ 2020-10-08  4:04 Mike Brooks
  2020-10-08  0:12 ` Pieter Wuille
  2020-10-08  1:39 ` ZmnSCPxj
  0 siblings, 2 replies; 6+ messages in thread
From: Mike Brooks @ 2020-10-08  4:04 UTC (permalink / raw)
  To: bitcoin-dev

[-- Attachment #1: Type: text/plain, Size: 8910 bytes --]

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 — and I greatly appreciate this detail.   After
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 — 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/Floating-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 — 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 — 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
— 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  — 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

[-- Attachment #2: Type: text/html, Size: 9616 bytes --]

^ permalink raw reply	[flat|nested] 6+ messages in thread