Is the idea of fraud proofs possible in reality? I once read this on Twitter, which is said by Luke Dashjr, a Core dev:


  The original design was to have full nodes create proofs of invalid
  blocks, to alert SPV nodes to them. SPV nodes would then verify these
  proofs and reject the invalid blocks. But it turns out, it isn't
  possible to prove a block is invalid.


So I wonder whether the idea of fraud proofs is actually possible? If not, why?
The whitepaper said that SPV clients would avoid accepting a rules violating block by being altered to the violation, downloading the block, and checking for themselves. This is not realistically possible in the protocol as it exists today because the commitment structure means that for many rules the smallest amount of data you must download to tell if a block is actually invalid is the entire chain-- even if you have a peer that knows where the invalidity is. For example: if a transaction spends a vin txid that never existed in the chain currently the smallest amount of data you need to verify a claim that it didn't exist is the whole chain.

Back in 2012/2013 I proposed an additional set of commitments that would make what the whitepaper described possible by allowing the alerting peer to point you to the invalidity (thus calling it "fraud proofs"). For the above invalid-vin example fraud is proven by having every block commit to where in the chain their inputs came from and simply showing those commitments to the querying lite client. Unfortunately, even that isn't that sufficient: a miner producing an invalid block could decide to only serve SPV requests and keep the invalid part hidden from every full node that could alert others to the invalidity.

In 2014/2015 I proposed that clients sample from a locally decodable error correcting code to make it difficult for a malicious block to serve parts of the block without indirectly serving the entire block.  Unfortunately, the result has high overhead to only achieve a relatively low level of security against falsely accepting an invalid block and as a result no one in the Bitcoin space currently seems all that interested in exploring that sub-idea further at this time.