DekartProof: Efficient Vector Range Proofs and Their Applications

A zero-knowledge range proof allows one party to convince another party that a secret value (or a batch of vaues) lies within a given range — such as being non-negative or below a certain bound — without revealing anything else about the value itself. These proofs are used directly in various applications, including (sometimes auditable) confidential transactions (to verify non-negative transaction amounts) [CFT98, BAZB20, CB21], digital identity schemes (to prove that a secret credential attribute, e.g. age, falls in a specific range), election protocols (to prove that all the ciphertexts on the ballot are encryptions of zero or one) [CGS97] and auditing [DBBCB15] (to prove that all committed balances lie in a certain range, so their sum doesn’t overflow). More generally, they form a core building block in modern cryptography by proving that ciphertexts are well-formed, underpinning systems including publicly verifiable secret sharing [Gro21, Chunky], ring learning with errors [PLS19, Lib24], privacy preserving federated learning [BGL+23], private auctions [LAN02] and Certificate Transparency [EMBB17].

In this post we describe an implementation of a zero-knowledge proof system based on the abstract approach presented in this paper.

Technical Overview

The starting point is Borgeaud’s range proof [Bor20] for a single secret value $z$. In this construction, $z$ is encoded as the constant term of a blinded univariate polynomial $f$, meaning $f(X) = z + rX$ for some random value $r$, which is then committed using a homomorphic commitment scheme. To prove to the verifier that $ z $ lies in the range $[0,2^\ell)$, Borgeaud’s prover commits to $\ell$ blinded univariate polynomials $f_1 ,\ldots, f_\ell$ such that each $f_j$ similarly encodes the $j$-th bit of $z$ in its constant term. The prover then uses standard techniques to prove that $f_j(X) \bigl(1 - f_j(X)\bigr)$ vanishes at the point $0$, which confirms that the $f_j$’s encode bits in their constant terms, and uses the homomorphic property of the commitment scheme to prove that the encoded bits form the bit decomposition of $z$.

$\mathsf{DekartProof}$ introduces a natural batching approach, which can be described as follows. Given secret values $z_1,\ldots,z_n$, the protocol starts with a commitment to a polynomial $f$ evaluating to these values on some evaluation domain. To make sure it can later do an opening (outside of this domain) without leaking information, a random mask $\beta$ is added as an evaluation point if it doesn’t already have one. As a result, on a slightly extended domain, the polynomial evaluates to $(\beta, z_1,\ldots, z_n)$.

Next, for each $1\leq j \leq \ell$, the prover constructs the tuple $(\beta_j, z_{1,j},\ldots, z_{n,j})$, where $\beta_j$ is a mask (possibly subject to mild conditions, discussed below) and each $z_{i,j}$ is defined to be the $j$-th bit of the secret value $z_i$, and commits to the corresponding polynomial $f_j$.

Letting $S$ denote the evaluation domain corresponding to the $z_i$’s, the prover then needs to show the following:

1. For each $j \in \{1,\ldots, \ell \}$, the polynomial $f_j (1 - f_j)$ vanishes on $S$.
2. The polynomial $f - \sum_{j = 1}^\ell 2^{j-1} f_j$ vanishes on $S$.

Using a challenge from the verifier, some (or all) of these checks can be batched into one check.

Univariate $\mathsf{DekartProof}$

For the moment, we stay within the realm of univariate polynomials. Letting $Z_S(X)$ denote the zero polynomial corresponding to the set $S$ of evaluation points of the $z_i$’s, these two checks become:

1. For each $j \in \{1,\ldots, \ell \}$, $Z_S(X)$ divides the univariate polynomial $f_j (1 - f_j)$.
2. $Z_S(X)$ divides the univariate polynomial $f - \sum_{j = 1}^\ell 2^{j-1} f_j$.

Applying the Schwartz–Zippel lemma, it suffices to show that given a challenge $c$,

• $Z_S(X)$ divides the univariate polynomial $g \mathrel{\vcenter{:}}= f - \sum_{j = 1}^\ell 2^{j-1} f_j + \sum_{j = 1}^\ell c^j f_j (1 - f_j) $.

In practice, executing this strategy involves explicitly computing (the evaluations on $S$ of) the quotient polynomial, and committing to it. This requires interpolating points, so if $n$ is large it involves computing FFTs over an evaluation domain consisting of roots of unity, incurring an $\mathcal{O}(n \log n)$ cost, making this approach relatively expensive to the prover.¹

This scheme was further developed here. Notably, the proof size depends on $\ell$ but is independent of $n$.

Multivariate $\mathsf{DekartProof}$

Instead, the paper switches to a multivariate setting, which avoids the need for FFTs. Here, we can use the multivariate sumcheck approach of Spartan [Spa20] to prove that a multivariate polynomial is zero on the hypercube; this protocol is efficient but will require an opening proof for this polynomial at a challenge point $\mathbf{x}$. Letting $\mathbf{0}$ denote the point of the hypercube corresponding to the masks, and $Z_\mathbf{0}$ denote the multilinear polynomial which evaluates to $0$ at the point $\mathbf{0}$ and evaluates to $1$ at all other points in the hypercube,² it would then suffice to show:

