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::span< const FF > multivariate_challenge, const size_t log_circuit_size)
	Compute the evaluation of \( 1 - L \) at the sumcheck challenge.

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 \( 4,\ldots, n-1 \), i.e.,

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

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

\[ 1 - L = 1 - L_0 - L_1 - L_2 - L_3. \]

that vanishes at the first \( 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:

\( 0 = (0,0, \ldots, 0) \)
\( 1 = (1,0,0,\ldots,0) \)
\( 2 = (0,1,0,\ldots,0) \)
\( 3 = (1,1,0,\ldots,0) \)

Round 0:

\[ \begin{aligned} S' &= S_{H,0} - \Big(L_0(X, 0,0, \ldots, 0) + L_1(X, 0,0,\ldots,0)\Big) H(X,0,0,\ldots, 0) \\ &\quad - \Big(L_2(X, 1,0,\ldots,0) + L_3(X,1,0,\ldots,0)\Big) H(X,1,0,\ldots,0) \end{aligned} \]

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

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

\[ \begin{aligned} L_0(X,\vec{0}) + L_1(X,\vec{0}) &= (1 - X) + X = 1 \\ L_2(X,1,0,\ldots,0) + L_3(X,1,0,\ldots,0) &= 1 \end{aligned} \]

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

Round 1:

\[ \begin{aligned} L_0(u_0,X,\vec{0}) + L_1(u_0,X,\vec{0}) &= (1 - u_0)(1 - X) + u_0 (1 - X) = (1 - X) \\ L_2(u_0,X,\vec{0}) + L_3(u_0,X,\vec{0}) &= (1 - u_0) X + u_0 X = X \end{aligned} \]

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

After folding, only 1 edge pair remains: the disabled contribution is at edge \( (0,\ldots,0) \) with factor \( (1-X) \).

Round 2:

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

Rounds i > 1:

\[ S_{H,i}(X) = S_{H,i} - \prod_{k=2}^{i-1}(1 - u_k) \cdot (1 - X) \cdot H(u_0, \ldots, u_{i-1}, X, 0, \ldots, 0). \]

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,0,0,\ldots,0) + H(X,1,0,\ldots,0) \) as a univariate of degree \( D \), else compute \( H(u_0, \ldots, u_{i-1}, X, 0, \ldots, 0) \) 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, 0, \ldots, 0) \) 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 - \prod_{k=2}^{d-1}(1 - u_k) \) otherwise.

Definition at line 122 of file row_disabling_polynomial.hpp.

Constructor & Destructor Documentation

◆ RowDisablingPolynomial()

template<typename FF >

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

default

Member Function Documentation

◆ evaluate_at_challenge()

template<typename FF >

static FF bb::RowDisablingPolynomial< FF >::evaluate_at_challenge	(	std::span< const 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 154 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