Ultimate blockchain compression w/ trust-free lite nodes

[theymos]

I'm not concerned about enough confirmations.  I'm actually concerned that it has 10,000 confirmations, and that it was actually spent 3,000 blocks ago, and that I have to search through 10,000 full blocks in order to know whether it's still a valid output.  Or, I can ask other nodes for help, but I how do I know to trust them? 

SPV nodes keep copies of all of their own transactions, so they should always know when outputs they own are spent. They don't need to query the network for this information.

[maaku]

SPV nodes keep copies of all of their own transactions, so they should always know when outputs they own are spent. They don't need to query the network for this information.

What if you have the same wallet on two systems?

[galambo]

No clue about any of this stuff, but thank you guys for working on this.  I think it's important to have this sorted out before adoption and use gets really heavy.

I think its important that everybody understand this and I didn't see anyone explaining it in general terms.

The Blockchain is a distributed computer file system containing a double entry accounting ledger. Each transaction has two sides which you may be familiar with from accounting: input and output OR debits and credits. However, a major difference is that bitcoin forces a debit(input) to exist for every credit(output).  Storing all of this takes a lot of space. extra explaination

This proposal will continously "balance the books." In accounting, when you close out the books for the quarter all of the debits and credits are summed, and the difference between the two is entered as a "balance" transaction. Because we know that bitcoin forces every credit(output) to have a debit(input), we only have to keep track of all credits(outputs) that are not claimed by a debit(input) to obtain the balance of each address.

The proposal is for a system to store the references to these unspent outputs in a data structure for quick downloading. It doesn't suggest how this tree would be updated efficiently, or how you would quickly grab all of the unspent outputs belonging to one address. This is under discussion.

[etotheipi]

I'm not concerned about enough confirmations.  I'm actually concerned that it has 10,000 confirmations, and that it was actually spent 3,000 blocks ago, and that I have to search through 10,000 full blocks in order to know whether it's still a valid output.  Or, I can ask other nodes for help, but I how do I know to trust them? 

SPV nodes keep copies of all of their own transactions, so they should always know when outputs they own are spent. They don't need to query the network for this information.

Sure they don't.  Until they do.  Maybe they haven't been online in a couple weeks and 2 GB of blockchain has happened since then.  Or maybe they want to check another address that they never owned to begin with.  Or maybe you just imported your wallet to another device (as Maaku said), or you're HDD failed and you are restoring from backup?   Are you now expected to become a nearly-full node to rescan the entire transaction history since your wallet was created 2 years ago? 

You can ask peers for it, and do fancy stuff to convince yourself the history you have been given is real and complete.  Or you avoid all of it and just get it from any peer you see on the network and not have to trust anyone other than majority hashing power.  Download it, verify it and you're done. 

[casascius]

OK, so I read that one of the problems making this tree work would be having to deal with recomputing it after each transaction.

What if the meta tree were not kept in a chain?  What if it were just a living thing that could be maintained by peers, and the only thing that would be kept in the chain is the merkle root of the meta tree put into the coinbase transaction?  A peer could request the whole tree from any peer who had it (assuming the peer "offered" the tree).

Further, to lower the overhead associated with updating the tree, let's say that a complete tree rebalance happens every 100 blocks or so.  Until then (i.e. unless blockheight % 100 == 0), leaf nodes would be removed from the tree by replacing them with a placeholder leaf node that would sort into the same place.  This way, one node can prove to another that no real records exist for that address by serving the placeholder node.

For security's sake, each peer offering the meta tree also ought to offer several versions (at least 2) of the meta tree as it looked when it was recreated at a 100-block checkpoint (more on that later).

So to illustrate this with an example...

I am a bitcoin client that comes to the network.  (This hypothetical network has evolved to the point where including the correct merkle root of the current meta tree in the coinbase is mandatory.)

First, I get all of the 80-byte headers going back to the genesis block and persuade myself that I have them all when I do.

Then, if I am interested in my own copy of the whole meta tree (for the good of the network), I ask a peer for it.  The peer sends it to me in its entirety.  I validate it against the merkle root I believe to be valid.

Instead of requesting the up-to-the-minute meta tree, I could request the meta tree 2 checkpoints ago (between 100-200 blocks ago) along with the corresponding full blocks with all the transactions, and play those transactions back.  This will help me be sure that I'm not looking at an orphan fork that completely replaced the meta tree with something else.

If I am NOT interested in my own copy of the whole meta tree, I give a peer a Bitcoin address and ask it to give me the leaf nodes surrounding that address in the sort order, along with the tree lineage to prove it's part of the tree.

[tevirk]

I don't see that even the complete tree of outstanding balances needs to be validated anyway.

To validate a transaction, I need answers to these questions:

• What block (number and hash) is the latest?
• In which block (number and hash) ancestral to block aaaaa is transaction xxxxx?
• Is output n of transaction xxxxx spent in any block betweeen number bbbbb (with hash ppppp) and number ccccc (with hash qqqqq)?

A service can give signed answers to all those questions.  If it ever gives a wrong answer, it can checked and proved to be wrong by anyone with the complete blockchain.   It wouldn't be hard for a client to do random spot-checks on a service at a low rate -- again, if it ever gets a signed wrong answer it has proof for all to see that the service it used was unreliable.

