padding_indicator_array.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
#include "../circuit_builders/circuit_builders_fwd.hpp"
#include "../witness/witness.hpp"
#include "barretenberg/polynomials/barycentric.hpp"
#include "barretenberg/transcript/origin_tag.hpp"
 
namespace bb::stdlib {
 
template <typename Curve, size_t virtual_log_n = CONST_PROOF_SIZE_LOG_N>
static std::vector<typename Curve::ScalarField> compute_padding_indicator_array(
    const typename Curve::ScalarField& log_n)
{
    using Fr = typename Curve::ScalarField;
    // Create a domain of size `virtual_log_n` and compute Lagrange denominators
    using Data = BarycentricDataRunTime<Fr, virtual_log_n, /*num_evals=*/1>;
 
    std::vector<Fr> result(virtual_log_n);
    // 1) Build prefix products:
    //    prefix[i] = ∏_{m=0..(i-1)} (x - 1 - big_domain[m]), with prefix[0] = 1.
    std::vector<Fr> prefix(virtual_log_n, Fr{ 1 });
    for (size_t i = 1; i < virtual_log_n; ++i) {
        prefix[i] = prefix[i - 1] * (log_n - Fr{ 1 } - Data::big_domain[i - 1]);
    }
 
    // 2) Build suffix products:
    //    suffix[i] = ∏_{m=i..(N-1)} (x - 1 - big_domain[m]),
    //    but we'll store it in reverse:
    //    suffix[virtual_log_n] = 1.
    std::vector<Fr> suffix(virtual_log_n + 1, Fr(1));
    for (size_t i = virtual_log_n; i > 0; i--) {
        suffix[i - 1] = suffix[i] * (log_n - Fr{ 1 } - Data::big_domain[i - 1]);
    }
 
    // To ensure 0 < log_n < N, note that suffix[1] = \prod_{i=1}^{N-1} (x - 1 - i), therefore we just need to ensure
    // that this product is 0.
    if constexpr (Curve::is_stdlib_type) {
        suffix[0].assert_equal(Fr{ 0 });
    }
 
    // 3) Combine prefixes & suffixes to get L_i(x-1):
    //    L_i(x-1) = (1 / lagrange_denominators[i]) * prefix[i] * suffix[i+1].
    //    (We skip factor (x - big_domain[i]) by splitting into prefix & suffix.)
    for (size_t i = 0; i < virtual_log_n; ++i) {
        result[i] = Data::precomputed_denominator_inverses[i] * prefix[i] * suffix[i + 1];
    }
    // Convert result into the array of step function evaluations sums b_i.
    for (size_t idx = virtual_log_n - 1; idx > 0; idx--) {
        // Use idx - 1 in the body if you prefer
        result[idx - 1] += result[idx];
    }
 
    // OriginTag false positive: the padding indicator array elements are derived from a `log_circuit_size` and are used
    // to perform conditional padding logic in Sumcheck (Currently, only in UltraZKRecursiveFlavor), where they are
    // mixing with sumcheck univariates.
    if constexpr (Curve::is_stdlib_type) {
        for (auto& indicator : result) {
            indicator.clear_round_provenance();
        }
    }
 
    return result;
}
} // namespace bb::stdlib