Smart Contracts
Fulfilling Nakamoto's Dreams
Prover-Verifier Systems
Richard Caetano and I presented Stratumn research on Proof Systems at the Ethereum Developer Conference in Paris on 18th of February, 2017. It was titled, ‘Going Beyond Decentralization with Prover-Verifier Systems’. This post refers to the same topic and uses slides from that talk.
A process is a sequence of steps in time. Whenever there is a movement of ideas, conversations, goods and products, we have a process.
In a process, there can be multiple owners, actors and stakeholders. A single process can split into two; multiple processes can intersect at a certain step or merge together. There can be parallel steps in a single process forming separate timelines.
In today’s hyper-connected world, more and more of these processes are being automated with software.
Software, if done right, provides efficiency, flexibility and interconnectivity for processes. Some examples of software-automated processes include:
Central to every process, there are the challenges of ensuring that:
Only if we can ensure that each of the above points have been met, can we then trust the process. To accomplish this, the process needs to come with proofs that can be verified. For this purpose, we introduce Proof Systems.
A proof system enables a prover to convince a verifier of a secret or a fact within a reasonable amount of doubt. Every proof system has at least two properties:
With respect to processes, there are primarily two kinds of Proofs:
In this article, we are concerned with crypto-economic proofs only, and this is what we mean by proofs in general.
In every proof system, there are two parties, the prover and the verifier, who are involved in a protocol to exchange messages. Messages are exchanged until the verifier is convinced that the prover has the secret or the fact within a reasonable doubt.
As an example, when the bitcoin miner proves that she found the nonce, she is the prover and the bitcoin network is the verifier. If her proof is verified, she is rewarded by the network. Another example would be when I pay using my credit card, I (prover) prove the ownership of my card with the pin number to the payment service provider (verifier).
However, proof systems are by no way restricted to decentralized systems. In fact if a legacy system can provide the proof of its honesty: for example, the proof of integrity of one of its transactions using a digitally signed receipt — that can be fed as an input to a blockchain smart contract as long as the smart contract is able to verify the signature. In this example, the legacy system is the prover and the blockchain smart contract is the verifier, while the digitally signed receipt is the evidence for the proof and the certificate authority for accepting the signature is the trusted source that both the prover and the verifier have to contractually accept.
Another example of Proof Systems that go beyond the decentralized maximalism is that of Proof of Existence schemes implemented by embedding cryptographic hashes of the data in question inside the OPCODE of a Bitcoin transaction. Here the blockchain, utilizing its decentralized timestamping service, acts as only an objective registry to store the evidence of the proof. However, the verifier could be a standalone program or even a client-server system with access to the actual data as long as it can connect to the blockchain for retrieving the hash to verify if it matches.
In these ways, proof systems can be designed to connect a wide variety of systems in a provably secure way. The roles of prover and verifier can be played interchangeably based on the context and the nature of the proof even in cases where information has to flow beyond the boundaries of decentralization vs centralization.
There are two dimensions to every proof system:
However, the construction of a proof is not symmetric to its verification:
As an example of a Proof System from the dimensional perspective, consider Smart Contracts. They are a powerful tool for automating the execution of code between multiple parties which rely on consensus to arrive at a provable outcome. Determinism, repeatability and logic are the requirements for executing smart contracts.
We can say that smart contracts are a type of proof that is constructed with a view of what can happen in the future. That is, given a well-written contract with clean logic, we can arrive at outcomes A, B or C in the future. Thus, from a proof construction perspective, we can say that smart contracts are a type of ‘proactive proof’.
However, when we look at the real world, we see that processes are dynamic, usually not repeatable and often zig-zag, meaning that people can offer different outcomes to satisfy an agreement.
One could imagine the multiple ways that the buyer could provide proof of payment: wire transfer, bitcoin transaction, cash, five cows, etc. These options may not be known at the time when the proof is to be constructed as in the case of smart contracts. Here we need to construct a proof after the event—that is, a proof of what always already happened. From a proof construction perspective, this can be referred to as a ‘retroactive proof’.
From a proof verification perspective, a proof is valid as long as the evidence of the proof could be verified to be factual, where facts are statements about reality. Thus, fact-checking is key to weighing in evidence.
If fact-checking can be done by evaluating a mathematical formula without the need to refer or depend on any source of trust, then the fact-checking can be referred to as objective.
On the other hand, if facts have to be trusted based on a trust source’s attestation of validity — e.g. validating a proof of address as long as it is signed by a government certified authority — then the fact-checking can be referred to as subjective.
Thus, from a Proof Verification perspective, we can have either objective or subjective fact-checking.
This relationship between the two dimensions of proofs construction vs verification represents the following Proof Matrix:
Proof of Process is a proof system that enables a prover to convince a verifier of the integrity of a process.
For example, in the process of manufacturing an airplane, the subcontractor making the wheels has to convince the aircraft manufacturer that she has followed all of the regulations in the process of making the wheels. The subcontractor is a prover and the aircraft manufacturer is the verifier in the proof of process. At the same time, when the aircraft manufacturer has to convince the regulatory bodies that its components comply with regulatory standards, that makes the manufacturer the prover and the regulators the verifier.
Central to Proof of Process is the following thesis:
If you can replay the steps of a process, you get traceability. If you can prove the data behind each step, you get transparency. With traceability and transparency, we have the conditions for trust.
There are five questions, or layers, in Proof of Process. Each layer builds up on its previous layer giving rise to an end-to-end proof system, as follows:
Thus, with Proof of Process, every proof can be verified on all of these five questions in a layer by layer basis. In a network where there are multiple verifiers trying to achieve consensus on the valid state of the process across all stakeholders, they can all refer to the same Proof of Process for every new step. This leads to a consistent view of the process across the network that is based on sharing proofs, not data. As a result, the proof of a process is decoupled from the actual process itself.
In addition to the properties of Completeness and Soundness that every Proof System has, every instance of Proof of Process has the following properties:
Applying the Proof Matrix to Proof of Process (PoP), we see that every PoP guarantees either what will happen (a pro-active proof) or always already happened (a retro-active proof) as long as it can be verified on an objective or subjective basis. This forms the trust model for Proof of Process.
Proactive Proofs, being forward facing, do not allow for the provision of forking, since going forward in time, it is not possible to define multiple parallel scenarios beforehand in a provable way as they are as-yet unknown and in most cases, undecidable.
In fact from a network perspective, if there has to be a consensus amongst a majority of verifiers on a proactive proof, then all forking has to be resolved (convergence) into a single thread of ‘what can happen’ in order to avoid ‘what all might happen’ so all verifiers can eventually agree on a single and thus, canonical version of truth. Thus, we can see that the upper half represents the deterministic and thus, non-forkable world of blockchains.
On the other hand, every time a retroactive proof is constructed, all of the different forks are already known because the construction captures (converges) all of the different threads/forks of evidence guaranteeing ‘what all has already happened’.
In fact from a proof construction perspective, retroactive proofs guarantee actualities as the evidence captures what all has already happened in each of the forks whereas proactive proofs guarantee potentialities as it guarantees what can happen.
Thus, the very act of a retroactive proof construction takes care of capturing (convergence) all of the forks into a single proof. Hence, retroactive proofs allow forking in a way that a majority of network participants can still achieve consensus on what has already happened based on the single converged proof. With respect to allowing forks in a chain, retroactive proofs represent process graphs (trees with branches) rather than blockchains (strictly linear chains). An example implementation of retroactive proofs used to secure processes is a Cryptographic Audit Trail (CAT).
Thus, from a network perspective, the upper half of the Proof Matrix represents blockchains while the lower half represents processes. Therefore, the PoP trust model has two primary modes:
Blockchains – The Proactive Model, or the upper half of PoP trust models:
Proactive guarantees of objective facts
Blockchains can be used to model deterministic processes that can be computationally verified, e.g. a pure smart contract to release the crowdfunding money, with all data born in the blockchain including the trigger to release the money.
Proactive guarantees of subjective facts
Blockchains can be used to model deterministic processes that need a trust source, e.g., a smart contract with an oracle input such as the DAO, with the input from the curators to release the fund. Another example is that of a smart contract which controls the sale and delivery of a product, where for every state transition in the life of the product you need signed attestations from the participants (as it lives outside the blockchain).
Processes – The Retroactive Model, or the lower half of PoP trust models:
Retroactive guarantees of objective facts
For non-deterministic processes that can be computationally verified, e.g. proof of delegation of computation with zero knowledge proofs—as long as you can verify the core of the proof with a formula (computational circuits) where the formula establishes the objectivity of the fact.
Retroactive guarantees of subjective facts
For non-deterministic processes that can be verified only with the help of a trust source, e.g. a CAT of a manufacturing process or a proof of address based on attestations in a network of participants.
Based on the above, the PoP trust model when applied to networks looks like this:
Compared to the traditional approach of securing networks with client-server architecture, the PoP trust model offers new ways of architecting networks with end-to-end security and surety. In such a network, proofs can be exchanged amongst the participants where they can interchangeably play the roles of prover and verifier.
With the client-server architecture, the clients trust the server, but not the other way around. This asymmetry of trust is based on a spoke-hub architecture, where the server is the hub and its clients the spokes, resulting in the centralization of all security measures in and around the server. Thus, the server alone has to insure against all attacks, by hiding the service behind firewalls to safeguard against attacks, while using access control systems to allow only authenticated clients. As a result, the server ends up isolating itself, which leads to inflexibility in the network topology.
As an alternative to the client-server architecture, PoP secures processes by mapping them onto prover-verifier networks where objectively verifiable data coexists with oracles and trusted third parties.
PoP allows participants to focus their energy into more creative and meaningful work — instead of working to maintain the ad-hoc data security of the client-server model.
While proof systems enable participants to trust their common processes, PoP enables participants to trust the networks — allowing participants to leverage their connections to create mutually beneficial contractual relationships at will.
We will explore this idea of (proof of) process networks in relation to network economies in coming posts.
You can watch the talk here.
Anuj Das Gupta is a researcher and technologist.