Ultimate blockchain compression w/ trust-free lite nodes

[ThomasV]

I don't think so.  If you are at ABCD and it has only 3 children, "ABCDE" "ABCDP" and "ABCDZ", there's still only 3 seeks.  You seek for "ABCDA", and the iterator ends up at ABCDE (which is the first element equal-to-or-greater-than your seek value).  So you know that's the first child, and that there's no point in seeking for "ABCDB", "ABCDC" etc.  Then your next seek is "ABCDF", which puts you at "ABCDP".  Rinse and repeat.

oh indeed, I did not see that. thank you

[lunarboy]

Fascinating. Logical. Influential...... Open source development such a privilege to watch.

[maaku]

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

[2112]

I originally wrote this post couple of days ago in response to another humorous/pithy comment. However the original comment got deleted before I finished editing it and it made almost no sense afterwards. It appears that this thread is now approaching its end and I decided to post re-edited version of it to put it in a permanent public record.

The original Greenspun's tenth rule of programming states:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

I propose a modified version of it pertaining to Bitcoin and other blockchain-based cryptocurrencies:

Any sufficiently complete attempt at implementing Bitcoin will contain an ad hoc, informally-specified, bug-ridden, slow implementation of half of MUMPS.

I'm trying to suggest that MUMPS should be used to implement Bitcoin. I'm just observing that there will be tremendous amount of work expended to re-invent and re-implement one key feature of MUMPS: larger-than-core sparse hierarchical tree storage with all the expected ACID properties.

For those who are interested why the technology from circa 1975 outperforms all previous attempts at blockchain storage (both full and pruned) I have the following links:

• http://en.wikipedia.org/wiki/InterSystems_Cach%C3%A9 , closed-source, but a free single-user version available for evaluation. Has a great help system and thus is great for quick research and tests.
• http://en.wikipedia.org/wiki/GT.M , nicely open-sourced but rather hard to start productive work in it.
• http://www.cs.uni.edu/~okane/source/ISR/isr.html , Information Storage and Retrieval course at University of Northern Iowa using MUMPS and C++ Multidimensional & Hierarchical Toolkit. All software open-sourced and very easy to use, but targeted at teaching, not production.

It is a shame that I don't know of any open-source software that is compatible with the MIT license and other requirements specific to Bitcoin.

[Peter Todd]

In case anyone misses 2112's remarkably obscure troll with regard to MUMPS, see this: http://thedailywtf.com/Comments/A_Case_of_the_MUMPS.aspx

[Sukrim]

I might start mining again if this gets implemented!
Also as long as there is a UTXO block merge mined every few hours or even days this is still much better/faster than the current situation with checkpoints + the bootstrap.dat torrent.

By the way, thanks for not rushing this and debating about proper solutions longer as this is in my opinion one thing that can drive forward bitcoin adoption a LOT more than another porn site accepting them! The frustration and confusion when starting a full client for the first time for sure is one of the major reasons why this is still seen as a "geek tool". It is important to get this right on the first try.

[maaku]

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?

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

[socrates1024]

IMO your 3-point plan is missing out on the best aspect of having a Merkle UTXO. It's unnecessary for Level 2 to be a weaker security "SPV+", it can still do Full Validation even without having to do download the whole chain. The reason why is that you can check EVERY TX IN A BLOCK (not just ones involving your wallet) just by knowing the root hash of the UTXO and requesting short checkable proofs from untrusted nodes.

At one point I convinced etotheipi of how this works, and he basically said he hadn't realized that it would be possible. https://bitcointalk.org/index.php?topic=101734.0 I made a reference implementation using a redblack tree but it would be totally fine to substitute a merkle patricia trie for it.

[maaku]

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

[etotheipi]

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

If I understand (remember) correctly, Socrates1024 is making the point that someone could theoretically do mining without having the full blockchain.  All they need is the root hash of the last block, and to see the full blocks coming in.  This is because you can verify that the UTXOs being spent by the new transactions are unspent with a simple branch request from a peer.

