Beyond Decentralization

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:

• Trading and settlements
• Validating corporate documents for stock issuance
• Proving KYC compliance to regulators
• Online multi-player games

Central to every process, there are the challenges of ensuring that:

• the process fulfills all of the promises and contractual obligations
  – each step of the process is executed per its contractual specifications as agreed upon by the stakeholders
  – each step of the process adheres to contractual regulations as set by regulators and auditors
• all of the stakeholders in the process are equally in sync with the current state of the process
• all of the stakeholders of the process are bound by their access rights
• the process maintains its integrity in the face of attack from hackers.

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.

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:

1. Completeness: A prover should be able to convince a verifier anything that is correct. In other words, you can prove anything that’s right.
2. Soundness: A prover should not be able to prove a verifier anything is incorrect. In other words, you cannot prove anything that’s wrong.

With respect to processes, there are primarily two kinds of Proofs:

1. Formal Proofs: Proofs of algorithms that can be verified mathematically without ever having to actually execute the algorithm. These types of proofs are known as ‘correct by construction’ as they prove the correctness of an intended algorithm with respect to a formal specification (construction) of the algorithm. For example, to prove that a certain sorting algorithm works, a formal proof can be used to mathematically verify its correctness without ever executing the algorithm—as long as the specification of the algorithm can be formally specified. In cases where the execution is costly or test runs are not feasible, formal proofs of algorithms are the best fit.
2. Crypto-economic Proofs: Proofs of steps of a process, that are verified by actually executing the steps either by multiple independent nodes or by a trust source in a network, in order to come to a consensus as to its correctness—if the majority nodes agree on the result of the execution. This can be referred to as ‘correct by consensus’ since even if a trust source provides the primary validation, it can be verified by others, ideally anyone else with the proper access rights should be able to verify the proof. This is a mix of cryptography and economics, hence the term crypto-economics: cryptography for securing the process, and economic game theory to incentivize the nodes to execute and validate honestly without any colluding.

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.

The Dimensions of Every Proof System

There are two dimensions to every proof system:

1. Construction: The construction of a proof is valid as long as it is based on facts. This would entail strategies to capture the data that mirrors reality to be a factual element.
2. Verification: This would then entail fact-checking.

However, the construction of a proof is not symmetric to its verification:

• Construction may have secret data but can still be verified without access to that secret
• Construction can be done by one party but remain verifiable by multiple parties

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:

Applying Proof Systems to Processes

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.

Proof of Process: Layers and Properties

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:

1. What lies in this step? Or, Proof of Integrity: prove that the content of a step has not been tampered using cryptographically secure data digests.
2. When was this step executed? Or, Proof of Anteriority: prove when a step was executed by objectively time-stamping the Proof of Integrity on a common timeline.
3. Who is behind the step? Or, Proof of Non-repudiation: prove who is responsible for a step in such a way that the source or the destination of the information content of a step cannot be repudiated. This is done with the help of authentication services utilizing identity certificates and digital signatures on the Proof of Anteriority and Proof of Integrity.
4. Where is the step in the process? Or, Proof of Contextuality: prove where a step belongs in the process, i.e. prove the correct sequencing/ordering of steps in relation to the specific step by cryptographically referencing in the proof of each step that of its previous step.
5. Why is the step necessary Or, Proof of Applicability: prove why the step was executed or, more importantly, bind the actual legal clause with the execution of every step in a way that the other four proofs of every step can be admissible in a court of law.

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:

1. Cumulative: In every step, the proof is constructed by referencing the proof of its previous step. Thus, it is impossible to alter a single proof without invalidating all of its previous proofs.
2. Directional: Proofs in each step, being cumulative, have a direction and total ordering from that of the first to the most recent step as they are constructed. Not only can you demonstrate the proof of a step but you can also prove the path it took to construct the proof for a step.
3. Immutable: The cumulative proofs are cryptographically anchored to a common timeline shared across all participants of the process. Thus, proofs cannot be tampered by any single participant.

Trust Models: Applying Proof Matrix to Proof of Process

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:

1. 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).

2. 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.

PoP Trust Model Applied to Network and Process Security

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.