The conclusion of a Series on Polynomial Commitment Schemes for NomosDA. Read Part 1 here, Part 2 here, Part 3 here, and Part 4 here.

While designing the Nomos blockchain’s tailor-made data availability solution, known as NomosDA, our research team had to make a decision as to which polynomial commitment scheme (PCS) NomosDA would use. To this end, we analysed a variety of PCSs, evaluating each one based on our four main criteria: setup mechanism, post-quantum security, performance, and ease of implementation. Three of these schemes were described in depth in the previous installments of this series. Ultimately, the team decided on the KZG scheme as the PCS of choice for NomosDA, for reasons that will be explained in this conclusion to the NomosDA PCS article series.

Summary of Analysis

In total, we analysed nine different schemes for use in NomosDA. The three main candidates (KZG, IPAs, and FRI-based) were discussed in previous articles on this blog. The remainder will be briefly discussed below.

The Hyrax Family of Schemes

Hyrax Commitment Scheme

Hyrax was introduced in a 2017 paper as a zkSNARK, and its protocol includes a commitment scheme for multilinear polynomials. The PCS used in Hyrax (henceforth Hyrax-commit) combines matrix commitments with inner product arguments to yield a scheme with attractive prover costs and a transparent setup.

Paraphrasing Setty, Thaler, and Wahby (2023), Hyrax-commit’s performance can be summarised as follows:

To commit to an \(\ell\)-variate multilinear polynomial that has \(N = 2^{\ell}\) coefficients, the prover performs \(\sqrt{N}\) multi-exponentiations - each of length \(\sqrt{N}\). To compute an evaluation proof, the prover performs \(\mathcal{O}(N)\) field operations and \(\sqrt{N}\) exponentiations by applying Bulletproofs to prove an inner product instance consisting of length \(\sqrt{N}\) vectors. This process results in an evaluation proof consisting of \(\mathcal{O}(\log N)\) group elements.

The downside of Hyrax-commit is that the verification costs are large: commitments consist of \(\sqrt{N}\) group elements, and to verify an evaluation proof, the verifier has to perform two multi-exponentiations of size \(\sqrt{N}\). Hyrax-commit, as well as the other schemes derived from it, is also not post-quantum secure.

Dory Commitment Scheme

Dory was introduced in a 2020 paper as an improvement of the Hyrax-commit scheme. It can be thought of as reducing the Hyrax verifier’s costs from \(\mathcal{O}(\sqrt{N})\) to \(\mathcal{O}(\log N)\). However, this improvement comes at the cost of requiring the use of elliptic curve pairings. Dory also requires the verifier to perform a logarithmic number of operations in the target group of a pairing-friendly group.

Sona Commitment Scheme

The above-mentioned 2023 paper by Setty, Thaler, and Wahby improved on Hyrax-commit by creating Sona. Sona combines the commitment time of Hyrax and evaluation proof computation involving sublinear cryptographic work, with the lower verification costs of Nova. This makes it the most attractive of the Hyrax family of commitment schemes. Unfortunately, implementations of the Sona scheme available at the time of writing are limited or optimised for specific purposes, which means that NomosDA would require a custom implementation of this scheme.

DARK Commitment Scheme

Diophantine ARgument of Knowledge (DARK) is a polynomial commitment scheme introduced in a 2019 paper. It is intended for univariate and multivariate polynomials over finite fields, with logarithmic size evaluation proofs and verification time, measured in the number of coefficients of the polynomial. The underlying technique involves leveraging integer representations of polynomials and groups of unknown order. DARK has a transparent setup and is not post-quantum secure.

Behemoth Commitment Scheme

Behemoth is a constant-size polynomial commitment scheme introduced in a 2023 paper. It has constant-size opening proofs and a constant-time verifier, as well as a transparent setup. The disadvantage of Behemoth is that it employs a cubic prover in the degree of the committed polynomial and is not post-quantum secure. There is no implementation at the time of writing.

Lattice-Based Schemes

In recent years, polynomial commitment schemes based on algebraic lattices have been introduced, often conceptualised as operating on polynomials over power-of-two cyclotomic rings which are transformed into polynomials over finite fields. Their major advantage consists of their post-quantum security. However, even recent lattice-based PCSs such as SLAP (2023) feature long concrete proof sizes and proof and verification times due to the logarithmic cost of cyclotomic ring operations. Additionally, many of these schemes use a trusted setup or rely on new security assumptions that have not been sufficiently tested.

A new lattice-based PCS known as Greyhound has been proposed in a freshly-published 2024 paper. It claims to have excellent performance, with \(\mathcal{O}(\sqrt{N})\) verification time and concrete proof sizes \(10^4\) times smaller than those of SLAP, all while using a transparent setup, being post-quantum secure, and relying on standard lattice security assumptions. Because it is so new, our team has not yet been able to fully investigate this option.

Comparison Table

Our findings for the schemes we surveyed are summarised in the table below, based on the four criteria we evaluated.

* These times and sizes are with respect to the cyclotomic ring operations, each of which is actually \(\log N\) with respect to the degree of the polynomial.

Why We Chose KZG

