Ultimate blockchain compression w/ trust-free lite nodes

[ArticMine]

Before commenting on this thread I reviewed Satoshi Nakamoto's original paper: Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org/bitcoin.pdf, and I am left with two questions:

1) How is this proposal better or worse than 7. Reclaiming Disk Space in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to overall blockchain size management?

This works as a way to reclaim disk space provided you are starting with the whole block chain, but as presented, there is no way for one node to convey that stubbed tree to another node along with the assurance that only spent transactions have been removed.  If I run a node that prunes and stubs off a transaction showing I spent some coins, and then send you that pruned block, my spent coins look unspent to you.

Since it's a solution that's only useful to a node with the full block chain, and the real problem we face is more the downloading of the block chain rather than storing it, a solution that requires a full block chain download before anything can be safely pruned doesn't address the problem.

2) How is this proposal better or worse than 8. Simplified Payment Verification in "Bitcoin: A Peer-to-Peer Electronic Cash System" with respect to verifying payments?

That proposal suggests spending the funds and then watching to see if the rest of the network confirms the spend into a block before any useful verification is possible, or freshly receiving the funds while watching new blocks.  The idea discussed in this thread would allow instant verification of the existence of pre-existing funds without having to spend them first or downloading any blocks at all - and is actually not a different proposal, but the same proposal with significant improvements.

Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?

[casascius]

Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?

The subsequent block hashes don't tell you whether or not the funds are spent.  The only way you know funds are spent is that you know of a transaction that spends it.  There is no present way to know that certain funds are NOT spent unless you have the whole block chain coming after that transaction.

Remember, the goal is to eliminate a boundless multi-gigabyte download for new users.  The only way to solve that is to remove some information from that data set so it is smaller.  The party receiving the reduced data set can be assured that the data that's there actually belongs there, but he has no way to know whether the missing (pruned) data was actually supposed to be pruned.  This proposal addresses that.

[ArticMine]

Yes but under (1) what happens when you actually try to double spend the funds to me? I can still verify the double spend is in fact a double spend because I have the subsequent block hashes so what is the incentive to convey the block with the previous spend information removed?

The subsequent block hashes don't tell you whether or not the funds are spent.  The only way you know funds are spent is that you know of a transaction that spends it.  There is no present way to know that certain funds are NOT spent unless you have the whole block chain coming after that transaction.

Remember, the goal is to eliminate a boundless multi-gigabyte download for new users.  The only way to solve that is to remove some information from that data set so it is smaller.  The party receiving the reduced data set can be assured that the data that's there actually belongs there, but he has no way to know whether the missing (pruned) data was actually supposed to be pruned.  This proposal addresses that.

The fact that the correct data is pruned is secured on a second blockchain with merged mining. I can see the point of this for certain applications such as verifying the integrity of a physical Bitcoin without actually opening it up and spending the funds. So there is an advantage in that respect over the proposal in Bitcoin: A Peer-to-Peer Electronic Cash System.

[casascius]

The fact that the correct data is pruned is secured on a second blockchain with merged mining. I can see the point of this for certain applications such as verifying the integrity of a physical Bitcoin without actually opening it up and spending the funds. So there is an advantage in that respect over the proposal in Bitcoin: A Peer-to-Peer Electronic Cash System.

It's also useful for instantly screening an incoming unconfirmed transaction as being "good pending confirmation" versus "totally bogus and no chance of confirmation" without needing a block chain at all.

It's also useful not just for physical bitcoins, but if people start printing disposable bitcoin cash from their printer. (example: user clicks File -> Print Money to "be their own bank" instead of driving to an ATM and paying an ATM fee - something I see as wildly compatible with the average joe.  such self-printed bills would have the same requirements as physical bitcoins). 

[iain]

Apologies if this is a stupid question, but... would it not also be of benefit to make available, by the same sort of methods, a record of all the spent txouts? I'm thinking of how things can go when a future light client is querying (in untrusting style) a full client node - perhaps in exchange for a micropayment, or a subscription or whatever - about whether various txouts are spent or unspent. Here's an anthropomorphized dialogue. (Obviously the number of rounds back and forth is higher than it needs to be, just for the sake of anthropomorphizing the exchange.)

