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
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pete@petertodd.org>) id 1XZJd7-00054a-OF
for bitcoin-development@lists.sourceforge.net;
Wed, 01 Oct 2014 13:07:41 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org
designates 62.13.148.100 as permitted sender)
client-ip=62.13.148.100; envelope-from=pete@petertodd.org;
helo=outmail148100.authsmtp.co.uk;
Received: from outmail148100.authsmtp.co.uk ([62.13.148.100])
by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1XZJd0-00024A-V3 for bitcoin-development@lists.sourceforge.net;
Wed, 01 Oct 2014 13:07:41 +0000
Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235])
by punt15.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s91D7SqV001601
for <bitcoin-development@lists.sourceforge.net>;
Wed, 1 Oct 2014 14:07:28 +0100 (BST)
Received: from savin.petertodd.org (75-119-251-161.dsl.teksavvy.com
[75.119.251.161]) (authenticated bits=128)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s91D7NQ9075176
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO)
for <bitcoin-development@lists.sourceforge.net>;
Wed, 1 Oct 2014 14:07:26 +0100 (BST)
Date: Wed, 1 Oct 2014 09:08:26 -0400
From: Peter Todd <pete@petertodd.org>
To: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Message-ID: <20141001130826.GM28710@savin.petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="uwB7x3tnyrZQfZJI"
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: e412afb6-496b-11e4-b396-002590a15da7
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd
P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXwR1
LxsNXVBSFQF4ABgL BhkUUB88cABYeX95 e0RnX25aWkVlcE56
XU8aVmQHEWAeCWkf V0VZcAUacgRLdhkL P1R+ViJbM2MaYnNm
FUpqZj1teD8EeXoQ GllXcANKSB9WEjdj USMoPA1nEVcMSTkG
ZzcGB3U/OGE6EXkT FHYfdGg5HS5aT0Vm BUxTDSlFb1BJWzos
EB8SU1QZFXVXTCZa DVUzOhJOHl4aRyxE BU8NQhdHBjNdUTNB
VDdaVGUxDV0kTwAA
X-Authentic-SMTP: 61633532353630.1023:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 75.119.251.161/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Score: -0.5 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 UC_GIBBERISH_OBFU Multiple instances of "word VERYLONGGIBBERISH
word"
X-Headers-End: 1XZJd0-00024A-V3
Subject: [Bitcoin-development] [BIP draft] CHECKLOCKTIMEVERIFY - Prevent a
txout from being spent until an expiration time
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 01 Oct 2014 13:07:42 -0000
--uwB7x3tnyrZQfZJI
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
I've written a reference implementation and BIP draft for a new opcode,
CHECKLOCKTIMEVERIFY. The BIP, reproduced below, can be found at:
https://github.com/petertodd/bips/blob/checklocktimeverify/bip-checkloc=
ktimeverify.mediawiki
The reference implementation, including a full-set of unittests for the
opcode semantics can be found at:
https://github.com/petertodd/bitcoin/compare/checklocktimeverify
<pre>
BIP:
Title: OP_CHECKLOCKTIMEVERIFY
Author: Peter Todd <pete@petertodd.org>
Status: Draft
Type: Standards Track
Created: 2014-10-01
</pre>
=3D=3DAbstract=3D=3D
This BIP describes a new opcode (OP_CHECKLOCKTIMEVERIFY) for the Bitcoin
scripting system that allows a transaction output to be made unspendable un=
til
some point in the future.
=3D=3DSummary=3D=3D
CHECKLOCKTIMEVERIFY re-defines the existing NOP2 opcode. When executed it
compares the top item on the stack to the nLockTime field of the transaction
containing the scriptSig. If that top stack item is greater than the transa=
tion
nLockTime the script fails immediately, otherwise script evaluation continu=
es
as though a NOP was executed.
The nLockTime field in a transaction prevents the transaction from being mi=
ned
until either a certain block height, or block time, has been reached. By
comparing the argument to CHECKLOCKTIMEVERIFY against the nLockTime field, =
we
indirectly verify that the desired block height or block time has been reac=
hed;
until that block height or block time has been reached the transaction outp=
ut
remains unspendable.
=3D=3DMotivation=3D=3D
The nLockTime field in transactions makes it possible to prove that a
transaction output can be spent in the future: a valid signature for a
transaction with the desired nLockTime can be constructed, proving that it =
is
possible to spend the output with that signature when the nLockTime is reac=
hed.
An example where this technique is used is in micro-payment channels, where=
the
nLockTime field proves that should the receiver vanish the sender is guaran=
teed
to get all their escrowed funds back when the nLockTime is reached.
However the nLockTime field is insufficient if you wish to prove that
transaction output ''can-not'' be spent until some time in the future, as t=
here
is no way to prove that the secret keys corresponding to the pubkeys contro=
ling
the funds have not been used to create a valid signature.
=3D=3D=3DEscrow=3D=3D=3D
If Alice and Bob jointly operate a business they may want to
ensure that all funds are kept in 2-of-2 multisig transaction outputs that
require the co-operation of both parties to spend. However, they recognise =
that
in exceptional circumstances such as either party getting "hit by a bus" th=
ey
need a backup plan to retrieve the funds. So they appoint their lawyer, Len=
ny,
to act as a third-party.
With a standard 2-of-3 CHECKMULTISIG at any time Lenny could conspire with
either Alice or Bob to steal the funds illegitimately. Equally Lenny may pr=
efer
not to have immediate access to the funds to discourage bad actors from
attempting to get the secret keys from him by force.
However with CHECKLOCKTIMEVERIFY the funds can be stored in scriptPubKeys of
the form:
IF
<now + 3 months> CHECKLOCKTIMEVERIFY DROP
<Lenny's pubkey> CHECKSIGVERIFY
1
ELSE
2
ENDIF
<Alice's pubkey> <Bob's pubkey> 2 CHECKMULTISIG
At any time the funds can be spent with the following scriptSig:
<Alice's signature> <Bob's signature> 0
After 3 months have passed Lenny and one of either Alice or Bob can spend t=
he
funds with the following scriptSig:
<Alice/Bob's signature> <Lenny's signature> 1
=3D=3D=3DNon-interactive time-locked refunds=3D=3D=3D
There exist a number of protocols where a transaction output is created that
the co-operation of both parties to spend the output. To ensure the failure=
of
one party does not result in the funds becoming lost refund transactions are
setup in advance using nLockTime. These refund transactions need to be crea=
ted
interactively, and additionaly, are currently vulnerable to transaction
mutability. CHECKLOCKTIMEVERIFY can be used in these protocols, replacing t=
he
interactive setup with a non-interactive setup, and additionally, making
transaction mutability a non-issue.
=3D=3D=3D=3DTwo-factor wallets=3D=3D=3D=3D
Services like GreenAddress store Bitcoins with 2-of-2 multisig scriptPubKey=
's
such that one keypair is controlled by the user, and the other keypair is
controlled by the service. To spend funds the user uses locally installed
wallet software that generates one of the required signatures, and then use=
s a
2nd-factor authentication method to authorize the service to create the sec=
ond
SIGHASH_NONE signature that is locked until some time in the future and sen=
ds
the user that signature for storage. If the user needs to spend their funds=
and
the service is not available, they wait until the nLockTime expires.
The problem is there exist numerous occasions the user will not have a valid
signature for some or all of their transaction outputs. With
CHECKLOCKTIMEVERIFY rather than creating refund signatures on demand
scriptPubKeys of the following form are used instead:
IF
<service pubkey> CHECKSIGVERIFY
ELSE
<expiry time> CHECKLOCKTIMEVERIFY DROP
ENDIF
<user pubkey> CHECKSIG
Now the user is always able to spend their funds without the co-operation of
the service by waiting for the expiry time to be reached.
=3D=3D=3D=3DMicropayment Channels=3D=3D=3D=3D
Jeremy Spilman style micropayment channels first setup a deposit controlled=
by
2-of-2 multisig, tx1, and then adjust a second transaction, tx2, that spends
the output of tx1 to payor and payee. Prior to publishing tx1 a refund
transaction is created, tx3, to ensure that should the payee vanish the pay=
or
can get their deposit back. The process by which the refund transaction is
created is currently vulnerable to transaction mutability attacks, and
additionally, requires the payor to store the refund. Using the same
scriptPubKey from as in the Two-factor wallets example solves both these is=
sues.
=3D=3D=3DTrustless Payments for Publishing Data=3D=3D=3D
The PayPub protocol makes it possible to pay for information in a trustless=
way
by first proving that an encrypted file contains the desired data, and seco=
ndly
crafting scriptPubKeys used for payment such that spending them reveals the
encryption keys to the data. However the existing implementation has a
significant flaw: the publisher can delay the release of the keys indefinit=
ely.
This problem can be solved interactively with the refund transaction techni=
que;
with CHECKLOCKTIMEVERIFY the problem can be non-interactively solved using
scriptPubKeys of the following form:
IF
HASH160 <Hash160(encryption key)> EQUALVERIFY
<publisher pubkey> CHECKSIG
ELSE
<expiry time> CHECKLOCKTIMEVERIFY DROP
<buyer pubkey> CHECKSIG
ENDIF
The buyer of the data is now making a secure offer with an expiry time. If =
the
publisher fails to accept the offer before the expiry time is reached the b=
uyer
can cancel the offer by spending the output.
=3D=3D=3DProving sacrifice to miners' fees=3D=3D=3D
Proving the sacrifice of some limited resource is a common technique in a
variety of cryptographic protocols. Proving sacrifices of coins to mining f=
ees
has been proposed as a ''universal public good'' to which the sacrifice cou=
ld
be directed, rather than simply destroying the coins. However doing so is
non-trivial, and even the best existing technqiue - announce-commit sacrifi=
ces
- could encourage mining centralization. CHECKLOCKTIMEVERIFY can be used to
create outputs that are provably spendable by anyone (thus to mining fees
assuming miners behave optimally and rationally) but only at a time
sufficiently far into the future that large miners profitably can't sell the
sacrifices at a discount.
=3D=3D=3DReplacing the nLockTime field entirely=3D=3D=3D
As an aside, note how if the SignatureHash() algorithm could optionally cov=
er
part of the scriptSig the signature could require that the scriptSig contain
CHECKLOCKTIMEVERIFY opcodes, and additionally, require that they be execute=
d.
(the CODESEPARATOR opcode came very close to making this possible in v0.1 of
Bitcoin) This per-signature capability could replace the per-transaction
nLockTime field entirely as a valid signature would now be the proof that a
transaction output ''can'' be spent.
=3D=3DDetailed Specification=3D=3D
Refer to the reference implementation, reproduced below, for the precise
semantics and detailed rationale for those semantics.
case OP_NOP2:
{
// CHECKLOCKTIMEVERIFY
//
// (nLockTime -- nLockTime )
=20
if (!(flags & SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY))
break; // not enabled; treat as a NOP
=20
if (stack.size() < 1)
return false;
=20
// Note that elsewhere numeric opcodes are limited to
// operands in the range -2**31+1 to 2**31-1, however it is
// legal for opcodes to produce results exceeding that
// range. This limitation is implemented by CScriptNum's
// default 4-byte limit.
//
// If we kept to that limit we'd have a year 2038 problem,
// even though the nLockTime field in transactions
// themselves is uint32 which only becomes meaningless
// after the year 2106.
//
// Thus as a special case we tell CScriptNum to accept up
// to 5-byte bignums, which are good until 2**32-1, the
// same limit as the nLockTime field itself.
const CScriptNum nLockTime(stacktop(-1), 5);
=20
// In the rare event that the argument may be < 0 due to
// some arithmetic being done first, you can always use
// 0 MAX CHECKLOCKTIMEVERIFY.
if (nLockTime < 0)
return false;
=20
// There are two times of nLockTime: lock-by-blockheight
// and lock-by-blocktime, distinguished by whether
// nLockTime < LOCKTIME_THRESHOLD.
//
// We want to compare apples to apples, so fail the script
// unless the type of nLockTime being tested is the same as
// the nLockTime in the transaction.
if (!(
(txTo.nLockTime < LOCKTIME_THRESHOLD && nLockTime < LOCKTIM=
E_THRESHOLD) ||
(txTo.nLockTime >=3D LOCKTIME_THRESHOLD && nLockTime >=3D LOC=
KTIME_THRESHOLD)
))
return false;
=20
// Now that we know we're comparing apples-to-apples, the
// comparison is a simple numeric one.
if (nLockTime > (int64_t)txTo.nLockTime)
return false;
=20
// Finally the nLockTime feature can be disabled and thus
// CHECKLOCKTIMEVERIFY bypassed if every txin has been
// finalized by setting nSequence to maxint. The
// transaction would be allowed into the blockchain, making
// the opcode ineffective.
//
// Testing if this vin is not final is sufficient to
// prevent this condition. Alternatively we could test all
// inputs, but testing just this input minimizes the data
// required to prove correct CHECKLOCKTIMEVERIFY execution.
if (txTo.vin[nIn].IsFinal())
return false;
=20
break;
=20
}
https://github.com/petertodd/bitcoin/commit/ab0f54f38e08ee1e50ff72f801680ee=
84d0f1bf4
=3D=3DUpgrade and Testing Plan=3D=3D
TBD
=3D=3DCredits=3D=3D
Thanks goes to Gregory Maxwell for suggesting that the argument be compared
against the per-transaction nLockTime, rather than the current block height=
and
time.
=3D=3DReferences=3D=3D
PayPub - https://github.com/unsystem/paypub
Jeremy Spilman Micropayment Channels - http://www.mail-archive.com/bitcoin-=
development%40lists.sourceforge.net/msg02028.html
=3D=3DCopyright=3D=3D
This document is placed in the public domain.
--=20
'peter'[:-1]@petertodd.org
000000000000000009012f16fe9db21abbba5025453a9b7b589a807b21cec318
--uwB7x3tnyrZQfZJI
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQGrBAEBCACVBQJUK/zEXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAxNWE5ZTBmZmMxODI4ODA2OTVhZGJkNjM2YTk3OTkzOGFi
ZTQ3NDA1ZGU2ZDM4MmUvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkftDyQf8CbG3yaZE/Eryvm4Zrvfx8uAF
2SzU+tcTXRYgpufsC0vcYK5499UHmaYn8a6fhGrrnADtZxIPMlK7BZYAQCoPsZyK
om1NgN0yvxqlTBVHNy3y9UIMm4tSE5558L5CTlD27s4uImvfLGUywFggmSNXL1/y
z3Dizw5zUUSJtreDoB/36jrXxBPOPi8QZEh8nD7G3JeoovWIUBoYROvZG+nGZrx2
IWLaOZ81daQq3gB6AIi/Oso6nBLJyL3jRqcMMtyP/QTJDVK2XAtDN6rAb0KFQCDt
Z3PLIURp6JkxxoFbLXnfPvDohJAoePxD8WaVpZwwEq2d9wOs0fvNA3mD44s2Gg==
=77sD
-----END PGP SIGNATURE-----
--uwB7x3tnyrZQfZJI--
|