Evaluating Piecewise Multilinears

Combining differently-sized subcubes

Here, we drop another bit of interesting mathematical content, to prepare the way for our batched commitment scheme. The idea again has to do with piecewise multilinears. We already saw that our batched commitment scheme starts with individual polynomials $t_0, \ldots , t_{n - 1}$ over the huge field $\mathcal{T}_\tau$ , generally allowed to be different sizes. To commit to those polynomials, that procedure concatenates all of the given polynomials into a huge list, and reinterprets that list as a large multilinear polynomial (possibly after zero-padding the master list to a power-of-two length).

As we also mentioned, that procedure can also be viewed in a geometric way, using the idea of a piecewise function. That is, it takes its input multilinears $t_0, \ldots , t_{n - 1}$ , with numbers of variables $\ell_0, \ldots , \ell_{n - 1}$ , say. Each of these individual multilinears $t_i(X_0, \ldots , X_{\ell_i - 1})$ defines "a $\mathcal{B}_{\ell_i}$ 's worth" of data. The master multilinear $t^*(X_0, \ldots , X_{\ell^* - 1})$ that comes out of our commitment procedure is essentially a piecewise multilinear on the huge cube $\mathcal{B}_{\ell^*}$ , which takes the values that the individual polynomials $t_i(X_0, \ldots , X_{\ell_i - 1})$ respectively do on various disjoint subcubes $\mathcal{B}_{\ell_i} \subset \mathcal{B}_{\ell^*}$ .

Here, we set out with a basic question: let's say that we fix some evaluation point $(r_0, \ldots , r_{\ell^* - 1}) \in \mathcal{T}_\tau^{\ell^*}$ . How do the individual evaluations

\begin{equation*}t_i(r_0, \ldots , r_{\ell_i - 1})\end{equation*}

of the "facets", on appropriate prefixes of the $(r_0, \ldots , r_{\ell^* - 1})$ , relate to the evaluation of the whole multilinear

\begin{equation*}t^*(r_0, \ldots , r_{\ell^* - 1})\end{equation*}

at $(r_0, \ldots , r_{\ell^* - 1})$ ?

The Idea

The idea here isn't especially mysterious mathematically, but it involves some interesting algorithmic aspects. We imagine the components $(r_0, \ldots , r_{\ell^* - 1})$ coming to us one by one. The idea is to work "starting at the small end". As of the end of the $i$ ^th round, some among the individual polynomials $t_j(X_0, \ldots X_{\ell_j - 1})$ might become "freshly ready"—namely, those for which $\ell_j - 1 = i$ . We recall that these things will be "placed" on $\ell_j$ -dimensional subcubes of $\mathcal{B}_{\ell^*}$ .

Upon receiving $r_i$ , our goal will be to "bootstrap" all outstanding subcubes of $i$ -dimensions into $i + 1$ -dimensional subcubes. We do this by doing linear combinations with $1 - r_i$ and $r_i$ .

In general, as of the end of round $i$ , we will have some mix of freshly available, $i + 1 = \ell_j$ -dimensional subcubes, as well as possibly $i$ -dimensional subcubes left over from previous rounds. Our goal will be to "coalesce" or "smooth" everything $i$ -dimensional into $i + 1$ -dimensional things, by doing a pass over the trailing end of the data.

We will keep doing passes like this, as $i$ grows from $\{0, \ldots , \ell^* - 1\}$ .

As a worked example, let's look again at the piecewise function described here. The master function is $\ell^* = 3$ -dimensional. So, let's say we want to evaluate the whole polynomial at a single point—to learn $t^*(r_0, r_1, r_2)$ , say. How can we cook up this evaluation, given only the individual, front-loaded evaluations $t_2()$ , $t_1(r_0)$ and $t_0(r_0, r_1)$ ?

Roughly, we can work the following way, keeping the geometric picture constantly in mind. We are going to work from the small cubes upward. Recall that, by fiat, we have $t^*(0, 1, 1) = t_2()$ , while $t^*(1, 1, 1) = 0$ . So, we can thus write in $t^*(r_0, 1, 1) = (1 - r_0) \cdot t_2() + r_0 \cdot 0$ .

Moreover, by definition, the lines $t^*(X_0, 0, 1)$ and $t_1(X_0)$ agree identically. Thus, we can directly write $t^*(r_0, 0, 1) = t_1(r_0)$ .