1. For each $j \in \{1,\ldots, \ell \}$, the multivariate polynomial $f_j (1 - f_j) Z_\mathbf{0}$ vanishes on the hypercube.
2. The multivariate polynomial $(f - \sum_{j = 1}^\ell 2^{j-1} f_j ) Z_\mathbf{0}$ vanishes on the hypercube.

We now describe two (very similar) approaches:

• Execute the sumcheck zerocheck protocol with batched input $g \mathrel{\vcenter{:}}= \bigl( f - \sum_{j = 1}^\ell 2^{j-1} f_j + \sum_{j = 1}^\ell c^j f_j (1 - f_j) \bigr) Z_\mathbf{0}$. To obtain the evaluation of $g$ at a challenge point $\mathbf{x}$, do a batch opening of $f$ and the $f_j$’s at $\mathbf{x}$, then use this explicit formula for $g$ in terms of $f$ and the $f_j$’s to obtain the value of $g$ at $\mathbf{x}$.

• Execute the sumcheck zerocheck protocol with batched input $g \mathrel{\vcenter{:}}= \bigl( \sum_{j = 1}^\ell c^{j - 1} f_j (1 - f_j) \bigr) Z_\mathbf{0}$. Again do a batch opening of $f$ and the $f_j$’s at $\mathbf{x}$, then use the evaluations of the $f_j$’s to compute the value of $g$ at $\mathbf{x}$; this settles (1). If the masks were constructed to be “correlated”, namely to satisfy $\beta = \sum_{j = 1}^\ell 2^{j-1} \beta_j$, then the polynomial $f - \sum_{j = 1}^\ell 2^{j-1} f_j$ is zero which can be proven (again from Schwartz–Zippel) by comparing the evaluations at $\mathbf{x}$, settling (2). Intuitively, because $f$ is precisely the weighted sum of these polynomials, its evaluation reveals nothing new so it doesn’t matter that its mask wasn’t independent.

Note that in the first approach, the polynomial $f - \sum_{j = 1}^\ell 2^{j-1} f_j$ is already zero on the hypercube, except at $\mathbf{0}$. Thus it seems that the difference between the two approaches is moving a weighted size $\ell+1$ summation in the input field between the prover and verifier, and in practice the computational cost of such a computation is going to completely negligible. For simplicity (and because the aim is generally to shift cost away from the verifier regardless) one might therefore be inclined follow the first approach. A strong argument for the second one however is that there are various optimisations for the sumcheck protocol protocol when the input is a product of multilinear polynomials.

The sumcheck protocol is not zero-knowledge by default, but requires one to mask the input with a masking polynomial.

Sumcheck masking

Following [Lib19], the masking polynomial will be of the following form:

Definition (no mixed terms).
We will say that a multivariate polynomial $g(X_1,\ldots, X_m)$ in $m$ variables has no mixed terms if it can be decomposed into a sum $g(X_1,\ldots, X_m) = \sum_{i=1}^m g_i(X_i)$ of $m$ univariate polynomials $g_i(X)$.³

A multivariate polynomial in $m$ variables of total degree $d$ has \(\mathcal{O} (m^d)\) terms when $d$ is fixed. [Lib19] showed that such a polynomial can be masked by a degree-$d$ polynomial with no mixed terms, and those only have \(\mathcal{O}(m d)\) terms. The sumcheck messages of such a polynomial are cheap to compute:

Proposition.
Let $g(X_1,\ldots, X_m)$ be a multivariate polynomial of degree $d$ with no mixed terms. Then one can evaluate the hypercube sum

\[H_g \mathrel{\vcenter{:}}= \sum_{ b\in \\\{0,1\\\}^m } g(b)\]

and a sumcheck prover message

\[h_j (X) \mathrel{\vcenter{:}}= \sum_{ b\in \\\{0,1\\\}^{m - j} } g(r_1 ,\ldots, r_{j-1}, X, b_{1},\ldots, b_{m- j}),\qquad \textrm{for some values } r_1,\ldots, r_{j-1},\]

in $\mathcal{O}( m d)$ steps.

Note that both the generation of the masking polynomial and the computation of the first sum can be done by the prover ahead of time.

Proof: Decompose \(g(X_1,\ldots, X_m) = \sum_{i=1}^m g_i(X_i)\), then

\[H_g = \sum_{i=1}^m \sum_{ b\in \\\{0,1\\\}^m } g_i(X_i) = \sum_{i=1}^m 2^{m-1} \bigl(g_i(0) + g_i(1)\bigr)\]

and similarly

\[h_j (X) = g_j(X) + \sum_{i=1}^{j-1} g_i (r_i) + \sum_{i={j+1}}^m 2^{m-j - 1} \bigl(g_i(0) + g_i(1)\bigr) .\]

As evaluating each of the univariate polynomials $g_i(X)$ takes $\mathcal{O}( d )$ steps, the claim follows.

The following lemma will imply that computing opening proofs for such masking polynomials are also quite efficient, when instantiated with e.g. multivariate KZG [PST13].

Lemma.
Let $g(X_1,\ldots, X_m)$ be a multivariate polynomial of degree $d$ with no mixed terms. Then for any point $x = (x_1,\ldots,x_m)$ there exists a unique set of $m$ univariate polynomials $q_i(X)$ of degree $d-1$ such that

