Polynomial for Sumcheck with disabled Rows. More...

#include <row_disabling_polynomial.hpp>

Public Member Functions
	RowDisablingPolynomial ()=default

void	update_evaluations (FF round_challenge, size_t round_idx)
	Compute the evaluations of L^{(i)} at 0 and 1.

Static Public Member Functions
static FF	evaluate_at_challenge (std::vector< FF > multivariate_challenge, const size_t log_circuit_size)
	Compute the evaluation of \( 1 - L \) at the sumcheck challenge.

static FF	evaluate_at_challenge (std::span< FF > multivariate_challenge, const std::vector< FF > &padding_indicator_array)
	A variant of the above that uses `padding_indicator_array`.

Public Attributes
FF	eval_at_0 { 1 }

FF	eval_at_1 { 1 }

Detailed Description

template<typename FF>
struct bb::RowDisablingPolynomial< FF >

Polynomial for Sumcheck with disabled Rows.

\( n = 2^d \) circuit size \( L_i \) multilinear Lagrange in \( d \) variables, \( i = 0,\ldots, n-1 \).

Assume we are given a "valid" execution trace at rows \( 0,\ldots, n-5 \), i.e.,

\[ \sum_{\mathbb{H} \setminus \{n-1, n-2, n-3, n-4\}} H = 0. \]

We want to pad the witness polynomials with random field elements in rows \( n-1, n-2, n-3 \). Since the commitment to the shift must coincide with the commitment to its unshifted counterpart, we have to reserve \( 4 \) rows at the end to be able to. To achieve this, we multiply the Honk relation \( H \) by the polynomial

\[ 1 - L = 1 - L_{n-1} - L_{n-2} - L_{n-3} - L_{n-4}. \]

that vanishes at the last \( 4 \) rows and is equal to \( 1 \) everywhere else on the hypercube.

We consider the sumcheck protocol for the modified relation

\[ \sum_{\mathbb{H}} (1 - L) H = \sum_{\mathbb{H}} H - \sum_{\mathbb{H}} L \cdot H. \]

Note that the target sum remains \( 0 \) because the contributions from the last rows are multiplied by \( 0 \).

Recall:

\( n-1 = 2^d - 1 = (1,1, \ldots, 1) \)
\( n-2 = (0,1,\ldots,1) \)
\( n-3 = (1,0,\ldots,1) \)
\( n-4 = (0,0,\ldots,1) \)

Round 0:

