summaryrefslogtreecommitdiff
path: root/a1/3833b2048ba35f7cce87bf022164cc41903fbf
blob: a6f509f4ccbd3a0383dae946b61a9b5142b8ba70 (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
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 21B6A97A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 14:23:33 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f52.google.com (mail-it0-f52.google.com
	[209.85.214.52])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 62EA3685
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 14:23:31 +0000 (UTC)
Received: by mail-it0-f52.google.com with SMTP id n202-v6so3314273ita.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 07:23:31 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=blockstream.io; s=google;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=Cs2udz2wg4m9v4wxdNzmcJ1kPNVvyVDjVufBGzI9kxU=;
	b=GkpG4Uc4VFyOlpYoJEuRw0uz+rHmRT6NbtPM01gRpl4Sgvg0UsAnZUQ/fR6w8wbn9O
	t4gHA1hL3JCVlub5taF1PWm8fZqMyGdAM0sBPH+inzIQV8qavcOb3s2AIB1JwkCPugpm
	1pRa4GVwEqVSWvgcvjieSmkMmh/Bp7Lb6eY9A=
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;
	bh=Cs2udz2wg4m9v4wxdNzmcJ1kPNVvyVDjVufBGzI9kxU=;
	b=GuvL3PkRbCqjbdZjkaAz4gk6qijN1EiBwjeoYmXHEF8Me+rg+ibHfL46hAMk4KTymi
	GNdxAsIK7AA0sn8KGwGPS+SRKAkKLAcW2GmAZNqtoiDFdgTdyz8/2FdvjumN+djSDHn2
	QTdyFpFOFZVIap+i/myGqoc0Jpa+RF5FA/oAVAWcJUJ+kDlAIl0ah3KCxclmumaZ0UwY
	jsEvvNO0UHel2kCmr5W94tMusDQJFsOi5W4s+078/xt00t5rMQixQHsAXnGurxR5hb5d
	GmFfIIa3V1C1iRRNsK1EM09c/I42UwTnhkfz21+rTNa/SbeKT73SubkTrMsjN+CMWeNa
	mMaA==
X-Gm-Message-State: ALKqPwcVkwOkfFBJEr5CdQ+EqF8IOAaABbP6GNLBN3eaKdW4rH5WVw/0
	t0I6UZoJch1bV1vzCR7MERZEPKGit+r9sJZseN0AT2aVLDU=
X-Google-Smtp-Source: AB8JxZo0/1DLOrXwXlntkEcjgXGpg2fAhDDVmwJmA0fIX8mRMueF44eqghqB+pi5NxnVdb9I5Gix58wLI6rfwd+ZrCk=
X-Received: by 2002:a24:4522:: with SMTP id
	y34-v6mr2118357ita.74.1525962210486; 
	Thu, 10 May 2018 07:23:30 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a02:1086:0:0:0:0:0 with HTTP; Thu, 10 May 2018 07:23:09
	-0700 (PDT)
In-Reply-To: <20180510121027.GA17607@erisian.com.au>
References: <20180510121027.GA17607@erisian.com.au>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 10 May 2018 10:23:09 -0400
Message-ID: <CAMZUoKnPVz+XOq-cQRQuLbCuqn4H28WSMXCK3Rnt8VVivedYCw@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000007f475b056bdac37d"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,
	T_TVD_FUZZY_SECURITIES 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] MAST/Schnorr related soft-forks
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: Thu, 10 May 2018 14:23:33 -0000

--0000000000007f475b056bdac37d
Content-Type: text/plain; charset="UTF-8"

Thanks for writing this up Anthony.

Do you think that a CHECKSIGFROMSTACK proposal should be included within
this discussion of signature soft-forks, or do you see it as an unrelated
issue?

CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See
http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's
covenants, and I believe the lightning folks are interested in it as well
for some constant space storage scheme.

