Introduction

This document describes the cryptographic protocol underlying NomosDA, which is the data availability (DA) solution used by the Nomos blockchain. NomosDA provides an assurance that all data from Nomos zones - referred to as blobs - are accessible and verifiable by every network participant.

This document describes the way that cryptographic processes, specifically polynomial commitments and erasure coding, are used in the three main stages of NomosDA: encoding, dispersal, and sampling.

Mathematical Background

Polynomial Interpolation

Polynomial interpolation is the process of creating a unique polynomial from a set of data. There are two major ways to do this:

Coefficient form: If you have a data set $a_0, a_1,..., a_k$ then it defines a degree $k$ polynomial $f$ in the coefficient form where $f(x)=a_0+a_1x+a_2x^2+...+a_kx^k$

Evaluation form: Let $w$ be a primitive element of the field (i.e. $w^{k+1}=1$). If you have a data set $a_0, a_1,..., a_k$ then it defines the unique polynomial $f$ in the evaluation form where $f(w^i)=a_i$ and the degree of $f$ is less than or equal to $k$.

KZG Polynomial Commitments

The KZG polynomial commitment scheme provides a way to commit to a polynomial and provide a proof for an evaluation of this polynomial. This scheme has 4 steps: setup, polynomial commitment, proof evaluation, and proof verification. The prover does the first three steps and the verifier does the last step, verification.

Setup

Choose a generator $g$ of a pairing-friendly elliptic curve group $G$.
Select the maximum degree $d$ of the polynomials to be committed to.
Choose a secret parameter $\tau$ and compute global parameters $gp=(g,g^{\tau}, g^{\tau^2},\dots, g^{\tau^d}).$ Destroy $\tau$ and release the parameters publicly.

<aside> 💡 The expression $g^{a}$ refers to elliptic curve point addition, i.e. $g^a=[a]*g=g+g+\dots+g$ where $g$ is the generator point of the group $G$. This is known as multiplicative notation.

</aside>

Polynomial Commitment

Given a polynomial $f(x)=\sum_{i=0}^d a_ix^i$, compute the 48 byte commitment of $f$ as follows:

$$ com(f)=g^{f(\tau)}=(g)^{a_0}(g^{\tau})^{a_1}(g^{\tau^2})^{a_2}\cdots(g^{\tau^d})^{a_d} $$