public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Bob McElrath <bob@mcelrath.org>
To: Mike Brooks <f@in.st.capital>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Date: Thu, 8 Oct 2020 18:43:00 +0000	[thread overview]
Message-ID: <20201008184259.GA25738@mcelrath.org> (raw)
In-Reply-To: <CAPaMHfTSqyDDBfmdM=z-FtLRTUxed2pNmoOFx-t2w0MyZ_mgCg@mail.gmail.com>

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 



  parent reply	other threads:[~2020-10-08 18:56 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-09-24 19:40 [bitcoin-dev] Floating-Point Nakamoto Consensus Mike Brooks
2020-09-25 15:18 ` bitcoin ml
2020-09-25 16:04   ` Mike Brooks
2020-09-25 16:33   ` Jeremy
2020-09-25 17:35     ` Mike Brooks
2020-09-26 10:11       ` David A. Harding
2020-09-26 11:09         ` Mike Brooks
2020-09-29  1:51 ` Franck Royer
2020-09-29 16:00   ` Mike Brooks
2020-09-30  6:31     ` ZmnSCPxj
2020-09-30  6:37       ` Mike Brooks
2020-09-30 23:44         ` ZmnSCPxj
2020-09-30 23:53           ` Mike Brooks
2020-10-01  1:36             ` ZmnSCPxj
     [not found]               ` <CALFqKjT_ZTnqzhvRRpFV4wzVf2pi=_G-qJvSkDmkZkhYwS-3qg@mail.gmail.com>
     [not found]                 ` <LPR_1lQZZGN-sT86purDUy8X_jF0XH35_xxdaqzRXHXPSZDtGVowS-FgIq1RN2mtT1Ds0bBErYvM-1TF7usCSAjojCCfkk5WOnZAvBLFzII=@protonmail.com>
     [not found]                   ` <CALFqKjR+uK2Rr4dUsL+D=ZUba2sroqnkhC1xcGHdjjupvDc7+Q@mail.gmail.com>
2020-10-01  6:47                     ` ZmnSCPxj
2020-10-04 15:58                       ` Mike Brooks
2020-10-01 16:42             ` Larry Ruane
2020-10-01 19:26               ` Mike Brooks
2020-09-29  3:10 ` LORD HIS EXCELLENCY JAMES HRMH
2020-10-10  1:26   ` Mike Brooks
2020-10-15 16:02     ` yanmaani
2020-10-08 18:43 ` Bob McElrath [this message]
2020-10-10  0:59   ` Mike Brooks

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20201008184259.GA25738@mcelrath.org \
    --to=bob@mcelrath.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=f@in.st.capital \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox