1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
Return-Path: <bob@mcelrath.org>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 3A3CFC0051
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Oct 2020 18:56:03 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by whitealder.osuosl.org (Postfix) with ESMTP id 2872887046
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Oct 2020 18:56:03 +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 nDiZ3A0kwSjm
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Oct 2020 18:56:02 +0000 (UTC)
X-Greylist: delayed 00:12:59 by SQLgrey-1.7.6
Received: from mcelrath.org (moya.mcelrath.org [50.31.3.130])
by whitealder.osuosl.org (Postfix) with ESMTPS id 6113F86E0A
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Oct 2020 18:56:02 +0000 (UTC)
Received: from mcelrath.org (localhost [127.0.0.1])
by mcelrath.org (8.14.4/8.14.4/Debian-8+deb8u2) with ESMTP id 098Ih0gf000636
(version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT);
Thu, 8 Oct 2020 18:43:00 GMT
Received: (from mcelrath@localhost)
by mcelrath.org (8.14.4/8.14.4/Submit) id 098Ih0eK000635;
Thu, 8 Oct 2020 18:43:00 GMT
X-Authentication-Warning: mcelrath.org: mcelrath set sender to
bob@mcelrath.org using -f
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 08 Oct 2020 18:56:03 -0000
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
|