\[g(X_1,\ldots, X_m) - g(x) = \sum_{i=1}^m q_i(X_i)(X_i - x_i).\]

Proof: We leave proof of uniqueness to the reader. Pick a decomposition \(g(X_1,\ldots, X_m) = \sum_{i=1}^m g_i(X_i)\) into univariate polynomials and set $y_i \mathrel{\vcenter{:}}= g(x_i)$. Then for each $i$ there exists a (unique) polynomial $q_i(X)$ of degree $d - 1$ such that

\[g_i(X) - y_i = q_i(X)(X-x_i).\]

Since $g(x) = \sum_{i=1}^m g_i(x_i) = \sum_{i=1}^m y_i$, it follows that

\[g(X_1,\ldots, X_m) - g(x) = \sum_{i=1}^m g_i(X_i) - \sum_{i=1}^m y_i = \sum_{i=1}^m \bigl( g_i(X_i) - y_i \bigr) = \sum_{i=1}^m q_i(X)(X-x_i).\]

The downside of using [PST13] is that the verifier will have to compute a multi-pairing of size $m+1$. And there’s a hint that we can do better — we just used that the $q_i$ are small multivariate polynomials, but they are actually univariate polynomials.

If say we can batch the openings of the univariate $g_i$ at the $x_i$ without losing the masking property, then the evaluation of $g$ is the sum of those evaluations. The problem is that revealing all of those evaluations naively would leak too much information, so that gives us two ways to proceed:

• Increase the entropy of $g$ so it can leak those evaluations securely.
• Hide those evaluations, only reveal the evaluation of $g$.

I’m not sure how to do the first option efficiently, so we’ll explore the second option (suggested by Trisha Datta).

Formal description

Zeromorph reduces an opening proof of a multilinear polynomial into $m+1$ opening proofs of univariate polynomials at the same point, which are subsequently batched into two opening proofs, and then into a single opening proof. Similarly, Mercury transforms an opening proof of a multilinear polynomial into $8$ opening proofs of univariate polynomials at distinct points. which using e.g. Shplonk [BDFG20] can also be batched into just one KZG-style opening proof.

Thus, we fix a multilinear polynomial commitment scheme $\mathsf{mPCS}$ which reduces to a univariate polynomial commitmen scheme $\mathsf{uPCS}$, and furthermore $\mathsf{uPCS}$ supports batching opening proofs of distinct polynomials over distinct challenge points into a single opening proof.

We let $\mathcal{R}_\mathsf{Com}$ denote the randomness space of the commitment scheme.

In the case of [ZGK+17, KT23]’s hiding KZG the commitment randomness is just a scalar, whereas for [KZG10, CHM+19]’s hiding KZG we fix it to be a degree $1$ polynomial, so a pair of scalars.

\(\textsf{ZKSC.Blind}( \mathsf{prk}_\mathsf{PCS} ) \rightarrow ( \beta, C_\beta, \rho_\beta, \pi_\beta )\)

Compute a commitment $C_\beta$ to the multilinear polynomial $\beta \cdot \mathrm{eq}_\mathbf{0}$ for a random $\beta$, and use the homomorphic property to obtain a proof \(\pi_\beta\) that this commitment is indeed of a polynomial of the form \(\beta \cdot \mathrm{eq}_\mathbf{0}\) for some $\beta$.

As the inputs of this function are known ahead of time, the output of this function can be preprocessed (using a separate Fiat–Shamir transcript; one would have to rehash a \(\mathsf{vk}\) here, and rehash $C_\beta,\pi_\beta$ in the outer transcript); for simplicity, in this description we won’t.

Step 1a: Sample the mask \(\beta \xleftarrow{\$} \mathbb{F}\).

Step 1b: Define the multilinear polynomial $f_\beta \mathrel{\vcenter{:}}= \beta \cdot \mathrm{eq}_\mathbf{0}$.

Step 1c: Sample commitment randomness \(\rho_\beta \xleftarrow{\$} \mathcal{R}_\mathsf{Com}\).

Step 1d: Compute the commitment \(C_\beta \leftarrow \textsf{mPCS.Commit} ( \mathsf{prk}_\mathsf{PCS}, f_\beta; \rho_\beta )\).

Step 1e: Add $C_\beta$ to the Fiat–Shamir transcript.

Step 2a: Create a proof of knowledge $\pi_\beta$ for the inverse image $(\beta, \rho_\beta)$ of the resulting homomorphism. (This involves adding the first prover message to the Fiat–Shamir transcript.)

In the case of [ZGK+17, KT23]’s hiding KZG this homomorphism can be concretely presented as the concatenation of

\[(w_1 , w_2 )\longmapsto (f_{w_1} , w_2 ) \longmapsto w_1 \cdot [1]_1 + w_2 \cdot [\xi]_1 .\]

Whereas for [KZG10, CHM+19]’s hiding KZG with a degree $1$ random polynomial, it would be

\[\bigl( w_1 , (w_2, w_3) \bigr) \longmapsto \bigl( f_{w_1} , (w_2, w_3) \bigr) \longmapsto w_1 \cdot [1]_1 + w_2 \cdot [\xi]_1 + w_3 \cdot [\xi \tau]_1 .\]

Note here that the original commitment $C$ does not need to be masked with a degree $1$ random polynomial; degree $0$ suffices for the hiding property.

