This is a series of articles. Part 7,​ ​ PDF version

Zero-Knowledge Proof of Computation

Since the introduction of the general-purpose computation protocol (Proof of Operation section) we had to let go of the zero-knowledge property, to make the transition simpler. Until this point, we have constructed a verifiable computation protocol.

Previously to make a proof of polynomial zero-knowledge we have used the random δ-shift, which makes the proof indistinguishable from random (Zero-Knowldge section):

Image for post
Image for post

With the computation we are proving instead that:

Image for post
Image for post

While we could just adapt this approach to the multiple polynomials using same δ, i.e., …


This is a series of articles. Part 6,​ ​ PDF version

Constraints

Our analysis has been primarily focusing on the notion of operation. However, the protocol is not actually “computing” but rather is checking that the output value is the correct result of an operation for the operand’s values. That is why it is called a constraint, i.e., a verifier is constraining a prover to provide valid values for the predefined “program” no matter what are they. A multitude of constraints is called a constraint system (in our case it is a rank 1 constraint system or R1CS).

Note: This implies that one way to find all correct solutions is to perform a brute-force of all possible combinations of values and select only ones that satisfy the constraints, or use more sophisticated techniques of constraint satisfaction [con18]. …


This is a series of articles. Part 5,​ ​ PDF version

We went through many important modifications of the knowledge of polynomial protocol to make it general-purpose, so let us see how it is defined now. Assuming agreed upon function ​ f(*) the result of computation of which is the subject of the proof, with the number of operations d, the number of variables n and corresponding to them coefficients

Image for post
Image for post


This is a series of articles. Part 4, ​ ​PDF version

With the multi-operation polynomials approach introduced in part 4, we can prove many operations at once (e.g., millions and more), but there is a critical downside to it.

If the “program,” execution for which is being proved, uses the same variable, either as an operand or as output, in different operations, for example:

Image for post
Image for post

The a will have to be represented in the left operand polynomial for both operations as:

Image for post
Image for post

Nevertheless, because our protocol allows prover to set any coefficients to a polynomial, he is not restricted from setting different values of a for different operations (i.e., …


This is a series of articles. Part 3, ​ PDF version.

We have paved our way with a simple yet sufficient example involving most of the zk-SNARK machinery, and it is now possible to advance the scheme to execute zero-knowledge programs.

Computation

Let us consider a simple program in pseudocode:

Algorithm 1: Operation depends on an input
————————————————————————————————————————————————————————————————————
function calc(w, a, b)
if w then
return a × b
else
return a + b
end if
end function

From a high-level view, it is quite unrelated to polynomials, which we have the protocol for. Therefore we need to find a way to convert a program into the polynomial form. The first step then is to translate the program into the language of math, which is relatively easy, the same statement can be expressed as following (assuming w is either 0 or…


This is a series of articles. Part 2,​ ​ PDF version

Non-Interactivity

Till this point, we had an interactive zero-knowledge scheme. Why is that the case? Because the proof is only valid for the original verifier, nobody else (other verifiers) can trust the same proof since:

  • the verifier could collude with the prover and disclose those secret parameters s,α which allows to fake the proof, as mentioned in remark 3.1
  • the verifier can generate fake proofs himself for the same reason
  • verifier have to store α and t(s) until all relevant proofs are verified, which allows an extra attack surface with possible leakage of secret…


This is a series of articles. Part 1,​ ​ PDF version.

We start with a problem of proving the knowledge of a polynomial and make our way to a generic approach. We will discover many other properties of polynomials along the way.

The discussion so far has focused on a weak notion of a proof, where parties have to trust each other because there are no measures yet to enforce the rules of the protocol. For example, the prover is not required to know a polynomial, and he can use any other means available to him to come up with a correct result. Moreover, if the amplitude of the verifier’s polynomial evaluations is not large, let us say 10, the prover can guess a number, and there is a non-negligible probability that it will be accepted. We have to address such weakness of the protocol, but first what does it means to know a polynomial? …


The article is an adaptation of the PDF version.

Despite the existence of multiple great resources on zk-SNARK construction, from original papers [Bit+11; Par+13] to explainers [Rei16; But16; But17; Gab17], due to the sheer number of moving parts the subject remains a black box for many. While some pieces of the puzzle are given one can not see the full picture without the missing ones.

The first time author discovered how things fit nicely together, one was astounded by the beauty of math, and the more dimensions were uncovered, the more it kept the spirit of wonderment. Hence the focus of this work is sharing the experience by shedding light onto the topic with a straightforward and clean approach based on examples and answering many whys along the way so that more individuals can appreciate the state of the art technology, its innovators and ultimately the beauty of math. …


A private blockchain is a great way to achieve consensus between independent companies on transactions they do between each other. It brings decentralization into the equation, where no single party is responsible for maintaining master records and running business logic, and therefore has to be trusted.

While usually, parties are cooperating, they live in an open market’s competing environment, hence no chance they will open up all business activities to each-other, therefore giving up competitive advantage. This single fact has proven consortium chains to be useless if there’s no confidentiality. …


It was a great and surprisingly very welcoming experience to demo first ever Title Deed registration on the Quorum blockchain. Other physical objects such as a bar of gold and a package for shipment was demoed at Enterprise Ethereum Alliance launch event.

Discover how can you give cryptographic identity to any physical object and connect the dots between real world and the blockchain world.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store