MIME-Version: 1.0
References: <CAPaMHfTSqyDDBfmdM=z-FtLRTUxed2pNmoOFx-t2w0MyZ_mgCg@mail.gmail.com>
 <20201008184259.GA25738@mcelrath.org>
In-Reply-To: <20201008184259.GA25738@mcelrath.org>
From: Mike Brooks <m@ib.tc>
Date: Fri, 9 Oct 2020 17:59:31 -0700
Message-ID: <CALFqKjR0PoWtgGKvng907nZ04SsiQ3j50z7PKMwqdbBXQxSMWQ@mail.gmail.com>
To: Bob McElrath <bob@mcelrath.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000054ebd005b1401896"
Cc: Mike Brooks <f@in.st.capital>
Subject: Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Precedence: list

--00000000000054ebd005b1401896
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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, an=
d
> 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 i=
t
> 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 =E2=80=
=94
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 sam=
e
> number of blocks and amount of hashpower, this bias will oscillate,
> sometimes
> favoring one side, sometimes favoring the other. Unlike work, this bias i=
s
> not
> cumulative. Each side will over time converge to having the same amount o=
f
> 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 =E2=80=94 then the exac=
t 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 =E2=80=94 there would be no re=
ason to
ever disagree.

All the best,
Michael

--00000000000054ebd005b1401896
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">Hey Bob McElarth,<div><br></div><div>I ap=
preciate=C2=A0this discussion.=C2=A0 The issues with chain thrashing was ex=
plicitly=C2=A0addressed with heredity, I saw this problem, and there is an =
elegant=C2=A0solution=C2=A0here.<br></div><div><br></div><div>Sorry that su=
mmation process wasn&#39;t made clear in the paper, I&#39;ll be sure to go =
back and improve this.=C2=A0 =C2=A0Here is a full implementation=C2=A0which=
 should resolve=C2=A0the confusion around the summation of fitness scores:<=
br>=C2=A0 =C2=A0<a href=3D"https://github.com/bitcoin/bitcoin/pull/19665/fi=
les">https://github.com/bitcoin/bitcoin/pull/19665/files</a><br><div><br></=
div><div>There is however a minor mistake in the code and in the paper.=C2=
=A0 We have changed our position a bit after Franck Royer&#39;s post on thi=
s thread.=C2=A0 =C2=A0I think generally=C2=A0optimizing for lower value is =
a better approach as this resolves the procession=C2=A0of difficulty when p=
roducing blocks across=C2=A0an epoch divide.=C2=A0 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.=
=C2=A0 Or, put another way; the lowest base10 numeric summation of both cha=
ins starting at the point of their disagreement.=C2=A0</div><div></div><div=
><br></div></div></div><div class=3D"gmail_quote"><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex">The main point here is that the work w is an unbia=
sed statistical estimator for<br>
the number of sha256d computations performed by the network. It is truly a<=
br>
measurement of &quot;work&quot;. The fitness f is a *biased* estimator for =
exactly the<br>
same thing, and other than introducing statistical bias, provides no additi=
onal<br>
information of any value.<br></blockquote><div><br></div><div>FPNC is an ex=
tension 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.=C2=
=A0 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=C2=A0ideal no bias will be introduced.</div><div><br></div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px=
 solid rgb(204,204,204);padding-left:1ex">
The fundamental question of FPNC as I understand it is: should we introduce=
 the<br>
historic block hash h as a consensus-critical parameter?<br>
<br>
The answer is a strict no: This quantity f (fitness) is purely random, and =
does<br>
not in any way favor the &quot;honest&quot; chain, nor can it identify it. =
Between two<br>
competing chains, the amount of bias on one chain vs. the other is purely r=
andom<br>
and does *not* reflect more work done by one side or the other. Nor can it =
have<br>
any knowledge of things like network splits.<br></blockquote><div><br></div=
><div>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=
=C2=A0is further decreased. A floating-point evaluation introduces the conc=
ept that no two blocks can ever be of equal value unless they are in fact t=
he same hash value.=C2=A0 We are in full agreement with the statement you m=
ade above, there is nothing intrinsic about the honest chain vs any other c=
hain=C2=A0=E2=80=94 nodes are acting on an empirical=C2=A0evaluation.=C2=A0=
 It should only take 10-20 seconds of propagation for every node on the glo=
bal network to see every solution block, if we remove ambiguity and make su=
re that no two blocks are the same value, since all nodes see all solutions=
 they should all choose the same highest-value solution.<br></div><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex">
At constant difficulty assuming two competing chains with exactly the same<=
br>
number of blocks and amount of hashpower, this bias will oscillate, sometim=
es<br>
favoring one side, sometimes favoring the other. Unlike work, this bias is =
not<br>
cumulative. Each side will over time converge to having the same amount of =
bias<br>
from any biased estimator such as f constructed from the hashes h. Just bec=
ause<br>
one side had an abnormally small hash doesn&#39;t mean the other side won&#=
39;t have a<br>
similar abnormally low hash. The expectation value for the amount of bias i=
s<br>
equal on both sides.</blockquote><div><br></div><div>Ah!=C2=A0 Yes!=C2=A0 T=
hank you so much for bringing this up.=C2=A0 This is the single most import=
ant part of the entire soltuion, and I am so happy to have this discussion.=
=C2=A0 =C2=A0If this solution was simply labeling one side a winner and ano=
ther side a loser, then there is no incentive=C2=A0for mining efforts to mi=
grate, and with the incentives of sunken cost into mining would be enough t=
o keep nodes from switching.=C2=A0 So If the solution was simply a label th=
en your statement above would be correct...=C2=A0 However, this exact situa=
tion=C2=A0was taken into consideration.=C2=A0</div><div><br></div><div>In t=
he current protocol clients always choose the chain of greatest value, beca=
use trying mine a full block behind would require more than 50% of the netw=
ork power to &quot;catch up.&quot;=C2=A0 No miner in their right mind would=
 choose=C2=A0to be behind the network.=C2=A0 =C2=A0If this evaluation is ma=
de on the floating-point scale, as in not whole numbers and not whole block=
s=C2=A0=E2=80=94 then the exact same properties of behind still come into p=
lay.=C2=A0 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.=C2=A0 =C2=
=A0The threat of generating a loser block from a=C2=A0 loser parent outweig=
hs any other incentive.=C2=A0 The heredity of block fitness creates converg=
ence on the most valuable chain.=C2=A0 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 disagre=
ement.=C2=A0 No thrashing will happen, because no miner has incentives for =
this to happen.<br></div><div><br></div><div>Nodes on the network cannot kn=
ow the history of a block or why it was produced,=C2=A0 but through an empi=
rical measure of value we can have a protocol that avoids ambiguity in the =
block selection process and prevents disagreement from forming.=C2=A0 =C2=
=A0Ambiguity in block selection is also exploitable, through pre-emption on=
e solution can dominate a &quot;first seen&quot; system, and any dissent ca=
n be silenced with DoS.=C2=A0 But using resource-consumption attacks and th=
e exploitation of a race-condition to gain an edge isn&#39;t helpful if the=
re isn&#39;t a disagreement to shape. The disagreement here is powerful min=
ers trying to prove each other wrong, but if they had a more accurate measu=
re of value=C2=A0=E2=80=94 there would be no reason to ever disagree.=C2=A0=
</div><div><br></div><div>All the best,</div><div>Michael</div></div></div>

--00000000000054ebd005b1401896--