<p>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.</p>

<p>Back in 2012/2013 <a href="https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs" rel="noreferrer">I proposed</a> 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.</p>

<p>In 2014/2015 <a href="https://download.wpsoftware.net/bitcoin/wizards/2015-04-18.html" rel="noreferrer">I proposed</a> 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.</p>

CC BY-SA 4.0
2019-01-11T14:20:09.977Z
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
CC BY-SA 4.0
2019-02-27T10:22:07.237Z
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
CC BY-SA 4.0
2019-02-27T17:52:35.800Z
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
CC BY-SA 4.0
2019-01-07T17:43:10.470Z
2019-01-07T17:43:10.470Z
G. Maxwell
<p>I once read <a href="https://twitter.com/lukedashjr/status/1003441699329331200" rel="nofollow noreferrer">this</a> on Twitter, which is said by Luke Dashjr, a Core dev:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>So I wonder whether the idea of fraud proofs is actually possible? If not, why?</p>

<full-node><spv><fraudproofs>
Is the idea of fraud proofs possible in reality?
Chris Chen
# Is the idea of fraud proofs possible in reality?

(Asked by: username_0 on 2019-01-06)

I once read [this](https://twitter.com/lukedashjr/status/1003441699329331200) 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?

**Tags:** full-node, spv, fraudproofs


---

## 1 answers

### Answer by username_1 on 2019-01-07. Score: 5 | Accepted answer

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](https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs) 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](https://download.wpsoftware.net/bitcoin/wizards/2015-04-18.html) 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.

> **Comments:**
> **username_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.  
> **username_0**: 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?  
> **username_1**: 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.  

---

