summaryrefslogtreecommitdiff
path: root/60/a69f69b3af8a79bcecae583c467012c3dbd59c
blob: 5bf7f5a64013ab172cda14fdb3a6f24925f0211c (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
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
Return-Path: <antoine.riard@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 84E83C000B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 18:09:24 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 6C21140360
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 18:09:24 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id qB7XAEts9MXB
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 18:09:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yb1-xb2a.google.com (mail-yb1-xb2a.google.com
 [IPv6:2607:f8b0:4864:20::b2a])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 4006140192
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 18:09:20 +0000 (UTC)
Received: by mail-yb1-xb2a.google.com with SMTP id y6so21104046ybc.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 10:09:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=pU8I8+oEBrYQeNprJhENfUmOBN/o0zpRAEhs3kYgzfE=;
 b=Wrb2Eto9kg89PqAQuPZRuhwLxp0gJG4cQiQon10YawEEe2dgKwPFtMeHUJUH2hgYec
 3Ckg70w/hbA9jiqk5vFxPXStXAkMsRRJf6l9zehD1omCopk7GhRdLUb3/mqZsQ1iJ+yl
 5PGD0hWReVSzEdDt9SNR3YfIZqUJm+ON+KrnRGJCuPx6TfnBWOa2OIZqLBph3kFj6SK5
 ndGfhQhJyWSmt/yHrvTC3mafBhNaoQnMndjDpZ3Gab3mhwEo2qUOIYzAeSLEd+0mfMAt
 Iyp/laQA1a6o9aLFYdKfopXgc0W/kCtt7L5CAfgaqFiJGA8JLuZAIygi6J9zZDZ1FtLE
 cebA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=pU8I8+oEBrYQeNprJhENfUmOBN/o0zpRAEhs3kYgzfE=;
 b=mmDDQ7pbiZlkoelRQ9kElQtz/LSGzmgrH+HI6CuQhzCnZ/ty56QDs2RNtR9ZAAxgqk
 5eFoOsDbEMjjwwZRNISENy+gNWSAEtpxUd+3+6pRFeeD8GoqvOqcUd6K/MAC+NaU6sK8
 yZG1O3hbiO2fjh2PSLYW8T80D00p5xVBUua2hPRGRlk1ogmt1apKgxmtvXdkY3uPoRWm
 eS9TARCWENmDE/89xK1M6Na9M878x/i0S5J3VWwaZXCkytvE+BDmgyDi6hOpZMeld0R6
 o7ww++HRw+G9AGdV8snWBAE708uWrxa0C829frWXTOJ7ggZUFkmiZTw6sTSrDlqS+pFO
 dnFw==
X-Gm-Message-State: AOAM530F5TV8Q+DThoA9Vr74k/yIvhzKMGgeLz50+9N0urAmv4VoTFGi
 4QszVbckzWR758PyBCwfbUoNFRP8wnfmcTOZSh5ONiPDX9Y=
X-Google-Smtp-Source: ABdhPJwLhtvlxh25167ioI32bSixWt22Fq9arPUE9rlGx18BlRS0bU512QUsiSJNyt+pXKgsDTmOSvNauqR2OXd5rLE=
X-Received: by 2002:a25:a0cc:0:b0:624:3d74:9244 with SMTP id
 i12-20020a25a0cc000000b006243d749244mr6220097ybm.173.1645207759023; Fri, 18
 Feb 2022 10:09:19 -0800 (PST)
MIME-Version: 1.0
References: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
In-Reply-To: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Fri, 18 Feb 2022 13:09:07 -0500
Message-ID: <CALZpt+Ee9kuVjpXYgOb_7dB7Yr8HYmicdRhfgXsQkey2szNDHg@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000000ef30305d84ec871"
X-Mailman-Approved-At: Fri, 18 Feb 2022 18:31:39 +0000
Cc: Anthony Towns <aj@erisian.com.au>
Subject: Re: [bitcoin-dev] `OP_EVICT`: An Alternative to
	`OP_TAPLEAFUPDATEVERIFY`
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: Fri, 18 Feb 2022 18:09:24 -0000

--0000000000000ef30305d84ec871
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Zeeman,

> After some thinking, I realized that it was the use of the
> Merkle tree to represent the promised-but-offchain outputs of
> the CoinPool that lead to the O(log N) space usage.
> I then started thinking of alternative representations of
> sets of promised outputs, which would not require O(log N)
> revelations by avoiding the tree structure.

In the context of payment pools, I think the O(log N) revelations can be
avoided already today by pre-signing all the combinations of
promised-but-offchain outputs publications order. However, this approach
presents a factorial complexity and appears as an intractable problem for
high-number of pool users.

I think this factorial complexity issue is the primary problem to enable
scalable payment pools. This issue appears to be solvable by introducing an
accumulator at the script interpreter level. IMO, the efficiency of the
accumulated set representations comes as a second-order issue.

In the comparison of different covenant primitives, I believe we should ask
first if the flexibility offered is enough to solve the factorial
complexity. I would say performance trade-offs analysis can only be
conducted in logically equivalent primitives.

> A statechain is really just a CoinPool hosted inside a
>  Decker-Wattenhofer or Decker-Russell-Osuntokun construction.

Note, to the best of my knowledge, how to use LN-Penalty in the context of
multi-party construction is still an unsolved issue. If an invalidated
state is published on-chain, how do you guarantee that the punished output
value is distributed "fairly" among the "honest" set of users ? At least
where fairness is defined as a reasonable proportion of the balances they
owned in the latest state.

> (To Bitcoin Cashers: this is not an IOU, this is *committed* and
> can be enforced onchain, that is enough to threaten your offchain
> counterparties into behaving correctly.
> They cannot gain anything by denying the outputs they promised,
> you can always drop it onchain and have it enforced, thus it is
> not just merely an IOU, as IOUs are not necessarily enforceable,
> but this mechanism *would* be.
> Blockchain as judge+jury+executioner, not noisy marketplace.)

To be fair towards the Bitcoin Cashers, I think there are still limitations
of LN, we have not solved yet. Especially, w.r.t to mass exits from the
off-chain layers to the chain, where the blocks would stay fulfilled longer
than the standard HTLC timelocks, at  a fee price point that the average
user can't buy... I'm not sure if we have outlawed the "bank runs" scenario
yet of LN.

I would say yes the Blockchain is a juge authority, but in the worst-case
we might be all in market competition to get enforcement.

> In principle, a set of promised outputs, if the owners of those
> outputs are peers, does not have *any* inherent order.
> Thus, I started to think about a commitment scheme that does not
> impose any ordering during commitment.

I think we should dissociate a) *outputs publication ordering* from the b)
*spends paths ordering* itself. Even if to each spend path a output
publication is attached, the ordering constraint might not present the same
complexity.

Under this distinction, are you sure that TLUV imposes an ordering on the
output publication ?

> With `OP_TLUV`, however, it is possible to create an "N-of-N With
> Eviction" construction.
> When a participant in the N-of-N is offline, but the remaining
> participants want to advance the state of the construction, they
> instead evict the offline participant, creating a smaller N-of-N
> where *all* participants are online, and continue operating.

