Using Utreexo proofs to speed up IBD

[kcalvinalvin]

Problem:

The initial block download (IBD) is what all Bitcoin nodes do to sync up to the current Bitcoin's state. It involves downloading and verifying all the blocks in the Bitcoin blockchain. This process is slow and the main bottlenecks are the signature verification and the writing and reading utxos from disk.

Utreexo proof messages:

Since utreexo nodes do not have the UTXO set, it also does not locally store the UTXOs. But the UTXO data consisting of: height, isCoinBase, and pkscript MUST be provided to validate a given block. To do so, utreexo nodes receive this data through a p2p message called MsgUtreexoHeader and MsgUtreexoProof.

MsgUtreexoHeader consists of the following:

0: The bitcoin block hash this utreexo proof is proving
1: number of additional leaves getting added to this block
2: vector of positions that are getting removed on this block

MsgUtreexoProof consists of the following:

0: The bitcoin block hash this utreexo proof is proving
1: vector of hashes needed to hash the utxos to the utreexo roots
2: vector of LeafData which is: height, isCoinBase, and Pkscript (if not recoverable by the bitcoin block)

With this data + the data provided by the MsgUtreexoHeader, a utreexo node is able to generate the Utxo viewpoint at the block for the MsgUtreexoProof. And with this data the utreexo node is able to validate blocks in the same way the current bitcoin nodes validate a block.

How current nodes can have faster IBD with utreexo proof messages:

Since a utreexo proof message is the utxo viewpoint at a given block, a current node can use these utreexo proof messages to pre-load the utxo viewpoint needed at a future block. This both avoids the disk reads from the database and also makes the utxo set loading more concurrent. Since by default Bitcoin nodes do not validate signatures up to the assumevalid checkpoint during IBD, the biggest bottleneck is reading and writing to the disk for the utxo set. But with the utreexo proof messages, we can remove the bottleneck and greatly speed up IBD.

Details:

• The utreexo roots for all the blocks are committed in the binary. This allows for the verification of each utreexo proof msg possible ahead of time.