summaryrefslogtreecommitdiff
path: root/6c/c468d7e347c28ff002247cc5d711628b7ef6af
blob: 05835bedc86e3d680d1fff0381442f66a4f793a9 (plain)
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
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 66CF4B55
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 14 Dec 2016 16:27:01 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qk0-f176.google.com (mail-qk0-f176.google.com
	[209.85.220.176])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 526F6E3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 14 Dec 2016 16:27:00 +0000 (UTC)
Received: by mail-qk0-f176.google.com with SMTP id q130so26848699qke.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 14 Dec 2016 08:27:00 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=hcA6LBK5hOws65SPRL+gkhT2fQ0N9n/OrgBf7tc33v0=;
	b=WsOA/hooMRH2FGaB6m3nFVozNBuFnUgcNwHcRhohvhqTkkD3VUR2MfxnXZw4LdE4cx
	3hT5Vp4pkmxcBuvsZ1K4GZdb5LZ8+AUGLZTRxcB5pEkQzHKXeZqk1EARdMohefHr10i+
	DGVY8l+2MIleu1nEGJt0TC3C5VoJmvphJhCPzjpKWTDWNsmXvtr64rNoeECbuHwXTVw2
	nbioeWtQ7UMxZN5BeWdO9qCKFqahpETNYcpWD0AGly0BtrzxhUJJVBv7P1yOnr4iQC1k
	p3cia5mtcM52kUUKcX1x03tVpYe9NqAEqwfbrAuOt0XNoHp2N19eY9GMbS3Xzr9poNuo
	Rlqw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=hcA6LBK5hOws65SPRL+gkhT2fQ0N9n/OrgBf7tc33v0=;
	b=sQ7VYfjmnjVS/BM8GLBp+F3rFJd7KRxiemEuc31fhokAGCbLWSQ8MYbfA9fUScD4ez
	xoKRhv2zcQ0hoWYmOr1bCvhE+HTmqkZew5VFERuDowPRP9iWPw71MFkemEOgNaYQjYZx
	OT2H4geoUYMAd2LH4RGyIfzKmQdKBNozf/BQyg5SV276VBrqeLkUN06I2bXctmtoRs+J
	DBk0xn7pZpeUEculfwb7g0o8FsRPHRawsEH3sCc/m2pX7fimhxyGGQuxtPsi5p23Z4gP
	8DjtLHz6dkIG4dqf6Uis/fGLZIme8bAAf0SL/LE4vFxDeya3qUmqVTdJo2sv61qAHmoy
	lQqg==
X-Gm-Message-State: AKaTC013lxNG+noH0wuP/2rl/S2npRQrU0bFedBrrVseqi93zAv/5zRvhZuC93xPnC/NLJx/xP1+/Fv36AuDTw==
X-Received: by 10.55.154.200 with SMTP id c191mr88646989qke.117.1481732819515; 
	Wed, 14 Dec 2016 08:26:59 -0800 (PST)
MIME-Version: 1.0
Received: by 10.237.52.99 with HTTP; Wed, 14 Dec 2016 08:26:58 -0800 (PST)
In-Reply-To: <DB6F4DDF-1424-4FC4-84B3-5D16963E8589@xbt.hk>
References: <FB8593E6-3CD7-46D5-8FC8-A73A0EF1AE9A@xbt.hk>
	<CAE-z3OUpbUA2yviYoZouuZ0fp1WbbVdehWwNCd3juNsN-u9csA@mail.gmail.com>
	<201612102141.58206.luke@dashjr.org>
	<CAE-z3OX5QW0jy_ZvU7=onaVoynJrsuyeCdc=q7wj=d5O4XLO7Q@mail.gmail.com>
	<02E75CD7-24A8-4E2F-9466-B5497D0B77F8@xbt.hk>
	<CAE-z3OWEkwuxu+LiT1VsWDBnnoi5pQHDDiiKpi7i8oDOtPrB4A@mail.gmail.com>
	<DB6F4DDF-1424-4FC4-84B3-5D16963E8589@xbt.hk>
From: Tier Nolan <tier.nolan@gmail.com>
Date: Wed, 14 Dec 2016 16:26:58 +0000
Message-ID: <CAE-z3OXeV34SbE4AKknOVVcwEGDq22WO4iqfkQ2v3DCen1sP-Q@mail.gmail.com>
To: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/alternative; boundary=001a114d66245c04280543a0ce19
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE, 
	RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Forcenet: an experimental network with a new
	header format
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: Wed, 14 Dec 2016 16:27:01 -0000

