From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 45065C0051 for ; Fri, 9 Oct 2020 17:15:31 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 40CFD8780A for ; Fri, 9 Oct 2020 17:15:31 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id oJZpqkHT1VFo for ; Fri, 9 Oct 2020 17:15:30 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wm1-f53.google.com (mail-wm1-f53.google.com [209.85.128.53]) by whitealder.osuosl.org (Postfix) with ESMTPS id A0BD587809 for ; Fri, 9 Oct 2020 17:15:29 +0000 (UTC) Received: by mail-wm1-f53.google.com with SMTP id e23so3523775wme.2 for ; Fri, 09 Oct 2020 10:15:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ib.tc; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=2GtoX9TpFqGsJI/0gDC8iVraC0zwzhpLLmz7xM68C8I=; b=l6QahpvWOyyiWPbBIxb4Nm6o1z3Gynhvg0X/SOuHkgrkmj9L1vt0n1tyNrMvSv5dA6 PWISbROZhq6lKFjFvkMMlPmQT3Qq7p3p5L4aKEWtIz7ZUpBFf4BZUVYotPBFhKFyrWr7 p75Gx8GwYODMFfj39AGMJjtyfYKYlYBATLoiX9dq3ss3qqLBLiIm47gfezhNaBfLOKOw j23F6DHLE+JGf7X1GndU9+2af4ijsY8oN97NQnvt3ypTrlymhRUruF5AaiS37TEpN5m7 df8MBfQJEtEE+2MDzwKnVoXA09vD/ECGIDPbr3NpS5pZwjpYqnnm2FY44oldj0MQREXv Lz2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=2GtoX9TpFqGsJI/0gDC8iVraC0zwzhpLLmz7xM68C8I=; b=gQPR+AriGBtj0026+hvtr0FD5CqB9T0mZsH5SKVsrMGXDenhUN3P3q6fHlhRBBVtjD IheuSUne812efgWHOhAaUKlju5SXs/NQ87Mh9Fh4CEj4uXdyo4MwTjoCkUJw86DbZ2n2 /PCHbC+Bz8N2l3BcyIrjA6kISsxBwEz+Q6E0wxdyEBLBdAm6VZlyrDQwNfZ1Mk88tyyy r1eWCU2qspv65HDmR/D5Ua/M8HFspTPrQ3XK4pHWaGFL1m3gVZDuF0vr4zxj+hetGFUV NcOGeWAQf/ByaK3E3t7Si6CSyMgU+1tZWimQw1SUaxyaMtpMm5A2btRUlB3nSwSxg1Xr RuDQ== X-Gm-Message-State: AOAM5313UNtTQZXg8GyvRaLyjsZJaoS4/vlNGuQ4ltO2n2xDU2H/HDl9 Jd/3uDPx9dbR7tKML425VnTw5/MwulrkULLy8cY8O6nW6rWMFg== X-Google-Smtp-Source: ABdhPJxPi4TcFWiLKOIf0gK/WGH0Y0LPP/8ZRGM2Wi9U1du3Xa76+pZQNhYD7i+z0zfXZImqzl8F5VFDkxIz5UdgMwI= X-Received: by 2002:a7b:cb44:: with SMTP id v4mr15222416wmj.101.1602263727788; Fri, 09 Oct 2020 10:15:27 -0700 (PDT) MIME-Version: 1.0 References: <20201008184259.GA25738@mcelrath.org> In-Reply-To: <20201008184259.GA25738@mcelrath.org> From: Mike Brooks Date: Fri, 9 Oct 2020 17:59:31 -0700 Message-ID: To: Bob McElrath , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="00000000000054ebd005b1401896" X-Mailman-Approved-At: Fri, 09 Oct 2020 17:47:01 +0000 Cc: Mike Brooks Subject: Re: [bitcoin-dev] Floating-Point Nakamoto Consensus X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Oct 2020 17:15:31 -0000 --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
Hey Bob McElarth,

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.

Sorry that su= mmation process wasn't made clear in the paper, I'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=A0https://github.com/bitcoin/bitcoin/pull/19665/files

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'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

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

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.

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 r= andom
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= =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.
=C2= =A0
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
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 bec= ause
one side had an abnormally small hash doesn't mean the other side won&#= 39;t have a
similar abnormally low hash. The expectation value for the amount of bias i= s
equal on both sides.

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

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 "catch up."=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.

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 "first seen" 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't helpful if the= re isn'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=

All the best,
Michael
--00000000000054ebd005b1401896--