Do not store Merkle branches in the wallet.

sipa commented at 7:13 pm on August 11, 2015: member

Assume that when a wallet transaction has a valid block hash and transaction position in it, the transaction is actually there. We’re already trusting wallet data in a much more fundamental way anyway.

To prevent backward compatibility issues, a new record is used for storing the block locator in the wallet. Old wallets will see a wallet file synchronized up to the genesis block, and rescan automatically.

Fixes #6536 using a suggestion by @jonasschnelli to retain backward compatibility.

dcousens commented at 0:53 am on August 12, 2015: contributor

utACK

in src/primitives/block.cpp: in 7cb0da3d44 outdated

14@@ -15,7 +15,7 @@ uint256 CBlockHeader::GetHash() const
15     return SerializeHash(*this);
16 }
17 
18-uint256 CBlock::BuildMerkleTree(bool* fMutated) const
19+uint256 CBlock::ComputeMerkleRoot(bool* fMutated) const

dcousens commented at 0:55 am on August 12, 2015:

Unrelated to this PR, but is there any reason we prefer the optional arguments compared to a tuple return value?

laanwj commented at 7:36 am on August 12, 2015:

I’m not sure this is so much “preferred”, it’s how it happens to be written between two more-or-less equivalent ways to formulate it.

sipa commented at 6:34 pm on August 12, 2015:

You’re relying on an optional optimization allowed by the C++ standard (copy elision) to avoid constructing a tuple as a temporary and copying it to the return location. In C++11 it’s better because you can explicitly indicate move semantics.

in src/wallet/wallet.cpp: in 7cb0da3d44 outdated

2835@@ -2841,11 +2836,9 @@ int CMerkleTx::GetDepthInMainChainINTERNAL(const CBlockIndex* &pindexRet) const
2836         return 0;
2837 
2838     // Make sure the merkle branch connects to this block
2839-    if (!fMerkleVerified)
2840+    if (nIndex == -1)

dcousens commented at 0:58 am on August 12, 2015:

Why is this added? Its already done above in:

0 if (hashBlock.IsNull() || nIndex == -1)
1         return 0;

Or is nIndex somehow modified elsewhere?

jonasschnelli commented at 7:12 pm on August 12, 2015:

Yes. I think this check can be removed completely.

sipa commented at 7:14 pm on August 12, 2015:

Indeed. I missed it was already checked.

sipa commented at 4:15 pm on September 7, 2015:

Fixed.

laanwj commented at 7:37 am on August 12, 2015: member

Concept ACK.

laanwj added the label Wallet on Aug 12, 2015

jtimon commented at 9:21 am on August 12, 2015: contributor

Concept ACK

sipa commented at 6:42 pm on August 12, 2015: member

This needs testing :)

jonasschnelli commented at 6:46 pm on August 12, 2015: contributor

Concept ACK. Started testing…

jonasschnelli commented at 7:51 pm on August 12, 2015: contributor

Tested ACK (lldb stepped; update of “old” wallet.dat works). Played around with some huge regtest wallets/chains. Moved wallet.dat back and forth from master bitcoin-core to master+this PR bitcoin-core.

I think this is a step forward. IMO it’s totally sufficient to check if a wtx has a valid block in the active chain and the wtx transaction index matches the position in the block.

Next step could be to simplify the height calculation. GetDepthInMainChainINTERNAL() is very ineffective and holds cs_main because it accesses mapBlockIndex. Calculating balance, UI listing of transactions will call GetDepthInMainChainINTERNAL() for each wallet transaction (! and it even gets called when the credit of a wtx is cached).

I think a height cache would perform better (together with a invalidating option down to a certain height in case of a reorg).

sipa commented at 8:04 pm on August 12, 2015: member

Thanks for testing! @jonasschnelli No need for a height cache, just a cached chainActive.Tip() inside the wallet suffices (you can do ancestor-of checks without cs_main). I can do that, but it’s not for this PR.

theuni commented at 8:07 pm on August 12, 2015: member

This will cause the merkle tree to be calculated at least 3x per accepted block, as far as I can see: ProcessNewBlock -> CheckBlock ProcessNewBlock -> AcceptBlock -> CheckBlock ProcessNewBlock -> ActivateBestChain -> … ConnectBlock -> CheckBlock

Is the calculation time significant enough to try to skip some of that?

sipa commented at 8:09 pm on August 12, 2015: member

@theuni Ugh, that’s bad. No, it won’t make up for that. We should avoid doing those duplicated checks.

theuni commented at 8:37 pm on August 12, 2015: member

@sipa If I’m reading correctly, it looks like the CheckBlock() in AcceptBlock() is safe to use !fCheckMerkleRoot since it’s only ever called from ProcessNewBlock() where it’s already been checked.

