Question about Merkle tree

[Borph]

Hi, sorry for the newbie question, but I would like to understand the Merkle tree.

When it comes to scalability of Bitcoin, it is often said that thin clients don't have to load the full blockchain with all transactions of the world. The blockheader with the merkle root is enough. Given a transaction, you would not need the full tree, but only the path to the root to decide, if that tx was included in the block.

1. But how do I know the other hashes, so the sibling nodes of the tree? I can hash my believed-to-be-good transaction, but I hash that again together with the sibling hash to get the next 'level' of the tree, until I reach the root. For this, I would need all transactions again, in order to be able to calculate all needed hashes!

2. When there is something in the protocol to ask another node for the merkle hashes (so I don't need to download all, but something), how does this go with the "trust nobody" principle? Someone gives me a hash, I will include it in my calculation, and if I get the correct merkle root, I believe the TX to be good? Isn't it like a big NONCE, someone could give me a false hash to make me believe? Maybe it's just impractical, because you would have to try a lot, but in theory? The other node doesn't give me the full data, just the sibling hash, so I could never prove it!

Did I miss something in understanding? Advice appreciated :-)
Peter

[DeathAndTaxes]

You know the merkle root is valid so you only need to download a portion of the tree.

Please excuse my ASCII art.

Code:

           * merkle root
          / \
         /   \
        /     \
       /       \
      /         \ 
     *           *
    / \         / \
   /   \       /   \
  *     *     X     X
 / \   / \   / \   / \
*   * X   X X   X X   X
    |
   transaction to verify

* = hashes needed
x = hashes not needed.

You only need roughly half the hashes, the merkle root hash, and the transaction details on one of the transactions.  The light client doesn't care about the actual details of the other transactions or hashes more than 1 branch away from it's "path". Given hashes are smaller than the transaction this can be a significant reduction in bandwidth and storage, you also only need to verify hash the hashes which reduces computational load.

[Borph]

Thanks for the nice ascii art

So it's like I mentioned in (2.), I actually have to download the other hashes (marked with *). But I cannot verify them, I have to trust they are correct hashed from the underlying transactions? Or is it impossible to generate a false hash, as it would never result in the correct Merkle tree root??

I'm thinking of this "trust nobody" principle, but here I would download these intermediate hashes from somebody else I don't trust.

[DeathAndTaxes]

So it's like I mentioned in (2.), I actually have to download the other hashes (marked with *). But I cannot verify them, I have to trust they are correct hashed from the underlying transactions? Or is it impossible to generate a false hash, as it would never result in the correct Merkle tree root??

You can verify them and you are right in the second part.  The way hashes work is it is "easy" in terms of computational power to verify a hash but computationally infeasible to produce a "fake hash".  The odds that an attacker could find a hash which when hashes will produce the correct value "up tree" on the merkle tree is highly improbable.  The hash space is 2^256.  With current global computing power it is simply not economical for an attacker to attempt "fake a hash".  

To have a 1 in 1 trillion chance of finding a single hash collision in SHA-256 would require all the computers in the world working 24/7/365 for next 40 quadrilion years.  So it is impossible in cryptography to say "impossible" but we can say it is highly improable and infeasible unless the hash is cryptgraphically flawed (broken).

I'm thinking of this "trust nobody" principle, but here I would download these intermediate hashes from somebody else I don't trust.

"Trust in numbers".  You don't have to trust the person sending you the data. Hell you (and the client) should assume there is a chance he is an attacker.  You trust that it is computationally infeasible for an attacker to substitute a transaction or hash that would "fit" the merkle tree.  The client is designed to find remote peers and get data from various locations.   This is done to prvent an attacker from controling the flow of information (hiding transactions). If sufficiently paranoid you could even write a client which won't act upon data until it receive it from multiple remote peers.

[Maged]

Thanks for the nice ascii art

So it's like I mentioned in (2.), I actually have to download the other hashes (marked with *). But I cannot verify them, I have to trust they are correct hashed from the underlying transactions? Or is it impossible to generate a false hash, as it would never result in the correct Merkle tree root??

I'm thinking of this "trust nobody" principle, but here I would download these intermediate hashes from somebody else I don't trust.

It's not impossible, but it's extreme difficult to fake. It's much like how we just have to "trust" that no two people generate the same private key, or find a private key whose public key maps to the same address as someone else. That's how hashes and cryptography work.

The best that someone can do is withhold true information. They can never lie.

[Borph]