Light client (LC): hi, is this txout (.....) spent or unspent?
Full client (FC): unspent.
LC: ...and your proof? (I don't trust you, remember!)
FC: here's the merkle chain [or similar thing for whatever the data structure is exactly] leading from your txout to the root hash, which you can acquire from the network with suitably impressive [merged-]mining effort associated therewith. (transmits a pleasantly short merkle chain)
LC: ok, thanks very much! now, what about this txout: spent or unspent?
FC: spent.
LC: ...and your proof?
FC: well, uh, the proof is the fact that I'm not sending you a merkle chain like I did with the unspent one!
LC: sorry, but that's not a proof from my point of view!

With a record of spent txouts, the FC can send a merkle chain convincing the untrusting LC of a txout's spent status, rather than having to say "trust my absence-of-proof-of-unspent to mean it's spent".

(Maybe this is overkill? The FC could just send the transaction which spends the given txout. But maybe that was a transaction that "died" (failed to be bedded down in the winning blockchain) long ago, and for the FC to send it is misleading. Admittedly, the main reason for such "dyings" is losing a double-spending battle, in which case the relevant txout is likely still in fact spent, just not by the transaction the FC is advertising. But one can imagine scenarios where the LC wants proof not just of spent status, but of where it went, and a suitable data structure could support a reply of "it's spent, and here's the tx it went into, and here's a pleasantly short merkle chain establishing this".)

[casascius]

It would be a bit different than that. Rather than saying "spent" it would say and prove "not unspent".

The way it would do this is by sending the leaf nodes immediately surrounding where the unspent tx would go IF it existed, along with Merkle lineage. This would be like me proving to you there are no "fockheads" in the phone book by sending you the pages immediately surrounding "fockhead" alphabetically (e.g. Freitag thru Foster). This assumes everything is kept in a sorted order, and that is what is proposed in this thread.

[ArticMine]

It's also useful for instantly screening an incoming unconfirmed transaction as being "good pending confirmation" versus "totally bogus and no chance of confirmation" without needing a block chain at all.

It's also useful not just for physical bitcoins, but if people start printing disposable bitcoin cash from their printer. (example: user clicks File -> Print Money to "be their own bank" instead of driving to an ATM and paying an ATM fee - something I see as wildly compatible with the average joe.  such self-printed bills would have the same requirements as physical bitcoins). 

Basically any situation where one needs to prove what the balance is in a particular bitcoin address without actually spending the coins in that address.

[iain]

It would be a bit different than that. Rather than saying "spent" it would say and prove "not unspent".

The way it would do this is by sending the leaf nodes immediately surrounding where the unspent tx would go IF it existed, along with Merkle lineage. This would be like me proving to you there are no "fockheads" in the phone book by sending you the pages immediately surrounding "fockhead" alphabetically (e.g. Freitag thru Foster). This assumes everything is kept in a sorted order, and that is what is proposed in this thread.

Ah, of course! Thanks for the explanation.

Perhaps a record of spent txouts would still be of some value, to cover the case where a light client wants to query a full node with "prove to me how (i.e. into what tx) this txout was spent"? (But then again, maybe the need (if any) for such a query type would be sufficiently rare and specialized that running a full node oneself can be deemed the reasonable way to meet such an "expert" need.)

[maaku]

Without being too snarky, we have such an index: it's called the block chain. A full node would send the transaction in which it was spent, the block header that transaction was included in, and the path through the transaction Merkle-tree linking the two.

Now in the far, distant future it might be useful to have an index of block hashes so that the lite node doesn't even have to keep track of that information, but right now the overhead of maintaining that tree vs the storage cost (about ~1.25MB per year) doesn't make sense.

[iain]

Without being too snarky, we have such an index: it's called the block chain. A full node would send the transaction in which it was spent, the block header that transaction was included in, and the path through the transaction Merkle-tree linking the two.

Now in the far, distant future it might be useful to have an index of block hashes so that the lite node doesn't even have to keep track of that information, but right now the overhead of maintaining that tree vs the storage cost (about ~1.25MB per year) doesn't make sense.

Yes indeed, you're quite right, my worry was groundless. Well then, this is really exciting, the road to a secure lightweight client is open and clear!

[mp420]

I tried to read the OP again and I have a question. I apologize for the fact that I'm not very Bitcoin-literate and I may be asking things that are obvious.

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Or is there a zero-trust way for a full node to assure the lite-node that a TxOut hasn't been spent since the last altchain block that does not require the lite node to ever download full primary-chain blocks?

Of course if we drop the zero-trust requirement, it's trivial to set up a third party service that does the validation for the lite clients up to the last alt-chain block.

[Maged]

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Pretty much. That being said, keep in mind that this would allow someone to become a full node without much trust while ONLY having to download that much.

[maaku]

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Pretty much. That being said, keep in mind that this would allow someone to become a full node without much trust while ONLY having to download that much.

No, the lite client need only download the alt-chain headers since the last checkpoint, and then can request a path through the Merkle-tree to the unspent TxOut (or the surrounding outputs, if it has in fact been spent).

[casascius]

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Pretty much. That being said, keep in mind that this would allow someone to become a full node without much trust while ONLY having to download that much.

When a lite node is trying to check the balance of a particular address, it needs to have downloaded the (pruned) alt-chain and every block of the main chain that have been included in the blockchain since the last alt-chain block.

Pretty much. That being said, keep in mind that this would allow someone to become a full node without much trust while ONLY having to download that much.

No, the lite client need only download the alt-chain headers since the last checkpoint, and then can request a path through the Merkle-tree to the unspent TxOut (or the surrounding outputs, if it has in fact been spent).

Between the above two conflicting answers, the bottom one is the one I consider to be the more correct one.

Neither answer is false, but as I understand it, the way the OP wants to structure the tree, it would be possible to both prove or disprove the existence of funds with a simple query to someone else, and trust it with nothing more than the hash of the latest block.  Trusting that latest hash would typically require downloading the block headers, but not the entire blocks themselves.  What Maged says you can do, you can do, but what Maaku says you can also do, I believe you can also do.

[allten]

Still trying to understand if pruning the block chain is a good idea. I need a little help understanding.
One of the premises of bitcoin is that we only need to trust math and cryptography. So, anyone can download
the entire block chain and verify all the signatures, hashes, etc. and verify that it 100% complies with the math, cryptography, and bitcoin's protocols; however,
is this still possible once transaction with spent outputs are removed? It would seem that you would have to start putting trust in the mining community that
there wasn't a mass conspiracy to give themselves bitcoins.

Sorry, I really want to understand the detailed technicals so please have patience with my lack of understanding.
I'll do my best to understand if someone will explain it.

I can definitely see pruned/compressed blockchains would be beneficial for many applications, but it worries me that it would be the norm for everyone.

Thanks to all working on what I also see as one of the more pressing issues with bitcoin right now.

[socrates1024]

"Pruning the trees" is a red herring. Here is another way of explaining what this proposal is about.

Bitcoin already supports a Zero-Trust validation technique that is also 100% pruned - it only requires storing a single O(1) block hash. The problem is that it's blatantly inefficient. What we are doing with Merkle trees is altering the blockchain to make this technique, which is inherently fully pruned and zero-trust, more efficient.

[Inefficient O(N), Zero-trust, 100%-pruned technique] (It's just a counter example, bear with me) The entire bitcoin blockchain is already represented by the current block hash. Every client, even the lightest of light clients, stores the current block hash. If you know your current block hash, then you can't be fooled about any of the data in the chain. For example, if you want to check that a particular txoutput hasn't been spent, you iterate backwards through the blocks all the way to that transaction, checking that there's no previous transaction that spends it.

This isn't efficient. It literally involves processing the whole damn chain each time you validate a transaction. So, current light clients certainly don't do this - instead they have to trust a helper to validate that the transactions aren't double-spends. Full nodes have an easier time because they have the storage available to maintain an indexed database of unspent txouts.

[Merkle trees O(log N), Zero-trust, 100%-pruned] What we are all proposing in various ways is to alter how the blockchain history is represented in the current block hash. In addition to the previous block data, we will also include a 'snapshot' of the unspent txoutputs database in each block hash. This snapshot is the root of a Merkle tree, which gives us little shortcuts so we can validate a transaction much more efficiently, O(log N) per validation.

[maaku]

Neither answer is false, but as I understand it, the way the OP wants to structure the tree, it would be possible to both prove or disprove the existence of funds with a simple query to someone else, and trust it with nothing more than the hash of the latest block.  Trusting that latest hash would typically require downloading the block headers, but not the entire blocks themselves.  What Maged says you can do, you can do, but what Maaku says you can also do, I believe you can also do.

Yes, I should have been more explicit. I interpreted the original question as “what is the minimum necessary action that needs to be taken by a client to verify the status of a TxOut”. Maged's solution is perfectly valid and would result in the correct answer, but would also be more work for the client than is strictly necessary.

[mp420]

Thanks, I think I understand it now, the Merkle tree is arranged so that there's always a path from the latest hash to each unspent-TxOut, so only headers are required.

I think this idea is very clever and elegant. Of course the devil is in the implementation details. I'd very much like to see this implemented.

[BrightAnarchist]

I'd very much like to see this implemented.

Same here. So far more than 20 coins have been pledged  to the person or persons that implement this: https://bitcointalk.org/index.php?topic=93606 Hopefully more pledges soon...

[allten]

Before I read this I just want to quickly post that I personally, no matter whether justifiably or unjustifiably, I personally feel like this is the most pressing issue when it comes to Bitcoin's successful future and I really hope the core team has an order of priorities planed accordingly.

I too believe this is a critical issue for Bitcoin, as a whole.  I had floated the idea that handling blockchain size was critical, in the past, but other issues seemed more pressing for the devs at the time -- I didn't have a solid idea to promote, and the blockchain size wasn't so out of hand yet.

One nice benefit of this solution is that because it's an alt-chain, technically no core devs have to be on-board.  It can be done completely indepedently and operate completely non-disruptively, even with only the support of other devs who believe in it.  I'd certainly like to get core devs interested in it, as they are very smart people who probably have a lot of good ideas to add.  But one of the biggest upsides here is that it can be done completely indepdently.

Read some more of your proposal today and I now have a better idea of how it works and what you are accomplishing. Good proposal BTW.
I'm still very concerned that this development will make it so the full blockchain database will not be as accessible for download.
Its important for Bitcoin that anyone can fully audit the blockchain and only need to trust in math and cryptography and not the miners (even though it would be an extremely low probability that enough miners would conspire to get coins in the compressed blockchain).

I completely agree that there are many applications and situations that a compressed blockchain would be extremely useful. Please update us on your perspective of the balance between systems that should have the full block chain and ones that should use the compressed version. The way I read the OP proposal and probably because of my fears is that this compressed form is to replace the full block chain in all instances.