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
|
Delivery-date: Thu, 07 Nov 2024 09:48:10 -0800
Received: from mail-yb1-f185.google.com ([209.85.219.185])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBT72WO4QMGQEGGIOLKA@googlegroups.com>)
id 1t96c5-0007EU-Ht
for bitcoindev@gnusha.org; Thu, 07 Nov 2024 09:48:10 -0800
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e293b3e014asf1848214276.3
for <bitcoindev@gnusha.org>; Thu, 07 Nov 2024 09:48:09 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1731001683; cv=pass;
d=google.com; s=arc-20240605;
b=YEqYPSequK0+Eb8zNQeBkUTqvbakXt0J5qeGGWPVL2FIyf/GJfuXRz8wNBanYH5SSn
QWwWayA9UQ1/bkBMpZRi1FaifOO3pTolmeAyP6t4ejxJhOoBdGAh0SBNtHROeauYrx2s
xqaOLg1IMhJYTU4AphBu/LF44FeiXI7OX4oteiI9by/DVYKTVJ63mrX00QfPuEIr1YHN
4h9bFaO1tSEzGmxi+c8lVJnIOMR685hqt/XjNVXe6h/TRUNJixSkB3HUDkLLi0+qOxIQ
V7/6/T5aXh2BAg/LSyTSVDD0oVJJ2lVGHz+/GnfUYwMV5iSYGmYvtwHEfIlZWQy/Gm8P
eyOQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:content-transfer-encoding:to
:subject:message-id:date:from:mime-version:sender:dkim-signature
:dkim-signature;
bh=wUf0OmnO4ki9Bmyhc7tAWTyIJH30/L0O7ZiCjsgEIJM=;
fh=PlGNjHfkbHaYh95X16vq7PtINym1vg30AfjsckoNueE=;
b=HTX47OKsT5EWSy5f2tsJ45wu7jive1aUav7ipApZdIMN2T6cyn6IskY/hpRJIJdglW
ywrn3JweQj0wsWajPXajLvREv0cQW/sias7AelsRkf3qRIVARh7Mi2eHRVLORPrE+Ec8
xo1MZUtIE4Oh1mQGzPlGrAEn+SYwSG9A9Gfs7xJzF8GvvrCvANf9y5YQla3kCEt6YzdQ
4hJzMDxfBpcn5KlXFqwryh8Nnvewl2LCf1lPHsn+1sz7Oy0Sjn6cZXuJ1G7l0ATL7I2Z
FtdpdsqB2y87aI8omNG4t2YFbH4USyLhDwGvW+zh/oBUxssLi0GWoGz/yHUUrPfRm2pp
CFFg==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=Mchp0nOL;
spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::62d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1731001683; x=1731606483; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:content-transfer-encoding:to:subject:message-id
:date:from:mime-version:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=wUf0OmnO4ki9Bmyhc7tAWTyIJH30/L0O7ZiCjsgEIJM=;
b=NThktA7dx5lwJsmVU+J3DMccoBBTi8/pBOH5ljH0H7YUI8IwRJmOrNkUxsTe3Nn+BT
qlytQHcaVXdGvvsbm3xPD1i68CJ7Wk342nEhxHpIFXcvIhYTrRkyPzGaKfy3eKoYmrtr
Kofp+C0i82OOy9d6UHVn9QmkrKhdohQGr3s+bx13TP6JxzOmzTxDKxfeKT+oF8HsN73L
VdVEk/gLz8CCvb4ZSVpkGyRdq5xUkowS6BbfED6rLxJhv//bCGM1WD/GvSvBOke49Gt5
UDuLmhYAUAeo4tYMPuxlgipWnXNDAvTEAxNDiDdlFOWgJSvqTHzk5S58Juh2kA6ABVf1
cj0g==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1731001683; x=1731606483; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:content-transfer-encoding:to:subject:message-id
:date:from:mime-version:from:to:cc:subject:date:message-id:reply-to;
bh=wUf0OmnO4ki9Bmyhc7tAWTyIJH30/L0O7ZiCjsgEIJM=;
b=ivlNRDdfNSIMdJYQPXMV5Z7pkio6c7e/Vuf/cuKPgQVrVhkhH5OxkzrYIVgPLz1F/9
fp5tN7lsmCgPJtr+pI4HlsCB6SizbYl7wwtcCif1Aia1nmHQnCCS/gF1CzE6OoIT5Fee
fgyoINnrZHwV1ZFSKiKK+hFY3ROtAF11FP4Zcgf0VIupQEyShSSRxhhSxCeZ9wWXo+NY
nDFJpbxJoYKQQO8osPnHUuFsJmuUY/xexeDbnu4lNdXSFIEl38eN/NUAezkRPzxVlLDd
W8FyLMOU2tqk5/t/DAiNL7jkW1kTsTtof4ho6kuT8ers/EGckhlAYrTUT8cFpMLg/15J
ppdA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1731001683; x=1731606483;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:content-transfer-encoding:to:subject:message-id
:date:from:mime-version:x-beenthere:x-gm-message-state:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=wUf0OmnO4ki9Bmyhc7tAWTyIJH30/L0O7ZiCjsgEIJM=;
b=uEg3Us7qMJYsw97IahDJiDpDsRcpoF1YOOO/ipc5SH7xbG22UdVVABEOQtNPEcxu5H
5v4F9viCp1tjt6r1lC2ygiDWkIEque1Nr+6YakcIhO+N4M5vsZyNP0dlPlef/tRQ/jAl
IMQzKd2y/E9bGFk3OLMquZ4jA9MqgeoSTpKXZ3i1N6TEn3AEkjL9A8HJ6PKX6MuuMHmt
3e5uRXEpje5v+pl2+2wBzc1J4IlGK85zsZDlegWTtZHEg+hUo9+AZ3wQWeGlMhwifukS
wak84Lk6T3bhd8nYkUphqmSjwxEVuAqzmhaqEVFVSGldEwJ6RquQfie1DWDaSHqDgk0q
1BbQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUmS+X+gdknKslnADBXvc+SH7VmZ1ufB3HekYQNUMaHvmKIgfY19qJDn1xlaxxMKQk9NUfD/lwyp7Jq@gnusha.org
X-Gm-Message-State: AOJu0YwbgUSlsZUaRRxGtfGWZv/CK90GaZSXSutzp/vgGYgVhXaPUs93
mPRy1YcxGfNxmn5DpWVZbdlJpH9TOxT9eEE50cFHw3mMg9TUDJ8a
X-Google-Smtp-Source: AGHT+IEW1+CeUzDu+MHI/NdBR8c+CrDxqYY9D1wa8F8pRXQWccGRQ6YmNTdF55ZGr6dJehEKdHaTzA==
X-Received: by 2002:a05:6902:118e:b0:e30:e1f3:2aab with SMTP id 3f1490d57ef6-e337e43dc12mr321657276.39.1731001682927;
Thu, 07 Nov 2024 09:48:02 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:b07:b0:e2b:b91d:c685 with SMTP id
3f1490d57ef6-e336800d633ls1470045276.0.-pod-prod-04-us; Thu, 07 Nov 2024
09:47:59 -0800 (PST)
X-Received: by 2002:a05:6902:2488:b0:e2e:3407:fa06 with SMTP id 3f1490d57ef6-e337e46007amr265529276.50.1731001679441;
Thu, 07 Nov 2024 09:47:59 -0800 (PST)
Received: by 2002:a05:620a:3f89:b0:7b1:4744:32d3 with SMTP id af79cd13be357-7b327dbe1eems85a;
Thu, 7 Nov 2024 09:45:24 -0800 (PST)
X-Received: by 2002:a05:600c:1911:b0:431:59ab:15cf with SMTP id 5b1f17b1804b1-4319acb2a0bmr403232285e9.19.1731001521839;
Thu, 07 Nov 2024 09:45:21 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1731001521; cv=none;
d=google.com; s=arc-20240605;
b=CHAamr40cW2V4yYMX1wkDpirRDx2QlWKqUf6EvI2P2Lf3g+SfBYdTmPnRVJOsekXag
BV1hjnA607TiR1n+RYo34iz0AowL7a9tpyOlblD/4BORaxndd0dHMjZtSYy38u/gYzmv
Ev0iPEb7bBrNQQ2e1vGU3xJ5YCe4/l5LhJyzX+DzBJl/A26vPmt5BtnXAZOOYAv4uuer
DL+7k36Ku20iv5P6ZA3WcZvAo6Nhzq12EAdW5/gHD2MgHJVxXw3t3VV4nUMJt3mLqp91
0MUoaK6nuzGE54UP9904hqLtYnSfzCn0mH9UyAtlkwju1830h/DWL+b1b/WBDC4naMke
d7HA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=content-transfer-encoding:to:subject:message-id:date:from
:mime-version:dkim-signature;
bh=j6KW3BW2OhHdRbijdm6GxRiOMm1/zFF2Ug+rEgeisfA=;
fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
b=Dzk7hPWbtJS41nZShETOCzkAwQ5fRuq7zbUqUqLYIERABmcVJPHvytMVJHHQUvNYF9
DjWIkVXWenvRTMS9CcVB6JRM+kd+myrFlsURluulDZDoy4xfou4SkPlb+6WXjfxfMKvB
aUEYPXIcoyfBrxSRWsK8jau6L31hbuA2sIIbQFlWr2bzzzV55flyPrMNpbw/XKATBS34
8IhkDOoQCKjnpjT5Zyj6mDwmlq+ZmR5ObDRrhLxpVUBU1Lavb2vPgV6v0egSwnT+dGeK
rRNKTO9AMLv+KyfH0mQBydVrWpvR7268zbf/V0QmbuvTtk6mv84rUeTdupqq+1AQBZ7b
chaw==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=Mchp0nOL;
spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::62d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
dara=pass header.i=@googlegroups.com
Received: from mail-ej1-x62d.google.com (mail-ej1-x62d.google.com. [2a00:1450:4864:20::62d])
by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-432a26a896bsi2198995e9.0.2024.11.07.09.45.21
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Thu, 07 Nov 2024 09:45:21 -0800 (PST)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::62d as permitted sender) client-ip=2a00:1450:4864:20::62d;
Received: by mail-ej1-x62d.google.com with SMTP id a640c23a62f3a-a9a0ef5179dso196994966b.1
for <bitcoindev@googlegroups.com>; Thu, 07 Nov 2024 09:45:21 -0800 (PST)
X-Received: by 2002:a17:907:961c:b0:a9e:e1a9:792f with SMTP id
a640c23a62f3a-a9ee1a9ba41mr295028966b.25.1731001520726; Thu, 07 Nov 2024
09:45:20 -0800 (PST)
MIME-Version: 1.0
From: Ethan Heilman <eth3rs@gmail.com>
Date: Thu, 7 Nov 2024 12:44:44 -0500
Message-ID: <CAEM=y+W2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ@mail.gmail.com>
Subject: [bitcoindev] ColliderScript: Covenants in Bitcoin via 160-bit hash collisions
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@gmail.com header.s=20230601 header.b=Mchp0nOL; spf=pass
(google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::62d as
permitted sender) smtp.mailfrom=eth3rs@gmail.com; dmarc=pass (p=NONE
sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/)
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 Bitc=
oin 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 https://bitvmx.org/knowledge/optimizing-algorithms-for-bitcoin-=
script
Let=E2=80=99s say you have a Small Script implementation of SHA-1 where 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 element
OP_SHA1(12345678abcdef00) =E2=86=92 a12d9ee23d07317c2d2d6887fe955819bc2d24=
c5
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 followi=
ng:
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 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=3D01101
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_SHA1
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 -- 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
--=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/=
CAEM%3Dy%2BW2jyFoJAq9XrE9whQ7EZG4HRST01TucWHJtBhQiRTSNQ%40mail.gmail.com.
|