Bitcoin Forum
September 25, 2018, 10:05:26 PM *
News: ♦♦ New info! Bitcoin Core users absolutely must upgrade to previously-announced 0.16.3 [Torrent]. All Bitcoin users should temporarily trust confirmations slightly less. More info.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Fast parallel block validation without UTXO-index  (Read 4511 times)
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 06, 2017, 04:55:38 PM
 #1


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
1537913126
Hero Member
*
Offline Offline

Posts: 1537913126

View Profile Personal Message (Offline)

Ignore
1537913126
Reply with quote  #2

1537913126
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1537913126
Hero Member
*
Offline Offline

Posts: 1537913126

View Profile Personal Message (Offline)

Ignore
1537913126
Reply with quote  #2

1537913126
Report to moderator
1537913126
Hero Member
*
Offline Offline

Posts: 1537913126

View Profile Personal Message (Offline)

Ignore
1537913126
Reply with quote  #2

1537913126
Report to moderator
1537913126
Hero Member
*
Offline Offline

Posts: 1537913126

View Profile Personal Message (Offline)

Ignore
1537913126
Reply with quote  #2

1537913126
Report to moderator
piotr_n
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 07, 2017, 12:07:29 AM
 #2

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 07, 2017, 01:12:20 AM
 #3

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
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 07, 2017, 01:27:26 AM
 #4

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 07, 2017, 05:46:01 AM
 #5

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
Legendary
*
Offline Offline

Activity: 1120
Merit: 1000



View Profile
April 07, 2017, 08:50:25 PM
 #6

Does this make SegWit obsolete?

I'm grumpy!!
misterbigg
Legendary
*
Offline Offline

Activity: 1064
Merit: 1001



View Profile
April 08, 2017, 01:20:53 AM
 #7

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
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 08, 2017, 01:33:53 AM
 #8

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 08, 2017, 06:37:25 PM
 #9

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
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 09, 2017, 12:37:27 AM
 #10

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?

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

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2506
Merit: 1507



View Profile
April 09, 2017, 02:40:26 AM
 #11

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.


Bitcoin will not be compromised
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 09, 2017, 06:24:01 AM
 #12

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
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 09, 2017, 06:53:40 AM
 #13

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
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 09, 2017, 11:31:25 AM
 #14

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
piotr_n
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 09, 2017, 03:33:28 PM
 #15

I think I get it. Smiley

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
piotr_n
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 10, 2017, 05:59:43 PM
 #16

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
piotr_n
Legendary
*
Offline Offline

Activity: 1932
Merit: 1018


aka tonikt


View Profile WWW
April 10, 2017, 06:16:18 PM
 #17

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

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 11, 2017, 07:51:53 AM
 #18

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
Moderator
Legendary
*
qt
Offline Offline

Activity: 2506
Merit: 1507



View Profile
April 11, 2017, 08:29:57 AM
 #19

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.

Bitcoin will not be compromised
tomtomtom7
Newbie
*
Offline Offline

Activity: 38
Merit: 0


View Profile
April 11, 2017, 09:09:35 AM
 #20

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.
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!