mirror of https://github.com/zcash/zips.git
246 lines
19 KiB
HTML
246 lines
19 KiB
HTML
<!DOCTYPE html>
|
||
<html>
|
||
<head>
|
||
<title>ZIP 68: Relative lock-time using consensus-enforced sequence numbers</title>
|
||
<meta charset="utf-8" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1"><link rel="stylesheet" href="css/style.css"></head>
|
||
<body>
|
||
<section>
|
||
<pre>ZIP: 68
|
||
Title: Relative lock-time using consensus-enforced sequence numbers
|
||
Credits: Mark Friedenbach <mark@friedenbach.org>
|
||
BtcDrak <btcdrak@gmail.com>
|
||
Nicolas Dorier <nicolas.dorier@gmail.com>
|
||
kinoshitajona <kinoshitajona@gmail.com>
|
||
Category: Consensus
|
||
Status: Draft
|
||
Created: 2016-06-06</pre>
|
||
<section id="terminology"><h2><span class="section-heading">Terminology</span><span class="section-anchor"> <a rel="bookmark" href="#terminology"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>The key words "MUST" and "MAY" in this document are to be interpreted as described in RFC 2119. <a id="footnote-reference-1" class="footnote_reference" href="#rfc2119">1</a></p>
|
||
<p>The "Median Time Past" of a block in this document is to be interpreted as described in <a id="footnote-reference-2" class="footnote_reference" href="#zip-0113">4</a>.</p>
|
||
</section>
|
||
<section id="abstract"><h2><span class="section-heading">Abstract</span><span class="section-anchor"> <a rel="bookmark" href="#abstract"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>This ZIP introduces relative lock-time (RLT) 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.</p>
|
||
</section>
|
||
<section id="motivation"><h2><span class="section-heading">Motivation</span><span class="section-anchor"> <a rel="bookmark" href="#motivation"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>Zcash transactions have a sequence number field for each input, inherited from Bitcoin. The original idea in Bitcoin 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 ZIP repurposes the sequence number for new use cases without breaking existing functionality. It also leaves room for future expansion and other use cases.</p>
|
||
<p>The transaction <code>nLockTime</code> is used to prevent the mining of a transaction until a certain date. <code>nSequence</code> 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 <a id="footnote-reference-3" class="footnote_reference" href="#deployable-lightning">5</a> and <a id="footnote-reference-4" class="footnote_reference" href="#zip-0112">3</a>.</p>
|
||
</section>
|
||
<section id="specification"><h2><span class="section-heading">Specification</span><span class="section-anchor"> <a rel="bookmark" href="#specification"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>This specification defines the meaning of sequence numbers for transactions in blocks after this proposal has activated.</p>
|
||
<p>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.</p>
|
||
<p>If bit (1 << 31) of the sequence number is not set, then the sequence number is interpreted as an encoded relative lock-time.</p>
|
||
<p>The sequence number encoding MUST be interpreted as follows:</p>
|
||
<p>Bit (1 << 22) determines if the relative lock-time is time-based or block based: If the bit is set, the relative lock-time specifies a timespan in units of 32 seconds granularity. The timespan starts from the Median Time Past of the output’s previous block, and ends at the Median Time Past of the previous block. If the bit is not set, the relative lock-time specifies a number of blocks.</p>
|
||
<p>Note: the 64-second time unit differs from Bitcoin's BIP 68, which uses a 512-second time unit.</p>
|
||
<p>The flag (1 << 22) is the highest order bit in a 3-byte signed integer for use in Zcash scripts as a 3-byte <code>PUSHDATA</code> with <code>OP_CHECKSEQUENCEVERIFY</code> <a id="footnote-reference-5" class="footnote_reference" href="#zip-0112">3</a>.</p>
|
||
<p>This specification only interprets 22 bits of the sequence number as relative lock-time, so a mask of <code>0x003FFFFF</code> MUST be applied to the sequence field to extract the relative lock-time. The 22-bit specification allows for over 8.5 years of relative lock-time.</p>
|
||
<figure class="align-center" align="center">
|
||
<img src="assets/images/zip-0068-encoding.png" alt="" />
|
||
<figcaption>A 32-bit field with 'Disable Flag' at bit (1 << 31), 'Type Flag' at bit (1 << 22), and 'Value' in the low 22 bits.</figcaption>
|
||
</figure>
|
||
<p>For time-based relative lock-time, 64-second granularity was chosen because the block target spacing for Zcash, after activation of the Blossom network upgrade, is 75 seconds. So when using block-based or time-based, roughly 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 64.</p>
|
||
<p>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 64 * n seconds after the mining date of the output it is spending, or any block thereafter. The mining date of the output is equal to the Median Time Past of the previous block that mined it.</p>
|
||
<p>The block produced time is equal to the Median Time Past of its previous block.</p>
|
||
<p>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 that can be included in any block. More generally, a relative block lock-time n MAY be included n blocks after the mining date of the output it is spending, or any block thereafter.</p>
|
||
<p>The new rules are not applied to the <code>nSequence</code> field of the input of the coinbase transaction.</p>
|
||
</section>
|
||
<section id="reference-implementation"><h2><span class="section-heading">Reference Implementation</span><span class="section-anchor"> <a rel="bookmark" href="#reference-implementation"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<!-- highlight::c++
|
||
enum {
|
||
/* Interpret sequence numbers 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;
|
||
/* Below flags apply in the context of ZIP 68. */
|
||
/* If this flag set, CTxIn::nSequence is NOT interpreted as a
|
||
* relative lock-time. */
|
||
static const uint32_t SEQUENCE_LOCKTIME_DISABLE_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_TYPE_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 = 0x003fffff;
|
||
/* 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 75s on average after Blossom activation,
|
||
* the minimum granularity for time-based relative lock-time is
|
||
* fixed at 64 seconds.
|
||
* Converting from CTxIn::nSequence to seconds is performed by
|
||
* multiplying by 64, or equivalently shifting up by 6 bits. */
|
||
static const int SEQUENCE_LOCKTIME_GRANULARITY = 6;
|
||
/**
|
||
* Calculates the block height and previous block's Median Time Past at
|
||
* which the transaction will be considered final in the context of ZIP 68.
|
||
* Also removes from the vector of input heights any entries which did not
|
||
* correspond to sequence locked inputs as they do not affect the calculation.
|
||
*/
|
||
static std::pair<int, int64_t> CalculateSequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
|
||
{
|
||
assert(prevHeights->size() == tx.vin.size());
|
||
// 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.
|
||
// The semantics of nLockTime are the last invalid height/time, so
|
||
// use -1 to have the effect of any height or time being valid.
|
||
int nMinHeight = -1;
|
||
int64_t nMinTime = -1;
|
||
// tx.nVersion is signed integer so requires cast to unsigned otherwise
|
||
// we would be doing a signed comparison and half the range of nVersion
|
||
// wouldn't support ZIP 68.
|
||
bool fEnforceZIP68 = static_cast<uint32_t>(tx.nVersion) >= 2
|
||
&& flags & LOCKTIME_VERIFY_SEQUENCE;
|
||
// Do not enforce sequence numbers as a relative lock time
|
||
// unless we have been instructed to
|
||
if (!fEnforceZIP68) {
|
||
return std::make_pair(nMinHeight, nMinTime);
|
||
}
|
||
for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
|
||
const CTxIn& txin = tx.vin[txinIndex];
|
||
// Sequence numbers 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_DISABLE_FLAG) {
|
||
// The height of this input is not relevant for sequence locks
|
||
(*prevHeights)[txinIndex] = 0;
|
||
continue;
|
||
}
|
||
int nCoinHeight = (*prevHeights)[txinIndex];
|
||
if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) {
|
||
int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast();
|
||
// NOTE: Subtract 1 to maintain nLockTime semantics
|
||
// ZIP 68 relative lock times have the semantics of calculating
|
||
// the first block or time at which the transaction would be
|
||
// valid. When calculating the effective block time or height
|
||
// for the entire transaction, we switch to using the
|
||
// semantics of nLockTime which is the last invalid block
|
||
// time or height. Thus we subtract 1 from the calculated
|
||
// time or height.
|
||
// 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 {
|
||
nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1);
|
||
}
|
||
}
|
||
return std::make_pair(nMinHeight, nMinTime);
|
||
}
|
||
static bool EvaluateSequenceLocks(const CBlockIndex& block, std::pair<int, int64_t> lockPair)
|
||
{
|
||
assert(block.pprev);
|
||
int64_t nBlockTime = block.pprev->GetMedianTimePast();
|
||
if (lockPair.first >= block.nHeight || lockPair.second >= nBlockTime)
|
||
return false;
|
||
return true;
|
||
}
|
||
bool SequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
|
||
{
|
||
return EvaluateSequenceLocks(block, CalculateSequenceLocks(tx, flags, prevHeights, block));
|
||
}
|
||
bool CheckSequenceLocks(const CTransaction &tx, int flags)
|
||
{
|
||
AssertLockHeld(cs_main);
|
||
AssertLockHeld(mempool.cs);
|
||
CBlockIndex* tip = chainActive.Tip();
|
||
CBlockIndex index;
|
||
index.pprev = tip;
|
||
// CheckSequenceLocks() uses chainActive.Height()+1 to evaluate
|
||
// height based locks because when SequenceLocks() is called within
|
||
// ConnectBlock(), the height of the block *being*
|
||
// evaluated is what is used.
|
||
// Thus if we want to know if a transaction can be part of the
|
||
// *next* block, we need to use one more than chainActive.Height()
|
||
index.nHeight = tip->nHeight + 1;
|
||
// pcoinsTip contains the UTXO set for chainActive.Tip()
|
||
CCoinsViewMemPool viewMemPool(pcoinsTip, mempool);
|
||
std::vector<int> prevheights;
|
||
prevheights.resize(tx.vin.size());
|
||
for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
|
||
const CTxIn& txin = tx.vin[txinIndex];
|
||
CCoins coins;
|
||
if (!viewMemPool.GetCoins(txin.prevout.hash, coins)) {
|
||
return error("%s: Missing input", __func__);
|
||
}
|
||
if (coins.nHeight == MEMPOOL_HEIGHT) {
|
||
// Assume all mempool transaction confirm in the next block
|
||
prevheights[txinIndex] = tip->nHeight + 1;
|
||
} else {
|
||
prevheights[txinIndex] = coins.nHeight;
|
||
}
|
||
}
|
||
std::pair<int, int64_t> lockPair = CalculateSequenceLocks(tx, flags, &prevheights, index);
|
||
return EvaluateSequenceLocks(index, lockPair);
|
||
} -->
|
||
</section>
|
||
<section id="acknowledgments"><h2><span class="section-heading">Acknowledgments</span><span class="section-anchor"> <a rel="bookmark" href="#acknowledgments"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>This ZIP is based on BIP 68, authored by Mark Friedenbach, BtcDrak, Nicolas Dorier, and kinoshitajona.</p>
|
||
<p>Credit goes to Gregory Maxwell for providing a succinct and clear description of the behavior of this change, which became the basis of the BIP text.</p>
|
||
</section>
|
||
<section id="deployment"><h2><span class="section-heading">Deployment</span><span class="section-anchor"> <a rel="bookmark" href="#deployment"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>At the time of writing it has not been decided which network upgrade (if any) will implement this proposal.</p>
|
||
<p>This ZIP is designed to be deployed simultaneously with <a id="footnote-reference-6" class="footnote_reference" href="#zip-0112">3</a> and <a id="footnote-reference-7" class="footnote_reference" href="#zip-0113">4</a>.</p>
|
||
</section>
|
||
<section id="compatibility"><h2><span class="section-heading">Compatibility</span><span class="section-anchor"> <a rel="bookmark" href="#compatibility"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<p>The only use of sequence numbers by the zcashd reference client software is to disable checking the <code>nLockTime</code> constraints in a transaction. The semantics of that application are preserved by this ZIP.</p>
|
||
<p>As can be seen from the specification section, a number of bits are undefined by this ZIP to allow for other use cases by setting bit (1 << 31) as the remaining 31 bits have no meaning under this ZIP. Additionally, bits (1 << 23) through (1 << 30) inclusive have no meaning at all when bit (1 << 31) is unset.</p>
|
||
<p>Unlike BIP 68 in Bitcoin, all of the low 22 bits are used for the value. This reflects the fact that blocks are more frequent (75 seconds instead of 600 seconds), and so more bits are needed to obtain approximately the same range of time.</p>
|
||
<p>The most efficient way to calculate sequence number from relative lock-time is with bit masks and shifts:</p>
|
||
<!-- hightlight::c++
|
||
// 0 <= nHeight <= 4194303 blocks (~10 years at post-Blossom block target spacing)
|
||
nSequence = nHeight;
|
||
nHeight = nSequence & 0x003fffff;
|
||
// 0 <= nTime <= 268435392 seconds (~8.5 years)
|
||
nSequence = (1 << 22) | (nTime >> 6);
|
||
nTime = (nSequence & 0x003fffff) << 6; -->
|
||
</section>
|
||
<section id="references"><h2><span class="section-heading">References</span><span class="section-anchor"> <a rel="bookmark" href="#references"><img width="24" height="24" class="section-anchor" src="assets/images/section-anchor.png" alt=""></a></span></h2>
|
||
<table id="rfc2119" class="footnote">
|
||
<tbody>
|
||
<tr>
|
||
<th>1</th>
|
||
<td><a href="https://tools.ietf.org/html/rfc2119">Key words for use in RFCs to Indicate Requirement Levels</a></td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
<table id="mailing-list" class="footnote">
|
||
<tbody>
|
||
<tr>
|
||
<th>2</th>
|
||
<td><a href="https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html">Bitcoin mailing list discussion</a></td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
<table id="zip-0112" class="footnote">
|
||
<tbody>
|
||
<tr>
|
||
<th>3</th>
|
||
<td><a href="https://github.com/daira/zips/blob/op-csv/zip-0112.rst">ZIP 112: CHECKSEQUENCEVERIFY</a></td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
<table id="zip-0113" class="footnote">
|
||
<tbody>
|
||
<tr>
|
||
<th>4</th>
|
||
<td><a href="https://github.com/daira/zips/blob/op-csv/zip-0113.rst">ZIP 113: Median Time Past as endpoint for lock-time calculations</a></td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
<table id="deployable-lightning" class="footnote">
|
||
<tbody>
|
||
<tr>
|
||
<th>5</th>
|
||
<td><a href="https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf">Reaching The Ground With Lightning (draft 0.2)</a></td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</section>
|
||
</section>
|
||
</body>
|
||
</html> |