<p>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 (<a href="https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L296" rel="nofollow noreferrer">https://github.com/tomasvdw/bitcrust/blob/556375ccfaa81ca241b25f7b5b7f00fb97d5bd6b/src/store/spend_tree/record.rs#L296</a>)</p>

<p>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)</p>

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

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

CC BY-SA 4.0
2018-12-11T17:56:44.730Z
2018-12-11T17:56:44.730Z
Dmitry Petukhov
<p>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. </p>

<p>Can someone explain how the <a href="https://github.com/tomasvdw/bitcrust/blob/master/doc/bitcrust-db.md" rel="nofollow noreferrer">Bitcrust-db</a> achieves that?</p>

CC BY-SA 4.0
2018-11-14T09:48:36.463Z
Did you ever find out?
RedGrittyBrick
CC BY-SA 4.0
2018-11-24T16:14:37.913Z
@RedGrittyBrick: Sorry, haven't picked that question back up since.
Murch
<database><utxo-set>
How does the new database design used by Bitcrust work?
Murch
# How does the new database design used by Bitcrust work?

(Asked by: username_0 on 2017-06-18)

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](https://github.com/tomasvdw/bitcrust/blob/master/doc/bitcrust-db.md) achieves that?

**Tags:** database, utxo-set

> **Comments:**
> **username_1**: Did you ever find out?  
> **username_0**: @username_1: Sorry, haven't picked that question back up since.  

---

## 1 answers

### Answer by username_2 on 2018-12-11. Score: 1 | Accepted answer

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>


---

