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

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) KZG10 Commitment: based on pairing group

(2) IPA Commitment: based on discrete log group

(3) FRI Commitment: based on hash function

(4) DARKS Commitment: based on 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.