--001a114d66245c04280543a0ce19
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Wed, Dec 14, 2016 at 3:45 PM, Johnson Lau <jl2012@xbt.hk> wrote:

> I think that=E2=80=99s too much tech debt just for softforkability.
>
> The better way would be making the sum tree as an independent tree with a
> separate commitment, and define a special type of softfork (e.g. a specia=
l
> BIP9 bit).
>

One of the problems with fraud proofs is withholding by miners.  It is
important that proof of publication/archive nodes check that the miners are
actually publishing their blocks.

If you place the data in another tree, then care needs to be taken that the
merkle path information can be obtained for that tree.

If an SPV node asks for a run of transactions from an archive node, then
the archive node can give the merkle branch for all of those transactions.
The archive node inherently has to check that tree.

The question is if there is a way to show that data is not available, but
without opening up the network to DOS.  If enough people run full nodes
then this isn't a problem.

>
> When the softfork is activated, the legacy full node will stop validating
> the sum tree. This doesn=E2=80=99t really degrade the security by more th=
an a
> normal softfork, as the legacy full node would still validate the total
> weight and nSigOp based on its own rules. The only purpose of the sum tre=
e
> is to help SPV nodes to validate. This way we could even completely
> redefine the structure and data committed in the sum tree.
>

Seems reasonable.  I think the soft-fork would have to have a timeout
before actually activating.  That would give SPV clients time to switch
over.

That could happen before the vote though, so it isn't essential.  The SPV
clients would have to support both trees and then switch mode.  Ensuring
that SPV nodes actually bother would be helped by proving that the network
actually intends to soft fork.

The SPV client just has to check that every block has at least one of the
commitments that it accepts so that it can understand fraud proofs.


>
> I=E2=80=99d like to combine the size weight and sigOp weight, but not sur=
e if we
> could. The current size weight limit is 4,000,000 and sigop limit is
> 80,000. It=E2=80=99s 50:1. If we maintain this ratio, and define
> weight =3D n * (total size +  3 * base size) + sigop , with n =3D 50
> a block may have millions of sigops which is totally unacceptable.
>

You multiplied by the wrong term.

weight =3D total size +  3 * base size + n * sigop , with n =3D 50

weight for max block =3D 8,000,000

That gives a maximum of 8,000,000 / 50 =3D 160,000 sigops.

To get that you would need zero transaction length.  You could get close if
you have transactions that just repeat OP_CHECKSIG over and over (or maybe
something with OP_CHECKMULTISIG).


>
> On the other hand, if we make n too low, we may allow either too few
> sigop, or a too big block size.
>
> Signature aggregation will make this a bigger problem as one signature ma=
y
> spend thousands of sigop
>
>
>
> On 14 Dec 2016, at 20:52, Tier Nolan <tier.nolan@gmail.com> wrote:
>
>
>
> On Wed, Dec 14, 2016 at 10:55 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>
>> In a sum tree, however, since the nSigOp is implied, any redefinition
>> requires either a hardfork or a new sum tree (and the original sum tree
>> becomes a placebo for old nodes. So every softfork of this type creates =
a
>> new tree)
>>
>
> That's a good point.
>
>
>> The only way to fix this is to explicitly commit to the weight and
>> nSigOp, and the committed value must be equal to or larger than the real
>> value. Only in this way we could redefine it with softfork. However, tha=
t
>> means each tx will have an overhead of 16 bytes (if two int64 are used)
>>
>
> The weight and sigop count could be transmitted as variable length
> integers.  That would be around 2 bytes for the sigops and 3 bytes for th=
e
> weight, per transaction.
>
> It would mean that the block format would have to include the raw
> transaction, "extra"/tree information and witness data for each transacti=
on.
>
> On an unrelated note, the two costs could be combined into a unified
> cost.  For example, a sigop could have equal cost to 250 bytes.  This wou=
ld
> make it easier for miners to decide what to charge.
>
> On the other hand, CPU cost and storage/network costs are not completely
> interchangeable.
>
> Is there anything that would need to be summed fees, raw tx size, weight
> and sigops that the greater or equal rule wouldn't cover?
>
> On 12 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>
> On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org> wrote:
>
>> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev
>> wrote:
>> > Any new merkle algorithm should use a sum tree for partial validation
>> and
>> > fraud proofs.
>>
>> PR welcome.
>>
>
> Fair enough.  It is pretty basic.
>
> https://github.com/luke-jr/bips/pull/2
>
> It sums up sigops, block size, block cost (that is "weight" right?) and
> fees.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
>
>