Step 2b: Add the remainder of $\pi_\beta$ to the Fiat–Shamir transcript.

\(\textsf{ZKSC.SendMask}\bigl( \mathsf{prk}_\mathsf{PCS} , m, d \bigr) \rightarrow \bigl( g, \\\{g_i, C_{g_i}, \rho_{g_i} \\\}_{1 \leq i \leq m}, H_g \bigr)\)

Here $d$ denotes the degree of the univariate $g_i$, which should agree with the maximum degree in the individual variables of the multivariate polynomial it’s masking. Note that $\textsf{uPCS.Commit}$ will require that $\mathsf{prk}_\mathsf{PCS}$ is large enough to accommodate these commitments; for KZG this means that the $\tau^i$’s will have to go up to degree $d$, for this range proof that means $3$.

As the inputs of this function are known ahead of time, the output of this function can be preprocessed.

Step 1: Sample a random $m$-variate polynomial $g(X_1,\ldots , X_m) = \sum_{i=1}^m g_i(X_i)$ of degree $d$ with no mixed terms.

Step 2: Compute $H_g = \sum_{ b\in \{0,1\}^m } g(b)$ (using e.g. the algorithm mentioned earlier).

Step 3: For each $1 \leq i \leq m$, sample commitment randomness: \(\rho_{g_i} \xleftarrow{\$} \mathcal{R}_\mathsf{Com}\).

Step 4: For each $1 \leq i \leq m$: \(C_{g_i} \leftarrow \textsf{uPCS.Commit}\bigl( \mathsf{prk}_\mathsf{PCS} , g_i; \rho_{g_i} \bigr)\).

\(\textsf{ZKZC.SendPolys} ( f,g) \rightarrow \bigl( \mathbf{x}, \\\{ h_i \\\}_{i = 1}^{\ell} \bigr)\)

Proves that an \(\ell\)-multivariate function $f$ of degree $d$ is zero on the hypercube away from \(\mathbf{0}\), by showing that the hypercube sum away from \(\mathbf{0}\) of \(f \cdot \mathrm{eq}_{\mathbf{c}}\) for a random \(\mathbf{c}\) is zero. This works by Schwartz–Zippel: \(\tilde{f}(Y) \mathrel{\vcenter{:}}= \sum_{b \in \{0,1\}^\ell} f(b) \cdot \mathrm{eq}_{Y}(b)\) is the multilinear extension of $f$ and $f \cdot \mathrm{eq}_{\mathbf{c}}$ is its evaluation at a random point. Since $f$ might not be zero outside of the hypercube, a masking polynomial of degree $d+1$ is used to avoid leaking any other information on $f$.

Step 1: \(\mathbf{c}_\operatorname{zc} \xleftarrow{\mathcal{FS}} \mathbb{F}^\ell\).

Step 2a: Define \(\check{f} = f \cdot \mathrm{eq}_{\mathbf{c}_\operatorname{zc}}\).

Step 2b: \((\mathbf{x}, \\\{ h_i \\\}_{i = 1}^{\ell}) \leftarrow \textsf{ZKSC.SendPolys}( \check{f},g)\).

\(\textsf{ZKSC.SendPolys}( f, g, \alpha) \rightarrow \bigl( \mathbf{x}, \\\{ h_i \\\}_{i = 1}^{\ell} \bigr)\)

Executes a sumcheck protocol not on $f + \alpha g$, but instead on $\tilde{f} + \alpha g$ where $\tilde{f}$ is the same as $f$ on the cube except it is $0$ at the point $\mathbf{0}$.

Step 1: Set $ h \mathrel{\vcenter{:}}= f\cdot Z_{\mathbf{0}} + \alpha g$.

Step 2: \(\bigl(\mathbf{x}, \\\{ h_i \\\}_{i = 1}^{\ell} \bigr) \leftarrow \textsf{SC.SendPolys}(h)\).

\(\textsf{Dekart}_{2}^{\textsf{SC}}\textsf{.Setup}\bigl( m_\max, \ell_\max \bigr) \rightarrow \mathsf{prk}\)

TODO

\(\textsf{Dekart}_{2}^{\textsf{SC}}\textsf{.Commit}\bigl( \mathsf{prk}_\mathsf{PCS}, \\\{ z_i \\\}_{1 \leq i \leq m}, \ell ; \rho \bigr) \rightarrow \bigl(C, ( \rho, \beta ) \bigr)\)

Fix a bijection

\[\{ 0,\ldots, 2^{m_\max} - 1 \} \longrightarrow \{ 0,1 \}^{m_\max}\]

with the property that the image of any integer of bit-length $0 \leq k\leq m_\max$ has nonzero entries only in its first $k$ coordinates (in particular, the value $0$ is mapped to the vector $\mathbf{0}\mathrel{\vcenter{:}}= (0,\ldots,0)$). This constraint is imposed for efficiency; a canonical choice is the standard binary (bitwise) decomposition.

Step 1a: Let $m$ be the smallest integer such that $n < 2^m$.

Step 1b: Extract $m_\max$ from \(\mathsf{prk}_\mathsf{PCS}\) and verify that $m \leq m_\max$.

