Replace FindLatestBefore used by importmuti with FindEarliestAtLeast.

gmaxwell commented at 7:23 am on January 8, 2017: contributor

In spite of the name FindLatestBefore used std::lower_bound to try to find the earliest block with a nTime greater or equal to the the requested value. But lower_bound uses bisection and requires the input to be ordered with respect to the comparison operation. Block times are not well ordered.

I don’t know what lower_bound is permitted to do when the data is not sufficiently ordered, but it’s probably not good. (I could construct an implementation which would infinite loop…)

To resolve the issue this commit introduces a maximum-so-far to the block indexes and searches that.

For clarity the function is renamed to reflect what it actually does.

An issue that remains is that there is no grace period in importmulti: If a address is created at time T and a send is immediately broadcast and included by a miner with a slow clock there may not yet have been any block with at least time T.

The normal rescan has a grace period of 7200 seconds, but importmulti does not.

gmaxwell commented at 7:32 am on January 8, 2017: contributor

Tag for 0.14 please. Comments on if we should do something about the lack of grace in importmulti?

This came up while I was reviewing #7871 and realized that an obvious use of it would be making sure that you only pruned after performing your relevant importmultis, so it’s important that we be able to prune and importmulti on the same basis. (also, looks like importmulti will crash on pruned nodes… but thats another issue.)

fanquake added this to the milestone 0.14.0 on Jan 8, 2017

fanquake added the label Validation on Jan 8, 2017

fanquake added the label Wallet on Jan 8, 2017

in src/validation.cpp: in 5d33f8b5cb outdated

2600@@ -2601,6 +2601,7 @@ CBlockIndex* AddToBlockIndex(const CBlockHeader& block)
2601         pindexNew->nHeight = pindexNew->pprev->nHeight + 1;
2602         pindexNew->BuildSkip();
2603     }
2604+    pindexNew->nTimeMax = (pindexNew->pprev ? std::max(pindexNew->pprev->nTimeMax, pindexNew->nTime) : pindexNew->nTime);

ryanofsky commented at 3:43 pm on January 9, 2017:

How does nTimeMax get assigned when the block index is loaded on startup? Do you need to add a similar assignment to LoadBlockIndexDB?

gmaxwell commented at 7:43 pm on January 9, 2017:

::facepalm:: fixed.

ryanofsky commented at 4:33 pm on January 11, 2017: member

Will need to rebase now that #7871 is merged (it added a new FindLatestBefore call)

gmaxwell commented at 10:06 pm on January 11, 2017: contributor

Rebased.

sipa commented at 10:14 pm on January 11, 2017: member

At least on x86_64 + glibc malloc, this does not actually increase memory usage.

jtimon commented at 11:18 pm on January 11, 2017: contributor

I can’t think of a better solution, but in principle it looks like introducing unsigned int CBlockIndex::nTimeMax should hurt in terms of memory. I didn’t tried sipa’s memory test though.

As an aside, I don’t really understand the recommended policy for choosing between unsigned int, uint_32t and uint_64t for class attributes.

gmaxwell commented at 0:57 am on January 12, 2017: contributor

I can’t think of a better solution, but in principle it looks like introducing unsigned int CBlockIndex::nTimeMax should hurt in terms of memory. I didn’t tried sipa’s memory test though.

It doesn’t increase the usage because the alignment requirements of the existing objects required padding.

sdaftuar commented at 2:52 am on January 12, 2017: member

ACK 336289e39285fcfdc80be969501e5db4cf35e1ae. Tested FindEarliestAtLeast() with a unit test here: 3e1f59823f572b71359884487bdc273dbab0eadf

laanwj commented at 11:17 am on January 12, 2017: member

utACK 336289e, will merge after pull 3e1f598 into this.

Replace FindLatestBefore used by importmuti with FindEarliestAtLeast.

In spite of the name FindLatestBefore used std::lower_bound to try
 to find the earliest block with a nTime greater or equal to the
 the requested value.  But lower_bound uses bisection and requires
 the input to be ordered with respect to the comparison operation.
 Block times are not well ordered.

