Searching for an item in a blockchain

Question

A blockchain is a chain that includes a hash to the previous block. Each block is composed of a single hash tree (or a Merkle Tree). What I am discussing is the overall structure of the blockchain.

Since values of a blockchain are inside of a hash tree, what is the best way to look for a value inside of a block chain? I imagine it would be unfeasible to traverse the entire block chain to search the tree for the value you wish to find. Is there a search method I am missing for searching for a value inside of a block in a blockchain?

Answer 1

If all you have is a blockchain with Merkle-trees in each block, then this data structure by definition does not provide any means for searching anything efficiently:

• All the hashes in the leafs of the Merkle tree are essentially pseudo-random, and contain no usable information about the content
• All the hashes in the nodes of the merkle tree are pseudo-random bit sequences formed by hashing of concatenations of pseudo-random bit sequences (cryptographically strong pseudo-random-nonsense squared, log N times)
• The hash pointing to the previous block is good for nothing except finding that previous block (pseudo-random-nonsense to the power of M, where M is the number of blocks)
• Ditto for the hash of the block itself

In conclusion: no, the hashes of the blocks and the Merkle-trees are essentially useless for searching information. It's not only "inefficient", it's by design the most useless "indexing" of the data contained in the blockchain (because the hashes change completely as soon as a single bit in the data flips). If you want to find anything in such a data structure, there is absolutely nothing you can do except traversing it in linear time. All those hashes do is ensuring that the blockchain is not tampered with, and nothing else.

However, nobody forces you to traverse the entire blockchain every time you want to find some information in it. Instead, you can

• Traverse the entire blockchain once
• Build whatever additional data structures you need for finding what you need in the blockchain (indexes, search trees, graphs, fingerprints, whatever you can build from the data in the blockchain)

and then on every request you simply

• use the pre-computed data structures to execute your query efficiently

and every time a new block is appended

• update all the precomputed data structures.

Alternatively: rebuild your data structures occasionally, treat the last few blocks separately.

It's very much the same with "the internet". It's a network of nodes with content in them. How do you find anything in those nodes? Do you traverse all the nodes every time you want to find anything? No, you ask a search engine. Because the search engine has already done the job in the background, and visited (some) of the nodes in the network, and indexed the content, so that you can find stuff in it easily. Same thing here, except that your graph is linear (if you forget the orphan branches), and that the nodes previously added to the graph don't change too often (never, unless someone disproportionally powerful attacks your blockchain). The immutability of the previously added nodes should certainly be used for efficiency when you update your data structures: if you already have seen those nodes, there is no need to re-scan them every time (unlike in the internet, where content of the previously indexed nodes nodes can change).

Another (obvious) alternative, if you can influence the design of the blockchain: think about what might be useful ahead of time, bake the required data structures into the blockchain right from the start, so that not only the blockchain itself, but also the data structures that help navigate the blockchain cannot be modified easily.