Re: [bitcoin-dev] Floating-Point Nakamoto Consensus

[Mike Brooks <m@ib.tc>]

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

Hey Bob McElarth,

I appreciate this discussion.  The issues with chain thrashing was
explicitly addressed with heredity, I saw this problem, and there is an
elegant solution here.

Sorry that summation process wasn't made clear in the paper, I'll be sure
to go back and improve this.   Here is a full implementation which should
resolve the confusion around the summation of fitness scores:
   https://github.com/bitcoin/bitcoin/pull/19665/files

There is however a minor mistake in the code and in the paper.  We have
changed our position a bit after Franck Royer's post on this thread.   I
think generally optimizing for lower value is a better approach as this
resolves the procession of difficulty when producing blocks across an epoch
divide.  Optimizing for a higher non-zero value would place a non-zero at
the most significant octet, which is avoided by optimizing for a lower
overall numeric value of the solution.  Or, put another way; the lowest
base10 numeric summation of both chains starting at the point of their
disagreement.

The main point here is that the work w is an unbiased statistical estimator
> for
> the number of sha256d computations performed by the network. It is truly a
> measurement of "work". The fitness f is a *biased* estimator for exactly
> the
> same thing, and other than introducing statistical bias, provides no
> additional
> information of any value.
>

FPNC is an extension of the same measure of work, any criticism of
zero-prefix in base16 should also be a criticism of zero-prefix in base2 or
any other base.  A change in base should not affect the bias, and
optimizing for a lower value in big-endian has a continuous difficulty
curve. So long as sha2564 remains ideal no bias will be introduced.

The fundamental question of FPNC as I understand it is: should we introduce
> the
> historic block hash h as a consensus-critical parameter?
>
> The answer is a strict no: This quantity f (fitness) is purely random, and
> does
> not in any way favor the "honest" chain, nor can it identify it. Between
> two
> competing chains, the amount of bias on one chain vs. the other is purely
> random
> and does *not* reflect more work done by one side or the other. Nor can it
> have
> any knowledge of things like network splits.
>

A zero-prefix has the direct effort of lowering the big-endian base16 value
of the hash, and with each epoch the numeric value of the solution is
further decreased. A floating-point evaluation introduces the concept that
no two blocks can ever be of equal value unless they are in fact the same
hash value.  We are in full agreement with the statement you made above,
there is nothing intrinsic about the honest chain vs any other chain —
nodes are acting on an empirical evaluation.  It should only take 10-20
seconds of propagation for every node on the global network to see every
solution block, if we remove ambiguity and make sure that no two blocks are
the same value, since all nodes see all solutions they should all choose
the same highest-value solution.


> At constant difficulty assuming two competing chains with exactly the same
> number of blocks and amount of hashpower, this bias will oscillate,
> sometimes
> favoring one side, sometimes favoring the other. Unlike work, this bias is
> not
> cumulative. Each side will over time converge to having the same amount of
> bias
> from any biased estimator such as f constructed from the hashes h. Just
> because
> one side had an abnormally small hash doesn't mean the other side won't
> have a
> similar abnormally low hash. The expectation value for the amount of bias
> is
> equal on both sides.


Ah!  Yes!  Thank you so much for bringing this up.  This is the single most
important part of the entire soltuion, and I am so happy to have this
discussion.   If this solution was simply labeling one side a winner and
another side a loser, then there is no incentive for mining efforts to
migrate, and with the incentives of sunken cost into mining would be enough
to keep nodes from switching.  So If the solution was simply a label then
your statement above would be correct...  However, this exact situation was
taken into consideration.

In the current protocol clients always choose the chain of greatest value,
because trying mine a full block behind would require more than 50% of the
network power to "catch up."  No miner in their right mind would choose to
be behind the network.   If this evaluation is made on the floating-point
scale, as in not whole numbers and not whole blocks — then the exact same
properties of behind still come into play.  No miner chooses to mine from
N-1 blocks, because they would be behind, just as no miner would choose to
mine from a N-0.5 block.   The threat of generating a loser block from a
loser parent outweighs any other incentive.  The heredity of block fitness
creates convergence on the most valuable chain.  When looking at the
electorate over time, more miners will choose to mine with the higher-value
coinbase - thus eroding support for the computational effort needed to
sustain the disagreement.  No thrashing will happen, because no miner has
incentives for this to happen.

Nodes on the network cannot know the history of a block or why it was
produced,  but through an empirical measure of value we can have a protocol
that avoids ambiguity in the block selection process and prevents
disagreement from forming.   Ambiguity in block selection is also
exploitable, through pre-emption one solution can dominate a "first seen"
system, and any dissent can be silenced with DoS.  But using
resource-consumption attacks and the exploitation of a race-condition to
gain an edge isn't helpful if there isn't a disagreement to shape. The
disagreement here is powerful miners trying to prove each other wrong, but
if they had a more accurate measure of value — there would be no reason to
ever disagree.

All the best,
Michael

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