I think we should dissociate two types of pool spends : a) eviction by the
pool unanimity in case of irresponsive participants and b) unilateral
withdrawal by a participant because of the liquidity allocation policy. I
think the distinction is worthy, as the pool participant should be stable
and the eviction not abused.

I'm not sure if TLUV enables b), at least without transforming the
unilateral withdrawal into an eviction. To ensure the TLUV operation is
correct  (spent leaf is removed, withdrawing participant point removed,
etc), the script content must be inspected by *all* the participant.
However, I believe
knowledge of this content effectively allows you to play it out against the
pool at any time ? It's likely solvable at the price of a CHECKSIG.

`OP_EVICT`
----------

>  * If it is `1` that simply means "use the Taproot internal
>    pubkey", as is usual for `OP_CHECKSIG`.

IIUC, this assumes the deployment of BIP118, where if the  public key is a
single byte 0x01, the internal pubkey is used
for verification.

>  * Output indices must not be duplicated, and indicated
>    outputs must be SegWit v1 ("Taproot") outputs.

I think public key duplication must not be verified. If a duplicated public
key is present, the point is subtracted twice from the internal pubkey and
therefore the aggregated
key remains unknown ? So it sounds to me safe against replay attacks.

>  * The public key is the input point (i.e. stack top)
>    **MINUS** all the public keys of the indicated outputs.

Can you prevent eviction abuse where one counterparty threatens to evict
everyone as all the output signatures are known among participants and free
to sum ? (at least not considering fees)

> Suppose however that B is offline.
> Then A, C, and D then decide to evict B.
> To do so, they create a transaction that has an output
> with "B :=3D 6", and they reveal the `OP_EVICT` Tapscript
> as well as sign(b, "B :=3D 6").
> This lets them change state and spend their funds without
> B being online.
> And B remains secure, as they cannot evict B except using
> the pre-signed output, which B certifies as their expected
> promised output.

I think in the context of (off-chain) payment pool, OP_EVICT requires
participant cooperation *after* the state update to allow a single
participant to withdraw her funds.

I believe this is unsafe if we retain as an off-chain construction security
requirement that a participant should have the unilateral means to enforce
the latest agreed upon state at any time during the construction lifetime.

I would say an OP_EVICT construction could solve the issue where the pool
participants exchange pre-signatures of the internal pubkey with the
withdrawing participant point removed. However, I believe such fix would a)
block promised outputs batching (or at least in a pre-committed way like
radix pools) and b) be grieved by the factorial complexity described above.

> The combined fund cannot be spent except if all participants
> agree.

If all participants agree minus the evicted ones, correct ? The output
promises signatures are shared at state setup, therefore no additional
contribution from the evicted participant (I think).

> To prevent signature replay, each update of an updateable
> scheme like CoinPool et al should use a different pubkey
> for each participant for each state.

I'm not even sure if it's required with OP_EVICT, as the publication of the
promised output are ultimately restrained by a signature of the updated
internal pubkey, this set of signers verify that promised output N does
bind to the published state N ?

> Its advantage is reduced number of eviction transactions,
> as multiple evictions, plus the revival of the CoinPool,
> can be put in a single transaction.
> It has the disadvantage relative to `OP_TLUV` of requiring
> point operations.
> I have not explored completely, but my instinct suggests
> that `OP_TLUV` use may require at least one signature
> validation anyway.

I believe you can slightly modify TLUV to make it functional for CoinPool
revival, where you want to prevent equivocation among the remaining set of
signers. Though, I'm leaning to agree that you may require at least one
signature validation  (first to restrain spend authorization inside the
pool participants, second to attach fees at broadcast-time).

> It may be possible to design an `OP_CSFS` variant that
> allows batch validation, such as by extending the virtual
> machine with an accumulator for pending signature
> validations.

I agree that in the context of payment pools, aggregation of
non-cooperative unilateral spends is a scalability bottleneck, especially
in the face of mempools congestion. If we rely on merkle
trees as the accumulator primitive, there is still the path to aggregate
many branches in-flight.

Any misunderstandings of this proposal are my own.
,
Antoine