Step 2a: Sample randomness \(\beta \xleftarrow{\$} \mathbb{F}\), or alternatively set $\beta = 0$ and defer sampling to $\textsf{ZKSC.Blind}$.

Step 2b: Restrict the above bijection to its first $m$ coordinates, thereby identifying \(\{ 0,1 \}^{m}\) with \(\{ 0,\ldots, 2^m - 1 \}\). Now let $f$ denote the multilinear extension of the resulting map

\[\{ 0,1 \}^{m} \longrightarrow \mathbb{F}^{m}\]

which evaluates to $\beta$ at $\mathbf{0}$, to $z_i$ at the Boolean vector corresponding to \(i \in \{1,\ldots, n \}\) and to $0$ elsewhere; we say that $f$ is the multilinear extension of the vector $(\beta, z_1,\ldots,z_n)$.

Step 3a: Sample commitment randomness: \(\rho \xleftarrow{\$} \mathcal{R}_\mathsf{Com}\).

Step 3b: \(C \leftarrow \textsf{mPCS.Commit} \bigl(\mathsf{prk}_\mathsf{PCS}, f; \rho \bigr).\)

\(\textsf{Dekart}_{2}^{\textsf{SC}}\textsf{.Prove} \bigl( \mathsf{prk}, C, \ell, \\\{z_i \\\}_{1 \leq i \leq n}; \rho \bigr) \rightarrow \pi\)

Step 1: Initialisation

Parse inputs and add the first items to the Fiat–Shamir transcript.

Step 1a: Parse the prover key: $(\mathsf{prk}_\mathsf{PCS}, \mathsf{vk}) \leftarrow \mathsf{prk}$.

Step 1b: Let $m$ be the smallest integer such that $n < 2^m$.

Step 1c: Extract $m_\max$ from \(\mathsf{prk}_\mathsf{PCS}\) and verify that $m \leq m_\max$.

Step 1d: Extract $\ell_\max$ from \(\mathsf{vk}\) and verify that $\ell \leq \ell_\max$.

Step 1e: Add (a hash of) $\mathsf{vk}$, $C$, $m$ and $\ell$ to the Fiat–Shamir transcript.

Step 2 (optional): Generate a commitment mask

Suppose $f$ was generated without a mask. The aim of the commitment mask $C_\beta$ is to replace $C$ with $C + C_\beta$, which by the homomorphic property corresponds to replacing $f$ with $f + \beta \cdot \mathrm{eq}_\mathbf{0}$. The effect of this change is that we can later do an opening proof outside of the hypercube (using commitment randomness \(\rho + \rho_\beta\)) without leaking information.

Step 2a: \((\beta, C_\beta, \rho_\beta, \pi_\beta) \leftarrow \textsf{ZKSC.Blind}(\mathsf{prk}_\mathsf{PCS} )\).

Step 2b: Replace $C$ by $C + C_\beta$ and $\rho$ by $\rho + \rho_\beta$.

Step 3: Compute masked bit commitments

For each $j \in [1, \ell]$ we gather the $j$’th bits of all of the secret values $\{z_i\}_{1 \leq i\leq n}$ into one polynomial, and add a mask again so that we can safely do an opening.

Step 3a: For each $i \in [n]$ and $j \in [\ell]$ compute the $j$-th bit $z_{i,j}$ of $z_i$, so that $z_i = \sum_{j=1}^\ell 2^{j - 1} z_{i,j}$.

Step 3b: Sample correlated randomness \(\beta_1,\ldots,\beta_\ell \xleftarrow{\$} \mathsf{CorrRand}(\beta, \ell)\).

Step 3c: Now for each $j\in [\ell]$ let $f_j$ be the multilinear extension of the vector

\[(\beta_j, z_{1,j},\ldots,z_{n,j}).\]

Step 3d: Sample commitment randomness $\ell$ times: \(\rho_1 ,\ldots, \rho_\ell \xleftarrow{\$} \mathcal{R}_\mathsf{Com}\).

(i) Since we’re going to batch the openings into one opening, here we probably only need one random scalar per commitment, even in the hiding schemes of [KZG10, CHM+19].

(ii) We are assuming that $\textsf{mPCS.Commit}$ reduces to a simple KZG-style commitment, and since we’re committing binary values, it may be significantly faster (depending on the elliptic curve library) to execute the resulting MSM manually, rather than calling a generic Pippenger algorithm.

Step 3e: For each $j \in [\ell]$ compute commitments to the $f_j$:

\[C_{f_j} \leftarrow \textsf{mPCS.Commit} \bigl(\mathsf{prk}_\mathsf{PCS}, f_j; \rho_j \bigr).\]

Step 4: Retrieve a masking polynomial

The input to the masked sumcheck protocol is $\check{f}$ multiplied by \(\operatorname{eq}_\mathbf{c}\) and \(\operatorname{vnsh}_\mathbf{0}\). $\check{f}$ is the sum of a multilinear polynomials and the products of pairs of those, so the the degree in any variable of the resulting polynomial is at most $4$.

Step 4a: \(\bigl( g, \\\{g_i, C_{g_i}, \rho_{g_i} \\\}_{1 \leq i \leq m}, H_g \bigr) \leftarrow \textsf{ZKSC.SendMask}\bigl( \mathsf{prk}_\mathsf{PCS} , m, 4 \bigr)\).

