Get rid of stored merkle branches

sipa commented at 8:39 pm on September 15, 2014: member

Do not store merkle branches inside the wallet. This means removing the check that someone might have inserted an unconfirmed transaction in your wallet and making it look like a confirmed one.

This means we don’t need to keep the merkle branch in wallets (which takes up to half a kilobyte per transactions), we don’t need to validate it (which requires a dozen sha256 operation per wallet transaction), remove the need to keep the merkle tree in blocks (the case where it’s needed is done separately in CPartialMerkleTree), and simplifies the merkle root computation.

This may be controversial, as it weakens the security assumption slightly, but simplifies the code.

sipa renamed this:
~~Get rid of stored merkle branches.~~
Get rid of stored merkle branches
on Sep 15, 2014

christophebiocca commented at 8:47 pm on September 15, 2014: none

This means removing the check that someone might have inserted an unconfirmed transaction in your wallet and making it look like a confirmed one.

Just for clarity, are we talking about someone with write access to the wallet file?

sipa force-pushed on Sep 15, 2014

theymos commented at 1:03 am on September 16, 2014: none

Satoshi intended the Merkle branches to be useful if one day a super-lightweight mode of Bitcoin never downloaded blocks at all. I think that the idea was that these lightweight nodes would send the input transactions and their Merkle branches along with any sent transactions to prove to other lightweight nodes that the transaction is OK, and then the recipient would download full Merkle trees for the next few blocks and save the appropriate branches.

I guess that something like this isn’t planned for Bitcoin Core anymore, but I suspect that the branches may still be useful for something in the future. They allow you to prove that a wallet transaction is in the main chain without making the recipient of the proof download anything but headers, which seems potentially useful. Maybe someone else knows of some specific use-cases. (Perhaps this doesn’t justify keeping them now, since they could be added again later if they’re actually needed.)

laanwj added the label Wallet on Sep 16, 2014

dgenr8 commented at 3:19 pm on September 16, 2014: contributor

@mikehearn as someone invested in both, any comment on how this would affect core wallet in a comparison to bitcoinj-based wallets?

mikehearn commented at 3:37 pm on September 16, 2014: contributor

bitcoinj doesn’t store merkle branches for transactions in its wallet. Exactly why the Bitcoin Core wallet does is one of the codebase’s many mysteries, I’ve never located a use case for this data. Proving a transaction exists can be useful in some specialised protocols but because you have no idea if the outputs are spent or not, it ends up being not that useful.

jgarzik commented at 3:51 pm on September 16, 2014: contributor

Proof-of-TX-existence in this manner is useful for embedding block headers of side chains, and then proving that with another lightweight client. It is useful for more generic timestamping applications outside the currency realm.

sipa commented at 4:20 pm on September 16, 2014: member

As long as we don’t prune the full blockchain, the merkle branches can always be recreated (we store the index into the block still with this PR), and if there’s a need for providing such branches to some peers, we can always add the code back.

Also, even if we want to turn the Bitcoin Core wallet into SPV, this is not necessary. You verify the branches when received, and don’t accept it into the wallet if it’s wrong.

The only downside is someone with offline write access to the wallet could introduce a fake transaction and make it look confirmed.

mikehearn commented at 4:32 pm on September 16, 2014: contributor

Yes indeed. The logic for removing it is sound.

sipa commented at 4:55 pm on September 16, 2014: member

Oh, this also makes the wallet file incompatible with older releases, as they will consider all transactions as unconfirmed (as if they were “injected”), but for a major release like 0.10 that is probably acceptable.

laanwj commented at 6:47 am on September 17, 2014: member

If we are to break the wallet format in an incompatible way, I’d rather do it once and switch to a better format which is, for example, not reliant on berkeleydb.

I like cleaning up unused code, but I can see this causing user frustration and support work for very little gain.

cozz commented at 1:39 am on September 18, 2014: contributor

I vote for merging this, I was always wondering about those merkle branches…

As for incompatibility, isn’t this what minVersion is there for? So that the users will get this error message: “Error loading wallet.dat: Wallet requires newer version of Bitcoin Core”. The code comments say, we already did that in the past with 0.4.0 and 0.6.0.

laanwj commented at 7:42 am on September 18, 2014: member

I’ve been thinking about this. In principle the transactions in the wallet aren’t very important, they can always be reconstructed (ie, through zapwallettxes). So this provides a downgrade possibility, it just has to be documented in the release notes.

petertodd commented at 6:05 pm on September 18, 2014: contributor

@jgarzik For instance I was looking into using CMerkleTx for a colored coin library I’m working on. However it looks like using CMerkleBlock is strictly superior due to the increased efficiency when multiple transactions in the same block needed to be proved.

re: this pull-req, I have no strong opinions one way or the other, although if it ain’t broke, don’t fix it…

TheBlueMatt commented at 8:22 pm on September 18, 2014: member

I would very much like to see this merged…but I have to agree with @laanwj…if we’re gonna break wallet compat, we should really break wallet compat (which needs to happen eventually anyway, preferably sooner rather than later).

Get rid of stored merkle branches.

Do not store merkle branches inside the wallet. This means removing the check
that someone might have inserted an unconfirmed transaction in your wallet and
making it look like a confirmed one.

This means we don't need to keep the merkle branch in wallets (which takes up to
half a kilobyte per transactions), we don't need to validate it (which requires
a dozen sha256 operation per wallet transaction), remove the need to keep the
merkle tree in blocks (the case where it's needed is done separately in
CPartialMerkleTree), and simplifies the merkle root computation.

a6b1443e3f

sipa force-pushed on Sep 22, 2014

BitcoinPullTester commented at 8:13 pm on September 22, 2014: none

Automatic sanity-testing: FAILED BUILD/TEST, see http://jenkins.bluematt.me/pull-tester/p4925_a6b1443e3f48f2a43c4746c2bb1e950858d6aa36/ for binaries and test log.

This could happen for one of several reasons:

It chanages paths in makefile.linux-mingw or otherwise changes build scripts in a way that made them incompatible with the automated testing scripts (please tweak those patches in qa/pull-tester)
It adds/modifies tests which test network rules (thanks for doing that), which conflicts with a patch applied at test time
It does not build on either Linux i386 or Win32 (via MinGW cross compile)
The test suite fails on either Linux i386 or Win32
The block test-cases failed (lookup the first bNN identifier which failed in https://github.com/TheBlueMatt/test-scripts/blob/master/FullBlockTestGenerator.java)

If you believe this to be in error, please ping BlueMatt on freenode or TheBlueMatt here.

This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

sipa commented at 2:33 am on October 2, 2014: member

Needs significant changes now, closing. I may redo after #4926.

sipa closed this on Oct 2, 2014

MarcoFalke locked this on Sep 8, 2021

Get rid of stored merkle branches #4925