Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
grand_product_delta.hpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: not started, auditors: [], date: YYYY-MM-DD }
3// external_1: { status: not started, auditors: [], date: YYYY-MM-DD }
4// external_2: { status: not started, auditors: [], date: YYYY-MM-DD }
5// =====================
6
7#pragma once
8
10#include <span>
11namespace bb {
12
24template <typename Flavor>
26 const typename Flavor::FF& beta,
27 const typename Flavor::FF& gamma,
28 const typename Flavor::FF& offset = 0)
29{
30 using FF = typename Flavor::FF;
31 FF numerator = FF(1);
32 FF denominator = FF(1);
33
34 // Let m be the number of public inputs x₀,…, xₘ₋₁.
35 // Recall that we broke the permutation σ⁰ by changing the mapping
36 // (i) -> (n+i) to (i) -> (-(i+1)) i.e. σ⁰ᵢ = −(i+1)
37 //
38 // Therefore, the term in the numerator with ID¹ᵢ = n+i does not cancel out with any term in the denominator.
39 // Similarly, the denominator contains an extra σ⁰ᵢ = −(i+1) term that does not appear in the numerator.
40 // We expect the values of W⁰ᵢ and W¹ᵢ to be equal to xᵢ.
41 // The expected accumulated product would therefore be equal to
42
43 // ∏ᵢ (γ + W¹ᵢ + β⋅ID¹ᵢ) ∏ᵢ (γ + xᵢ + β⋅(n+i) )
44 // ----------------------- = ------------------------
45 // ∏ᵢ (γ + W⁰ᵢ + β⋅σ⁰ᵢ ) ∏ᵢ (γ + xᵢ - β⋅(i+1) )
46
47 // The RHS is often referred to as the "grand product delta". Note that the products on the RHS is only over the
48 // public input indices, while the products on the LHS are over the entire circuit.
49 //
50 // At the start of the loop for each xᵢ where i = 0, 1, …, m-1, we have
51 // numerator_acc = γ + β⋅(n+i) = γ + β⋅n + β⋅i
52 // denominator_acc = γ - β⋅(1+i) = γ - β - β⋅i
53 // at the end of the loop, add and subtract β to each term respectively to
54 // set the expected value for the start of iteration i+1.
55 // Note: The public inputs may be offset from the 0th index of the wires, for example due to the inclusion of an
56 // initial zero row or Goblin-stlye ECC op gates. Accordingly, the indices i in the above formulas are given by i =
57 // [0, m-1] + offset, i.e. i = offset, 1 + offset, …, m - 1 + offset.
58
59 // Using n = SEPARATOR ensures that the evaluations of `id_i` (`sigma_i`) and `id_j`(`sigma_j`) polynomials on the
60 // boolean hypercube do not intersect for i != j.
62 FF numerator_acc = gamma + (beta * (SEPARATOR + offset));
63 FF denominator_acc = gamma - beta * (offset + 1);
64
65 for (size_t i = 0; i < public_inputs.size(); i++) {
66 numerator *= (numerator_acc + public_inputs[i]); // γ + xᵢ + β(n+i)
67 denominator *= (denominator_acc + public_inputs[i]); // γ + xᵢ - β(1+i)
68
69 // To avoid introducing extra variables in the circuit, we skip numerator_acc and denominator_acc in the final
70 // loop iteration, since their values won't be used
71 if (i < public_inputs.size() - 1) {
72 numerator_acc += beta;
73 denominator_acc -= beta;
74 }
75 }
76 return numerator / denominator;
77}
78
79} // namespace bb
bb::field< bb::Bn254FrParams > FF
Definition field.cpp:22
typename Curve::ScalarField FF
ssize_t offset
Definition engine.cpp:36
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
Flavor::FF compute_public_input_delta(std::span< const typename Flavor::FF > public_inputs, const typename Flavor::FF &beta, const typename Flavor::FF &gamma, const typename Flavor::FF &offset=0)
Compute the correction term for the permutation argument.
constexpr uint32_t PERMUTATION_ARGUMENT_VALUE_SEPARATOR
Definition constants.hpp:9
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13