Written by: Kang Shuiyue, CEO of Fox Tech; Meng Xuanji, Chief Scientist of Fox Tech
Preface
Zero-knowledge proof technology in cryptography has a wide range of applications in the web3 world, including privacy computing, zkRollup, etc. FOAKS, used by the Layer2 project FOX, is a zero-knowledge proof algorithm. Among the above series of applications, there are two extremely important properties for zero-knowledge proof algorithms, namely, the efficiency and interactivity of the algorithm.
The importance of algorithm efficiency is self-evident. Efficient algorithms can significantly reduce system running time, thereby reducing client latency and significantly improving user experience and efficiency. This is also an important reason why FOAKS is committed to achieving linear proof time.
On the other hand, from a cryptographic perspective, the design of a zero-knowledge proof system often relies on multiple rounds of interactions between the prover and the verifier. For example, in the story of the "zero-knowledge cave" that is used in many popular science articles that introduce zero-knowledge proofs, the realization of the proof relies on multiple rounds of information transmission interactions between Alibaba (the prover) and the reporter (the verifier). But in fact, in many application scenarios, relying on interactions will make the system no longer available or increase latency extremely high. Just like in the zkRollup system, we expect the prover (that is, the folder in FOX) to be able to calculate the correct proof value locally without relying on interaction with the verifier.
From this perspective, how to transform an interactive zero-knowledge proof protocol into a non-interactive one is a very meaningful question. In this article, we will introduce how FOX uses the classic Fiat-Shamir heuristic to generate challenges in Brakedown to implement a non-interactive protocol.
Challenges in Zero-Knowledge Proofs
Zero-knowledge proof algorithms have become extremely popular as their applications have spread. In recent years, various algorithms have been born, including FOAKS, Orion, and zk-stark. The core proof logic of these algorithms, as well as the early sigma protocol in the cryptography community, is that the prover first sends a value to the verifier, and the verifier generates a challenge through a local random number and sends this randomly generated challenge value to the prover. The prover needs to have real knowledge to respond with a high probability to pass the verifier. For example, in the zero-knowledge cave, the reporter tossed a coin and told Alibaba to come out from the left or the right. The "left and right" here is a challenge to Alibaba. If he really knows the spell, he can definitely come out from the required direction, otherwise there is a 50% chance of failure.
Here we note that the generation of Challenge is a critical step, which has two requirements: randomness and unpredictability by the prover. First, randomness guarantees its probabilistic properties. Second, if the prover can predict the challenge value, it means that the security of the protocol is compromised, and the prover can pass the verification without knowledge. We can continue the analogy. If Alibaba can predict which side the reporter asks him to come out from, he can enter that side in advance even without the spell, and the result will still pass the protocol.
Therefore, we need a method that allows the prover to generate such an unpredictable random number locally and at the same time be verified by the verifier, so that a non-interactive protocol can be implemented.
Hash Function
The name of hash function may be familiar to us. Whether it is the mathematical problem of mining in Bitcoin's consensus protocol POW, or compressing data volume, constructing message verification codes, etc., hash functions are present. In the above different protocols, various properties of hash functions are actually used.
Specifically, the properties of secure hash functions include the following:
Compression: A certain hash function can compress a message of any length into a fixed length.
Efficiency: Given an input x, it is easy to compute the output h(x).
Collision resistance: Given an input x1, it is difficult to find another input x2, x1x2, such that h(x1) = h(x2).
Note that if a hash function satisfies collision resistance, it must also satisfy one-way property, which means that given an output y, it is difficult to find x such that h(x) = y. In cryptography, it is not possible to construct a function that theoretically absolutely satisfies one-way property, but hash functions can be basically regarded as one-way functions in practical applications.
In this way, we can find that the above-mentioned applications correspond to several different properties of hash functions. At the same time, we say that another very important role of hash functions is to provide randomness. Although the perfect random number generator required in cryptographic theory cannot be constructed at present, hash functions can also play this role in practice. This provides the basis for the Fiat-Shamir heuristic technique introduced later.
Fiat-Shamir Heuristic
In fact, the Fiat-Shamir heuristic uses a hash function to perform a hash operation on the previously generated script to obtain a value, which is used as a challenge value.
Because the hash function H is treated as a random function, the challenge is chosen 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 use it as an oracle. In this case, the probability that Alice responds correctly without following the protocol (especially when she does not know the necessary secret) is inversely proportional to the size of the domain of H.
Figure 1: Non-interactive proof using the Fiat-Shamir Heuristic
Non-interactive FOAKS
In this section, we specifically demonstrate the application of the Fiat-Shamir heuristic in the FOAKS protocol, mainly used to generate challenges in the Brakedown part, thereby realizing non-interactive FOAKS.
First of all, we can see that in the steps of generating proofs for Brakedown, the steps that need to be challenged are the "approximation check" and the Merkle Tree proof part (readers can refer to the previous article "Understanding the polynomial commitment protocol Brakedown in FOAKS in one article"). For the first point, the original process is that the prover needs a random vector generated by the verifier here, and the calculation process is shown in the figure below:
Figure 2: Brakedown Checks in FOAKS
Now we use a hash function to let the prover generate this random vector himself.
Let γ0=H(C1,R, r0,r1). Correspondingly, in the verification calculation of the verifier, the step of calculating γ0 also needs to be added. According to this construction, it can be found that before generating the commitment, the prover cannot predict the challenge value in advance, so he cannot "cheat" according to the challenge value in advance, that is, generate a false commitment value. At the same time, according to the randomness of the hash function output, this challenge value also satisfies randomness.
For the second point, let Î =H(C1,R, r0,r1,c1,y1,cγ0,yγ0).
We use pseudocode to give the proof and verification functions in the modified non-interactive Brakedown polynomial commitment, which is also the function used in the FOAKS system.
function PC. Commit(ϕ)：
Parse was a k × k matrix. The prover locally computes the tensor code encoding C1，C2 ，C1 is a k × n matrix，C2 is a n × n 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 γ0 ∈ Fk by computing: γ0 =H(C1,R, r0,r1)
Proximity:
Consistency:
Prover sends c1,y1,cγ0,yγ0 to the verifier.
Prover computes a vector Î as challenge, in which Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
for idx ∈ Î 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: ∀idx ∈ Î, Cγ0 [idx] == <γ0, C1[:,idx]> and Ec(yγ0) == Cγ0
Consistency: ∀idx ∈ Î, C1 [idx] == <γ0, C1[:,idx]> and Ec(y1) == C1
y==
∀idx ∈ Î, 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 the prover and the verifier at the beginning of their design, but this interactive proof protocol is not suitable for application scenarios that pursue high efficiency and have high network communication overhead, such as on-chain data privacy protection and zkRollup. Through the Fiat-Shamir heuristic, the prover can generate a random number "challenge" locally without destroying the security of the protocol, and it can be verified by the prover. Based on this method, FOAKS also implements non-interactive proof and applies it in the system.
references
1.Fiat, Amos; Shamir, Adi (1987). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html