On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello world,
>
> After the core dev meetup in March I wrote up some notes of where I
> think things stand for signing stuff post-Schnorr. It was mostly for my
> own benefit but maybe it's helpful for others too, so...
>
> They're just notes, so may assume a fair bit of background to be able to
> understand the meaning of the bullet points. In particular, note that I'm
> using "schnorr" just to describe the signature algorithm, and the terms
> "key aggregation" to describe turning an n-of-n key multisig setup into
> a single key setup, and "signature aggregation" to describe combining
> signatures from many inputs/transactions together: those are often all
> just called "schnorr signatures" in various places.
>
>
> Anyway! I think it's fair to split the ideas around up as follows:
>
> 1) Schnorr CHECKSIG
>
>   Benefits:
>     - opportunity to change signature encoding from DER to save a few
>       bytes per signature, and have fixed size signatures making tx size
>       calculations easier
>
>     - enables n-of-n multisig key aggregation (a single pubkey and
>       signature gives n-of-n security; setup non-interactively via muSig,
>       or semi-interactively via proof of possession of private key;
>       interactive signature protocol)
>
>     - enables m-of-n multisig key aggregation with interactive setup and
>       interactive signature protocol, and possibly substantial storage
>       requirements for participating signers
>
>     - enables scriptless scripts and discreet log contracts via
>       key aggregation and interactive
>
>     - enables payment decorrelation for lightning
>
>     - enables batch validation of signatures, which substantially reduces
>       computational cost of signature verification, provided a single
>       "all sigs valid" or "some sig(s) invalid" output (rather than
>       "sig number 5 is invalid") is sufficient
>
>     - better than ecdsa due to reducing signature malleability
>       (and possibly due to having a security proof that has had more
>       review?)
>
>    Approaches:
>      - bump segwit version to replace P2WPKH
>      - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>      - hardfork to allowing existing addresses to be solved via Schnorr sig
>        as alternative to ECDSA
>
> 2) Merkelized Abstract Syntax Trees
>
>    Two main benefits for enabling MAST:
>     - logarithmic scaling for scripts with many alternative paths
>     - only reveals (approximate) number of alternative execution branches,
>       not what they may have been
>
>    Approaches:
>     - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>       item remaining on the alt stack at the end of script exeution as a
>       script and do tail-recursion into it (BIP 116, 117)
>     - bump the segwit version and introduce a "pay-to-merkelized-script"
>       address form (BIP 114)
>
> 3) Taproot
>
>    Requirements:
>     - only feasible if Schnorr is available (required in order to make the
>       pubkey spend actually be a multisig spend)
>     - andytoshi has written up a security proof at
>       https://github.com/apoelstra/taproot
>
>    Benefits:
>     - combines pay-to-pubkey and pay-to-script in a single address,
>       improving privacy
>     - allows choice of whether to use pubkey or script at spend time,
>       allowing for more efficient spends (via pubkey) without reducing
>       flexibility (via script)
>
>    Approaches:
>     - bump segwit version and introduce a "pay-to-taproot" address form
>
> 4) Graftroot
>
>    Requirements:
>     - only really feasible if Schnorr is implemented first, so that
>       multiple signers can be required via a single pubkey/signature
>     - people seem to want a security proof for this; not sure if that's
>       hard or straightforward
>
>    Benefits:
>     - allows delegation of authorisation to spend an output already
>       on the blockchain
>     - constant scaling for scripts with many alternative paths
>       (better than MAST's logarithmic scaling)
>     - only reveals the possibility of alternative execution branches,
>       not what they may have been or if any actually existed
>
>    Drawbacks:
>     - requires signing keys to be online when constructing scripts (cannot
>       do complicated pay to cold wallet without warming it up)
>     - requires storing signatures for scripts (if you were able to
>       reconstruct the sigs, you could just sign the tx directly and
> wouldn't
>       use a script)
>     - cannot prove that alternative methods of spending are not
>       possible to anyone who doesn't exclusively hold (part of) the
>       output address private key
>     - adds an extra signature check on script spends
>
>    Approaches:
>     - bump segwit version and introduce a "pay-to-graftroot" address form
>
> 5) Interactive Signature Aggregation
>
>    Requirements:
>     - needs Schnorr
>
>    Description:
>     - allows signers to interactively collaborate when constructing a
>       transaction to produce a single signature that covers multiple
>       inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
>       signatures
>
>    Benefits:
>     - reduces computational cost of additional signatures (i think?)
>     - reduces witness storage needed for additional signatures to just the
>       sighash flag byte (or bytes, if it's expanded)
>     - transaction batching and coinjoins potentially become cheaper than
>       independent transactions, indirectly improving on-chain privacy
>
>    Drawbacks:
>     - each soft-fork introduces a checkpoint, such that signatures that
>       are not validated by versions prior to the soft-fork cannot be
>       aggregated with signatures that are validated by versions prior to
>       the soft-fork (see [0] for discussion about avoiding that drawback)
>
>    Approaches:
>     - crypto logic can be implemented either by Bellare-Neven or MuSig
>     - needs a new p2wpkh output format, so likely warrants a segwit
>       version bump
>     - may warrant allowing multiple aggregation buckets
>     - may warrant peer-to-peer changes and a new per-tx witness
>
> 6) Non-interactive half-signature aggregation within transaction
>
>    Requirements:
>      - needs Schnorr
>      - needs a security proof before deployment
>
>    Benefits:
>      - can halve the size of non-aggregatable signatures in a transaction
>      - in particular implies the size overhead of a graftroot script
>        is just 32B, the same as a taproot script
>
>    Drawbacks:
>      - cannot be used with scriptless-script signatures
>
>    Approaches:
>      - ideally best combined with interactive aggregate signatures, as it
>        has similar implementation requirements
>
> 7) New SIGHASH modes
>
>    These will also need a new segwit version (for p2pk/p2pkh) and probably
>    need to be considered at the same time.
>
> 8) p2pk versus p2pkh
>
>    Whether to stick with a pubkeyhash for the address or just have a pubkey
>    needs to be decided for any new segwit version.
>
> 9) Other new opcodes
>
>    Should additional opcodes in new segwit versions be reserved as OP_NOP
> or
>    as OP_RETURN_VALID, or something else?
>
>    Should any meaningful new opcodes be supported or re-enabled?
>
> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit
>
>    Making existing p2pk or p2pkh outputs spendable via Schnorr with
>    interactive signature aggregation would likely be a big win for people
>    with old UTXOs, without any decrease in security, especially if done
>    a significant time after those features were supported for new outputs.
>
> 11) Should addresses be hashes or scripts?
>
>    maaku's arguments for general opcodes for MAST make me wonder a bit
>    if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
>    should we have script opcodes as the top level way to write addresses,
>    rather than picking the "best" form of address everyone should use,
>    and having people have to opt-out of that. probably already too late
>    to actually have that debate though.
>
> Anyway, I think what that adds up to is:
>
>  - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
>    really needs to be done via new segwit versions
>
>  - We can evaluate MAST in segwit v0 independently -- use the existing
>    BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
>    segwit versions.
>
>  - There is no point deploying any of this for non-segwit scripts
>
>  - Having the taproot script be a MAST root probably makes sense. If so,
>    a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
>    sense at some point.
>
> So I think that adds up to:
>
>  a) soft-fork for MAST in segwit v0 anytime if there's community/economic
>     support for it?
>
>  b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime
>
>  c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
>     taproot+mast addresses in not too much time
>
>  d) soft-fork for segwit v2 introducing further upgrades, particularly
>     graftroot
>
>  e) soft-fork for segwit v2 to support interactive signature aggregation
>
>  f) soft-fork for segwit v3 including non-interactive sig aggregation
>
> The rationale there is:
>
>   (a) and (b) are self-contained and we could do them now. My feeling is
>   better to skip them and go straight to (c)
>
>   (c) is the collection of stuff that would be a huge win, and seems
>   "easily" technically feasible. signature aggregation seems too
>   complicated to fit in here, and getting the other stuff done while we
>   finish thinking about sigagg seems completely worthwhile.
>
>   (d) is a followon for (c), in case signature aggregation takes a
>   *really* long while. It could conceivably be done as a different
>   variation of segwit v1, really. It might turn out that there's no
>   urgency for graftroot and it should be delayed until non-interactive
>   sig aggregation is implementable.
>
>   (e) and (f) are separated just because I worry that non-interactive
>   sig aggregation might not turn out to be possible; doing them as a
>   single upgrade would be preferrable.
>
> Cheers,
> aj
>
> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
> 2018-March/015838.html
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Thanks for writing this up Anthony.<br><br></div>Do y=
ou think that a CHECKSIGFROMSTACK proposal should be included within this d=
iscussion of signature soft-forks, or do you see it as an unrelated issue?<=
br><br>CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See <a =
href=3D"http://people.csail.mit.edu/ranjit/papers/scd.pdf">http://people.cs=
ail.mit.edu/ranjit/papers/scd.pdf</a>), enables poor-man&#39;s covenants, a=
nd I believe the lightning folks are interested in it as well for some cons=
tant space storage scheme.<br></div><div class=3D"gmail_extra"><br><div cla=
ss=3D"gmail_quote">On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitco=
in-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfound=
ation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;<=
/span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex">Hello world,<br>
<br>
After the core dev meetup in March I wrote up some notes of where I<br>
think things stand for signing stuff post-Schnorr. It was mostly for my<br>
own benefit but maybe it&#39;s helpful for others too, so...<br>
<br>
They&#39;re just notes, so may assume a fair bit of background to be able t=
o<br>
understand the meaning of the bullet points. In particular, note that I&#39=
;m<br>
using &quot;schnorr&quot; just to describe the signature algorithm, and the=
 terms<br>