--001a114d66245c04280543a0ce19
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Wed, Dec 14, 2016 at 3:45 PM, Johnson Lau <span dir=3D"ltr">&lt;<a t=
arget=3D"_blank" href=3D"mailto:jl2012@xbt.hk">jl2012@xbt.hk</a>&gt;</span>=
 wrote:<br><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so=
lid rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"><div style=3D"=
word-wrap:break-word">I think that=E2=80=99s too much tech debt just for so=
ftforkability.<div><br></div><div>The better way would be making the sum tr=
ee as an independent tree with a separate commitment, and define a special =
type of softfork (e.g. a special BIP9 bit).</div></div></blockquote><div><b=
r></div><div>One of the problems with fraud proofs is withholding by miners=
.=C2=A0 It is important that proof of publication/archive nodes check that =
the miners are actually publishing their blocks.<br><br></div><div>If you p=
lace the data in another tree, then care needs to be taken that the merkle =
path information can be obtained for that tree.<br><br>If an SPV node asks =
for a run of transactions from an archive node, then the archive node can g=
ive the merkle branch for all of those transactions.=C2=A0 The archive node=
 inherently has to check that tree.<br><br></div><div>The question is if th=
ere is a way to show that data is not available, but without opening up the=
 network to DOS.=C2=A0 If enough people run full nodes then this isn&#39;t =
a problem.<br></div>=C2=A0<blockquote style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left:1px solid rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"=
><div style=3D"word-wrap:break-word"><div> When the softfork is activated, =
the legacy full node will stop validating the sum tree. This doesn=E2=80=99=
t really degrade the security by more than a normal softfork, as the legacy=
 full node would still validate the total weight and nSigOp based on its ow=
n rules. The only purpose of the sum tree is to help SPV nodes to validate.=
 This way we could even completely redefine the structure and data committe=
d in the sum tree.</div></div></blockquote><div><br></div><div>Seems reason=
able.=C2=A0 I think the soft-fork would have to have a timeout before actua=
lly activating.=C2=A0 That would give SPV clients time to switch over.=C2=
=A0 <br><br></div><div>That could happen before the vote though, so it isn&=
#39;t essential.=C2=A0 The SPV clients would have to support both trees and=
 then switch mode.=C2=A0 Ensuring that SPV nodes actually bother would be h=
elped by proving that the network actually intends to soft fork.<br><br></d=
iv><div>The SPV client just has to check that every block has at least one =
of the commitments that it accepts so that it can understand fraud proofs.<=
br></div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left:1px solid rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"=
><div style=3D"word-wrap:break-word"><div><br></div><div>I=E2=80=99d like t=
o combine the size weight and sigOp weight, but not sure if we could. The c=
urrent size weight limit is 4,000,000 and sigop limit is 80,000. It=E2=80=
=99s 50:1. If we maintain this ratio, and define</div><div>weight =3D n * (=
total size + =C2=A03 * base size) + sigop , with n =3D 50</div><div>a block=
 may have millions of sigops which is totally unacceptable.</div></div></bl=
ockquote><div><br></div><div>You multiplied by the wrong term.<br><br>weigh=
t =3D total size + =C2=A03 * base size + n * sigop , with n =3D 50<br><br><=
/div><div>weight for max block =3D 8,000,000<br></div><div><br></div><div>T=
hat gives a maximum of 8,000,000 / 50 =3D 160,000 sigops.<br><br></div><div=
>To get that you would need zero transaction length.=C2=A0 You could get cl=
ose if you have transactions that just repeat OP_CHECKSIG over and over (or=
 maybe something with OP_CHECKMULTISIG).<br></div><div>=C2=A0</div><blockqu=
