padding_indicator_array.hpp File Reference

For a small integer N = virtual_log_n and a given witness x = log_n, compute in-circuit an indicator_padding_array of size \( N \), such that. More...

#include "../circuit_builders/circuit_builders_fwd.hpp"
#include "../witness/witness.hpp"
#include "barretenberg/polynomials/barycentric.hpp"

Go to the source code of this file.

Namespaces
namespace	bb
	Entry point for Barretenberg command-line interface.
namespace	bb::stdlib

Detailed Description

For a small integer N = virtual_log_n and a given witness x = log_n, compute in-circuit an indicator_padding_array of size \( N \), such that.

\begin{align} \text{indicator_padding_array}[i] = \text{"} i < x \text{"}. \end{align}

. To achieve the strict ineqaulity, we evaluate all Lagranges at (x-1) and compute step functions. More concretely

1) Constrain x to be in the range \( [1, \ldots, N] \) by asserting

\begin{align} \prod_{i=0}^{N-1} (x - 1 - i) = 0 \end{align}

.

2) For \( i = 0, ..., N-1 \), evaluate \( L_i(x) \). Since \( 1 < x <= N \), \( L_i(x - 1) = 1 \) if and only if \( x - 1 = i \).

3) Starting at \( b_{N-1} = L_{N-1}(x - 1)\), compute the step functions

\begin{align} b_i(x - 1) = \sum_{i}^{N-1} L_i(x - 1) = L_i(x - 1) + b_{i+1}(x - 1) \end{align}

.

We compute the Lagrange coefficients out-of-circuit, since \( N \) is a circuit constant.

The resulting array is being used to pad the number of Verifier rounds in Sumcheck and Shplemini to a fixed constant and turn Recursive Verifier circuits into constant circuits. Note that the number of gates required to compute \( [b_0(x-1), \ldots, b_{N-1}(x-1)] \) only depends on \( N \) adding ~ \( 4\cdot N \) gates to the circuit.

Definition in file padding_indicator_array.hpp.