Ugh, just found out about the GigaOm meetup tonight. Registration is closed. :\

Monday at the current hash rate.

#28303. And the hard-fork is now scheduled for #28336.

Note that San Francisco is very, very far from the conference. Hope you got a hotel room closer.

Every 9 blocks it can adjust as much as +/- 1.055x. That's approximately a doubling (or halving) every 117 blocks, or a factor of +/- 10x every 387 blocks. So 1 to 1e6 or vice versa would take about 2322 blocks, plus another day/144 blocks or so for it to stabilize (the filter is slightly under-damped, so it overshoots and then corrects; you can see that in the real results above). How that works out in real time is a different story, because obviously 1 block != 10min for most of the adjustment period. From 1 to 1e9 about 10 days sounds about right and I trust galambo to have calculated that correctly. In the other direction it'll take quite a bit longer, as at first ~19 years (!) will pass between blocks. Hard-fork is your only real option in that case.

It is confusing and for that I apologize. We took the exact same source code and changed the cutoff block to earlier (block #28336). The new binaries replaced the old binaries at the same URL. So download the binary again, and install it again overwriting the old files.

@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).

@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.

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...


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.


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.


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.

Since @etotheipi is occupied for the next half-year and since I have a large interest in this proposal, I am offering my services to help make it happen. I have created a new thread with specific details of my proposal:

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

Various real-life events have conspired to find me in-between jobs right now. More than anything I would rather work on bitcoin full-time, and so I am taking a cue from @etotheipi and offering my services to the community to implement this proposal. Since this is a separate proposal from the OP's bounty, I have created a new thread:

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

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.

@smoothie, stop trolling.

@Bik, don't feed the trolls

They are change addresses, and you own them.

Jtimon, that is what they do currently. The list entries are used as the leaves of a binary tree. hashMerkleRoot in the block header is the root hash of this tree.

Why not hash160(txout.scriptPubKey)? I had assumed from the beginning that's what we'd be doing. "Addresses" are a UI issue - the protocol should only concern itself with scripts.

Update:

There was a mistake in the version that was released this morning. The Github repository and binary distributions have been updated to correct this flaw, however any version of Freicoin which was downloaded between the original announcement and now may be non-standard. We recommend upgrading your daemons immediately upon receipt of this message.

The current development timeline is:

1. New difficulty adjustment algorithm.
2. Freicoin Assets
3. Republicoin

Since it's pretty much just me doing development, these are progressing serially. So no, not much work has gone into Republicoin yet. I welcome contributions (ideas or code) from anyone else though.

Freiland was not socialized land, rather that was merely one avenue to implementation. The American Georgism is is a libertarian realization of Freiland, or at least Freiland-compatible.

EDIT: This was true of Gesell's work in general. He was a man of his times and as such an avowed statist. He though demurrage currency necessarily required a state monopoly on money. He also thought that his land-tax mechanism would have to be implemented through state ownership. Our opinion is that state monopoly is only one implementation pathway. In the case of Freigeld, p2p currency provides another more libertarian option. I personally remain optimistic that Freiland could be implemented with some sort of p2p auction to discover undeveloped value.