&quot;key aggregation&quot; to describe turning an n-of-n key multisig setu=
p into<br>
a single key setup, and &quot;signature aggregation&quot; to describe combi=
ning<br>
signatures from many inputs/transactions together: those are often all<br>
just called &quot;schnorr signatures&quot; in various places.<br>
<br>
<br>
Anyway! I think it&#39;s fair to split the ideas around up as follows:<br>
<br>
1) Schnorr CHECKSIG<br>
<br>
=C2=A0 Benefits:<br>
=C2=A0 =C2=A0 - opportunity to change signature encoding from DER to save a=
 few<br>
=C2=A0 =C2=A0 =C2=A0 bytes per signature, and have fixed size signatures ma=
king tx size<br>
=C2=A0 =C2=A0 =C2=A0 calculations easier<br>
<br>
=C2=A0 =C2=A0 - enables n-of-n multisig key aggregation (a single pubkey an=
d<br>
=C2=A0 =C2=A0 =C2=A0 signature gives n-of-n security; setup non-interactive=
ly via muSig,<br>
=C2=A0 =C2=A0 =C2=A0 or semi-interactively via proof of possession of priva=
te key;<br>
=C2=A0 =C2=A0 =C2=A0 interactive signature protocol)<br>
<br>
=C2=A0 =C2=A0 - enables m-of-n multisig key aggregation with interactive se=
tup and<br>
=C2=A0 =C2=A0 =C2=A0 interactive signature protocol, and possibly substanti=
al storage<br>
=C2=A0 =C2=A0 =C2=A0 requirements for participating signers<br>
<br>
=C2=A0 =C2=A0 - enables scriptless scripts and discreet log contracts via<b=
r>
=C2=A0 =C2=A0 =C2=A0 key aggregation and interactive<br>
<br>
=C2=A0 =C2=A0 - enables payment decorrelation for lightning<br>
<br>
=C2=A0 =C2=A0 - enables batch validation of signatures, which substantially=
 reduces<br>
