Keep reorgs fast for SequenceLocks checks

morcos commented at 7:45 pm on December 8, 2015: member

Builds on #7184

Adds a commit to keep the mempool consistent with respect to sequence locked txs in the event of a reorg

morcos closed this on Dec 8, 2015

morcos reopened this on Dec 8, 2015

jtimon commented at 9:43 pm on December 8, 2015: contributor

Since #6312 has gne through a lot of review already, I would prefer that this branch builds on top of that to more easily review the differences. We can always squash things before merging for a cleaner history.

morcos commented at 9:55 pm on December 8, 2015: member

~~@jtimon That was the first thing I created: maaku@sequencenumbers…morcos:refactorb~~ (misunderstanding of what he was asking)

But I think #7184 is a cleaner implementation of BIP 68 on its own.

jtimon commented at 10:05 pm on December 8, 2015: contributor

as said squashes to clean up the history can happen after review. As mentiooned before, I still don’t see how maaku@sequencenumbers…morcos achieves its alleged goal.

morcos force-pushed on Dec 9, 2015

morcos commented at 2:52 am on December 9, 2015: member

rebased

NicolasDorier commented at 3:54 am on December 9, 2015: contributor

I think this PR is too complicated for fixing the perf issue, if https://github.com/NicolasDorier/bitcoin/compare/67646e099c13...b2a27a71823b is correct, it would be simpler to review. Regardless if we use #7184 or not.

jtimon commented at 5:28 am on December 9, 2015: contributor

@NicolasDorier I agree. Maybe more importantly, all the extra complexity is outside of the consensus critical code. Maybe you should consider opening a PR for your solution? In this thread we should focus on the code of this PR. We have #7176 to discuss the different solutions more generally.

jtimon commented at 6:23 am on December 9, 2015: contributor

Is this supposed to fix the performance issues of CNB without touching miner.cpp, or are this just preparations without the actual performance solution?

jonasschnelli added the label Feature on Dec 9, 2015

jonasschnelli added the label Mempool on Dec 9, 2015

morcos commented at 11:19 am on December 9, 2015: member

@jtimon This fixes the performance issues by never introducing them into CNB in the first place. #7184 on its own has performance issues with reorgs. @NicolasDorier You think just the second commit here is significantly more complicated than your final commit in #7190?

morcos force-pushed on Dec 9, 2015

morcos commented at 12:10 pm on December 9, 2015: member

squashed a bug fix (wasn’t actually skipping the work it was supposed to)

NicolasDorier commented at 3:09 pm on December 9, 2015: contributor

I like the fact you separate CheckLockTime (if you rename IsFinalTx) and CheckSequenceLockTime, but I really don’t like the LockPoints structure. I’m still reviewing if commit 2 might not result in mempool finality corruption, I really don’t find it obvious.

NicolasDorier commented at 3:18 pm on December 9, 2015: contributor

btw can you rename IsFinalTx to CheckLockTime as you said you wanted to do ?

morcos commented at 4:14 pm on December 9, 2015: member

@NicolasDorier My approach and yours are not that different.

You are storing the hash at which the calculation of the sequence lock time and height happened and using the fact that if that hash is still on the chain that the calculation must still be valid and the comparison to the current time and height must be valid because they can not have gone below what they were at the hash you saved.
I’m storing the lowest height hash at which the calculation of the sequence lock time and height would necessarily still be valid (which is the hash of the highest height input with a sequence lock, b/c if none of the inputs changed height then the calculation is trivially the same) and the result of the calculation. But in the case of my code, I have to redo the comparison part because the current time and height maybe be lower than they were at the time I originally did the comparison. So I will redo comparisons for every tx on every reorg, but that is extremely fast, and I save redoing the expensive calculations for many more txs.

NicolasDorier commented at 4:54 pm on December 9, 2015: contributor

Ok I’m getting it. Seems like it can work. You forget to check SequenceLockTime in rpcwallet.cpp, wallet.cpp.

