Fraud Proofs

priestc

Member
Nov 19, 2015
94
191
I've just read every post in this thread. I think too many people are overthinking the problem. The way I see it, there are basically four types of fraud proofs:

1. Math based "Full weight" fraud proofs
2. Math based compact fraud proofs
3. Trust based compact fraud proofs
4. Community based compact fraud proofs

#1 and #3 and #4 are possible today. It is my opinion that #2 is impossible now and will be forever impossible. Everyone in this threads seems to be trying to come up with a #2 type of fraud alert.

Imagine if someone wanted you to prove that Bob is not in Chicago. The only way to perform this "proof" is to travel to Chicago, and then go through every building, evert coffee shop, every public park, etc. until you've checked everywhere. Only then can you determine that you've proven that Bob is not in Chicago.

In blockchain terms, this is the "math based full weight fraud proof". You prove that a payment is present in the blockchain by validating the entire blockchain is valid, then walking through the blockchain until you get to the end and don't see it. "Full weight" fraud proofs are what full nodes use to validate all payments.

"Math based compact fraud proofs" are when you don't have the entire blockchain to look through. This is like trying to prove that Bob is not in Chicago when it is impossible to travel to certain parts of the city. If there are parts of Chicago that you can't look, then you can't prove that you didn't find him.

Imagine a mathematician writing a 10 page proof that solves a research level math problem. He sends one page of his proof to each of 10 mathematicians. No one mathematician has the entire proof, but each one has 1/10 of the proof. There is no way than any of the 10 mathematicians will be able to determine if the entire proof is valid or not. Even if the all the mathematicians send merkel roots of their page to each other. You have to have then entire math to determine that the math is complete. This is why I also think "sharding" will never see the light of day.

"Community based" and "trust based" compact fraud proofs are possible today and will probably be the best we'll ever get to a real practical "compact fraud proof". If you can't travel to all parts of Chicago, the next best thing is to ask the police department if they've seen Bob (the police have access to every part of Chicago). The downside to doing this is that you have to trust the police.

But what if there were multiple competing police departments? Lets say there were 5 police departments, all with patrol officers that have access to 100% of the city. If you asked each police department and they all tell you they have not seen Bob, this is the best you're going to get without going door to door yourself. The level of trust required is that there is no grand police conspiracy. What are the odds that the entire police community is lying to you? The assumption is that a single person in the community may lie to you, but the entire community will not lie to you.

In blockchain terms, this is calling multiple blockexplorer APIs. One random blockchain API may give you false data, but not every single one will lie to you. There will always be a majority of services that agree with each other that makes up the authoritative blockchain.
 

priestc

Member
Nov 19, 2015
94
191
If someone says they have an idea for build a perpetual motion machine, you'd want to see the machine actually built to believe it really solves the "perpetual motion problem". If the person who wrote that document really has a solution to the "compact fraud proof" problem, then they need to prove it by writing an implementation in actual code. English words describing the concept is not enough. Such a problem needs to be solved with code, and you can't compile english words into working software.
 
  • Like
Reactions: janko33

Mengerian

Moderator
Staff member
Aug 29, 2015
536
2,597
Luke Jr. is working on a block size fraud proof: https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki

Seems kind of silly to me, should light clients really care about enforcing a block size limit?

This is the stated motivation:
Recently, there have been proposals for hardforks to increase the block size limit. While no consensus has been reached, proponents of these ideas often threaten and attempt to have miners force them through anyway. As things presently are, light clients cannot detect invalid blocks at all, and could be fooled into accepting an invalid chain created in such a manner. By supporting block size fraud proofs, light clients can protect their users from this form of unconsensual "hardfork" attempt.
In other words, it's an attempt to combat efforts to increase block size, and further entrench the block size limit.

It seems far more important (and in the interests of light client users) to develop a proof for non-existent transaction inputs.
 

Justus Ranvier

Active Member
Aug 28, 2015
875
3,746
Spending non-existent inputs is counterfeiting.
Spending inputs that have previously been spent is counterfeiting.
Issuing more new coins than allowed by the issuance schedule is counterfeiting.
Spending inputs without satisfying the conditions of their script is theft.

Counterfeiting and theft are included in every definition of fraud of which I am aware.

The Luke-Jr position seems to be that:

1. C++ code is agnostic with regards to the financial/economic meaning of the rules it enforces.
2. Therefore all rules expressed in code are equivalent.
3. Therefore any non-conformance with the C++ code of my preferred repository is fraud.