Appending \(\{C_{f_j}\}_j\) was delayed until here to do batch normalisation together with the \(\{C_{g_i}\}_i\).

Step 4b: Add the \(\{C_{f_j} \}_{1 \leq j \leq \ell}\) to the Fiat–Shamir transcript.

Step 4c: Add the $\{C_{g_i} \}_{1 \leq i \leq m}$ and $H_g$ to the Fiat–Shamir transcript.

Step 5: Initialise sumcheck protocol

Execute the sumcheck protocol with a batched input as described in the introduction, and obtain the challenge point $\mathbf{x}$.

Step 5a: \(c \xleftarrow{\mathcal{FS}} \mathbb{F}\).

Step 5b: Set $\check{f} \mathrel{\vcenter{:}}= \sum_{j = 1}^\ell c^j f_j (1 - f_j)$.

Step 5c: \(\alpha \xleftarrow{\mathcal{FS}} \mathbb{F}\).

Step 5d: \(\bigl( \mathbf{x}, \\\{ h_i \\\}_{i = 1}^{m} \bigr) \leftarrow \textsf{ZKSC.SendPolys}( \check{f},g, \alpha)\).

Step 6: Batch the multilinear opening proofs

Instead of creating a batched opening proof for our multilinear polynomials, we take one step back and use the assumption that the $\mathsf{mPCS}$ creates an opening proof by reducing it to several univariate openings (which are then batched into one opening). For Zeromorph, \(\{ \hat{g}_i \}_i\) consists of $2$ polynomials or just $1$ if it’s been batched already. $\pi_\mathsf{mPCS}$ consists of $m+1$ KZG commitments, corresponding to the functions (in the notation of the Zeromorph paper) $q_0,\ldots, q_{m- 1}, \hat{q}$.

Step 6a: Compute $y_f \leftarrow f(\mathbf{x})$.

Step 6b: For each $1 \leq j \leq \ell$, compute $y_j \leftarrow f_j(\mathbf{x})$.

Step 6c: Add $y_f$ and the \(\{ y_j \}_{1 \leq j \leq \ell}\) to the Fiat–Shamir transcript.

We now initiate an $\mathsf{mPCS}$ batch opening for these values.

Step 6d: \(\hat{c} \xleftarrow{\mathcal{FS}} \mathbb{F}\).

Step 6e: $\hat{f} \leftarrow f + \sum_{j = 1}^\ell \hat{c}^{j} f_j$.

Step 6f: $\hat{\rho} \leftarrow \rho + \sum_{j = 1}^\ell \hat{c}^{j} \rho_j$.

Step 6g: \(\bigl( \\\{ \hat{x}_i \\\}_{1 \leq i \leq k}, \\\{ \hat{g}_i \\\}_{1 \leq i \leq k}, \\\{ \rho_{\hat{g}_i} \\\}_{1 \leq i \leq k}, \pi_\mathsf{mPCS} \bigr) \leftarrow \textsf{mPCS.ReduceToUnivariate}(\mathbf{x}, \hat{f}, \hat{\rho})\).

Step 7: Batch all of the opening proofs

Now we’re going to batch open the $\{ \hat{g}_i \}_i$ of the previous step with the $\{ g_i \}_i$ of the masked polynomial. Except we’re not going to reveal the vector of evaluations $\mathbf{y}$ of the $\{ g_i \}_i$, but only its sum $y_g$. To commit to $\mathbf{y}$, any homomorphic vector commitment scheme can be used here, e.g. hiding KZG.

One way to instantiate this would be to use an $\mathsf{mPCS}$ like Zeromorph which reduces to a KZG variant, then use Shplonked to batch the opening proofs. The Zeromorph polynomials evaluate to $0$ on their evaluation points.

Step 7a: Parse \((x_1,\ldots, x_m) \leftarrow \mathbf{x}\).

Step 7b: Gather the set of polynomials \(\mathbf{g} \mathrel{\vcenter{:}}= \\\{ \hat{g}_i \\\}_{1 \leq i \leq k} \cup \\\{ g_i \\\}_{1 \leq i \leq m}\) with corresponding commitment randomness \(\mathbf{r} \mathrel{\vcenter{:}}= \\\{ \rho_{\hat{g}_i} \\\} \cup \\\{ \rho_{g_i} \\\}\) and evaluation sets \(\mathbf{S} \mathrel{\vcenter{:}}= \\\{ \hat{x}_i \\\}_{1 \leq i \leq k} \cup \\\{ x_i \\\}_{1 \leq i \leq m}\). We let $\varphi$ denote the homomorphism which sums the $g_i(x_i)$.

Step 7c: \((y_g, \pi_\mathsf{Open}) \leftarrow \textsf{uPCS.BatchOpen}\bigl( \mathsf{prk}_\mathsf{PCS}, \mathbf{S}, \varphi; \mathbf{g}, \mathbf{r} \bigr).\)

Step 8: Return the proof

Assemble the proof.

Step 8: \(\pi \leftarrow \bigl(\{C_{f_j} \}_{1 \leq j \leq \ell}, \\\{ C_{g_i} \\\}_{1 \leq i\leq m}, H_g, \\\{ h_i \\\}_{1 \leq i\leq m}, y_f, \\\{ y_i \\\}_{1 \leq i\leq \ell}, y_g, \pi_\mathsf{mPCS}, \pi_\mathsf{Open} \bigr).\)