morcos commented at 6:19 pm on December 9, 2015: member

@NicolasDorier I left that out on purpose. See #7184. It might need to be added back in but it wasn’t really clear to me how that code ever gets hit. I’ve tried asking about it on IRC a couple of times. But it doesn’t seem possible to me to generate a wallet tx which is sequence locked except in the event of a reorg, at which point the tx won’t be in your mempool anyway.

NicolasDorier commented at 6:23 am on December 10, 2015: contributor

Ok, I don’t really understand those implication yet.

NicolasDorier commented at 6:24 am on December 10, 2015: contributor

Will you rename to IsFinalTx to CheckLockTime and CheckSequenceLocks to CheckSequenceLockTime ?

morcos force-pushed on Jan 14, 2016

morcos commented at 10:35 pm on January 14, 2016: member

Updated for the updated #7184 and took @sdaftuar’s suggestion

morcos force-pushed on Jan 15, 2016

morcos force-pushed on Feb 16, 2016

morcos commented at 8:59 pm on February 16, 2016: member

This has been rebased and updated now that #7184 is merged. @laanwj Ideally this would be backported to the 0.12 branch when the soft fork for BIP68 code is merged. Otherwise the code for reorgs could be particularly slow.

NicolasDorier commented at 10:07 pm on February 16, 2016: contributor

I remember having done this remark already: and I was still not too much convinced by your response, I’m saying it here so other reviewer can dig in about it:

My main doubt is that there is a case where the nHeight/nTime of LockPoint should be invalidated but is not. Imagine you have a tx spending unconf coin C1 when tip is B1 and height X. MaxInputHash would be equals to hash(B1).

Now if B2 is found at height X+1, C1 still unconf, since B1 is still in the chain the LockPoint is not invalidated. My worry is that LockPoint SHOULD be invalidated as the prevHeights vector for calculating the LockPoint would not be the same anymore (the assumed height of C1 would be X+2 instead of X+1). The value of nHeight/nTime in the LockPoint would be impacted by it. I am still not entirely clear if it would have a chance of corrupting the mempool with an invalid tx though. (which would give problem to GBT which now rely on a coherent mempool)

morcos commented at 3:18 am on February 17, 2016: member

@NicolasDorier Yes sorry I hate the way those get lost. Here is your old comment: https://github.com/morcos/bitcoin/commit/f8b6614#commitcomment-15979134

I ended up punting on building the infrastructure to accept sequence locked txs that were not yet final. I have the code written to do it, but it requires slight changes to the BIP 68 code and I didn’t want to hold up merger for something of dubious value. But then I forgot to go back and clarify why the code here is safe.

I’ve now added a commit with what is hopefully a detailed explanation. And in the process I actually made it more efficient by eliminating the mempool input heights instead of capping them which will make recalculations on reorg even less frequent.

morcos force-pushed on Feb 17, 2016

NicolasDorier commented at 6:11 am on February 17, 2016: contributor

Good explanation, seems ok to me, I’ll test a bit though.

morcos force-pushed on Feb 17, 2016

morcos commented at 4:28 pm on February 17, 2016: member

just changed a couple words in the comment

NicolasDorier commented at 3:41 am on February 18, 2016: contributor

you may optimize even more: Only take the heights which correspond to an input who has a LockSequence for maxInputHeight calculation.

morcos commented at 6:28 pm on February 18, 2016: member

@NicolasDorier that’s already done. CalculateSequenceLocks already sets heights for non sequence locked inputs to 0.

laanwj added the label Needs backport on Feb 18, 2016

sdaftuar commented at 6:02 pm on February 26, 2016: member

Code review ACK (apart from comment nit). Testing…

sdaftuar commented at 6:44 pm on February 26, 2016: member

Tested ACK (hacked up some extra tests to bip68-sequence.py to exercise the reorg logic) 5912944f4d5eeb4078a5bb658ad09ef7eabbf53b

btcdrak commented at 7:12 pm on February 26, 2016: contributor

