Date: Thu, 8 Oct 2020 18:43:00 +0000
From: Bob McElrath <bob@mcelrath.org>
To: Mike Brooks <f@in.st.capital>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20201008184259.GA25738@mcelrath.org>
References: <CAPaMHfTSqyDDBfmdM=z-FtLRTUxed2pNmoOFx-t2w0MyZ_mgCg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAPaMHfTSqyDDBfmdM=z-FtLRTUxed2pNmoOFx-t2w0MyZ_mgCg@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Subject: Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Precedence: list

A diversion on statistics:

There are two quantities available for consensus:
    t   target difficulty
    h   block hash where h < t
From these we can form two quantities that might be used in consensus:
    w   work    = log(sum(1/t_i))
    f   fitness = log(sum(1/h_i))   (term used by authors)

(The original authors do not specify mathematically how they obtain their
numbers -- but it doesn't really matter, fundamentally, they want to use the
block hash h instead of t) Bitcoin introduces some constants in the above sums
which I omit for clarity.

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.

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.

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.

Therefore, hard NACK on using h in this way and FPNP. At best it introduces
unecessary randomness into the chain selection process, at worst it proves a new
game to be played by miners. As a consensus critical change, it's also
incredibly risky to push through without some very serious advantage, which this
does not have.

--
Cheers, Bob McElrath

"For every complex problem, there is a solution that is simple, neat, and wrong."
    -- H. L. Mencken