=C2=A0 =C2=A0 =C2=A0 computational cost of signature verification, provided=
 a single<br>
=C2=A0 =C2=A0 =C2=A0 &quot;all sigs valid&quot; or &quot;some sig(s) invali=
d&quot; output (rather than<br>
=C2=A0 =C2=A0 =C2=A0 &quot;sig number 5 is invalid&quot;) is sufficient<br>
<br>
=C2=A0 =C2=A0 - better than ecdsa due to reducing signature malleability<br=
>
=C2=A0 =C2=A0 =C2=A0 (and possibly due to having a security proof that has =
had more<br>
=C2=A0 =C2=A0 =C2=A0 review?)<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 =C2=A0- bump segwit version to replace P2WPKH<br>
=C2=A0 =C2=A0 =C2=A0- replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY=
<br>
=C2=A0 =C2=A0 =C2=A0- hardfork to allowing existing addresses to be solved =
via Schnorr sig<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0as alternative to ECDSA<br>
<br>
2) Merkelized Abstract Syntax Trees<br>
<br>
=C2=A0 =C2=A0Two main benefits for enabling MAST:<br>
=C2=A0 =C2=A0 - logarithmic scaling for scripts with many alternative paths=
<br>
=C2=A0 =C2=A0 - only reveals (approximate) number of alternative execution =
branches,<br>
=C2=A0 =C2=A0 =C2=A0 not what they may have been<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and =
treat an<br>
=C2=A0 =C2=A0 =C2=A0 item remaining on the alt stack at the end of script e=
xeution as a<br>
=C2=A0 =C2=A0 =C2=A0 script and do tail-recursion into it (BIP 116, 117)<br=
>
=C2=A0 =C2=A0 - bump the segwit version and introduce a &quot;pay-to-merkel=
ized-script&quot;<br>
=C2=A0 =C2=A0 =C2=A0 address form (BIP 114)<br>
<br>
3) Taproot<br>
<br>
=C2=A0 =C2=A0Requirements:<br>
=C2=A0 =C2=A0 - only feasible if Schnorr is available (required in order to=
 make the<br>
=C2=A0 =C2=A0 =C2=A0 pubkey spend actually be a multisig spend)<br>
=C2=A0 =C2=A0 - andytoshi has written up a security proof at<br>
=C2=A0 =C2=A0 =C2=A0 <a href=3D"https://github.com/apoelstra/taproot" rel=
=3D"noreferrer" target=3D"_blank">https://github.com/apoelstra/<wbr>taproot=
</a><br>
<br>
=C2=A0 =C2=A0Benefits:<br>
=C2=A0 =C2=A0 - combines pay-to-pubkey and pay-to-script in a single addres=
s,<br>
=C2=A0 =C2=A0 =C2=A0 improving privacy<br>
=C2=A0 =C2=A0 - allows choice of whether to use pubkey or script at spend t=
ime,<br>
=C2=A0 =C2=A0 =C2=A0 allowing for more efficient spends (via pubkey) withou=
t reducing<br>
=C2=A0 =C2=A0 =C2=A0 flexibility (via script)<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 - bump segwit version and introduce a &quot;pay-to-taproot&qu=
ot; address form<br>
<br>
4) Graftroot<br>
<br>
=C2=A0 =C2=A0Requirements:<br>
=C2=A0 =C2=A0 - only really feasible if Schnorr is implemented first, so th=
at<br>
=C2=A0 =C2=A0 =C2=A0 multiple signers can be required via a single pubkey/s=
ignature<br>
=C2=A0 =C2=A0 - people seem to want a security proof for this; not sure if =
that&#39;s<br>
=C2=A0 =C2=A0 =C2=A0 hard or straightforward<br>
<br>
=C2=A0 =C2=A0Benefits:<br>
=C2=A0 =C2=A0 - allows delegation of authorisation to spend an output alrea=
dy<br>
=C2=A0 =C2=A0 =C2=A0 on the blockchain<br>
=C2=A0 =C2=A0 - constant scaling for scripts with many alternative paths<br=
>
=C2=A0 =C2=A0 =C2=A0 (better than MAST&#39;s logarithmic scaling)<br>
=C2=A0 =C2=A0 - only reveals the possibility of alternative execution branc=
hes, <br>
=C2=A0 =C2=A0 =C2=A0 not what they may have been or if any actually existed=
<br>
<br>
=C2=A0 =C2=A0Drawbacks:<br>
=C2=A0 =C2=A0 - requires signing keys to be online when constructing script=
s (cannot<br>
=C2=A0 =C2=A0 =C2=A0 do complicated pay to cold wallet without warming it u=
p)<br>
=C2=A0 =C2=A0 - requires storing signatures for scripts (if you were able t=
o<br>
=C2=A0 =C2=A0 =C2=A0 reconstruct the sigs, you could just sign the tx direc=
tly and wouldn&#39;t<br>
=C2=A0 =C2=A0 =C2=A0 use a script)<br>
=C2=A0 =C2=A0 - cannot prove that alternative methods of spending are not<b=
r>
=C2=A0 =C2=A0 =C2=A0 possible to anyone who doesn&#39;t exclusively hold (p=
art of) the<br>
=C2=A0 =C2=A0 =C2=A0 output address private key<br>
=C2=A0 =C2=A0 - adds an extra signature check on script spends<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 - bump segwit version and introduce a &quot;pay-to-graftroot&=
quot; address form<br>
<br>
5) Interactive Signature Aggregation<br>
<br>
=C2=A0 =C2=A0Requirements:<br>
=C2=A0 =C2=A0 - needs Schnorr<br>
<br>
=C2=A0 =C2=A0Description:<br>
=C2=A0 =C2=A0 - allows signers to interactively collaborate when constructi=
ng a<br>
=C2=A0 =C2=A0 =C2=A0 transaction to produce a single signature that covers =
multiple<br>
=C2=A0 =C2=A0 =C2=A0 inputs and/or OP_CHECKSIG invocations that are resolve=
d by Schnorr<br>
=C2=A0 =C2=A0 =C2=A0 signatures<br>
<br>
=C2=A0 =C2=A0Benefits:<br>
=C2=A0 =C2=A0 - reduces computational cost of additional signatures (i thin=
k?)<br>
=C2=A0 =C2=A0 - reduces witness storage needed for additional signatures to=
 just the<br>