Le jeu. 17 f=C3=A9vr. 2022 =C3=A0 21:45, ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D
>
> In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to
> implement CoinPools and similar constructions.
>
> `Jeremy` observed that due to the use of Merkle tree paths, an
> `OP_TLUV` would require O(log N) hash revelations in order to
> reach a particular tapleaf, which, in the case of a CoinPool,
> would then delete itself after spending only a particular amount
> of funds.
> He then observed that `OP_CTV` trees also require a similar
> revelation of O(log N) transactions, but with the advantage that
> once revealed, the transactions can then be reused, thus overall
> the expectation is that the number of total bytes onchain is
> lesser compared to `OP_TLUV`.
>
> After some thinking, I realized that it was the use of the
> Merkle tree to represent the promised-but-offchain outputs of
> the CoinPool that lead to the O(log N) space usage.
> I then started thinking of alternative representations of
> sets of promised outputs, which would not require O(log N)
> revelations by avoiding the tree structure.
>
> Promised Outputs
> ----------------
>
> Fundamentally, we can consider that a solution for scaling
> Bitcoin would be to *promise* that some output *can* appear
> onchain at some point in the future, without requiring that the
> output be shown onchain *right now*.
> Then, we can perform transactional cut-through on spends of the
> promised outputs, without requiring onchain activity ("offchain").
> Only if something Really Bad (TM) happens do we need to actually
> drop the latest set of promised outputs onchain, where it has to
> be verified globally by all fullnodes (and would thus incur scaling
> and privacy costs).
>
> As an example of the above paradigm, consider the Lightning
> Network.
> Outputs representing the money of each party in a channel are
> promised, and *can* appear onchain (via the unilateral close
> mechanism).
> In the meantime, there is a mechanism for performing cut-through,
> allowing transfers between channel participants; any number of
> transactions can be performed that are only "solidified" later,
> without expensive onchain activity.
>
> Thus:
>
> * A CoinPool is really a way to commit to promised outputs.
>   To change the distribution of those promised outputs, the
>   CoinPool operators need to post an onchain transaction, but
>   that is only a 1-input-1-output transaction, and with Schnorr
>   signatures the single input requires only a single signature.
>   But in case something Really Bad (TM) happens, any participant
>   can unilaterally close the CoinPool, instantiating the promised
>   outputs.
> * A statechain is really just a CoinPool hosted inside a
>   Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
>   This allows changing the distribution of those promised outputs
>   without using an onchain transaction --- instead, a new state
>   in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction
>   is created containing the new state, which invalidates all older
>   states.
>   Again, any participant can unilaterally shut it down, exposing
>   the state of the inner CoinPool.
> * A channel factory is really just a statechain where the
>   promised outputs are not simple 1-of-1 single-owner outputs,
>   but are rather 2-of-2 channels.
>   This allows graceful degradation, where even if the statechain
>   ("factory") layer has missing participants, individual 2-of-2
>   channels can still continue operating as long as they do not
>   involve missing participants, without requiring all participants
>   to be online for large numbers of transactions.
>
> We can then consider that the base CoinPool usage should be enough,
> as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be
> used to implement statechains and channels and channel factories.
>
> I therefore conclude that what we really need is "just" a way to
> commit ourselves to exposing a set of promised outputs, with the
> proviso that if we all agree, we can change that set (without
> requiring that the current or next set be exposed, for both
> scaling and privacy).
>
> (To Bitcoin Cashers: this is not an IOU, this is *committed* and
> can be enforced onchain, that is enough to threaten your offchain
> counterparties into behaving correctly.
> They cannot gain anything by denying the outputs they promised,
> you can always drop it onchain and have it enforced, thus it is
> not just merely an IOU, as IOUs are not necessarily enforceable,
> but this mechanism *would* be.
> Blockchain as judge+jury+executioner, not noisy marketplace.)
>
> Importantly: both `OP_CTV` and `OP_TLUV` force the user to
> decide on a particular, but ultimately arbitrary, ordering for
> promised outputs.
> In principle, a set of promised outputs, if the owners of those
> outputs are peers, does not have *any* inherent order.
> Thus, I started to think about a commitment scheme that does not
> impose any ordering during commitment.
>
> Digression: N-of-N With Eviction
> --------------------------------
>
> An issue with using an N-of-N construction is that if any single
> participant is offline, the construction cannot advance its state.
>
> This has lead to some peopple proposing to instead use K-of-N
> once N reaches much larger than 2 participants for CoinPools/statechains/
> channel factories.
>
> However, even so, K-of-N still requires that K participants remain
> online, and the level K is a security parameter.
> If less than K participants are online, then the construction
> *still* cannot advance its state.
>
> Worse, because K < N, a single participant can have its funds
> outright stolen by a quorum of K participants.
> There is no way to prove that the other participants in the same
> construction are not really sockpuppets of the same real-world
> entity, thus it is entirely possible that the K quorum is actually
> just a single participant that is now capable of stealing the
> funds of all the other participants.
> The only way to avoid this is to use N-oF-N: N-of-N requires
> *your* keys, thus the coins are *your* coins.
> In short: K-of-N, as it allows the state to be updated without your
> keys (on the excuse that "if you are offline, we need to be able to
> update state"), is *not your keys not your coins*.
>
> K-of-N should really only be used if all N are your sockpuppets,
> and you want to HODL your funds.
> This is the difference between consensus "everyone must agree" and
> voting "enough sockpuppets can be used to overpower you".
>
> With `OP_TLUV`, however, it is possible to create an "N-of-N With
> Eviction" construction.
> When a participant in the N-of-N is offline, but the remaining
> participants want to advance the state of the construction, they
> instead evict the offline participant, creating a smaller N-of-N
> where *all* participants are online, and continue operating.
>
> This avoids the *not your keys not your coins* problem of K-of-N
> constructions, while simultaneously providing a way to advance
> the state without the full participant set being online.
>
> The only real problem with `OP_TLUV` is that it takes O(log N)
> hash revelations to evict one participant, and each evicted
> participant requires one separate transaction.
>
> K-of-N has the "advantage" that even if you are offline, the state
> can be advanced without evicting you.
> However, as noted, as the coins can be spent without your keys,
> the coins are not your coins, thus this advantage may be considered
> dubious --- whether you are online or offline, a quorum of K can
> outright steal your coins.
> Eviction here requires that your coins be returned to your control.
>
> Committing To An Unordered Set
> ------------------------------
>
> In an N-of-N CoinPool/statechain/channel factory, the ownership
> of a single onchain UTXO is shared among N participants.
> That is, there are a number of promised outputs, not exposed
> onchain, which the N participants agree on as the "real" current
> state of the construction,
> However, the N participants can also agree to change the current
> state of the construction, if all of them sign off on the change.
>
> Each of the promised outputs has a value, and the sum of all
> promised values is the value of the onchain UTXO.
> Interestingly, each of the promised outputs also has an SECP256K1
> point that can be used as a public key, and the sum of all
> promised points is the point of the onchain UTXO.
>
> Thus, the onchain UTXO can serve as a commitment to the sum of
> the promised outputs.
> The problem is committing to each of the individual promised
> outputs.
>
> We can observe that a digital signature not only proves knowledge
> of a private key, it also commits to a particular message.
> Thus, we can make each participant sign their own expected
> promised output, and share the signature for their promised
> output.
>
> When a participant is to be evicted, the other participants
> take the signature for the promised output of the to-be-evicted
> participant, and show it onchain, to attest to the output.
> Then, the onchain mechanism should then allow the rest of the
> funds to be controlled by the N-of-N set minus the evicted
> participant.
>
> `OP_EVICT`
> ----------
>
> With all that, let me now propose the `OP_EVICT` opcode.
>
> `OP_EVICT` accepts a variable number of arguments.
>
> * The stack top is either the constant `1`, or an SECP256K1
>   point.
>   * If it is `1` that simply means "use the Taproot internal
>     pubkey", as is usual for `OP_CHECKSIG`.
> * The next stack item is a number, equal to the number of
>   outputs that were promised, and which will now be evicted.
> * The next stack items will alternate:
>   * A number indicating an output index.
>   * A signature for that output.
>   * Output indices must not be duplicated, and indicated
>     outputs must be SegWit v1 ("Taproot") outputs.
>     The public key of the output will be taken as the public
>     key for the corresponding signature, and the signature
>     only covers the output itself (i.e. value and
>     `scriptPubKey`).
>     This means the signature has no `SIGHASH`.
>   * As the signature covers the public key, this prevents
>     malleation of a signature using one public key to a
>     signature for another public key.
> * After that is another signature.
>   * This signature is checked using `OP_CHECKSIG` semantics
>     (including `SIGHASH` support).
>   * The public key is the input point (i.e. stack top)
>     **MINUS** all the public keys of the indicated outputs.
>
> As a concrete example, suppose A, B, C, and D want to make a
> CoinPool (or offchain variant of such) with the following
> initial state:
>
> * A :=3D 10
> * B :=3D 6
> * C :=3D 4
> * D :=3D 22
>
> Let us assume that A, B, C, and D have generated public
> keys in such a way to avoid key cancellation (e.g.
> precommitment, or the MuSig scheme).
>
> The participants then generate promised outputs for the
> above, and each of them shares signatures for the promised
> outputs:
>
> * sign(a, "A :=3D 10")
> * sign(b, "B :=3D 6")
> * sign(c, "C :=3D 4")
> * sign(d, "D :=3D 22")
>
> Once that is done, they generate:
>
> * Q =3D A + B + C + D
> * P =3D h(Q|`<1> OP_EVICT`) * Q
>
> Then they spend their funds, creating a Taproot output:
>
> * P :=3D 42
>
> If all participants are online, they can move funds between
> each other (or to other addresses) by cooperatively signing
> using the point P, and the magic of Taproot means that use
> of `OP_EVICT` is not visible.
>
> Suppose however that B is offline.
> Then A, C, and D then decide to evict B.
> To do so, they create a transaction that has an output
> with "B :=3D 6", and they reveal the `OP_EVICT` Tapscript
> as well as sign(b, "B :=3D 6").
> This lets them change state and spend their funds without
> B being online.
> And B remains secure, as they cannot evict B except using
> the pre-signed output, which B certifies as their expected
> promised output.
>
> Note that the opcode as described above allows for multiple
> evictions in the same transaction.
> If B and C are offline, then the remaining participants
> simply need to expose multiple outputs in the same
> transaction.
>
> Security
> --------
>
> I am not a cryptographer.
> Thus, the security of this scheme is a conjecture.
>
> As long as key cancellation is protected against, it should
> be secure.
> The combined fund cannot be spent except if all participants
> agree.
> A smaller online participant set can be created only if a
> participant is evicted, and eviction will force the owned
> funds of the evicted participant to be instantiated.
> The other participants cannot synthesize an alternate
> signature signing a different value without knowledge of the
> privkey of the evicted participant.
>
> To prevent signature replay, each update of an updateable
> scheme like CoinPool et al should use a different pubkey
> for each participant for each state.
> As the signature covers the pubkey, it should be safe to
> use a non-hardened derivation scheme so that only a single
> root privkey is needed.
>
> Additional Discussion
> ---------------------
>
> ### Eviction Scheme
>
> We can consider that the eviction scheme proposed here is the
> following contract:
>
> * Either all of us agree on some transfer, OR,
> * Give me my funds and the rest of you can all go play with
>   your funds however you want.
>
> The signature that commits to a promised output is then the
> agreement that the particular participant believes they are
> entitled to a particular amount.
>
> We can consider that a participant can re-sign their output
> with a different amount, but that is why `OP_EVICT` requires
> the *other* participants to cooperatively sign as well.
> If the other participants cooperatively sign, they effectively
> agree to the participant re-signing for a different amount,
> and thus actually covered by "all of us agree".
>
> ### Pure SCRIPT Contracts
>
> A "pure SCRIPT contract" is a Taproot contract where the
> keyspend path is not desired, and the contract is composed of
> Tapscript branches.
>
> In such a case, the expected technique would be for the
> contract participants to agree on a NUMS point where none
> of the participants can know the scalar (private key) behind
> the point, and to use that as the internal Taproot pubkey
> `Q`.
> For complete protocols, the NUMS point can be a protocol-defined
> constant.
>
> As the `OP_EVICT` opcode requires that each promised output
> be signed, on the face of it, this technique cannot be used
> for `OP_EVICT`-promised outputs, as it is impossible to sign
> using the NUMS point.
>
> However, we should note that the requirement of a "pure SCRIPT"
> contract is that none of the participants can unilaterally
> sign an alternate spend.
> Using an N-of-N of the participants as the Taproot internal
> pubkey is sufficient to ensure this.
>
> As a concrete example: suppose we want an HTLC, which has a
> hashlock branch requiring participant A, and a timelock branch
> requiring participant B.
> Such a simple scheme would not require that both A and B be
> able to cooperatively spend the output, thus we might have
> preferred the technique of using a NUMS point as Taproot
> internal pubkey.
> But using a NUMS point would not allow any signature, even the
> `OP_EVICT`-required signatures-of-promised-outputs.
>
> Instead of using a NUMS point for the Taproot internal pubkey,
> we can use the sum of `A[tmp] + B[tmp]` (suitably protected
> against key cancellation).
> Then both A and B can cooperatively sign the promised output,
> and keep the promised output in an `OP_EVICT`-enforced UTXO.
> After creating the signature for the promised output, A and B
> can ensure that the keypath branch cannot be used by securely
> deleting the private keys for `A[tmp]` and `B[tmp]`
> respectively.
>
> ### Signature Half-Aggregation
>
> It is possible to batch-validate, and as `OP_EVICT` must
> validate at least two signatures (an eviction and the
> signature of the remaining) it makes sense to use batch
> validation for `OP_EVICT`.
>
> Of note is that Schnorr signatures allow for third-party
> half-aggregation, where the `s` components of multiple
> signatures are summed together, but the `R` components
> are not.
>
> (Warning: I am not aware of any security proofs that
> half-aggregation is actually **safe**!
> In particular, BIP-340 does not define half-aggregation,
> and its batch validation algorithm is not, to my naivete,
> extensible to half-aggregation.)
>
> Basically, if we are batch validating two signatures
> `(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`
> and `m[1]` signed by two keys `A[0]` and `A[1]`, we
> would do:
>
> * For `i =3D 0, 1`: `e[i] =3D h(R[i]|m[i])`
> * Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1=
]
> * A[1]`.
>
> As we can see, the `s` can be summed before being
> posted on the blockchain, as validators do not need
> individual `s[i]`.
> However, `R` cannot be summed as each one needs to be
> hashed.
>
> This half-aggregation is third-party, i.e. someone
> without any knowledge of any private keys can simply
> sum the `s` components of multiple signatures.
>
> As `OP_EVICT` always validates at least two signatures,
> using half-aggregation can remove at least 32 weight
> units, and each additional promised output being evicted
> is another signature whose `s` can be added to the sum.
> Of course, **that depends on half-aggregation being
> secure**.
>
> ### Relationship to Other Opcodes
>
> `OP_CTV` does other things than this opcode, and cannot
> be used as a direct alternative.
> In particular while `OP_CTV` *can* commit to a set of
> promised outputs, if a promised output needs to be
> published, the remaining funds are now distributed over a
> set of UTXOs.
> Thus, "reviving" the CoinPool (or offchain variant thereof)
> requires consuming multiple UTXOs, and the consumption of
> multiple UTXOs is risky unless specifically designd for it.
> (In particular, if the UTXOs have different signer sets,
> one signer set can initially cooperate to revive the
> CoinPool, then spend their UTXO to a different transaction,
> which if confirmed will invalidate the revival transaction.)
>
> This opcode seems largely in direct competitiong with
> `OP_TLUV`, with largely the same design goal.
> Its advantage is reduced number of eviction transactions,
> as multiple evictions, plus the revival of the CoinPool,
> can be put in a single transaction.
> It has the disadvantage relative to `OP_TLUV` of requiring
> point operations.
> I have not explored completely, but my instinct suggests
> that `OP_TLUV` use may require at least one signature
> validation anyway.
>
> It may be possible to implement `OP_EVICT` in terms of
> `OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction
> operation.
> However, `OP_EVICT` allows for the trivial implementation
> of batch validation (and, if half-aggregation is safe, to
> use half-aggregation instead), whereas we expect multiple
> `OP_CSFS` to be needed to implement this, without any
> possibility of batch validation.
> It may be possible to design an `OP_CSFS` variant that
> allows batch validation, such as by extending the virtual
> machine with an accumulator for pending signature
> validations.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr">Hi Zeeman,<br><br>&gt; After some thinking, I realized tha=
t it was the use of the<br>&gt; Merkle tree to represent the promised-but-o=
ffchain outputs of<br>&gt; the CoinPool that lead to the O(log N) space usa=
ge.<br>&gt; I then started thinking of alternative representations of<br>&g=
t; sets of promised outputs, which would not require O(log N)<br>&gt; revel=
ations by avoiding the tree structure.<br><br>In the context of payment poo=
ls, I think the O(log N) revelations can be avoided already today by pre-si=
gning all the combinations of promised-but-offchain outputs publications or=
der. However, this approach presents a factorial complexity and appears as =
an intractable problem for high-number of pool users.<br><br>I think this f=
actorial complexity issue is the primary problem to enable scalable payment=
 pools. This issue appears to be solvable by introducing an accumulator at =
