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