Part 1 of a Series on Polynomial Commitment Schemes for NomosDA

As the demand for scalable and secure blockchains grows, modern blockchains have come to rely on data availability sampling (DAS) to convince clients that block data is intact with minimal data downloading. Polynomial commitment schemes, or PCSs, play a vital role in this process by allowing a prover to commit to a polynomial and later provide proofs that specific evaluations of that polynomial are correct. PCSs are also employed in similar applications, such as Verifiable Information Dispersal, to prove that a data fragment indeed originates from an original piece of data.

In this series, we’ll compare various polynomial commitment schemes, evaluating their strengths and weaknesses in terms of their practicality for data availability solutions, and explain our choice of PCS for the Nomos blockchain project.

Properties of PCSs

A polynomial commitment scheme is a cryptographic protocol that produces a short string known as a commitment based on a given polynomial. This commitment, together with an associated proof also generated by the scheme, can be used by any party to verify the evaluation of the polynomial at the given value without revealing the entire polynomial. Both polynomial commitments and proofs should be relatively easy to create and verify, but difficult to falsify. Compared with simple Merkle trees, their proofs should also be relatively short.

In the context of data availability, PCSs are used to prove that the data points sampled by a verifier are consistent with the entire data, represented by the commitment published by the prover. The polynomial used for the PCS is typically constructed from the original data, interpreted as evaluation points. Only one unique polynomial can be defined by a set of points of length k, so long as its degree is at most k-1. DA solutions often involve the use of erasure codes to expand the original set of points to include more points satisfying the polynomial. So long as at least k points remain intact, the entire data can be reconstructed by interpolating the unique polynomial and filling in the missing evaluation points. This remains true only if it can be provably known that the original polynomial had a degree of at most k-1.

Above that degree, an infinite amount of polynomials will be satisfied by the same set of points and this assurance of the possibility of reconstruction is no longer present. Therefore, besides for the basic functionality mentioned above - that a commitment to a polynomial must be valid and hard to falsify - a PCS should also provide an assurance that the polynomial is of a low degree. If both of these critical features are present, the PCS can be used as a component of DAS - providing clients an assurance that the data is intact with only a few samples taken.

Criteria for Comparison

All of the commitment schemes examined in this series satisfy our basic requirements of providing a commitment to a polynomial with a certain low degree, together with an evaluation proof that can be verified with relative ease. However, they differ in certain key criteria, selected here for their importance for security and applicability to DA implementations. The tradeoffs made by each PCS between these four criteria have served as the primary factor in determining the PCS used for the Nomos project’s DA solution.

Trusted Setup

One of the major principles that has guided the crypto space is the desire to decrease or eliminate trust assumptions. However, some PCSs require a trusted setup phase, which usually involves the use of multi-party computation. This requires users to trust that at least one of the parties involved was honest and got rid of any secrets generated in the process. PCSs that have transparent setups, on the other hand, tend to increase the prover and verifier complexity, causing performance problems.

Post-Quantum Security

With current estimates of high-scale quantum computers being able to break 2048-bit RSA encryption by 2030, the security of many cryptographic protocols used today is at serious risk. This includes the majority of PCSs, although some are post-quantum secure. Some DA solutions have been designed to initially use non-post-quantum secure schemes, with plans to transition to more robust schemes in the future.

Performance

The biggest priority for PCS performance is low verification time, since DA verifiers are expected to operate on minimal hardware as “light nodes”. Any verification time complexity above logarithmic is simply not usable for DA. That said, in the course of our analysis, we determined that prover time is also an important factor for PCSs used in DA. The sizes of proofs and commitments, as well as the time to generate them, also play a role in the analysis.

Ease of Implementation

Some PCSs, especially those based on elliptic curve pairings, require complex mathematical operations that make implementation difficult. Additionally, more popular schemes often have existing libraries and implementations that make using them in production much simpler.

Schemes Evaluated

In the next few parts of this series, we will compare the top schemes that stood out to us based on their applicability to the Nomos project’s DA solution. We reviewed different polynomial commitment schemes, including KZG, IPA, FRI, Hyrax, Sona, Dory, Dark, and Behemoth, to find one that meets our criteria. In this series, we focus on the most popular ones, which are also widely used in the literature. Each scheme will be introduced and explained, and then analyzed based on the criteria mentioned above. These schemes are:

• KZG commitment scheme
• IPA commitment scheme
• FRI-based commitment scheme

Stay tuned as we continue to publish our analyses of these schemes. At the end, we will conclude with the scheme chosen for use by NomosDA, together with an explanation for why it was chosen.