binius_core/protocols/gkr_exp/
mod.rs

1// Copyright 2025 Irreducible Inc.
2
3//! Exponentiation via GKR.
4//!
5//! Let's represent $A$ by its bits, i.e., for each $v \in B_\ell$ we have $A(v)= \sum_{i=0}^{n-1}
6//! 2^{i} \cdot b_{i}(v)$. Then, exponentiation can be split into cases, each with its own circuit.
7//!
8//! 1) Exponentiation of the generator by a chunk of bit-columns:
9//!
10//!    $$
11//!    V_0(X) = 1 - a_0(X) + a_0(X) \cdot g \\\\
12//!    V_1(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot V_{0}(v) \cdot \left(1 -
13//!    a_{1}(v) + a_{1}(v) \cdot g^{2} \right) \\\\
14//!    \ldots \\\\
15//!    V_n(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot V_{n-2}(v) \cdot \left(1 -
16//!    a_{n-1}(v) + a_{n-1}(v) \cdot g^{2^{n-1}} \right)
17//!    $$
18//!
19//! 2) Exponentiation of the multilinear base by a chunk of bit-columns:
20//!
21//!    $$
22//!    W_0(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (1 - a_{n-1}(v) + a_{n-1}(v)
23//!    \cdot V(v)) \\\\
24//!    W_1(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (W_0(v))^2 \cdot (1 -
25//!    a_{n-2}(v) + a_{n-2}(v) \cdot V(v)) \\\\
26//!    \ldots \\\\
27//!    W_{n-1}(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (W_{n-2}(v))^2 \cdot (1 -
28//!    a_0(v) + a_0(v) \cdot V(v)).
29//!    $$
30//!
31//! You can read more information in [Integer Multiplication in Binius](https://www.irreducible.com/posts/integer-multiplication-in-binius).
32
33mod batch_prove;
34mod batch_verify;
35mod common;
36mod compositions;
37mod error;
38mod oracles;
39mod provers;
40mod utils;
41mod verifiers;
42mod witness;
43
44pub use batch_prove::batch_prove;
45pub use batch_verify::batch_verify;
46pub use common::{BaseExpReductionOutput, ExpClaim, LayerClaim};
47pub use error::Error;
48pub use oracles::{construct_gkr_exp_claims, get_evals_in_point_from_witnesses, make_eval_claims};
49pub use witness::BaseExpWitness;
50
51#[cfg(test)]
52mod tests;
binius_core/protocols/gkr_exp/mod.rs

binius_core/protocols/gkr_exp/
mod.rs
