1

Let me express what I have got to know about blockchain and where am I stuck.

Transactions are stored in the form of merkel trees inside a block. (I know how a merkel tree is made). A merkel root is calculated and stored in the block header. An SPV can ask a full node about the balance of an address (which is an encryption of public key).

Now a full node is supposed to give merkel root hash of all the blocks which contain the transactions( which contains the UTXOs which can be spent by the private key holder by unlocking its output script using its digital signature).

I want to know how does the full node get to know which blocks exactly contains those UTXOs? Does it the traverse merkel tree of each block till genesis block? or is there any way to know if the block contains those transaction or not just by utilising its merkel root.

2

Transactions are stored in the form of merkel trees inside a block. (I know how a merkel tree is made). A merkel root is calculated and stored in the block header. 

All correct.

An SPV can ask a full node about the balance of an address

No, it can only ask for a proof that a particular transaction was included in the blockchain. The Merkle tree has transactions as leaves, not addresses

At the protocol level there are no balances, only UTXOs. UTXOs (or "coins") are things with a value and an address, and every transaction simply "reforges" coins. It explicitly lists certain input coins which are melted down fully (destroying those coins in the process), and then constructs new coins whose value does not exceed the value of the consumed coins. Nowhere in this system does a balance appear.

(which is an encryption of public key).

A hash, not an encryption. There is no encryption anywhere in Bitcoin (except locally to password protocol your wallet file).

I want to know how does the full node get to know which blocks exactly contains those UTXOs?

This is unrelated. Blocks contain Merkle roots of transactions. They don't contain UTXOs.

One way to look at it is that there is an implicitly-defined set of UTXOs for each block. This set is empty for the genesis block. Every transaction processed deletes the UTXOs it consumes from that set, and adds new UTXOs to it for each output it has. As blocks are groups of transactions, they too are just aggregations of groups of UTXOs being deleted from and added to the UTXO set.

In fact, that is how full nodes work. They just maintain a database with all unspent outputs. Every block is just an authenticated "patch" of changes to make to the UTXO set.

Does it the traverse merkel tree of each block till genesis block? or is there any way to know if the block contains those transaction or not just by utilising its merkel root.

I assume you're talking about BIP37 Bloom Filters? There is no searching involved at all. A light client tells a full node "hey I am interested in transactions to address X". Then it asks for a range of blocks. The full node reads through those blocks, and if a matching transaction is found, sends it to the light client along with a Merkle branch that proves the transaction was indeed in that block.

This approach has various downsides. First of all, it is inefficient, as it requires the full node involved to read and scan through all transactions in all blocks. Secondly, it is terrible for privacy. Even while the set of addresses the light client is interested in is hidden inside a Bloom filter, it is very hard to not make it leak what transactions a node cares about.

BIP157/BIP158 specify a more efficient and more private protocol called Neutrino to accomplish the same.

  • Thank you so much Pieter for giving such an elaborate answer. Could you please clarify didn't you mean searching by this quoted statement? "The full node reads through those blocks, and if a matching transaction is found, sends it to the light client " – Learner Jan 29 '18 at 19:46
  • I guess I wouldn't call that searching as there is nothing smart about it... no indexes, no fancy data structures... just read from front to back and send back what matches. – Pieter Wuille Jan 29 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.