[Fundraising] Finish “Ultimate blockchain compression”

[justusranvier]

Thank you.

[1715296584]

1715296584

[maaku]

I have started a blog where I will post periodic status updates and technical explanations as I begin work on this proposal. Please check it out:

http://utxo.tumblr.com/

[solex]

Maaku, instead of whining and complaining about the size of the blockchain, you have stepped up like a man to solve the situation.

You've just been sent a grant of 150 Bitcoins by myself, on behalf of SatoshiDICE, for the ongoing growth and development of this amazing technology we call Bitcoin. (Note to SD shareholders, this is a personal contribution, not coming out of SD earnings)

Further, if after three months, Alan (whom I respect very highly) recommends further development, I will commit to funding another three months (we'll revisit the btc amount based on the exchange rate then).

Please contact me on skype (evoorhees) and we can discuss further. And I agree with Alan that this needs a better name

Just saw this post, and want to say that this is an awesome expression of support for the future success of Bitcoin!

[freedomno1]

This is quite high level stuff and I can see how significant these changes would be to the overall usability of bitcoin downloading that client is a significant barrier to its usage as the blockchain grows.
In addition the amount of gruntwork to make such a system work
Since this is a technical discussion thread I will refrain from further posting but I wanted to express my appreciation to developers in building up bitcoin and ensuring it's ongoing growth and commend your transparency
Thank you and I look forward to seeing the new implementation

[maaku]

I've posted a status update to the implementation blog, including a brief overview of the current development pathway:

http://utxo.tumblr.com/post/52638982528/pathway-to-freedom

[K1773R]

great to see you dont abandon it, keep it up

[Arcurus]

Hi Maaku,
Do you have also a Freicoin donation address for this project?

I would love to donate some FRCs for this Project

I wish you the best for your project,
Arcurus

UPDATE:

Oh I just saw at your blog, that also Freicoins are accepted at this address, so I can just donate Freicoins to the same address?

"13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP (Bitcoin or Freicoin accepted)."

[dansmith]

maaku, are you aware that RSS feed isn't working on your website.
I can't conveniently keep abreast with your progress.

[maaku]

Hi Arcturus, that address should work just fine for freicoin as well. Thanks! I'll see what the RSS  problem is about .. it's a tumblr blog so I'm not sure what control I have over that, but I will try.

[Arcurus]

Hi Arcturus, that address should work just fine for freicoin as well. Thanks! I'll see what the RSS  problem is about .. it's a tumblr blog so I'm not sure what control I have over that, but I will try.

nice!

Freicoins are coming

And good luck for your coding effords!
Arcurus

[cozz]

Does the UTXO root hash have to be recalculated after every block, and maybe other tree recalculations?

If so, I am a little bit concerned about the performance impact. Lets say bitcoin grows, then the recalculation of this thing could
take minutes.

So do you think, it is possible to do all the necessary recalculations after every block in lets say 1 second, even if bitcoin gets really big and there is huge database?

(other than this, many thanks for working on the project, I have donated 1BTC)

[maaku]

Validation of a full block currently takes more than 1 second on most commodity hardware, and that's with the 1MB blocksize limit. There's a reason Satoshi choose 10 minute interblock times.

But it's a fair question to ask, and we should be concerned about performance. The number of hash operations required to update the UTXO index is approximately:

2 * (I + O) log (N)
I: # inputs in new block
O: # outputs in new block
N: # outputs in UTXO set

So it scales linearly with the size of the block, and logarithmically with the size of the UTXO set. The constant 2 is because there will be two indices maintained, not the 1 index currently used for block validation, although one should expect the constant factor to be different anyway.

Besides the constant-factor difference, the added cost is that log(N) factor. That's not a super-significant change to scalability, and in my own opinion is definitely a worthwhile cost for secure lightweight clients and quicker sync times.

However when it comes to performance and scalability, the elephant in the room is ECDSA, not hashing. A modern consumer PC can hash about 100 MB/s, but only do about 100 ECDSA signature verifications per second. The number of signature operations is related to the number of inputs, and therefore the size of the block. That's a speed difference of 3 to 5 orders of magnitude, depending on natural variation on the size of outputs and the number of signature operations per input.

EDIT: And thank you for your contribution!

[cozz]

A modern consumer PC can hash about 100 MB/s, but only do about 100 ECDSA signature verifications per second.

Just wanted to add that this number seems a little bit low to me, I have run bitcoin with the -benchmark flag, and it tells me
that I can verify over 10000 signatures per second on a 4x4GHz cpu.

[maaku]

fBenchmark (-benchmark) doesn't measure ECDSA performance. Are you sure you're reading the output correctly?

[etotheipi]

I know sipa was working on an optimized ECDSA verifier that would outperform SSL about 4x.  I don't know if he finished it (and got it into Bitcoin-Qt/bitcoind yet).

But I do remember that a single core of my i5-2500K did something like 200-500 ECDSA verifications per sec.  So with 4 cores that would be like 1000-2000/s.  And probably something like 5,000/sec when using sipa's optimization. 

However, it still doesn't change the fact that it's a couple orders of magnitude slower than hashing, which can execute about 15,000,000/s on the same hardware.  In the grand scheme of things, the address-indexed DB will not consume much time when implemented properly.  Each block only updates a couple MB of DB values which should take far less than a second, even with synchronous writes.

[cozz]

cat debug.log | grep 'Verify '
- Verify 130 txins: 29.40ms (0.226ms/txin)
- Verify 345 txins: 76.33ms (0.221ms/txin)
- Verify 171 txins: 38.20ms (0.223ms/txin)
- Verify 201 txins: 44.65ms (0.222ms/txin)
- Verify 212 txins: 51.27ms (0.242ms/txin)
- Verify 385 txins: 83.74ms (0.218ms/txin)

ok, so this is like 4000-5000 /s

[maaku]

I have pushed to three related code updates, representing work done during the month of August towards implementation of the UTXO index structures for bitcoin. As I've mentioned earlier on my blog, I'm doing the preliminary exploration work in Python, and so far that's paid off. I've gone through three iterations of the prefix-tree design, at each step uncovering weaknesses that require various modifications to the original design. The design, implement, test, benchmark, redesign cycle is averaging about a week, much faster than developing directly in C++ would have been. Python is, however, much slower, chiefly because of the time spent marshaling in and out of the block store or constructing hash preimages, and the resulting dynamic string manipulations. Now that the design is starting to solidify, I will probably do one more iteration before moving to C++ and beginning implementation for the Satoshi client.

The code updates include a new release of python-bitcoin, which contains the UTXO index data structures. Of particular interest to other developers would be the modules patricia.py, ledger.py, and merkle.py. The patricia.py module contains the PatriciaNode class which implements the node-compressed, level-compressed trie structure and whose API looks very similar to an ordered dictionary. ledger.py contains the supporting structures necessary to TxIdIndex and ContractIndex - the two authenticated indices underlying the “Ultimate blockchain compression” proposal. The merkle.py module contains a similarly constructed albeit not finished implementation of prunable Merkle trees. You can access this code here:

https://github.com/monetizeio/python-bitcoin/

The second project, which I'm releasing now for the first time, is a SQL blockchain storage backend using the absolutely wonderful SQLAlchemy object relational mapper. For this project, using SQL for storage has been beneficial as many profiling tools exist, and it allows arbitrary queries to be constructed after-the-fact to help diagnose bottlenecks. There are, however, obvious performance limitations and nobody should ever consider using a SQL backend for a fully validating node. Some people may find it useful for specialized applications requiring join queries, or perhaps a block explorer-like website. The code is available on github, and interfaces with python-bitcoin:

https://github.com/monetizeio/sqlalchemy-bitcoin/

Finally, in case anyone wants to play around with what I've been working on, there's a tool for synchronizing the SQL storage backend with the block chain via bitcoind's JSON-RPC interface. I *only* recommend using this for testnet data, and preferably the smaller testnet-in-a-box chain. Performance is abysmal, but for known reasons explained above. Back-of-the-envelope calculations based on profiling data show that a compiled implementation with smart memory management and a fast key/value data store should operate at least 100x faster, which would be enough to handle the live bitcoin block chain. Code is available here:

https://github.com/maaku/utxo-ledger/

I will be posting more updates soon.

[maaku]

Final revision of the index structure has been committed to python-bitcoin. It is now a level-compressed and node-compressed binary prefix tree. This is a pretty big change from the original proposal, but clearly the right decision to make in light of the performance numbers. The purpose of a 256-way radix tree was to reduce the number of hash operations, but that came at the price of greatly increased node sizes. This made index traversal more complex, and resulted in enormous proof sizes. Alternatives such as having a Merkle-ized internal node structure would have resulted in the exact same performance as a binary tree, but with much greater code complexity.

There may be one more minor change (eliminating the no longer needed coinbase flags from the ultraprune structure), but after that hash values and proof structure should remain unchanged from then until the deployment to the Satoshi client. The design phase is now over.

I also made some slight but important adjustments to how the utxosync.py program constructs the root hash. Insertion of coinbase transactions into the ledger is delayed by 99 blocks, meaning that an output shows up in the ledger only once it is eligible to be spent in the next block, according to the network rules. The primary reason is that the index of a block cannot contain its own coinbase, if the hash of the index is itself going to be committed to the coinbase. Otherwise you'd have a circular hash dependency (input depends on output), which is obviously impossible to resolve.

The final performance characteristics: average-case proof size of 64 * log2(utxo transactions) for the txid index, which is currently about 1.35kB. Average case for the address index is: 65 * log2(utxo outputs), currently 1.45kB. The worst case size for a txid proof is 16.25kB, although that will never happen because setting it up would require a SHA-256 pre-image attack. Worst case for the address index is 65 bytes * number of bits in the scriptPubKey, which doesn't require a pre-image but can be protected by not reusing addresses.

Syncing with the block chain takes a few seconds per block, or a few dozen for the really big blocks, with 95% of that being spent in the SQL database, and 4 of the remaining 5% spent marshaling data. As mentioned earlier, moving to LevelDB and a compiled language should eliminate most of that, hopefully resulting in two orders of magnitude speedup. So performance is looking good, so far.


I have approx two weeks left on the first round of funding the members of this forum have so generously provided. I will use that time finish and push the pruning and proof generation code, and time permitting expand the utxosync.py script into a small Django web API for querying the UTXO indicies. This could be used for prototyping wallet software that uses the new proofs. However this will provide no increase in security until bitcoin is soft-forked to include UTXO index commitments, or a merged-mined meta-chain is implemented.

This brings me to the next round funding. I am requesting a final 3 months of time to implement the final revision of the index structure in C++ and using LevelDB, optimize it to achieve sub-second update times (or as close to that performance goal as possible), and either (1) submit a documented pull request adding coinbase UTXO hash commitments to the Satoshi client, or (2) write a proxy server for miners to do their own commitments on a merged-mined meta chain. Which outcome depends on whether acceptance of a coinbase commitment pull request is likely to happen, which in turn depends on the achievable performance metrics which we do not know for certainty at this time.

Because of unexpected costs (insurance) and volatility, I'm forced to increase my monthly cost to 65btc, and will fully cash it out on receipt. I am therefore requesting a total of 195btc to finish the implementation as described above. If this is received by the end of the month, then I can promise the deliverable by the end of the year. Otherwise I will continue work, but at a rate in proportion to funds received, as funds are received ("billing" my time hourly). Please send donations to the same address:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Donation address for implementing phase 2
of "Ultimate blockchain compression"

13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
-----BEGIN PGP SIGNATURE-----

iQIcBAEBAgAGBQJSLkT7AAoJECsa1YSJj/UDJ0IP/26oyR1COsLs/f+rEvz33kFP
0HtGvsjbEoF+7cetJpIV0eyFomngOWpafr0uhy+uO6mGguPHbXPJlmcgywFdKDwB
pQrRVYcT2DQx+Hfwnhn51QNIJoB6LhnykUi9KrDar8FwbNfYOgLaSUDGqKShtDOC
lc/qVkP56cCvalcqs6a6Q8O0D69BLO+TwifMPJmtdzdnn/2Fs9ONdgXpnnNLGwpJ
g/LWPy9Zdjspq7qoH/p3kFWo2S8TmX5EShsMDM8C4oUTnMjXbBvodJQwm6AzC0KY
XWdg+/W82YpMpmAmhSxqw43/VzUrODw9WAn7cXrCA86/IwhihZnNhLsELYP7Cd77
kgBWR9HE+NILWTRn+x8CONfi6+gk8ZqYsKmcj+PcYbf1u2BAknKb1EVpTwNp2ehD
8y6oNFj99vkDfZz8hSmt8HLn7YbU9jnmJcFqXwCwDFZD+nvWi1dHFeqnJppH3lWX
HaIF3V+psYQuMpglk+fFVrbmF+omCzsd7dArCXk4n+txA8rGIVBD2nWz4MUUxB9e
TLIeVr4EkH+yjvEK00VzjryfINE6mG58hetm1/y4Y/1EvoDATOyZhR91UFB6x/21
+pCagBDSVquc7DVYk7e275PnKSxjM4miAcf88jkO6TvcdiUaiYnYGxZQRCBY89/6
WgWf1x6CQvknPrYT6sZv
=hg1Y
-----END PGP SIGNATURE-----

As always, I welcome questions and comments regarding this proposal and my work towards implementing it, particularly from funders or developers of lightweight clients that might use it.

[justusranvier]

I'll continue donating monthly through your ReDonate campaign for an extra 3 months.

[maaku]

Thank you justusranvier. Your generous support over the last few months is what has kept me going to hit this milestone after the funding would have run out at the end of August. In case people missed it, here's the ReDonate campaign:

http://redonate.net/dashboard/bitcoin-developer-maaku