Right now, if you wanted to do this... you can't.  You can easily prove that a UTXO once existed, but you don't know it was spent since then without downloading all the blocks since then and verifying no spends.  But with this UTXO tree structure, you can prove both inclusion and exclusion of UTXOs on any given block.  It may not be that big of a distinction today, but perhaps in the future when you require TB of storage, that could make a difference. 

But I do question how much is gained -- since only some upper limits ratio of the network could operate like this without being extremely burdensome on the actual full nodes.  And I'm not confident that these lite nodes could expect reliable branch information from each other even if they all "agreed" to hold, say, 1% of the full thing.  I certainly wouldn't want to risk my miner becoming idle because it's having trouble finding some subset of the tree (or large subsets of the network going dark for that reason)

Have I understood this properly?


One thing that has come up before, is that I'd like to see an additional piece of information added to the header:  fast-forward data each block.  sipa has already implemented undo data because you need it in the event of a reorg, and I tried to convince him he might as well include fast-forward data, because you save some 75% bandwidth on transmission of block data (to those that request it).  If the OutPoints-removed-and-TxOuts-added data is organized into a merkle tree, then that root could be included in the merkle tree, and such UTXO-only nodes would be able to avoid pulling whole blocks.  sipa didn't like the complexity for a "constant" factor, but I think 75% is worthy constant factor.  Unless I'm missing something...

[TierNolan]

If I understand (remember) correctly, Socrates1024 is making the point that someone could theoretically do mining without having the full blockchain.  All they need is the root hash of the last block, and to see the full blocks coming in.  This is because you can verify that the UTXOs being spent by the new transactions are unspent with a simple branch request from a peer.

I think providing a way to pre-package blocks would help here.  You send the block you are mining in advance (subject to spam protection).

Another option is to allow transactions to be packaged.  You send a hash + 64 transactions.  Later, you can include all 64 just with the header hash.

[socrates1024]

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

Sure, hardware wallets are an example. You could plug it in to an untrusted host computer that has already downloaded the proof data. Or even a mobile phone wallet, where you don't have much bandwidth during the day so it's SPV, but maybe it could sync up with the network overnight when it's around an untrusted wifi.

[LvM]

@etotheipi:
Is it REALLY impossible for each client
"to download just the unspent-TxOut list for each address in their wallet, and verify that list directly against the blockheaders."
...quickly and easily without your proposed complications with alt/meta-chains ?

I cannot believe that. If so, this seems besides the "Cash/Change" concept*) another remarkable bug at the lowest level.

*) CASH/CHANGE simulation vs. GAAP fundamentals
https://bitcointalk.org/index.php?topic=211835