the script interpreter level. IMO, the efficiency of the accumulated set re=
presentations comes as a second-order issue.<br><br>In the comparison of di=
fferent covenant primitives, I believe we should ask first if the flexibili=
ty offered is enough to solve the factorial complexity. I would say perform=
ance trade-offs analysis can only be conducted in logically equivalent prim=
itives.<br><br>&gt; A statechain is really just a CoinPool hosted inside a<=
br>&gt; =C2=A0Decker-Wattenhofer or Decker-Russell-Osuntokun construction.<=
br><br>Note, to the best of my knowledge, how to use LN-Penalty in the cont=
ext of multi-party construction is still an unsolved issue. If an invalidat=
ed state is published on-chain, how do you guarantee that the punished outp=
ut value is distributed &quot;fairly&quot; among the &quot;honest&quot; set=
 of users ? At least<br>where fairness is defined as a reasonable proportio=
n of the balances they owned in the latest state.<br><br>&gt; (To Bitcoin C=
ashers: this is not an IOU, this is *committed* and<br>&gt; can be enforced=
 onchain, that is enough to threaten your offchain<br>&gt; counterparties i=
nto behaving correctly.<br>&gt; They cannot gain anything by denying the ou=
tputs they promised,<br>&gt; you can always drop it onchain and have it enf=
orced, thus it is<br>&gt; not just merely an IOU, as IOUs are not necessari=
ly enforceable,<br>&gt; but this mechanism *would* be.<br>&gt; Blockchain a=
s judge+jury+executioner, not noisy marketplace.)<br><br>To be fair towards=
 the Bitcoin Cashers, I think there are still limitations of LN, we have no=
t solved yet. Especially, w.r.t to mass exits from the off-chain layers to =
the chain, where the blocks would stay fulfilled longer than the standard H=
TLC timelocks, at=C2=A0 a fee price point that the average user can&#39;t b=
uy... I&#39;m not sure if we have outlawed the &quot;bank runs&quot; scenar=
io yet of LN.<br><br>I would say yes the Blockchain is a juge authority, bu=
t in the worst-case we might be all in market competition to get enforcemen=
t.<br><br>&gt; In principle, a set of promised outputs, if the owners of th=
ose<br>&gt; outputs are peers, does not have *any* inherent order.<br>&gt; =
Thus, I started to think about a commitment scheme that does not<br>&gt; im=
pose any ordering during commitment.<br><br>I think we should dissociate a)=
 *outputs publication ordering* from the b) *spends paths ordering* itself.=
 Even if to each spend path a output publication is attached, the ordering =
constraint might not present the same complexity.<br><br>Under this distinc=
tion, are you sure that TLUV imposes an ordering on the output publication =
?<br><br>&gt; With `OP_TLUV`, however, it is possible to create an &quot;N-=
of-N With<br>&gt; Eviction&quot; construction.<br>&gt; When a participant i=
n the N-of-N is offline, but the remaining<br>&gt; participants want to adv=
ance the state of the construction, they<br>&gt; instead evict the offline =
participant, creating a smaller N-of-N<br>&gt; where *all* participants are=
 online, and continue operating.<br><br>I think we should dissociate two ty=
pes of pool spends : a) eviction by the pool unanimity in case of irrespons=
ive participants and b) unilateral withdrawal by a participant because of t=
he liquidity allocation policy. I think the distinction is worthy, as the p=
ool participant should be stable and the eviction not abused.<br><br>I&#39;=
m not sure if TLUV enables b), at least without transforming the unilateral=
 withdrawal into an eviction. To ensure the TLUV operation is correct=C2=A0=
 (spent leaf is removed, withdrawing participant point removed, etc), the s=
cript content must be inspected by *all* the participant. However, I believ=
e <br>knowledge of this content effectively allows you to play it out again=
st the pool at any time ? It&#39;s likely solvable at the price of a CHECKS=
IG.<br><br>`OP_EVICT`<br>----------<br><br>&gt; =C2=A0* If it is `1` that s=
imply means &quot;use the Taproot internal<br>&gt; =C2=A0 =C2=A0pubkey&quot=
;, as is usual for `OP_CHECKSIG`.<br><br>IIUC, this assumes the deployment =
of BIP118, where if the=C2=A0 public key is a single byte 0x01, the interna=
l pubkey is used<br>for verification.<br><br>&gt; =C2=A0* Output indices mu=
st not be duplicated, and indicated<br>&gt; =C2=A0 =C2=A0outputs must be Se=
gWit v1 (&quot;Taproot&quot;) outputs.<br><br>I think public key duplicatio=
n must not be verified. If a duplicated public key is present, the point is=
 subtracted twice from the internal pubkey and therefore the aggregated<br>=
key remains unknown ? So it sounds to me safe against replay attacks.<br><b=
r>&gt; =C2=A0* The public key is the input point (i.e. stack top)<br>&gt; =
=C2=A0 =C2=A0**MINUS** all the public keys of the indicated outputs.<br><br=
>Can you prevent eviction abuse where one counterparty threatens to evict e=
veryone as all the output signatures are known among participants and free =
to sum ? (at least not considering fees)<br><br>&gt; Suppose however that B=
 is offline.<br>&gt; Then A, C, and D then decide to evict B.<br>&gt; To do=
 so, they create a transaction that has an output<br>&gt; with &quot;B :=3D=
 6&quot;, and they reveal the `OP_EVICT` Tapscript<br>&gt; as well as sign(=
b, &quot;B :=3D 6&quot;).<br>&gt; This lets them change state and spend the=
ir funds without<br>&gt; B being online.<br>&gt; And B remains secure, as t=
hey cannot evict B except using<br>&gt; the pre-signed output, which B cert=
ifies as their expected<br>&gt; promised output.<br><br>I think in the cont=
ext of (off-chain) payment pool, OP_EVICT requires participant cooperation =
*after* the state update to allow a single participant to withdraw her fund=
s.<br><br>I believe this is unsafe if we retain as an off-chain constructio=
n security requirement that a participant should have the unilateral means =
to enforce the latest agreed upon state at any time during the construction=
 lifetime.<br><br>I would say an OP_EVICT construction could solve the issu=
e where the pool participants exchange pre-signatures of the internal pubke=
y with the withdrawing participant point removed. However, I believe such f=
ix would a) block promised outputs batching (or at least in a pre-committed=
 way like radix pools) and b) be grieved by the factorial complexity descri=
bed above.<br><br>&gt; The combined fund cannot be spent except if all part=
icipants<br>&gt; agree.<br><br>If all participants agree minus the evicted =
ones, correct ? The output promises signatures are shared at state setup, t=
herefore no additional contribution from the evicted participant (I think).=
<br><br>&gt; To prevent signature replay, each update of an updateable<br>&=
gt; scheme like CoinPool et al should use a different pubkey<br>&gt; for ea=
ch participant for each state.<br><br>I&#39;m not even sure if it&#39;s req=
uired with OP_EVICT, as the publication of the promised output are ultimate=
ly restrained by a signature of the updated internal pubkey, this set of si=
gners verify that promised output N does bind to the published state N ?<br=
><br>&gt; Its advantage is reduced number of eviction transactions,<br>&gt;=
 as multiple evictions, plus the revival of the CoinPool,<br>&gt; can be pu=
