API/RSS

Social

How to transform interactive proofs into non-interactive proofs?

Fox Tech

23-03-17 17:18

Read this article in 15 Minutes

AI summary

View the summary

原文标题：《如何将交互式证明改造为非交互式？》

Shuiyue Kang, CEO of Fox Tech; Hyun Ji Meng is chief scientist at Fox Tech

preface

Zero-knowledge proof techniques in cryptography have a wide range of applications in the web3 world, including privacy computing, zkRollup, and so on. FOAKS, used by FOX in the Layer2 project, is a zero-knowledge proof algorithm. In the above series of applications, two attributes are extremely important for the zero-knowledge proof algorithm, that is, the efficiency of the algorithm and the interactivity.

The importance of algorithm efficiency is self-evident. Efficient algorithms can significantly reduce system uptime, thereby reducing client latency and significantly improving user experience and efficiency. This is an important reason why FOAKS is committed to achieving linear proof time.

On the other hand, from the perspective of cryptography, the design of zero-knowledge proof systems often relies on multiple rounds of interaction between prover and verifier. For example, in the story of "zero knowledge cave" which is used in many popular science articles introducing zero knowledge proof, the realization of proof depends on multiple rounds of information transmission interaction between Alibaba (prover) and journalists (verifier). But in fact, in many application scenarios, dependent interactions can render the system unusable or increase latency significantly. Like in the zkRollup system, we expect the prover (i.e., the folder in FOX) to be able to compute the correct prover value locally, without relying on interaction with the prover.

From this point of view, how to transform the interactive zero-knowledge proof protocol into non-interactive is a very significant problem. In this article, we introduce FOX's process of using the classic Fiatic-Shamir heuristic to generate challenges in Brakedown to implement non-interactive protocols.

The Challenge in proof of zero knowledge

Zero-knowledge proof algorithm has become extremely popular with the spread of applications. In recent years, a variety of algorithms including FOAKS, Orion, zk-stark, etc. The core logic of these algorithms, as well as early sigma protocols in cryptography, is that the Prover first sends a value to the Verifier, who generates a Challenge through local random numbers and sends the randomly generated challenge value to the proifier. The prover needs to have real knowledge to make a response that passes the prover with high probability. For example, in the cave of zero knowledge, the reporter tossed a coin and told Alibaba to come out from the left side or the right side. The "left and right" here was the challenge to Alibaba. If he really knew the spell, he would be able to come out from the required direction, otherwise there would be half the probability of failure.

Here we note that the generation of the Challenge is a critical step, and it has two requirements, random and unprovable prediction. Number one, randomness guarantees its probabilistic properties. Second, if the prover can predict the challenge value, it means that the security of the agreement is broken, and the prover can pass the verification without knowledge. It can continue the analogy, if Alibaba can predict which side the reporter asks him to come from, he can enter that side in advance even without a spell, and the result shows that he can pass the agreement.

So we need a way for the prover to generate such an unpredictable random number locally, yet be validated by the prover, so that a non-interactive protocol can be implemented.

Hash Function

The name of the hash function may be familiar to us, whether in Bitcoin's consensus protocol POW as a mining math problem, to compress the amount of data, the construction of message verification code, and so on, hash functions are used. And in all of these different protocols, you actually use a variety of properties of the hash function.

Specifically, the properties of a secure hash function include the following:

Compressibility: A certain hash function can compress a message of arbitrary length into a fixed length.

Validity: Given input x, calculating output h (x) is easy.

Collision resistance: Given an input x1, it is difficult to find another input x2, x1x2, h (x1) = h (x2).

Note that if the hash function satisfies collision resistance, then it must satisfy unidirectivity, that is, given an output y, it is difficult to find x satisfying h (x) = y. In cryptography, it is not possible to construct a function that absolutely satisfies unidirectivity in theory, but the hash function can be regarded as a unidirectional function in practical application.

