Owner: @Mehmet
In this survey, we summarized polynomial commitment schemes (PCS) that can be used for data availability considering some critical criteria. These can be broadly categorized into four domains: trusted setup, post-quantum security, performance, and ease-to-implement.
Trusted Setup: In decentralized mechanisms, it is aimed to have no central authority. Some polynomial commitment schemes initiate with a "trusted setup" phase while some do not. Though cryptographic protocols ensuring security during this trusted ceremony phase have been defined [1], it remains crucial to guarantee that the private values generated by participants must be deleted. While PCSs without a trusted setup are more desirable in terms of security, they tend to transfer some of the computations to the prover and verifier, thereby causing some performance problems. Inherently, the choice between the trusted and transparent setup brings out a trade-off.
Post-Quantum Security: Analyzing the post-quantum security criterion in the context of data availability paints a nuanced picture. Commitment schemes have two properties: hiding (privacy) and binding (integrity). For data availability, the binding property is required but the hiding property is not needed. Given the coming quantum threat, the binding property remains secure until a high-scale quantum computer arises. Some applications, acknowledging this, initially adopt non-post-quantum secure structures, with plans to transition to more robust schemes in the future [2,3]. Moreover, it is estimated with a high probability that high-scale quantum computers will be operational by 2030 [4,5].
Performance: From a performance perspective, verification time stands out as a heavy feature when considering PCS for data availability. Following verifier time, the size of proof/commitment and the prover time assume importance. Given that verifiers may operate on smaller devices, their time complexity should ideally be constant or, at most, logarithmic. It is concluded that schemes with verifier time above logarithmic are not a good option for data availability.
Ease-to-Implement: Pairing-based elliptic curve operations and unknown group order-based operations demand a complex mathematical operation, making their implementation challenging. In contrast, implementations based purely on hash algorithms tend to be more straightforward. In the application of data availability, the KZG polynomial commitment scheme has been recognized in the literature. The existence of external libraries and extensive prior work moves KZG to the forefront. However, even with KZG's pre-existing code, modifications are often essential during the application phase.
Brief explanations and comparisons of polynomial commitment schemes from these perspectives are articulated in the next section. Additionally, the results obtained (from Vitalik) regarding data availability using different structures are summarized here.
KZG commitments are named after Kate, Zaverucha, and Goldberg, the authors of the work in which they were introduced. It is a Univariate Homomorphic Polynomial Commitment from Pairings and a Trusted Setup. A major benefit of it is that commitments and opening proofs consist of only a constant number of group elements. KZG is widely used in the blockchain space. It will also be integrated into Ethereum’s protocol with Proto-Danksharding (EIP-4844).
Main Paper: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf
Related Papers: https://eprint.iacr.org/2011/587.pdf {Multivariate Type}
Based on: Pairing Group
Setup Mechanism: Trusted Setup
Verifier Time: $\mathcal{O}(1)$
Proof Size: $\mathcal{O}(1)$
Prover Time: $\mathcal{O}(N)$
Post-Quantum Security: Not secure