@sdaftuar Would you mind publishing/PRing those extra tests? Maybe they could be added to this PR?

morcos commented at 9:30 pm on February 29, 2016: member

comment nit addressed

sipa commented at 5:24 am on March 5, 2016: member

Kicked Travis

in src/txmempool.h: in 51531d2f25 outdated

178+    update_lock_points(LockPoints _lp) : lp(_lp) { }
179+
180+    void operator() (CTxMemPoolEntry &e) { e.UpdateLockPoints(lp); }
181+
182+private:
183+    LockPoints lp;

sipa commented at 10:51 pm on March 5, 2016:

I believe it suffices to turn this into a const reference.

in src/txmempool.cpp: in 51531d2f25 outdated

60@@ -61,6 +61,11 @@ void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
61     feeDelta = newFeeDelta;
62 }
63 
64+void CTxMemPoolEntry::UpdateLockPoints(LockPoints& lp)

sipa commented at 10:52 pm on March 5, 2016:

Make input argument const?

odinTy commented at 11:31 pm on March 5, 2016: none

If I’ve done something wrong it was by mistake I’m new and trying to learn. Sorry if I messed up

odinTy commented at 11:33 pm on March 5, 2016: none

Please explain all my mistakes please as this should help the future

btcdrak commented at 11:09 am on March 15, 2016: contributor

utACK ddb4dab

laanwj commented at 11:30 am on March 16, 2016: member

If I’ve done something wrong it was by mistake I’m new and trying to learn. Sorry if I messed up

What happened exactly? If you have specific questions about development and review process feel free to mail me on laanwj@gmail.com

laanwj commented at 3:58 pm on March 16, 2016: member

ut/code review ACK ddb4dab

in src/txmempool.h: in ddb4dab126 outdated

43+    int height;
44+    int64_t time;
45+    // As long as the current chain descends from the highest height block
46+    // containing one of the inputs used in the calculation, then the cached
47+    // values are still valid even after a reorg.
48+    uint256 maxInputHash;

laanwj commented at 4:04 pm on March 16, 2016:

Did you consider storing a CBlockIndex* here instead of a uint256? (may be a stupid suggestion, but from what I see the only thing you do is look it back up in mapBlockIndex)

morcos commented at 4:16 pm on March 16, 2016:

hmm… i feel like we did consider that, but i can’t see now why that wouldn’t work. maybe it didn’t work with some previous iteration. it makes sense to switch to that if we can’t see any problems with it.

laanwj commented at 4:21 pm on March 16, 2016:

right, I don’t see any problems with it at least: as I see it it’d simplify the code, reduce storage requirement for LockPoints, and makes the same (valid) assumption that a block index entry never goes away

jtimon commented at 4:12 pm on March 16, 2016: contributor

Concept ACK, started reviewing more deeply.

morcos commented at 4:39 pm on March 16, 2016: member

@laanwj ok done. If you think this has sufficient review I can squash.

Add LockPoints

Obtain LockPoints to store in CTxMemPoolEntry and during a reorg, evaluate whether they are still valid and if not, recalculate them.

982670c333

morcos force-pushed on Mar 16, 2016

morcos commented at 8:16 pm on March 16, 2016: member

Squashed from e6cc06b which contained the switch to CBlockIndex*’s

laanwj commented at 8:19 pm on March 16, 2016: member

utACK 982670c

laanwj merged this on Mar 16, 2016

laanwj closed this on Mar 16, 2016

laanwj referenced this in commit 14d6324a24 on Mar 16, 2016

btcdrak commented at 8:56 pm on March 16, 2016: contributor

@laanwj this PR has been backported in 7543.

MarcoFalke removed the label Needs backport on Apr 25, 2016

MarcoFalke commented at 1:35 pm on April 25, 2016: member

Removed ’needs backport’ label per previous comment

MarkLTZ referenced this in commit 7425415619 on Apr 27, 2019

MarcoFalke locked this on Sep 8, 2021

Keep reorgs fast for SequenceLocks checks #7187