=C2=A0 =C2=A0 =C2=A0 sighash flag byte (or bytes, if it&#39;s expanded)<br>
=C2=A0 =C2=A0 - transaction batching and coinjoins potentially become cheap=
er than<br>
=C2=A0 =C2=A0 =C2=A0 independent transactions, indirectly improving on-chai=
n privacy<br>
<br>
=C2=A0 =C2=A0Drawbacks:<br>
=C2=A0 =C2=A0 - each soft-fork introduces a checkpoint, such that signature=
s that<br>
=C2=A0 =C2=A0 =C2=A0 are not validated by versions prior to the soft-fork c=
annot be<br>
=C2=A0 =C2=A0 =C2=A0 aggregated with signatures that are validated by versi=
ons prior to<br>
=C2=A0 =C2=A0 =C2=A0 the soft-fork (see [0] for discussion about avoiding t=
hat drawback)<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 - crypto logic can be implemented either by Bellare-Neven or =
MuSig<br>
=C2=A0 =C2=A0 - needs a new p2wpkh output format, so likely warrants a segw=
it<br>
=C2=A0 =C2=A0 =C2=A0 version bump<br>
=C2=A0 =C2=A0 - may warrant allowing multiple aggregation buckets<br>
=C2=A0 =C2=A0 - may warrant peer-to-peer changes and a new per-tx witness<b=
r>
<br>
6) Non-interactive half-signature aggregation within transaction<br>
<br>
=C2=A0 =C2=A0Requirements:<br>
=C2=A0 =C2=A0 =C2=A0- needs Schnorr<br>
=C2=A0 =C2=A0 =C2=A0- needs a security proof before deployment<br>
<br>
=C2=A0 =C2=A0Benefits:<br>
=C2=A0 =C2=A0 =C2=A0- can halve the size of non-aggregatable signatures in =
a transaction<br>
=C2=A0 =C2=A0 =C2=A0- in particular implies the size overhead of a graftroo=
t script<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0is just 32B, the same as a taproot script<br>
<br>
=C2=A0 =C2=A0Drawbacks:<br>
=C2=A0 =C2=A0 =C2=A0- cannot be used with scriptless-script signatures<br>
<br>
=C2=A0 =C2=A0Approaches:<br>
=C2=A0 =C2=A0 =C2=A0- ideally best combined with interactive aggregate sign=
atures, as it<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0has similar implementation requirements<br>
<br>
7) New SIGHASH modes<br>
<br>
=C2=A0 =C2=A0These will also need a new segwit version (for p2pk/p2pkh) and=
 probably<br>
