[Fundraising] Finish “Ultimate blockchain compression”

[maaku]

Update: Please read the latest news here:

https://bitcointalk.org/index.php?topic=204283.msg3117454#msg3117454

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.


TL;DR: I plan to implement the Ultimate blockchain compression w/ trust-free lite nodes proposal by @etotheipi. Please help me acquire funding work full-time on it by pledging coins to 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP.

After a startup misadventure, I have recently found myself back on the job market. Rather than take a soul-crushing 8-5 job, I have taken inspiration from @etotheipi and would like to try my hand at full-time open-source development.

In my mind the most critical barrier to the widespread adoption of Bitcoin is the initial block download. Requiring the user to spend days downloading and processing gigabytes of data before getting started is unacceptable, and SPV clients do not provide enough security to be an acceptable alternative for many purposes. We can have our cake and eat it too, but it will require a heck of a lot of grunt-work.

I reject bounties as being inappropriate for a task of this scale. The likely length of the project prevents me from doing this as pay-on-delivery as I would be receiving no income for living expenses between now and then, and I have a wife and daughter to support. It would also force me to develop in secret and take on a hostile stance with possible competing developers who may “scoop” my ideas or code to claim the bounty before me. The rules of the bounty may also prevent me from having the flexibility to alter the scope or structure of the project due to unforeseen considerations and unavoidable complications. I do not believe such an outcome would be good for the community.

Rather, I promise to develop in an open fashion. I will implement the UBC proposal directly in the Satoshi bitcoind daemon/Bitcoin-Qt client, with my changes periodically pushed to a github repository. I will make weekly status reports on a blog, cross-posted to this forum. I will engage with the developer community to get peer review on design choices and address concerns as they come up. The general plan for development would be:

* Implement the PATRICIA trie index of the UTXO set, using LevelDB as the storage backend. Implement p2p messages and rpc commands for querying this index.
* Add support for tracking multiple chains to bitcoind, and implement the merged-mined UTXO meta-chain.
* Restructure bitcoind to allow retrieval of wallet transactions from a UTXO peer, and construction of the pruned block/transaction database from the UTXO set.
* Implement bittorrent distribution of blockchain data, offloading IBD and full UTXO set retrieval from the bitcoin protocol.
* Switch the default Bitcoin-Qt behavior to perform IBD in the following manner:

1. Download bitcoin block headers and verify proof-of-work.
2. Download coinbase transactions for most recent X bitcoin blocks.
3. Determine head of UTXO meta-chain, retrieve meta-chain block header, and extract UTXO root hash.
4. Fetch wallet transactions from peer, with UTXO proof.
5. Download UTXO set (fast) and construct full transaction validation database.
6. Begin operation as a validating transaction processing node (total time elapsed: minutes).
7. Download entire block chain history (slow) and verify blocks.
8. (Potentially) begin operation as a mining node (total time elapsed: hours/days).

(Update: please read this blog post for my current views regarding SPV+ support in the Satoshi client, in view of the fact that the Satoshi client is no longer the officially recommended wallet app. Implementation of SPV+ mode in lightweight clients such as MultiBit or Electrum has taken priority, although recent changes to the Satoshi client make SPV+ mode more plausible.)

I expect that full implementation of this proposal would take 4-6 months. It might take longer. I am requesting 150 BTC (or equivalent fiat) to cover rent, food, insurance, medical bills, etc. for the first 3 months in lieu of taking a job to support my family. Obviously this will not be sufficient time to complete the project, but I am expecting to make significant progress and certainly have a better idea of how much follow-on work would be required. You may then evaluate whether a further donation is a worthwhile investment for you.

I have started a blockchain.info wallet for this purpose.

13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP

If it does not reach 150BTC, I will return all contributions. Please reply in this thread or PM me if you have any questions, and I will be happy to answer them. I will also be a panelist at Bitcoin 2013 and would be happy to meet with anyone in person.

CREDENTIALS

