Ultimate blockchain compression w/ trust-free lite nodes

[Maged]

...and new miners would go back at least 10,000 meta-blocks...

Even if new miners chose not to do this, and successfully get tricked with a bogus view of the meta tree, their worst case is that they produce invalid blocks that become farts in the wind.  But I suppose mining pools would have a responsibility to do this.

I would argue that as long as new miners that are bootstrapping at any given time are only a small % of the hash power, they'd be stupid not to verify that far back. Any misplaced trust in the recent meta-blocks could cause them to create an invalid block, which would be a terrible finical loss. In fact, for this reason, many miners will likely opt to always hold the entire chain, and not trust the meta-blocks at all. I consider that a good thing.

Generally, only users and merchants should be using the meta-chain to bootstrap, although I won't be that disappointed if miners eventually have to use it too, as long as they're careful.

[casascius]

@realpra How will you connect to any node not controlled by an attacker if I the attacker control your upstream Internet and am redirecting your connection attempts to nodes I control?  You think you are connected to node X by its IP, but you are really connected to my node Y and have no way to know.

[Maged]

But consumers of the meta chain would depend on nothing that didn't have 6 confirmations (meta chain confirmations in the bitcoin block chain, not just 6 bitcoin blocks)

.
That would be DAYS in confirmation time in the beginning, who would use that to any great extent?

Many people. Imagine if all you had to do today to bootstrap was to download a week of blocks. A low-end laptop can do that in less than an hour today, and that's without all of the code optimizations the Bitcoin implementations will have in the future, not to mention hardware.

[Realpra]

@realpra How will you connect to any node not controlled by an attacker if I the attacker control your upstream Internet and am redirecting your connection attempts to nodes I control?  You think you are connected to node X by its IP, but you are really connected to my node Y and have no way to know.

Its called SSL I think.

Say I store the public keys for:
1. My friend Bob.
2. Guy who posted his key on a forum.
3. MtGox.

Since I am lazy that's it.

You send me invalid money and I check those nodes.

It now either becomes apparent that someone is blocking my connection OR one of them will likely NOT be colluding with you.

You can fake IPs but you have no way to fake that you have their private keys for my encrypted communication so my client will just display "You are under attack!!!".

Many people. Imagine if all you had to do today to bootstrap was to download a week of blocks. A low-end laptop can do that in less than an hour today, and that's without all of the code optimizations the Bitcoin implementations will have in the future, not to mention hardware.

I mean what customer/merchant would wait days to know whether payment was made or not?

edit: A swarm client would run on a smartphone and act as a full node btw.. Could even mine a bit in a pool.

[DiThi]

You are discussing two issues that IMHO it's already resolved in my proposal or a followup:

Efficient tree update: The update functions only recalculates the hashes affected by the changes of each block. Those changes can be reversed, as long as the block is valid (i.e. there's no double spends), therefore it will be easy to roll-back in case of getting orphaned blocks.

Where to save the roots: In my proposal I explain how to roll it out in the coinbase of the existing chain, but nullifying the risk of a chain split by rejecting blocks with invalid root only when there are more than 55% of valid roots in a specific time span.

For extra security (and this is what isn't originally in my proposal), the root should be accompanied by a hash of the previous+current valid roots, effectively making a secure blockchain from day one. But after it's deployed widely, it will be unnecessary, as we'll know miners will reject blocks with invalid roots. Miners won't reject blocks without roots. Blocks with valid root but without this blockchain-ish hash won't be rejected either (so we can drop this hash when it's not longer necessary).

In this way, creating a separate chain is just a temporal fix for something that will be in the main chain some day.

[galambo]

This idea could end up having more uses than enabling lightweight clients.

For instance, forking the main blockchain is practically impossible today. Even if someone came around with worthwhile changes to the storage subsystem or the scripting subsystem we could never implement it. The moment the two chains got out of sync you need two copies of the block chain .dat that are mostly identical.

With this proposal a certain "snapshot" in the metachain could be specified as the branch point for the blockchain. This snapshot could be used to refer back to the legacy system.

The proposal would allow experiments and tests using the real chain. The developers have been sort of paralyzed because they cannot change many things in the implementation because there's not really any way to change it.

If one of these experimental branches became popular enough, a new branch could be created on the official branch with ample notice to all users.

Also, having a chain of snapshots would allow the network to avoid new and unforeseen attacks. If one user managed to do something detrimental in the block chain to his advantage and every other user's disadvantage (like a sustained 51% attack, or an exploit), the community could achieve a consensus to "go back in time" to a previous snapshot with a patched client.

[DiThi]

About rolling out new features and avoiding block chain splits, what we need is a good automatic system to automatically and democratically add any feature. Just like the implementation schedule of p2sh but being more like my proposal: time-flexible, with an additional temporal sub-chain, and for any feature. It may be difficult and problematic to code it only for one feature, but IMHO it's worth it if it's a generic implementation-deprecation system for determining the validity of blocks.

[casascius]

Its called SSL I think.

I would be pretty surprised if nodes started identifying themselves through SSL certificates.

That said however, what it looks like you have proposed is tiers of nodes and a structure that includes supernodes.  I actually agree with you that such a structure will be critical to scalability of the network.

[etotheipi]

You are discussing two issues that IMHO it's already resolved in my proposal or a followup:

Efficient tree update: The update functions only recalculates the hashes affected by the changes of each block. Those changes can be reversed, as long as the block is valid (i.e. there's no double spends), therefore it will be easy to roll-back in case of getting orphaned blocks.

Where to save the roots: In my proposal I explain how to roll it out in the coinbase of the existing chain, but nullifying the risk of a chain split by rejecting blocks with invalid root only when there are more than 55% of valid roots in a specific time span.

For extra security (and this is what isn't originally in my proposal), the root should be accompanied by a hash of the previous+current valid roots, effectively making a secure blockchain from day one. But after it's deployed widely, it will be unnecessary, as we'll know miners will reject blocks with invalid roots. Miners won't reject blocks without roots. Blocks with valid root but without this blockchain-ish hash won't be rejected either (so we can drop this hash when it's not longer necessary).

In this way, creating a separate chain is just a temporal fix for something that will be in the main chain some day.

DiThi,

I see this from a different angle.  

(1) The tree-part of my proposal should be seen as an extension of yours.  I'm sure my idea was inspired from reading yours a long time ago.  The difference being that extra complexity is added to the tree structure to accommodate the most common use-case:  requesting address balances.  My tree structure guarantees that you can not only get any TxOut, but you can get all TxOuts for a given address/script and have no doubts that it's correct.

I believe this is a worthy trade-off, comared to your tree structure, as it removes a channel of uncertainty for the operator, and removes a channel for shenanigans from those who wish to deceive you.  And in the end, it's not actually that much more complicated.  It's simply more-tailored for the way that users need to access the network.

(2)  As echoed by others, I believe that a hard-forking blockchain change is going to only happen in the event of a crisis.  To do so requires more than democracy -- it will seriously impact the entire network in a detrimental way.  There are users who are still using version 0.3.X bitcoin clients not because they want to, but because it works, and they don't follow the forums or Bitcoin news or anything of the sort.  And the hard fork exposes them to all sorts of malicious behavior by others who would exploit their ignorance of current events and manipulate the abandoned chain that they are stuck on.

To maintain confidence in the system, a hard fork is going to need more than democracy -- it's going to need super-majority, probably 80-90% ... and gaining that level of consensus is pretty much impossible for new ideas that are not well-understood -- unless the idea has been in the wild, and in use for many months/years and is already used by 80%+ people.

The idea of using a second blockchain is actually a way of creating a "staging area" for such ideas on the main network (like galambo said) without actually risking exposing that network to any of the unforeseen issues that could arise.  It can be used to add such functionality to the network without actually changing the network.

In this way, the meta-chain can grow and develop as people start using it and understanding it.  People start building infrastructure on the availability of the information in that chain.  Once it has become ubiquitous enough and time-tested as a pillar of a part of the network, then you have 80%+ agreement amongst users without even having to ask for it.  At this point, a hard-fork is entirely feasible -- or at least orders of magnitude less disruptive.

You're right, it's not the only way, but I think it's about as good as it's going to get.

[DiThi]

My tree structure guarantees that you can not only get any TxOut, but you can get all TxOuts for a given address/script and have no doubts that it's correct.

I always saw that a separate issue/feature of my proposal (i.e. not necessary for starting and deploying an implementation), also making things simpler. Sometimes (actually most of the time) you just need to know an output hasn't been spent. If you need the balance and someone gives you a list of outputs, you can be sure those outputs are unspent; the only thing remaining is knowing if *all* the outputs are given to you.

That's easy to solve. I'm thinking of several solutions that doesn't require full nodes to build and verify the tree. For example having a separate tree, address-based instead of chain-based, which just stores the number of unspent outputs (removing the key if the value is 0).

Initially, though, we can just query several nodes to give us the count of unspent outputs and trust the majority.

[etotheipi]

My tree structure guarantees that you can not only get any TxOut, but you can get all TxOuts for a given address/script and have no doubts that it's correct.

I always saw that a separate issue/feature of my proposal (i.e. not necessary for starting and deploying an implementation), also making things simpler. Sometimes (actually most of the time) you just need to know an output hasn't been spent. If you need the balance and someone gives you a list of outputs, you can be sure those outputs are unspent; the only thing remaining is knowing if *all* the outputs are given to you.

That's easy to solve. I'm thinking of several solutions that doesn't require full nodes to build and verify the tree. For example having a separate tree, address-based instead of chain-based, which just store the number of unspent outputs (removing the key if the value is 0).

Initially, though, we can just query several nodes to give us the count of unspent outputs and trust the majority.

Well that's where we are differing in opinion.  Majority peer-influence is cheap relative to majority mining power.  That's not to say it's an easy exploit, or that it would be in any way worth it.  But I see it as a source of uncertainty, and a channel waiting to be exploited in some way we haven't thought about.  I think the added complexity is well worth closing the "hole" completely.  Though not everyone feels it's actually a hole. 

I personally think it makes more sense, anyway -- you can still get a single TxOut with O(log(N)+log(M)) if you really want it -- but most of the time, it would be new nodes hopping on the network with imported wallets, and simply want to get their balance.  This tree structure takes that use case into account directly and doesn't leave a shred of uncertainty that they got the right answer.

[Realpra]

Its called SSL I think.

I would be pretty surprised if nodes started identifying themselves through SSL certificates.

I would also be surprised if someones upstream connection was stolen

At least with SSL known, it would only happen once before an SSL update was made.

That said however, what it looks like you have proposed is tiers of nodes and a structure that includes supernodes.  I actually agree with you that such a structure will be critical to scalability of the network.

No my structure theoretically could operate entirely with swarm clients.

However in the case of mining pools you might have one node orchestrating which hash will be worked on.

The guy of this thread has super nodes, I don't. Maybe you got confused that way.

I don't like super nodes, I think it's bad centralized design.

DiThi

Could you give me a link to your proposal?

[casascius]

I would also be surprised if someones upstream connection was stolen

Perhaps you are unfamiliar with how the Internet works in places like Iran and China, where not only do they do MITM attacks on their citizens, they coerce SSL certificate providers to issue them bogus certificates so their citizens will be caught unaware.

Bitcoin needs to work there, too.

http://www.bgr.com/2011/08/30/iranian-government-said-to-be-using-mitm-hack-to-spy-on-gmail-other-google-services/

[unclescrooge]

About rolling out new features and avoiding block chain splits, what we need is a good automatic system to automatically and democratically add any feature. Just like the implementation schedule of p2sh but being more like my proposal: time-flexible, with an additional temporal sub-chain, and for any feature. It may be difficult and problematic to code it only for one feature, but IMHO it's worth it if it's a generic implementation-deprecation system for determining the validity of blocks.

Maybe I'm misunderstanding the change your talking about. But I think this is dangerous.I use bitcoin because i trust the protocol behind to never change. If the majority or the devs can push a change in protocol, then I'm out. A way to compress the blockchain fine. A fork, hard or soft... mmmmm seems dangerous to me.

[galambo]

(2)  As echoed by others, I believe that a hard-forking blockchain change is going to only happen in the event of a crisis.  To do so requires more than democracy -- it will seriously impact the entire network in a detrimental way.  There are users who are still using version 0.3.X bitcoin clients not because they want to, but because it works, and they don't follow the forums or Bitcoin news or anything of the sort.  And the hard fork exposes them to all sorts of malicious behavior by others who would exploit their ignorance of current events and manipulate the abandoned chain that they are stuck on.

To maintain confidence in the system, a hard fork is going to need more than democracy -- it's going to need super-majority, probably 80-90% ... and gaining that level of consensus is pretty much impossible for new ideas that are not well-understood -- unless the idea has been in the wild, and in use for many months/years and is already used by 80%+ people.

The idea of using a second blockchain is actually a way of creating a "staging area" for such ideas on the main network (like galambo said) without actually risking exposing that network to any of the unforeseen issues that could arise.  It can be used to add such functionality to the network without actually changing the network.

In this way, the meta-chain can grow and develop as people start using it and understanding it.  People start building infrastructure on the availability of the information in that chain.  Once it has become ubiquitous enough and time-tested as a pillar of a part of the network, then you have 80%+ agreement amongst users without even having to ask for it.  At this point, a hard-fork is entirely feasible -- or at least orders of magnitude less disruptive.

You're right, it's not the only way, but I think it's about as good as it's going to get.

Thank you for your feedback. I wasn't quite sure if people would agree that this could help automate the BIP process.

Maybe I'm misunderstanding the change your talking about. But I think this is dangerous.I use bitcoin because i trust the protocol behind to never change. If the majority or the devs can push a change in protocol, then I'm out. A way to compress the blockchain fine. A fork, hard or soft... mmmmm seems dangerous to me.

The only way you would notice this kind of fork is if you applied the experimental patch to your Bitcoin client. Think about it like another "test net."

[casascius]

I actually disagree that a hard fork would be required to implement this.  A simple majority of mining power would be enough.  New blocks meeting the new requirements would still be valid blocks to the old clients, the only change being that the majority of miners would work to orphan blocks not containing the proper meta tree root, so miners mining with an old client would have an impossible time getting any blocks.

[cantor]

So as I understand it, the issue here is to build a meta-chain that would contain digests of the contents of the main blockchain, in a way that would allow a lite-client to query a server for information stored into the blockchain, and use the meta-chain to verify the answer.  And even the meta-chain itself would be constructed in such a way that it can be partially queried and verified using only its root hash, meaning the lite-client would only need a bound amount of storage.

I hope I'm doing a good summary of what is being discussed in this thread, considering that it's pretty late at night here   At any rate, subscribing, this looks really interesting.

[etotheipi]

So as I understand it, the issue here is to build a meta-chain that would contain digests of the contents of the main blockchain, in a way that would allow a lite-client to query a server for information stored into the blockchain, and use the meta-chain to verify the answer.  And even the meta-chain itself would be constructed in such a way that it can be partially queried and verified using only its root hash, meaning the lite-client would only need a bound amount of storage.

I hope I'm doing a good summary of what is being discussed in this thread, considering that it's pretty late at night here  At any rate, subscribing, this looks really interesting.

Yeah, fairly accurate.  I'll re-summarize here because my view of my own proposal has evolved over discussions of the last few days, so I figured it was a good time to restate it, anyway


The first goal is blockchain pruning:  the amount of information needed to store the entire state of the network at any point in time is much less than the entire blockchain history.  You can basically just save the "outer surface" of the transaction map instead of the entire history and still do full validation.  

So I propose a structure that achieves this compression, and further organizes it accommodate a specific, common problem we want to solve anyway:  a new node gets on the network with its imported wallet and doesn't need the whole chain, but would like to get a complete history of it's own transactions in a verifiable manner.  I argue that with a more-straightforward "snapshot" tree, there's still room for deception by malicious peers, albeit not a whole lot.

Either way, I believe it's possible that new nodes can use a structure like this one to get up in running with full confidence in less than 50 MB of downloading, even in the far future.  And such a solution will be necessary, so let's hash it out now...

However, for lite-nodes to reliably use the new information, there must be some kind of enforcement that miners provide correct answers when updating the root node.  This could be done by hard-forking the network by changing the headers to require a valid root node, soft-forking by requiring a specific tx or coinbase script to contain a valid root, or as I propose: create a separate chain solely to allow mining power to "vote" on the correct snapshot root.  Such a solution would then be completely optional and transparent to anyone who doesn't know or care about it -- though I would expect most miners and developers would be anxious to leverage it.

As galambo brought up -- the alt-/meta-chain idea is a kind of "staging area" for this new piece of the protocol.  Once the community starts using it and becomes dependent on the information it provides, it could be integrated into the main chain (via hard- or soft-forking) as it would have super-majority support at that point.

[2112]

So as I understand it, the issue here is to build a meta-chain that would contain digests of the contents of the main blockchain,

This isn't a good summary.

The issues are:

1) saving local storage space by purging spent transaction info, but at the same time maintaining cryptographic verifiability of the stored info.

2) augmenting the p2p protocol such that in order to participate in network client doesn't have to start from the genesis all the way until now, but start at now (or close past) and go back in time only to the oldest coin dealt in the transaction, not all the way back to the genesis.

3) relaxing the original peer-to-peer protocol to allow at least partial parasite-to-peer operation, where parasite is a pretend-peer that doesn't fully verify the relayed information but just repeats the latest rumors really fast. The goal is to limit the possible damage caused by such network rumormongers.

My description probably isn't clearer but it is closer to the truth.

[doobadoo]

Can compression be used as an intermediate step along the way.  That is, is the blockchain stored on the disk in an efficient manner?  Also, why do noobs have to dl the whole block chain from peers?  Its soooo slow.  Couldn't each release come along with a zipped copy of the blockchain up to the date it was released, along with a hard-coded hash of that block chain up till then with a built in check.  That way the user can just dl the whole shebang in one swoop.

These of course are not permanent measures but maybe as interim fixes for now.