In this way, we've assembled both $t^*(r_0, 0, 1)$ and $t^*(r_0, 1, 1)$ . By doing a simple linear interpolation, we con further obtain $t^*(r_0, r_1, 1) = (1 - r_1) \cdot t^*(r_0, 0, 1) + r_1 \cdot t^*(r_0, 1, 1)$ . On the other hand, by fiat, $t^*(r_0, r_1, 0) = t_0(r_0, r_1)$ . We thus have both $t^*(r_0, r_1, 0)$ and $t^*(r_0, r_1, 1)$ . By doing one final interpolation, we can obtain $t^*(r_0, r_1, r_2) \coloneqq (1 - r_2) \cdot t^*(r_0, r_1, 0) + r_2 \cdot t^*(r_0, r_1, 1)$ . This gives us what we want!

The entire point of the rest of this page is to systematize this procedure.

The Algorithm

We sketch the algorithm here. We assume as usual that $\ell_0 \geq \cdots \geq \ell_{n - 1}$ . We imagine that we start with a list $T_0, \ldots , T_{n - 1}$ of "claim" objects. From the verifier's viewpoint, each $T_j$ will eventually contain the evaluation of $t_j(r_0, \ldots , r_{\ell_j - 1})$ —that is, as of the end of the $\ell_j - 1$ ^st round, these things will become ready. In each round $i$ , our job will be to receive any such objects—i.e., for which $\ell_j - 1 = i$ , or in other words $\ell_j = i + 1$ . Moreover, we will "lift" everything which is not yet $i + 1$ -dimensional to the $i + 1$ -dimensional level, by smoothing trailing subcubes.

To keep track of all the relevant information, we bake a linked-list structure into the claims $T_0, \ldots , T_{n - 1}$ . To begin with, we initialize $T_j.\text{next} \coloneqq j + 1$ , for each $j \in \{0, \ldots , n - 1\}$ .

Here are the steps.

For each round $i \in \{0, \ldots , \ell^* - 1\}$ $i \in {0, \dots, ℓ^{*} - 1}$ :
- The verifier samples $r_i \gets \mathcal{T}_\tau$ and sends it to the prover.
- For each claim index $j \in \{0, \ldots , n - 1\}$ for which $\ell_j - 1 = i$ on the nose, the prover sends a claimed evaluation $b_{j, \ell_j} \stackrel{?}= t_j(r_0, \ldots , r_{\ell_j - 1})$ to the verifier.
- For the same set of $j \in \{0, \ldots , n - 1\}$ (i.e., for which $\ell_j - 1 = i$ ), the verifier marks: $\begin{equation*}T_j.\text{claim} \coloneqq b_{j, \ell_j}.\end{equation*}$
- The verifier again writes $j_i$ $j_{i}$ for the minimum among those $j \in \{0, \ldots , n\}$ $j \in {0, \dots, n}$ for which $\ell_j \leq i$ $ℓ_{j} \leq i$ holds. The verifier initializes $k \coloneqq j_i$ $k : = j_{i}$ , and then runs the following loop. While $k < n$ $k < n$ :
  - The verifier sets $c_0 \coloneqq T_k.\text{claim}$ .
  - If the next element $T_k.\text{next} < n$ , then the verifier sets $c_1 \coloneqq T_k.\text{next}.\text{claim}$ , and moreover cuts $T_k.\text{next}$ out of the list, by overwriting $T_k.\text{next} = T_k.\text{next}.\text{next}$ . Otherwise, the verifier sets $c_1 \coloneqq 0$ .
  - In any case, the verifier now overwrites $T_k.\text{claim} = (1 - r_i) \cdot c_0 + r_i \cdot c_1$ , and also updates $k = T_k.\text{next}$ .
At this point, the verifier outputs the final value $T_0.\text{claim}$ .

Security Claim

Now, during the course of the above algorithm, the prover either did or didn't supply the correct evaluation claims $b_{j, \ell_j} \stackrel{?}= t_j(r_0, \ldots , r_{\ell_j - 1})$ to the verifier. Our completeness claim is that if these claims were all valid, then the verifier's final output will be equal to nothing other than $t^*(r_0, \ldots , r_{\ell^* - 1})$ , where, again, $t^*(X_0, \ldots , X_{\ell^* - 1})$ is defined in the piecewise way we already discussed. Conversely, if even a single of these was wrong, then the verifier's final output $T_0.\text{claim}$ will not be equal to $t^*(X_0, \ldots , X_{\ell^* - 1})$ , with high probability over the verifier's choice of the point $(r_0, \ldots , r_{\ell^* - 1})$ . In fact, it can be shown that this soundness error is at most $\frac{\ell^*}{|\mathcal{T}_\tau|}$ .