I implemented Freicoin, which adds interest/demurrage to the bitcoin blockchain. This required considerably more design and simulation than one might naïvely expect, as interest obviously depends on timing, transactions lack timestamps, and block time is untrustworthy. The solution developed for Freicoin is original and works well in practice.

More recently I have implemented an improved difficulty adjustment algorithm for bitcoin protocol currencies, replacing the 2016-block average with an optimal Parks-McClellan filter co-designed by @galambo and tweaked to give very quick response response times (adjustments every 9 blocks) while maintaining accuracy and avoiding instability.

I have also co-designed with @jtimon a colored coin proposal that adds interest-bearing assets and a distributed, peer-to-peer exchange. I will shortly be posting this as a separate bounty / work proposal.

Outside of bitcoin, I have worked for several years at NASA-Ames Research Center, doing various web development & data analysis & visualization tasks for the planetary science and astrobiology institutes.

EDIT: After less than a day, the funding goal has been achieved. Thank you! As there are still contributions coming in, I will treat it as a rolling fundraiser for continued development after the 3 months have elapsed. This is a project that will take at least 4-6 months, and possibly more. The project will officially start June 1st, after I have wrapped up some other obligations.

[etotheipi]

@maaku

Thank you.  I think you are a good match for this development activity, as you clearly have the self-motivation and technical expertise to pull it off.  And you have the proper attitude as well -- sober but encouraging. 

One thing we might consider is renaming this proposal.  The thread was started a year ago with the phrase "Ultimate Blockchain Compression" because of a really silly oversight on my part:  that the address-indexed DB would have to be in addition to the txHash-indexed DB.  I originally thought it would be a replacement for the tx-indexed DB, but you clearly need both.  Therefore, this necessarily adds resource usage on top of an optimally-pruning miner.  I think the recent discussion where I realized that you can eliminate all the pointers, makes the overhead much more manageable, but it's still non-negligible.    I don't know your real name, but if you make this work, perhaps it would we could just name it the Reiner-Maaku tree   But I think the "UBC" part should be adjusted since it's not "ultimate compression" (though it does fit on top of an ultimately-compressed blockchain).

I'm happy to contribute to this design where I can.  As you pointed out, I'm quite busy, but I also think this is quite a valuable addition to the protocol.  Even if it somehow turns out to be infeasible, we'll learn a lot from the exercise that will help us do it right on the next try.  However, I'm confident that this will bear fruit with someone capable devoting themselves to it. 

You might consider/research using something other than LevelDB for the full nodes.  LevelDB is very fast and efficient for some things, but I fear it may not be reliable enough for the heavy lifting that will be done by the mining nodes in the [far] future.  For partial/lite nodes, LevelDB makes perfect sense, especially because it's easily bundle-able into end-user software.  But the miners of the future will probably be running dedicated hardware anyway, so they won't be terribly inconvenienced having to have a hardc0re DB engine available to run something like this, with all the robustness/ACID properties that are desired.   Therefore, it would be really nice to have a generic interface (or two interfaces, one for SQL and one for noSQL-key-value-store), so that something like LevelDB can be bundled with the software for "regular" users, and something more concrete can be swapped in for full-mining nodes. 

Also, I should mention that socrates/amiller had some interesting ideas that would be worth discussing.  He had an idea for lite-storage-but-full-verification nodes, which I'm still not confident it is possible, but he insists it is and we agreed to debate it in the future when I had time.  Maybe you can discuss it here before embarking on this journey, to make sure the design is extensible enough to accommodate it if it is feasible.

[lunarboy]

just a little 0.1 to show my support.

good luck 

[evoorhees]

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

[Deafboy]

Wow... that escalated quickly!
Sending few cents anyway

[oakpacific]

Thank you maaku. My 0.5 BTC because we all want to see it happen.

[jtimon]

Great maaku! I've sent 1 btc.

This is much necessary. Specially for certain use cases such as having colors in the chain.