In this way, it can be found that the above several applications correspond to several different properties of hash function. At the same time, we say that hash function also plays an important role in providing randomness. Although the perfect random number generator required by cryptography theory cannot be constructed at present, hash function can also play this role in practice. This provides the basis for the Fiat-Shamir Heuristic techniques we introduce later.

Fiat-Shamir Heuristic

In fact, the Fiat-Shamir Heuristic uses hash functions to hash previously generated scripts, yielding a value that serves as a challenge value.

Since the hash function H is regarded as a random function, the challenge is to be selected uniformly randomly, independent of the prover's public information and commitment. Security analysis assumes that Alice cannot predict the output of H, and can only treat it as an oracle. In this case, the probability that Alice will respond correctly without following the protocol (especially if she does not know the necessary secrets) is inversely proportional to the size of the range of H.

Figure 1: Non-interactive proof of non-interactive FOAKS with Fiat-Shamir Heuristic

In this section, we show how the Fiat-Shamir heuristic applies to the FOAKS protocol, primarily to generate the Brakedown portion of the challenge to implement non-interactive FOAKS.

First, we saw that among the Brakedown proof generation steps, the ones to be challenged were the "approximation test" and the Merkle Tree proof section (refer to the previous article "Brakedown, a polynomial Commitment Protocol in FOAKS"). For the first point, the original process is a random vector generated by the prover. The calculation process is shown as follows:

Figure 2: Brakedown Checks in non-interactive proof FOAKS

Now let's use the hash function and let the prover generate this random vector.

Let 0=H(C1,R, r0,r1), corresponding to the verification calculation of the verifier, also need to add this step to calculate 0. According to this construction, it can be found that the prover cannot predict the challenge value in advance before the generation of the promise, so it cannot "cheat" according to the challenge value in advance, that is, generate the corresponding false promise value. Meanwhile, according to the randomness of the output of the hash function, the challenge value also satisfies the randomness.

For the second point, let I=H(C1,R, r0,r1,c1,y1,c0,y0).

We use pseudocode to present the proof and verification functions in the modified non-interactive Brakedown polynomial promise, which is also used in the FOAKS system.

function PC.Commit () :

Parse w as a kk matrix. The prover locally computes the tensor code encoding C1, C2, C1 is a kn matrix, C2 is a nn matrix. Parse W as a kk matrix. The prover locally computes the tensor code encoding C1, C2, C1 is a kn matrix, C2 is a NN matrix.

for i [n] do

Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])

Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment.

function PC. Prover(, X, R)

The prover generates a random vector 0Fk by computing: 0=H(C1,R, r0,r1)

Proximity: c0=i=0k-10[i]C1[:,i],y0=i=0k-10[i]w[i]

Consistency: c1=i=0k-1r0[i]C1[:,i],y1=i=0k-1r0[i]w[i]

Prover sends c1,y1,c0,y0 to the verifier.

Prover computes a vector I as challenge, in which I=H(C1,R, r0,r1,c1,y1,c0,y0)

for idxI do

Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier

function PC. VERIFY_EVAL(X,X,y=(X),R)

Proximity: idxI,C0[idx]==< 0,C1[:,idx]> and EC(y0)==C0

Consistency: idxI,C1[idx]==< r0,C1[:,idx]> and EC(y1)==C1

y==< r1, y1>

idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx "s Merkle tree proof is valid.

Output accept if all conditions above holds. Otherwise output reject.

conclusion

Many zero-knowledge proof algorithms rely on the interaction between prover and verifier at the beginning of design, but this interactive proof protocol is not suitable for application scenarios that pursue high efficiency and high network communication cost, such as on-chain data privacy protection and zkRollup. Through the Fiat-Shamir Heuristic, the prover can generate random number "challenges" locally without breaking the security of the protocol, and can be verified by the prover. In this way, FOAKS also implements non-interactive proofs and applies them to the system.