I've recently learned about a new Bitcoin node implementation in Rust called Bitcrust. They state that they have found a novel way of storing the Bitcoin blockchain as a "Spend tree" instead of tracking the UTXO set and claim to have significantly improved the performance of database interactions that way.

Can someone explain how the Bitcrust-db achieves that?

  • Did you ever find out? Nov 14 '18 at 9:48
  • @RedGrittyBrick: Sorry, haven't picked that question back up since.
    – Murch
    Nov 24 '18 at 16:14

My understanding after a quick look at the code is that they use this sequential scan of stacked records of spends only for the recent 3 blocks (https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L296)

If the sequential scan did not find a match (if the input is from older blocks), they use this huge 2^58-bit bitmap, that is sparsely mapped to sparse files (if the filesystem does not support sparse files, they will use 16GB of storage for each 'range' that contains at least one bit set)

the code that uses 58-bit index: https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_index.rs#L67 (more exactly, a 52-bit index to a map of U64 values)

the 'hash' variable there does not contain a true hash, it is just a mapping of the internal storage indexes to 58-bit value: https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L168

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.