ote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204=
);padding-left:1ex" class=3D"gmail_quote"><div style=3D"word-wrap:break-wor=
d"><div><br></div><div>On the other hand, if we make n too low, we may allo=
w either too few sigop, or a too big block size.</div><div><br></div><div>S=
ignature aggregation will make this a bigger problem as one signature may s=
pend thousands of sigop</div><div><div class=3D"gmail-h5"><div><br></div><d=
iv><br></div><div><br><div><blockquote type=3D"cite"><div>On 14 Dec 2016, a=
t 20:52, Tier Nolan &lt;<a target=3D"_blank" href=3D"mailto:tier.nolan@gmai=
l.com">tier.nolan@gmail.com</a>&gt; wrote:</div><br class=3D"gmail-m_-76442=
85980438085242Apple-interchange-newline"><div><div dir=3D"ltr"><br><div cla=
ss=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Dec 14, 2016 at 1=
0:55 AM, Johnson Lau <span dir=3D"ltr">&lt;<a target=3D"_blank" href=3D"mai=
lto:jl2012@xbt.hk">jl2012@xbt.hk</a>&gt;</span> wrote:<br><blockquote style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex" class=3D"gmail_quote"><div style=3D"word-wrap:break-word"><div>I=
n a sum tree, however, since the nSigOp is implied, any redefinition requir=
es either a hardfork or a new sum tree (and the original sum tree becomes a=
 placebo for old nodes. So every softfork of this type creates a new tree)<=
/div></div></blockquote><div><br></div><div>That&#39;s a good point.<br></d=
iv><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-le=
ft:1px solid rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"><div =
style=3D"word-wrap:break-word"><div>The only way to fix this is to explicit=
ly commit to the weight and nSigOp, and the committed value must be equal t=
o or larger than the real value. Only in this way we could redefine it with=
 softfork. However, that means each tx will have an overhead of 16 bytes (i=
f two int64 are used)</div></div></blockquote><div><br></div><div style=3D"=
word-wrap:break-word">The weight and sigop count could be transmitted as va=
riable length integers.=C2=A0 That would be around 2 bytes for the sigops a=
nd 3 bytes for the weight, per transaction.<br><br></div><div style=3D"word=
-wrap:break-word">It would mean that the block format would have to include=
 the raw transaction, &quot;extra&quot;/tree information and witness data f=
or each transaction.<br><br></div>On an unrelated note, the two costs could=
 be combined into a unified cost.=C2=A0 For example, a sigop could have equ=
al cost to 250 bytes.=C2=A0 This would make it easier for miners to decide =
what to charge.<br><br></div><div class=3D"gmail_quote">On the other hand, =
CPU cost and storage/network costs are not completely interchangeable.<br><=
br>Is there anything that would need to be summed fees, raw tx size, weight=
 and sigops that the greater or equal rule wouldn&#39;t cover?<br></div><di=
v class=3D"gmail_quote"><div style=3D"word-wrap:break-word"><br></div>On 12=
 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev &lt;<a target=3D"_blank" hr=
ef=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linux=
founda<wbr>tion.org</a>&gt; wrote:<div style=3D"word-wrap:break-word"><div>=
<blockquote type=3D"cite"><div><div class=3D"gmail-m_-7644285980438085242h5=
"><br class=3D"gmail-m_-7644285980438085242m_6699621031753262314Apple-inter=
change-newline"></div></div><div><div><div class=3D"gmail-m_-76442859804380=
85242h5"><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_qu=
ote">On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <span dir=3D"ltr">&lt;<a =
target=3D"_blank" href=3D"mailto:luke@dashjr.org">luke@dashjr.org</a>&gt;</=
span> wrote:<br><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"><span cla=
ss=3D"gmail-m_-7644285980438085242m_6699621031753262314gmail-">On Saturday,=
 December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:<br>
&gt; Any new merkle algorithm should use a sum tree for partial validation =
and<br>
&gt; fraud proofs.<br>
<br>
</span>PR welcome.<br></blockquote><div><br></div><div>Fair enough.=C2=A0 I=
t is pretty basic.<br><br><a target=3D"_blank" href=3D"https://github.com/l=
uke-jr/bips/pull/2">https://github.com/luke-jr/bip<wbr>s/pull/2</a><br><br>=
</div><div>It sums up sigops, block size, block cost (that is &quot;weight&=
quot; right?) and fees.<br></div></div></div></div></div></div><span>
______________________________<wbr>_________________<br>bitcoin-dev mailing=
 list<br><a target=3D"_blank" href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
ion.org">bitcoin-dev@lists.linuxfoundat<wbr>ion.org</a><br><a target=3D"_bl=
ank" href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev=
">https://lists.linuxfoundation.<wbr>org/mailman/listinfo/bitcoin-d<wbr>ev<=
/a><br></span></div></blockquote></div><br></div></div><br></div></div>
</div></blockquote></div><br></div></div></div></div></blockquote></div><br=
></div></div>

--001a114d66245c04280543a0ce19--