$\textsf{Dekart}_{2}^{\textsf{SC}}\textsf{.Verify}(\mathsf{vk}, C, \ell; \pi ) \rightarrow \{0,1 \}$

Step 1: Initialisation

Parse inputs and add the first items to the Fiat–Shamir transcript.

Step 1a: Parse the verificaton key: \(( \mathsf{vk}_\mathsf{PoK}, \mathsf{vk}_\mathsf{PCS}, \ell_\mathrm{max} ) \leftarrow \mathsf{vk}\) and check that $\ell \leq \ell_\mathrm{max}$.

Step 1b: Parse the proof: \(\bigl(\{C_{f_j} \}_{1 \leq j \leq \ell}, \\\{ C_{g_i} \\\}_{1 \leq i\leq m}, H_g, \\\{ h_i \\\}_{1 \leq i\leq m}, y_f, \\\{ y_i \\\}_{1 \leq i\leq \ell}, y_g, \pi_\mathsf{mPCS}, \pi_\mathsf{Open} \bigr) \leftarrow \pi\).

Step 1c: Add (a hash of) $\mathsf{vk}$, $C$, $m$ and $\ell$ to the Fiat–Shamir transcript.

Step 2 (optional): Verify the blinding commitment

If the original commitment was blinded, confirm that the blinding commitment $C_\beta$ used is of the required form (and hence adding it won’t modify the $z_i$’s in $C$).

Step 2a: Add $C_\beta$ to the Fiat–Shamir transcript.

Step 2b: \(\Sigma_\textsf{PoK.Verify}(\mathsf{vk}_\mathsf{PoK} , C_\beta ; \pi_\beta) \overset{?}{=} 1\). (This involves adding the first prover message to the Fiat–Shamir transcript.)

Step 2c: Add the rest of $\pi_\beta$ to the Fiat–Shamir transcript.

Step 3: Initialise sumcheck protocol verification

Begin verifying the masked sumcheck protocol, culminating in challenge point.

Step 3a: Add the \(\{C_{f_i} \}_{1 \leq i \leq \ell}\), \(\{C_{g_i} \}_{1 \leq i \leq m}\), and $H_g$ to the Fiat–Shamir transcript.

Step 3b: \(c \xleftarrow{\mathcal{FS}} \mathbb{F}\).

Step 3c: \(\alpha \xleftarrow{\mathcal{FS}} \mathbb{F}\backslash \{0\}\).

Step 3d: \(\mathbf{c}_\operatorname{zc} \xleftarrow{\mathcal{FS}} \mathbb{F}^m\).

Step 3e: \(\textsf{ZKSC.PolyCheck}\bigl(\alpha H_g, \\\{ h_i \\\}_{i = 1}^{m - 1} \bigr) \overset{?}{=} 1\) and outputs $\mathbf{x} = (x_1 ,\ldots, x_m)$.

Step 4: Finish sumcheck protocol verification

Assuming all evaluations are correct, we can finish the verification of the sumcheck protocol. We do this step first to allow for better batching.

Step 4a: Check the identity:

\[\bigl( \sum_{j = 1}^\ell c^{j} y_j (1 - y_j) \bigr) \cdot \mathrm{eq}_{\mathbf{c}_\operatorname{zc}} (\mathbf{x}) \cdot Z_\mathbf{0} (\mathbf{x}) + \alpha \, y_g \overset{?}{=} h_m (x_m).\]

Step 4b: Check the identity:

\[y_f - \sum_{j = 1}^\ell 2^{j-1} y_j\]

Step 5: Verify evaluations

Verify the evaluations. The pairing check is left last so it can be batched as part of a larger multi-pairing.

Step 5a: Add $y_f$ and the \(\{ y_j \}_{1 \leq j \leq \ell}\) to the Fiat–Shamir transcript.

Step 5b: \(\hat{c} \xleftarrow{\mathcal{FS}} \mathbb{F}\).

In the notation of the Zeromorph paper, by $\hat{g}$ we mean the function corresponding to the element $C_{\zeta, Z}$. Roughly corresponds to an MSM of size $m$ plus 3 additions.

Step 5c: Using $\hat{c}$, compute the \(\{ \hat{g}_i (\hat{x}_i)\}_i\) and their MSM representations \(\{ \mathbf{C}_{\hat{g}_i} \}_i\).

Ordinarily we would now do an MSM to compute the commitments \(\\\{ C_{\hat{g}_i} \\\}_{1 \leq i \leq k}\) from $C$ and the \(\{C_{f_j} \}_{1 \leq j \leq \ell}\), then pass them into \(\textsf{uPCS.BatchVerify}\). Then those get reused inside an MSM, so this would mean two MSMs are computed, when only one is really needed. So instead we pass the MSM representation of the \(\\\{ C_{\hat{g}_i} \\\}_{1 \leq i \leq k}\), which we will denote by \(\\\{ \mathbf{C}_{\hat{g}_i} \\\}_{1 \leq i \leq k}\).

