Fast parallel block validation without UTXO-index

[tomtomtom7]

I have build a storage engine as the core of a new Bitcoin Node in development. The idea is to abandon the UTXO index and use a fast concurrent spend tree instead.

The results are very promising. Further information is here: https://bitcrust.org

Performance results: https://bitcrust.org/results

Source code in Rust is available at https://github.com/tomasvdw/bitcrust

[piotr_n]

How much memory and disk space does it need?

Do you keep it all in files on disk?

If you get to verify a transaction (block) that tries to spend an unexisting output, do you have to go back through all the files just to find out that it doesn't exist?

[tomtomtom7]

Current usage:

1.3G   ../data-cmp/block-index
5.6G   ../data-cmp/spend-tree
41M   ../data-cmp/headers
25G   ../data-cmp/transactions2
196M   ../data-cmp/spend-index
3.6G   ../data-cmp/tx-index
85G   ../data-cmp/transactions1
119G   ../data-cmp/

But this can be pruned, just like with Core.

As for memory, this uses memory mapped files which means lots of virtual memory, but leave it to the OS to swap. By using proper locality of reference, the data that isn't used is kept out of memory.

The problem of spending early outputs is solved by the spend-index, which lags behind the tips a few blocks to catch these. This is also explained under the "spend-index" section on the site.

[piotr_n]

The problem of spending early outputs is solved by the spend-index, which lags behind the tips a few blocks to catch these. This is also explained under the "spend-index" section on the site.

Ok. But what about outputs that never existed in the first place. How do you find that they don't exist?

[tomtomtom7]

Ok. But what about outputs that never existed in the first place. How do you find that they don't exist?

The spend tree is scanned; if the output is found it is a double spent, if the corresponding transaction is spent it is ok, and if nothing is found it is spending a non-existing output.

Similarly, if the spend-index "catches" the search, two lookups are done: presence of the transaction and absence of the output.

The 'cheat' of spending an output of an existing transaction with an index higher then the output count is caught by script validation.

[cryptoanarchist]

Does this make SegWit obsolete?

[misterbigg]

Does this make SegWit obsolete?

No, it just improves the performance of common operations when validating transactions and blocks. Which is very helpful since it lowers the costs of operating a full node. In other words, it increases decentralization (we like that).

I read the entire document, clearly these folks have some skills!

[piotr_n]

As much as I like out of the box approaches to topics that interest me, to be honest I don't think this one can improve the overall speed of "common operations when validating transactions and blocks".

The UTXO index is there for a reason.
Personally I'd rather see some work on improving the index and the UTXO-db itself, rather than getting rid of it, which I think is not the right way to go.

Looking at the "performance results" one must remember that core (and the leveldb solution) use a limited amount of system memory, while this solution seems to be using all of it. Also, when the core gets to verify a transaction that is trying to spend a non-existing input, it won't consume so much resources. This is a potential DoS problem.

Sorry, I don't mean to be a mean person - it's just my cold professional opinion that it won't work well for you, for an actual real bitcoin node.
I wish you all the best with your project, @tomtomtom7, but I don't think this is a proper approach to optimise the performance.

[tomtomtom7]

Thanks for your feedback.

The UTXO index is there for a reason.
Personally I'd rather see some work on improving the index and the UTXO-db itself, rather than getting rid of it, which I think is not the right way to go.

I see the UTXO approach actually as a left over from the architecture before Compact-Blocks/XThin.

If all transaction are pre-synchronized, we can distinguish base load script validation (when a tx comes in) and peak load order validation (when a block comes), the UTXO-index doesn't make all that much sense.

This is because for script validation, when output scripts are needed the distinction between spent and unspent doesn't really exists as it can be spent on one branch and not spent on another. Using a transactionally maintained UTXO index there   only complication things (with reorgs).

And for order validation, the output scripts are not needed at all.

Looking at the "performance results" one must remember that core (and the leveldb solution) use a limited amount of system memory, while this solution seems to be using all of it.

I don't really think this is the case. Bitcrust uses memory mapped pages which show up as lots of virtual memory, but are swapped by the OS as needed. If instead you just traditional disk IO, the data is cached by the OS as needed.

Either way, MRU pages are kept  in memory.

Also, when the core gets to verify a transaction that is trying to spend a non-existing input, it won't consume so much resources. This is a potential DoS problem.

It is never needed to scan the entire chain as after a few blocks the spend-index catches a seek and performs a direct lookup. There may still be potential DoS problems, but not with spending a non-existing output.

