Switch the website to: 繁體中文， English
（Powered By :
ChatGPT）

Fox Tech

03-17 17:18

The popular science

Reading this article requires 19 minutes

Translate this text into 繁體中文， 简体中文
（Powered By :
ChatGPT）

Abstract is generated
ChatGPT produce

This article describes how FOX uses the classic Fiat-Shamir heuristic to generate challenges in Brakedown to implement non-interactive protocols.

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

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

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.

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.

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.

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.

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.

Original link

The popular science

Learn from here

Related articles

Introduction | What are the types of Bitcoin addresses?

How many types of wallet addresses does Bitcoin have and what are their characteristics? Let's explore together in this knowledge sharing session.

05-20

科普教程Wallet Tracking 101 Guide

Mastering wallet tracking skills to find the right wallet and easily profit.

05-19

科普教程MEV and Privacy Development Trends: Current State of MEV Technology and Novel Privacy Designs.

Current Status, Technical Trends, and New Designs of MEV

05-12

科普教程Popular articles

Exclusive Interview with Kakarot: The Future Super Saiyan Invested by Vitalik.

Exclusive Interview with Kakarot: The Future Super Saiyan Invested by Vitalik.

Arthur Hayes: Don't lose heart, the bull market in the fourth quarter is coming.

Arthur Hayes: Don't lose heart, the bull market in the fourth quarter is coming.

19 Responses from He Yi: Regarding Binance Listing, IEO Rumors, and Market Share.

19 Responses from He Yi: Regarding Binance Listing, IEO Rumors, and Market Share.

Business

Business

Contribute

Post