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
|
Delivery-date: Sun, 24 Nov 2024 20:24:34 -0800
Received: from mail-yb1-f188.google.com ([209.85.219.188])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBC3PT7FYWAMRB5XXR65AMGQEVIDQIOA@googlegroups.com>)
id 1tFQeG-00021D-5z
for bitcoindev@gnusha.org; Sun, 24 Nov 2024 20:24:34 -0800
Received: by mail-yb1-f188.google.com with SMTP id 3f1490d57ef6-e3886f4cee2sf6107690276.0
for <bitcoindev@gnusha.org>; Sun, 24 Nov 2024 20:24:31 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1732508665; x=1733113465; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=WT9BS99x1czpcHiBhxI1AqDtCML/Poz+AePyIjxBJKU=;
b=mBjTY8a5mtISPsqkXaAFjBLGKvs1z9qR8djZnel/rsf5QMg96DfRAH+vkx+yco49na
r/hB1ffmxD1M8q6aOWqA6W2xzwOZc4t8HfKw8JJ+xiHMutJQAxZTGnnu8n/iqss65Yb9
6XcsyfCEp+7DvecSiJURF79Bwv92l8g31vaHMrUDoKHTx59MHVn5XZZ9roVaEe1k61lr
sLWhaayIi382ILLu+AeiN/2pXG1RHYcNnA32cKLM0zbj8JO4QQlKBmNa46rBW1S0vSRC
ks3/Gvsb9aSK/p/y6vk11gEJfeubLRVtgttp1uqoo5/DreiTrAS6Nja5LP/6lOBGZMxz
jhwA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1732508665; x=1733113465; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:from:to:cc
:subject:date:message-id:reply-to;
bh=WT9BS99x1czpcHiBhxI1AqDtCML/Poz+AePyIjxBJKU=;
b=b+ABPp0S1ZWMOkYt2S34JbvaXQuPsR9TsxWuR6btR+/uhOnt2HhGHvx1Jbv8IekTWT
SWBrUxh59I/6GSlq6Z3INlItQsspZ95T67G2qBPJzt9BBJN54firy8rg1M4WwFRc2cR+
1DQ1fpSG6G+c5bupRtdIclXcthgQ7ciVSRmUP3PhhpWZJVb6+c9G1i4whXrwvtKcTcKP
jDV/dfhbcdlKQNiPBlbMSCn83F4mu56ADHv+BB6OkyGeDA2fBofa8z0MCOr7/W9PpS9M
MRrdanUxpRIP1L4SNecJzj3+gmDj26HRdzOftaqQ8fUKJyhe7f7c7M5dBfB0B6YVoEPU
lISg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1732508665; x=1733113465;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=WT9BS99x1czpcHiBhxI1AqDtCML/Poz+AePyIjxBJKU=;
b=gDuLfsWIwy5/ka0VD8HKvyoI6+EutI7l39NObT4Wlk0UzMw/NNio7ifaBqa9xjOJo1
aQLI/LfY5pgxR/o23cLFnuIsaT7khCXmXAXrGYWX0L/KAJlSXMU8JHe6tWYR382nXxfM
5U0PVRvPd7QKFu3XsBBLOVUYb1zo61jOrNGofFOGxdzHUzvjfvjI5xL+pjTyw9tGxDHb
QQ0Di2ItHUrAJ6+rJukBcsTO4NzAlooa1x286Rm6yc2S1oyWefrGJXdhUFfomE3XJUiE
9vI7OjRPfr8gtV39YTu1IybRC3YrrdGUQhtFQcDsqzYcC5XPUHbssy3QU+Hd8xqebZch
IZjw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCXv07R36W4UqkTjuau05hAWNbRFkQ6GVuaAuZlY4rHq9PxQH5LzmbjkwzExC1OB/IuadNWoiWmp1wBT@gnusha.org
X-Gm-Message-State: AOJu0Ywf0hhwLTyAR4S9yOmeNzeRXRt30SLBNg6mDWpOWUkZVRTh3efj
bXRdcxVdVsTYlIjISXqoycgXrmRPXXs30FGK+r95CdrWVtIbYXtU
X-Google-Smtp-Source: AGHT+IGkBZQRl5v3fciEmprHJ63EqA6BURmTjNUXeeDjlL2dM3ayLnXGBadwHM6sLMXKBWz08iUD2Q==
X-Received: by 2002:a05:6902:72c:b0:e38:8993:b4dc with SMTP id 3f1490d57ef6-e38f6fe5864mr9662716276.1.1732508665092;
Sun, 24 Nov 2024 20:24:25 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:907:b0:e38:3521:5e21 with SMTP id
3f1490d57ef6-e38e1693a9els9175276.0.-pod-prod-09-us; Sun, 24 Nov 2024
20:24:22 -0800 (PST)
X-Received: by 2002:a05:690c:7091:b0:6e7:f98e:12dc with SMTP id 00721157ae682-6eee08a970bmr97871297b3.9.1732508662567;
Sun, 24 Nov 2024 20:24:22 -0800 (PST)
Received: by 2002:a05:690c:6182:b0:6ea:3075:201e with SMTP id 00721157ae682-6eee0446e13ms7b3;
Sun, 24 Nov 2024 19:42:28 -0800 (PST)
X-Received: by 2002:a05:690c:498e:b0:6ee:988b:dbc with SMTP id 00721157ae682-6eee0a26d96mr107226037b3.31.1732506147830;
Sun, 24 Nov 2024 19:42:27 -0800 (PST)
Date: Sun, 24 Nov 2024 19:42:27 -0800 (PST)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <5b69515c-b5b1-4333-88e2-7653face1a3bn@googlegroups.com>
In-Reply-To: <CAEM=y+V2YqRZhvNrgoxMbmaz=i94=hkAj=5HaTErKsOzYq6R4w@mail.gmail.com>
References: <CAEM=y+W2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ@mail.gmail.com>
<fc031fe3-444c-446d-a5c1-f2d7a430b478n@googlegroups.com>
<CAEM=y+V2YqRZhvNrgoxMbmaz=i94=hkAj=5HaTErKsOzYq6R4w@mail.gmail.com>
Subject: Re: [bitcoindev] Re: ColliderScript: Covenants in Bitcoin via 160-bit
hash collisions
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary="----=_Part_27734_151653098.1732506147577"
X-Original-Sender: antoine.riard@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)
------=_Part_27734_151653098.1732506147577
Content-Type: multipart/alternative;
boundary="----=_Part_27735_1001706531.1732506147577"
------=_Part_27735_1001706531.1732506147577
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Ethan,
Thanks for the additional thoughts.
> You have the basic idea correct but I think you might be missing one
> piece of this (or perhaps you just simplified some details).
Reading again the paper, my example and your new example, I don't understan=
d
yet all the details for sure, though on the fundamental trick, I believe
we're saying more or less the same thing. If I'm understanding correctly,
the trick is about proving that y(y1 =3D y2) both in Big Script and Small=
=20
Script.
> For an honest party spending a covenant the s1 and s2 they generate
> are always equal. This means that y1 <- h_big_script(s1) and y2 <-
> h_small_script(s2) will generate the same y (y1 =3D y2). As you point
> out we can't compare y1 to y2 because they are encoded differently.
Where s1 and s2 is the byte-for-byte equivalent spent transactions.
For the security definition you're giving of the equivalence check,
I don't think it matters that a party in a multi-party colliderscript-based
vault protocol being honest. Either, the equivalence check is sound,
and it's immutable once the UTXO's containing the lock script is=20
confirmed in the chain, the covenant creator cannot himself generate
not equal s1 and s2 _and_ successfully spend the coin.
The lemma in terms of security model, I think for multi-party protocol,
is that all the participant should verify the soundness of the y(y1 =3D y2)=
,
before to engage in the protocol (e.g staking more coins under the
locking script or doing a swap).
> we know just DUP w and t for evaluation in
> small script and big script. Since dGen is deterministic it must be
> the case that dGen_big_script(w, t) always equals dGen_small_script(w,
> t). The trick is finding a w, t, s where dGen(w, t) =3D h(s) where s =3D
> s1 =3D s2.
Do we really need to OP_DUP w and t on the script stack ? Like isn't
the s signature verified by Big Script is enough to then decompose the
data payload in Small Script 32-bit inputs.
I don't see where w, t are formally defined in the paper, though I
browsed again the section 4. about realizing Bitcoin equivalence tester
sets. There are just given as parameters, ||w|| =3D 33 and 35 <=3D || t ||
<=3D 75, and it doesn't say if there are data elements or transaction
fields feeded in the signature digest.
> If I understand what you mean by staticness, the answer is no.
> Staticness should not provide any advantage to an attacker. In fact if
> the attacker does not sufficiently randomize the sighash on each
> query, they will have more difficulty, not less, finding collisions.
Yes, for example for staticness if you take bip143 signature digest,
the nVersion field is going to be the same for all the v2 transaction
or v3 transaction.
I see the introduction of the randomness p in the section 3 about
equivalence check in bitcoin, though at the same time the idea is
to find a semantically equivalent transaction to get s of tx(p).
So for a given s signature, is there an existing efficient NP algorithm,
that could find tx1 and tx2 for a same randomness p, where tx1 and
tx2 are not semantically equivalent...? I think it's an interesting
problem, and I don't see the paper is introducing a formal notion of
semantically equivalent.
> I'm not sure what you mean here. Can you provide a concrete example of
> this attack?
Let's recall the Schnorr signing algorithm, G^s =3D R + P^hash(R || m).
Given m is the transaction data and G the generator, R the nonce and
P the public key point, and all of same are equivalent, can I grind
any of G, R or P to find 2 valid curve points for the same signature=20
s where the curve point would correspond to 2 messages m1, m2 ?
I think it's as hard as breaking the DL problem, though I'm not
sure if they have been new cryptanalysis of the Schnorr trick,
compared to existent proofs for Schnorr under the RO / GGM models.
Best,
Antoine
ots hash: 27b5b4bdeea168147580d96769fda7bb395619435832a2e1d0aee0f03b22f27b
Le mercredi 13 novembre 2024 =C3=A0 22:23:29 UTC, Ethan Heilman a =C3=A9cri=
t :
> > If I'm understanding correctly, the goal of the equivalence check is to=
=20
> find a `y` such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)=
`
> are logically equal. Once such `y` is found, the data-carrying
> transaction is grinded until s1 and s2 are equal.
>
> You have the basic idea correct but I think you might be missing one
> piece of this (or perhaps you just simplified some details).
>
> For an honest party spending a covenant the s1 and s2 they generate
> are always equal. This means that y1 <- h_big_script(s1) and y2 <-
> h_small_script(s2) will generate the same y (y1 =3D y2). As you point
> out we can't compare y1 to y2 because they are encoded differently.
>
> > The hash `y` outcome for both `h_big_script` and `h_small_script` will=
=20
> be never compared themselves during the script execution, as we *cannot*.=
=20
> The former is a plain data push and the remainder an array of 32-bits=20
> script elements.
>
> To show equivalence between s1 and s2, we find a value d <-- dGen(w,t)
> which is equal to y.
>
> y1 <- h_big_script(s1)
> d1 <-- dGen_big_script(w, t)
> y1 =3D=3D d1?
>
> y2 <- h_small_script(s2)
> d2 <-- dGen_small_script(w, t)
> y2 =3D=3D d2?
>
> Since the inputs to dGen are 32-bit elements in both dGen_big_script
> and dGen_small_script, we know just DUP w and t for evaluation in
> small script and big script. Since dGen is deterministic it must be
> the case that dGen_big_script(w, t) always equals dGen_small_script(w,
> t). The trick is finding a w, t, s where dGen(w, t) =3D h(s) where s =3D
> s1 =3D s2.
>
> > 1). could a 160-bit hash collision attacker leverage some staticness of=
=20
> fields in bip341 sighash to lower the hardness under 2^109 ? As analyzed =
in=20
> appendix G.
>
> If I understand what you mean by staticness, the answer is no.
> Staticness should not provide any advantage to an attacker. In fact if
> the attacker does not sufficiently randomize the sighash on each
> query, they will have more difficulty, not less, finding collisions.
>
> > 2) The Schnorr trick assumes a signature where the pubkey and nonce are=
=20
> equivalent to the generator point. I think there could be some forgery of=
=20
> the covenanted transaction data, if an adversary can construct a=20
> transaction with still the same s1 and s2 to satisfy Big Script and Small=
=20
> Script.
>
> I'm not sure what you mean here. Can you provide a concrete example of
> this attack?
>
> Thanks,
> Ethan
>
> On Tue, Nov 12, 2024 at 12:41=E2=80=AFPM Antoine Riard <antoin...@gmail.c=
om>=20
> wrote:
> >
> > Hi Ethan,
> >
> > Thanks you for this astute paper.
> >
> > The crux of the paper relies on the equivalence check, which
> > in my understanding can be described as the following (correct
> > me if the set of algorithms differs). On one side, we have our
> > old good correct signatures on the stack. A signature is a
> > commitment to the signature hash fields. This signature can be
> > verified to be valid and it can be given to one of the 160-bits
> > hash functions, i.e OP_SHA1 or OP_RIPEMD160.
> >
> > E.g: <<signature> <OP_DUP> <pubkey> <OP_CHECKSIG> <OP_SHA1>>
> >
> > Doing the Schnorr trick, a data-carrying transaction can be
> > altered until its signature is equivalent to the SchnorrHash,
> > by selecting accordingly that pubkey P and nonce R are equal
> > to the generator. Those elements that the signature is well-
> > composed are further checked by the small script "signature
> > defragmentation" 32-bits integers opcodes.
> >
> > On the other side, we have the 32-bits integers opcodes
> > that can be used to re-implement "bitcoin script natively-ish"
> > cryptographic operations, e.g blake3. Giving the full script
> > would be too lengthy, though hash functions are just (very)
> > smart sequences of XORed seed, key, data that one can simulate
> > easy in bitcoin script. E.g to flip one bit of data.
> >
> > E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP_IF> <0x0> <OP_ELSE>
> > <0x1> <OP_ENDIF>>
> >
> > So let's say we have some basic cryptographic operation
> > like OP_SHA1 in small script (for p2tr tapscript spend
> > the script size limit is the block size). If I'm understanding
> > correctly, the goal of the equivalence check is to find a `y`
> > such that `y <- h_big_script(s1)` and `y <- h_small_script(s2)`
> > are logically equal. Once such `y` is found, the data-carrying
> > transaction is grinded until s1 and s2 are equal. The hash `y`
> > outcome for both `h_big_script` and `h_small_script` will be
> > never compared themselves during the script execution, as
> > we *cannot*. The former is a plain data push and the remainder
> > an array of 32-bits script elements.
> >
> > Once the equivalence check has been done, the restrictions
> > on the signature construction from the Schnorr trick can
> > be checked, and then what covenant checks can be done in
> > the remainder of the 4MB weight unit can be play out. E.g
> > checking the spending transaction nAmount twice 32 bits
> > are less than a given value.
> >
> > <<32-bits> <first digit amount> <OP_LESSTHAN>
> > <32-bits> <second digit amount> <OP_LESSTHAN>>
> >
> > Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160
> > fips-180-1 implem in small script effectively fit in the
> > block size, I think the colliderscript equivalent check
> > construction as presented can be sound, though I have
> > few questions on the security model.
> >
> > 1) Let's say you have a 2 step smart contract as presented
> > in Figure 4. The locking script is committed in a tapscript
> > somewhere in the tree, and as such the collision `y` to found
> > cannot be observed ahead of the spending.
> >
> > Once the script is revealed and before the transaction confirms
> > every 10 block _in average_, an adversary with enormous
> > computational resources, could come to find another collision
> > (what I think you call a triple collision). While the s1 value,
> > i.e the main data fields of the data-carrying transaction
> > shouldn't be know ahead, for some use-cases they might very
> > standards.
> >
> > E.g if you take a vault protocol, only the spent outpoint and
> > pubkey might differs among vault instance belonging to different
> > users (e.g everyone use same emergency or revaulting timelocks by
> > default). So could a 160-bit hash collision attacker leverage
> > some staticness of fields in bip341 sighash to lower the
> > hardness under 2^109 ? As analyzed in appendix G.
> >
> > 2) The Schnorr trick assumes a signature where the pubkey and
> > nonce are equivalent to the generator point. I think there
> > could be some forgery of the covenanted transaction data, if
> > an adversary can construct a transaction with still the same
> > s1 and s2 to satisfy Big Script and Small Script.
> >
> > However, the transaction data would be a security downgrade
> > from the smart contract protocol. E.g a nLocktime committing
> > to a sooner chain tip than now, or even worst a malleated
> > output pubkey. I think it's easy to fix if the schnorr pubkey,
> > nonce are committed in the covenant locking script, and explicitly
> > verified as such in the small script. This is pointed out
> > in the section 2.4 about transaction grinding, but it's not
> > discussed further afaict e.g in the section 7 on the security
> > discussion.
> >
> > Best,
> > Antoine
> > ots hash:=20
> b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9ebbcb6795
> > Le jeudi 7 novembre 2024 =C3=A0 17:48:03 UTC, Ethan Heilman a =C3=A9cri=
t :
> >>
> >> We wanted to make bitcoin-dev aware of our recently published draft on
> >> how to create and spend covenants on Bitcoin using Tapscript.
> >> https://colliderscript.co/colliderscript.pdf
> >>
> >> Our approach does not require soft forks and should work on Bitcoin as
> >> it is currently deployed. While creating these covenants is as easy as
> >> creating a transaction with P2WSH output, spending these covenants
> >> requires substantial computation and involves creating very large
> >> bitcoin transactions.
> >>
> >> Spending such a covenant requires ~2^86 hash calls to SHA-1 and
> >> RIPEMD-160. In comparison, mining a Bitcoin block at current
> >> difficulty requires ~2^78.3 hash calls to SHA256x2. Thus, spending
> >> such a covenant would require the same number of hash queries the
> >> entire Bitcoin network does in roughly ~33 hours. Such covenants could
> >> be created today, but spending them likely requires the creation of
> >> dedicated ASICs.
> >>
> >> While the computational costs limit the immediate applicability of our
> >> covenants, we are optimistic that future work can significantly
> >> improve these numbers. This approach is not a replacement for a
> >> covenant opcode because:
> >> 1. High computational cost: Our approach is likely to be many orders
> >> of magnitude more computationally expensive than a covenant opcode.
> >> 2. 4Mb transactions: Transaction size, computation cost trade-off
> >> exists that reduces the computational costs of these covenants by
> >> increasing the transaction size. Due to most of the cost being
> >> computational it is likely they always be just under 4MB in size even
> >> with efficiency gain. 4MB is the limit for valid transactions.
> >>
> >> Our approach is framed around covenants, but our approach enables
> >> arbitrary computation on Bitcoin transaction data. This arbitrary
> >> computation is bounded only by the circuit size we can pack into what
> >> is left of a 4Mb Bitcoin transaction after it contains all our
> >> necessary machinery. This means, for example, we can do Tapscript
> >> lamport signatures that sign the sighash of the spending transaction.
> >>
> >> One of the authors of our paper, Andrew Poelstra, proposes in the
> >> paper a very interesting use case for lamport signatures (Section 7.2)
> >> which I think is worth making the list aware of. Leveraging the fact
> >> that it is very cheap for users to write and deploy our covenants, it
> >> is only expensive to spend them, the following scheme is proposed. A
> >> user could create a covenant in a tapleaf whose spending condition
> >> requires a Lamport signature over spending transaction. While the
> >> resulting script will be very large, they can hide it in a Taproot
> >> leaf where it will never be serialized on-chain unless it is used. In
> >> the case of a =E2=80=9Csurprise quantum computer=E2=80=9D which forces=
Bitcoin to
> >> suddenly disable all elliptic curve cryptography including taproot key
> >> spends, such users will still be able to spend their coins (though at
> >> enormous cost). If a large quantity of users do this, it may be
> >> possible for the Bitcoin chain to survive such an event, even if no
> >> better solution is found or deployed.
> >>
> >>
> >> Our Technique
> >> =3D=3D=3D=3D
> >>
> >> We will now look at how our technique works by introducing the core
> >> problem we solve and then showing how by solving this problem we can
> >> enforce covenants.
> >>
> >>
> >> Let=E2=80=99s say you want to write a Bitcoin script that checks if
> >> 12345678abcdef00 and [12345678, abcdef00] are equivalent. That is, if
> >> you treated 12345678 and abcdef00as a single element would it be
> >> equal to 12345678abcdef00?
> >>
> >> If we had OP_CAT this would be easy:
> >> 12345678abcdef00 =3D=3D CAT(12345678, abcdef00)
> >>
> >> We call checking if one element is the concatenation of a list of
> >> smaller elements, an equivalence check. We can ask is 12345678abcdef00
> >> equivalent to [12345678, abcdef00]?
> >> In Bitcoin script, checking equivalence between a single big element
> >> and a list of small elements is quite challenging, below we will show
> >> how to do it.
> >>
> >> Before getting there we need to make a short digression first. It has
> >> been part of the lore for some time that Bitcoin script can perform
> >> arbitrary computation on inputs, so long as the inputs are encoded as
> >> a list of 32-bit stack elements. This uses opcodes like OP_ADD,
> >> OP_SUB, which only accept 32-bit inputs. We call functions written
> >> using 32-bit elements Small Script. People have built all sorts of
> >> things in Small Script, for instance you can compute Blake3 in
> >> Tapscript in a bitcoin output using only 45,000 opcodes (a.k.a. 45,000
> >> bytes)! See=20
> https://bitvmx.org/knowledge/optimizing-algorithms-for-bitcoin-script
> >>
> >> Let=E2=80=99s say you have a Small Script implementation of SHA-1 wher=
e it
> >> treats [12345678, ABCDEF00] as an Small Script encoding of
> >> 12345678abcdef00. Does the following equivalence check work?
> >>
> >> OP_SHA1(12345678abcdef00) =3D=3D smallscript_SHA1([12345678, ABCDEF00]=
)
> >>
> >> No, because OP_SHA1 will produce one big 160-bit (20 byte) stack eleme=
nt
> >> OP_SHA1(12345678abcdef00) =E2=86=92 a12d9ee23d07317c2d2d6887fe955819bc=
2d24c5
> >> whereas the Small Script implementation of SHA1 will produce 5 32-bit
> >> (4 Byte) stack elements
> >> smallscript_SHA1([12345678, abcdef00]) =E2=86=92 [a12d9ee2, 3d07317c,
> >> 2d2d6887, fe955819, bc2d24c5]
> >>
> >> Checking if these are the same requires the equivalence check, the
> >> very thing we were trying to build. Ok, hear me out, what if you
> >> magically discovered a value X which was 32-bits in size and just so
> >> happened to collide with 12345678abcdef00. That is,
> >> SHA1(12345678abcdef00) =3D=3D SHA1(X) is true
> >> AND
> >> 12345678abcdef00 !=3D X
> >> AND
> >> Size(X) =3D 32-bits
> >>
> >> You could do an equivalence check for 12345678abcdef00 by doing the=20
> following:
> >>
> >> In Big Script
> >> Check OP_SHA1(12345678abcdef00) =3D=3D OP_SHA1(X)
> >>
> >> In Small Script
> >> Check smallscript_SHA1([12345678, abcdef00]) =3D=3D smallscript_SHA1(X=
)
> >>
> >> If both of these return true, then we decide 12345678abcdef00 is
> >> equivalent to [12345678, abcdef00].
> >>
> >> Put more generally:
> >> Check OP_SHA1(A) =3D=3D OP_SHA1(X)
> >> and
> >>
> >> Check smallscript_SHA1(B) =3D=3D smallscript_SHA1(X)
> >>
> >> Now if A is equivalent to B, and X collides with A, then X will
> >> collide with B in Small Script because B is just the Small Script
> >> encoding of A. However if A is not equivalent to B then this implies a
> >> triple collision which is much more expensive to find:
> >>
> >> SHA1(A) =3D SHA1(X) =3D SHA1(B)
> >>
> >> where A !=3D B, A!=3DX, B!=3DX
> >>
> >> Given the choice between two possibles for an A and B that pass the=20
> check:
> >> 1. A equivalent to B
> >> 2. A not actually equivalent to B requires a triple collision that is
> >> computationally infeasible
> >> We argue that 1 is much more likely.
> >>
> >> Ok, but as some of the cryptographers are now typing, if X is only
> >> 32-bits it is extremely unlikely to find an X that collides for any
> >> particular value. To exploit the birthday bound to find collisions
> >> with a 160-bit hash function you need the input to be >80-bit in size.
> >> Overcoming this problem is the last trick of the paper. We introduce
> >> the function dGen(w, t) which can take any length of input and that
> >> input can be read by Small Script and Big Script.
> >>
> >> dGen(w, t):
> >> y =3D SHA1(w)
> >> for b in t:
> >> If b =3D=3D 0:
> >> y =3D SHA1(y)
> >> If b =3D=3D 1:
> >>
> >> y =3D RIPEMD160(y)
> >> return y
> >>
> >> w is a 33-bit stack element, t is a series of 32-bit stack elements
> >> which we treat as a list of bits. For instance is w=3D312a123e, t=3D01=
101
> >> dGen would return the value created by running
> >> SHA1(RIPEMD160(SHA1(SHA1(RIPEMD160(SHA1(312a123e))))))
> >>
> >> dGen can be run using OP_SHA1 and OP_RIPEMD160 and can also be run in
> >> Small Script using Small Script implementations of SHA1 and RIPEMD160.
> >> Since both sides can use the same stack elements to compute the output
> >> it lets us build our equivalence check. We just need to find a (w, t)
> >> such that:
> >>
> >> OP_SHA1(A) =3D=3D BigScript-dGen(w, t) // Big script dGen using OP_SHA=
1
> >> and OP_RIPEMD160
> >> SHA1(B) =3D=3D SmallScript-dGen(w, t) // Small script dGen
> >>
> >> Finding (w,t) is the main computational expense of spending our
> >> covenant as our covenant depends on this equivalence check. That said
> >> finding collisions in 160-bit hash functions requires significantly
> >> less computation than the Bitcoin network regularly performs. See our
> >> paper for our collision algorithm and discussions of known weaknesses
> >> in SHA1.
> >>
> >> How do you turn this equivalence check into a covenant?
> >>
> >> Past work --=20
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html
> >> -- has shown that by structuring a Schnorr signature correctly, that
> >> Schnorr signature will be the hash of the spending transaction (see
> >> our paper for how we adapt this to our setting). At very high level
> >> our covenant works as follows:
> >>
> >> 1. Get sighash of spending transaction onto stack
> >> 2. Use equivalence check to show that small script encoded sighash is
> >> the same as the sighash we have on the stack
> >> 3. Open the sighash in small script by showing bytes pushed on stack
> >> by the spending transaction hash to sighash are bytes of the spending
> >> transaction. Now we have the bytes of the spending transaction on the
> >> stack.
> >> 4. Use Small Script to enforce covenant on the bytes of the spending
> >> transaction.
> >>
> >> See paper for full details. Thanks,
> >> Ethan
> >
> > --
> > You received this message because you are subscribed to the Google=20
> Groups "Bitcoin Development Mailing List" group.
> > To unsubscribe from this group and stop receiving emails from it, send=
=20
> an email to bitcoindev+...@googlegroups.com.
> > To view this discussion visit=20
> https://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7=
a430b478n%40googlegroups.com
> .
>
--=20
You received this message because you are subscribed to the Google Groups "=
Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
5b69515c-b5b1-4333-88e2-7653face1a3bn%40googlegroups.com.
------=_Part_27735_1001706531.1732506147577
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Ethan,<br /><br />Thanks for the additional thoughts.<br /><br />> Yo=
u have the basic idea correct but I think you might be missing one<br />>=
; piece of this (or perhaps you just simplified some details).<br /><br />R=
eading again the paper, my example and your new example, I don't understand=
<br />yet all the details for sure, though on the fundamental trick, I beli=
eve<br />we're saying more or less the same thing. If I'm understanding cor=
rectly,<br />the trick is about proving that y(y1 =3D y2) both in Big Scrip=
t and Small Script.<br /><br />> For an honest party spending a covenant=
the s1 and s2 they generate<br />> are always equal. This means that y1=
<- h_big_script(s1) and y2 <-<br />> h_small_script(s2) will gene=
rate the same y (y1 =3D y2). As you point<br />> out we can't compare y1=
to y2 because they are encoded differently.<br /><br />Where s1 and s2 is =
the byte-for-byte equivalent spent transactions.<br />For the security defi=
nition you're giving of the equivalence check,<br />I don't think it matter=
s that a party in a multi-party colliderscript-based<br />vault protocol be=
ing honest. Either, the equivalence check is sound,<br />and it's immutable=
once the UTXO's containing the lock script is <br />confirmed in the chain=
, the covenant creator cannot himself generate<br />not equal s1 and s2 _an=
d_ successfully spend the coin.<br /><br />The lemma in terms of security m=
odel, I think for multi-party protocol,<br />is that all the participant sh=
ould verify the soundness of the y(y1 =3D y2),<br />before to engage in the=
protocol (e.g staking more coins under the<br />locking script or doing a =
swap).<br /><br />> we know just DUP w and t for evaluation in<br />>=
small script and big script. Since dGen is deterministic it must be<br />&=
gt; the case that dGen_big_script(w, t) always equals dGen_small_script(w,<=
br />> t). The trick is finding a w, t, s where dGen(w, t) =3D h(s) wher=
e s =3D<br />> s1 =3D s2.<br /><br />Do we really need to OP_DUP w and t=
on the script stack ? Like isn't<br />the s signature verified by Big Scri=
pt is enough to then decompose the<br />data payload in Small Script 32-bit=
inputs.<br /><br />I don't see where w, t are formally defined in the pape=
r, though I<br />browsed again the section 4. about realizing Bitcoin equiv=
alence tester<br />sets. There are just given as parameters, ||w|| =3D 33 a=
nd 35 <=3D || t ||<br /><=3D 75, and it doesn't say if there are data=
elements or transaction<br />fields feeded in the signature digest.<br /><=
br />> If I understand what you mean by staticness, the answer is no.<br=
/>> Staticness should not provide any advantage to an attacker. In fact=
if<br />> the attacker does not sufficiently randomize the sighash on e=
ach<br />> query, they will have more difficulty, not less, finding coll=
isions.<br /><br />Yes, for example for staticness if you take bip143 signa=
ture digest,<br />the nVersion field is going to be the same for all the v2=
transaction<br />or v3 transaction.<br /><br />I see the introduction of t=
he randomness p in the section 3 about<br />equivalence check in bitcoin, t=
hough at the same time the idea is<br />to find a semantically equivalent t=
ransaction to get s of tx(p).<br /><br />So for a given s signature, is the=
re an existing efficient NP algorithm,<br />that could find tx1 and tx2 for=
a same randomness p, where tx1 and<br />tx2 are not semantically equivalen=
t...? I think it's an interesting<br />problem, and I don't see the paper i=
s introducing a formal notion of<br />semantically equivalent.<br /><br />&=
gt; I'm not sure what you mean here. Can you provide a concrete example of<=
br />> this attack?<br /><br />Let's recall the Schnorr signing algorith=
m, G^s =3D R + P^hash(R || m).<br /><br />Given m is the transaction data a=
nd G the generator, R the nonce and<br />P the public key point, and all of=
same are equivalent, can I grind<br />any of G, R or P to find 2 valid cur=
ve points for the same signature <br />s where the curve point would corres=
pond to 2 messages m1, m2 ?<br /><br />I think it's as hard as breaking the=
DL problem, though I'm not<br />sure if they have been new cryptanalysis o=
f the Schnorr trick,<br />compared to existent proofs for Schnorr under the=
RO / GGM models.<br /><br />Best,<br />Antoine<br />ots hash: 27b5b4bdeea1=
68147580d96769fda7bb395619435832a2e1d0aee0f03b22f27b<br /><br /><div class=
=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">Le mercredi 13 nove=
mbre 2024 =C3=A0 22:23:29 UTC, Ethan Heilman a =C3=A9crit=C2=A0:<br/></div>=
<blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-left=
: 1px solid rgb(204, 204, 204); padding-left: 1ex;">> If I'm unders=
tanding correctly, the goal of the equivalence check is to find a `y` such =
that `y <- h_big_script(s1)` and `y <- h_small_script(s2)`
<br>are logically equal. Once such `y` is found, the data-carrying
<br>transaction is grinded until s1 and s2 are equal.
<br>
<br>You have the basic idea correct but I think you might be missing one
<br>piece of this (or perhaps you just simplified some details).
<br>
<br>For an honest party spending a covenant the s1 and s2 they generate
<br>are always equal. This means that y1 <- h_big_script(s1) and y2 <=
-
<br>h_small_script(s2) will generate the same y (y1 =3D y2). As you point
<br>out we can't compare y1 to y2 because they are encoded differently.
<br>
<br>> The hash `y` outcome for both `h_big_script` and `h_small_script`=
will be never compared themselves during the script execution, as we *cann=
ot*. The former is a plain data push and the remainder an array of 32-bits =
script elements.
<br>
<br>To show equivalence between s1 and s2, we find a value d <-- dGen(w,=
t)
<br>which is equal to y.
<br>
<br>y1 <- h_big_script(s1)
<br>d1 <-- dGen_big_script(w, t)
<br>y1 =3D=3D d1?
<br>
<br>y2 <- h_small_script(s2)
<br>d2 <-- dGen_small_script(w, t)
<br>y2 =3D=3D d2?
<br>
<br>Since the inputs to dGen are 32-bit elements in both dGen_big_script
<br>and dGen_small_script, we know just DUP w and t for evaluation in
<br>small script and big script. Since dGen is deterministic it must be
<br>the case that dGen_big_script(w, t) always equals dGen_small_script(w,
<br>t). The trick is finding a w, t, s where dGen(w, t) =3D h(s) where s =
=3D
<br>s1 =3D s2.
<br>
<br>> 1). could a 160-bit hash collision attacker leverage some staticne=
ss of fields in bip341 sighash to lower the hardness under 2^109 ? As analy=
zed in appendix G.
<br>
<br>If I understand what you mean by staticness, the answer is no.
<br>Staticness should not provide any advantage to an attacker. In fact if
<br>the attacker does not sufficiently randomize the sighash on each
<br>query, they will have more difficulty, not less, finding collisions.
<br>
<br>> 2) The Schnorr trick assumes a signature where the pubkey and nonc=
e are equivalent to the generator point. I think there could be some forger=
y of the covenanted transaction data, if an adversary can construct a trans=
action with still the same s1 and s2 to satisfy Big Script and Small Script=
.
<br>
<br>I'm not sure what you mean here. Can you provide a concrete example=
of
<br>this attack?
<br>
<br>Thanks,
<br>Ethan
<br>
<br>On Tue, Nov 12, 2024 at 12:41=E2=80=AFPM Antoine Riard <<a href data=
-email-masked rel=3D"nofollow">antoin...@gmail.com</a>> wrote:
<br>>
<br>> Hi Ethan,
<br>>
<br>> Thanks you for this astute paper.
<br>>
<br>> The crux of the paper relies on the equivalence check, which
<br>> in my understanding can be described as the following (correct
<br>> me if the set of algorithms differs). On one side, we have our
<br>> old good correct signatures on the stack. A signature is a
<br>> commitment to the signature hash fields. This signature can be
<br>> verified to be valid and it can be given to one of the 160-bits
<br>> hash functions, i.e OP_SHA1 or OP_RIPEMD160.
<br>>
<br>> E.g: <<signature> <OP_DUP> <pubkey> <OP_CH=
ECKSIG> <OP_SHA1>>
<br>>
<br>> Doing the Schnorr trick, a data-carrying transaction can be
<br>> altered until its signature is equivalent to the SchnorrHash,
<br>> by selecting accordingly that pubkey P and nonce R are equal
<br>> to the generator. Those elements that the signature is well-
<br>> composed are further checked by the small script "signature
<br>> defragmentation" 32-bits integers opcodes.
<br>>
<br>> On the other side, we have the 32-bits integers opcodes
<br>> that can be used to re-implement "bitcoin script natively-ish=
"
<br>> cryptographic operations, e.g blake3. Giving the full script
<br>> would be too lengthy, though hash functions are just (very)
<br>> smart sequences of XORed seed, key, data that one can simulate
<br>> easy in bitcoin script. E.g to flip one bit of data.
<br>>
<br>> E.g: <<1-bit input_a> <0x1> <OP_EQUAL> <OP=
_IF> <0x0> <OP_ELSE>
<br>> <0x1> <OP_ENDIF>>
<br>>
<br>> So let's say we have some basic cryptographic operation
<br>> like OP_SHA1 in small script (for p2tr tapscript spend
<br>> the script size limit is the block size). If I'm understanding
<br>> correctly, the goal of the equivalence check is to find a `y`
<br>> such that `y <- h_big_script(s1)` and `y <- h_small_script(s=
2)`
<br>> are logically equal. Once such `y` is found, the data-carrying
<br>> transaction is grinded until s1 and s2 are equal. The hash `y`
<br>> outcome for both `h_big_script` and `h_small_script` will be
<br>> never compared themselves during the script execution, as
<br>> we *cannot*. The former is a plain data push and the remainder
<br>> an array of 32-bits script elements.
<br>>
<br>> Once the equivalence check has been done, the restrictions
<br>> on the signature construction from the Schnorr trick can
<br>> be checked, and then what covenant checks can be done in
<br>> the remainder of the 4MB weight unit can be play out. E.g
<br>> checking the spending transaction nAmount twice 32 bits
<br>> are less than a given value.
<br>>
<br>> <<32-bits> <first digit amount> <OP_LESSTHAN>
<br>> <32-bits> <second digit amount> <OP_LESSTHAN>>=
;
<br>>
<br>> Withstanding the code proof that a OP_SHA1 or OP_RIPEMD160
<br>> fips-180-1 implem in small script effectively fit in the
<br>> block size, I think the colliderscript equivalent check
<br>> construction as presented can be sound, though I have
<br>> few questions on the security model.
<br>>
<br>> 1) Let's say you have a 2 step smart contract as presented
<br>> in Figure 4. The locking script is committed in a tapscript
<br>> somewhere in the tree, and as such the collision `y` to found
<br>> cannot be observed ahead of the spending.
<br>>
<br>> Once the script is revealed and before the transaction confirms
<br>> every 10 block _in average_, an adversary with enormous
<br>> computational resources, could come to find another collision
<br>> (what I think you call a triple collision). While the s1 value,
<br>> i.e the main data fields of the data-carrying transaction
<br>> shouldn't be know ahead, for some use-cases they might very
<br>> standards.
<br>>
<br>> E.g if you take a vault protocol, only the spent outpoint and
<br>> pubkey might differs among vault instance belonging to different
<br>> users (e.g everyone use same emergency or revaulting timelocks by
<br>> default). So could a 160-bit hash collision attacker leverage
<br>> some staticness of fields in bip341 sighash to lower the
<br>> hardness under 2^109 ? As analyzed in appendix G.
<br>>
<br>> 2) The Schnorr trick assumes a signature where the pubkey and
<br>> nonce are equivalent to the generator point. I think there
<br>> could be some forgery of the covenanted transaction data, if
<br>> an adversary can construct a transaction with still the same
<br>> s1 and s2 to satisfy Big Script and Small Script.
<br>>
<br>> However, the transaction data would be a security downgrade
<br>> from the smart contract protocol. E.g a nLocktime committing
<br>> to a sooner chain tip than now, or even worst a malleated
<br>> output pubkey. I think it's easy to fix if the schnorr pubkey,
<br>> nonce are committed in the covenant locking script, and explicitly
<br>> verified as such in the small script. This is pointed out
<br>> in the section 2.4 about transaction grinding, but it's not
<br>> discussed further afaict e.g in the section 7 on the security
<br>> discussion.
<br>>
<br>> Best,
<br>> Antoine
<br>> ots hash: b47373e430c25a96e642ddad3cc330ee364f06c06f81a63238926a9e=
bbcb6795
<br>> Le jeudi 7 novembre 2024 =C3=A0 17:48:03 UTC, Ethan Heilman a =C3=
=A9crit :
<br>>>
<br>>> We wanted to make bitcoin-dev aware of our recently published =
draft on
<br>>> how to create and spend covenants on Bitcoin using Tapscript.
<br>>> <a href=3D"https://colliderscript.co/colliderscript.pdf" targe=
t=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.co=
m/url?hl=3Dfr&q=3Dhttps://colliderscript.co/colliderscript.pdf&sour=
ce=3Dgmail&ust=3D1732592503978000&usg=3DAOvVaw0qM2BW4w6WvstDfuJvf1W=
a">https://colliderscript.co/colliderscript.pdf</a>
<br>>>
<br>>> Our approach does not require soft forks and should work on Bi=
tcoin as
<br>>> it is currently deployed. While creating these covenants is as=
easy as
<br>>> creating a transaction with P2WSH output, spending these coven=
ants
<br>>> requires substantial computation and involves creating very la=
rge
<br>>> bitcoin transactions.
<br>>>
<br>>> Spending such a covenant requires ~2^86 hash calls to SHA-1 an=
d
<br>>> RIPEMD-160. In comparison, mining a Bitcoin block at current
<br>>> difficulty requires ~2^78.3 hash calls to SHA256x2. Thus, spen=
ding
<br>>> such a covenant would require the same number of hash queries =
the
<br>>> entire Bitcoin network does in roughly ~33 hours. Such covenan=
ts could
<br>>> be created today, but spending them likely requires the creati=
on of
<br>>> dedicated ASICs.
<br>>>
<br>>> While the computational costs limit the immediate applicabilit=
y of our
<br>>> covenants, we are optimistic that future work can significantl=
y
<br>>> improve these numbers. This approach is not a replacement for =
a
<br>>> covenant opcode because:
<br>>> 1. High computational cost: Our approach is likely to be many =
orders
<br>>> of magnitude more computationally expensive than a covenant op=
code.
<br>>> 2. 4Mb transactions: Transaction size, computation cost trade-=
off
<br>>> exists that reduces the computational costs of these covenants=
by
<br>>> increasing the transaction size. Due to most of the cost being
<br>>> computational it is likely they always be just under 4MB in si=
ze even
<br>>> with efficiency gain. 4MB is the limit for valid transactions.
<br>>>
<br>>> Our approach is framed around covenants, but our approach enab=
les
<br>>> arbitrary computation on Bitcoin transaction data. This arbitr=
ary
<br>>> computation is bounded only by the circuit size we can pack in=
to what
<br>>> is left of a 4Mb Bitcoin transaction after it contains all our
<br>>> necessary machinery. This means, for example, we can do Tapscr=
ipt
<br>>> lamport signatures that sign the sighash of the spending trans=
action.
<br>>>
<br>>> One of the authors of our paper, Andrew Poelstra, proposes in =
the
<br>>> paper a very interesting use case for lamport signatures (Sect=
ion 7.2)
<br>>> which I think is worth making the list aware of. Leveraging th=
e fact
<br>>> that it is very cheap for users to write and deploy our covena=
nts, it
<br>>> is only expensive to spend them, the following scheme is propo=
sed. A
<br>>> user could create a covenant in a tapleaf whose spending condi=
tion
<br>>> requires a Lamport signature over spending transaction. While =
the
<br>>> resulting script will be very large, they can hide it in a Tap=
root
<br>>> leaf where it will never be serialized on-chain unless it is u=
sed. In
<br>>> the case of a =E2=80=9Csurprise quantum computer=E2=80=9D whic=
h forces Bitcoin to
<br>>> suddenly disable all elliptic curve cryptography including tap=
root key
<br>>> spends, such users will still be able to spend their coins (th=
ough at
<br>>> enormous cost). If a large quantity of users do this, it may b=
e
<br>>> possible for the Bitcoin chain to survive such an event, even =
if no
<br>>> better solution is found or deployed.
<br>>>
<br>>>
<br>>> Our Technique
<br>>> =3D=3D=3D=3D
<br>>>
<br>>> We will now look at how our technique works by introducing the=
core
<br>>> problem we solve and then showing how by solving this problem =
we can
<br>>> enforce covenants.
<br>>>
<br>>>
<br>>> Let=E2=80=99s say you want to write a Bitcoin script that chec=
ks if
<br>>> 12345678abcdef00 and [12345678, abcdef00] are equivalent. That=
is, if
<br>>> you treated 12345678 and abcdef00as a single element would it =
be
<br>>> equal to 12345678abcdef00?
<br>>>
<br>>> If we had OP_CAT this would be easy:
<br>>> 12345678abcdef00 =3D=3D CAT(12345678, abcdef00)
<br>>>
<br>>> We call checking if one element is the concatenation of a list=
of
<br>>> smaller elements, an equivalence check. We can ask is 12345678=
abcdef00
<br>>> equivalent to [12345678, abcdef00]?
<br>>> In Bitcoin script, checking equivalence between a single big e=
lement
<br>>> and a list of small elements is quite challenging, below we wi=
ll show
<br>>> how to do it.
<br>>>
<br>>> Before getting there we need to make a short digression first.=
It has
<br>>> been part of the lore for some time that Bitcoin script can pe=
rform
<br>>> arbitrary computation on inputs, so long as the inputs are enc=
oded as
<br>>> a list of 32-bit stack elements. This uses opcodes like OP_ADD=
,
<br>>> OP_SUB, which only accept 32-bit inputs. We call functions wri=
tten
<br>>> using 32-bit elements Small Script. People have built all sort=
s of
<br>>> things in Small Script, for instance you can compute Blake3 in
<br>>> Tapscript in a bitcoin output using only 45,000 opcodes (a.k.a=
. 45,000
<br>>> bytes)! See <a href=3D"https://bitvmx.org/knowledge/optimizing=
-algorithms-for-bitcoin-script" target=3D"_blank" rel=3D"nofollow" data-saf=
eredirecturl=3D"https://www.google.com/url?hl=3Dfr&q=3Dhttps://bitvmx.o=
rg/knowledge/optimizing-algorithms-for-bitcoin-script&source=3Dgmail&am=
p;ust=3D1732592503978000&usg=3DAOvVaw23wbK_J99rQZHnPnfRq0Sx">https://bi=
tvmx.org/knowledge/optimizing-algorithms-for-bitcoin-script</a>
<br>>>
<br>>> Let=E2=80=99s say you have a Small Script implementation of SH=
A-1 where it
<br>>> treats [12345678, ABCDEF00] as an Small Script encoding of
<br>>> 12345678abcdef00. Does the following equivalence check work?
<br>>>
<br>>> OP_SHA1(12345678abcdef00) =3D=3D smallscript_SHA1([12345678, A=
BCDEF00])
<br>>>
<br>>> No, because OP_SHA1 will produce one big 160-bit (20 byte) sta=
ck element
<br>>> OP_SHA1(12345678abcdef00) =E2=86=92 a12d9ee23d07317c2d2d6887fe=
955819bc2d24c5
<br>>> whereas the Small Script implementation of SHA1 will produce 5=
32-bit
<br>>> (4 Byte) stack elements
<br>>> smallscript_SHA1([12345678, abcdef00]) =E2=86=92 [a12d9ee2, 3d=
07317c,
<br>>> 2d2d6887, fe955819, bc2d24c5]
<br>>>
<br>>> Checking if these are the same requires the equivalence check,=
the
<br>>> very thing we were trying to build. Ok, hear me out, what if y=
ou
<br>>> magically discovered a value X which was 32-bits in size and j=
ust so
<br>>> happened to collide with 12345678abcdef00. That is,
<br>>> SHA1(12345678abcdef00) =3D=3D SHA1(X) is true
<br>>> AND
<br>>> 12345678abcdef00 !=3D X
<br>>> AND
<br>>> Size(X) =3D 32-bits
<br>>>
<br>>> You could do an equivalence check for 12345678abcdef00 by doin=
g the following:
<br>>>
<br>>> In Big Script
<br>>> Check OP_SHA1(12345678abcdef00) =3D=3D OP_SHA1(X)
<br>>>
<br>>> In Small Script
<br>>> Check smallscript_SHA1([12345678, abcdef00]) =3D=3D smallscrip=
t_SHA1(X)
<br>>>
<br>>> If both of these return true, then we decide 12345678abcdef00 =
is
<br>>> equivalent to [12345678, abcdef00].
<br>>>
<br>>> Put more generally:
<br>>> Check OP_SHA1(A) =3D=3D OP_SHA1(X)
<br>>> and
<br>>>
<br>>> Check smallscript_SHA1(B) =3D=3D smallscript_SHA1(X)
<br>>>
<br>>> Now if A is equivalent to B, and X collides with A, then X wil=
l
<br>>> collide with B in Small Script because B is just the Small Scr=
ipt
<br>>> encoding of A. However if A is not equivalent to B then this i=
mplies a
<br>>> triple collision which is much more expensive to find:
<br>>>
<br>>> SHA1(A) =3D SHA1(X) =3D SHA1(B)
<br>>>
<br>>> where A !=3D B, A!=3DX, B!=3DX
<br>>>
<br>>> Given the choice between two possibles for an A and B that pas=
s the check:
<br>>> 1. A equivalent to B
<br>>> 2. A not actually equivalent to B requires a triple collision =
that is
<br>>> computationally infeasible
<br>>> We argue that 1 is much more likely.
<br>>>
<br>>> Ok, but as some of the cryptographers are now typing, if X is =
only
<br>>> 32-bits it is extremely unlikely to find an X that collides fo=
r any
<br>>> particular value. To exploit the birthday bound to find collis=
ions
<br>>> with a 160-bit hash function you need the input to be >80-b=
it in size.
<br>>> Overcoming this problem is the last trick of the paper. We int=
roduce
<br>>> the function dGen(w, t) which can take any length of input and=
that
<br>>> input can be read by Small Script and Big Script.
<br>>>
<br>>> dGen(w, t):
<br>>> y =3D SHA1(w)
<br>>> for b in t:
<br>>> If b =3D=3D 0:
<br>>> y =3D SHA1(y)
<br>>> If b =3D=3D 1:
<br>>>
<br>>> y =3D RIPEMD160(y)
<br>>> return y
<br>>>
<br>>> w is a 33-bit stack element, t is a series of 32-bit stack ele=
ments
<br>>> which we treat as a list of bits. For instance is w=3D312a123e=
, t=3D01101
<br>>> dGen would return the value created by running
<br>>> SHA1(RIPEMD160(SHA1(SHA1(RIPEMD160(SHA1(312a123e))))))
<br>>>
<br>>> dGen can be run using OP_SHA1 and OP_RIPEMD160 and can also be=
run in
<br>>> Small Script using Small Script implementations of SHA1 and RI=
PEMD160.
<br>>> Since both sides can use the same stack elements to compute th=
e output
<br>>> it lets us build our equivalence check. We just need to find a=
(w, t)
<br>>> such that:
<br>>>
<br>>> OP_SHA1(A) =3D=3D BigScript-dGen(w, t) // Big script dGen usin=
g OP_SHA1
<br>>> and OP_RIPEMD160
<br>>> SHA1(B) =3D=3D SmallScript-dGen(w, t) // Small script dGen
<br>>>
<br>>> Finding (w,t) is the main computational expense of spending ou=
r
<br>>> covenant as our covenant depends on this equivalence check. Th=
at said
<br>>> finding collisions in 160-bit hash functions requires signific=
antly
<br>>> less computation than the Bitcoin network regularly performs. =
See our
<br>>> paper for our collision algorithm and discussions of known wea=
knesses
<br>>> in SHA1.
<br>>>
<br>>> How do you turn this equivalence check into a covenant?
<br>>>
<br>>> Past work -- <a href=3D"https://www.wpsoftware.net/andrew/blog=
/cat-and-schnorr-tricks-i.html" target=3D"_blank" rel=3D"nofollow" data-saf=
eredirecturl=3D"https://www.google.com/url?hl=3Dfr&q=3Dhttps://www.wpso=
ftware.net/andrew/blog/cat-and-schnorr-tricks-i.html&source=3Dgmail&=
;ust=3D1732592503978000&usg=3DAOvVaw27Gs19EMPGJRUW_pKWT-mg">https://www=
.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html</a>
<br>>> -- has shown that by structuring a Schnorr signature correctly=
, that
<br>>> Schnorr signature will be the hash of the spending transaction=
(see
<br>>> our paper for how we adapt this to our setting). At very high =
level
<br>>> our covenant works as follows:
<br>>>
<br>>> 1. Get sighash of spending transaction onto stack
<br>>> 2. Use equivalence check to show that small script encoded sig=
hash is
<br>>> the same as the sighash we have on the stack
<br>>> 3. Open the sighash in small script by showing bytes pushed on=
stack
<br>>> by the spending transaction hash to sighash are bytes of the s=
pending
<br>>> transaction. Now we have the bytes of the spending transaction=
on the
<br>>> stack.
<br>>> 4. Use Small Script to enforce covenant on the bytes of the sp=
ending
<br>>> transaction.
<br>>>
<br>>> See paper for full details. Thanks,
<br>>> Ethan
<br>>
<br>> --
<br>> You received this message because you are subscribed to the Google=
Groups "Bitcoin Development Mailing List" group.
<br>> To unsubscribe from this group and stop receiving emails from it, =
send an email to <a href data-email-masked rel=3D"nofollow">bitcoindev+...@=
googlegroups.com</a>.
<br>> To view this discussion visit <a href=3D"https://groups.google.com=
/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b478n%40googlegroups.co=
m" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.g=
oogle.com/url?hl=3Dfr&q=3Dhttps://groups.google.com/d/msgid/bitcoindev/=
fc031fe3-444c-446d-a5c1-f2d7a430b478n%2540googlegroups.com&source=3Dgma=
il&ust=3D1732592503978000&usg=3DAOvVaw0DZk3hyccbjEEqTNoHhcH8">https=
://groups.google.com/d/msgid/bitcoindev/fc031fe3-444c-446d-a5c1-f2d7a430b47=
8n%40googlegroups.com</a>.
<br></blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/5b69515c-b5b1-4333-88e2-7653face1a3bn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/5b69515c-b5b1-4333-88e2-7653face1a3bn%40googlegroups.com</a>.<br />
------=_Part_27735_1001706531.1732506147577--
------=_Part_27734_151653098.1732506147577--
|