diff options
Diffstat (limited to 'bip-0112.mediawiki')
| -rw-r--r-- | bip-0112.mediawiki | 351 |
1 files changed, 252 insertions, 99 deletions
diff --git a/bip-0112.mediawiki b/bip-0112.mediawiki index c06caf5..e1a186f 100644 --- a/bip-0112.mediawiki +++ b/bip-0112.mediawiki @@ -2,7 +2,8 @@ BIP: 112 Title: CHECKSEQUENCEVERIFY Authors: BtcDrak <btcdrak@gmail.com> - Mark Friedenbach <mark@friedenbach.org> + Mark Friedenbach <mark@friedenbach.org> + Eric Lombrozo <elombrozo@gmail.com> Status: Draft Type: Standards Track Created: 2015-08-10 @@ -18,14 +19,15 @@ being spent. ==Summary== -CHECKSEQUENCEVERIFY redefines the existing NOP3 opcode. When executed -it compares the top item on the stack to the inverse of the nSequence -field of the transaction input containing the scriptSig. If the -inverse of nSequence is less than the sequence threshold (1 << 31), -the transaction version is greater than or equal to 2, and the top -item on the stack is less than or equal to the inverted nSequence, -script evaluation continues as though a NOP was executed. Otherwise -the script fails immediately. +CHECKSEQUENCEVERIFY redefines the existing NOP3 opcode. +When executed, the script interpreter continues as if a NOP was executed +so long as one of the following conditions is met: + + * the transaction's nVersion field is 0 or 1; + * the top item on the stack is a value greater than or equal to (1 << 31); or + * the top item on the stack and the transaction input's sequence number are both relative lock-times of the same units, and the relative lock-time represented by the sequence number is greater than or equal to the relative lock-time represented by the top item on the stack. + +Otherwise, script execution terminates with an error. BIP 68's redefinition of nSequence prevents a non-final transaction from being selected for inclusion in a block until the corresponding @@ -52,19 +54,194 @@ of applications in phased protocols such as escrow, payment channels, or bidirectional pegs. +===Contracts With Expiration Deadlines=== + +====Escrow with Timeout==== + +An escrow that times out automatically 30 days after being funded can be +established in the following way. Alice, Bob and Escrow create a 2-of-3 +address with the following redeemscript. + + IF + 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY + ELSE + "30d" CHECKSEQUENCEVERIFY DROP + <Alice's pubkey> CHECKSIGVERIFY + ENDIF + +At any time funds can be spent using signatures from any two of Alice, +Bob or the Escrow. + +After 30 days Alice can sign alone. + +The clock does not start ticking until the payment to the escrow address +confirms. + + +===Retroactive Invalidation=== + +In many instances, we would like to create contracts that can be revoked in case +of some future event. However, given the immutable nature of the blockchain, it +is practically impossible to retroactively invalidate a previous commitment that +has already confirmed. The only mechanism we really have for retroactive +invalidation is blockchain reorganization which, for fundamental security +reasons, is designed to be very hard and very expensive to deliberately pull off. + +Despite this limitation, we do have a way to provide something functionally similar +using CHECKSEQUENCEVERIFY. By constructing scripts with multiple branches of +execution where one or more of the branches are delayed we provide +a time window in which someone can supply an invalidation condition that allows the +output to be spent, effectively invalidating the would-be delayed branch and potentially discouraging +another party from broadcasting the transaction in the first place. If the invalidation +condition does not occur before the timeout, the delayed branch becomes spendable, +honoring the original contract. + +Some more specific applications of this idea: + +====Hash Time-Locked Contracts==== + +Hash Time-Locked Contracts (HTLCs) provide a general mechanism for offchain contract negotiation. An execution pathway can be made to require knowledge of a secret (a hash preimage) that can be presented within an invalidation time window. By sharing the secret it is possible to guarantee to the counterparty that the transaction will never be broadcast since this would allow the counterparty to claim the output immediately while one would have to wait for the time window to pass. If the secret has not been shared, the counterparty will be unable to use the instant pathway and the delayed pathway must be used instead. + +====Bidirectional Payment Channels==== + +Scriptable relative locktime provides a predictable amount of time to respond in +the event a counterparty broadcasts a revoked transaction: Absolute locktime +necessitates closing the channel and reopen it when getting close to the timeout, +whereas with relative locktime, the clock starts ticking the moment the +transactions confirms in a block. It also provides a means to know exactly how +long to wait (in number of blocks) before funds can be pulled out of the channel +in the event of a noncooperative counterparty. + + +====Lightning Network==== + +The lightning network extends the bidirectional payment channel idea to allow for payments to be routed over multiple bidirectional payment channel hops. + +These channels are based on an anchor transaction that requires a 2-of-2 +multisig from Alice and Bob, and a series of revocable commitment +transactions that spend the anchor transaction. The commitment +transaction splits the funds from the anchor between Alice and Bob and +the latest commitment transaction may be published by either party at +any time, finalising the channel. + +Ideally then, a revoked commitment transaction would never be able to +be successfully spent; and the latest commitment transaction would be +able to be spent very quickly. + +To allow a commitment transaction to be effectively revoked, Alice +and Bob have slightly different versions of the latest commitment +transaction. In Alice's version, any outputs in the commitment +transaction that pay Alice also include a forced delay, and an +alternative branch that allows Bob to spend the output if he knows that +transaction's revocation code. In Bob's version, payments to Bob are +similarly encumbered. When Alice and Bob negotiate new balances and +new commitment transactions, they also reveal the old revocation code, +thus committing to not relaying the old transaction. + +A simple output, paying to Alice might then look like: + + HASH160 <revokehash> EQUAL + IF + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + "24h" CHECKSEQUENCEVERIFY + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ENDIF + +This allows Alice to publish the latest commitment transaction at any +time and spend the funds after 24 hours, but also ensures that if Alice +relays a revoked transaction, that Bob has 24 hours to claim the funds. + +With CHECKLOCKTIMEVERIFY, this would look like: + + HASH160 <revokehash> EQUAL + IF + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + "2015/12/15" CHECKLOCKTIMEVERIFY + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ENDIF + +This form of transaction would mean that if the anchor is unspent on +2015/12/16, Alice can use this commitment even if it has been revoked, +simply by spending it immediately, giving no time for Bob to claim it. + +Ths means that the channel has a deadline that cannot be pushed +back without hitting the blockchain; and also that funds may not be +available until the deadline is hit. CHECKSEQUENCEVERIFY allows you +to avoid making such a tradeoff. + +Hashed Time-Lock Contracts (HTLCs) make this slightly more complicated, +since in principle they may pay either Alice or Bob, depending on whether +Alice discovers a secret R, or a timeout is reached, but the same principle +applies -- the branch paying Alice in Alice's commitment transaction gets a +delay, and the entire output can be claimed by the other party if the +revocation secret is known. With CHECKSEQUENCEVERIFY, a HTLC payable to +Alice might look like the following in Alice's commitment transaction: + + HASH160 DUP <revokehash> EQUAL + IF + DROP DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + <R hash> EQUAL + IF + "24h" CHECKSEQUENCEVERIFY DROP + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ENDIF + ENDIF + +and correspondingly in Bob's commitment transaction: + + HASH160 DUP <revokehash> EQUAL + IF + DROP DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + <R hash> EQUAL + IF + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + "24h" CHECKSEQUENCEVERIFY DROP + "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ENDIF + ENDIF + +Note that both CHECKSEQUENCEVERIFY and CHECKLOCKTIMEVERIFY are used in the +final branch of above to ensure Bob cannot spend the output until after both +the timeout is complete and Alice has had time to reveal the revocation +secret. + +See the [https://github.com/ElementsProject/lightning/blob/master/doc/deployable-lightning.pdf Deployable Lightning] paper. + + +====2-Way Pegged Sidechains==== + +The 2-way pegged sidechain requires a new REORGPROOFVERIFY opcode, the semantics of which are outside the scope of this BIP. CHECKSEQUENCEVERIFY is used to make sure that sufficient time has passed since the return peg was posted to publish a reorg proof: + + IF + lockTxHeight <lockTxHash> nlocktxOut [<workAmount>] reorgBounty Hash160(<...>) <genesisHash> REORGPROOFVERIFY + ELSE + withdrawLockTime CHECKSEQUENCEVERIFY DROP HASH160 p2shWithdrawDest EQUAL + ENDIF + + ==Specification== Refer to the reference implementation, reproduced below, for the precise semantics and detailed rationale for those semantics. - // Threshold for nLockTime: below this value it is interpreted as block number, - // otherwise as UNIX timestamp (already defined in Bitcoin Core). - static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC + /* Threshold for nSequence: below this value it is interpreted + * as a relative lock-time, otherwise ignored. */ + static const uint32_t SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31); - // Threshold for inverted nSequence: below this value it is interpreted - // as a relative lock-time, otherwise ignored. - static const uint32_t SEQUENCE_THRESHOLD = (1 << 31); + /* Threshold for nSequence when interpreted as a relative + * lock-time: below this value it has units of blocks, otherwise + * seconds. */ + static const uint32_t SEQUENCE_UNITS_THRESHOLD = (1 << 30); case OP_NOP3: { @@ -79,123 +256,94 @@ semantics and detailed rationale for those semantics. if (stack.size() < 1) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); - // Note that unlike CHECKLOCKTIMEVERIFY we do not need to - // accept 5-byte bignums since any value greater than or - // equal to SEQUENCE_THRESHOLD (= 1 << 31) will be rejected - // anyway. This limitation just happens to coincide with - // CScriptNum's default 4-byte limit with an explicit sign - // bit. + // 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. // - // This means there is a maximum relative lock time of 52 - // years, even though the nSequence field in transactions - // themselves is uint32_t and could allow a relative lock - // time of up to 120 years. - const CScriptNum nInvSequence(stacktop(-1), fRequireMinimal); + // Thus as a special case we tell CScriptNum to accept up + // to 5-byte bignums, which are good until 2**39-1, well + // beyond the 2**32-1 limit of the nSequence field itself. + const CScriptNum nSequence(stacktop(-1), fRequireMinimal, 5); // In the rare event that the argument may be < 0 due to // some arithmetic being done first, you can always use // 0 MAX CHECKSEQUENCEVERIFY. - if (nInvSequence < 0) + if (nSequence < 0) return set_error(serror, SCRIPT_ERR_NEGATIVE_LOCKTIME); - // Actually compare the specified inverse sequence number - // with the input. - if (!CheckSequence(nInvSequence)) + // To provide for future soft-fork extensibility, if the + // operand is too large to be treated as a relative lock- + // time, CHECKSEQUENCEVERIFY behaves as a NOP. + if (nSequence >= SEQUENCE_LOCKTIME_THRESHOLD) + break; + + // Actually compare the specified sequence number with the input. + if (!checker.CheckSequence(nSequence)) return set_error(serror, SCRIPT_ERR_UNSATISFIED_LOCKTIME); break; } - bool CheckSequence(const CScriptNum& nInvSequence) const + bool TransactionSignatureChecker::CheckSequence(const CScriptNum& nSequence) const { - int64_t txToInvSequence; + // Relative lock times are supported by comparing the passed + // in operand to the sequence number of the input. + const int64_t txToSequence = (int64_t)txTo->vin[nIn].nSequence; - // Fail under all circumstances if the transaction's version - // number is not set high enough to enable enforced sequence - // number rules. - if (txTo->nVersion < 2) + // Fail if the transaction's version number is not set high + // enough to trigger BIP 68 rules. + if (static_cast<uint32_t>(txTo->nVersion) < 2) return false; - // Sequence number must be inverted to convert it into a - // relative lock-time. - txToInvSequence = (int64_t)~txTo->vin[nIn].nSequence; - - // Sequence numbers under SEQUENCE_THRESHOLD are not consensus - // constrained. - if (txToInvSequence >= SEQUENCE_THRESHOLD) + // Sequence numbers above SEQUENCE_LOCKTIME_THRESHOLD + // are not consensus constrained. Testing that the transaction's + // sequence number is not above this threshold prevents + // using this property to get around a CHECKSEQUENCEVERIFY + // check. + if (txToSequence >= SEQUENCE_LOCKTIME_THRESHOLD) return false; - // There are two types of relative lock-time: lock-by- - // blockheight and lock-by-blocktime, distinguished by - // whether txToInvSequence < LOCKTIME_THRESHOLD. + // There are two kinds of nSequence: lock-by-blockheight + // and lock-by-blocktime, distinguished by whether + // nSequence < SEQUENCE_UNITS_THRESHOLD. // // We want to compare apples to apples, so fail the script - // unless the type of lock-time being tested is the same as - // the lock-time in the transaction input. + // unless the type of nSequence being tested is the same as + // the nSequence in the transaction. if (!( - (txToInvSequence < LOCKTIME_THRESHOLD && nInvSequence < LOCKTIME_THRESHOLD) || - (txToInvSequence >= LOCKTIME_THRESHOLD && nInvSequence >= LOCKTIME_THRESHOLD) + (txToSequence < SEQUENCE_UNITS_THRESHOLD && nSequence < SEQUENCE_UNITS_THRESHOLD) || + (txToSequence >= SEQUENCE_UNITS_THRESHOLD && nSequence >= SEQUENCE_UNITS_THRESHOLD) )) return false; // Now that we know we're comparing apples-to-apples, the // comparison is a simple numeric one. - if (nInvSequence > txToInvSequence) + if (txTo->vin[nIn].nSequence > txToSequence) return false; return true; } -https://github.com/maaku/bitcoin/commit/33be476a60fcc2afbe6be0ca7b93a84209173eb2 - - -==Example: Escrow with Timeout== - -An escrow that times out automatically 30 days after being funded can be -established in the following way. Alice, Bob and Escrow create a 2-of-3 -address with the following redeemscript. - - IF - 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY - ELSE - <LOCKTIME_THRESHOLD + 30*24*60*60> CHECKSEQUENCEVERIFY DROP - <Alice's pubkey> CHECKSIGVERIFY - ENDIF - -At any time funds can be spent using signatures from any two of Alice, -Bob or the Escrow. - -After 30 days Alice can sign alone. - -The clock does not start ticking until the payment to the escrow address -confirms. - ==Reference Implementation== -A reference implementation is provided in the following git repository: +A reference implementation is provided by the following pull request: -https://github.com/maaku/bitcoin/tree/checksequenceverify +https://github.com/bitcoin/bitcoin/pull/6564 ==Deployment== We reuse the double-threshold switchover mechanism from BIPs 34 and -66, with the same thresholds, but for nVersion = 8. The new rules are -in effect for every block (at height H) with nVersion = 8 and at least +66, with the same thresholds, but for nVersion = 4. The new rules are +in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also -have nVersion = 8. Furthermore, when 950 out of the 1000 blocks -preceding a block do have nVersion = 8, nVersion = 3 blocks become +have nVersion = 4. Furthermore, when 950 out of the 1000 blocks +preceding a block do have nVersion = 4, nVersion = 3 blocks become invalid, and all further blocks enforce the new rules. -When assessing the block version as mask of ~0x20000007 must be applied -to work around the complications caused by -[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010396.html BIP101's premature use] -of the [https://gist.github.com/sipa/bf69659f43e763540550 undecided version bits proposal]. - -By applying ~0x20000007 with nVersion = 8, the thresholds should be tested -comparing block nVersion >= 4 as this will save a bit for future use. - It is recommended that this soft-fork deployment trigger include other related proposals for improving Bitcoin's lock-time capabilities, including: @@ -219,28 +367,33 @@ done by Peter Todd for the closely related BIP 65. BtcDrak authored this BIP document. +Thanks to Eric Lombrozo and Anthony Towns for contributing example usecases. + ==References== -BIP 68: Consensus-enforced transaction replacement signalled via -sequence numbers -https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68] Consensus-enforced transaction replacement signalled via sequence numbers + +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65] OP_CHECKLOCKTIMEVERIFY + +[https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113] Median past block time for time-lock constraints -BIP 65: OP_CHECKLOCKTIMEVERIFY -https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki +[http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-July/000021.html HTLCs using OP_CHECKSEQUENCEVERIFY/OP_LOCKTIMEVERIFY and revocation hashes] -BIP 113: Median past block time for time-lock constraints -https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki +[http://lightning.network/lightning-network-paper.pdf Lightning Network] -HTLCs using OP_CHECKSEQUENCEVERIFY/OP_LOCKTIMEVERIFY and -revocation hashes -http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-July/000021.html +[https://github.com/ElementsProject/lightning/blob/master/doc/deployable-lightning.pdf Deployable Lightning] + +[http://diyhpl.us/diyhpluswiki/transcripts/sf-bitcoin-meetup/2015-02-23-scaling-bitcoin-to-billions-of-transactions-per-day/ Scaling Bitcoin to Billions of Transactions Per Day] [http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010396.html Softfork deployment considerations] [https://gist.github.com/sipa/bf69659f43e763540550 Version bits] +[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html Jeremy Spilman Micropayment Channels] + ==Copyright== This document is placed in the public domain. + |