Opporty Technical Paper. Part 2

Part I of Opporty’s Technical Paper was dedicated to issues of confidentiality, anonymity, and data privacy in blockchain technology. We unveiled some of the solutions used by Opporty to enhance the security and privacy elements of blockchain technology.

In this second part of Opporty’s Technical Paper, we explain the benefits of zk-SNARKs algorithms and their implementation.

Opporty Implementation of zk-SNARKs Protocol

Abstract

zk-SNARKs algorithms are among the most crucial components when embedding blockchain protocols.

This algorithm enables us to confirm data and check sustainability from a witness. It uses math calculations to meet decentralization requirements.

Safety is achieved by an input that is secret to everyone, which is generated by the algorithm during confirmation. Confirmation is made by applying a series of math calculations. Once the confirmation is made, the algorithm deletes the secret input.

This algorithm can be used for block mining:

After checking the block, a miner gets an offer to provide his confirmation by executing the algorithm. Some data details, generated by the algorithm, are kept secret from the miner.

After the confirmation is generated, the miner gets a reward, the secret input is deleted (no one will ever know it), and the confirmation is sent to the blockchain as a pass for the block.

The zk-SNARKs algorithm has great potential and can be introduced in a variety of use cases.

Applicable to blockchain, this algorithm will be used at Opporty for transaction anonymity and data reduction. zk-SNARKs allows for the checking of complicated calculations without repeating them and, most importantly, without revealing any data other than the input data.

zk-SNARKs consists of three algorithms:

Definitions:

The key generator G takes a secret parameter lambda and a program C. It also generates two public keys: a proving key pk, and a verification key vk. These keys are public parameters that need only be generated once for a given program C.

The prover P takes as input the proven key pk, a public input x and a private witness w. The algorithm generates a proof prf=P(pk,x,w) where the prover knows a witness w and that the witness satisfies the program C.

The verifier V identifies V(vk,x,prf)which returns true if the proof is correct, and false if otherwise. Thus, this function returns true if the prover knows that secret w satisfies C(x,w) is true.

For zk-SNARKs implementation, we must review its four basic parts. By embedding these parts, we can embed the protocol itself. They are:

1) Polynomial encoding:

To compute the program, we must encode it first into a quadratic equation of polynomials. After that, we have to make sure that the program is being executed. To do so, we must check the point on the polynomials and check the equality:

2) Random Sampling Succinctness

The verifier picks secret evaluation points, so the polynomial problem is reduced to simple operations on certain curves and field elements:

This dramatically reduces both the proof size and the verification time.

3) Homomorphic encoding

An encoding function E has homomorphic properties. This allows the proverto compute the value of E(H(s)), E(Z(s)), E(A(s)), E(B(s)), E(C(s)) without knowing the s value, and only knowing E(s).

4) Zero Knowledge

The prover does not reveal the value of E(H(s)), E(Z(s)), E(A(s)), E(B(s)), E(C(s)), but multiplies them by a certain number, sending the encrypted data to the verifier in this way. They obtain the same properties and the checking goes successfully.

Opporty implemented zSNARKs using the algorithms introduced by Bryan Parno Jon Howell, Craig Gentry, and Mariana Raykova in Pinocchio: Nearly Practical Verifiable Computation.

Let’s begin with the first generation algorithm:

Generator (C, λ)

First of all, we have to find the polynomials A, B, C, Z , A*B-C=0 to identify the keys. This means we need to convert the computations into Quadratic Arithmetic Programs (QAP). Therefore, the whole program is transformed into a set of logic gates. Each logic gate is compliant with a particular operation, with two inputs and one output.

In other words, a circuit is a set of gates and wires which cohere to the intermediate variables.

It is easy to determine the QAP and polynomials A, B, C, Z: A QAP over field Fcontains three sets of polynomials: A linear combination {A1…Am}, B linearcombination {B1…Bm}, C linear combination {C1…Cm}, and a target polynomial Z.

Suppose F is a function that takes as input n elements of F and outputs Nelements, a total of n+N IO elements.

Then we say that Q computes F if: (c1,…, cn) ∈ F is a valid assignment, that there exist coefficients (cn+1,…, cm) such that Z(x) divides P(x), where:

Building a QAP is a trivial task. First, we pick an arbitrary root r ∈ F for each multiplication gate.

