Essentially enforces sequence numbers as a relative lock-time as an IsStandard() rule to make it easy to test applications using it; blocks containing transactions with invalid sequence numbers given the age of their inputs per BIP 68 are still accepted.
This pull-req is not a soft-fork nor does it contain any code to start that process.
This pull request builds on top of #6177.
Background: BIP 68, Consensus-enforced transaction replacement signalled via sequence numbers
Fixed.
On Sun, Jun 21, 2015 at 11:28 AM, Peter Todd notifications@github.com wrote:
Mind fixing that BIP link? 404
— Reply to this email directly or view it on GitHub #6312 (comment).
Now again, could you please do up a quick demo example app that actually uses this? e.g. like my https://github.com/petertodd/checklocktimeverify-demos/blob/master/micropayment-channel.py
Doesn’t have to be much, but we really need a worked out example here… Notably, see how without a way to fix tx mutability the nSequence proposal really isn’t any different in practice than just signing increasingly decreasing nLockTime’s? Because if you could safely sign the transaction it’d already be mined and thus you don’t need a relative nSequence - an absolute nLockTime calculated from the height/time of the tx you know already is in the chain is fine.
IMO there’s no reason to merge this until it has a safe use-case that provides a concrete benefit over the existing status quo; a simple change in what exact number is being signed isn’t a concrete benefit.
@btcdrak that code is here:
https://github.com/maaku/bitcoin/tree/checksequenceverify
It is entirely separate from what this pull request accomplishes. For example, it is possible to do simple transaction replacement without CHECKSEQUENCEVERIFY, as explained in the BIP. Likewise the source code of the CSV branch does not in fact depend on this pull request – all CSV does is verify a constraint on the sequence number of the input, it does not depend on that sequence number having consensus-enforced semantics.
@maaku I think the value of this PR in isolation is limited. You really need the opcode as well. It would be wonderful if you could publish a separate PR+BIP for CSV if you dont wish to combine them.
CSV is a very useful feature and one I think we clearly need to help address scalability. I see no profit in not getting it on the table now especially since it’s been deployed in Elements already and is clearly working.
I’m working on it. Things take time. On Jun 23, 2015 15:14, “฿tcDrak” notifications@github.com wrote:
@maaku https://github.com/maaku I think the value of this PR in isolation is limited. You really need the opcode as well. It would be wonderful if you could publish a separate PR+BIP for CSV if you dont wish to combine them.
CSV is a very useful feature and one I think we clearly need to help address scalability. I see no profit in not getting it on the table now especially since it’s been deployed in Elements already and is clearly working.
— Reply to this email directly or view it on GitHub #6312 (comment).
13@@ -14,5 +14,7 @@ static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
14 static const int COINBASE_MATURITY = 100;
15 /** Threshold for nLockTime: below this value it is interpreted as block number, otherwise as UNIX timestamp. */
16 static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
17+/** Threshold for inverted CTxIn::nSequence: below this value it is interpreted as a relative lock-time, otherwise ignored. */
18+static const uint32_t SEQUENCE_THRESHOLD = (1 << 31);
672@@ -673,22 +673,110 @@ bool IsStandardTx(const CTransaction& tx, string& reason)
673 return true;
674 }
675
676-bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime)
677+int64_t LockTime(const CTransaction &tx, int flags, const CCoinsView* pCoinsView, int nBlockHeight, int64_t nBlockTime)
1049@@ -969,6 +1050,19 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
1050 view.SetBackend(dummy);
1051 }
1052
1053+ // Enforce sequnce numbers as relative lock-time
1054+ // only for tx.nVersion >= 2.
1055+ int nLockTimeFlags = 0;
1056+ if (tx.nVersion >= 2)
1057+ nLockTimeFlags |= LOCKTIME_VERIFY_SEQUENCE;
1057+ nLockTimeFlags |= LOCKTIME_VERIFY_SEQUENCE;
1058+
1059+ // Only accept nLockTime-using transactions that can be mined in the next
1060+ // block; we don't want our mempool filled up with transactions that can't
1061+ // be mined yet.
1062+ if (LockTime(tx, nLockTimeFlags, &view, chainActive.Height() + 1, GetAdjustedTime()))
163+
164+ // Enforce sequnce numbers as relative lock-time
165+ // only for tx.nVersion >= 2.
166+ int nLockTimeFlags = 0;
167+ if (tx.nVersion >= 2)
168+ nLockTimeFlags |= LOCKTIME_VERIFY_SEQUENCE;
941@@ -860,6 +942,18 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
942 view.SetBackend(dummy);
943 }
944
945+ // Enforce sequnce numbers as relative lock-time
s/sequnce/sequence
Agreed with @petertodd that this is fairly pointless without BIP-62 (malleability), but I do want both for lightning.
(I also note that we should in future detach the locktime field from requiring non-FFFFFFFF nSequence; they’re completely orthogonal AFAICT. But that’s a minor soft-fork.)
nSequence apart?
Yup, my objection was a somewhat pedantic point of process; now that CSV has been proposed it’s moot objection.
Will review all this stuff soon FWIW, travelling right now… Per usual. :/
On 17 August 2015 18:43:33 GMT-07:00, Mark Friedenbach notifications@github.com wrote:
@rustyrussell @petertodd : what relative lock-time gives you is a committed response window to a proof-of-publication. With CHECKSEQUENCEVERIFY (#6564) there is indeed some features you can get that in some situations aren’t just replicatable with CHECKLOCKTIMEVERIFY. However the most exciting use cases also require something additional still. In the case of lightning, not just BIP 62, but some sort of normative txid.
@dcousens I believe @petertodd’s point is that since all the inputs are already on the block chain, you can just set nLockTime to the confirmed age of the input + the relative lock-time. And if the inputs are not all confirmed, then you are building chains of transactions that aren’t safe due to malleability. So really this is a feature that becomes most useful when we have a definitive fix for malleability, which we will in the not so distant future.
Reply to this email directly or view it on GitHub: #6312 (comment)
@maaku Just to clarify (though a bit OT):
Lightning wants normalized txid for simpler dual-input anchors, but doesn’t need it (the escape tx design seems to work).
Lightning needs normalized txid for outsourcing of revocation enforcement.
14 /** The maximum allowed number of signature check operations in a block (network rule) */
15 static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
16 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
17 static const int COINBASE_MATURITY = 100;
18+/** Threshold for inverted CTxIn::nSequence: below this value it is interpreted as a relative lock-time, otherwise ignored. */
19+static const uint32_t SEQUENCE_THRESHOLD = (1 << 31);
RELATIVE_LOCKTIME_THRESHOLD?
637@@ -638,22 +638,110 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans) EXCLUSIVE_LOCKS_REQUIRE
638 return nEvicted;
639 }
640
641-bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime)
642+int64_t LockTime(const CTransaction &tx, int flags, const CCoinsView* pCoinsView, int nBlockHeight, int64_t nBlockTime)
Luke, did you notice that the semantics changed? That’s why the name changed. On Aug 18, 2015 7:23 PM, “Luke-Jr” notifications@github.com wrote:
In src/main.cpp #6312 (review):
@@ -638,22 +638,110 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans) EXCLUSIVE_LOCKS_REQUIRE return nEvicted; }
-bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime) +int64_t LockTime(const CTransaction &tx, int flags, const CCoinsView* pCoinsView, int nBlockHeight, int64_t nBlockTime)
IsFinalTx was a better name IMO.
— Reply to this email directly or view it on GitHub https://github.com/bitcoin/bitcoin/pull/6312/files#r37374581.
No it switches to opposite meaning – zero indicates tx is final, nonzero indicates when it will become final. On Aug 18, 2015 8:24 PM, “Luke-Jr” notifications@github.com wrote:
In src/main.cpp #6312 (review):
@@ -638,22 +638,110 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans) EXCLUSIVE_LOCKS_REQUIRE return nEvicted; }
-bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime) +int64_t LockTime(const CTransaction &tx, int flags, const CCoinsView* pCoinsView, int nBlockHeight, int64_t nBlockTime)
You mean because it returns int64_t instead of bool? But unless I missed a spot, the return value is only ever used as a bool in the same sense…
— Reply to this email directly or view it on GitHub https://github.com/bitcoin/bitcoin/pull/6312/files#r37376960.
OK, I tested with with the lightning cli tools. Passed and failed transactions using nSequence as expected. That was for git rev 246d456476119d464adfb8fa2e938b6def13ad50.
Acked-by: Rusty Russell rusty@rustcorp.com.au
I have pushed two separate repos which provide an alternative to BIP 68 as specified, based on feedback received. I would appreciate review of these alternatives:
https://github.com/maaku/bitcoin/tree/sequencenumbers2
This repo removes the inversion of the sequence number, such that the relative lock-time value is used directly as the sequence number.
https://github.com/maaku/bitcoin/tree/sequencenumbers3
This repo also inverts the sequence number, as well as interprets it as a fixed-point number. This allows up to 5 year relative lock times using blocks as units, and saves 12 low-order bits for future use. Or, up to about 2 year relative lock times using seconds as units, and saves 4 bits for future use without second-level granularity. More bits could be recovered from time-based locktimes by choosing a higher granularity (a soft-fork change if done correctly).
Mark Friedenbach notifications@github.com writes:
I have pushed two separate repos which provide an alternative to BIP 68 as specified, based on feedback received. I would appreciate review of these alternatives:
https://github.com/maaku/bitcoin/tree/sequencenumbers2
This repo removes the inversion of the sequence number, such that the relative lock-time value is used directly as the sequence number.
OK, I like this.
https://github.com/maaku/bitcoin/tree/sequencenumbers3
This repo also inverts the sequence number, as well as interprets it as a fixed-point number. This allows up to 5 year relative lock times using blocks as units, and saves 12 low-order bits for future use. Or, up to about 2 year relative lock times using seconds as units, and saves 4 bits for future use without second-level granularity. More bits could be recovered from time-based locktimes by choosing a higher granularity (a soft-fork change if done correctly).
I think that’s overkill. We already have the high bit to say “ignore it” for future soft forks.
BTW, you need to fix the commit messages, as they still talk about inversion.
Cheers, Rusty.
Since posting the two alternatives 26 days ago, I have had conversations with many stakeholders via the mailing list, IRC, direct messaging, and in-person at the Scaling Bitcoin workshop in Montreal. Not all of these conversations were explicitly on the public record, so I will obey Chatham House rules in presenting a summary of these conversations in aggregate without identities attached. I hope that those who disagree with the summary or the outcome speak up in response.
With this in mind I have decided to update this pull request to the sequencenumbers3 branch. This branch restricts maximum relative lock-times to approximately 1 year, and in doing so sets aside 5 bits for future expansion when using time-based relative lock-time (granularity: 1 second), and 14 bits for future expansion when using height-based relative lock-time (granularity: 1 block). Further bits could be set aside by decreasing granularity in a soft-fork compatible way.
All of the presently imagined use cases for BIP 68 and the related CHECKSEQUENCEVERIFY opcode (#6564) use relative lock-times much less than one year, so it is expected that this constraint on the maximum range does not restrict usability in any meaningful way.
BIP 68 will be updated to reflect this new scheme.
682+ continue;
683+
684+ // Skip this input if it is not in the UTXO set. This should
685+ // only ever happen in non-consensus code.
686+ if (!pCoinsView->GetCoins(txin.prevout.hash, coins))
687+ continue;
647- return true;
648- BOOST_FOREACH(const CTxIn& txin, tx.vin)
649- if (!txin.IsFinal())
650- return false;
651- return true;
652+ CCoins coins;
Yep that would have been better. However I wonder if this is necessary or desirable now that this PR has received many full reviews, including verification that the change is a soft-fork.
If you or others are having trouble verifying this, I recommend looking at the individual commits. There are two preparatory commits that contain no consensus changes, only rearrangement of the logic for IsFinalTx() into what will become LockTime(). The BIP 68 changes then affect only specific portions of the IsFinalTx / LockTime code.
Just pushed a relatively minor consensus change to BIP 68 functionality, based on something that was observed while editing the BIP 68 and BIP 112 drafts.
Previously, it was possible to have a “zero” relative lock-time that allowed child and parent to be in the same block, but only if block-height was used. The smallest allowed relative lock-height using block-time required at least one block separation between child and parent. The reason for this asymmetry was a legacy of bit inversion where SEQUENCE_FINAL overlapped in meaning with 0-height relative lock-time.
There is no longer justification for treating these two units separately. Conceivably there could be an obscure use case where the CHECKSEQUENCEVERIFY parameter is calculated on the stack and yet the check itself needs to be disabled under some circumstances – passing though a zero in this case could save a few bytes over wrapping the CSV in an IF/ELSE block. So I have opted for making the behavior symmetric in that both 0x00000000 (0 blocks) and 0x40000000 (0 seconds) allow child and parent to appear in the same block. The tests have been updated accordingly.
All nits have been addressed except @sipa’s (see my comment there). @rustyrussell for your convenience I have extracted the patch from the tree you ACK’d to the present state of the pull request. Here is the 0bin:
http://0bin.net/paste/R7x6LS+2bZ588OLs#2yvQPDe36d0PxI8ImqRhhie4-DS5l4wb0OcpDJIgWw1
Does not need rebase… anyone know how to get github to reload a PR? My branch is updated but the PR is not updating.
EDIT: yay fixed
So to summarise this latest iteration now frees up some nSequence bits for future expansion as follows:
The first two bits signal whether relative lock-time is used, and which units (0 = height, 1 = seconds for bit 30), then either 16 bits of relative height, or 25 bits of relative time.
The remaining low order bits (5 or 14) are unused, reserved for future expansion: if you don’t want relative lock-time, there’s 31 bits to use for whatever purpose (by setting the MSB) and if you do want relative lock-time, then there are 5 or 14 bits based on which units you use. More bits are reclaimable if you decrease granularity (in a soft-fork compatible way), e.g. round up the second based relative lock-time to the next multiple of 512, and you now have 14 bits for both units (512s is less than the expected time between blocks, so it’s barely any a change anyway).
This failed my test script.
In particular, I generate tx A, and tx B which spends A and has nSequence indicating +60 seconds. I sendrawtransaction A, generate 11 blocks, sleep 61, generate 11 blocks, then try to spend B. It fails as nonfinal. This worked with previous versions. I suspect in some places we’re using median time and in other places block time.
Immediately after spending A, we try to spend B (and expect it to fail): in LockTime() nBlockTime is 1443510877, but pindexBestHeader->GetAncestor(coins.nHeight-1)->GetMedianTimePast() is 1443510890. That extra 13 seconds is just weird.
This is -regtest, BTW.
Rusty, I believe that is due to the normal behavior of regtest. It is a consensus rule that the median time past increase in each block, and in regtest mode you are creating blocks faster than 1 second. The consensus rule probably should have been checking that nTime >= GetMedianTimePast() rather than strictly greater, but c’est la vie. Add that to the list of trivial hard forks.
So given that there were 13 seconds of discrepency, you’ve given us insight into how long it took on your machine to generate 100 blocks, submit a transaction, and generate 22 more blocks.
@maaku thanks, indeed: the block times were being pushed forward about 13 seconds (block generation bumps the time if it would be <= GetMedianPast()). Taking that into account, my tests all pass!
Tested-by: Rusty Russell rusty@rustcorp.com.au
We’re permanently sacrificing a bit from nSequence - and possibly sacrificing a few more longer term. But the immediate utility of CSV seems to outweigh the sacrifice, and we can eventually recover 31 bits back if we end up deprecating this mechanism in the future.
I still have some reservations on the implementation. Did not test with wallet. But I would like to see some form of this merged soon. .
692+ // be certain about whether lock-time constraints have
693+ // been satisfied. Note that it should only ever be
694+ // possible for this to happen with wallet transactions
695+ // that have unknown inputs.
696+ else
697+ return std::numeric_limits<int64_t>::max();
(summarizing earlier discussion about this) The problem is that that would be the case whenever the wallet check finality on an transaction whose inputs are already spent.
IMHO the clean solution is to pass in the heights/times of all inputs to this function, which could have a different implementation for mempool/wallet/blockchain behaviour. Another - but probably more invasive change - would be to extend the CCoinsView interface to be able to request height/time data for inputs, and implement a CCoinsView for the wallet too.
685+ // Fetch the UTXO corresponding to this input.
686+ if (!pCoinsView->GetCoins(txin.prevout.hash, coins)) {
687+ // It is fully expected that coinbases inputs are not
688+ // found in the UTXO set. Proceed to the next intput...
689+ if (txin.prevout.IsNull())
690+ continue;
Looks good. Having 1 year of relative time for nSequence is more than sufficient for multisigature revocation scripts used in systems such as Lightning Network. These systems have the particular use case of revoking multisignature double-spends via lower relative locktimes. In effect, the 1 year relative time becomes a dispute period for observing activity on-chain and is therefore well more than sufficient, as that presumes a maximum programmable length of onece per year when one watches the blockchain.
Additionally, the per-input use of consuming a bit in nSequence makes a lot of sense, as there may be inputs with different behavior – applying it to all inputs with nVersion would significantly increase complexity and reduce use, as maaku explained. It’s also good to have similar functionality for blockheight and relative timestamp to match nLockTime.
Enabling/disabling relative locks permanently consumes a single bit in nSequence seems to make a lot of sense, as there may be different uses of relative timestamps (e.g. timestops in the future) or more exotic uses. Stellar has something which uses the phrase “sequence number”[1] but appears that functionality in Bitcoin can be used without some sequence flag via sending to different Bitcoin addresses per transaction.
[1] https://www.stellar.org/blog/multisig-and-simple-contracts-stellar/
utACK
Gave a close read-over. I think the extra flexibility is a good idea at the expense of total relative lock time span.
.gitignore but weren’t. I’ve removed them.
709+ //
710+ // Note that it is not guaranteed that indexBestBlock will
711+ // be consistent with the passed in view. The proper thing
712+ // to do is to have the view return time information about
713+ // UTXOs.
714+ const CBlockIndex& indexBestBlock = *chainActive.Tip();
cs_main for this, though I think the callers already do. So perhaps an AssertLockHeld(cs_main) would be appropriate at the top of this function?
AssertLockHeld(cs_main) in the main tree. I don’t think it does any harm adding an assert though.
AssertLockHeld(cs_main).
718+ // The only time the negative branch of this conditional
719+ // is executed is when the prior output was taken from the
720+ // mempool, in which case we assume it makes it into the
721+ // same block (see above).
722+ int64_t nCoinTime = (nCoinHeight <= (indexBestBlock.nHeight+1))
723+ ? indexBestBlock.GetAncestor(nCoinHeight-1)->GetMedianTimePast()
Pasting @maaku ’s response on the commit :
No, GetMedianTimePast is preferred because it is not a free choice by the miner who included the transaction being spent. BIP 113 changes the other end of the interval for both nLockTime and nSequence to be GetMedianTimePast, which is a soft-fork change, but changing the start of the interval in that way would be a hard-fork change. So we start from the very beginning using GetMedianTimePast.
Ok it is clear thanks !
I agree that IsFinalTx should be a pure logic function.
I think a compromise can be made by having two overload of the IsFinalTx : One with the CCoinsView and the pure logic one.
The one with CCoinsView would pull out the list of input heights/times and then call the pure function. This would not break the code which already depends on the current IsFinalTx, while still allowing to call the IsFinalTx pure function for other part which need to decide by themselves how to deal with missing inputs.
If the PR needs to be expedient, the clients of IsFinalTx may be modified in a separate PR, but at least IsFinalTx will be easier to review and test.
I tried to implement the purely logical way of doing it in C#: (code very similar to C) ChainedBlock correspond to CBlockIndex, also this is a non static method, so “Input” and “LockTime” refer to the currently evaluated transaction.
Basically, I pass an array of CBlockIndex which is expected to have the same size as the number of input in the transaction. If an element is null, I assume that the transaction in the mempool. “confirmedBlocks[i]” corresponds to the CBlockIndex of the i’th input of the transaction.
https://github.com/MetacoSA/NBitcoin/commit/874a21c240b2da2ab9310d4e5962336cfea4efbb
Now, for being expedient on this PR, it would be possible to make a LockTime function which have the same parameter as now but which search the “confirmedBlocks” in the CCoinView directly, take the tip of th activeChain, and call the pure logic overload.
Since I am assuming null element of the input’s block array are spent output from the mempool, if you can keep the exact same semantic than now in the case the CCoinView does not have the coin, then you can feel with the array with the genesis CBlockIndex if CCoinView does not find the coin.
This would have the same effect as:
0if (!pCoinsView->GetCoins(txin.prevout.hash, coins))
1 continue;
Because nMinTime and nMinHeight would not be modified.
I can implement it in C if it helps, but since I can’t really compile it would certainly need some fixes.
I gave it a try : 5f24b6603407c78ae112ae82fd293ac24fbefb52
I have not compiled it, but it explains my point.
@NicolasDorier Oh that’s great. I can cherry-pick this into the PR after testing.
edit: doesn’t compile.
I fix that for tonight, thanks, will setup travis on my branch as well as you advised.
EDIT : fixed on 6a9495392f0f89ed9ce46ff2bc3460ce443f407a you can try, if it does not work I’ll try to setup travis on my branch to debug myself.
Just sent a new commit which make LockTime independant from the tip, but also responsible for calculating the blocktime correctly based on MTP flag. With that I could remove several code duplication.
65506413367f09d34b942a3b1256066e4346eccf
I’m thinking about changing this line, so the CCoinView is not queried twice. (once in HaveInputs, the other in LockTime to fetch previous coins)
Also, it would make the consensus code dependent only the purely logical LockTime function instead of the other.
Thoughts ?
I’m thinking about changing this line, so the CCoinView is not queried twice. (once in HaveInputs, the other in LockTime to fetch previous coins) Thoughts ?
It reminds me of #6445 (which I’m happy to rebase at any time if/when/after “we merge the mempool limiting code” (sorry, I’m not sure which PR to point you to) ).
The scope of #6445 seems to do way more optimization. So I think that all of these optimization should be done at the same time with another PR. (calling the logical function LockTime included) I also don’t know if it is worth since the CCoinView is already caching coins.
The PR seems complete to me right now, I’ll start making more tests by running a node.
Last question I have : I’m not used to dev in C, so I don’t really know the best practice out here, as you can see here there is a std::vector<CCoins> parameter. This works fine, but does a std::vector<CCoin*> would be preferable to avoid copies ?
648- BOOST_FOREACH(const CTxIn& txin, tx.vin)
649- if (!txin.IsFinal())
650- return false;
651- return true;
652+ int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST)
653+ ? block.pprev->GetMedianTimePast()
Good catch, I just fixed it on https://github.com/NicolasDorier/bitcoin/commit/eb2696281bd9bd13d0fca5c25e7c96969b5ef518
If you want to update this PR.
concept ACK + it-works test
Reviewed downstream payment channel code and specifications - no apparent conflicting uses in the field widely deployed AFAICS, which was my main concern with BIP 68.
Concept ACK.
I really miss some RPC tests. A RPC test/playground-script could be used to demo the new functionality, allow modification for testers and would prove that it actually works. For testing/verification purposes its far more useful than the internal unit tests (not saying the unit tests would then be superfluous!).
@jonasschnelli I can provide that, but it would be in C#, so I’m not sure if it will be useful for people here.
Maybe a website where you can create your own script and point it to your node ?
@NicolasDorier: I think it should be in line with our qa/rpc-tests. They are written in Python, a language that everyone can lear within 5-10mins. :)
You might check the bip65 test scripts:
https://github.com/bitcoin/bitcoin/blob/master/qa/rpc-tests/bip65-cltv-p2p.py
Would be awesome to see some bip68 rpc tests that demonstrate and test real-world examples.
@jonasschnelli those are tests for the softfork and were added to CLTV after the mempool only PR was merged. They were added as part of the CLTV softfork implementation in #6351.
So for this reason, we’ll add RPC tests when it’s time to activate the softfork.
This PR is 5 months old now and we’ve accommodated everyone’s nits. I believe it’s refined enough now to be merged. It is currently mempool-only behaviour so does not pose any risks.
I don’t want this PR to end up in “rebase-hell”, especially because we know there are more refactoring coming up that will affect this patch. Better merge now, and refactor/optimise afterwards.
@btcdrak Please have a look at https://github.com/sipa/bitcoin/commits/sequencenumbers. I added a commit that turns LockTime into a function that only takes in a height map of inputs, and CheckLockTime contain all mempool-specific logic (no intermediate-level LockTime function either).
It also avoids calling the inefficient GetCoins method on pcoinsTip in block validation, which would make a full copy of all UTXO data of transactions being spent.
Reviewed d6ed8e6 this is good to me, I prefer the height map as well. Although, I think not having the wrapper make it less readable. What difference between GetCoins and AccessCoins ? if the problem was about performance, we could have used AccessCoins in the wrapper, it would spare us some code. @CodeShark I’m not against squashing anything, I just thought it was better for review to keep them separate:
I think they should be reviewed separately to understand how we’ve been from @maaku implementation to the modified one.
@NicolasDorier Yes, performance. GetCoins copies. AccessCoins returns a reference. But you can only use AccessCoins on caches (so not on the mempoolview, for example).
I’m not against leaving the wrapper, though I think it’s better this way.
@jtimon I’m not sure but I think there are blocks in the past without input for the coinbase ? In such case they would be size() == 0, but this would have different semantic as point==NULL.
Also, I think expressing missing parameter with NULL is more common.
69+ * sequence number disabled relative lock-time. */
70+ static const uint32_t SEQUENCE_LOCKTIME_DISABLED_FLAG = (1 << 31);
71+ /* If CTxIn::nSequence encodes a relative lock-time and this flag
72+ * is set, the relative lock-time has units of 512 seconds,
73+ * otherwise it specifies blocks with a granularity of 1. */
74+ static const uint32_t SEQUENCE_LOCKTIME_SECONDS_FLAG = (1 << 22);
SEQUENCE_LOCKTIME_SECONDS_FLAG is not a good name because this flag determines the type of relative lock-time, i.e. timebased or block based. I wonder if SEQUENCE_LOCKTIME_TYPE_FLAG would be better.
652+ assert(prevHeights == NULL || prevHeights->size() == tx.vin.size());
653+ int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST)
654+ ? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast()
655+ : block.GetBlockTime();
656+
657+ bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2
Because otherwise you’d be doing a signed comparison and there’d be half the range of nVersion that wouldn’t support BIP 68.
On Tue, Dec 1, 2015 at 4:33 AM, Jorge Timón notifications@github.com wrote:
In src/main.cpp #6312 (review):
{
- if (tx.nLockTime == 0)
return true;- if ((int64_t)tx.nLockTime < ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD ? (int64_t)nBlockHeight : nBlockTime))
return true;- BOOST_FOREACH(const CTxIn& txin, tx.vin)
if (!txin.IsFinal())return false;- return true;
- 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
why is this cast needed?
— Reply to this email directly or view it on GitHub https://github.com/bitcoin/bitcoin/pull/6312/files#r46199226.
Instead of checking if the transaction is in a category of cases to return true and failing otherwise, we return false if the tx is a failure case and otherwise return true. This removes an early-exit opportunity which will no longer be possible once sequence numbers are re-enabled, but has no change in behaviour.
Breaks up the modifications to IsFinalTx() / LockTime() for easier review. This commit does not change the logic of IsFinalTx().
In summary, the sequence number of each input in a transaction can be used to store a relative locktime: a delta value which is added to the height or time of the block which included the output being spent to generate a per-input lock time from the sequence number. If enforced, this would make consensus-enforced transaction replacement possible as replacing an input with a lower sequence number / relative lock time would allow the new transaction to make it on the chain before previous versions of the transaction become valid.
This commit does not implement the transaction replacement logic. Nor does this commit make the relative lock time rules as consensus or policy rules. It merely adds new, but disabled functionality and unit tests of that functionality.
Transactions that fail relative lock time checks will be rejected from the mempool and not included in generated blocks, making it easy to test the feature. However blocks including transactions containing "invalid" relative lock times will still be accepted; this is *not* the soft-fork required to actually enable relative lock times for production use.
LockTime() : the nCoinTime of a confirmed coin does not depend on MTP
flag, so the nCoinTime of an unconfirmed also should not be.
Addressing sipa's nits
@NicolasDorier Ah, I hadn’t realized that we wouldn’t be able to merge #6312 until we worked on the efficient way of doing that. @sipa Why not just make the mempool be consistent with finality of txs so we don’t have to check that any more in CreateNewBlock. This is what we discussed in #6915, we only need to store one height, which is the max of the height the tx is viable for coinbase maturity and for BIP68 sequence numbers. Then on a reorg we revaluate if the reorg dropped below this height.
So that’s necessary before #6312 can be merged? I or @sdaftuar can do it.
I tried to modify sipa’s commit to adapt on https://github.com/NicolasDorier/bitcoin/commit/33254c779baa365f15af74074e66f620388a5e5e#diff-4a59b408ad3778278c3aeffa7da33c3cL142 but it is not good it fails
0test_bitcoin: main.cpp:666: int64_t LockTime(const CTransaction&, int, const std::__debug::vector<int>*, const CBlockIndex&): Assertion `prevHeights == __null || prevHeights->size() == tx.vin.size()' failed.
1unknown location(0): fatal error in "CreateNewBlock_validity": signal: SIGABRT (application abort requested)
2test/miner_tests.cpp(139): last checkpoint
This is the only point that need to be fixed for rebasing, I needed to fix conflict and modify lots of commits which took into account recent commits on master, https://github.com/NicolasDorier/bitcoin/commits/sequencenumbers .
I don’t understand why what I did for CreateBlocks does not work though (GetMempoolParent only get parents which are in mempool and not conf ?)… I would appreciate some help, this really seems the last problem. :(
Ok, I understand. Checking finality during reorg is better done in a separate PR, or can we try to squeeze it into this one ?
Seems like best to do that than trying to fetch heights in CNB like I tried.
_SECONDS_FLAG to _TYPE_FLAG
_DISABLED_FLAG to _DISABLE_FLAG
@NicolasDorier longest-chain means most-work, not most-blocks. Think about a reorg that crosses drastically different difficulty adjustments.
But while such edge cases should be properly handled, I wouldn’t want you to waste your time trying to get the checks in CNB removed. Such a change will be nack’d. Those checks exist because we’ve had mempool inconsistencies in the past, and we will have mempool inconsistencies in the future. This is other people’s money we’re talking about in CNB, so it’s really not a terrible thing to double-check ourselves.
@maaku I understand for the chain, I indeed thought longest chain was “more blocks”. It is a bit a shame that it breaks the perf improvement that @morcos spent time to fix though.
What I propose to keep CNB while having perf improvement, is to save in mempool entry the highest blockid at the time of AcceptToMempool after the finality check. In CNB if the blockid of the mempool entry is not in current chain, then we do the CNB test, else we can skip it. How does it sound ? Easy to implement, and not lots of room for mistake. (I think people will not like the +32bytes per entry ;( )
You will do this by storing the height and time at which the entry is final, and only recalculating if the reorg dropped below that height (or for added efficiency if the reorg dropped below the height necessary to calculate those heights).
Doing such thing would be a bug. Because even if the reorg does not drop below the height, the FinalTx may be invalidated. (the “blocktime” in LockTime() may have changed) This is why we would need to store the hash of the evaluated block in the mempool entry, not only the height.
or can we try to squeeze it into this one ?
At some point we will hopefully stop improving this PR and finally merge it. It was my belief that the plan was to do it before 0.12, but 6 months after the functionality was first implemented and more than 5 months after the PR was created (now) seems as good of a time as any other. That doesn’t mean we can’t keep improving the code later, but it would be nice to finally get this functionality in. We use this “that improvement can be added later” argument with many other PRs, in fact, I’m pretty confused about what’s the criterion on when to stop adding improvements to a given PR, it seems very inconsistent from PR to PR (this PR being a good example of a perpetually-changing PR).
const CCoinsViewCache& parameter and I would happily review any attempt to change that fact. Just saying…
This is what I had in mind: https://github.com/maaku/bitcoin/compare/sequencenumbers...morcos:refactorb
It’s still missing commits to properly recalculate the LockPoints after a reorg and to remove the checking of LockTime in CreateNewBlock. However I wanted to see if this is the direction people want to go?
@NicolasDorier The only thing that I’d argue should be added to this PR is the change to the consensus functions. The first commit from my branch and maybe the change to CheckLockTime from the second. The other changes should be in a separate PR that is backported only to 0.12 (but before the point release that contains this PR)
I wanted to show the version that has the fewest changes from this PR first, but I do think its a good question as to whether thats the right goal. This is unreleased consensus code still, so it might make sense to make a bit more substantial refactor. Open questions:
LockTime interface?These changes would be very small additional changes to the consensus code, but would require changing all the tests, so it would be more to review.
@morcos, on my side, I’m just getting tired of rebasing every time something change on master. I’ll do anything to get that merged. I’ll pay ACKs in beers for those coming in HK… And make them drink until they give the ACK. :p
I quickly reviewed your commits : I don’t understand the purpose of the structure update_lock_points. I fear also that we will again need to update the BIPs explaining why there is a new structure and why it is broken in two function before this PR can be pushed. And pushing your two commits in this PR without the one calling updatePoint during reorg is like doing the job mid way spread onto 2 different PR.
This is a good idea, but the monstruosity of this PR make it already hard to review, which is why it never get ACKed. A sort of psychological blocks happen when one see 11 commits with 174 messages in discussion. Anyway, I’m not against having your commits in this PR if it accelerate the reviews, but I doubt it.
(EDITED) OK I updated https://github.com/maaku/bitcoin/compare/sequencenumbers...morcos:refactorb to be a slightly different refactoring.
The first two commits are bug fixes for the unit tests. The third commit is a minor refactor of LockTime to get access to the critical variables. The fourth commit uses that refactor to store LockPoints in CTxMemPoolEntries. The fifth commit keeps LockPoints valid during a reorg. The sixth commit removes LockTime calculations from CreateNewBlock
Probably the miner_tests need to be completely rewritten now that mempool consistency is depended on. A lot of the tests are designed to make sure invalid blocks won’t be created if the mempool isn’t consistent.
If this is the direction of refactor we want to achieve our goal, then I think we should only cherry-pick at most the first three commits into this pull (and for backporting to 0.11). The third commit which is the change to consensus code should be trivial for people to review.
@morcos what is exactly the problem with leaving all your commits for the next PR instead of putting “half of the change” here? Now I see why I wasn’t able to understand how your code fixes cnb (the goal of the changes), it doesn’t yet!
I think it’s better to put the preparation commits in the same PR when the preparations are actually going to be used when possible (ie when this doesn’t result in a 20 commit PR). Otherwise ww may change our mind on how to fix the problem but the preparations remain there.
I prefered your previous commits CalculateLocks should returns information direclty into LockPoint datastructure, so we don’t have to make the mapping. Also I think it is hard to review right now and I guess, @maaku was not so eager to remove locktime check in CNB.
How about a simpler change : We store a bool called “LockTimeChecked” in the mempool entry, then when there is a reorg (which is the only case where the lock can be invalidated) we set the bool do false.
CNB, would check LockTime only if the bool is false, and once checked, it can put it back to “true” so next call to CNB will be fast.
I am not comfortable with your changes, it change lots of stuff that was reviewed and tested. Not mentioning the fact we would need to update the BIP again. My change would achieve the same thing as you but with minimal changes. I will try to propose a commit.
@NicolasDorier sounds like a nice and easy way to solve the CNB performance problem without having to touch the consensus code further and without having it depend on new structures.
Let’s have a thought experiment. Let’s say this was merged with morcos’ preparations for his solution but without the actual solution for CNB. Let’s say @NicolasDorier had had the odea only after merging morcos’ preparations. Now what? Do we revert morcos’ changes? That’s why I don’t like including more things here. Regarding bakports, the same commits can be backported regarlesss of them being in a single PR or 2 separate ones. Please let’s leave this as it is and solve the CNB performance issue later, even if we all like Nicolas’ solution. We may rhink of another even better solution later.
For the record, @ajtowns has been working on some exotic HTLC functional demos using my #6312+#6564 branch which will help allay fears about the lack of tested ACKs (which is the real reason for delay). It will also help protect against regression if we need to change anything.
This PR has to be backported to 0.11 and 0.12, so we need to take that into consideration. So long as we have good functional tests we should be able to add commits to cater for CNB() optimisations that can be removed for 0.11.
With regards to updating the BIP, we’re not changing any of the specification, only parts of the code implementation which is simple copy paste, so I don’t think it will present a problem.
tl;dr - while I appreciate reluctance for too much change, that is not the obstacle to getting this merged.
There was an extraneous tx being added to the mempool which spent the same inputs. This only didn't cause a problem because locktimes stopped it from being selected for the template.
In addition, since the merger of MedianTimePast, locked txs that were time based were not being correctly tested in the unit test.
Yes, CheckLockTime assumes that if a parent is not in CCoinView, then the locktime is correct. I don’t want this behavior in CNB, what I want is : if it is not in CCoinView, assume it is in the mempool.
But this will likely be completely deleted because I managed to keep mempool consistent with finality while not having to call CheckLockTime on every tx in the mempool during reorg (which was a big performance problem, regardless of CNB, as you noted), we will not have to call CheckLockTime in CNB now. Can you check https://github.com/NicolasDorier/bitcoin/compare/67646e099c13...b2a27a71823b to see if it makes sense ? I’ve fixed the failing test. Travis running, but it should work.
@NicolasDorier We need MTP and BIP 113 and the enum all for the purposes of nLockTime locks because nLockTime is already consensus and we want to soft fork its semantics to be MTP.
However in the case of sequence locks and BIP 68, there is no reason for us to not just redefine BIP 68 to have MTP semantics from the outset, because there is no policy or consensus meaning to sequence locks yet.
This change to BIP68 (https://github.com/bitcoin/bips/pull/260) while making a clearer specification just broke completely this PR. Basically this PR assumed similar blocktime calculation (MTP or not) policy for both nLockTime and sequence lock time. But the change of specification makes MTP mandatory for sequence locktime while nLockTime is still depends on MTP activation.
This PR, if preferred over alternatives, will need to be updated. (or the change to specification reverted) I expect the changes to tests code and logic to be significant though to be worth the trouble.
I think the best choices are either to move to Morcos’ PR (https://github.com/bitcoin/bitcoin/pull/7184) which is very different from this implementation. Or, reverting https://github.com/bitcoin/bips/pull/260 if people wants to stick with this well reviewed PR.
The assumption of MTP only was discussed at the IRC meeting and that BIP68 and BIP113 need to be softforked together.
I am in favour of #7184. However, the assumption was if this PR is chosen over #7184 then this PR would be updated accordingly to the new specification. It’s just #7184 already made the assumption. It’s a lot cleaner to assume MTP and really, there is no situation where it would not be MTP because we are deploying 68 and 113 together.
Yeah sorry about that, I guess it is a bit tough to try to keep BIP spec in line with code. But honestly I think this confusion shows why I like the code organization of #7184 better. The consensus code for sequence and nLockTime is too intermingled here.
One of the hesitations with switching to #7184 has been that this PR is already heavily reviewed and tested. I think this is wrong. It had a lot of preliminary review, but then the code changed, and I think its had only minimal testing. An example is the checking of sequence locks that is throughout the wallet and GUI code in this PR. I believe those would lead to unacceptable performance for any node with a half way decent size wallet. They would slow down a lot of operations and also make the utxo cache worthless.
I think this is wrong. It had a lot of preliminary review, but then the code changed, and I think its had only minimal testing.
It is true that the code changed after most of the reviews were done. Fortunately @btcdrak kept the commits separated so that concern has an easy solution: remove the latest changes. I have to say that this has also been tested as part of the elements/alpha testchain (still in operation) for more than 6 months. @rustyrussell may be able to tell us more about tests in the context of lighting development (my apologies if that’s not the case).
@jtimon one of my change is actually a bug fix… sadly it was squashed. Regardless of what happen, this should be kept.
The problem was that the birth time of an unconfirmed coin was set to blockTime which depended on MTP activation. Whereas confirmed coins always used MTP time.
@NicolasDorier Well, if it was a bugfix then it’s not sad that it was squashed, is it? I mean more the later changes to make the function a pure function, which is, I assume the less reviewed changes @morcos is concerned with.
In my opinion no optimization had been needed in the mining code this could have been merged before 0.12 with no backporting problems. If the optimizations hadn’t been urgent they could have been later during 0.13.99. But now it’s too late for that, thus the need for #7176 . All the possible fixes could be built on top of the same branch (this one, for example) to compare them more easily, but seems not everybody agrees that a common base makes branches easier because I have already say this without the different proponents agreeing on a common base, and @maaku seems to be the only other person that thinks #7187 should be based on this PR instead of #7184 so I shouldn’t insist on this.
Which is why it is better not to squash until the very end before merge. On Dec 20, 2015 7:04 PM, “Nicolas Dorier” notifications@github.com wrote:
By “sad being squashed”, I mean that if you want to revert recent changes I made, at least you should keep the bug fix commit. Extracting it would have been simpler without squash. (but well, the bug is not a big deal to fix again)
— Reply to this email directly or view it on GitHub #6312 (comment).
As already posted on #7184
https://github.com/maaku/bitcoin/compare/sequencenumbers...morcos:7184onorig6312
Feel free to incorporate that here if that is preferred.
Tested-by: Rusty Russell rusty@rustcorp.com.au
(I merged both this and #6564 for the test, with only a trivial conflict to resolve).