About the funding alternative to bounties, I want to tell the concrete story about the freicoin initial development one, because I think it's an interesting example of how things can change even when all seems clearly and simply defined (at least it was in my head if you disagree it was well defined).
The bounty asked for the implementation of the new currency based on my simple design draft plus adding merged mining from namecoin's code.
First, my solution to the "exact payment problem" didn't guaranteed that a transaction would survive a reorg. This is an important problem he identified, and after some discussion, he came up with the elegant solution of using a referece Height set by the payer to calculate demurrage. Although the solution was reasonably simple in design terms, what I initially thought would be an "easy task" was starting to get substantially more complicated.
There was some rounding potential problems I missed too. He also implemented some gitian building scripts and adapted p2pool to interact with demurrage. He implemented the modification to send the budgets to the foundation that I didn't wanted at first but the community was asking for.
He didn't took the code for merged mining because it wasn't (and still isn't) a priority.

Well, I was more than happy with his work and the other donor didn't complained when I asked so I just gave the bounty to him (after the fact, so not as useful for him as the crowdfunding campaign). But if there were many more donors, maybe some of them would have blocked the bounty release.

[Sukrim]

As far as I understand it, it might not be possible to do complete block chain analysis after implementing this change, so there might be some reservations from bitcoin-qt developers to this (as you delete parts of history).

Maybe consider a full fork of Bitcoin-qt ("Bitcoinquick-qt"?) in case this doesn't get accepted to the main bitcoin-qt client. Other than that congratulations on reaching your funding goal so quickly and looking forward to first updates regarding implementation!

[CIYAM]

Actually a Project had been created in CIYAM Open for this very thing a while back (was never actually "opened" though) - if this could be useful (in terms of creating Project Areas and then specific Project Tasks) then CIYAM Open would be happy to help manage this free of charge (if the current Project Owner is not interested to do that then I will volunteer my own time to help out).

[maaku]

Thank you everyone.

Let's take it from the top:

The topic/proposal should definitely be renamed, as it does not allow for any pruning beyond what is already possible (in theory) with the ultraprune branch that made it into 0.8. I kept the name in the OP only because that is what people know the proposal as, but now that the project is funded we should correct details like this. Suggestions are welcome; perhaps “unspent-TxOut queries for trust-free lite nodes and quick synchronization”? A bit clunky...

I think the recent discussion where I realized that you can eliminate all the pointers, makes the overhead much more manageable, but it's still non-negligible.    I don't know your real name, but if you make this work, perhaps it would we could just name it the Reiner-Maaku tree

Ah, but you forget I was the proponent of a 2-3-4 BST But no matter, you won me over. One of my first tasks would be finalizing the serialized form of the hybrid trie structure, while making sure that it is efficiently retrievable from an indexed key-value store and inexpensive to update.

I am confident that LevelDB will be a reasonable default choice and prove reliable even under high load, given the performance numbers I've seen and its heritage from Google's BigTable. However yes, the proper abstraction is “indexed key-value store”, for which there are many NoSQL (and SQL) solutions. I may not go to the extent of actually writing or using an intermediary database wrapper, but I will make sure that there is nothing LevelDB-specific about the solution.

Also, I should mention that socrates/amiller had some interesting ideas that would be worth discussing.  He had an idea for lite-storage-but-full-verification nodes, which I'm still not confident it is possible, but he insists it is and we agreed to debate it in the future when I had time.  Maybe you can discuss it here before embarking on this journey, to make sure the design is extensible enough to accommodate it if it is feasible.

Yes, I do recall that discussion, and in fact amiller's description of trust-free lite-node operation is I think the primary long-term benefit. Actually, I confess I thought it was your original purpose the first time I read your proposal. Of course “full-verification” is I think a misuse of terms, as in such a case there is in fact no transaction validation but rather trust that the miners on the meta-chain are themselves properly validating, and then construction of a “balance-proof” from the unspent-TxOut trie.

To be clear, UBC (or whatever we call it) allows for two separate “lite” modes of operation: one where the entire unspent-TxOut set is downloaded from peers and new transactions/blocks are validated against it. This is the same as the pruned mode 0.8 is theoretically capable of, except that the unspent-TxOut set need not be built from scratch.

The second, lighter mode of operation is what amiller describes, where the lite client requests other nodes to provide self-validating proofs of address balances by providing paths through the unspent-TxOut Merkle tree. The client can then proceed to operate in an enhanced SPV mode while downloading first the unspent-TxOut set and then the full blockchain in the background.

I thought the controversy was over balanced BST vs trie structures, but I may be misremembering that discussion. I think I have a professional obligation now to take another look through the whole thread and evaluate all ideas contained within.

@evoorhees, I sent you a Skype invite and I'd be happy to talk with you that way or at the conference. My timezone is U.S. Pacific Daylight Time.

@jtimon, thank you for the reference and kind words. Yes, our “assets” colored-coin proposal is what drew me back to this proposal. If people think SatoshiDice brings a lot of traffic and bloats the block chain, wait until they see what a distributed exchange and transitive credit will do, especially once the block-size limit is relaxed.

As far as I understand it, it might not be possible to do complete block chain analysis after implementing this change, so there might be some reservations from bitcoin-qt developers to this (as you delete parts of history).

This proposal in no way impacts block chain analysis / validation. It is strictly adding functionality to a fully-validating node. However that functionality would allow for non-validating clients to operate with significantly better security than current lite clients such as non-validating bitcoinj or electrum. Further, it becomes possible that the Satoshi client could start operation in one of these enhanced lite security modes (with a sync time of seconds or a few minutes), and then transition to full-validation once the initial block download is complete.


@CIYAM Open, thanks I do appreciate it, although I have my own project management tools configured the way I like them


For everyone who has contributed, thank you. As there are still contributions coming in, I will treat it as a rolling fundraiser for continued development after the 3 months have elapsed. Between the conference and some other obligations I am winding up, my time will be split for the next couple of weeks. Therefore the 3 months will officially start June 1st.

[etotheipi]

Ah, but you forget I was the proponent of a 2-3-4 BST But no matter, you won me over. One of my first tasks would be finalizing the serialized form of the hybrid trie structure, while making sure that it is efficiently retrievable from an indexed key-value store and inexpensive to update.

The beauty of one the last revelations in that thread was that you can define it in terms of that hybrid tree, but implement it with a regular iteration over the natural sorting of the database.  In other words, if you iterate over the database and are careful about tracking where you were and where you are, you can perfectly simulate the hybrid PATRICIA tree without actually implementing all its complexity.  And at the same time saving all the space you would've spent storing pointers.  You simply define it in terms of the hybrid tree (skip strings, omitting NULL pointers), but the actual implementation will be much simpler.

I am confident that LevelDB will be a reasonable default choice and prove reliable even under high load, given the performance numbers I've seen and its heritage from Google's BigTable. However yes, the proper abstraction is “indexed key-value store”, for which there are many NoSQL (and SQL) solutions. I may not go to the extent of actually writing or using an intermediary database wrapper, but I will make sure that there is nothing LevelDB-specific about the solution.

I was just thinking that in the future and/or when developers decide they don't like LevelDB, we may need to switch.  For instance, I read that LevelDB had some problems above 200 million entries.  I don't know the exact parameters (if it's always 200 million, or if it's DB size, etc), but apparently the scalability and robustness may not be there for the long haul.  But it will work perfectly for a proof-of-concept.

Also, I should mention that socrates/amiller had some interesting ideas that would be worth discussing.  He had an idea for lite-storage-but-full-verification nodes, which I'm still not confident it is possible, but he insists it is and we agreed to debate it in the future when I had time.  Maybe you can discuss it here before embarking on this journey, to make sure the design is extensible enough to accommodate it if it is feasible.

Yes, I do recall that discussion, and in fact amiller's description of trust-free lite-node operation is I think the primary long-term benefit. Actually, I confess I thought it was your original purpose the first time I read your proposal. Of course “full-verification” is I think a misuse of terms, as in such a case there is in fact no transaction validation but rather trust that the miners on the meta-chain are themselves properly validating, and then construction of a “balance-proof” from the unspent-TxOut trie.

To be clear, UBC (or whatever we call it) allows for two separate “lite” modes of operation: one where the entire unspent-TxOut set is downloaded from peers and new transactions/blocks are validated against it. This is the same as the pruned mode 0.8 is theoretically capable of, except that the unspent-TxOut set need not be built from scratch.

The second, lighter mode of operation is what amiller describes, where the lite client requests other nodes to provide self-validating proofs of address balances by providing paths through the unspent-TxOut Merkle tree. The client can then proceed to operate in an enhanced SPV mode while downloading first the unspent-TxOut set and then the full blockchain in the background.

I was actually talking about some discussions with socrates outside the thread, on IRC.  You said "I think it's a misuse of terms", but no, actually it's not.  Your recap is accurate concerning what I originally proposed.  But socrates took it one step further, saying that you could build on top of this to create a fully-validating node without storing the whole database.  I believe it involves downloading and verifying parts of the chain in real-time, as you are verifying new blocks.  But it can be done, because if you are confident in the state of the blockchain at block N, you can verify block N+1 efficiently given the availability of this new datastructure we are building.  The node wouldn't be very useful for seeding other nodes, but it would at least enforce the rules on new blocks, and theoretically could even solo mine without holding everything.  

To me, it didn't seem very possible that you could have a bunch of low-storage nodes doing full verification, but I also didn't have the patience at the time to flesh out the idea with him.  Perhaps given a system with a high density of full-storage nodes that can help the lite node do its verification, but it certainly wouldn't be feasible for the network to be made up of them, if no one is serving the full data set.

If he's right, that dramatically loosens the specs needed by future miners, when everyone is predicting that only super-computers/clusters will be able to verify-and-mine.  I have my doubts, but we should definitely invite him to expand on that, and even if it's not completely feasible, there's will probably still be useful ideas in there.

[jtimon]

I don't know all the details of the proposals, but let me explain it the way I see it and then you people tell me what I'm missing.
I propose "trust levels" as the name. For simplicity, I'm assuming the root of the UTXO tree is part of the headers, not just merged mined, but we can argue about that later.

Trust level 2: The current Simplified payment verification.

Trust level 1: We define a distance in blocks to the past which is secure for the node to assume won't suffer a reorg, say 1000 blocks ago and call it the "pseudo-checkpoint". He downloads the full UTXO tree that was in block (currentHeight-1000), the UTXO tree in the pseudo-checkpoint. He downloads 1000 blocks and reproduces the current UTXO tree from the the old one. For a given unspent output, he can provide its full merkle branch until coinbase OR the pseudo-checkpoint if the coinbase is older.

Trust level 0: The node downloads the rest of the chain, being able to verify that the UTXO tree from the pseudo-checkpoint he used was correct, and he will be able to always provide full output markle branches to their coinbases from now on.

You could download the whole chain from the top to the bottom and optimistically start assuming the last UTXO tree was legit, then validate it with the previous one and the transactions of last block, and so on to the genesis. Effectively decreasing the pseudo-checkpoint height from last block created to genesis.
Once you've achieved trust 0, nothing forces you to store the whole chain. You can then set another pseudo-checkpoint, only being afraid of reorgs and/or not being able to provide long enough output chains.
In fact, you can go to trust level 1 or even trust level 0 to operation level 2 if you want. You can download the whole chain but then only keep the branches of your own outputs.

Nodes would have more room for specialization. I think there will be always "librarian nodes" ala block explorer. distributing the whole history. But I think their lack is what worries @Sukrim.

After this I think you can only improve the storage of the UTXO (and posibly their full merkle brach) using caches.

Is this basically what we're talking about or am I lost and the name "trust levels" is awful?

[Sukrim]

Nodes would have more room for specialization. I think there will be always "librarian nodes" ala block explorer. distributing the whole history. But I think their lack is what worries @Sukrim.

True, also there is no incentive to actually operate such a node and if they get rarer, they actually have to serve even more data which puts a stronger pressure to shut them down.

In the OP however there is also some BitTorrent distribution mechanism mentioned... even though torrent files (actually info hashes) for a given file are not 100% deterministic, they can be made deterministic, if there is an agreement on block size. My suggestion would be to include the info hash of a bootstrap.dat file that contains all blocks from (#currentblock-120-#currentblock mod 2016) - meaning that120 blocks after every difficulty change a new info hash gets posted to the UTXO chain. That way the torrent file stays static enough to be properly seeded but changes quickly enough for new clients to catch up.
As BitTorrent downloads are properly hashed, checked etc. and the blockchain can also be verified again upon importing, this should be safe enough, if one also trusts this UTXO chain.
That way full archival nodes would not be queried for older blocks that much, as the bootstrap procedure for a "Ultimate compression" client would be:

* Get current block height
* Get block height of the highest UTXO block X blocks below current height (I would stay with 120 as this is the magic number for spending coinbase transactions, not over 1000... but this canbe even user configurable)
* Download this UTXO block and all UTXO blocks after it, as well as all mainline blocks since then
* Verify that following UTXO blocks were correctly created and also that mainline blocks are OK.
* Get all mainline block headers since genesis (probably a big art of this data can be already come with the installer) and verify that the recent mainline blocks are part of this chain.
### Here you can already start mining your own blocks ###
* Get the full block torrent info hash from the header (?) of the UTXO block(s)
* Download the torrent via a magnet link over DHT (all you need is the info hash after all)
* Verify all full blocks since genesis
### Now you are at the same stage as current bitcoin-qt ###

Now you can either continue to seed the torrent (and maybe even do this on a dedicated machine!) or be happy that the UTXO chain was actually not lying to you, discard most older block contents (maybe here it might make sense to keep the most recent 1000 or so in case there are longer reorgs somewhere in the future?) and just work on UTXO/mainline chains.

With BitTorrent it would be possible to help distributing the block chain without running bitcoind, a downside is that any client that does not have the info hash of the most current check point will seed a relatively dead torrent...

[The Bitcoin Catalog]

This will be an incredible step forward for bitcoin! I will also contribute and try to raise some funds for this project.

[maaku]

@Sukrim, that's essentially my thinking with regards to bittorrent. It's just about moving synchronization of new clients or clients which have been offline for a while off of the p2p bitcoin network, and making it easier for people to offer high-bandwidth “seed nodes” just for this purpose. If done correctly there should be no security implications as blockchain data is self-validating.

@jtimon, you are essentially correct although what you describe is only part of the story. I think “trust level” is an appropriate term. Here's how I would lay them out:

Level 4: Electrum-like client/server. Keys are stored on the client, the but the client trusts the server for information about the unspent-TxOut set. This is only marginally better than sticking your coins on a server-side wallet. I would never make a general recommendation to operate at this level unless you own both the server and the client and have a secure, authenticated connection between the two.

Level 3: Simplified payment verification. Client trusts the “longest” (most work) chain, but reads and processes every block. The client must scan the contents of every block more recent than the oldest address in its wallet in order to be sure that its record of unspent wallet outputs is correct. BitcoinJ has some optimizations not mentioned, but only because they make simplifying assumptions about the circumstances under which wallet transactions might be generated. It remains true that you must touch every transaction of every block that might have a wallet input or output within it.

Both of the above levels will be completely obsoleted by this proposal.

Level 2: The client downloads the “longest” (most work) meta-chain, and retrieves the block of data associated with the current head of the meta-chain. This data includes the Merkle hash of the unspent-TxOut trie and it's associated block height. The client then queries any node exposing the correct service bits about its wallet addresses, retrieving either the associated transaction outputs with proof-of-inclusion, or a negative proof showing that no such output exists in the trie. I call this enhanced simple payment verification, or SPV+, and operates trust-free at an economic security level equal to the hash power of the merged-mined meta-chain.

Level 1: The meta-chain data block probably will include other information, such as a deterministic bittorrent infohash of the serialized unspent-TxOut trie and blockchain checkpoint data. The client downloads the unspent-TxOut trie torrent and verifies that its root hash matches what was in the meta-chain. It then reconstructs the information necessary to do full-block validation from that point forward. The initial synchronization is at the meta-chain level of economic security, but after that it would take a 51% attack on bitcoin itself to subvert a client at this level.

Level 0: The client either verifies the entire chain forwards from the genesis block, or backwards up to the most recent checkpoint as @jtimon described. It is now a fully-validated client operating exactly as the Satoshi client does today, and with the same level of security.

There is also a “0.5” mode that might be good enough for most people: only verify backwards long enough to satisfy your own security requirements (a configurable number of blocks, perhaps as a command line parameter).

I've cross-posted most of this to the original proposal thread, since technical discussion should probably occur there.

[maaku]

Due to constructive feedback received at the conference, I have created a ReDonate campaign as an optional method for adding to the "Ultimate blockchain compression w/ trust-free lite nodes" campaign. ReDonate is a service for contributing a one-time donation, while receiving periodic reminders in the future to re-donate if you are happy with the progress being made.

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

As noted in the OP, the 3-month funding goal has been achieved, but it is expected that it will take more than 3 months to implement this feature. Any further contributions now will go toward extending the amount of time I have to work on it.

[justusranvier]

Due to constructive feedback received at the conference, I have created a ReDonate campaign as an optional method for adding to the "Ultimate blockchain compression w/ trust-free lite nodes" campaign. ReDonate is a service for contributing a one-time donation, while receiving periodic reminders in the future to re-donate if you are happy with the progress being made.

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

That's the link for your personal dashboard. The rest of us need to use this link:

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

[Bicknellski]

Status: 0/unconfirmed, broadcast through 7 nodes
Date: 24/05/2013 17:59
To: Makku 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Debit: -0.099 BTC
Transaction fee: -0.0005 BTC
Net amount: -0.0995 BTC
Transaction ID: eae93c9d529c486cb679bf0e9f0a72f43bb4db92580ba21cc6a2d7a66847941e

COMPRESS IT!

[justusranvier]

Occasionally though other coins will create something that can be ported back to BTC.  Over at FRC we have set our the goal for our next hard-fork to adding a block-chain compression feature originally proposed by etotheipi that will solve the notorious huge-download-barrier-for-new-user problem.  Our lead programmer has secured 3 months funding generously provided by evoorhees on behalf of SatoshiDICE on the promise the code will be back compatible with BTC.  Our motivation at FRC is that while our block-chain is small now we expect to be around a long time and don't want to have that download problem in the future so it's in our interest to solve this problem.

maaku, would you mind clarifing the scope of his project?

[maaku]

Impaler can get excited sometimes. I am preparing a blog post explaining in detail what I propose to accomplish. Here is a listing of the major points of order:

* The bitcoin Satoshi client (bitcoind and Bitcoin-Qt) will be updated to support two separate Merkle-tree indices: txid:n -> TxOut, and script -> TxOut.
* JSON-RPC commands will be added to query these indices, retrieving (1) the root hashes of the indices for a block; (2) proof of (non-)existence of an unspent transaction output; or (3) the unspent outputs associated with a script, with proof.
* New P2P messages will be created for making queries (2) and (3) against nodes exposing suitable service bits.
* Implement a merged-mined “meta-chain” which contains instead of transactions, checkpoints of the root hashes of the above indices.
* Modify the Satoshi client to start in security-level 2 (see above), and work its way to security-level 0 as a fully-validating node, allowing for quick startup times irregardless of blockchain size.

There are other related things which may be valuable to accomplish, such as pruned operation, and many, many small details left out. However any work on alternative currencies such as Freicoin is outside of scope, and will not be paid for by this stipend.