Running a service like that is easy: all you need is enough cpu to keep up with the blockchain, which is trivial, and enough disk to store the blockchain and indexes -- currently about 5GB, say 1TB looking forward a few years.  Again, that is trivial.  The services could be run by ISPs, exchanges, online stores, enthusiasts, and could easily be ad-supported.  It could easily be made into an appliance that would cost only about USD200 at current prices, meaning any retailer using bitcoin regularly could have one of their own.  The client could check with a few different services: again, any wrong answer can be proved to be wrong by anyone with the blockchain.

That surely is the way forward in the long term.

[casascius]

I don't see that even the complete tree of outstanding balances needs to be validated anyway.
...

If it ever gives a wrong answer, it can checked and proved to be wrong by anyone with the complete blockchain.  

...

That surely is the way forward in the long term.

This thread is about a proposal to one-up that: to create a service whose wrong answers can be proven wrong instantly, automatically, and cryptographically without anything more than a single merkle root you are certain represents the latest state of the chain.  That's better than trusting a service where the only recourse is that you could rat them out if you manage to catch them lying, which you'll never be in a position to do unless you're also in a position to not need their services.

[Realpra]

Once you cut down on the section of the blockchain you need to download while still verifying, you have essentially a swarm node.

I suggested something very similar in my thread about pruning not being enough.

However if you create a tx log instead of a merkle tree then you break compatibility, since the "root hash/log signature" will be different.


My proposal used heavily pruned merkle tree sections to send individual transactions without trust and had no forking.

You would check a new address really had funds by asking the network for the branches concerning just that address.

Even if the majority of nodes withheld information you would only need one honest node to get the complete picture in a short download.

[casascius]

My proposal used heavily pruned merkle tree sections to send individual transactions without trust and had no forking.

You would check a new address really had funds by asking the network for the branches concerning just that address.

Even if the majority of nodes withheld information you would only need one honest node to get the complete picture in a short download.

How would that compare to maintaining a merkle tree with an enforced sort order: sorted by address?  Then the odds of accepting an answer from a lying node would be zero.  No need to seek a consensus.

If there were an enforced sort order, a response to a query could reliably prove he returned the entire set of records matching the query (or prove none existed), simply by providing a contiguous chunk of leaf nodes that completely contains the query, along with everything up to the merkle root.  Sort of how I could prove "Gordon Dinklebutt" is or isn't in the phone book by providing copies of contiguously numbered pages that include both "Dickson" (which is less than Dinklebutt) and "Dipweed" (which is greater), as well as everything in between.

[casascius]

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.

A first class meta tree and a second class meta tree.  The purpose of having two meta trees would be so that someone operating a P2P node can choose to offer resources to the network without having to offer unlimited resources to the network, and to have those resources give maximum benefit to the network.  Think: a user who would rather contribute to supporting real transactions instead of spam and bitdust.

The first class meta tree would be constrained in size, and would contain the most important txouts to the network.  "Important" being determined by value as well as age.  The goal would be that everything will end up in the first class tree except for bitdust.

The second class meta tree would contain everything, including the bitdust.

Users would be able to choose the level of resource commitment to the P2P network.  In today's terms, hosting the first tree could be a comfortable 100 megabyte commitment, and you would do it for selfish reasons: fast transaction processing and minimum transaction fees (explained later).  If the first tree had a size cap (perhaps that size is algorithmically pre-determined to follow Moore's law), people could give comfortably to the network.  

The second tree - which would contain everything that didn't fit in the first tree - could help force people putting the biggest burden on the network to pay the most.  Miners would have no choice but to host both trees, but miners are also in a position to force a more generous transaction fee for access to those transactions.

Bitdust would become second-class currency, but easily upgraded to first-class by spending and consolidating it, and waiting a bit.  Owners of bitdust would bear two burdens: a greater transaction fee, and a greater confirmation time when spent to someone who chooses to be agnostic of the second tree.

Someone running a client that only concerned itself with the first-class tree would learn about incoming bitdust transactions not immediately, but only after a miner mined the transaction spending the bitdust into a block, and then that block reached a threshold of anywhere between 6 and 100 confirmations to meet the criteria for it to be integrated into the first class tree.  As long as it was spent in a matter that consolidated it into a bigger transaction instead of leaving it in the form of dust, it would remain first class currency likely permanently.

[Realpra]

My proposal used heavily pruned merkle tree sections to send individual transactions without trust and had no forking.

You would check a new address really had funds by asking the network for the branches concerning just that address.

Even if the majority of nodes withheld information you would only need one honest node to get the complete picture in a short download.

How would that compare to maintaining a merkle tree with an enforced sort order: sorted by address?  Then the odds of accepting an answer from a lying node would be zero.  No need to seek a consensus.

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.

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?

If there were an enforced sort order, a response to a query could reliably prove he returned the entire set of records matching the query (or prove none existed), simply by providing a contiguous chunk of leaf nodes that completely contains the query, along with everything up to the merkle root.  Sort of how I could prove "Gordon Dinklebutt" is or isn't in the phone book by providing copies of contiguously numbered pages that include both "Dickson" (which is less than Dinklebutt) and "Dipweed" (which is greater), as well as everything in between.

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?

My solution had further advantages as NO ONE would need the full block - a big advantage as miners can't run lite nodes as it is.

My solution also solved propagation time problems blocks have today - this solution would not as it relies on the normal blockchain.

All of this without forking or merged mining.

[Realpra]

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.

[casascius]

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.

[Maged]

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.

[casascius]

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

[Realpra]

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

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.

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)

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.

[casascius]

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.

[HostFat]

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

[Realpra]

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.

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?

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.

[Realpra]

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.