t in a single transaction.<br>&gt; It has the disadvantage relative to `OP_=
TLUV` of requiring<br>&gt; point operations.<br>&gt; I have not explored co=
mpletely, but my instinct suggests<br>&gt; that `OP_TLUV` use may require a=
t least one signature<br>&gt; validation anyway.<br><br>I believe you can s=
lightly modify TLUV to make it functional for CoinPool revival, where you w=
ant to prevent equivocation among the remaining set of signers. Though, I&#=
39;m leaning to agree that you may require at least one signature validatio=
n=C2=A0 (first to restrain spend authorization inside the pool participants=
, second to attach fees at broadcast-time).<br><br>&gt; It may be possible =
to design an `OP_CSFS` variant that<br>&gt; allows batch validation, such a=
s by extending the virtual<br>&gt; machine with an accumulator for pending =
signature<br>&gt; validations.<br><br>I agree that in the context of paymen=
t pools, aggregation of non-cooperative unilateral spends is a scalability =
bottleneck, especially in the face of mempools congestion. If we rely on me=
rkle<br>trees as the accumulator primitive, there is still the path to aggr=
egate many branches in-flight.<br><br>Any misunderstandings of this proposa=
l are my own.<br>,<br>Antoine<br></div><br><div class=3D"gmail_quote"><div =
dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0jeu. 17 f=C3=A9vr. 2022 =C3=A0=C2=
=A021:45, ZmnSCPxj via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.=
linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9=
crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">`OP_=
EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D<br>
<br>
In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to<br>
implement CoinPools and similar constructions.<br>
<br>
`Jeremy` observed that due to the use of Merkle tree paths, an<br>
`OP_TLUV` would require O(log N) hash revelations in order to<br>
reach a particular tapleaf, which, in the case of a CoinPool,<br>
would then delete itself after spending only a particular amount<br>
of funds.<br>
He then observed that `OP_CTV` trees also require a similar<br>
revelation of O(log N) transactions, but with the advantage that<br>
once revealed, the transactions can then be reused, thus overall<br>
the expectation is that the number of total bytes onchain is<br>
lesser compared to `OP_TLUV`.<br>
<br>
After some thinking, I realized that it was the use of the<br>
Merkle tree to represent the promised-but-offchain outputs of<br>
the CoinPool that lead to the O(log N) space usage.<br>
I then started thinking of alternative representations of<br>
sets of promised outputs, which would not require O(log N)<br>
revelations by avoiding the tree structure.<br>
<br>
Promised Outputs<br>
----------------<br>
<br>
Fundamentally, we can consider that a solution for scaling<br>
Bitcoin would be to *promise* that some output *can* appear<br>
onchain at some point in the future, without requiring that the<br>
output be shown onchain *right now*.<br>
Then, we can perform transactional cut-through on spends of the<br>
promised outputs, without requiring onchain activity (&quot;offchain&quot;)=
.<br>
Only if something Really Bad (TM) happens do we need to actually<br>
drop the latest set of promised outputs onchain, where it has to<br>
be verified globally by all fullnodes (and would thus incur scaling<br>
and privacy costs).<br>
<br>
As an example of the above paradigm, consider the Lightning<br>
Network.<br>
Outputs representing the money of each party in a channel are<br>
promised, and *can* appear onchain (via the unilateral close<br>
mechanism).<br>
In the meantime, there is a mechanism for performing cut-through,<br>
allowing transfers between channel participants; any number of<br>
transactions can be performed that are only &quot;solidified&quot; later,<b=
r>
without expensive onchain activity.<br>
<br>
Thus:<br>
<br>
* A CoinPool is really a way to commit to promised outputs.<br>
=C2=A0 To change the distribution of those promised outputs, the<br>
=C2=A0 CoinPool operators need to post an onchain transaction, but<br>
=C2=A0 that is only a 1-input-1-output transaction, and with Schnorr<br>
=C2=A0 signatures the single input requires only a single signature.<br>
=C2=A0 But in case something Really Bad (TM) happens, any participant<br>
=C2=A0 can unilaterally close the CoinPool, instantiating the promised<br>
=C2=A0 outputs.<br>
* A statechain is really just a CoinPool hosted inside a<br>
=C2=A0 Decker-Wattenhofer or Decker-Russell-Osuntokun construction.<br>
=C2=A0 This allows changing the distribution of those promised outputs<br>
=C2=A0 without using an onchain transaction --- instead, a new state<br>
=C2=A0 in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction<br>
=C2=A0 is created containing the new state, which invalidates all older<br>
=C2=A0 states.<br>
=C2=A0 Again, any participant can unilaterally shut it down, exposing<br>
=C2=A0 the state of the inner CoinPool.<br>
* A channel factory is really just a statechain where the<br>
=C2=A0 promised outputs are not simple 1-of-1 single-owner outputs,<br>
=C2=A0 but are rather 2-of-2 channels.<br>
=C2=A0 This allows graceful degradation, where even if the statechain<br>
=C2=A0 (&quot;factory&quot;) layer has missing participants, individual 2-o=
f-2<br>
=C2=A0 channels can still continue operating as long as they do not<br>
=C2=A0 involve missing participants, without requiring all participants<br>
=C2=A0 to be online for large numbers of transactions.<br>
<br>
We can then consider that the base CoinPool usage should be enough,<br>
as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be<br>
used to implement statechains and channels and channel factories.<br>
<br>
I therefore conclude that what we really need is &quot;just&quot; a way to<=
br>
commit ourselves to exposing a set of promised outputs, with the<br>
proviso that if we all agree, we can change that set (without<br>
requiring that the current or next set be exposed, for both<br>
scaling and privacy).<br>
<br>
(To Bitcoin Cashers: this is not an IOU, this is *committed* and<br>
can be enforced onchain, that is enough to threaten your offchain<br>
counterparties into behaving correctly.<br>
They cannot gain anything by denying the outputs they promised,<br>
you can always drop it onchain and have it enforced, thus it is<br>
not just merely an IOU, as IOUs are not necessarily enforceable,<br>
but this mechanism *would* be.<br>
Blockchain as judge+jury+executioner, not noisy marketplace.)<br>
<br>
Importantly: both `OP_CTV` and `OP_TLUV` force the user to<br>
decide on a particular, but ultimately arbitrary, ordering for<br>
promised outputs.<br>
In principle, a set of promised outputs, if the owners of those<br>
outputs are peers, does not have *any* inherent order.<br>
Thus, I started to think about a commitment scheme that does not<br>
impose any ordering during commitment.<br>
<br>
Digression: N-of-N With Eviction<br>
--------------------------------<br>
<br>
An issue with using an N-of-N construction is that if any single<br>
participant is offline, the construction cannot advance its state.<br>
<br>
This has lead to some peopple proposing to instead use K-of-N<br>
once N reaches much larger than 2 participants for CoinPools/statechains/<b=
r>
channel factories.<br>
<br>
However, even so, K-of-N still requires that K participants remain<br>
online, and the level K is a security parameter.<br>
If less than K participants are online, then the construction<br>
*still* cannot advance its state.<br>
<br>
Worse, because K &lt; N, a single participant can have its funds<br>
outright stolen by a quorum of K participants.<br>
There is no way to prove that the other participants in the same<br>
construction are not really sockpuppets of the same real-world<br>
entity, thus it is entirely possible that the K quorum is actually<br>
just a single participant that is now capable of stealing the<br>
funds of all the other participants.<br>
The only way to avoid this is to use N-oF-N: N-of-N requires<br>
*your* keys, thus the coins are *your* coins.<br>
In short: K-of-N, as it allows the state to be updated without your<br>
keys (on the excuse that &quot;if you are offline, we need to be able to<br=
>
update state&quot;), is *not your keys not your coins*.<br>
<br>
K-of-N should really only be used if all N are your sockpuppets,<br>
and you want to HODL your funds.<br>
This is the difference between consensus &quot;everyone must agree&quot; an=
d<br>
voting &quot;enough sockpuppets can be used to overpower you&quot;.<br>
<br>
With `OP_TLUV`, however, it is possible to create an &quot;N-of-N With<br>
Eviction&quot; construction.<br>
When a participant in the N-of-N is offline, but the remaining<br>
participants want to advance the state of the construction, they<br>
instead evict the offline participant, creating a smaller N-of-N<br>
where *all* participants are online, and continue operating.<br>
<br>
This avoids the *not your keys not your coins* problem of K-of-N<br>
constructions, while simultaneously providing a way to advance<br>
the state without the full participant set being online.<br>
<br>
The only real problem with `OP_TLUV` is that it takes O(log N)<br>
hash revelations to evict one participant, and each evicted<br>
participant requires one separate transaction.<br>
<br>
K-of-N has the &quot;advantage&quot; that even if you are offline, the stat=
e<br>
can be advanced without evicting you.<br>
However, as noted, as the coins can be spent without your keys,<br>
the coins are not your coins, thus this advantage may be considered<br>
dubious --- whether you are online or offline, a quorum of K can<br>
outright steal your coins.<br>
Eviction here requires that your coins be returned to your control.<br>
<br>
Committing To An Unordered Set<br>
------------------------------<br>
<br>
In an N-of-N CoinPool/statechain/channel factory, the ownership<br>
of a single onchain UTXO is shared among N participants.<br>
That is, there are a number of promised outputs, not exposed<br>
onchain, which the N participants agree on as the &quot;real&quot; current<=
br>
state of the construction,<br>
However, the N participants can also agree to change the current<br>
state of the construction, if all of them sign off on the change.<br>
<br>
Each of the promised outputs has a value, and the sum of all<br>
promised values is the value of the onchain UTXO.<br>
Interestingly, each of the promised outputs also has an SECP256K1<br>
point that can be used as a public key, and the sum of all<br>
promised points is the point of the onchain UTXO.<br>
<br>
Thus, the onchain UTXO can serve as a commitment to the sum of<br>
the promised outputs.<br>
The problem is committing to each of the individual promised<br>
outputs.<br>
<br>
We can observe that a digital signature not only proves knowledge<br>
of a private key, it also commits to a particular message.<br>
Thus, we can make each participant sign their own expected<br>
promised output, and share the signature for their promised<br>
output.<br>
<br>
When a participant is to be evicted, the other participants<br>
take the signature for the promised output of the to-be-evicted<br>
participant, and show it onchain, to attest to the output.<br>
Then, the onchain mechanism should then allow the rest of the<br>
funds to be controlled by the N-of-N set minus the evicted<br>
participant.<br>
<br>
`OP_EVICT`<br>
----------<br>
<br>
With all that, let me now propose the `OP_EVICT` opcode.<br>
<br>
`OP_EVICT` accepts a variable number of arguments.<br>
<br>
* The stack top is either the constant `1`, or an SECP256K1<br>
=C2=A0 point.<br>
=C2=A0 * If it is `1` that simply means &quot;use the Taproot internal<br>
=C2=A0 =C2=A0 pubkey&quot;, as is usual for `OP_CHECKSIG`.<br>
* The next stack item is a number, equal to the number of<br>
=C2=A0 outputs that were promised, and which will now be evicted.<br>
* The next stack items will alternate:<br>
=C2=A0 * A number indicating an output index.<br>
=C2=A0 * A signature for that output.<br>
=C2=A0 * Output indices must not be duplicated, and indicated<br>
=C2=A0 =C2=A0 outputs must be SegWit v1 (&quot;Taproot&quot;) outputs.<br>
=C2=A0 =C2=A0 The public key of the output will be taken as the public<br>
=C2=A0 =C2=A0 key for the corresponding signature, and the signature<br>
=C2=A0 =C2=A0 only covers the output itself (i.e. value and<br>
=C2=A0 =C2=A0 `scriptPubKey`).<br>
=C2=A0 =C2=A0 This means the signature has no `SIGHASH`.<br>
=C2=A0 * As the signature covers the public key, this prevents<br>
=C2=A0 =C2=A0 malleation of a signature using one public key to a<br>
=C2=A0 =C2=A0 signature for another public key.<br>
* After that is another signature.<br>
=C2=A0 * This signature is checked using `OP_CHECKSIG` semantics<br>
=C2=A0 =C2=A0 (including `SIGHASH` support).<br>
=C2=A0 * The public key is the input point (i.e. stack top)<br>
=C2=A0 =C2=A0 **MINUS** all the public keys of the indicated outputs.<br>
<br>
As a concrete example, suppose A, B, C, and D want to make a<br>
CoinPool (or offchain variant of such) with the following<br>
initial state:<br>
<br>
* A :=3D 10<br>
* B :=3D 6<br>
* C :=3D 4<br>
* D :=3D 22<br>
<br>
Let us assume that A, B, C, and D have generated public<br>
keys in such a way to avoid key cancellation (e.g.<br>
precommitment, or the MuSig scheme).<br>
<br>
The participants then generate promised outputs for the<br>
above, and each of them shares signatures for the promised<br>
outputs:<br>
<br>
* sign(a, &quot;A :=3D 10&quot;)<br>
* sign(b, &quot;B :=3D 6&quot;)<br>
* sign(c, &quot;C :=3D 4&quot;)<br>
* sign(d, &quot;D :=3D 22&quot;)<br>
<br>
Once that is done, they generate:<br>
<br>
* Q =3D A + B + C + D<br>
* P =3D h(Q|`&lt;1&gt; OP_EVICT`) * Q<br>
<br>
Then they spend their funds, creating a Taproot output:<br>
<br>
* P :=3D 42<br>
<br>
If all participants are online, they can move funds between<br>
each other (or to other addresses) by cooperatively signing<br>
using the point P, and the magic of Taproot means that use<br>
of `OP_EVICT` is not visible.<br>
<br>
Suppose however that B is offline.<br>
Then A, C, and D then decide to evict B.<br>
To do so, they create a transaction that has an output<br>
with &quot;B :=3D 6&quot;, and they reveal the `OP_EVICT` Tapscript<br>
as well as sign(b, &quot;B :=3D 6&quot;).<br>
This lets them change state and spend their funds without<br>
B being online.<br>
And B remains secure, as they cannot evict B except using<br>
the pre-signed output, which B certifies as their expected<br>
promised output.<br>
<br>
Note that the opcode as described above allows for multiple<br>
evictions in the same transaction.<br>
If B and C are offline, then the remaining participants<br>
simply need to expose multiple outputs in the same<br>
transaction.<br>
<br>
Security<br>
--------<br>
<br>
I am not a cryptographer.<br>
Thus, the security of this scheme is a conjecture.<br>
<br>
As long as key cancellation is protected against, it should<br>
be secure.<br>
The combined fund cannot be spent except if all participants<br>
agree.<br>
A smaller online participant set can be created only if a<br>
participant is evicted, and eviction will force the owned<br>
funds of the evicted participant to be instantiated.<br>
The other participants cannot synthesize an alternate<br>
signature signing a different value without knowledge of the<br>
privkey of the evicted participant.<br>
<br>
To prevent signature replay, each update of an updateable<br>
scheme like CoinPool et al should use a different pubkey<br>
for each participant for each state.<br>
As the signature covers the pubkey, it should be safe to<br>
use a non-hardened derivation scheme so that only a single<br>
root privkey is needed.<br>
<br>
Additional Discussion<br>
---------------------<br>
<br>
### Eviction Scheme<br>
<br>
We can consider that the eviction scheme proposed here is the<br>
following contract:<br>
<br>
* Either all of us agree on some transfer, OR,<br>
* Give me my funds and the rest of you can all go play with<br>
=C2=A0 your funds however you want.<br>
<br>
The signature that commits to a promised output is then the<br>
agreement that the particular participant believes they are<br>
entitled to a particular amount.<br>
<br>
We can consider that a participant can re-sign their output<br>
with a different amount, but that is why `OP_EVICT` requires<br>
the *other* participants to cooperatively sign as well.<br>
If the other participants cooperatively sign, they effectively<br>
agree to the participant re-signing for a different amount,<br>
and thus actually covered by &quot;all of us agree&quot;.<br>
<br>
### Pure SCRIPT Contracts<br>
<br>
A &quot;pure SCRIPT contract&quot; is a Taproot contract where the<br>
keyspend path is not desired, and the contract is composed of<br>
Tapscript branches.<br>
<br>
In such a case, the expected technique would be for the<br>
contract participants to agree on a NUMS point where none<br>
of the participants can know the scalar (private key) behind<br>
the point, and to use that as the internal Taproot pubkey<br>
`Q`.<br>
For complete protocols, the NUMS point can be a protocol-defined<br>
constant.<br>
<br>
As the `OP_EVICT` opcode requires that each promised output<br>
be signed, on the face of it, this technique cannot be used<br>
for `OP_EVICT`-promised outputs, as it is impossible to sign<br>
using the NUMS point.<br>
<br>
However, we should note that the requirement of a &quot;pure SCRIPT&quot;<b=
r>
contract is that none of the participants can unilaterally<br>
sign an alternate spend.<br>
Using an N-of-N of the participants as the Taproot internal<br>
pubkey is sufficient to ensure this.<br>
<br>
As a concrete example: suppose we want an HTLC, which has a<br>
hashlock branch requiring participant A, and a timelock branch<br>
requiring participant B.<br>
Such a simple scheme would not require that both A and B be<br>
able to cooperatively spend the output, thus we might have<br>
preferred the technique of using a NUMS point as Taproot<br>
internal pubkey.<br>
But using a NUMS point would not allow any signature, even the<br>
`OP_EVICT`-required signatures-of-promised-outputs.<br>
<br>
Instead of using a NUMS point for the Taproot internal pubkey,<br>
we can use the sum of `A[tmp] + B[tmp]` (suitably protected<br>
against key cancellation).<br>
Then both A and B can cooperatively sign the promised output,<br>
and keep the promised output in an `OP_EVICT`-enforced UTXO.<br>
After creating the signature for the promised output, A and B<br>
can ensure that the keypath branch cannot be used by securely<br>
deleting the private keys for `A[tmp]` and `B[tmp]`<br>
respectively.<br>
<br>
### Signature Half-Aggregation<br>
<br>
It is possible to batch-validate, and as `OP_EVICT` must<br>
validate at least two signatures (an eviction and the<br>
signature of the remaining) it makes sense to use batch<br>
validation for `OP_EVICT`.<br>
<br>
Of note is that Schnorr signatures allow for third-party<br>
half-aggregation, where the `s` components of multiple<br>
signatures are summed together, but the `R` components<br>
are not.<br>
<br>
(Warning: I am not aware of any security proofs that<br>
half-aggregation is actually **safe**!<br>
In particular, BIP-340 does not define half-aggregation,<br>
and its batch validation algorithm is not, to my naivete,<br>
extensible to half-aggregation.)<br>
<br>
Basically, if we are batch validating two signatures<br>
`(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`<br>
and `m[1]` signed by two keys `A[0]` and `A[1]`, we<br>
would do:<br>
<br>
* For `i =3D 0, 1`: `e[i] =3D h(R[i]|m[i])`<br>
* Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1] =
* A[1]`.<br>
<br>
As we can see, the `s` can be summed before being<br>
posted on the blockchain, as validators do not need<br>
individual `s[i]`.<br>
However, `R` cannot be summed as each one needs to be<br>
hashed.<br>
<br>
This half-aggregation is third-party, i.e. someone<br>
without any knowledge of any private keys can simply<br>
sum the `s` components of multiple signatures.<br>
<br>
As `OP_EVICT` always validates at least two signatures,<br>
using half-aggregation can remove at least 32 weight<br>
units, and each additional promised output being evicted<br>
is another signature whose `s` can be added to the sum.<br>
Of course, **that depends on half-aggregation being<br>
secure**.<br>
<br>
### Relationship to Other Opcodes<br>
<br>
`OP_CTV` does other things than this opcode, and cannot<br>
be used as a direct alternative.<br>
In particular while `OP_CTV` *can* commit to a set of<br>
promised outputs, if a promised output needs to be<br>
published, the remaining funds are now distributed over a<br>
set of UTXOs.<br>
Thus, &quot;reviving&quot; the CoinPool (or offchain variant thereof)<br>
requires consuming multiple UTXOs, and the consumption of<br>
multiple UTXOs is risky unless specifically designd for it.<br>
(In particular, if the UTXOs have different signer sets,<br>
one signer set can initially cooperate to revive the<br>
CoinPool, then spend their UTXO to a different transaction,<br>
which if confirmed will invalidate the revival transaction.)<br>
<br>
This opcode seems largely in direct competitiong with<br>
`OP_TLUV`, with largely the same design goal.<br>
Its advantage is reduced number of eviction transactions,<br>
as multiple evictions, plus the revival of the CoinPool,<br>
can be put in a single transaction.<br>
It has the disadvantage relative to `OP_TLUV` of requiring<br>
point operations.<br>
I have not explored completely, but my instinct suggests<br>
that `OP_TLUV` use may require at least one signature<br>
validation anyway.<br>
<br>
It may be possible to implement `OP_EVICT` in terms of<br>
`OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction<br>
operation.<br>
However, `OP_EVICT` allows for the trivial implementation<br>
of batch validation (and, if half-aggregation is safe, to<br>
use half-aggregation instead), whereas we expect multiple<br>
`OP_CSFS` to be needed to implement this, without any<br>
possibility of batch validation.<br>
It may be possible to design an `OP_CSFS` variant that<br>
allows batch validation, such as by extending the virtual<br>
machine with an accumulator for pending signature<br>
validations.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000000ef30305d84ec871--