Proof Systems are the engine behind blockchains
As long as the millions of untrusting bitcoiners are able to prove their bitcoin transactions to each other, the network lives on. Here, in Part I, we lay out the basics of proof systems as the means to convince each other using verifiable pieces of evidence. Think of fossils or a digital signature.
In Part Two, we explore the economics around proof systems.
It is extremely unlikely that anyone reading this document has stood in the presence of a dinosaur. And yet, you probably believe me when I say:
Tall, huge, beautiful dinosaurs grazed this green and blue Earth long ago.
Megalosaurus was the first dinosaur ever described scientifically in 1824 by William Buckland, even though similar fossils were uncovered much earlier (2,000 years ago) in China where they were called ‘dragon bones’. Without the tools to inspect these stones, they do not ‘prove’ anything conclusive, they were just stones with some fanciful stories attached to them, such as the Greeks and Romans concluding from these fossils about their ogre and griffin legends.
We see this pattern everywhere in life: a doubtful claim is made by someone, which on inspection, turns out to be true, convincing one and all. Some other examples:
the story of Darryl Hunt, who was wrongly accused of a murder and gets released eventually as a result of a DNA ‘evidence’;
the claim by the elders of Dogon Tribe years before its discovery by Western astrophysicists of the existence of dwarf planet to Sirius, called Sirius B even though it can not be seen with the naked eyes; and
friends who claim their happy disposition is the result of years of meditation, inspiring me to do the same, and observing the truth of their claim as I slowly become happier over the years.
There is a pattern here:
- I make a claim: Tall, huge, beautiful dinosaurs grazed this green and blue Earth long ago.
- You doubt my claim, and challenge me: Prove it.
- I provide evidence relevant to my claim: Check the DNA samples and fossil records!
- You verify the evidence: Impressive. I believe you. Or, These records are phony.
As a result of successful verification of the evidence, my claim now comes with the guarantee of truth, being that the evidence has established itself as a proof1 by you.
We call this pattern a proof system. It begins with a claim and ends (hopefully) with a conviction. The proof system is the path the parties walk together, in search of the truth2.
Components of a proof system
A proof system is a relationship between two (or more3) parties in which one party, the prover, tries to convince the other, the verifier, of the truth of a given claim. The prover does this by sharing relevant evidence with the verifier. The verifier then verifies the prover’s evidence, and either approves or rejects the prover’s claim based on their findings.
The quality of the prover’s evidence is naturally very important. However, while evidence is necessary to prove a claim, it is not sufficient. The ancient Greeks, Romans, and Chinese were not convinced of the existence of dinosaurs when they found giant bones 2,000 years ago. It is only by using the right tools, a verification system, to verify the available evidence that a verifier can be convinced.
Evidence, by itself, is not enough. Without the right tools to verify an evidence, a proof cannot be established.
Thus, proof systems, in addition to a prover and a verifier, usually involve evidence (presented by the prover to the verifier) and a verification system (used by the verifier) to establish the truth of the prover’s claim.
We use the proof system pattern, implicitly or explicitly, any time doubt needs to be cleared or truth needs to be shared. Proof systems can take on many shapes:
|I am a human being in control of a house/room
|I have access to the given webmail account
|Palaeolithic humans practiced the visual arts
||The Cave Paintings of the Lascaux Cave
|Stars creating a curve in the spacetime resulting in photons being bent around them
||Sir Arthur Eddington
||Positions of background stars close to the sun’s edge (it’s limb)
|I am sending bitcoins to you
||Is the transaction signed by me and not spent in parallel
What Makes Good Evidence in Information Systems?
A basic building block of Proof of Process is this relationship between prover and verifier in digital relationships and information systems (read: The Internet). As an example of the proof system pattern in a digital context, we turn toward an earlier entry from our blog: “Satya wants to join the famous Bering Sea Billionaire’s Club and needs to convince Chloe, the club’s president, that he’s a billionaire. Here, Satya is the prover and Chloe the verifier.”
Assuming Chloe trusts Satya’s bank and the government, Satya can convince Chloe that he is a billionaire by providing her with two pieces of evidence:
A digitally signed bank statement showing that someone named Satya has a balance of at least 1 billion USD, and
A government-certified photo-ID showing that he is the same Satya referred to in the bank statement.
Provided that Satya is already in possession of his photo-ID, all Satya has to do is download his statement from the bank’s website. He will then upload both to the club’s website for Chloe to verify. Once Chloe has access to the documents, she will use her (implicit or explicit) verification system to determine whether she a) trusts the evidence, and b) finds the evidence convincing.
Chloe’s trust in the evidence provided (both the digital copy of the physical ID and the digital bank statement) is based on the assumption that the evidence has integrity, that is to say, that it is authentic and unaltered. We can be confident in the integrity of evidence when it is:
A. Constructible only by the appropriate authority,
B. Easily verifiable by the public, and
C. Difficult to deconstruct or reverse engineer.
Physical evidence such as passports and driving licenses base their integrity upon a variety of complicated production mechanisms that are difficult to reproduce for forgers without access to expensive and specialized equipment. For digital evidence, we use the cryptographic primitive of digital signatures as our primary example.
Satya’s bank may make use of a digital signature protocol to satisfy our integrity constraints:
Constructible only by the appropriate authority
On Satya’s request, the bank constructs the digital signature on Satya’s bank balance, using its own private key, which only the bank holds.
Easily verifiable by the public
Chloe verifies the signature based the bank’s public key, an easy and performant operation.
Difficult to deconstruct or reverse engineer
No one, including the verifier, can deconstruct the signature using publicly available information (the bank’s public key) to duplicate the signature or reveal the private key. This is due to the fact that deriving a public key from a private key is a one-way function.
Note that in terms of performance, verifying digital signatures takes less time and computational resources than construction, whereas construction takes exponentially less time and resources than deconstructing (breaking) it:
This asymmetry in computational performance is generally a desirable trait for our proof systems, and is baked into most modern cryptographic protocols.
In order for Chloe to be convinced about Satya’s evidence (the bank balance and the government ID), they have to be relevant to his claim (“I am a billionaire”) and come from a worthwhile authority. Imagine that Satya signs his own bank balance, instead of asking his bank to do it. Even if the digital signature verified correctly (the evidence has integrity), would Chloe really accept Satya as an authority on the matter? Probably not.
Convincing evidence should be:
A. Precise: Address the claim directly with relevant substantive information,
B. Complete: Leave no questions in the mind of the verifier, and
C. Authoritative: Be recognized as an objective, credible source of truth.
To return to our example with Chloe and Satya, a valid bank balance from a reputable bank dated 10 years previously may be precise but not complete (it might be out-of-date), while a scanned passport with a fuzzy photo would be complete even if it were not precise.
With both trusted and convincing evidence, we can expect to satisfy an attentive verifier. The obvious drawback, of course, is how willing Satya will be to provide such trusted and complete information about his life to Chloe.
Now, do you trust me, Chloe?
Imagine that Satya has successfully presented trusted (digitally signed) and convincing evidence of his billionaire status to Chloe. In our information system, does this mean that Chloe will trust future claims Satya advances, such as “I used to be the best chef in Sri Lanka back in 2010”?
Alas, no! Proof systems do not enable us to trust each other, but rather allow us to trust specific claims made to one another. While the proofs establish the truth of a claim, they say nothing about the claimant. If only we had a “proof of reliability” or a “proof of soul”!
From proof system to proof network
We now see how Chloe can be convinced that Satya is indeed a billionaire, but how do the rest of the club members trust Chloe? Here, we run into the limitations of our proof systems: Proofs are relevant only within the context of the specific proof system and relationship. This means that every other club member has to have faith in Chloe as an honest verifier.
If they wanted proof, other club members would have to repeat some (if not all) of the steps of the proof system, which could even mean starting with designing the proof requirements. We will address this (quite serious) limitation in the next part of this series.
For now, we have established the following criteria as desirable for proof systems in digital relationships:
The verifier must have the tools to verify the evidence,
The prover must provide evidence that is both trustable (belonging to the rightful source, easy to verify, difficult to forget)
As well as the following limitations:
The prover has little control over the information shared with the verifier, and
Proofs do not translate well outside of relationships, so we “trust” external verifiers at our own peril!and convincing (precise, complete, and authoritative), leveraging the asymmetry of computational performance,
This relationship, between prover and verifier, is the most fundamental way to establish truth in our everyday lives. Thus, being able to model this relationship in digital systems opens up the door to building4 systems to solve a wide range of problems. Modern asymmetric cryptography allows us to meet our criteria for digital proof systems. In the next installation, we will explore how to address the given limitations through zero-knowledge proofs and economic networks.
Here, proofs should be interpreted in the detective sense (“Do you have any proof of that, Sherlock?) rather than in the mathematical sense (“Here is an inductive proof of your theorem, Watkins). That is, we are interested in empirical proofs rather than formal proofs.
There are certain kinds of truth that do not need to be verified, — these are obvious kinds of truth such as a tautology. Examples of a tautology: “All bachelors are unmarried”, “All triangles have three sides”. Here the truth in these two claims is given. For every other kind of truth, verification is a must! In this article, we will see how these non-obvious forms of truth come alive.
Where the proof system involves multiple provers and verifiers working together, it is more of a proof network. An example of that is the Bitcoin blockchain, where every address is proving to every other address the legitimacy of its transactions.
Speaking of proving the existence of dinosaurs using fossils as the verifiable evidence, here at Stratumn, one of the first tools we built years ago was aptly named “Fossilization”. It allowed users to timestamp a hash in the Bitcoin Blockchain.
Anuj Das Gupta is a researcher and technologist.