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

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?

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.

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.

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.

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.

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.

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.

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.

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. 

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.

What if you have the same wallet on two systems?

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.

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? 

Electrum and Stratum don't use SPV. Those clients don't keep block headers (AFAIK). BitcoinJ uses SPV.


I wait until it has 6 confirmations. SPV allows me to determine the number of confirmations accurately (assuming the majority of mining power is honest).

Yes, but how do you know a particular TxOut hasn't been spent since it appeared in the blockchain?  I can verify, by downloading full transactions, that a particular TxOut was valid at one point in time, but I have no way to determine if it's been spent since that time.  Whether I'm verifying my own balance, or trying to confirm the validity of the inputs of another transaction, any malicious node can give me seemingly correct information, but still make my node incapable of operating -- perhaps because when I got online the first time an imported my wallet, I was given only old TxOuts that have since been spent, and my node will be stuck creating invalid transactions trying to spend them.

This is the basis of the overlay network that Electrum/Stratum uses.  I don't think there's anything wrong with that overlay network, other than it relies on trusted nodes being setup and available, or subscribing to a service, all of which is a degree of centralization (and extra user effort).  This chain avoids all of it, providing (at the expense of complexity), more reliable information without trusting anyone.  

If that was the only benefit, I'd agree it wouldn't be worth the hassle.  But as I said, that's a secondary benefit of this structure.  The main reason to do it is compression.

Which could be implemented with a simpler tree structure using an alt/meta-chain.  Or this tree-structure using a different distribution technique (protocol change, overlay network, trusting random peers, etc).

Notice that if the lightweight Client runs the Merkle tree scheme I described, it can rejected double-spends, invalid scripts, etc. Even without needing to store a copy of the unspent outputs.

Instead, the Client receives each block header, as well as O(M log N) of verification data (paths through the Merkle tree). This way, the Client can check each transaction against the database, as indicated by the current root hash. Only a full node acting as an untrusted helper needs to store the entire unspent outputs database, in order to generate the verification data.

If I have a copy of all unspent outputs, the majority of mining power can only change the ordering of transactions (and this ability might be more limited in the future). But a lightweight node will accept double-spends within the block chain, too-high block subsidies, invalid scripts, etc. if the attacker has enough mining power.


You don't have to trust random peers with SPV. SPV clients have the block headers and can use the Merkle roots to accurately get the number of confirmations for any transaction.

This doesn't make sense at all.  The entirety of all Bitcoin trust relies on trusting "the majority of the network's mining power."  That is the security model of Bitcoin itself, and has the benefit that you only need one honest node out of one million to be able to distinguish truth amongst a sea of malicious peers.

The issue with SPV is that you have to trust either random peers to give you the correct/complete info, or connect to your own trusted system/subscription to get reliable information.  Without a subscription service, you have to query lots of peers and possibly use filtering/profiling games with peers to identify untrusted nodes, etc.   With this idea, you minimize the amount of information needed to be downloaded, and can compare directly against the headers -- you can get all the information you need from a single peer and know it's right (assuming you've already got the headers).

And that is actually just a side-benefit of it -- the original goal was blockchain compression, which this does near-optimally.

I agree that complexity is high.  But I disagree with the notion that you're not getting something for it.

It doesn't seem trustless to me. Lightweight nodes (not storing all unspent outputs) can't know whether a block is valid, so they need to trust the majority of the network's mining power. This is no more secure than SPV, though possibly a little easier for lightweight nodes.

There is an advantage to "mostly-full" nodes who store all unspent transactions: they don't have to download all past blocks to start validating. But a regular Merkle tree of unspent outputs works just as well.

Using an alt chain instead of putting the Merkle root in a main-chain transaction seems unnecessarily complex.

Thanks, that makes sense.

That's much better terminology. Thank you.