[piotr_n]

Oh, ok. Sorry, I didn't get the spend-index idea at first.

Can you please say something more about how it actually works inside?

This is a very compact bit index with one bit for each transaction and one for each output

[gmaxwell]

I see the UTXO approach actually as a left over from the architecture before Compact-Blocks/XThin.

If all transaction are pre-synchronized,

Point of fact: transactions being validated in advance has always been true and is completely orthogonal with compact blocks.  Bitcoin has also directly exploited this fact via signature caching (which your benchmarks disables, btw, because you use the undocumented blocks only mode) since applying Satoshi's patch for it in May 2012, and further with the input cache since July 2012.

I've seen Peter R make the same argument a couple times and I've asked him why he presents it that way but AFAIR he has never responded to one of those messages.

[tomtomtom7]

I see the UTXO approach actually as a left over from the architecture before Compact-Blocks/XThin.

If all transaction are pre-synchronized,

Point of fact: transactions being validated in advance has always been true and is completely orthogonal with compact blocks.  Bitcoin has also directly exploited this fact via signature caching (which your benchmarks disables, btw, because you use the undocumented blocks only mode) since applying Satoshi's patch for it in May 2012, and further with the input cache since July 2012.

I've seen Peter R make the same argument a couple times and I've asked him why he presents it that way but AFAIR he has never responded to one of those messages.

I understand Core  pre validates signatures with our without Compact Blocks/XThin. I also understand the benches aren't comparing this, but only compare full block verification which I explain on that very page.

But without Compact Blocks/XThin, optimizing for order comparison is a a lot less relevant because of the high bandwidth cost.

[tomtomtom7]

Oh, ok. Sorry, I didn't get the spend-index idea at first.

Can you please say something more about how it actually works inside?

I essentially transform transactions and outputs to a "hash" with:

Code:

hash(tx) = tx.filepos / 16
hash(output) = tx.filepos / 16 + 1 + output-index

(guarded for exceptional overflows by a (now empty) map of exceptions for if output-count +1> tx-size/16)

And use the "hash" as a direct index in the bit-index.

The spend-index represents the spent state a few blocks from the tip; a set bit at a location means the transaction exists there or an output is spent there. When the spend tree is searched and reaches the position spend-index, a positive lookup for transaction and a negative lookup for  output is enough.

The spent index grows with 1 bit per every every 16 bytes, or 1/128th of the blockchain size. Just like with the spend-tree, mostly the end is accessed, so the start can be kept on disk.

Code of the spend-index itself is pretty simple here: https://github.com/tomasvdw/bitcrust/blob/master/src/store/spend_index.rs

[piotr_n]

I essentially transform transactions and outputs to a "hash" with:

Code:

hash(tx) = tx.filepos / 16
hash(output) = tx.filepos / 16 + 1 + output-index

(guarded for exceptional overflows by a (now empty) map of exceptions for if output-count +1> tx-size/16)

And use the "hash" as a direct index in the bit-index.

The spend-index represents the spent state a few blocks from the tip; a set bit at a location means the transaction exists there or an output is spent there. When the spend tree is searched and reaches the position spend-index, a positive lookup for transaction and a negative lookup for  output is enough.

The spent index grows with 1 bit per every every 16 bytes, or 1/128th of the blockchain size. Just like with the spend-tree, mostly the end is accessed, so the start can be kept on disk.

Code of the spend-index itself is pretty simple here: https://github.com/tomasvdw/bitcrust/blob/master/src/store/spend_index.rs

I honestly can't say that I understand half of what you've said.
But I'm trying.

Let's say you receive a new transaction and you have to verify it.
All you know is that it spends one output described as TXID-VOUT.

Correct me if I'm wrong: first you go through the last X blocks up the spend tree trying to find TXID there.
But say the TXID wasn't there - so then you have to go to the spend-index, right?

Now, how do you look for the TXID inside the spend-index?
How do you transform the TXID into the hash?

[piotr_n]

I think I get it.

So you basically extract all the transactions from the blocks and store them in a separate files (transactions1+transactions2), giving each transaction a unique sequencional "numeric index".

Then you have the index file (tx-index) where each different TXID points to the "numeric index" - that's actually your equivalent of UTXO-index, except that it includes also spent transactions.

And then you have the spend-index (addressed by the "numeric index") which basically tells you whether a specific output of a specific transaction has been spent.

Is that correct?

[piotr_n]

