Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Pieter Wuille]

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

On Wednesday, October 7, 2020 1:31 PM, Mike Brooks via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

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

Greg Maxwell isn't on this list, but assuming this is about the conversion you've had on Bitcoin Core's security disclosure list, I believe this is a misrepresentation. The discussion has been mostly around a DoS attack report which turned out to be a mistake.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[ZmnSCPxj]

Good morning all,

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

This is my understanding:

The selfish mining attack described above was already presented and known about **many years** ago, with the solution presented here: https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf

The solution was later determined to actually raise the needed threshhold to 33%, not 25% in the paper.

That solution is what is used in the network today.

Implementing floating-point Nakamoto Consensus removes the solution presented in the paper, and therefore risks reintroducing the selfish mining attack.

Therefore, floating-point Nakamoto Consensus is a hard NAK.


Regards,
ZmnSCPxj

[bitcoin-dev] Progress on Miner Withholding - FPNC

[Mike Brooks]

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

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Önder Gürcan]

Hello all,

By the way, is this FPNC is similar to the way the current (or recent) code of Ethereum that is selecting branches based on the difficulty of the crypto puzzles solved to obtain the blocks of this branch without comparing the sizes of the subtrees?

Any ideas?

Best,

Önder


> On 8 Oct 2020, at 03:39, ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Good morning all,
> 
>> 
>> 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.
> 
> This is my understanding:
> 
> The selfish mining attack described above was already presented and known about **many years** ago, with the solution presented here: https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf
> 
> The solution was later determined to actually raise the needed threshhold to 33%, not 25% in the paper.
> 
> That solution is what is used in the network today.
> 
> Implementing floating-point Nakamoto Consensus removes the solution presented in the paper, and therefore risks reintroducing the selfish mining attack.
> 
> Therefore, floating-point Nakamoto Consensus is a hard NAK.
> 
> 
> Regards,
> ZmnSCPxj
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Mike Brooks]

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

Very interesting,

Block mixing did not resolve the selfish mining that is currently observed
on the network.  This mitigation was only intended to limit the maximum
impact of waiting for a 2nd block to be produced.

Rebalancing the selfish-mining incentives with FPNC and a faster block
creation time is the single best thing we can do to decentralize mining
efforts.  It will also produce a better network.



On Wed, Oct 7, 2020 at 6:40 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning all,
>
> >
> > 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.
>
> This is my understanding:
>
> The selfish mining attack described above was already presented and known
> about **many years** ago, with the solution presented here:
> https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf
>
> The solution was later determined to actually raise the needed threshhold
> to 33%, not 25% in the paper.
>
> That solution is what is used in the network today.
>
> Implementing floating-point Nakamoto Consensus removes the solution
> presented in the paper, and therefore risks reintroducing the selfish
> mining attack.
>
> Therefore, floating-point Nakamoto Consensus is a hard NAK.
>
>
> Regards,
> ZmnSCPxj
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Mike Brooks]

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

Pieter,

You are correct.

And also, I did prove what I set out to prove. The code provided privately
to the security team will in fact consume 99% of the CPU, which means it
does have an effect on the electorate.  It is true the node still
stubbornly passes messages, but I would argue that this is still very much
a problem that would concern operators, and perhaps the threshold for a
patch is much too high.  A layered security system like what is found in
bitcoin necessitates an attack chain.  The `getdata` message is an implicit
information disclosure that allows for the identification of dissenting
nodes.   As ZmnSCPxj pointed out, block mixing will give preemption at most
67% of the network, and the remaining dissenting nodes can be quelled by
maxing out their processing power.  All of this can be used together to
make sure that a withheld block becomes the prevailing solution.

FPNC rebalances incentives to serve the interests of the network, and
fundamentally resolves a class of abuses that reshape the electorate.  FPNC
will produce a more deceliterized and fair network than "first seen."

Cheers,
Mike

On Wed, Oct 7, 2020 at 5:12 PM Pieter Wuille <bitcoin-dev@wuille.net> wrote:

> On Wednesday, October 7, 2020 1:31 PM, Mike Brooks via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> 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.
>
>
> Greg Maxwell isn't on this list, but assuming this is about the conversion
> you've had on Bitcoin Core's security disclosure list, I believe this is a
> misrepresentation. The discussion has been mostly around a DoS attack
> report which turned out to be a mistake.
>
> Cheers,
>
> --
> Pieter
>
>
>

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