Based on the criteria mentioned throughout the series, our choice of KZG for NomosDA may seem strange. After all, it is the only scheme surveyed that requires a trusted setup, and is one of only two that rely on complex elliptic curve pairing operations. As a result, it’s not even post-quantum secure! While all that is true, it is important to understand that some of our criteria are more important than others. Evaluating the relative weight of each criterion will clear up the reasons behind our decision.

Setup Mechanism

While a trusted setup involves some trust assumptions (as the name implies), this is not nearly as big an issue as it may appear at first glance. For KZG, this setup generates the public elliptic curve points, known as the powers of tau, that are calculated based on a secret value \(\tau\). Due to the properties of the multiparty computation (MPC) process used to generate these points, the setup will be secure even if only one participant is honest. Therefore, using a trusted setup with a large amount of participants will make it extremely unlikely for the scheme to be compromised. This likelihood can also be improved by using powers of tau generated by a third-party’s MPC process, such as Ethereum’s KZG Summoning Ceremony, and adding our own contributions to it. In practice, a trusted setup mechanism with such a large and diverse group of contributors will not be any less secure than a scheme with a transparent setup.

Ease of Implementation

The relative ease of implementing a particular scheme played a major factor in our decision. However, evaluating schemes based on the ease of implementing their mathematical building blocks from scratch is not entirely accurate, as many schemes already have open-source implementations ready for us to use - or needing only minor modifications. This is particularly true in the case of KZG, which, due to its popularity, has many robust implementations despite its theoretically complex basis. These implementations give KZG a major edge over many of the other schemes surveyed, some of which had few or no implementations available and would require the team to implement them from the ground up or make major modifications.

Performance

The most important criterion for our decision was the performance of each scheme. Any unnecessary delay in the time spent creating or verifying proofs increases the time it takes for validators to attest to the availability of the data. Additionally, a larger proof size requires greater bandwidth and increases the cost of data availability sampling. Proof size in particular was determined by our team to be the most critical of the performance criteria.

Some schemes, such as IPAs, had qualities that made them especially unsuitable for use in data availability sampling. Other schemes, such as the Hyrax family and Lattice-based schemes, had very inefficient performance in at least one area. Some schemes, like FRI and DARK, had reasonable verification times and proof sizes. However, with constant verification time and proof size, as well as linear proof time, no other PCS comes close to KZG. Vitalik Buterin reached a similar conclusion in support of Ethereum’s use of KZG in their Danksharding data availability solution.

Post-Quantum Security

One final area that needs addressing is the issue of post-quantum security. A recently-published draft paper from the National Institute of Standards and Technology (NIST) predicts an imminent threat to quantum-vulnerable cryptographic standards from rapidly improving quantum computing technology. In particular, the authors suggest replacing elliptic curve cryptography, upon which KZG is based, by 2035. With this looming vulnerability on the horizon, choosing anything but a FRI-based or Lattice-based scheme may seem short-sighted.

However, there are some nuances to our specific use case that should not be missed. For data availability sampling, unlike many other applications of polynomial commitment schemes, privacy is not strictly necessary. In NomosDA, the PCS is used to verify that some data chunk sent by an executor matches the data they committed to earlier - that is, for the PCS’s binding property. The hiding property, that a verifier cannot read the rest of the committed data, is not relevant for our application. Intuitively, the goal of data availability sampling is to reduce the information burden on validator nodes, not to hide information from them. Commitment schemes used for privacy could become vulnerable to “store now, decrypt later” attacks, where the attacker will store commitment values now and break them with a quantum computer 10 years down the line to reveal information. In the case of NomosDA, such an attacker would not gain anything, since that data’s usage period will have already expired.

Another thing to keep in mind is that the NomosDA solution is not tied to any particular scheme. Our implementation will work the same whether it is implemented with KZG, FRI, or some other scheme. This quality opens up the possibility of switching PCSs further down the line. Rather than committing to KZG forever, NomosDA can be updated to use FRI or some other scheme whenever quantum computing breaks KZG.

In short, since we can always change which PCS NomosDA uses, and there is no issue of breaking the privacy of previous KZG blob commitments, we have decided to use KZG for its exceptional performance until the time that it becomes obsolete.

Conclusion

A major tension in our analysis above can be described briefly as “theory” vs “reality”. While there may be some schemes with better qualities “on paper” (such as transparent setup), the priorities of the Nomos research team have been to choose a PCS that would best enable a viable data availability solution. From this angle, KZG’s major advantages in performance metrics, as well as the plethora of existing implementations, make it a clear winner for use in NomosDA. That said, the choice is not final - as long the world of cryptographic research continues inventing new and better polynomial commitment schemes, NomosDA may be updated to use the most cutting edge technology with the best qualities for our use case.

Sources and Further Reading

• Doubly-efficient zkSNARKs without trusted setup (2017)
• Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments (2020)
• Unlocking the lookup singularity with Lasso (2023)
• Transparent SNARKs from DARK Compilers (2019)
• Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time (2023)
• Vitalik Buterin - Proto-Danksharding FAQ
• Transition to Post-Quantum Cryptography Standards (2024)
• SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions (2023)
• Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency (2023)
• Greyhound: Fast Polynomial Commitments from Lattices (2024)