=C2=A0 =C2=A0need to be considered at the same time.<br>
<br>
8) p2pk versus p2pkh<br>
<br>
=C2=A0 =C2=A0Whether to stick with a pubkeyhash for the address or just hav=
e a pubkey<br>
=C2=A0 =C2=A0needs to be decided for any new segwit version.<br>
<br>
9) Other new opcodes<br>
<br>
=C2=A0 =C2=A0Should additional opcodes in new segwit versions be reserved a=
s OP_NOP or<br>
=C2=A0 =C2=A0as OP_RETURN_VALID, or something else?<br>
<br>
=C2=A0 =C2=A0Should any meaningful new opcodes be supported or re-enabled?<=
br>
<br>
10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit<br>
<br>
=C2=A0 =C2=A0Making existing p2pk or p2pkh outputs spendable via Schnorr wi=
th<br>
=C2=A0 =C2=A0interactive signature aggregation would likely be a big win fo=
r people<br>
=C2=A0 =C2=A0with old UTXOs, without any decrease in security, especially i=
f done<br>
=C2=A0 =C2=A0a significant time after those features were supported for new=
 outputs.<br>
<br>
11) Should addresses be hashes or scripts?<br>
<br>
=C2=A0 =C2=A0maaku&#39;s arguments for general opcodes for MAST make me won=
der a bit<br>
=C2=A0 =C2=A0if the &quot;p2pkh&quot; approach isn&#39;t better than the &q=
uot;p2wpkh&quot; approach; ie<br>
=C2=A0 =C2=A0should we have script opcodes as the top level way to write ad=
dresses,<br>
=C2=A0 =C2=A0rather than picking the &quot;best&quot; form of address every=
one should use,<br>
=C2=A0 =C2=A0and having people have to opt-out of that. probably already to=
o late<br>
=C2=A0 =C2=A0to actually have that debate though.<br>
<br>
Anyway, I think what that adds up to is:<br>
<br>
=C2=A0- Everything other than MAST and maybe some misc new CHECKVERIFY opco=
des<br>
=C2=A0 =C2=A0really needs to be done via new segwit versions<br>
<br>
=C2=A0- We can evaluate MAST in segwit v0 independently -- use the existing=
<br>
=C2=A0 =C2=A0BIPs to deploy MAST for v0; and re-evaluate entirely for v1 an=
d later<br>
=C2=A0 =C2=A0segwit versions.<br>
<br>
=C2=A0- There is no point deploying any of this for non-segwit scripts<br>
<br>
=C2=A0- Having the taproot script be a MAST root probably makes sense. If s=
o,<br>
=C2=A0 =C2=A0a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably ma=
kes<br>
=C2=A0 =C2=A0sense at some point.<br>
<br>
So I think that adds up to:<br>
<br>
=C2=A0a) soft-fork for MAST in segwit v0 anytime if there&#39;s community/e=
conomic<br>
=C2=A0 =C2=A0 support for it?<br>
<br>
=C2=A0b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime<br>
<br>
=C2=A0c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and<br=
>
=C2=A0 =C2=A0 taproot+mast addresses in not too much time<br>
<br>
=C2=A0d) soft-fork for segwit v2 introducing further upgrades, particularly=
<br>
=C2=A0 =C2=A0 graftroot<br>
<br>
=C2=A0e) soft-fork for segwit v2 to support interactive signature aggregati=
on<br>
<br>
=C2=A0f) soft-fork for segwit v3 including non-interactive sig aggregation<=
br>
<br>
The rationale there is:<br>
<br>
=C2=A0 (a) and (b) are self-contained and we could do them now. My feeling =
is<br>
=C2=A0 better to skip them and go straight to (c)<br>
<br>
=C2=A0 (c) is the collection of stuff that would be a huge win, and seems<b=
r>
=C2=A0 &quot;easily&quot; technically feasible. signature aggregation seems=
 too<br>
=C2=A0 complicated to fit in here, and getting the other stuff done while w=
e<br>
=C2=A0 finish thinking about sigagg seems completely worthwhile.<br>
<br>
=C2=A0 (d) is a followon for (c), in case signature aggregation takes a<br>
=C2=A0 *really* long while. It could conceivably be done as a different<br>
=C2=A0 variation of segwit v1, really. It might turn out that there&#39;s n=
o<br>
=C2=A0 urgency for graftroot and it should be delayed until non-interactive=
<br>
=C2=A0 sig aggregation is implementable.<br>
<br>
=C2=A0 (e) and (f) are separated just because I worry that non-interactive<=
br>
=C2=A0 sig aggregation might not turn out to be possible; doing them as a<b=
r>
=C2=A0 single upgrade would be preferrable.<br>
<br>
Cheers,<br>
aj<br>
<br>
[0] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018=
-March/015838.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linu=
xfoundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2018-March/015838.html</a><=
br>
<br>
______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
</blockquote></div><br></div>

--0000000000007f475b056bdac37d--