\[ \begin{aligned} S' &= S_{H,0} - \Big(L_{n-1}(X, 1, \ldots, 1) + L_{n-2}(X, 1,\ldots,1)\Big) H(X,1,\ldots, 1) \\ &\quad - \Big(L_{n-3}(X, 0,1,\ldots,1) + L_{n-4}(X,0,1,\ldots,1)\Big) H(X,0,1,\ldots,1) \end{aligned} \]

We do not modify the algorithm computing \( S_{H,0} \). Simply add a method that computes the contribution from the edges \( (0,1,\ldots,1) \) and \( (1,\ldots,1) \in \mathbb{H}^{d-1} \).

First, compute the coefficients in the Lagrange basis of the factor coming from the Lagranges:

\[ \begin{aligned} L_{n-1}(X,\vec{1}) + L_{n-2}(X,\vec{1}) &= X + (1 - X) = 1 \\ L_{n-3}(X,0,1,\ldots,1) + L_{n-4}(X,0,1,\ldots,1) &= 1 \end{aligned} \]

\[ S'_0 = S_{H,0} - H(X,1,\ldots,1) - H(X,0,1,\ldots,1) \]

Round 1:

\[ \begin{aligned} L_{n-1}(u_0,X,\vec{1}) + L_{n-2}(u_0,X,\vec{1}) &= u_0 X + (1 - u_0) X = X \\ L_{n-3}(u_0,X,\vec{1}) + L_{n-4}(u_0,X,\vec{1}) &= u_0 (1 - X) + (1 - u_0)(1 - X) = (1 - X) \end{aligned} \]

\[ S'_1 = S_{H,1} - H(X,1,\ldots,1) \]

Round 2:

\[ S'_2 = S_{H,2} - X \cdot H(u_0,u_1,X,1,\ldots,1) \]

Rounds i > 1:

We can compute the restricted sumcheck univariates \( S' \) in each round as follows:

\[ \begin{aligned} S' = S_{H,i} - \Big(L_{n-1}(u_0, \ldots, u_{i-1}, X, 1, \ldots, 1) + L_{n-2}(u_0, \ldots, u_{i-1}, X, 1,\ldots,1) \\ + L_{n-3}(u_0, \ldots, u_{i-1}, X, 1,\ldots,1) + L_{n-4}(u_0, \ldots, u_{i-1}, X, 1,\ldots,1)\Big) \\ \times H(u_0, \ldots, u_{i-1}, X, 1,\ldots,1) \end{aligned} \]

Compute the factor coming from the Lagranges:

\[ \begin{aligned} &\left(u_0 \cdots u_{i-1} + (1 - u_0) u_1 \cdots u_{i-1} + u_0 (1 - u_1) u_2 \cdots u_{i-1} + (1 - u_0)(1 - u_1) u_2 \cdots u_{i-1}\right) X \\ &= \left(u_0 u_1 + (1 - u_0) u_1 + u_0 (1 - u_1) + (1 - u_0)(1 - u_1)\right) u_2 \cdots u_{i-1} X \\ &= 0 \cdot (1 - X) + 1 \cdot u_2 \cdots u_{i-1} \cdot X \end{aligned} \]

This way, we get:

\[ S_{H,i}(X) = S_{H,i} - u_2 \cdots u_{i-1} \cdot X \cdot H(u_0, \ldots, u_{i-1}, X, 1, \ldots, 1). \]

The algorithm:

Let \( D \) be the max partial degree of \( H \).

Compute \( S_{H,i} \) without any modifications as a polynomial of degree \( D \). Extend it to degree \( D + 1 \), because it is the max partial degree of \( L \cdot H \).
If \( i = 0 \), compute \( H(X,1,1,\ldots,1) + H(X,0,1,\ldots,1) \) as a univariate of degree \( D \), else compute \( H(u_0, \ldots, u_{i-1}, X, 1, \ldots, 1) \) as a univariate of degree \( D \). Extend to degree \( D + 1 \).
Compute the extension of \( L^{(i)} = L(u_0, \ldots, u_{i-1}, X, 1, \ldots, 1) \) to the degree \( D + 1 \) polynomial.
Compute the coefficients of the product \( L^{(i)} \cdot H^{(i)} \).
Compute the coefficients of \( S_{H,i} - L^{(i)} \cdot H^{(i)} \) (degree \( D + 1 \) univariate).

The verifier needs to evaluate \( 1 - L(u_0, \ldots, u_{d-1}) \), which is equal to \( 0 \) if \( d < 2 \), and is equal to \( 1- u_2 \cdots u_{d-1} \) otherwise.

Definition at line 141 of file row_disabling_polynomial.hpp.

Constructor & Destructor Documentation

◆ RowDisablingPolynomial()

template<typename FF >

bb::RowDisablingPolynomial< FF >::RowDisablingPolynomial ( )

default

Member Function Documentation

◆ evaluate_at_challenge() [1/2]

template<typename FF >

static FF bb::RowDisablingPolynomial< FF >::evaluate_at_challenge	(	std::span< FF >	multivariate_challenge,
		const std::vector< FF > &	padding_indicator_array
	)

inlinestatic

A variant of the above that uses padding_indicator_array.

Parameters

multivariate_challenge	Sumcheck evaluation challenge
padding_indicator_array	An array with first log_n entries equal to 1, and the remaining entries are 0.

Definition at line 190 of file row_disabling_polynomial.hpp.

◆ evaluate_at_challenge() [2/2]

template<typename FF >

static FF bb::RowDisablingPolynomial< FF >::evaluate_at_challenge	(	std::vector< FF >	multivariate_challenge,
		const size_t	log_circuit_size
	)

inlinestatic

Compute the evaluation of \( 1 - L \) at the sumcheck challenge.

Parameters

multivariate_challenge
log_circuit_size

Returns: FF

Definition at line 173 of file row_disabling_polynomial.hpp.

◆ update_evaluations()

template<typename FF >

void bb::RowDisablingPolynomial< FF >::update_evaluations	(	FF	round_challenge,
		size_t	round_idx
	)

inline

Compute the evaluations of L^{(i)} at 0 and 1.

In every round, the contribution from the Honk relation computed at disabled rows has to be mutiplied by \( L^{(i)} \), which is a linear combination of Lagrange polynomials defined above.

Parameters