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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
Return-Path: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 00688CA8
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 4 Oct 2019 23:31:56 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com
[209.85.221.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3D546A8
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 4 Oct 2019 23:31:55 +0000 (UTC)
Received: by mail-wr1-f41.google.com with SMTP id r3so9001944wrj.6
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 04 Oct 2019 16:31:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=9CAodXU3yiL6zRBsU4D9uDPbowLgoyXfDtoZP3A8oB4=;
b=BZL/GDOKjJ4jwMEoUOgRF9S5ZY1zuw4D4FdqXEJ+wd9yfFS5t81HHYT2ZlHBf6+9es
62h2wImIrBWDDQlUWC+kgqoQxpvyXPeiGbZPSN8ECv4m0YdexA2PiIP24kDl2MZeyj7e
3yH7dM+i7M4boQW0d6QDZMp+5GcWXpzU5CWxewQQLqx+DCqtlrhJr+Iz5lY9+Sd9r5Sm
LRGxbqbtn4Qx23o8SfnPCjQE1L2fgKsrUlw3eS5I0QO9Z3Mp+QS+6zhO4ese/AjLo81f
oEB2F7cFYrAowAyqMvDreByGXR7CVD7di+BO1FcV/Y2bxxEP9TObauTnSQBZh8Z4GwGG
AEDg==
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;
bh=9CAodXU3yiL6zRBsU4D9uDPbowLgoyXfDtoZP3A8oB4=;
b=nxne1K1VZnyOBiWLWY0/NUToNTyoDJkGZVcYX30hq9MG7f9VeYewjGiaKbqTL6lJbG
AAoFdGA2/qkJ7U73HTvGFKkXvFYhIzNQVwKdxzP1ef7dVDaPg9sph7Ndkae5CcPWDlDQ
Xj6L99HK8Mbol3bkz4NYP3im0wqot3lQynNXS2G2uHlX7JJoLVoLzkBVJjsfTinmmZ7v
B28A/ZBqILqt2OfDR14rGLbrxNuic1RcrKuF8BixSei9sXQGbsqs3UfGbK+vPuwo9vq7
TZZEHRPvOSJP9BtGMt74nj8uxPqrm6p1LZzxUf1dnsQvn7HgyiMSA/qBSD4RZ6xNkBq7
RK8w==
X-Gm-Message-State: APjAAAVDxGcb7Es48XBX91secIxq6JgVSMD3iienjGu29Vp4vAktg76p
xGvrVZ7i9CDVakjdWLg78Nf3bj+QVag5nU6CRnbU7kdg
X-Google-Smtp-Source: APXvYqw7/heQGqMv6/BGDVwjryWMOSE2zxfNr2qRx0OvQls4HQfXfyTc36Me6xDceRIxzlkxySidor6k6YDtxuaVRdE=
X-Received: by 2002:a5d:4c45:: with SMTP id n5mr14402713wrt.100.1570231913576;
Fri, 04 Oct 2019 16:31:53 -0700 (PDT)
MIME-Version: 1.0
References: <42cd5ffd-63e8-b738-c4ea-13d0699b1268@purse.io>
In-Reply-To: <42cd5ffd-63e8-b738-c4ea-13d0699b1268@purse.io>
From: Tier Nolan <tier.nolan@gmail.com>
Date: Sat, 5 Oct 2019 00:31:18 +0100
Message-ID: <CAE-z3OV_LL+Jww3e=gO6t=02VW7m9PK+8EaYoEVLy9NKNMiSaQ@mail.gmail.com>
To: Braydon Fuller via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000006c7d8e05941e1bea"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM,
HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Chain width expansion
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Fri, 04 Oct 2019 23:31:56 -0000
--0000000000006c7d8e05941e1bea
Content-Type: text/plain; charset="UTF-8"
Are you assuming no network protocol changes?
At root, the requirement is that peers can prove their total chain POW.
Since each block has the height in the coinbase, a peer can send a short
proof of height for a disconnected header and could assert the POW for that
header.
Each peer could send the the N strongest headers (lowest digest/most POW)
for their main chain and prove the height of each one.
The total chain work can be estimated as N times the POW for the lowest in
the list. This is an interesting property of how POW works. The 10th best
POW block will have about 10% of the total POW.
The N blocks would be spread along the chain and the peer could ask for all
headers between any 2 of them and check the different in claimed POW. If
dishonesty is discovered, the peer can be banned and all info from that
peer wiped.
You can apply the rule hierarchically. The honest peers would have a much
higher POW chain. You could ask the peer to give you the N strongest
headers between 2 headers that they gave for their best chain. You can
check that their height is between the two limits.
The peer would effectively be proving their total POW recursively.
This would require a new set of messages so you can request info about the
best chain.
It also has the nice feature that it allows you to see if multiple peers
are on the same chain, since they will have the same best blocks.
The most elegant would be something like using SNARKS to directly prove
that your chain tip has a particular POW. The download would go tip to
genesis, unlike now when it is in the other direction.
------------------------------------------------------------------------
In regard to your proposal, I think the key is to limit things by peer,
rather than globally.
The limit to header width should be split between peers. If you have N
outgoing peers, they get 1/N of your header download resources each.
You store the current best/most POW header chain and at least one
alternative chain per outgoing peer.
You could still prune old chains based on POW, but the best chain and the
current chain for each outgoing peer should not be pruned.
The security assumption is that a node is connected to at least one honest
node.
If you split resources between all peers, then it prevents the dishonest
nodes from flooding and wiping out the progress for the honest peer.
- Message Limiting -
I have the same objection here. The message limiting should be per peer.
An honest peer who has just been connected to shouldn't suffer a penalty.
Your point that it is only a few minutes anyway may make this point moot
though.
--0000000000006c7d8e05941e1bea
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Are you assuming no network protocol changes?</div><d=
iv><br></div><div>At root, the requirement is that peers can prove their to=
tal chain POW.</div><div><br></div><div>Since each block has the height in =
the coinbase, a peer can send a short proof of height for a disconnected he=
ader and could assert the POW for that header.</div><div><br></div><div>Eac=
h peer could send the the N strongest headers (lowest digest/most POW) for =
their main chain and prove the height of each one.=C2=A0 <br></div><div><br=
></div><div>The total chain work can be estimated as N times the POW for th=
e lowest in the list.=C2=A0 This is an interesting property of how POW work=
s.=C2=A0 The 10th best POW block will have about 10% of the total POW.<br><=
/div><div><br></div><div>The N blocks would be spread along the chain and t=
he peer could ask for all headers between any 2 of them and check the diffe=
rent in claimed POW.=C2=A0 If dishonesty is discovered, the peer can be ban=
ned and all info from that peer wiped.</div><div><br></div><div>You can app=
ly the rule hierarchically.=C2=A0 The honest peers would have a much higher=
POW chain.=C2=A0 You could ask the peer to give you the N strongest header=
s between 2 headers that they gave for their best chain.=C2=A0 You can chec=
k that their height is between the two limits.</div><div><br></div><div>The=
peer would effectively be proving their total POW recursively.<br></div><d=
iv><br></div><div>This would require a new set of messages so you can reque=
st info about the best chain.</div><div><br></div><div>It also has the nice=
feature that it allows you to see if multiple peers are on the same chain,=
since they will have the same best blocks.<br></div><div><br></div><div>Th=
e most elegant would be something like using SNARKS to directly prove that =
your chain tip has a particular POW.=C2=A0 The download would go tip to gen=
esis, unlike now when it is in the other direction.<br></div><div><br></div=
><div>---------------------------------------------------------------------=
---<br></div><div><br></div><div>In regard to your proposal, I think the ke=
y is to limit things by peer, rather than globally.</div><div><br></div><di=
v>The limit to header width should be split between peers.=C2=A0 If you hav=
e N outgoing peers, they get 1/N of your header download resources each.</d=
iv><div><br></div><div>
You store the current best/most POW header chain and at least one alternati=
ve chain per outgoing peer.=C2=A0=20
</div><div><br></div><div>
You could still prune old chains based on POW, but the best chain and the c=
urrent chain for each outgoing peer should not be pruned.<br></div><div><br=
>
</div><div>The security assumption is that a node is connected to at least =
one honest node.</div><div><br></div><div>If you split resources between al=
l peers, then it prevents the dishonest nodes from flooding and wiping out =
the progress for the honest peer.<br></div><div><br></div><div>- Message Li=
miting -</div><div><br></div><div>I have the same objection here.=C2=A0 The=
message limiting should be per peer.</div><div><br></div><div>An honest pe=
er who has just been connected to shouldn't suffer a penalty.</div><div=
><br></div><div>Your point that it is only a few minutes anyway may make th=
is point moot though.<br></div></div>
--0000000000006c7d8e05941e1bea--
|