So you basically extract all the transactions from the blocks and store them in a separate files (transactions1+transactions2), giving each transaction a unique sequencional "numeric index".

Then you have the index file (tx-index) where each different TXID points to the "numeric index" - that's actually your equivalent of UTXO-index, except that it includes also spent transactions.

And then you have the spend-index (addressed by the "numeric index") which basically tells you whether a specific output of a specific transaction has been spent.

Is that correct?

I guess that means 'yes'.

In which case I can give a more accurate feedback.

First of all, you did not get rid of UTXO-index.
You still have it.
You just extended it into TXO-index meaning that you index not only unspent transactions, but also the spent ones.


Now, how is it possible that your code performs better than the leveldb solution used by core..?

It has nothing to do with any "fast concurrent spend tree".
It has all to do with the (U)TXO index itself.
You use a hashmap as the index, which is much faster than the index used by core's leveldb engine.
But it also takes much more system memory.

I know, because I also use hashmap based UTXO index in my gocoin s/w.
So you don't have to tell me that it's much faster.
But it comes at the cost of the memory - you can't run this with e.g. 2GB of RAM.
From my personal experience I'd say you need at least 8GB.
And because you index both; spent and unspent transactions, you need even more memory than the UTXO-index solution, which you are trying to beat.

The bottom line is: no way this can perform better than a simple hashmap based UTXO-index.

[piotr_n]

And because you index both; spent and unspent transactions, you need even more memory than the UTXO-index solution, which you are trying to beat.

The bottom line is: no way this can perform better than a simple hashmap based UTXO-index.

Let me add some numbers here.

At this moment (block 461402) a typical UTXO index has 20438271 records (transactions) - that's 20 millions.
In the meantime a TXO index used by your solution needs more than 210 millions of records.
https://blockchain.info/charts/n-transactions-total

[tomtomtom7]

So you basically extract all the transactions from the blocks and store them in a separate files (transactions1+transactions2), giving each transaction a unique sequencional "numeric index".

Then you have the index file (tx-index) where each different TXID points to the "numeric index" - that's actually your equivalent of UTXO-index, except that it includes also spent transactions.

And then you have the spend-index (addressed by the "numeric index") which basically tells you whether a specific output of a specific transaction has been spent.

Is that correct?

Yes. Though you leave out the spend-tree.

First of all, you did not get rid of UTXO-index.
You still have it.
You just extended it into TXO-index meaning that you index not only unspent transactions, but also the spent ones.

Now, how is it possible that your code performs better than the leveldb solution used by core..?

It has nothing to do with any "fast concurrent spend tree".
It has all to do with the (U)TXO index itself.
You use a hashmap as the index, which is much faster than the index used by core's leveldb engine.
But it also takes much more system memory.

I know, because I also use hashmap based UTXO index in my gocoin s/w.
So you don't have to tell me that it's much faster.
But it comes at the cost of the memory - you can't run this with e.g. 2GB of RAM.
From my personal experience I'd say you need at least 8GB.
And because you index both; spent and unspent transactions, you need even more memory than the UTXO-index solution, which you are trying to beat.

The bottom line is: no way this can perform better than a simple hashmap based UTXO-index.

The important part is to split base load transaction validation (when a transaction comes in) with peak load order validation (when a block comes in).

For the first, this design is in itself not faster as it indeed uses an index which includes spent outputs (though it can be pruned to be even more similar to the UTXO). This is also much less relevant because if no block is coming in, neither Core nor Bitcrust are needing a lot of resources.

For the latter, when a block comes in, the output scripts are not needed as they are already verified. The only thing that needs to be accessed is reads to the transaction index which only maps hashes to file offsets. And reads and writes to the spend tree and spent index which are very compact and concurrently accessible.

This in contrast to Core's model which needs sequential reads and writes to the UTXO index, even if all scripts are already verified.

Essentially Bitcrust simply ensures that the work and resources needed when a block comes in are minimized.

[gmaxwell]

This in contrast to Core's model which needs sequential reads and writes to the UTXO index, even if all scripts are already verified.

This is not how Bitcoin Core works. No access to the disk normally at all happens when a block is verified except for transactions that have not yet been seen, reading or writing.

[tomtomtom7]

This in contrast to Core's model which needs sequential reads and writes to the UTXO index, even if all scripts are already verified.

This is not how Bitcoin Core works. No access to the disk normally at all happens when a block is verified except for transactions that have not yet been seen, reading or writing.

I am not talking about disk reads and writes, I am talking about UTXO index reads and writes.