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
|
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 7962BC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 11 Nov 2022 21:50:14 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 3F10F4013E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 11 Nov 2022 21:50:14 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 3F10F4013E
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20210112 header.b=OLckkblr
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.098
X-Spam-Level:
X-Spam-Status: No, score=-0.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, PDS_OTHER_BAD_TLD=1.999,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001,
URI_DOTEDU=0.001] autolearn=no autolearn_force=no
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 AmjXr8mLPyRW
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 11 Nov 2022 21:50:10 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 7D5E6400B8
Received: from mail-il1-x134.google.com (mail-il1-x134.google.com
[IPv6:2607:f8b0:4864:20::134])
by smtp2.osuosl.org (Postfix) with ESMTPS id 7D5E6400B8
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 11 Nov 2022 21:50:10 +0000 (UTC)
Received: by mail-il1-x134.google.com with SMTP id q5so3123709ilt.13
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 11 Nov 2022 13:50:10 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:from:to:cc:subject:date:message-id:reply-to;
bh=c7ZlcXWFBvDDNdmF3eiRsNiV+b+hlmXImS/TUEYRKMI=;
b=OLckkblrfkiPBGF/X+bVVLhuyPjlueOzyMfSpviWFTHYLWZq6yo4bU6Kfu3aRg+ZyE
3CCud9rVhh3NBJIzA2SetwXSIVMNBsljgG01CDgJbQPW39G3dRdPMzQhNLGMrEY8Mmm0
zSPdT7c2BdvmDIyOJBlBNw/lIYTQlorlC4WRCk5fh6ErAvxMcqJvbyJU33ntHHcCEog6
XzHniFr2owG2N/Zz7epnmKbp+rh+15gg8/tY5t/KJ16ZFF+G3L+1hZ/CPJImusC4AI9b
bnEHkUuF7pRlanf8sE2TjScmf0ksZGuncIDAH8JqE4Mf6XYyYGIpPoIlZ+CKQ8hT55UY
wqhw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
bh=c7ZlcXWFBvDDNdmF3eiRsNiV+b+hlmXImS/TUEYRKMI=;
b=UBNgg1ayhHmFw0klrzHrYg0GozsUasfzs5vWr25ZwnNOrLW7L3rvm4oRA13X61Ks8s
ZsjvkMHhtT7qDbZy1WtfNIjIPE/ijsKeEgxnACFAF45/eWJyrxuWO7SqTz89ZGSSuvct
dN5c82k9CWleg2QXlAYR9gQuVUy0GCksyZrECvX+BF8nPjuQDEoF5334IhemJmOAsS+n
ZSXGcuIQY8D2wh42eur6a9dkc6rQWm8Mi/2YGPB1C/4r9mwjYdy9mW2osRv1nDmUWQVH
Ha1rSDBtQRZ8Gurb5EMGp0C8FTyg1Ysef/y9NW3Ybzw5idwEo0i5ISJ61eADvb0mW9mL
i9TA==
X-Gm-Message-State: ANoB5pnSCSKP3Z2d62KdOB772vXLJU//99ixE36EGt8uX/syfYBXec0t
gMw1HVB8beceXJHzLRr0ot6cy/7HPCRp+YIt0p7V+M5Y2vFOcQ==
X-Google-Smtp-Source: AA0mqf40skRlcHKPu0WLauLexeqI3fvybrzyJWk9msnjM1L7Hit3VIaHf5vjlpm4S/dbGlGxXTv+JnFo00FP63vX+g4=
X-Received: by 2002:a92:7d0c:0:b0:302:4948:2a9f with SMTP id
y12-20020a927d0c000000b0030249482a9fmr597254ilc.70.1668203409194; Fri, 11 Nov
2022 13:50:09 -0800 (PST)
MIME-Version: 1.0
References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
In-Reply-To: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Fri, 11 Nov 2022 16:49:58 -0500
Message-ID: <CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
To: Salvatore Ingala <salvatore.ingala@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000009e453205ed38dfdf"
X-Mailman-Approved-At: Fri, 11 Nov 2022 21:57:06 +0000
Subject: Re: [bitcoin-dev] Merkleize All The Things
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, 11 Nov 2022 21:50:14 -0000
--0000000000009e453205ed38dfdf
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Salvatore,
Thanks for bringing forward this MATT proposal!
Here my (rough) understanding of the protocol, the participants decompose
the entire computation into a number N of steps, each assigned a tapleaf,
each computation is a triplet (state_start, operation, state_end), the
tapleaves are built into a Merkle tree, the current state of the FSM is
also encoded in the Taproot output. The Merkle tree is committed in some
Script branch where a timelock is present to guarantee challenge (e.g "f(x)
=3D ?" OP_CHALLENGE + 100 OP_CSV). A funding transaction is broadcast to lo=
ck
the funds, participants can leverage this funding output to play out
off-chain the computation steps. To advance the resolution, a participant
spends the funding output with a witness embedding all the computation
trace encoded as Merkle branch and prove some statement "f(x) =3D y". Until
the CSV expires, another participant can contest by presenting another
witness with another computation trace. What is unclear to me is how the
contract's state issued off-chain can alter the pre-committed state
transitions. I think what could gain in clarity is the translation of the
bisection protocol steps in more complete new opcodes.
Another high-level remark, even if we assume any arbitrary computation can
be encoded in a Merkle Tree, as the computation grows in complexity, the
corresponding trace also increases in (witness) space. There might be some
economic bounds on the generalized smart contracts you can engage in, as
the worst-case scenario might be beyond your fee-bumping reserves. Less
flexible, but more templated opcodes for the same use-cases might make it
more affordable. At the same time, the ability to encode any cryptosystem
as the function f sounds really interesting.
Best,
Antoine
Le mar. 8 nov. 2022 =C3=A0 05:13, Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
> Hi list,
>
> I have been working on some notes to describe an approach that uses
> covenants in order to enable general smart contracts in bitcoin. You can
> find them here:
>
> https://merkle.fun
>
> The approach has a number of desirable features:
>
> - small impact to layer 1;
> - not application-specific, very general;
> - it fits well into P2TR;
> - it does not require new cryptographic assumptions, nor any construction
> that has not withstood the test of time.
>
> This content was presented at the BTCAzores unconference, where it
> received the name of MATT =E2=88=92 short for Merkleize All The Things.
> In fact, no other cryptographic primitive is required, other than Merkle
> trees.
>
> I believe this construction gets close to answering the question of how
> small a change on bitcoin's layer 1 would suffice to enable arbitrary sma=
rt
> contracts.
>
> It is not yet at the stage where a formal proposal can be made, therefore
> the proposed specs are only for illustrative purposes.
>
> The same content is reformatted below for the mailing list.
>
> Looking forward to hearing about your comments and improvements.
> Salvatore Ingala
>
>
> =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
>
>
> # General smart contracts in bitcoin via covenants
>
> Covenants are UTXOs that are encumbered with restrictions on the outputs
> of the transaction spending the UTXO. More formally, we can define a
> covenant any UTXO such that at least one of its spending conditions is
> valid only if one or more of the outputs=E2=80=99 scriptPubKey satisfies =
certain
> restrictions.
>
> Generally, covenant proposals also add some form of introspection (that
> is, the ability for Script to access parts of the inputs/outputs, or the
> blockchain history).
>
> In this note, we want to explore the possibilities unleashed by the
> addition of a covenant with the following properties:
>
> - introspection limited to a single hash attached to the UTXO (the
> =E2=80=9Ccovenant data=E2=80=9D), and input/output amounts;
> - pre-commitment to every possible future script (but not their data);
> - few simple opcodes operating with the covenant data.
>
> We argue that such a simple covenant construction is enough to extend the
> power of bitcoin=E2=80=99s layer 1 to become a universal settlement layer=
for
> arbitrary computation.
>
> Moreover, the covenant can elegantly fit within P2TR transactions, withou=
t
> any substantial increase for the workload of bitcoin nodes.
>
> A preliminary version of these notes was presented and discussed at the
> BTCAzores Unconference [1], on 23rd September 2022.
>
>
> # Preliminaries
>
> We can think of a smart contract as a =E2=80=9Cprogram=E2=80=9D that upda=
tes a certain
> state according to predetermined rules (which typically include access
> control by authorizing only certain public keys to perform certain
> actions), and that can possibly lock/unlock some coins of the underlying
> blockchain according to the same rules.
>
> The exact definition will be highly dependent on the properties of the
> underlying blockchain.
>
> In bitcoin, the only state upon which all the nodes reach consensus is th=
e
> UTXO set; other blockchains might have other data structures as part of t=
he
> consensus, like a key-value store that can be updated as a side effect of
> transaction execution.
>
> In this section we explore the following concepts in order to set the
> framework for a definition of smart contracts that fits the structure of
> bitcoin:
>
> - the contract=E2=80=99s state: the =E2=80=9Cmemory=E2=80=9D the smart co=
ntract operates on;
> - state transitions: the rules to update the contract=E2=80=99s state;
> - covenants: the technical means that can allow contracts to function in
> the context of a bitcoin UTXO.
>
> In the following, an on-chain smart contract is always represented as a
> single UTXO that implicitly embeds the contract=E2=80=99s state and possi=
bly
> controls some coins that are =E2=80=9Clocked=E2=80=9D in it. More general=
ly, one could
> think of smart contracts that are represented in a set of multiple UTXOs;
> we leave the exploration of generalizations of the framework to future
> research.
>
> ## State
>
> Any interesting =E2=80=9Cstate=E2=80=9D of a smart contract can ultimatel=
y be encoded as a
> list, where each element is either a bit, a fixed-size integers, or an
> arbitrary byte string.
>
> Whichever the choice, it does not really affect what kinds of computation=
s
> are expressible, as long as one is able to perform some basic computation=
s
> on those elements.
>
> In the following, we will assume without loss of generality that
> computations happen on a state which is a list of fixed length S =3D [s_1=
,
> s_2, =E2=80=A6, s_n], where each s_i is a byte string.
>
> ### Merkleized state
>
> By constructing a Merkle tree that has the (hashes of) the elements of S
> in the leaves, we can produce a short commitment h_S to the entire list S
> with the following properties (that hold for a verifier that only knows
> h_S):
>
> - a (log n)-sized proof can prove the value of an element s_i;
> - a (log n + |x|)-sized proof can prove the new commitment h_S=E2=80=99, =
where S=E2=80=99
> is a new list obtained by replacing the value of a certain leaf with x.
>
> This allows to compactly commit to a RAM, and to prove correctness of RAM
> updates.
>
> In other words, a stateful smart contract can represent an arbitrary stat=
e
> in just a single hash, for example a 32-byte SHA256 output.
>
> ### State transitions and UTXOs
>
> We can conveniently represent a smart contract as a finite state machine
> (FSM), where exactly one node can be active at a given time. Each node ha=
s
> an associated state as defined above, and a set of transition rules that
> define:
>
> - who can use the rule;
> - what is the next active node in the FSM;
> - what is the state of the next active node.
>
> It is then easy to understand how covenants can conveniently represent an=
d
> enforce the smart contracts in this framework:
>
> - The smart contract is instantiated by creating a UTXO encumbered with a
> covenant; the smart contract is in the initial node of the FSM.
> - The UTXO=E2=80=99s scriptPubKey specifies the current state and the val=
id
> transitions.
> - The UTXO(s) produced after a valid transition might or might not be
> further encumbered, according to the rules.
>
> Therefore, what is necessary in order to enable this framework in bitcoin
> Script is a covenant that allows the enforcement of such state transition=
s,
> by only allowing outputs that commit to a valid next node (and
> corresponding state) in the FSM.
>
> It is not difficult to show that arbitrary computation is possible over
> the committed state, as long as relatively simple arithmetic or logical
> operations are available over the state.
>
> Remark: using an acyclic FSM does not reduce the expressivity of the smar=
t
> contracts, as any terminating computation on bounded-size inputs which
> requires cycles can be unrolled into an acyclic one.
>
> ### Merkleized state transitions
>
> Similarly to how using Merkle trees allows to succinctly represent
> arbitrary data with a short, 32-byte long summary, the same trick allows =
to
> succinctly represent arbitrary state transitions (the smart contract=E2=
=80=99s
> code) with a single 32-byte hash. Each of the possible state transitions =
is
> encoded as a Script which is put in a leaf of a Merkle tree; the Merkle
> root of this tree is a commitment to all the possible state transitions.
> This is exactly what the taptree achieves in Taproot (see BIP-0341 [2]).
>
> Later sections in this document will suggest a possible way of how both
> the contract=E2=80=99s state and valid transition rules could be represen=
ted in
> UTXOs.
>
> ## On-chain computation?!
>
> Should the chain actually do computation?
>
> If naively designed, the execution of a contract might require a large
> number of transactions, which is not feasible.
>
> While the covenant approach does indeed enable a chain of transactions to
> perform arbitrary computation, simple economic considerations will push
> protocol designers to perform any non-trivial computation off-chain, and
> instead use the blockchain consensus only to verify the computation; or, =
if
> possible, skip the verification altogether.
>
> The fundamental fact that a blockchain=E2=80=99s layer 1 never actually n=
eeds to
> run complex programs in order to enable arbitrary complex smart contracti=
ng
> was observed in the past, for example in a 2016 post by Greg Maxwell [3].
>
> Vitalik Buterin popularized the concept of "functionality escape velocity=
"
> [4] to signify the minimum amount of functionality required on layer 1 in
> order to enable anything else to be built on top (that is, on layer 2 and
> beyond).
>
> In the following section, we will argue that a simple covenant
> construction suffices to achieve the functionality escape velocity in the
> UTXO model.
>
>
> # Commitments to computation and fraud challenges
>
> In this section, we explore how a smart contract that requires any
> non-trivial computation f : X --> Y (that is too expensive or not feasibl=
e
> with on-chain Script state transitions) can be implemented with the simpl=
e
> covenants described in the previous section.
>
> The ideas in this section appeared in literature; the reader is referred
> to the references for a more comprehensive discussion.
>
> We want to be able to build contracts that allow conditions of the type
> "f(x) =3D y"; yet, we do not want layer 1 to be forced to perform any
> expensive computation.
>
> In the following, we assume for simplicity that Alice and Bob are the onl=
y
> participants of the covenant, and they both locked some funds bond_A and
> bond_B (respectively) inside the covenant=E2=80=99s UTXO.
>
> 1. Alice posts the statement =E2=80=9Cf(x) =3D y=E2=80=9D.
> 2. After a challenge period, if no challenge occurs, Alice is free to
> continue and unlock the funds; the statement is true.
> 3. At any time before the challenge period expires, Bob can start a
> challenge: =E2=80=9Cactually, f(x) =3D z=E2=80=9D.
>
> In case of a challenge, Alice and Bob enter a challenge resolution
> protocol, arbitrated by layer 1; the winner takes the other party=E2=80=
=99s bond
> (details and the exact game theory vary based on the type of protocol the
> challenge is part of; choosing the right amount of bonds is crucial for
> protocol design).
>
> The remainder of this section sketches an instantiation of the challenge
> protocol.
>
> ## The bisection protocol for arbitrary computation
>
> In this section, we sketch the challenge protocol for an arbitrary
> computation f : X --> Y.
>
> ### Computation trace
>
> Given the function f, it is possible to decompose the entire computation
> in simple elementary steps, each performing a simple, atomic operation. F=
or
> example, if the domain of x and y is that of binary strings of a fixed
> length, it is possible to create a boolean circuit that takes x and
> produces y; in practice, some form of assembly-like language operating on=
a
> RAM might be more efficient and fitting for bitcoin Script.
>
> In the following, we assume each elementary operation is operating on a
> RAM, encoded in the state via Merkle trees as sketched above. Therefore,
> one can represent all the steps of the computation as triples tri =3D (st=
_i,
> op_i, st_{i + 1}), where st_i is the state (e.g. a canonical Merkle tree =
of
> the RAM) before the i-th operation, st_{i + 1} is the state after, and op=
_i
> is the description of the operation (implementation-specific; it could be
> something like =E2=80=9Cadd a to b and save the result in c).
>
> Finally, a Merkle tree M_T is constructed that has as leaves the values o=
f
> the individual computation steps T =3D {tr_0, tr_1, =E2=80=A6, tr_{N - 1}=
} if the
> computation requires N steps, producing the Merkle root h_T. The height o=
f
> the Merkle tree is log N. Observe that each internal node commits to the
> portion of the computation trace corresponding to its own subtree.
>
> Let=E2=80=99s assume that the Merkle tree commitments for internal nodes =
are
> further augmented with the states st_{start} and st_{end}, respectively t=
he
> state before the operation of in the leftmost leaf of the subtree, and
> after the rightmost leaf of the subtree.
>
> ### Bisection protocol
>
> The challenge protocol begins with Alice posting what she claims is the
> computation trace h_A, while Bob disagrees with the trace h_B !=3D h_A;
> therefore, the challenge starts at the root of M_T, and proceeds in steps
> in order to find a leaf where Alice and Bob disagree (which is guaranteed
> to exist, hence the disagreement). Note that the arbitration mechanism
> knows f, x and y, but not the correct computation trace hash h_T.
>
> (Bisection phase): While the challenge is at a non-leaf node of M_T, Alic=
e
> and Bob take turns to post the two hashes corresponding to the left and
> right child of their claimed computation trace hash; moreover, they post
> the start/end state for each child node. The protocol enforces that Alice=
=E2=80=99s
> transaction is only valid if the posted hashes h_{l; A} and h_{r; A}, and
> the declared start/end state for each child are consistent with the
> commitment in the current node.
>
> (Arbitration phase): If the protocol has reached the i-th leaf node, then
> each party reveals (st_i, op_i, st_{i + 1}); in fact, only the honest par=
ty
> will be able to reveal correct values, therefore the protocol can
> adjudicate the winner.
>
> Remark: there is definitely a lot of room for optimizations; it is left
> for future work to find the optimal variation of the approach; moreover,
> different challenge mechanisms could be more appropriate for different
> functions f.
>
> ### Game theory (or why the chain will not see any of this)
>
> With the right economic incentives, protocol designers can guarantee that
> playing a losing game always loses money compared to cooperating.
> Therefore, the challenge game is never expected to be played on-chain. Th=
e
> size of the bonds need to be appropriate to disincentivize griefing attac=
ks.
>
> ### Implementing the bisection protocol's state transitions
>
> It is not difficult to see that the entire challenge-response protocol
> above can be implemented using the simple state transitions described abo=
ve.
>
> Before a challenge begins, the state of the covenant contains the value o=
f
> x, y and the computation trace computed by Alice. When starting the
> challenge, Bob also adds its claim for the correct computation trace, and
> the covenant enters the bisection phase.
>
> During the bisaction phase, the covenant contains the claimed computation
> trace for that node of the computation protocol, according to each party.
> In turns, each party has to reveal the corresponding computation trace fo=
r
> both the children of the current node; the transaction is only valid if t=
he
> hash of the current node can be computed correctly from the information
> provided by each party about the child nodes. The protocol repeats on one
> of the two child nodes on whose computation trace the two parties disagre=
e
> (which is guaranteed to exist). If a leaf of M_T is reached, the covenant
> enters the final arbitration phase.
>
> During the arbitration phase (say at the i-th leaf node of M_T), any part=
y
> can win the challenge by providing correct values for tr_i =3D (st_i, op_=
i,
> st_{i + 1}). Crucially, only one party is able to provide correct values,
> and Script can verify that indeed the state moves from st_i to st_{i + 1}
> by executing op_i. The challenge is over.
>
> At any time, the covenant allows one player to automatically win the
> challenge after a certain timeout if the other party (who is expected to
> =E2=80=9Cmake his move=E2=80=9D) does not spend the covenant. This guaran=
tees that the
> protocol can always find a resolution.
>
> ### Security model
>
> As for other protocols (like the lightning network), a majority of miners
> can allow a player to win a challenge by censoring the other player=E2=80=
=99s
> transactions. Therefore, the bisection protocol operates under the honest
> miner majority assumption. This is acceptable for many protocols, but it
> should certainly be taken into account during protocol design.
>
>
> # MATT covenants
>
> We argued that the key to arbitrary, fully general smart contracts in the
> UTXO model is to use Merkle trees, at different levels:
>
> 1. succinctly represent arbitrary state with a single hash. Merkleize the
> state!
> 2. succinctly represent the possible state transitions with a single hash=
.
> Merkleize the Script!
> 3. succinctly represent arbitrary computations with a single hash.
> Merkleize the execution!
>
> (1) and (2) alone allow contracts with arbitrary computations; (3) makes
> them scale.
>
> Merkleize All The Things!
>
> In this section we sketch a design of covenant opcodes that are
> taproot-friendly and could easily be added in a soft fork to the existing
> SegWitv1 Script.
>
> ## Embedding covenant data in P2TR outputs
>
> We can take advantage of the double-commitment structure of taproot
> outputs (that is, committing to both a public key and a Merkle tree of
> scripts) to compactly encode both the covenant and the state transition
> rules inside taproot outputs.
>
> The idea is to replace the internal pubkey Q with a key Q=E2=80=99 obtain=
ed by
> tweaking Q with the covenant data (the same process that is used to commi=
t
> to the root of the taptree). More precisely, if d is the data committed t=
o
> the covenant, the covenant-data-augmented internal key Q=E2=80=99 is defi=
ned as:
>
> Q=E2=80=99 =3D Q + int(hashTapCovenantData(Q || h_{data}))G
>
> where h_{data} is the sha256-hash of the covenant data. It is then easy t=
o
> prove that the point is constructed in this way, by repeating the
> calculation.
>
> If there is no useful key path spend, similarly to what is suggested in
> BIP-0341 [5] for the case of scripts with no key path spends, we can use
> the NUMS point:
> H =3D
> lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803a=
c0).
>
> TODO: please double check if the math above is sound.
>
> ## Changes to Script
>
> The following might be some minimal new opcodes to add for taproot
> transactions in order to enable the construction above. This is a very
> preliminary proposal, and not yet complete nor correct.
>
> - OP_SHA256CAT: returns the SHA256 hash of the concatenation of the secon=
d
> and the first (top) element of the stack. (redundant if OP_CAT is enabled=
,
> even just on operands with total length up to 64 bytes)
> - OP_CHECKINPUTCOVENANTVERIFY: let x, d be the two top elements of the
> stack; behave like OP_SUCCESS if any of x and d is not exactly 32 bytes;
> otherwise, check that the x is a valid x-only pubkey, and the internal
> pubkey P is indeed obtained by tweaking lift_x(x) with d.
> - OP_INSPECTNUMINPUTS, OP_INSPECTNUMOUTPUTS, OP_INSPECTINPUTVALUE and
> OP_INSPECTOUTPUTVALUE - opcodes to push number on the stack of
> inputs/outputs and their amounts.
> - OP_CHECKOUTPUTCOVENANTVERIFY: given a number out_i and three 32-byte
> hash elements x, d and taptree on top of the stack, verifies that the
> out_i-th output is a P2TR output with internal key computed as above, and
> tweaked with taptree. This is the actual covenant opcode.
>
> TODO:
>
> - Many contracts need parties to provide additional data; simply passing
> it via the witness faces the problem that it could be malleated. Therefor=
e,
> a way of passing signed data is necessary. One way to address this proble=
m
> could be to add a commitment to the data in the annex, and add an opcode =
to
> verify such commitment. Since the annex is covered by the signature, this
> removes any malleability. Another option is an OP_CHECKSIGFROMSTACK opcod=
e,
> but that would cost an additional signature check.
> - Bitcoin numbers in current Script are not large enough for amounts.
>
> Other observations:
>
> - OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could have
> a mode where x is replaced with a NUMS pubkey, for example if the first
> operand is an empty array of bytes instead of a 32 byte pubkey; this save=
s
> about 31 bytes when no internal pubkey is needed (so about 62 bytes for a
> typical contract transition using both opcodes)
> - Is it worth adding other introspection opcodes, for example
> OP_INSPECTVERSION, OP_INSPECTLOCKTIME? See Liquid's Tapscript Opcodes [6]=
.
> - Is there any malleability issue? Can covenants =E2=80=9Crun=E2=80=9D wi=
thout signatures,
> or is a signature always to be expected when using spending conditions wi=
th
> the covenant encumbrance? That might be useful in contracts where no
> signature is required to proceed with the protocol (for example, any part=
y
> could feed valid data to the bisection protocol above).
> - Adding some additional opcodes to manipulate stack elements might also
> bring performance improvements in applications (but not strictly necessar=
y
> for feasibility).
>
> Remark: the additional introspection opcodes available in Blockstream
> Liquid [6] do indeed seem to allow MATT covenants; in fact, the opcodes
> OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could be
> replaced by more general opcodes like the group {OP_TWEAKVERIFY,
> OP_INSPECTINPUTSCRIPTPUBKEY, OP_PUSHCURRENTINPUTINDEX,
> OP_INSPECTOUTPUTSCRIPTPUBKEY }.
>
> ### Variant: bounded recursivity
>
> In the form described above, the covenant essentially allows fully
> recursive constructions (an arbitrary depth of the covenant execution tre=
e
> is in practice equivalent to full recursion).
>
> If recursivity is not desired, one could modify the covenants in a way
> that only allows a limited depth: a counter could be attached to the
> covenant, with the constraint that the counter must be decreased for
> OP_CHECKOUTPUTCOVENANTVERIFY. That would still allow arbitrary fraud proo=
fs
> as long as the maximum depth is sufficient.
>
> However, that would likely reduce its utility and prevent certain
> applications where recursivity seems to be a requirement.
>
> The full exploration of the design space is left for future research.
>
>
> # Applications
>
> This section explores some of the potential use cases of the techniques
> presented above. The list is not exhaustive.
>
> Given the generality of fraud proofs, some variant of every kind of smart
> contracts or layer two construction should be possible with MATT covenant=
s,
> although the additional requirements (for example the capital lockup and
> the challenge period delays) needs to be accurately considered; further
> research is necessary to assess for what applications the tradeoffs are
> acceptable.
>
> ## State channels
>
> A state channel is a generalization of a payment channel where,
> additionally to the balance at the end of each channel, some additional
> state is stored. The state channel also specifies what are the rules on h=
ow
> to update the channel=E2=80=99s state.
>
> For example, two people might play a chess game, where the state encodes
> the current configuration of the board. The valid state transitions
> correspond to the valid moves; and, once the game is over, the winner tak=
es
> a specified amount of the channel=E2=80=99s money.
>
> With eltoo-style updates, such a game could be played entirely off-chain,
> as long as both parties are cooperating (by signing the opponent=E2=80=99=
s state
> update).
>
> The role of the blockchain is to guarantee that the game can be moved
> forward and eventually terminated in case the other party does not
> cooperate.
>
> In stateful blockchain, this is simply achieved by publishing the latest
> state (Merkleized or not) and then continuing the entire game on-chain.
> This is expensive, especially if the state transitions require some compl=
ex
> computation.
>
> An alternative that avoids moving computations on-chain is the use of a
> challenge-response protocol, as sketched above.
>
> Similarly to the security model of lightning channels, an honest party ca=
n
> always win a challenge under the honest-majority of miners. Therefore, it
> is game-theoretically losing to attempt cheating in a channel.
>
> ## CoinPool
>
> Multiparty state channels are possible as well; therefore, constructions
> like CoinPool [7] should be possible, enabling multiple parties to share =
a
> single UTXO.
>
> ## Zero knowledge proofs in L2 protocols
>
> Protocols based on ZK-proofs require the blockchain to be the verifier;
> the verifier is a function that takes a zero-knowledge proof and returns
> true/false based on its correctness.
>
> Instead of an OP_STARK operator in L1, one could think of compiling the
> OP_STARK as the function f in the protocol above.
>
> Note that covenants with a bounded =E2=80=9Crecursion depth=E2=80=9D are =
sufficient to
> express OP_STARK, which in turns imply the ability to express arbitrary
> functions within contracts using the challenge protocol.
>
> One advantage of this approach is that no new cryptographic assumptions
> are added to bitcoin=E2=80=99s layer 1 even if OP_STARK does require it; =
moreover,
> if a different or better OP_STARK2 is discovered, the innovation can reac=
h
> layer 2 contracts without any change needed in layer 1.
>
> ## Optimistic rollups
>
> John Light recently posted a research report on how Validity Rollups coul=
d
> be added to bitcoin=E2=80=99s layer 1 [8]. While no exact proposal is pus=
hed
> forward, the suggested changes required might include a combination of
> recursive covenants, and specific opcodes for validity proof verification=
.
>
> Fraud proofs are the core for optimistic rollups; exploring the
> possibility of implementing optimistic rollups with MATT covenants seems =
a
> promising direction. Because of the simplicity of the required changes to
> Script, this might answer some of the costs and risks analyzed in the
> report, while providing many of the same benefits. Notably, no novel
> cryptography needs to become part of bitcoin=E2=80=99s layer 1.
>
> Optimistic Rollups would probably require a fully recursive version of th=
e
> covenant (while fraud proofs alone are possible with a limited recursion
> depth).
>
>
> # Acknowledgments
>
> Antoine Poinsot suggested an improvement to the original proposed covenan=
t
> opcodes, which were limited to taproot outputs without a valid key-path
> spend.
>
> The author would also like to thank catenocrypt, Antoine Riard, Ruben
> Somsen and the participants of the BTCAzores unconference for many useful
> discussions and comments on early versions of this proposal.
>
>
> # References
>
> The core idea of the bisection protocol appears to have been independentl=
y
> rediscovered multiple times. In blockchain research, it is at the core of
> fraud proof constructions with similar purposes, although not focusing on
> bitcoin or covenants; see for example:
>
> - Harry Kalodner et al. =E2=80=9CArbitrum: Scalable, private smart contra=
cts.=E2=80=9D =E2=88=92
> 27th USENIX Security Symposium. 2018.
> https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kal=
odner.pdf
> - Jason Teutsch and Christian Reitwiessner. =E2=80=9CA scalable verificat=
ion
> solution for blockchains=E2=80=9D =E2=88=92 TrueBit protocol. 2017.
> https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf
>
> The same basic idea was already published prior to blockchain use cases;
> see for example:
>
> Ran Canetti, Ben Riva, and Guy N. Rothblum. =E2=80=9CPractical delegation=
of
> computation using multiple servers.=E2=80=9D =E2=88=92 Proceedings of the=
18th ACM
> conference on Computer and communications security. 2011. http://diyhpl.u=
s/~bryan/papers2/bitcoin/Practical%20delegation%20of%20computation%20using%=
20multiple%20servers.pdf
>
>
>
> # Footnotes
>
> [1] - https://btcazores.com
> [2] - https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
> [3] -
> https://bitcointalk.org/index.php?topic=3D1427885.msg14601127#msg14601127
> [4] - https://vitalik.ca/general/2019/12/26/mvb.html
> [5] -
> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructi=
ng-and-spending-taproot-outputs
> [6] -
> https://github.com/ElementsProject/elements/blob/master/doc/tapscript_opc=
odes.md
> [7] - https://coinpool.dev/v0.1.pdf
> [8] - https://bitcoinrollups.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--0000000000009e453205ed38dfdf
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi Salvatore,<br><br>Thanks for bringing forward this MATT=
proposal!<br><br>Here my (rough) understanding of the protocol, the partic=
ipants decompose the entire computation into a number N of steps, each assi=
gned a tapleaf, each computation is a triplet (state_start, operation, stat=
e_end), the tapleaves are built into a Merkle tree, the current state of th=
e FSM is also encoded in the Taproot output. The Merkle tree is committed i=
n some Script branch where a timelock is present to guarantee challenge (e.=
g "f(x) =3D ?" OP_CHALLENGE + 100 OP_CSV). A funding transaction =
is broadcast to lock the funds, participants can leverage this funding outp=
ut to play out off-chain the computation steps. To advance the resolution, =
a participant spends the funding output with a witness embedding all the co=
mputation trace encoded as Merkle branch and prove some statement "f(x=
) =3D y". Until the CSV expires, another participant can contest by pr=
esenting another witness with another computation trace. What is unclear to=
me is how the contract's state issued off-chain can alter the pre-comm=
itted state transitions. I think what could gain in clarity is the translat=
ion of the bisection protocol steps in more complete new opcodes.<br><br>An=
other high-level remark, even if we assume any arbitrary computation can be=
encoded in a Merkle Tree, as the computation grows in complexity, the corr=
esponding trace also increases in (witness) space. There might be some econ=
omic bounds on the generalized smart contracts you can engage in, as the wo=
rst-case scenario might be beyond your fee-bumping reserves. Less flexible,=
but more templated opcodes for the same use-cases might make it more affor=
dable. At the same time, the ability to encode any cryptosystem as the func=
tion f sounds really interesting.<br><br>Best,<br>Antoine<br></div><br><div=
class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0mar. 8=
nov. 2022 =C3=A0=C2=A005:13, Salvatore Ingala via bitcoin-dev <<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>> a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex"><div dir=3D"ltr">Hi list,<br><br>I have been worki=
ng on some notes to describe an approach that uses covenants in order to en=
able general smart contracts in bitcoin. You can find them here:<div><br></=
div><div>=C2=A0 =C2=A0 <a href=3D"https://merkle.fun" target=3D"_blank">htt=
ps://merkle.fun</a><div><br></div><div>The approach has a number of desirab=
le features:<br><br>- small impact to layer 1;<br>- not application-specifi=
c, very general;<br>- it fits well into P2TR;<br>- it does not require new =
cryptographic assumptions, nor any construction that has not withstood the =
test of time.<br><br>This content was presented at the BTCAzores unconferen=
ce, where it received the name of MATT =E2=88=92 short for Merkleize All Th=
e Things.<br>In fact, no other cryptographic primitive is required, other t=
han Merkle trees.<br><br>I believe this construction gets close to answerin=
g the question of how small a change on bitcoin's layer 1 would suffice=
to enable arbitrary smart contracts.<br><br>It is not yet at the stage whe=
re a formal proposal can be made, therefore the proposed specs are only for=
illustrative=C2=A0purposes.<br><br></div><div>The same content is reformat=
ted below for the mailing list.<br><br>Looking forward to hearing about you=
r comments and improvements.<br><div>Salvatore Ingala<br><br><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<br><br><br># General smart contr=
acts in bitcoin via covenants<br><br>Covenants are UTXOs that are encumbere=
d with restrictions on the outputs of the transaction spending the UTXO. Mo=
re formally, we can define a covenant any UTXO such that at least one of it=
s spending conditions is valid only if one or more of the outputs=E2=80=99 =
scriptPubKey satisfies certain restrictions.<br><br>Generally, covenant pro=
posals also add some form of introspection (that is, the ability for Script=
to access parts of the inputs/outputs, or the blockchain history).<br><br>=
In this note, we want to explore the possibilities unleashed by the additio=
n of a covenant with the following properties:<br><br>- introspection limit=
ed to a single hash attached to the UTXO (the =E2=80=9Ccovenant data=E2=80=
=9D), and input/output amounts;<br>- pre-commitment to every possible futur=
e script (but not their data);<br>- few simple opcodes operating with the c=
ovenant data.<br><br>We argue that such a simple covenant construction is e=
nough to extend the power of bitcoin=E2=80=99s layer 1 to become a universa=
l settlement layer for arbitrary computation.<br><br>Moreover, the covenant=
can elegantly fit within P2TR transactions, without any substantial increa=
se for the workload of bitcoin nodes.<br><br>A preliminary version of these=
notes was presented and discussed at the BTCAzores Unconference [1], on 23=
rd September 2022.<br><br><br># Preliminaries<br><br>We can think of a smar=
t contract as a =E2=80=9Cprogram=E2=80=9D that updates a certain state acco=
rding to predetermined rules (which typically include access control by aut=
horizing only certain public keys to perform certain actions), and that can=
possibly lock/unlock some coins of the underlying blockchain according to =
the same rules.<br><br>The exact definition will be highly dependent on the=
properties of the underlying blockchain.<br><br>In bitcoin, the only state=
upon which all the nodes reach consensus is the UTXO set; other blockchain=
s might have other data structures as part of the consensus, like a key-val=
ue store that can be updated as a side effect of transaction execution.<br>=
<br>In this section we explore the following concepts in order to set the f=
ramework for a definition of smart contracts that fits the structure of bit=
coin:<br><br>- the contract=E2=80=99s state: the =E2=80=9Cmemory=E2=80=9D t=
he smart contract operates on;<br>- state transitions: the rules to update =
the contract=E2=80=99s state;<br>- covenants: the technical means that can =
allow contracts to function in the context of a bitcoin UTXO.<br><br>In the=
following, an on-chain smart contract is always represented as a single UT=
XO that implicitly embeds the contract=E2=80=99s state and possibly control=
s some coins that are =E2=80=9Clocked=E2=80=9D in it. More generally, one c=
ould think of smart contracts that are represented in a set of multiple UTX=
Os; we leave the exploration of generalizations of the framework to future =
research.<br><br>## State<br><br>Any interesting =E2=80=9Cstate=E2=80=9D of=
a smart contract can ultimately be encoded as a list, where each element i=
s either a bit, a fixed-size integers, or an arbitrary byte string.<br><br>=
Whichever the choice, it does not really affect what kinds of computations =
are expressible, as long as one is able to perform some basic computations =
on those elements.<br><br>In the following, we will assume without loss of =
generality that computations happen on a state which is a list of fixed len=
gth S =3D [s_1, s_2, =E2=80=A6, s_n], where each s_i is a byte string.<br><=
br>### Merkleized state<br><br>By constructing a Merkle tree that has the (=
hashes of) the elements of S in the leaves, we can produce a short commitme=
nt h_S to the entire list S with the following properties (that hold for a =
verifier that only knows h_S):<br><br>- a (log n)-sized proof can prove the=
value of an element s_i;<br>- a (log n + |x|)-sized proof can prove the ne=
w commitment h_S=E2=80=99, where S=E2=80=99 is a new list obtained by repla=
cing the value of a certain leaf with x.<br><br>This allows to compactly co=
mmit to a RAM, and to prove correctness of RAM updates.<br><br>In other wor=
ds, a stateful smart contract can represent an arbitrary state in just a si=
ngle hash, for example a 32-byte SHA256 output.<br><br>### State transition=
s and UTXOs<br><br>We can conveniently represent a smart contract as a fini=
te state machine (FSM), where exactly one node can be active at a given tim=
e. Each node has an associated state as defined above, and a set of transit=
ion rules that define:<br><br>- who can use the rule;<br>- what is the next=
active node in the FSM;<br>- what is the state of the next active node.<br=
><br>It is then easy to understand how covenants can conveniently represent=
and enforce the smart contracts in this framework:<br><br>- The smart cont=
ract is instantiated by creating a UTXO encumbered with a covenant; the sma=
rt contract is in the initial node of the FSM.<br>- The UTXO=E2=80=99s scri=
ptPubKey specifies the current state and the valid transitions.<br>- The UT=
XO(s) produced after a valid transition might or might not be further encum=
bered, according to the rules.<br><br>Therefore, what is necessary in order=
to enable this framework in bitcoin Script is a covenant that allows the e=
nforcement of such state transitions, by only allowing outputs that commit =
to a valid next node (and corresponding state) in the FSM.<br><br>It is not=
difficult to show that arbitrary computation is possible over the committe=
d state, as long as relatively simple arithmetic or logical operations are =
available over the state.<br><br>Remark: using an acyclic FSM does not redu=
ce the expressivity of the smart contracts, as any terminating computation =
on bounded-size inputs which requires cycles can be unrolled into an acycli=
c one.<br><br>### Merkleized state transitions<br><br>Similarly to how usin=
g Merkle trees allows to succinctly represent arbitrary data with a short, =
32-byte long summary, the same trick allows to succinctly represent arbitra=
ry state transitions (the smart contract=E2=80=99s code) with a single 32-b=
yte hash. Each of the possible state transitions is encoded as a Script whi=
ch is put in a leaf of a Merkle tree; the Merkle root of this tree is a com=
mitment to all the possible state transitions. This is exactly what the tap=
tree achieves in Taproot (see BIP-0341 [2]).<br><br>Later sections in this =
document will suggest a possible way of how both the contract=E2=80=99s sta=
te and valid transition rules could be represented in UTXOs.<br><br>## On-c=
hain computation?!<br><br>Should the chain actually do computation?<br><br>=
If naively designed, the execution of a contract might require a large numb=
er of transactions, which is not feasible.<br><br>While the covenant approa=
ch does indeed enable a chain of transactions to perform arbitrary computat=
ion, simple economic considerations will push protocol designers to perform=
any non-trivial computation off-chain, and instead use the blockchain cons=
ensus only to verify the computation; or, if possible, skip the verificatio=
n altogether.<br><br>The fundamental fact that a blockchain=E2=80=99s layer=
1 never actually needs to run complex programs in order to enable arbitrar=
y complex smart contracting was observed in the past, for example in a 2016=
post by Greg Maxwell [3].<br><br>Vitalik Buterin popularized the concept o=
f "functionality escape velocity" [4] to signify the minimum amou=
nt of functionality required on layer 1 in order to enable anything else to=
be built on top (that is, on layer 2 and beyond).<br><br>In the following =
section, we will argue that a simple covenant construction suffices to achi=
eve the functionality escape velocity in the UTXO model.<br><br><br># Commi=
tments to computation and fraud challenges<br><br>In this section, we explo=
re how a smart contract that requires any non-trivial computation f : X --&=
gt;=C2=A0Y (that is too expensive or not feasible with on-chain Script stat=
e transitions) can be implemented with the simple covenants described in th=
e previous section.<br><br>The ideas in this section appeared in literature=
; the reader is referred to the references for a more comprehensive discuss=
ion.<br><br>We want to be able to build contracts that allow conditions of =
the type "f(x) =3D y"; yet, we do not want layer 1 to be forced t=
o perform any expensive computation.<br><br>In the following, we assume for=
simplicity that Alice and Bob are the only participants of the covenant, a=
nd they both locked some funds bond_A and bond_B (respectively) inside the =
covenant=E2=80=99s UTXO.<br><br>1. Alice posts the statement =E2=80=9Cf(x) =
=3D y=E2=80=9D.<br>2. After a challenge period, if no challenge occurs, Ali=
ce is free to continue and unlock the funds; the statement is true.<br>3. A=
t any time before the challenge period expires, Bob can start a challenge: =
=E2=80=9Cactually, f(x) =3D z=E2=80=9D.<br><br>In case of a challenge, Alic=
e and Bob enter a challenge resolution protocol, arbitrated by layer 1; the=
winner takes the other party=E2=80=99s bond (details and the exact game th=
eory vary based on the type of protocol the challenge is part of; choosing =
the right amount of bonds is crucial for protocol design).<br><br>The remai=
nder of this section sketches an instantiation of the challenge protocol.<b=
r><br>## The bisection protocol for arbitrary computation<br><br>In this se=
ction, we sketch the challenge protocol for an arbitrary computation f : X =
--> Y.<br><br>### Computation trace<br><br>Given the function f, it is p=
ossible to decompose the entire computation in simple elementary steps, eac=
h performing=C2=A0a simple, atomic operation. For example, if the domain of=
x and y is that of binary strings of a fixed length, it is possible to cre=
ate a boolean circuit that takes x and produces y; in practice, some form o=
f assembly-like language operating on a RAM might be more efficient and fit=
ting for bitcoin Script.<br><br>In the following, we assume each elementary=
operation is operating on a RAM, encoded in the state via Merkle trees as =
sketched above. Therefore, one can represent all the steps of the computati=
on as triples tri =3D (st_i, op_i, st_{i + 1}), where st_i is the state (e.=
g. a canonical Merkle tree of the RAM) before the i-th operation, st_{i + 1=
} is the state after, and op_i is the description of the operation (impleme=
ntation-specific; it could be something like =E2=80=9Cadd a to b and save t=
he result in c).<br><br>Finally, a Merkle tree M_T is constructed that has =
as leaves the values of the individual computation steps T =3D {tr_0, tr_1,=
=E2=80=A6, tr_{N - 1}} if the computation requires N steps, producing the =
Merkle root h_T. The height of the Merkle tree is log N. Observe that each =
internal node commits to the portion of the computation trace corresponding=
to its own subtree.<br><br>Let=E2=80=99s assume that the Merkle tree commi=
tments for internal nodes are further augmented with the states st_{start} =
and st_{end}, respectively the state before the operation of in the leftmos=
t leaf of the subtree, and after the rightmost leaf of the subtree.<br><br>=
### Bisection protocol<br><br>The challenge protocol begins with Alice post=
ing what she claims is the computation trace h_A, while Bob disagrees with =
the trace h_B !=3D h_A; therefore, the challenge starts at the root of M_T,=
and proceeds in steps in order to find a leaf where Alice and Bob disagree=
(which is guaranteed to exist, hence the disagreement). Note that the arbi=
tration mechanism knows f, x and y, but not the correct computation trace h=
ash h_T.<br><br>(Bisection phase): While the challenge is at a non-leaf nod=
e of M_T, Alice and Bob take turns to post the two hashes corresponding to =
the left and right child of their claimed computation trace hash; moreover,=
they post the start/end state for each child node. The protocol enforces t=
hat Alice=E2=80=99s transaction is only valid if the posted hashes h_{l; A}=
and h_{r; A}, and the declared start/end state for each child are consiste=
nt with the commitment in the current node.<br><br>(Arbitration phase): If =
the protocol has reached the i-th leaf node, then each party reveals (st_i,=
op_i, st_{i + 1}); in fact, only the honest party will be able to reveal c=
orrect values, therefore the protocol can adjudicate the winner.<br><br>Rem=
ark: there is definitely a lot of room for optimizations; it is left for fu=
ture work to find the optimal variation of the approach; moreover, differen=
t challenge mechanisms could be more appropriate for different functions f.=
<br><br>### Game theory (or why the chain will not see any of this)<br><br>=
With the right economic incentives, protocol designers can guarantee that p=
laying a losing game always loses money compared to cooperating. Therefore,=
the challenge game is never expected to be played on-chain. The size of th=
e bonds need to be appropriate to disincentivize griefing attacks.<br><br>#=
## Implementing the bisection protocol's state transitions<br><br>It is=
not difficult to see that the entire challenge-response protocol above can=
be implemented using the simple state transitions described above.<br><br>=
Before a challenge begins, the state of the covenant contains the value of =
x, y and the computation trace computed by Alice. When starting the challen=
ge, Bob also adds its claim for the correct computation trace, and the cove=
nant enters the bisection phase.<br><br>During the bisaction phase, the cov=
enant contains the claimed computation trace for that node of the computati=
on protocol, according to each party. In turns, each party has to reveal th=
e corresponding computation trace for both the children of the current node=
; the transaction is only valid if the hash of the current node can be comp=
uted correctly from the information provided by each party about the child =
nodes. The protocol repeats on one of the two child nodes on whose computat=
ion trace the two parties disagree (which is guaranteed to exist). If a lea=
f of M_T is reached, the covenant enters the final arbitration phase.<br><b=
r>During the arbitration phase (say at the i-th leaf node of M_T), any part=
y can win the challenge by providing correct values for tr_i =3D (st_i, op_=
i, st_{i + 1}). Crucially, only one party is able to provide correct values=
, and Script can verify that indeed the state moves from st_i to st_{i + 1}=
by executing op_i. The challenge is over.<br><br>At any time, the covenant=
allows one player to automatically win the challenge after a certain timeo=
ut if the other party (who is expected to =E2=80=9Cmake his move=E2=80=9D) =
does not spend the covenant. This guarantees that the protocol can always f=
ind a resolution.<br><br>### Security model<br><br>As for other protocols (=
like the lightning network), a majority of miners can allow a player to win=
a challenge by censoring the other player=E2=80=99s transactions. Therefor=
e, the bisection protocol operates under the honest miner majority assumpti=
on. This is acceptable for many protocols, but it should certainly be taken=
into account during protocol design.<br><br><br># MATT covenants<br><br>We=
argued that the key to arbitrary, fully general smart contracts in the UTX=
O model is to use Merkle trees, at different levels:<br><br>1. succinctly r=
epresent arbitrary state with a single hash. Merkleize the state!<br>2. suc=
cinctly represent the possible state transitions with a single hash. Merkle=
ize the Script!<br>3. succinctly represent arbitrary computations with a si=
ngle hash. Merkleize the execution!<br><br>(1) and (2) alone allow contract=
s with arbitrary computations; (3) makes them scale.<br><br>=C2=A0 =C2=A0Me=
rkleize All The Things!<br><br>In this section we sketch a design of covena=
nt opcodes that are taproot-friendly and could easily be added in a soft fo=
rk to the existing SegWitv1 Script.<br><br>## Embedding covenant data in P2=
TR outputs<br><br>We can take advantage of the double-commitment structure =
of taproot outputs (that is, committing to both a public key and a Merkle t=
ree of scripts) to compactly encode both the covenant and the state transit=
ion rules inside taproot outputs.<br><br>The idea is to replace the interna=
l pubkey Q with a key Q=E2=80=99 obtained by tweaking Q with the covenant d=
ata (the same process that is used to commit to the root of the taptree). M=
ore precisely, if d is the data committed to the covenant, the covenant-dat=
a-augmented internal key Q=E2=80=99 is defined as:<br><br>=C2=A0 =C2=A0 Q=
=E2=80=99 =3D Q + int(hashTapCovenantData(Q || h_{data}))G<br><br>where h_{=
data}=C2=A0is the sha256-hash of the covenant data. It is then easy to prov=
e that the point is constructed in this way, by repeating the calculation.<=
br><br>If there is no useful key path spend, similarly to what is suggested=
in BIP-0341 [5] for the case of scripts with no key path spends, we can us=
e the NUMS point:<br>=C2=A0 =C2=A0 H =3D lift_x(0x0250929b74c1a04954b78b4b6=
035e97a5e078a5a0f28ec96d547bfee9ace803ac0).<br><br>TODO: please double chec=
k if the math above is sound.<br><br>## Changes to Script<br><br>The follow=
ing might be some minimal new opcodes to add for taproot transactions in or=
der to enable the construction above. This is a very preliminary proposal, =
and not yet complete nor correct.<br><br>- OP_SHA256CAT: returns the SHA256=
hash of the concatenation of the second and the first (top) element of the=
stack. (redundant if OP_CAT is enabled, even just on operands with total l=
ength up to 64 bytes)<br>- OP_CHECKINPUTCOVENANTVERIFY: let x, d be the two=
top elements of the stack; behave like OP_SUCCESS if any of x and d is not=
exactly 32 bytes; otherwise, check that the x is a valid x-only pubkey, an=
d the internal pubkey P is indeed obtained by tweaking lift_x(x) with d.<br=
>- OP_INSPECTNUMINPUTS, OP_INSPECTNUMOUTPUTS, OP_INSPECTINPUTVALUE and OP_I=
NSPECTOUTPUTVALUE - opcodes to push number on the stack of inputs/outputs a=
nd their amounts.<br>- OP_CHECKOUTPUTCOVENANTVERIFY: given a number out_i a=
nd three 32-byte hash elements x, d and taptree on top of the stack, verifi=
es that the out_i-th output is a P2TR output with internal key computed as =
above, and tweaked with taptree. This is the actual covenant opcode.<br><br=
>TODO:<br><br>- Many contracts need parties to provide additional data; sim=
ply passing it via the witness faces the problem that it could be malleated=
. Therefore, a way of passing signed data is necessary. One way to address =
this problem could be to add a commitment to the data in the annex, and add=
an opcode to verify such commitment. Since the annex is covered by the sig=
nature, this removes any malleability. Another option is an OP_CHECKSIGFROM=
STACK opcode, but that would cost an additional signature check.<br>- Bitco=
in numbers in current Script are not large enough for amounts.<br><br>Other=
observations:<br><br>- OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVEN=
ANTVERIFY could have a mode where x is replaced with a NUMS pubkey, for exa=
mple if the first operand is an empty array of bytes instead of a 32 byte p=
ubkey; this saves about 31 bytes when no internal pubkey is needed (so abou=
t 62 bytes for a typical contract transition using both opcodes)<br>- Is it=
worth adding other introspection opcodes, for example OP_INSPECTVERSION, O=
P_INSPECTLOCKTIME? See Liquid's Tapscript Opcodes [6].<br>- Is there an=
y malleability issue? Can covenants =E2=80=9Crun=E2=80=9D without signature=
s, or is a signature always to be expected when using spending conditions w=
ith the covenant encumbrance? That might be useful in contracts where no si=
gnature is required to proceed with the protocol (for example, any party co=
uld feed valid data to the bisection protocol above).<br>- Adding some addi=
tional opcodes to manipulate stack elements might also bring performance im=
provements in applications (but not strictly necessary for feasibility).<br=
><br>Remark: the additional introspection opcodes available in Blockstream =
Liquid [6] do indeed seem to allow MATT covenants; in fact, the opcodes OP_=
CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could be replaced=
by more general opcodes like the group {OP_TWEAKVERIFY, OP_INSPECTINPUTSCR=
IPTPUBKEY, OP_PUSHCURRENTINPUTINDEX, OP_INSPECTOUTPUTSCRIPTPUBKEY }.<br><br=
>### Variant: bounded recursivity<br><br>In the form described above, the c=
ovenant essentially allows fully recursive constructions (an arbitrary dept=
h of the covenant execution tree is in practice equivalent to full recursio=
n).<br><br>If recursivity is not desired, one could modify the covenants in=
a way that only allows a limited depth: a counter could be attached to the=
covenant, with the constraint that the counter must be decreased for OP_CH=
ECKOUTPUTCOVENANTVERIFY. That would still allow arbitrary fraud proofs as l=
ong as the maximum depth is sufficient.<br><br>However, that would likely r=
educe its utility and prevent certain applications where recursivity seems =
to be a requirement.<br><br>The full exploration of the design space is lef=
t for future research.<br><br><br># Applications<br><br>This section explor=
es some of the potential use cases of the techniques presented above. The l=
ist is not exhaustive.<br><br>Given the generality of fraud proofs, some va=
riant of every kind of smart contracts or layer two construction should be =
possible with MATT covenants, although the additional requirements (for exa=
mple the capital lockup and the challenge period delays) needs to be accura=
tely considered; further research is necessary to assess for what applicati=
ons the tradeoffs are acceptable.<br><br>## State channels<br><br>A state c=
hannel is a generalization of a payment channel where, additionally to the =
balance at the end of each channel, some additional state is stored. The st=
ate channel also specifies what are the rules on how to update the channel=
=E2=80=99s state.<br><br>For example, two people might play a chess game, w=
here the state encodes the current configuration of the board. The valid st=
ate transitions correspond to the valid moves; and, once the game is over, =
the winner takes a specified amount of the channel=E2=80=99s money.<br><br>=
With eltoo-style updates, such a game could be played entirely off-chain, a=
s long as both parties are cooperating (by signing the opponent=E2=80=99s s=
tate update).<br><br>The role of the blockchain is to guarantee that the ga=
me can be moved forward and eventually terminated in case the other party d=
oes not cooperate.<br><br>In stateful blockchain, this is simply achieved b=
y publishing the latest state (Merkleized or not) and then continuing the e=
ntire game on-chain. This is expensive, especially if the state transitions=
require some complex computation.<br><br>An alternative that avoids moving=
computations on-chain is the use of a challenge-response protocol, as sket=
ched above.<br><br>Similarly to the security model of lightning channels, a=
n honest party can always win a challenge under the honest-majority of mine=
rs. Therefore, it is game-theoretically losing to attempt cheating in a cha=
nnel.<br><br>## CoinPool<br><br>Multiparty state channels are possible as w=
ell; therefore, constructions like CoinPool [7] should be possible, enablin=
g multiple parties to share a single UTXO.<br><br>## Zero knowledge proofs =
in L2 protocols<br><br>Protocols based on ZK-proofs require the blockchain =
to be the verifier; the verifier is a function that takes a zero-knowledge =
proof and returns true/false based on its correctness.<br><br>Instead of an=
OP_STARK operator in L1, one could think of compiling the OP_STARK as the =
function f in the protocol above.<br><br>Note that covenants with a bounded=
=E2=80=9Crecursion depth=E2=80=9D are sufficient to express OP_STARK, whic=
h in turns imply the ability to express arbitrary functions within contract=
s using the challenge protocol.<br><br>One advantage of this approach is th=
at no new cryptographic assumptions are added to bitcoin=E2=80=99s layer 1 =
even if OP_STARK does require it; moreover, if a different or better OP_STA=
RK2 is discovered, the innovation can reach layer 2 contracts without any c=
hange needed in layer 1.<br><br>## Optimistic rollups<br><br>John Light rec=
ently posted a research report on how Validity Rollups could be added to bi=
tcoin=E2=80=99s layer 1 [8]. While no exact proposal is pushed forward, the=
suggested changes required might include a combination of recursive covena=
nts, and specific opcodes for validity proof verification.<br><br>Fraud pro=
ofs are the core for optimistic rollups; exploring the possibility of imple=
menting optimistic rollups with MATT covenants seems a promising direction.=
Because of the simplicity of the required changes to Script, this might an=
swer some of the costs and risks analyzed in the report, while providing ma=
ny of the same benefits. Notably, no novel cryptography needs to become par=
t of bitcoin=E2=80=99s layer 1.<br><br>Optimistic Rollups would probably re=
quire a fully recursive version of the covenant (while fraud proofs alone a=
re possible with a limited recursion depth).<br><br><br># Acknowledgments<b=
r><br>Antoine Poinsot suggested an improvement to the original proposed cov=
enant opcodes, which were limited to taproot outputs without a valid key-pa=
th spend.<br><br>The author would also like to thank catenocrypt, Antoine R=
iard, Ruben Somsen and the participants of the BTCAzores unconference for m=
any useful discussions and comments on early versions of this proposal.<br>=
<br><br># References<br><br>The core idea of the bisection protocol appears=
to have been independently rediscovered multiple times. In blockchain rese=
arch, it is at the core of fraud proof constructions with similar purposes,=
although not focusing on bitcoin or covenants; see for example:<br><br>- H=
arry Kalodner et al. =E2=80=9CArbitrum: Scalable, private smart contracts.=
=E2=80=9D =E2=88=92 27th USENIX Security Symposium. 2018. <a href=3D"https:=
//www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pd=
f" target=3D"_blank">https://www.usenix.org/system/files/conference/usenixs=
ecurity18/sec18-kalodner.pdf</a><br>- Jason Teutsch and Christian Reitwiess=
ner. =E2=80=9CA scalable verification solution for blockchains=E2=80=9D =E2=
=88=92 TrueBit protocol. 2017. <a href=3D"https://people.cs.uchicago.edu/~t=
eutsch/papers/truebit.pdf" target=3D"_blank">https://people.cs.uchicago.edu=
/~teutsch/papers/truebit.pdf</a><br><br>The same basic idea was already pub=
lished prior to blockchain use cases; see for example:<br><br>Ran Canetti, =
Ben Riva, and Guy N. Rothblum. =E2=80=9CPractical delegation of computation=
using multiple servers.=E2=80=9D =E2=88=92 Proceedings of the 18th ACM con=
ference on Computer and communications security. 2011. <a href=3D"http://di=
yhpl.us/~bryan/papers2/bitcoin/Practical%20delegation%20of%20computation%20=
using%20multiple%20servers.pdf" target=3D"_blank">http://diyhpl.us/~bryan/p=
apers2/bitcoin/Practical%20delegation%20of%20computation%20using%20multiple=
%20servers.pdf </a><br><br><br># Footnotes<br><br>[1] - <a href=3D"https://=
btcazores.com" target=3D"_blank">https://btcazores.com</a><br>[2] - <a href=
=3D"https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki" target=
=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki<=
/a><br>[3] - <a href=3D"https://bitcointalk.org/index.php?topic=3D1427885.m=
sg14601127#msg14601127" target=3D"_blank">https://bitcointalk.org/index.php=
?topic=3D1427885.msg14601127#msg14601127</a><br>[4] - <a href=3D"https://vi=
talik.ca/general/2019/12/26/mvb.html" target=3D"_blank">https://vitalik.ca/=
general/2019/12/26/mvb.html</a><br>[5] - <a href=3D"https://github.com/bitc=
oin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-o=
utputs" target=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0=
341.mediawiki#constructing-and-spending-taproot-outputs</a><br>[6] - <a hre=
f=3D"https://github.com/ElementsProject/elements/blob/master/doc/tapscript_=
opcodes.md" target=3D"_blank">https://github.com/ElementsProject/elements/b=
lob/master/doc/tapscript_opcodes.md</a><br>[7] - <a href=3D"https://coinpoo=
l.dev/v0.1.pdf" target=3D"_blank">https://coinpool.dev/v0.1.pdf</a><br>[8] =
- <a href=3D"https://bitcoinrollups.org" target=3D"_blank">https://bitcoinr=
ollups.org</a><br></div></div></div></div>
_______________________________________________<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>
--0000000000009e453205ed38dfdf--
|