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
|
<pre>
BIP: 68
Title: Consensus-enforced transaction replacement signaled via sequence numbers (relative lock-time)
Author: Mark Friedenbach <mark@friedenbach.org>
BtcDrak <btcdrak@gmail.com>
Nicolas Dorier <nicolas.dorier@gmail.com>
kinoshitajona <kinoshitajona@gmail.com>
Status: Draft
Type: Standards Track
Created: 2015-05-28
</pre>
==Abstract==
This BIP introduces consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding outpoint, for the purpose of supporting consensus-enforced transaction replacement features.
==Motivation==
Bitcoin transactions have a sequence number field for each input. The original idea appears to have been that a transaction in the mempool would be replaced by using the same input with a higher sequence value. Although this was not properly implemented, it assumes miners would prefer higher sequence numbers even if the lower ones were more profitable to mine. However, a miner acting on profit motives alone would break that assumption completely. The change described by this BIP repurposes the sequence number for new use cases without breaking existing functionality. It also leaves room for future expansion and other use cases.
The transaction nLockTime is used to prevent the mining of a transaction until a certain date. (in block height or time)
nSequence will be repurposed to prevent mining of a transaction until a certain age of the spent output. (in blocks or timespan)
This, among other uses, allows bi-directional payment channels as used in [Hashed Timelock Contracts (HTLCs)](https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf) and [BIP112](https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki#Bidirectional_Payment_Channels).
==Specification==
This specification defines the meaning of sequence numbers for transactions with an nVersion greater than or equal to 2 for which the rest of this specification relies on.
If bit (1 << 31) of the sequence number is set, then no consensus meaning is applied to the sequence number and can be included in any block under all currently possible circumstances.
If bit (1 << 31) of the sequence number is not set, then the sequence number is interpreted as an encoded relative lock-time.
The sequence number encoding is interpreted as follows:
Bit (1 << 22) determines if the relative lock-time is time-based or block based: If the bit is set, it specifies relative lock-time in units of 512 seconds granularity from the median time past of its previous block to the block-time Median Time Past or nTime depending on the enforcement status of BIP113. If the bit is not set, it specifies relative lock-time in blocks.
Note (1 << 22) was chosen because it is the highest you can go without moving to 4-byte pushes when using the Bitcoin scripting language in conjunction with OP_CHECKSEQUENCEVERIFY: i.e. 3 bytes = 24 bits where pushes are signed integers which leaving 1 bit for the flag and 22 bits for the relative lock-time encoding.
This specification only interprets 16 bits of the sequence number as relative lock-time, so a mask of 0x0000ffff MUST be applied to the sequence field to extract the relative lock-time. This is to allow for future expansion. The specification allows for a year of relative lock-time.
For time based relative lock-time, 512 second granularity was chosen because bitcoin blocks are generated every 600 seconds. So when using block based or time based relative lock-time, the same amount of time can be encoded with the available number of bits. Converting from a sequence number to seconds is performed by multiplying by 512 = 2^9, or equivalently shifting up by 9 bits.
When the relative lock-time is time-based, it is interpreted as a minimum block-time constraint over the input's age. A relative time-based lock-time of zero indicates an input which can be included in any block. More generally, a relative time-based lock-time n can be included into any block produced 512 * n seconds after the mining date of the output it is spending, or any block thereafter.
The mining date of the output is equals to the Median Time Past of the previous block which mined it.
The block produced time is either equals to median time past of its parent or to its nTime field, depending on the state of BIP113 (MTP).
When the relative lock-time is block-based, it is interpreted as a minimum block-height constraint over the input's age. A relative block-based lock-time of zero indicates an input which can be included in any block. More generally, a relative block lock-time n can be included n blocks after the mining date of the output it is spending, or any block thereafter.
This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus and non-consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence valuenumber constraints are not satisfied and zero otherwise:
<pre>
enum {
/* Interpret sequence valuenumbers as relative lock-time constraints. */
LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
};
/* Setting nSequence to this value for every input in a transaction
* disables nLockTime. */
static const uint32_t SEQUENCE_FINAL = 0xffffffff;
/* If this flag set, CTxIn::nSequence is NOT interpreted as a
* relative lock-time. Setting the most significant bit of a
* sequence valuenumber disabled relative lock-time. */
static const uint32_t SEQUENCE_LOCKTIME_DISABLED_FLAG = (1 << 31);
/* If CTxIn::nSequence encodes a relative lock-time and this flag
* is set, the relative lock-time has units of 512 seconds,
* otherwise it specifies blocks with a granularity of 1. */
static const uint32_t SEQUENCE_LOCKTIME_SECONDS_FLAG = (1 << 22);
/* If CTxIn::nSequence encodes a relative lock-time, this mask is
* applied to extract that lock-time from the sequence field. */
static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff;
/* In order to use the same number of bits to encode roughly the
* same wall-clock duration, and because blocks are naturally
* limited to occur every 600s on average, the minimum granularity
* for time-based relative lock-time is fixed at 512 seconds.
* Converting from CTxIn::nSequence to seconds is performed by
* multiplying by 512 = 2^9, or equivalently shifting up by
* 9 bits. */
static const int SEQUENCE_LOCKTIME_GRANULARITY = 9;
int64_t LockTime(const CTransaction &tx, int flags, const std::vector<int>* prevHeights, const CBlockIndex& block)
{
assert(prevHeights == NULL || prevHeights->size() == tx.vin.size());
int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST)
? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast()
: block.GetBlockTime();
bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2
&& flags & LOCKTIME_VERIFY_SEQUENCE;
// Will be set to the equivalent height- and time-based nLockTime
// values that would be necessary to satisfy all relative lock-
// time constraints given our view of block chain history.
int nMinHeight = 0;
int64_t nMinTime = 0;
// Will remain equal to true if all inputs are finalized
// (CTxIn::SEQUENCE_FINAL).
bool fFinalized = true;
for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
const CTxIn& txin = tx.vin[txinIndex];
// Set a flag if we witness an input that isn't finalized.
if (txin.nSequence == CTxIn::SEQUENCE_FINAL)
continue;
else
fFinalized = false;
// Do not enforce sequence valuenumbers as a relative lock time
// unless we have been instructed to, and a view has been
// provided.
if (!fEnforceBIP68)
continue;
// Sequence valuenumbers with the most significant bit set are not
// treated as relative lock-times, nor are they given any
// consensus-enforced meaning at this point.
if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLED_FLAG)
continue;
if (prevHeights == NULL)
continue;
int nCoinHeight = (*prevHeights)[txinIndex];
if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_SECONDS_FLAG) {
int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast();
// Time-based relative lock-times are measured from the
// smallest allowed timestamp of the block containing the
// txout being spent, which is the median time past of the
// block prior.
nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1);
} else {
// We subtract 1 from relative lock-times because a lock-
// time of 0 has the semantics of "same block," so a lock-
// time of 1 should mean "next block," but nLockTime has
// the semantics of "last invalid block height."
nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1);
}
}
// If all sequence valuenumbers are CTxIn::SEQUENCE_FINAL, the
// transaction is considered final and nLockTime constraints
// are not enforced.
if (fFinalized)
return 0;
if ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD)
nMinHeight = std::max(nMinHeight, (int)tx.nLockTime);
else
nMinTime = std::max(nMinTime, (int64_t)tx.nLockTime);
if (nMinHeight >= block.nHeight)
return nMinHeight;
if (nMinTime >= nBlockTime)
return nMinTime;
return 0;
}</pre>
Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be updated as well, since the semantics of the return value has been inverted.
==Example: Bidirectional payment channel==
A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1 BTC output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network.
Alice desires to send Bob a payment of 0.1 BTC. She does so by constructing a transaction spending the 1 BTC output and sending 0.1 BTC to Bob and 0.9 BTC back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence valuenumber field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1 BTC, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2 BTC, then 0.3 BTC to Bob with a relative lock-time of 29 days from creation of the channel.
Bob now desires to send Alice a refund of 0.25 BTC. He does so by constructing a transaction spending the 1btc output and sending 0.95 BTC (= 0.7 BTC + 0.25 BTC) to Alice and 0.05 BTC to himself. Since Bob will still have in his logs the transaction giving him 0.7 BTC 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures.
Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by finalizing the input (nSequence = MAX_INT) and both parties signing.
==Implementation==
A reference implementation is provided by the following pull request
https://github.com/bitcoin/bitcoin/pull/6312
==Acknowledgments==
Credit goes to Gregory Maxwell for providing a succinct and clear description of the behavior of this change, which became the basis of this BIP text.
This BIP was edited by BtcDrak and Nicolas Dorier.
==Deployment==
This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). Exact details TDB.
It is recommended to deploy BIP68 and BIP112 at the same time as this BIP.
==Compatibility==
The only use of sequence valuenumbers by the Bitcoin Core reference client software is to disable checking the nLockTime constraints in a transaction. The semantics of that application are preserved by this BIP.
There may be other uses for the sequence valuenumber field that are not commonplace or yet to be discovered. To allow for other uses of the sequence valuenumber field, it is only interpreted as a relative lock-time as described in this BIP if the most significant bit is clear. This allows up to 31 bits of the sequence valuenumber field to be used for other purposes in applications which don't simultaneously need a per-input relative lock-time. In addition, the unused low-order bits of the relative lock-time encoding are available for use by future soft-fork extensions.
The most efficient way to calculate sequence valuenumber from relative lock-time is with bit masks and shifts:
<pre>
// 0 <= nHeight < 65,535 blocks (1.25 years)
nSequence = nHeight << 14;
nHeight = nSequence >> 14;
// 0 <= nTime < 33,554,431 seconds (1.06 years)
nSequence = 1<<30 | (nTime << 5);
nTime = (nSequence ^ 1<<30) >> 5;
</pre>
==References==
Bitcoin mailing list discussion: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html
BIP112: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki
BIP113: https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki
Hashed Timelock Contrats (HTLCs): https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf
|
