Pages:
Author

Topic: Ultimate blockchain compression w/ trust-free lite nodes - page 19. (Read 87937 times)

legendary
Activity: 1428
Merit: 1093
Core Armory Developer
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.



full member
Activity: 156
Merit: 100
Firstbits: 1dithi
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.
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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.
full member
Activity: 156
Merit: 100
Firstbits: 1dithi
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.
sr. member
Activity: 966
Merit: 311
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.
full member
Activity: 156
Merit: 100
Firstbits: 1dithi
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.
hero member
Activity: 815
Merit: 1000
@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.
legendary
Activity: 1204
Merit: 1015
Quote
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
@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.
legendary
Activity: 1204
Merit: 1015
...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.
hero member
Activity: 815
Merit: 1000
I'm don't understand completely all your proposals, but I stick with the one that works in all cases with this rule: "trust no one".
My solution is basically trust that 1 guy out 1000 is honest - or run the client you are today with massive lag/huge fees.
hero member
Activity: 815
Merit: 1000
He can't control you if you choose to connect to say the mtgox node or some other trusted node via public key encryption.

The attacker would be unable to understand such secure messages - provided you have a known good public key to write to.

I don't see that happening any time soon, as it would be opposite Bitcoin's design goals of decentralization.
I think you misunderstand, you don't need to connect to a TRUSTED node per say just ANY node that is not colluding with the attacker.

ANY will do. Could even be a different ATTACKER that didn't know what the FIRST attacker wanted hidden!

As for secure communication that is pretty standard, BTC should have it already if it doesn't.

So that is basically a fork right? My solution doesn't have that.

Right, instead your well-intended solution has a double spend vulnerability easily exploited by any upstream provider that can only be mitigated by connecting to a known centralized server that you think you can "trust" (the opposite of peer-to-peer).
Read above.

Quote
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?

Quote
Your hash power would have to exceed that of those putting honest logs, essentially you would be attempting to attacking the meta chain and would need 51% of the meta chain's hash power to succeed.
You would be relying on SOMEONE checking that all those 6 logs are complete and then what? REPORTING it if not? Dumping the entire chain?
What miner would do that for an alt chain log?

As for reporting, yep you just arrived at part 1 of my solution, welcome.
staff
Activity: 4270
Merit: 1209
I support freedom of choice
I'm don't understand completely all your proposals, but I stick with the one that works in all cases with this rule: "trust no one".
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
He can't control you if you choose to connect to say the mtgox node or some other trusted node via public key encryption.

The attacker would be unable to understand such secure messages - provided you have a known good public key to write to.

I don't see that happening any time soon, as it would be opposite Bitcoin's design goals of decentralization.

So that is basically a fork right? My solution doesn't have that.

Right, instead your well-intended solution has a double spend vulnerability easily exploited by any upstream provider that can only be mitigated by connecting to a known centralized server that you think you can "trust" (the opposite of peer-to-peer).

Anyway what if I am a miner and I include a signature of a incomplete log in my base?

The ONLY way to tell my log was incomplete would be to download the entire chain.

Yep, you are right: so long as the meta chain were experimental and non-mandatory, anybody could throw anything they want in the coin base, including a completely falsified meta merkle root.  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).  Your hash power would have to exceed that of those putting honest logs, essentially you would be attempting to attacking the meta chain and would need 51% of the meta chain's hash power to succeed.
hero member
Activity: 815
Merit: 1000
My solution did not seek consensus, as I said once you have the branches with transactions linked to the main hash you KNOW they are true.
Even if 90% of the network is withholding the "spent it all" transaction you would easily be able to get it from just ONE honest node.

The problem is that you still have no certain way to know if a transaction is being withheld.  An attacker controlling your upstream connectivity (an attack that happens all the time in the real world) can easily engineer your view of the network such that you only see the nodes of the attacker's choice.
He can't control you if you choose to connect to say the mtgox node or some other trusted* node via public key encryption.

The attacker would be unable to understand such secure messages - provided you have a known good public key to write to.

(* Not really trusted, just ANYONE who doesn't realize what txs the attacker want withheld.)

Quote
By imposing a requirement that the merkle root be in the main chain's coinbase.  That essentially makes it "mandatory merged mining".

So that is basically a fork right? My solution doesn't have that.

Anyway what if I am a miner and I include a signature of a incomplete log in my base?

The ONLY way to tell my log was incomplete would be to download the entire chain.

Quote
Such an idea might start out as a novelty
A swarm client would be instantly useful and has similar/same programmatic complexity as this.

Heck mining pools might be richly rewarded by adopting swarm clients. (by being able to have larger pools/more txs/fees in a block)

Quote
A false meta tree would be outed by its root not matching what's in the block headers of the main chain.
I was lucky enough to put it there as a miner, so the signature has been merged mined, all inside txs are valid - I just didn't include the one where I moved a bunch of coins.

Only way to oust that is checking the entire chain yourself.

I think with every miner motivated to do the above attack my solution is safer.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
...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.

As long as at least one person forever stores the entire blockchain (but maybe even not, if people trust that the meta chain was accurate for the past several years), those limits should provide plenty of warning and safety in case the meta chain gets 51% attacked.

And if the meta chain could be made an integral part of Bitcoin to the point that mining it was mandatory to mine Bitcoin, then the only way to 51% attack the meta chain would be to successfully 51% attack Bitcoin, which I would find comforting.
legendary
Activity: 1204
Merit: 1015
An individual user client would likely use the tree 6 meta-blocks or more back to ensure that they are getting an accurate picture of things. Merchants would likely go back 100-1000 meta-blocks, and new miners would go back at least 10,000 meta-blocks,

As long as at least one person forever stores the entire blockchain (but maybe even not, if people trust that the meta chain was accurate for the past several years), those limits should provide plenty of warning and safety in case the meta chain gets 51% attacked.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
My solution did not seek consensus, as I said once you have the branches with transactions linked to the main hash you KNOW they are true.
Even if 90% of the network is withholding the "spent it all" transaction you would easily be able to get it from just ONE honest node.

The problem is that you still have no certain way to know if a transaction is being withheld.  An attacker controlling your upstream connectivity (an attack that happens all the time in the real world) can easily engineer your view of the network such that you only see the nodes of the attacker's choice.  I am not sure many people will view that as acceptable.  This is very important, because if someone can withhold from you the knowledge that an incoming transaction is invalid because it's a double-spend, then you're vulnerable to double-spending attacks.

How is the alternate merkle tree even safe with no/little mining? I could make a false log, sign it with minimal mining or put it in the blockchain (both easy) and fool you all right?

By imposing a requirement that the merkle root be in the main chain's coinbase.  That essentially makes it "mandatory merged mining".

Such an idea might start out as a novelty, where the tree is maintained voluntarily and can't really be relied upon, but results in a huge improvement when you choose to rely upon it, albeit at a risk.  The developers may then say, "That improvement is great, let's eliminate the risk by making it mandatory to provide the correct merkle root of the meta tree(s) rather than optional, as a condition of a block to be accepted by the network."

That only works if the phone book is complete - what if you are not sent the most up to date altchain/log-block? What if I send you false ones?

A false meta tree would be outed by its root not matching what's in the block headers of the main chain.
hero member
Activity: 815
Merit: 1000
If the idea of having a meta tree gained a following, then I'd almost like to throw out the following on top of it:  have two meta trees.
My solution already has this in it in by looking at branches.

Each node would be able to choose the depth of the merkle tree at which it wanted to verify.

All nodes could choose different points.
Pages:
Jump to: