Quote from: Peter R on May 29, 2015, 05:21:28 PM

Quote from: tvbcof on May 29, 2015, 06:55:19 AM

Quote from: Peter R on May 29, 2015, 12:45:55 AM

Quote from: tvbcof on May 28, 2015, 11:30:37 PM

Quote from: iCEBREAKER on May 28, 2015, 11:05:17 PM

...
The UXTO constraint may never be solved in an acceptable (sub)linear way, or the solution(s) could for political reasons never be implemented in BTC.
...

Almost certainly 'never' by any realistic definition of various things.
...
Solving 'the UTXO problem' would require what is by most definitions 'magic'. Perhaps some future quantum-effect storage, communications, and processing schemes could 'solve' the problem but I'm not expecting to pick up such technology at Fry's by the next holiday season (Moore's law notwithstanding.)

A comment from chriswilmer got me thinking

The UTXO set is actually bounded. The total amount of satoshis that will ever exists is

   (21x10^6) x (10^8) = 2.1 x 10^15 = 2.1 "peta-sats"
...
...
OK, now let's be reasonable! Let's assume that 10 billion people on earth each control about 4 unspent outputs on average. That's a total of 40 billion outputs, or

   (40 x 10^9) x (65 bytes) = 2.6 terabytes

With these assumptions, it now only takes about 20 of those SD cards to store the UTXO set:

   (2.6 x 10^12) / (128 x 10^9) = 20.3,

or, three 1-terrabyte SSDs, for a total cost of about $1,500.
...

I have thought about this bounding (mostly in the context of the current rather awkward/deceptive 'unspendable dust' settings.) I think that there is currently, and probably for quite some time, some big problems with this rosy picture:

- UTXO is changing in real time through it's entire population. This necessitates currently (as I understand things) a rather more sophisticated data-structure than something mineable like the blockchain. UTXO is in ram and under the thing that replaced BDB (forgot the name of that database at the moment) because seeks, inserts, and deletes are bus intensive and, again, in constant flux.

Agreed. The UTXO can be thought of as "hot" storage that's continually being updated, while the blockchain can be thought of as "cold" storage that does not have the same requirements for random memory reads and writes. However, the UTXO doesn't need to sit entirely in RAM (e.g., the uncompressed UTXO set is, AFAIK, around 2 GB, but bitcoind runs without problem on machines with less RAM).

Quote

...but would be interested to see a proof-of-concept, simulator, prototype, etc.

Agreed. What I'm curious about is the extent to which the UTXO database could be optimized algorithmically and with custom hardware.

Consider the above scenario where 10 billion people control on average 4 unspent outputs (40 billion coins), giving us a UTXO set approximately 2.6 TB in size. Now, let's assume that we sort these coins perfectly and write them to a database. Since they're sorted, we can find any coin using binary search in no more than 36 read operations (about 65 bytes each):

   log₂(40x10^9) = 36

Rough numbers: A typical NAND FLASH chip permits random access reads within about 30 us, a typical NOR FLASH chip within about 200 ns, and perhaps less than 20 ns for SDRAM, so it takes about

   36 x 30 us = 900 us (NAND FLASH)
   36 x 200 ns = 7.2 us (NOR FLASH)
   36 x 20 ns = 0.72 us (SDRAM)

to find a particular coin if there's 40 billion of them. If we commit 10% or our time to looking up coins, to match Visa's average rate of 2,000 TPS means we need to be able to find a particular coin in

   (1 sec x 10%) / (2000 /sec) = 50 us.

My gut tells me that looking up coins isn't too daunting a problem, even if 10 billion people each control 4 coins, and, in aggregate, make 2,000 transactions per seconds.

...Of course, the UTXO is constantly evolving. As coins get spent, we have to mark them as spent and then eventually erase them from the database, and add the new coins to that database that were created. If we assume the typical TX creates 2 new coins, then this means we need to write about

   (65 bytes per coin) x (2 coins per TX) x (2000 TXs per sec) = 0.26 MB/sec

Again, this isn't fast. Even an SD card like the SanDisk Extreme Pro has a write speed up to 95 MB/s.

Of course, this is the speed for sequential writes, and we'll need to do plenty of (slower) random writes and erase operations, but note that 0.26 MB means that only

   0.26 MB / 2.6 TB = 0.00001 %

of our database is modified each second, or about 1% per day.

My questions, then, are:

  - To what extent can we develop algorithms to optimize the UTXO database problem?
  - What is the best hardware design for such a database?

Mike Hearns on reddit:

If the block creates the outputs that it does itself spend all those outputs will be in RAM cache. So they will be effectively free to check.

LevelDB is very fast, even on a spinning hard disk. You can't assume 1 UTXO = 1 seek.

https://github.com/google/leveldb

readrandom : 16.677 micros/op; (approximately 60,000 reads per second)

60,000 reads per second, for random access.

This isn't a problem. Gavin is being highly conservative and I think panicked a little - LevelDB effectively sorts keys by hotness (due to the leveled SSTable structure). So old/dormant coins will eventually fall to the bottom of the pile and be a bit slower to access, with the benefit that recent coins are near the top and are cheaper to access. People who try and create then spend coins over and over again to waste IOPs are going to be very frustrated by their lack of success.

And now I'm off to the airport for a two week holiday. Have fun guys!