[d'aniel]

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

Sure, hardware wallets are an example. You could plug it in to an untrusted host computer that has already downloaded the proof data. Or even a mobile phone wallet, where you don't have much bandwidth during the day so it's SPV, but maybe it could sync up with the network overnight when it's around an untrusted wifi.

The big value of validation-without-the-blockchain seems to me to be when it's combined with the fraud proof/challenge idea, where an SPV node can reject invalid blocks upon receiving a short proof or challenge that proves the block was formed incorrectly (e.g. nonexistent txin, double spend, invalid coinbase).   It turns out all important cases of fraudulently formed blocks can be covered by these - including cheating on the block reward, after a simple change to the way the Merkle trees are constructed.  This would greatly increase the trust model of an SPV node, under the assumption that it's connected to at least one well-connected, honest peer.

The more honest nodes there are auditing blocks and forming these fraud proofs/challenges, the better chance SPV nodes will promptly and reliably receive them.  This is where the validation-without-the-blockchain idea really shines IMO, since it allows resource constrained nodes to contribute to overall network security, but without biting off more than they can chew - they only partially validate blocks.  I tend to think of this as the "correct" way to preserve decentralization while scaling up block sizes.

[jtimon]

@maaku, you said yesterday we left an open conversation more or less here:

maaku: Metachain miners could get lazy and not maintain the indexes properly.
jtimon: If the indexes are in the main chain there wouldn't be such a problem.
maaku: In the main chain the thing gets worse.
jtimon: How that's possible? blocks with wrong indexes will be orphaned.

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

@LvM
I think the purpose of the "change" approach is to make obfuscation easier. You could do GAAP and maintain a sequence number for the transactions from each account like Ripple does.
You claim that would reduce the size of the chain by half. But how do you know how many keypairs will people create to obfuscate their finances?
Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them. That's why you can't destroy accounts (funded keypairs) in Ripple. You may say "there's no replay, all BTC funds will be gone". Well, I'm thinking about people reissuing custom assets from "resurrected" accounts.
Well, probably we should go to your thread to discuss this anyway...

[maaku]

@maaku, you said yesterday we left an open conversation more or less here:

maaku: Metachain miners could get lazy and not maintain the indexes properly.
jtimon: If the indexes are in the main chain there wouldn't be such a problem.
maaku: In the main chain the thing gets worse.
jtimon: How that's possible? blocks with wrong indexes will be orphaned.

Actually we should let gmaxwell respond to this, as I was really just relaying his concerns expressed to me at the conference. I think perhaps he is considering the case where the information is included in the bitcoin coinbase, but not actually enforced as a protocol rule?

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

True except for the miner part. You can fork the blockchain just as easily with invalid asset transactions.

[jtimon]

Actually we should let gmaxwell respond to this, as I was really just relaying his concerns expressed to me at the conference. I think perhaps he is considering the case where the information is included in the bitcoin coinbase, but not actually enforced as a protocol rule?

I'm really interested. If the indexes are enforced by the protocol I see no problem.

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

True except for the miner part. You can fork the blockchain just as easily with invalid asset transactions.

I don't understand.
If I validate the full chain leaving out the ones that nobody says still exist and only download the hashes of the transactions involved...
Never mind. Once a death asset appears with living assets in the same transaction you have also to validate the full asset, recursively.
So probably miners need to validate death assets anyway, am I thinking this straight or did I got lost on recursion?

Anyway, asking for the full proofs on the whole current UTXO would let you mine at level 1.

1) You ask for the longest header chain.

2) You ask for the UTXO

3) You ask for the full proofs of all outputs, not just yours. Maybe starting with yours.

4) Maybe in parallel, or only with wifi, or whatever, you download the whole chain from the in-chain signed torrent.
You validate everything until "your checkpoint" independenlty.

What happens when there's a reorg?

1) You change "your checkpoint" to the last common block so you ask for the that block's UTXO

2) You ask for the new UTXO at the top

3) You ask for the missing proofs you lack for the new UTXO.

Hummh, maybe GAAP is also better for reorgs...
And in fact I already solved the "immortal accounts" on the new Ripple forum by substituting the sequence number for the hash of the previous transaction from that account.
LvM is right, GAAP and a ledger instead of the UTXO like Ripple would make things much simpler.
Is there any obvious arguments in favor of the change-like design I am missing?
Is there anything that makes the UTXO cooler than a simple ledger?
Anyway, that's too big of a change, but since nobody answered in LvM's thread and I'm doubting...

[maaku]

I got confused following your logic, but the conclusion is right. Miners must validate everything or the whole system falls apart.

As for ledger vs. UTXO, these UTXO indices give the advantages of a ledger (being able to look up final balances, for example), while maintaining an underlying block structure. But that connection to the underlying system is important - you still need it if you are going to create new transactions, for example. Does that make sense?

[aaaxn]

Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them.

You can simply use block number of last account operation. There is no way you get same sequence twice this way.

As for ledger vs. UXTO I think all this concept of outputs and scripts doesn't make sense and should be dropped and replaced with account balances and account types (EG. multisig accounts)

[maaku]

Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them.

You can simply use block number of last account operation. There is no way you get same sequence twice this way.

As for ledger vs. UXTO I think all this concept of outputs and scripts doesn't make sense and should be dropped and replaced with account balances and account types (EG. multisig accounts)

What doesn't make sense?  Outputs and scripts is how bitcoin works.