Same for the ConnectBlock() in ConnectTip(), since they’re already checked before writing to disk. That seems a bit more risky, but surely a bad/corrupt read would be detected long before that point anyway?

sipa commented at 4:20 pm on August 13, 2015: member

I guess we want to verify the merkle root any time 1) we receive new block date 2) read block data back from this.

If the functions who do that always verify, and there is no other way to construct a full CBlock, I think we’re good.

sipa commented at 9:34 pm on August 15, 2015: member

@theuni It looks a bit more complicated, as currently we do a CheckBlock on blocks read from disk for validation, which would be harder to do if we want to avoid duplicate checks. I’ve made a much simpler (and slightly uglier) change for now here, which is to cache the result of CheckBlock in CBlock. That also avoids a few other checks that were being done 3 times before.

gmaxwell commented at 8:33 am on September 6, 2015: contributor

Where does this stand right now? Should I spend cycles testing it as is?

sipa force-pushed on Sep 7, 2015

sipa commented at 4:17 pm on September 7, 2015: member

@gmaxwell Test away.

sipa force-pushed on Sep 7, 2015

sipa commented at 10:38 pm on September 14, 2015: member

Ping

in src/main.cpp: in c7efe04a03 outdated

2575@@ -2573,7 +2576,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
2576     // Check the merkle root.
2577     if (fCheckMerkleRoot) {
2578         bool mutated;
2579-        uint256 hashMerkleRoot2 = block.BuildMerkleTree(&mutated);
2580+        uint256 hashMerkleRoot2 = block.ComputeMerkleRoot(&mutated);

dcousens commented at 10:46 pm on September 14, 2015:

const?

sipa commented at 4:51 pm on September 22, 2015:

const what?

dcousens commented at 10:46 pm on September 14, 2015: contributor

re-utACK

Do not store Merkle branches in the wallet.

Assume that when a wallet transaction has a valid block hash and transaction position
in it, the transaction is actually there. We're already trusting wallet data in a
much more fundamental way anyway.

To prevent backward compatibility issues, a new record is used for storing the
block locator in the wallet. Old wallets will see a wallet file synchronized up
to the genesis block, and rescan automatically.

391dff16fe

Avoid duplicate CheckBlock checks 3b33ec85ed

sipa commented at 4:51 pm on September 22, 2015: member

Rebased.

sipa force-pushed on Sep 22, 2015

in src/primitives/block.h: in 3b33ec85ed

77@@ -78,7 +78,7 @@ class CBlock : public CBlockHeader
78     std::vector<CTransaction> vtx;
79 
80     // memory only
81-    mutable std::vector<uint256> vMerkleTree;
82+    mutable bool fChecked;

laanwj commented at 4:39 pm on September 23, 2015:

Ideally we’d have this fChecked status (which isn’t used in CBlock itself) on an administrative object that wraps a CBlock, instead of on CBlock itself.

sipa commented at 4:49 pm on September 23, 2015:

Fully agree, I actually started implementing that as a follow-up, but didn’t want to interfere with other refactorings.

laanwj commented at 4:55 pm on September 23, 2015:

OK, yes, I’m fine with keeping it like this for this pull

laanwj commented at 5:35 pm on September 23, 2015: member

Tested forward/backward compatibility of wallet with this code change. ACK.

laanwj merged this on Sep 23, 2015

laanwj closed this on Sep 23, 2015

laanwj referenced this in commit 5b77244c60 on Sep 23, 2015

Warrows referenced this in commit 940acf7635 on Jul 20, 2019

Warrows referenced this in commit 6c3e2ac15a on Jul 28, 2019

Warrows referenced this in commit 64f8c3f013 on Aug 4, 2019

Warrows referenced this in commit 8fd71ed6fe on Sep 11, 2019

Warrows referenced this in commit fe5a571cf2 on Sep 23, 2019

Warrows referenced this in commit 5447622a03 on Oct 9, 2019

random-zebra referenced this in commit 0f1764a3db on Oct 9, 2019

CaveSpectre11 referenced this in commit bf78c74c98 on Dec 14, 2019

wqking referenced this in commit d07f290acf on May 24, 2020

Kokary referenced this in commit befad91c2c on May 26, 2020

Kokary referenced this in commit c7eb9a3ac1 on Nov 13, 2020

Kokary referenced this in commit e7f65aae8a on Nov 17, 2020

Kokary referenced this in commit 192c41eae6 on Nov 17, 2020

KolbyML referenced this in commit 0ac446d8b2 on Nov 21, 2020

Kokary referenced this in commit f911b18370 on Nov 24, 2020

Cryptarchist referenced this in commit 2aea303109 on Nov 30, 2020

zkbot referenced this in commit 79c785d1f9 on Apr 20, 2021

MarcoFalke locked this on Sep 8, 2021

Do not store Merkle branches in the wallet. #6550