Univariate Polynomial Commitments

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } /* a, .open-files-container li.selected a { color: #5EB7E0; } */ </style> ![](https://i.imgur.com/MQdIp9i.png) Univarite polynomials are functions of the form $f(x) = a_0 x^0+a_1 x^1 + a_2 x^2+ ... + a_n x^n$ with a single scalar input (univariate) $x$ and a scalar output. Coefficients $f_a = [a_0, a_1, ..., a_n]$ of a univariate polynomial $f$ of maximal *degree* $n$ ($a_n=0$ etc. must be considered, hence *maximal* qualifier) uniquely identifies it and differentiates it from other univariate polynomials of maximal degree $n$. On the other hand, this is not the only way to identify and represent a polynomial of maximal degree $n$. Knowing the evaluation of the polynomial at *any* $n+1$ unique points, also identifies and represents such a polynomial, i.e. given a unique set of points $\bar{x} = [x_0, x_1, x_2, ..., x_n]$, $f_\bar{x} = [(x_0, f(x_0)), (x_1, f(x_1)), (x_2, f(x_2)), ..., (x_n, f(x_n))]$ is a representation that identifies $f$ among all such polynomials as well. Mapping this representation $f_\bar{x}$ to the polynomial $f(x)$ is accomplished through [*Lagrange interpolation*](https://en.wikipedia.org/wiki/Lagrange_polynomial). \begin{align} f(x) &= \sum_{i=1}^{n} l_{x_i}(x)f(x_i) \hspace{0.3in} (\text{Green in the figure below.})\\ l_{x_i}(x) &= \prod_{j=0, j\neq i}^{n} \frac{x-x_j}{x_i-x_j} \hspace{0.3in} (\text{Blue/animated in the figure.}) \end{align} ![](https://i.imgur.com/co66LLF.gif) The goal of this chapter is to discuss commitments to univariate polynomials. An obvious question that follows is, since we can represent a polynomial $f$ as the coefficient vector $f_a$ or the evaluation vector $f_\bar{x}$ of length $n+1$, can we not simply commit to these representation vectors and be done? Are vector commitment schemes *equivalent* to univariate polynomial commitment schemes? Vector commitment schemes are *not* equivalent to polynomial commitment schemes. Even though polynomials can be represented by these fixed length vectors, a polynomial commitment scheme in our classification requires the *ability to open/reveal* evaluations of the polynomial at random points *without revealing the entire polynomial* (hiding property), which is not possible when we commit directly to these vector represenations instead and open them through the vector commitment scheme. Evaluating a polynomial at distinct random points as many times as the degree of the polynomial could in principle reveal the entire polynomial (this would require knowing the maximal degree first). However, single point evaluations should reveal minimal information for the commitment scheme to be classified a polynomial commitment. In other words, if we commit to $f_a$ or $f_\bar{x}$ using a vector commitment scheme, and wish to create an opening for a random point $x^+$ (not in $\bar{x}$) and validate its evaluation candidate $f^*_{x^+} = f(x^+)$ to the public, we cannot do so without revealing the entire set of coefficients of the polynomial. This is due to the fact that a vector commitment scheme is designed only for accommodating partial openings of the vector and therefore it can partially open a coefficient (or an evaluation at a point in $\bar{x}$) but not the evaluation of the polynomial at a random point. However, as we will see later in our reduction of polynomial commitment schemes to vector commitment schemes, any polynomial commitment can simulate a vector commitment, as we can simply commit to a polynomial with the desired vector $m$ as the evaluations of the polynomial at some unique set of $n+1$ points $\bar{x}$, i.e. by committing to the polynomial represented by $f_\bar{x}=m$, using Lagrange interpolation first to obtain $f$ from $f_\bar{x}$. Next we discuss some of the methods designed to commit to a polynomial $f$ directly and not just to a vector representation of $f$ such as $f_a$ and $f_\bar{x}$. --- A polynomial commitment using groups of known order -- DL --- The first polynomial commitment scheme we present is based on encryption with groups of known order (discrete logarithm). It is a very inefficient scheme as it produces a very large digest of size $\mathrm{O}(n_\text{max})$, where the maximal degree of the polynomials the scheme can handle is $n_\text{max}$. As it looks similar to vector commitments we are familiar with from the last chapter in some ways, we begin our discussion with this scheme. Given a polynomial $f(x) = a_0 x^0+a_1 x^1 + a_2 x^2+ ... + a_n x^n$ with coefficient vector $m = [a_0, a_1, ..., a_n]$, which we will refer to as the message for consistency, the following are the algorithms of the scheme that commits to $f$. - As usual with groups of known order, the setup algorithm outputs the group generator, and its order, based on some security parameters $s$, such as the size of the group to be used, $\Phi(s)=\rho=(p,g)$. - The commitment algorithm creates a group encrpyted version of each individual coefficient after right-padding $m$ with $(n_\text{max}-n)$ zeros, and publishes it as the digest $C(\rho, m) = d = [g^{a_0}, g^{a_1}, ... ,g^{a_n}, g^{0}=g^{p}=1, 1, ..., 1]$. As we can see, this is a digest in name only, as its length is $n_\text{max}+1$. However, despite being public, it hides the coefficients (though not the maximal order $n$) as long as the DL problem is hard in $G$. - The opening algorithm outputs an empty proof for any random evaluation point $i(m) = f(i)$, $O(\rho, m, i) = \pi_i = ()$. - The verification algorithm aims to verify whether a candidate evaluation of the polynomial at point $i$, $m_i^*$, is correct, i.e. $f(i)=m_i^*$. This is accomplished, without needing to reveal the coefficients of the polynomial, through a key idea, *additive homomorphism* within the group encryption. Instead of checking that the evaluation $f(i)$ is equal to the candidate $m_i^*$ directly, the verification algorithm checks that the encrypted version of the evaluation $g^{f(i)}$ is equal to the encrypted version of the candidate, i.e. $V(\rho, d, i, \pi_i, m_i^*) = (g^{m_i^*} \stackrel{?}{=} g^{f(i)} = g^{\sum_{j=0}^{n_\text{max}} a_j \cdot i^j} =\prod_{j=0}^{n_\text{max}} (g^{a_j})^{i^j})$. Since the elements of the digest are given as $d_j= g^{a_j}$, we can rewrite the verification algorithm as $V(\rho, d, i, \pi_i, m_i^*) = (g^{m_i^*} \stackrel{?}{=} \prod_{j=0}^{n_\text{max}} d_j^{i^j})$. --- **Efficiency**: The space/communication complexity of the digest $d$ is $n_\text{max}$ group elements (whose size depends on the group size and representation) and the opening proofs are empty. The complexity of the commitment algorithm is $\mathrm{O}(n_\text{max} \log (\max_j a_j \mod p)))$ group operations in $G$, using fast exponentiation such as the square & multiply algorithm. The opening algorithm has no cost as it does nothing. The complexity of the verification algorithm is $\mathrm{O}(n_\text{max} + \log (\max_j i^j \mod p))$ group operations in $G$, using fast exponentiation. The scheme does not require a trusted-setup algorithm. --- Kate Polynomial Commitments --- Next, we discuss Kate commitments, a polynomial commitment scheme with many real world applications. Similar to the scheme above, it relies on a group of known order (an elliptic curve is used) and DL assumptions, but in addition, it also requires the group to be *pairing*-compatible (as it uses a [pairing](https://en.wikipedia.org/wiki/Pairing-based_cryptography) in its verification algorithm) and requires a trusted-setup. We will assume some knowledge of pairings in this discussion. These additional requirements results in significant improvements to the space efficiency of the scheme, i.e. both the digest and the opening proof for any point is of constant size. For example, this makes Kate scheme the ideal candidate to be used for Verkle tree node level vector commitments after the reduction. There are many other places, such as zero-knowledge proofs and zk-SNARKs, where Kate commitments come up as an important tool. Let us give the formal definitions of the algorithms of the scheme as usual. We will again assume that the maximum order the scheme can handle is $n_\text{max}$. - As usual with groups of known order, the setup algorithm outputs the generator $g$, and its order $p$, based on some security parameters $s$, such as the size of the group to be used. The group is a pairing-compatible elliptic curve, i.e. from a special class of cyclic groups that have nice security/efficiency properties that comes equipped with a symmetric bilinear pairing function $h: G\times G \rightarrow G$. Then, a private key $k_{\text{priv}}$ is generated, by chosing it uniformly randomly from the set $\{2, ..., p-1\}$. Then $k = [g = g^{k_{\text{priv}}^{0}} = g^{k_{\text{priv}}^{p-1}}, g^{k_{\text{priv}}^1}, g^{k_{\text{priv}}^2}, ..., g^{k_{\text{priv}}^{n_\text{max}}}]$ is generated as the public key, whereupon the private key is completely discarded as toxic waste (it is imperative the private key is unknown to all parties). The public setup parameters are then $\rho =(p, g, h, k)$. - The commitment algorithm generates the digest for a polynomial $f$ with coefficient vector $m = [a_0, a_1, ..., a_n]$ by combining the elements of the public key $k$ as $C(\rho, m) = d = \prod_{j=0}^n (k_j)^{a_j} = \prod_{j=0}^n (g^{k_{\text{priv}}^{j}})^{a_j} = \prod_{j=0}^n g^{a_j k_{\text{priv}}^{j}}= g^{\sum_{j=0}^n a_j k_{\text{priv}}^{j}} = g^{f(k_{\text{priv}})}$. The product of the public key elements raised to the coefficients of the polynomial, $(k_j)^{a_j}$, results in a group encrypted version of the evalution of the polynomial at the unknown private key, $f(k_{\text{priv}})$. The idea of *additive homomorphism* within the group encryption is moved from the verification algorithm to the commitment algorithm in this scheme. The opening and the verification algorithms depends on the following algebraic property of polynomials: Given a polynomial $f(x)$ of maximal degree $n$, for any $z$ in the domain of $f$, we can shift the polynomial vertically, $f_z(x) = f(x)-f(z)$, such that this new polynomial has a root (passes through zero) at $z$, which means that $(x-z)$ is a perfect divisor/factor of $f_z$. The quotient polynomial $\psi_z(x)=\frac{f_z(x)}{x-z} = \sum_{j=0}^{n-1} b_j x^j$ has a maximal degree of $n-1$ with coefficients $[b_0, b_1, ..., b_{n-1}]$. A noteworthy relation to keep in mind is $f(x) = \psi_z(x)(x-z) + f(z)$. - The opening algorithm operates very similar to the commitment algorithm. Given any random evaluation point $i(m) = f(i)$, the opening proof $\pi_i$ is a product of the public key elements raised to the coefficients of the *quotient polynomial for point $i$* $\psi_i(x)=\frac{f_i(x)}{x-i} = \sum_{j=0}^{n-1} b_j x^j$, with coefficients $[b_0, b_1, ..., b_{n-1}]$. This corresponds to $O(\rho, m, i) = \pi_i = \prod_{j=0}^{n-1} (k_j)^{b_j} = \prod_{j=0}^{n-1} g^{{b_j}k_{\text{priv}}^{j}} = g^{\sum_{i=0}^{n-1} {b_i}k_{\text{priv}}^{i}} = g^{\psi_i(k_{\text{priv}})}$. Note that this is equivalent to the group encrypted version of the evaluation of the quotient polynomial $\psi_i$ at the unknown private key $k_{\text{priv}}$, calculated using the public key. As usual, the opening proof for $i$ encapsulates key information pertaining the polynomial $f$ that cannot be gleaned from $f(i)$ itself in a succinct manner. The verification algorithm is the most intricate part of this scheme, where pairing of the group $h$ becomes important. Since $f(x) = \psi_i(x)(x-i) + f(i)$ for any $x$ and $i$, we know that $f(k_{\text{priv}}) = \psi_i(k_{\text{priv}})(k_{\text{priv}}-i) + f(i)$, which is equivalent to $\log_g d = (\log_g \pi_i) (k_{\text{priv}}-i) + f(i)$, can be used to check whether a digest $d$, an opening proof $\pi_i$ and an evaluation candidate for $f(i)$ fit together. This is easier said then done however, as it requires both solving the discrete logarithm problem for the group, as well as utilizing the unknown private key $k_{\text{priv}}$. Let us first see what happens when we group encrypt both sides of the equation, $g^{\log_g d} = g^{(\log_g \pi_i) (k_{\text{priv}}-i) + f(i)}$, which can be simplified as $d=\pi_i^{(k_{\text{priv}}-i)}g^{f(i)}$ (which requires knowing $k_{\text{priv}}$ to be useful) or $d=(k_1 g^{p-i})^{\log_g \pi_i}g^{f(i)}$ (which requires solving DL to be useful). As we can see, dealing with group encrypted version of things does not help much in this case. $g^{(\log_g \pi_i) (k_{\text{priv}}-i)}$ is the real problematic term and this is where pairings come into play to break this exponent to an expression involving $g^{(\log_g \pi_i)}=\pi_i$ and $g^{(k_{\text{priv}}-i)}=k_1 g^{p-i}$ separately. Among other properties, pairings are functions that have the property, $h(g, g)^{ab} = h(g^a, g^b)$. We can use this property to split up the problematic expression, by considering $h(g,g)^{(\log_g \pi_i) (k_{\text{priv}}-i)}$ instead of $g^{(\log_g \pi_i) (k_{\text{priv}}-i)}$. Clearly, this expression can be written as $h(g,g)^{(\log_g \pi_i) (k_{\text{priv}}-i)} = h(g^{(\log_g \pi_i)},g^{ (k_{\text{priv}}-i)})= h(\pi_i,k_1 g^{(p-i)})$ using the property given. So, instead of looking at the group encrpyted version of the relationship between $d$, $\pi_i$ and $f(i)$, let us consider the pairing encrpyted version, which simplifies more favorably. \begin{align} h(g,g)^{\log_g d} &= h(g,g)^{(\log_g \pi_i) (k_{\text{priv}}-i) + f(i)}\\ h(g^{\log_g d},g) &= h(g^{(\log_g \pi_i)},g^{(k_{\text{priv}}-i)}) h(g,g)^{f(i)}\\ h(d,g) &= h(\pi_i,k_1 g^{(p-i)}) h(g^{f(i)},g) \end{align}This final simplification does not require knowledge of the private key $k_{\text{priv}}$ nor the ability to solve the DL problem in $G$. It only requires efficient evaluation of the pairing function $h$, along with regular group operations. Therefore, Kate commitment scheme uses the pairing $h$ in its validation algorithm with this final expression. Let us define the validation algorithm formally as well. - The verification algorithm aims to verify whether a candidate evaluation of the polynomial at point $i$, $m_i^*$, is correct, i.e. $f(i)=m_i^*$. It checks the above simplified relationship $V(\rho, d, i, \pi_i, m_i^*) = (h(d,g) \stackrel{?}{=} h(\pi_i,k_1 g^{(p-i)}) h(g^{m_i^*},g))$. --- **Efficiency**: The space/communication complexity of the digest $d$ and the opening proof for any evaluation point $\pi_i$ is a single group element (whose size depends on the group size and representation). The complexity of the commitment algorithm is $\mathrm{O}(n + \log (\max_j a_j \mod p))$ group operations in $G$, using fast exponentiation such as the square & multiply algorithm. The opening algorithm is similar, $\mathrm{O}(n-1 + \log (\max_j b_j \mod p))$. The complexity of the verification algorithm is $\mathrm{O}(\log (\max(m_i^*, p-i) \mod p))$ group operations in $G$ using fast exponentiation, plus a constant number of evaluations of the pairing function. The scheme requires a trusted-setup algorithm. Getting rid of the private key as toxic waste is imperative and usually requires a cumbersome public ceremony of sorts. --- Reduction to vector commitments --- Given a univariate polynomial commitment $(\Phi^+, C^+, O^+, V^+)$, it is straightforward to simulate a vector commitment $(\Phi, C, O, V)$ through the following reduction: - The setup algorithm is the same, i.e. $\Phi(s)= \Phi^+(s) = \rho$. - The commitment algorithm creates a digest for a vector message $m=[m_1, m_2, ..., m_n]$ by creating a polynomial whose evaluation vector representation is $f_\bar{x} = [(0, 0), (1, m_1), (2, m_2), ..., (n, m_n)]$, which can be obtained in function form as $f(x)$ through Lagrange interpolation. Then this polynomial $f(x)$ is committed to using $C^+$, $C(\rho, m) = C^+(\rho, f) = d$. - The opening algorithm $O$ for the $i$ element of the vector $i(m) = m_i$ creates the opening proof for the evaluation of the polynomial at point $i$ with $O^+$, $O(\rho, m, i) = O^+(\rho, f, i)= \pi_i$. - The verification algorithm for a candidate message $m_i^*$ is simulated as $V(\rho, d, i, \pi_i, m_i^*) = V^+(\rho, d, i, \pi_i, m_i^*)$ without any changes. The simple idea is to wrap the vector message $m$ as a polynomial passing through the values of the vector at the index points and using the polynomial commitment algorithms to simulate the vector commitment by committing to that polynomial. The polynomial used is unique as it is created through Lagrange interpolation, which creates the lowest degree unique polynomial passing though those points. --- Remarks --- In the next chapter, we discuss multilinear polynomial commitment schemes, which are commitments to polynomials with multiple inputs where each term in the polynomial is linear w.r.t. each individual input variable. This is a more restricted class of multivariate polynomials, which normally would accommodate every term in the polynomial to be nonlinear in each input variable.  [Intro: A Hierarchical View of Cryptographic Commitment Schemes](/@kullervo/commitmentHierarchy) [Previous: Vector Commitments](/@kullervo/commitmentVector) [Next: Multilinear Polynomial Commitments](/@kullervo/commitmentMultilinearPoly)