I don't know what lower_bound is permitted to do when the data
 is not sufficiently ordered, but it's probably not good.
 (I could construct an implementation which would infinite loop...)

To resolve the issue this commit introduces a maximum-so-far to the
 block indexes and searches that.

For clarity the function is renamed to reflect what it actually does.

An issue that remains is that there is no grace period in importmulti:
 If a address is created at time T and a send is immediately broadcast
 and included by a miner with a slow clock there may not yet have been
 any block with at least time T.

The normal rescan has a grace period of 7200 seconds, but importmulti
 does not.

997a98a674

Add unit test for FindEarliestAtLeast 4b06e41c30

gmaxwell commented at 2:25 pm on January 12, 2017: contributor

@laanwj Pulled it in. @sdaftuar Thank you so much for the test!

morcos commented at 6:52 pm on January 12, 2017: member

utACK @gmaxwell +1 on adding a grace period. I can’t really imagine any downside to and only annoying hard to debug potential issues if we don’t.

sipa commented at 11:45 pm on January 13, 2017: member

utACK 4b06e41c309123c4eefce0d3578c01efe1ae10df

sipa merged this on Jan 14, 2017

sipa closed this on Jan 14, 2017

sipa referenced this in commit e126d0c12c on Jan 14, 2017

ryanofsky commented at 3:36 pm on February 14, 2017: member

An issue that remains is that there is no grace period in importmulti: If a address is created at time T and a send is immediately broadcast and included by a miner with a slow clock there may not yet have been any block with at least time T.

The normal rescan has a grace period of 7200 seconds, but importmulti does not.

This is not actually true. There is a check in importmulti that appears to skip rescan if the lowest imported key timestamp is higher than the highest blocktime:

https://github.com/bitcoin/bitcoin/blob/ec66d06e6ef38b4c2cf2246ba2eeb3d17a6040e5/src/wallet/rpcdump.cpp#L1051

But this check doesn’t actually do anything, because of the way the lowest key timestamp is initialized

https://github.com/bitcoin/bitcoin/blob/ec66d06e6ef38b4c2cf2246ba2eeb3d17a6040e5/src/wallet/rpcdump.cpp#L1023

I made a change in #9760 to just drop this check since it doesn’t do anything. An alternative would be to initialize nLowestTimestamp to numeric_limits<int64_t>::max() so the check does what it appears to do, and then add a grace period.

ryanofsky commented at 3:50 pm on February 14, 2017: member

The normal rescan has a grace period of 7200 seconds, but importmulti does not.

This is not actually true.

Actually it is true. @morcos pointed out the lack of grace period wasn’t in the GetBlockTimeMax comparison, but in the FindEarliestAtLeast call. I can make another PR to add a grace period to that call.

ryanofsky referenced this in commit 34cafb1204 on Feb 14, 2017

ryanofsky commented at 11:07 pm on February 14, 2017: member

Added grace period in #9761.

ryanofsky referenced this in commit 2e85d08d0f on Feb 15, 2017

ryanofsky referenced this in commit f50f40331a on Feb 15, 2017

ryanofsky referenced this in commit e662af3583 on Feb 16, 2017

codablock referenced this in commit fa58a20e8d on Jan 19, 2018

codablock referenced this in commit 813e14efe0 on Jan 20, 2018

codablock referenced this in commit ad9b9251ac on Jan 21, 2018

HashUnlimited referenced this in commit 917b721761 on Feb 27, 2018

lateminer referenced this in commit 25aef2b2cb on Jan 4, 2019

andvgal referenced this in commit 27795623df on Jan 6, 2019

CryptoCentric referenced this in commit 374bd739e3 on Feb 27, 2019

CryptoCentric referenced this in commit e11d1ae195 on Feb 27, 2019

furszy referenced this in commit a279df6e61 on Apr 6, 2021

DrahtBot locked this on Sep 8, 2021

Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. #9490