Defining the target polynomial Z:

The next step is to associate an index to each input of the circuit and to each output from a multiplication gate. We then define the polynomials in the following way: А polynomial encodes each first input in the gate, B polynomial encodes each second input in the gate, C encodes the outputs.

For example:

Then, knowing the polynomial solutions in those points, we may get the polynomial formulas by using Lagrange interpolation, and compute A, B, C, Z using the linear combination.

Having the polynomials computed, we are able to calculate their values in some random secret s point. These values can then be homomorphically encoded by using points and pairings on elliptic curves.

The information regarding pairings on elliptic curves and their encoding is quite vast and requires a separate article for a complete description. Yet it is enough to say that taking the point on curves gives us an opportunity to hide the real point’s value, so we are able to compute E(s), E(A(s))without uncovering the data.

On a basic level, the prover has to generate:

G — is point one on the curves.

And the verifier has to confirm that A(s)B(s)-C(s)=H(s)Z(s) is true.

This can be achieved by pairings on elliptic curves, as will be described later.

We also must mention that the prover must prove that a genuinely linear combination for polynomials has been provided, computed on a certain point.

This can be arrived at by the Knowledge of Coefficient Test.

Suppose there are several points P, Q, Q=k*P, and the test proves the infeasibility of creating such a pair of points R, S, where:

S=k*R, if R is not received from point P in a particular way.

In other words, we can receive the points R, S, where:

R=k*S, only if we take P, Q points and multiply by the coefficient, which only we know.

Another significant feature is that concepts of pairings make it simple to check that R, S points are received from P, Q, without even knowing that k:

Also, if we have the set of points (P1, P2, P3, P4, P5) and (Q1, Q2, Q3, Q4, Q5), where:

Q1=P1*k, the only way to receive the points R, S,

S=k*R, is to take the linear combination of points with coefficients:

It is impossible to get the result without kQ1,…,Q5 from P1,…,P5, without a linear combination and the k value.

Therefore, it is vital for the points creator to be credible and to delete k and other coefficients immediately after they have created all the points. This concept is called “Trusted Setup”, and that is what the first Generator algorithm does.

Here are the values that pass as p, vk.

Then we pick α. βA, βB, βC, y ← F in a random way. And the public key is created for the pk prover to use:

d — the polynomials degree

It is vital for si points that the prover is able to compute the values in polynomial points G*Hk(s).

The prover’s public key:

N — the number of indexes related to the input/output

Having the generated keys, the prover can launch the process of proof creation. This is the second prover’s function.

It receives pk and w– the witness’s parameter, which can be computed by executing the program.

With these parameters we can compute the polynomial values in a secure way, using operations on elliptic curve points.

And that is how we receive the data for the prover:

where {c1,…,ck} is a witness.

We need G*βA*A(s)+βB*B(s)+βC*C(s) value to check that all three linear combinations have the same coefficients. The most convenient way to check is by using the pairings.

In order to get the polynomial H value, we have to solve the polynomial, dividing:

In this way we can create a proof that will later pass to the third algorithm Verifier. This algorithm compares whether the program was correctly computed and executed by checking the QAP dividing and α, β coefficients.

Pairing on the elliptic curves is used on all occasions.

The first step is to check the α coefficient values.

Then, it is time to check all the combinations with the same coefficients:

The last check is the most crucial: the QAP division.

Reminder: the inputs are acquainted and are calculated separately

We have considered three basic algorithms related to zk-SNARKs.

Generator (C — circuit, λ is toxic waste):

Prover (x pub input, w sec inp):

Verifier:(input, proof)

Conclusion

In this article we did not discuss the zero knowledge part, but it is easily calculated by multiplying:

The changed value of P(x) will remain divided Z(x), but we will receive zero knowledge value, which is rather important.

In this way, we can prove the conducted calculations and check them.

There exist a variety of possible use cases for zk-SNARKs protocol, such as:

• transaction anonymity;
• data reduction;
• blockchain identifiers archivation;
• coin history representation.

Visit our Github profile to get more information about zk-SNARKs protocol.

You may read more about Opporty’s core technology and innate features in the First Part Of Opporty Technical Paper.

DISCLAIMER

This technical paper is a work in progress (i.e. not a final version of the document). The Opporty team reserves the right to update and edit the technical paper as required.