search

bcoin-org / bcoin

Javascript bitcoin library for node.js and browsers
https://bcoin.io
Other
3.01k stars 809 forks source link

Missing transactions during block scan/rescan from a BIP44 seed for a SPV Wallet and Full Wallet Node #835

Open braydonf opened 5 years ago

braydonf commented 5 years ago

Versions: bcoin v1.0.2 (possibly early too) and above to v2.0.0-dev

Expected:

All transactions are added to the wallet after the initial block chain download for a wallet that is given a mnemonic phrase. This is specific to an SPV Wallet as well as a full node wallet when running as a separate process, a Wallet Node.

Unaffected:

A full node with the wallet as a plugin is not affected by this bug.

Reproduce:

  1. Create a 'regtest' chain and send more than the lookahead value for the wallet (e.g. 10) transactions to the wallet. This could be over 10+ blocks, or more frequent, such as 10+ within a single block.
  2. Create a new SPV node wallet using the wallet seed, or a full node wallet running as a separate process (eg. Wallet Node).
  3. Have the wallet sync with the chain.
  4. There will be missing transactions.

Explanation:

This bug is due to a timing issue with the bloom filter used in BIP37.

A block is downloaded using a filter, and as that block is processed there are new addresses added to the filter using the lookahead value. There could be transactions in that block with those new addresses, however the block was not filtered with the new filter. It's then necessary to request the block again using the updated filter, during the initial sync.

That same issue can apply to following blocks if the filter is not updated before a block is downloaded. It's very slow to synchronize an SPV wallet without asking for multiple blocks at a time in the getdata request. Thus it's necessary to not only request the same block again, but any blocks that follow it. It's necessary to re-request a block and those following it anytime block receives a transaction (as it increases the lookahead). This approach is how both bitcoinj and breadwallet have worked around this problem:

From breadwallet:

  • if at any point tx messages consume enough wallet addresses to drop below the bip32 chain gap limit, more addresses are generated and local peer sends filterload with an updated bloom filter
  • after filterload is sent, getdata is sent to re-request recent blocks that may contain new tx matching the filter

https://github.com/breadwallet/breadwallet-core/blob/8eb05454df3e2d5cca248b4e24eeffa420c97e3a/bitcoin/BRPeer.c#L83-L85

From bitcoinj:

Yes, so we must abandon the attempt to process this block and any further blocks we receive, then wait for the Bloom filter to be recalculated, sent to this peer and for the peer to acknowledge that the new filter is now in use (which we have to simulate with a ping/pong), and then we can safely restart the chain download with the new filter that contains a new set of lookahead keys.

https://github.com/bitcoinj/bitcoinj/blob/806afa04419ebdc3c15d5adf065979aa7303e7f6/core/src/main/java/org/bitcoinj/core/Peer.java#L1076-L1079

Solution:

I think the solution to this issue is to switch entirely to client-side filter as defined in BIP157/BIP158, and deprecate BIP37.

In that case a block will no-longer need to be re-requested multiple times each the filter is updated. The wallet can determine the additional transactions that match within the block without it being necessary for additional requests. All matching blocks can be downloaded in sets with getdata requests, in parallel, without any need to make additional requests following filter updates.

An intermediate solution can be to implement a similar approach as bitcoinj and breadwallet.

Thanks @pinheadmz in help with identifying the bug and additional information.

pinheadmz commented 5 years ago

This is a great writeup. SPV leaks more privacy, but still has other benefits over Neutrino. SPV uses less bandwidth, memory and disk space. There may be bcoin users for a long time willing to make this tradeoff for a lighter client.

For the Wallet Node construction, would we store a few recent blocks in memory? Would receiving a tx (and generating a new address) trigger a (client-side) rescan of any recent blocks?

braydonf commented 5 years ago

SPV uses less bandwidth

To be clear, you mean BIP37? I actually don't think this claim can still be made in a meaningful way, given the great inefficiencies of the additional requests to re-request blocks and the filter updates.

braydonf commented 5 years ago

There is more rationale for deprecation of BIP37 (in addition to weak privacy):

pinheadmz commented 5 years ago

Yeah BIP37. If blocks are 2-3 MB, sparse wallets would definitely be consuming more bandwidth (download a full block from at least one peer just to discover a single 200 byte transaction). But I see your point that a denser wallet with dozens of transactions in a single [merkle]block, requiring multiple re-requests could top that.

braydonf commented 5 years ago

A wallet that doesn't receive many transactions, won't be receiving many blocks, so it is fairly moot. There are greater uses of bandwidth, application updates could exceed the value.

To conserve bandwidth for mempool and unconfirmed transactions, it could only request txs when the application in active and not in the background.

braydonf commented 5 years ago

A wallet rescan is also affected by this bug, unless no new keys are derived in the process of rescanning blocks. The same filter is used across multiple blocks in chaindb.scan that is called from the walletdb scan and rescan

braydonf commented 5 years ago

This issue has been fixed in the https://github.com/bcoin-org/bcoin/tree/chain-expansion branch.