2

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?

Improve this question

1 Answer 1

Reset to default
5

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.

Improve this answer
3
  • 2
    Specifically I believe that Luke's comment was about the problem that a miner can withhold all data from the network that would allow proving invalidity.
    – Pieter Wuille
    Commented Jan 11, 2019 at 14:20
  • I still don't understand how "proof of spending a non-existing input" could work. Should the entries of UTXO commitment be sorted? What if the miner simply sneaks a non-existing UTXO entry into it? What purpose does "a tree for outputs created and consumed within one block" serve for?
    – Chris Chen
    Commented Feb 27, 2019 at 10:22
  • One doesn't need a utxo set anything for that. E.g. include with every block a list of where the inputs came from. (e.g. {height, tx number, output}) and the proof the input never existed is simply an SPV proof of the input list and a SPV proof of the indicated input location. If the input existed but was spent it's simply a spv proof of the earlier spend.
    – G. Maxwell
    Commented Feb 27, 2019 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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