Keep reorgs fast for SequenceLocks checks #7187

pull morcos wants to merge 1 commits into bitcoin:master from morcos:fastReorgBIP68 changing 6 files +131 −26
  1. 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

  2. morcos closed this on Dec 8, 2015
  3. morcos reopened this on Dec 8, 2015
  4. 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.

  5. 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.

  6. 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.

  7. morcos force-pushed on Dec 9, 2015
  8. morcos commented at 2:52 AM on December 9, 2015: member

    rebased

  9. 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.

  10. 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.

  11. 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?

  12. jonasschnelli added the label Feature on Dec 9, 2015
  13. jonasschnelli added the label Mempool on Dec 9, 2015
  14. 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?

  15. morcos force-pushed on Dec 9, 2015
  16. 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)

  17. 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.

  18. 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 ?

  19. 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.
  20. 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.

  21. 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.

  22. NicolasDorier commented at 6:23 AM on December 10, 2015: contributor

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

  23. NicolasDorier commented at 6:24 AM on December 10, 2015: contributor

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

  24. morcos force-pushed on Jan 14, 2016
  25. morcos commented at 10:35 PM on January 14, 2016: member

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

  26. morcos force-pushed on Jan 15, 2016
  27. morcos force-pushed on Feb 16, 2016
  28. 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.

  29. 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)

  30. 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.

  31. morcos force-pushed on Feb 17, 2016
  32. NicolasDorier commented at 6:11 AM on February 17, 2016: contributor

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

  33. morcos force-pushed on Feb 17, 2016
  34. morcos commented at 4:28 PM on February 17, 2016: member

    just changed a couple words in the comment

  35. 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.

  36. 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.

  37. laanwj added the label Needs backport on Feb 18, 2016
  38. sdaftuar commented at 6:02 PM on February 26, 2016: member

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

  39. 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

  40. 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?

  41. morcos commented at 9:30 PM on February 29, 2016: member

    comment nit addressed

  42. sipa commented at 5:24 AM on March 5, 2016: member

    Kicked Travis

  43. in src/txmempool.h:None 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.

  44. in src/txmempool.cpp:None 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?

  45. 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

  46. odinTy commented at 11:33 PM on March 5, 2016: none

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

  47. btcdrak commented at 11:09 AM on March 15, 2016: contributor

    utACK ddb4dab

  48. 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

  49. laanwj commented at 3:58 PM on March 16, 2016: member

    ut/code review ACK ddb4dab

  50. in src/txmempool.h:None 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

  51. jtimon commented at 4:12 PM on March 16, 2016: contributor

    Concept ACK, started reviewing more deeply.

  52. morcos commented at 4:39 PM on March 16, 2016: member

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

  53. Add LockPoints
    Obtain LockPoints to store in CTxMemPoolEntry and during a reorg, evaluate whether they are still valid and if not, recalculate them.
    982670c333
  54. morcos force-pushed on Mar 16, 2016
  55. morcos commented at 8:16 PM on March 16, 2016: member

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

  56. laanwj commented at 8:19 PM on March 16, 2016: member

    utACK 982670c

  57. laanwj merged this on Mar 16, 2016
  58. laanwj closed this on Mar 16, 2016
  59. laanwj referenced this in commit 14d6324a24 on Mar 16, 2016
  60. btcdrak commented at 8:56 PM on March 16, 2016: contributor

    @laanwj this PR has been backported in 7543.

  61. MarcoFalke removed the label Needs backport on Apr 25, 2016
  62. MarcoFalke commented at 1:35 PM on April 25, 2016: member

    Removed 'needs backport' label per previous comment

  63. MarkLTZ referenced this in commit 7425415619 on Apr 27, 2019
  64. MarcoFalke locked this on Sep 8, 2021
Contributors
morcosjtimonNicolasDoriersdaftuarbtcdraksipaodinTylaanwjMarcoFalke
Labels
FeatureMempool
Linked (view graph)
#7184 Implement SequenceLocks functions for BIP 68#7543 [0.12] Backport BIP9, BIP68 and BIP112 with softfork
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-04-22 12:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me