How can an external party be sure that node's response is valid?

Question

Assume that 51% of nodes are honest and 49% malicious. Fur sure, longest chain would make the chains consistent/same all over the world as 51% can outweigh the 49%, but my question is slightly different.

If I am an external party(just a normal user) and ask whether the specific tx is in the specific block, how can I be sure that this request didn't reach the malicious node ? The solution is for me to get merkle root from a block header, then a node must return to me the proof and then I verify, but, but, but...

my confusion is that I also have to ask for merkle root to the node and how can I be sure that the "asking merkle root" request goes to honest node ? what if it ends up going to the malicious node - since 49% is malicious, it's likely that my request could end up to this malicious node geographically and it could return such a merkle root that the next request of me making for proof also returns appropriate proof to this malicious merkle root. I hope I made sense.

Answer 1

A Merkle inclusion proof is a proof that a transaction is included in a block with a particular hash, nothing more. Whoever gave you that proof can lie by omission (claiming no transactions you asked for exist in the given block), but if a proof is given, it can be validated.

As I believe you realize, the proof only covers the inclusion of a transaction in a given block. It doesn't prove anything about that block itself. You must independently acquire information about that block and ascertain it is part of the currently best active chain. If you just ask some node what their best chain is, they can claim whatever, and you're trusting that node entirely. That is however not how you're supposed to use such inclusion proofs (unless you have reason to trust them, e.g. because it's your own node, or because it's run by a known entity that you're willing to rely on).

Instead, you (the verifier) would generally run a lightweight network node, which does some part of the network validation. It would connect to multiple other nodes, download the block headers from those nodes, and validate them (just their syntactic correctness and proof-of-work). Among the headers chains you received, you'd pick the most-work valid one, and then verify the Merkle proof against that.

There are still ways in which you can be cheated, but it's not as simple as a single node lying to you:

• Since you are only validating the headers, it is possible that the highest-work headers chain is not actually a valid blockchain (e.g., it could contain unauthorized inflation, theft, or double-spending). Doing so would not convince full nodes, but it can convince lightweight nodes. The theory is that attackers will not try this because it is expensive, hard (needs a majority of the hashrate to keep up), and hopefully a sufficiently important part of the ecosystem would not accept their blocks, thus making the cost of mining wasted. However, this assumption does rely on the presence of enough fully-validating nodes in the network to make the attack uneconomical. If you are concerned about this, your own option is running your own fully-validating node instead of a lightweight one.
• If all peers you talk to are attackers (or colluding with an attacker), something referred to as an Eclipse attack, and are thus shielded off from the real best chain, attackers can get away with constructing an alternate minority-hashrate chain, and hiding the real best chain from you. Depending on how long they can keep the Eclipse attack, this may still be extremely expensive.

Note that "majority of nodes" is never relevant in this analysis. The criteria are whether you have at least one honest peer, and whether a majority of the hashrate is working with the attacker.

Answer 2

I interpret your question as "why can I trust a Merkle proof?"

1. A cryptographic hash function processes an input and always returns the same output. If you change the input in the slightest, you will get back a completely different result. It is considered computationally infeasible to find other inputs such that they produce a matching output to other inputs. The range of outputs is so humongous that merely knowing a specific output is proof that we knew about the corresponding input.
2. A block id is produced by hashing the header of a block. The header includes the previous block’s id and the Merkle root. The block hash must fulfill the current difficulty, which means that it must be an extremely unlikely low hash. Because it is so much work to find a valid block, it is hard to produce a block header that commits to other data but has a valid proof-of-work.
3. Miners decides which transactions they try to include in their block before attempting to find a valid block header. From the list of transaction ids, they build a Merkle tree. The Merkle tree starts from the transaction ids as the leaves and hashes them together pairwise at each level. Finally we get a Merkle root that compactly commits to the inclusion of all transactions.
4. Putting it all together, we have a block header that is covered by a proof-of-work that is expensive to fake, which commits to a Merkle root. We have a Merkle root that commits to all transactions, and vice versa, by showing that we know the hashing partners that form a series of hashes that connect a transaction id to the Merkle root, and the chain of block headers that connect the block to the Genesis block, we can provide a credible proof that a transaction is present in a block.
5. Malicious nodes can lie by omission: "No, I’ve never seen that transaction." But for honest nodes making a proof is cheap, and when you do get a proof, it is trivial to check whether it is valid and connected to what you think is the best blockchain. If a malicious node tried to lie to you, they would have to perform very expensive proof of work to stand a chance.