When learning Zero-Knowledge Proof (ZKP) algorithms, one will always encounter cryptographic primitives - Polynomial Commitment (PC). First, let's look at the definition of commitment. A commitment is a public value that is bound with the original message (computation binding) provided by a committer who will not reveal the message (hiding). The committer needs to open this commitment and send the message to the verifier to verify the correspondence between the commitment and the message. A PC can be regarded as a commitment to a certain polynomial P, and the committer can prove that the value of the polynomial at a certain point z satisfies P(z) = a through a proof without revealing the polynomial P. There are multiple schemes to implement PC: (1) Commitment: based on pairing group KZG10 (2) Commitment: based on discrete log group IPA (3) Commitment: based on hash function FRI (4) Commitment: based on DARKS unknown order group … This article will compare the differences between the above polynomial schemes from different perspectives. Note: Specific principles of each scheme will not be elaborated on in this article. Table 1 shows the computation forms of common PCs. In different ZKP algorithms, algorithms are different precisely because different PC schemes are applied. The following figure shows the corresponding relationship between ZKP algorithms and the above PC schemes: Different PC schemes result in different ZKP algorithms with different properties, efficiency, and security. For example, the FRI-based ZK-STARKs algorithm is quantum-resistant and does not require any trusted setups because it relies on few mathematical security assumptions. Furthermore, for the DARK-based Supersonic algorithm, if the unknown order group is RSA Group, it will require trusted setups because it relies on Integer Factorization Problem (IFP) assumptions; if the unknown order group is a Class Group, it does not require trusted setups because it relies on the difficulty of computing the number of Class Group elements. The following table lists the advantages and disadvantages of each PC. Among them, green, yellow, and red correspond to excellent, medium, and average respectively. In the ZKP algorithm, succinct generally represents: prove succinct, verify succinct, and communication succinct. Therefore, in the second row of the above table, I've marked the pros and cons of each algorithm according to the differences in the above three indicators. Next, let's take a look at the performance indicators corresponding to each PC. The color identification is consistent with the above. From the table, it can be concluded that KZG is the best scheme in terms of succinctness, because its proof size and verification time are both constant, which means that the size increase of the circuit will not cause an increase in the proof size. For other PC schemes, the proof size is related to the circuit scale, which means that the proof size will increase with the increase of the circuit scale. However, in terms of security, the KZG scheme is weaker compared with other schemes, for it requires a third-party trusted setup (see Table 1). This article analyzed several mainstream PC schemes from different perspectives. However, in the actual production and application process, the project party needs to make a comprehensive assessment of its application scenarios. Higher security or better efficiency has always been a trade-off. Hopefully through the above introduction, you can have a more comprehensive understanding of these mainstream PC schemes, and then choose the most suitable PC scheme in the actual application process. Note: This is an article co-written by Sin7Y and ZKSwap.

Yellow

Plookup with zkEVM: A Brief Introduction to How zkEVM Works

Zendoo Protocol: A Deep Dive

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Too Long; Didn't Read

KZG10, IPA, FRI, and DARKS: Analysis Of Polynomial Commitment Schemes

KZG10, IPA, FRI, and DARKS: Analysis Of Polynomial Commitment Schemes

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Study on Parallel Execution: Everything You Need to Know

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

A Study on Parallel Execution: Everything You Need to Know

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps