175 Followers
·
Follow

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

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