Thanks for the explanation DeathAndTaxes and Maged! So I got it: you just get a hash from somebody, but it's so unlikely get a correct merkle root at the end, that you can compare it to a private key. Does the Bitcoin network actually already has these messages implemented in order to make thin clients possible?

[..] getting struck by lightning twice

I was actually struck by a lightning once! Does this mean I don't have to worry to get struck a second time because of probabilities? ;-)  (I know, chances are same..)

[btc_artist]

(I know, chances are same..)

Unless being struck by lightning changed your behavior (i.e, never going outside during a storm, etc) then it might reduce the probability of you getting struck again.  /trollface :p

[theymos]

Interesting fact: Your wallet contains the Merkle branches for all of your transactions, so it's possible to import a wallet with only block headers.

Does the Bitcoin network actually already has these messages implemented in order to make thin clients possible?

There's a network message to get headers, but not a message to get Merkle trees. Why no message to get trees? Because without downloading full blocks there's not yet any way to detect that you've even received a transaction, so you'll have no need for trees.

Detecting that you've received a transaction without downloading full blocks is complex. It might require a new dedicated network protocol.

[Borph]

Detecting that you've received a transaction without downloading full blocks is complex. It might require a new dedicated network protocol.

Hum, couldn't you ask the peer node about transactions with receiving address XY? The "full" nodes act as a database provider then? The trust comes with the knowledge that it is buried deep in the blockchain, so others would have refused it when it would contain an invalid signature or so. The problem I can see here is that you have hundreds of addresses in your wallet. That's causing also a privacy issue btw: imagine a protocol would be like "here I give you a list of hundred addresses, please return all matching transactions", this means the peer node would know that they all belong to the same person.

[theymos]

That's one way to do it. That puts a lot of pressure on full nodes, though. All clients will need a full node to give them accurate responses to their requests. There may not be enough full nodes willing to do it.

A better way to do it would be to have a new network on top of the Bitcoin network that distributes parts of the block data without requiring too much effort from full nodes. There are many fancy network architectures and peer trust metrics that could be used here.

Another way would be to require that senders give the transaction hash (plus the Merkle branch, if they have it) to recipients directly using a direct IP connection, email, or some other method. Then clients only need to get Merkle trees and headers, which can both be easily spread in a distributed way.

[deepceleron]

Thanks for the explanation DeathAndTaxes and Maged! So I got it: you just get a hash from somebody, but it's so unlikely get a correct merkle root at the end, that you can compare it to a private key. Does the Bitcoin network actually already has these messages implemented in order to make thin clients possible?

[..] getting struck by lightning twice

I was actually struck by a lightning once! Does this mean I don't have to worry to get struck a second time because of probabilities? ;-)  (I know, chances are same..)

Yes, you have a higher probability if you were struck once, you likely live in an area with thunderstorms, and don't have the sense to seek shelter when they come. Like a shark attack, entirely preventable.

[Borph]

That's one way to do it. That puts a lot of pressure on full nodes, though. All clients will need a full node to give them accurate responses to their requests. There may not be enough full nodes willing to do it.

I would not say it's impossible. Similar to today, where a mobile phone thin client is just a front-end for i.e. Instawallet, I could imagine that in future thin clients need another node to work.

I could imagine three types of nodes:

• Full-nodes: The current official client. They have the _whole_ database of all transactions ever done. As this scales badly, maybe just some banks or universities could run one as a service of an "eternal" database.
• Stripped-node: Acts still as a node and checks validity of transactions, blocks and so on, but transactions which are fully redeemed (=cannot be spend anymore) are removed. DB contains only transactions which are needed to verify another incoming transaction.
• Thin-client: Cannot answer request about a transaction except the ones contained in its cache. Needs at least a stripped node to query 'incoming' transactions. Is still a kind-of node as it has a wallet and signs outgoing transactions.

The network protocol could incorporate this, like "give me stripped-nodes from the IRC-channel". There would be 'layers' within the existing protocol then.

[ThomasV]

Detecting that you've received a transaction without downloading full blocks is complex. It might require a new dedicated network protocol.

Hum, couldn't you ask the peer node about transactions with receiving address XY? The "full" nodes act as a database provider then? The trust comes with the knowledge that it is buried deep in the blockchain, so others would have refused it when it would contain an invalid signature or so. The problem I can see here is that you have hundreds of addresses in your wallet. That's causing also a privacy issue btw: imagine a protocol would be like "here I give you a list of hundred addresses, please return all matching transactions", this means the peer node would know that they all belong to the same person.

Electrum does exactly this. see http://ecdsa.org/electrum/