Step 5d: Gather the MSM representations \(\mathbf{C} \mathrel{\vcenter{:}}= \{ \mathbf{C}_{\hat{g}_i} \}_{1 \leq i \leq k} \cup \\\{ C_{g_i} \\\}_{1 \leq i \leq m}\) with (revealed) evaluations \(\mathbf{y} \mathrel{\vcenter{:}}= \\\{\hat{g}_i (\hat{x}_i) \\\}\) and evaluation sets \(\mathbf{S} \mathrel{\vcenter{:}}= \\\{ \hat{x}_i \\\}_{1 \leq i \leq k} \cup \\\{ x_i \\\}_{1 \leq i \leq m}\). We let $\varphi$ denote the homomorphism which sums the hidden evaluations $g_i(x_i)$.

Step 5e: \(\textsf{uPCS.BatchVerify}\bigl( \mathsf{vk}_\mathsf{PCS}, \mathbf{S}, \varphi, \mathbf{C}; \mathbf{y}, y_g, \pi_\mathsf{Open} \bigr) \overset{?}{=} 1.\)

Acknowledgements

Many thanks to Alin Tomescu for teaching me core principles of this field and suggesting the hiding KZG scheme of [KZG10, CHM+19], and to Trisha Datta for answering questions about $\mathsf{DekartProof}$.

References

[BAZB20] Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh. “Zether: Towards privacy in a smart contract world.” In International Conference on Financial Cryptography and Data Security, pp. 423-443. Cham: Springer International Publishing, 2020.

[BGL+23] James Bell, Adrià Gascón, Tancrède Lepoint, Baiyu Li, Sarah Meiklejohn, Mariana Raykova, and Cathie Yun. {ACORN}: Input validation for secure aggregation. In 32nd USENIX Security Symposium (USENIX Security 23), pages 4805–4822, 2023.

[Bor20] William Borgeaud. Membership proofs from polynomial commitments, 2020. https://solvable.group/posts/membership-proofs-from-polynomial-commitments/.

[CB21] Panagiotis Chatzigiannis and Foteini Baldimtsi. “Miniledger: Compact-sized anonymous and auditable distributed payments.” In European Symposium on Research in Computer Security, pp. 407-429. Cham: Springer International Publishing, 2021.

[CFT98] Agnes Chan, Yair Frankel, and Yiannis Tsiounis. “Easy come—easy go divisible cash.” In International Conference on the Theory and Applications of Cryptographic Techniques, pp. 561-575. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998.

[CGS97] Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. “A secure and optimally efficient multi‐authority election scheme.” European transactions on Telecommunications 8, no. 5 (1997): 481-490.

[Chunky] https://alinush.github.io/chunky

[CHM+19] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas Ward. “Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS.” https://eprint.iacr.org/2019/1047

[DBBCB15] Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark, and Dan Boneh. “Provisions: Privacy-preserving proofs of solvency for bitcoin exchanges.” In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 720-731. 2015.

[EMBB17] Saba Eskandarian, Eran Messeri, Joseph Bonneau, and Dan Boneh. “Certificate transparency with privacy.” arXiv preprint arXiv:1703.02209 (2017).

[Gro21] Jens Groth. Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, 2021.

[KZG10] Aniket Kate, Gregory M. Zaverucha and Ian Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 177–194. Springer, 2010.

[LAN02] Helger Lipmaa, N. Asokan, and Valtteri Niemi. “Secure Vickrey auctions without threshold trust.” In International Conference on Financial Cryptography, pp. 87-101. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002.

[Lib19] Tiacheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In A. Boldyreva and D. Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 733–764, Santa Barbara, CA, USA, Aug. 18–22, 2019. Springer, Cham, Switzerland.

[Lib24] Benoît Libert. “Vector commitments with proofs of smallness: Short range proofs and more.” In IACR International Conference on Public-Key Cryptography, pp. 36-67. Cham: Springer Nature Switzerland, 2024.

[PLS19] Rafaël del Pino, Vadim Lyubashevsky, and Gregor Seiler. “Short discrete log proofs for FHE and ring-LWE ciphertexts.” In IACR International Workshop on Public Key Cryptography, pp. 344-373. Cham: Springer International Publishing, 2019.

[PST13] Charalampos Papamanthou, Elaine Shi, and Roberto Tamassia. “Signatures of correct computation.” Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.

[Spa20] Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In D. Micciancio and T. Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 704–737, Santa Barbara, CA, USA, Aug. 17–21, 2020. Springer, Cham, Switzerland.

[ZGK+17] Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint Archive, Report 2017/1146 (2017), https://eprint.iacr.org/2017/1146

1. More concretely, on my M4 Max I’m seeing that the percentage of time spent on major components is as follows:

   Configuration	Binary MSM	(I)FFTs	KZG Commit/Open
   ℓ=8, n=1023	8%	15%	72%
   ℓ=64, n=1023	24%	41%	27%
   ℓ=8, n=131,071	8%	26%	62%
   ℓ=64, n=131,071	15%	56%	18%

   ↩︎

2. If say $\mathbf{0} = (0,\ldots,0)$ then we can explicitly write $Z_\mathbf{0} (X_1 ,\ldots, X_m) = 1 - (1 - X_1) \cdots (1 - X_m)$. ↩︎

3. For a tiny bit of extra efficiency, one might want to present $g$ as the sum of a constant term and univariate polynomials $g_i(X)$ with no constant term. ↩︎