# Ceno Frontend and Backend Design

The whole architecture is splitted into two folders, `/subprotocols` and `/gkr_iop`:
- `/subprotocols` consists the sumcheck protocol, the zerocheck protocol and expression structs.
- `/gkr_iop` consists of APIs to define `Chip`, and the whole protocols, including `commit_phase1`, `commit_phase2`, `gkr_phase`.

Here are detailed descriptions:

## Subprotocols

The goal of this folder is to define expression-based sumcheck and optimized zerocheck protocols.

### The reason to use expression-based arguments.

We use the logup constraints as an example. The logup expression is to compute the sum of two fractions:
$$
d(X) + \beta \cdot n(X) = \sum_{b \in \left \{ 0, 1 \right \}^\ell} eq(X, b) \cdot \left( d_0(X) \cdot d_1(X) + \beta \cdot \left( d_0(X) \cdot n_1(X) + d_1(X) \cdot n_0(X) \right) \right)
$$
which requires $5 \times 4 \times 2^\ell$ (or can be optimized to $5 \times 3 \times 2^\ell$) extension field multiplications to compute the sumcheck round proofs. However, for the old "list-of-product" implementation, the equation has to be
$$
d(X) + \beta \cdot n(X) = \sum_{b \in \left \{ 0, 1 \right \}^\ell} eq(X, b) \cdot d_0(X) \cdot d_1(X) + \beta \cdot eq(X, b) \cdot d_0(X) \cdot n_1(X) + \beta \cdot eq(X, b) \cdot d_1(X) \cdot n_0(X)
$$
which requires $8 \times 4 \times 2^\ell$ (or $8 \times 3 \times 2^\ell$).

### Sumcheck protocol
The sumcheck protocol takes one sigma $\sigma$ as the LHS of the equation, and one expression $\mathsf{expr}$ as the RHS. We prove the following equation:
$$
\sigma = \sum_{b \in \{0, 1\}^\ell} \mathsf{expr}(b)
$$

### Zerocheck protocol
While the zerocheck protocol takes multiple $\sigma_i$ as the LHS of the equation, and multiple expressions $\mathsf{expr}_i$, and prove the following equations:
$$
\begin{align}
&\sigma_0 = \sum_{b \in \{0, 1\}^\ell} eq(r_0, b) \cdot \mathsf{expr}_0(b) \ , \\
&\sigma_1 = \sum_{b \in \{0, 1\}^\ell} eq(r_1, b) \cdot \mathsf{expr}_1(b) \ , \\
&\vdots
\end{align}
$$
More specifically, we send the sumcheck round message to the verifier for each equation separately, while sharing the same verifier challenges among them.

We also use the optimizations in Section 3. in [this paper](https://eprint.iacr.org/2024/108). Dealing with equation separately is to be compatible with those optimizations.

## GKR IOP

The GKR IOP protocol is to define the commit phase, the GKR phase, and the opening phase for a chip (or an independent circuit). To achieve this, we have the following designs.

### Protocol builder and witness generator, prover and verifier.

We define the following traits for the scope of the whole protocol, including the commit phase, the GKR phase, and the opening phase.
- `ProtocolBuilder` is to define how to run the protocol.

    pub trait ProtocolBuilder: Sized {
        type Params;

        fn init(params: Self::Params) -> Self;

        /// Build the protocol for GKR IOP.
        fn build(params: Self::Params) -> (Self, Chip) {
            let mut chip_spec = Self::init(params);
            let mut chip = Chip::default();
            chip_spec.build_commit_phase1(&mut chip);
            chip_spec.build_commit_phase2(&mut chip);
            chip_spec.build_gkr_phase(&mut chip);

            (chip_spec, chip)
        }

        /// Specify the polynomials and challenges to be committed and generated in
        /// Phase 1.
        fn build_commit_phase1(&mut self, spec: &mut Chip);
        /// Specify the polynomials and challenges to be committed and generated in
        /// Phase 2.
        fn build_commit_phase2(&mut self, _spec: &mut Chip) {}
        /// Create the GKR layers in the reverse order. For each layer, specify the
        /// polynomial expressions, evaluation expressions of outputs and evaluation
        /// positions of the inputs.
        fn build_gkr_phase(&mut self, spec: &mut Chip);
    }

- `ProtocolWitnessGenerator` is to generate the witness.

    pub trait ProtocolWitnessGenerator<E>
    where
        E: ExtensionField,
    {
        type Trace;

        /// The vectors to be committed in the phase1.
        fn phase1_witness(&self, phase1: Self::Trace) -> Vec<Vec<E::BaseField>>;

        /// GKR witness.
        fn gkr_witness(&self, phase1: &[Vec<E::BaseField>], challenges: &[E]) -> GKRCircuitWitness<E>
        where
            E: ExtensionField;
    }

- `ProtocolProver` and `ProtocolVerifier` are to run the protocol, together with PCS protocol. (Maybe instead of traits, we should define them as functions with several generic types.)

### Chip and layout.

We define the struct `Chip` to store all information required in the GKR IOP protocol, including the commit phases, the gkr phase and the opening phase.

#[derive(Clone, Debug, Default)]
pub struct Chip {
    /// The number of base inputs committed in the whole protocol.
    pub n_committed_bases: usize,
    /// The number of ext inputs committed in the whole protocol.
    pub n_committed_exts: usize,

    /// The number of challenges generated through the whole protocols
    /// (except the ones inside sumcheck protocols).
    pub n_challenges: usize,
    /// All input evaluations generated at the end of layer protocols will be stored
    /// in a vector and this is the length.
    pub n_evaluations: usize,
    /// The layers of the GKR circuit, in the order outputs-to-inputs.
    pub layers: Vec<Layer>,

    /// The polynomial index and evaluation expressions of the base inputs.
    pub base_openings: Vec<(usize, EvalExpression)>,
    /// The polynomial index and evaluation expressions of the ext inputs.
    pub ext_openings: Vec<(usize, EvalExpression)>,
}

To define a new chip, we should define a layout to describe the chip. Take the tower circuit as an example, we define `TowerChipLayout` as follows:

#[derive(Clone, Debug, Default)]
struct TowerChipLayout<E> {
    params: TowerParams,

    // Commit poly indices.
    committed_table: usize,
    committed_count: usize,

    lookup_challenge: Constant,

    output_cumulative_sum: [EvalExpression; 2],

    _field: PhantomData<E>,
}

We implement `ProtocolBuilder` for `TowerChipLayout` and generate a `Chip` object. We also implement `ProtocolWitnessGenerator` for `TowerChipLayout` and generate the witness committed in the Phase 1 (there is no Phase 2) and used in the GKR intermediate layers. For more details please refer to [the source code](https://github.com/scroll-tech/ceno/blob/5c75107d14647aaeca500fc1b254200ad0144b0f/gkr_iop/examples/multi_layer_logup.rs).

### GKR circuit and protocol.

The GKR protocol is a sequence of sumcheck (or zerocheck) protocols, connected by evaluation reduction. The GKR circuit is defined as follows

#[derive(Clone, Debug)]
pub struct GKRCircuit<'a> {
    pub layers: &'a [Layer],

    pub n_challenges: usize,
    pub n_evaluations: usize,
    pub base_openings: &'a [(usize, EvalExpression)],
    pub ext_openings: &'a [(usize, EvalExpression)],
}

which can be extracted from `Chip`. So we have a method for it:

impl Chip {
    /// Extract information for the GKR protocol.
    pub fn gkr_circuit(&'_ self) -> GKRCircuit<'_> {
        GKRCircuit {
            layers: &self.layers,
            n_challenges: self.n_challenges,
            n_evaluations: self.n_evaluations,
            base_openings: &self.base_openings,
            ext_openings: &self.ext_openings,
        }
    }
}

With the GKR circuit, we can call the prover and verifier protocols:

impl GKRCircuit<'_> {
    pub fn prove<E>(
        &self,
        circuit_wit: GKRCircuitWitness<E>,
        out_evals: &[PointAndEval<E>],
        challenges: &[E],
        transcript: &mut impl Transcript<E>,
    ) -> Result<GKRProverOutput<E, Evaluation<E>>, BackendError<E>>
    where
        E: ExtensionField,
    {
        ...
    }

    pub fn verify<E>(
        &self,
        gkr_proof: GKRProof<E>,
        out_evals: &[PointAndEval<E>],
        challenges: &[E],
        transcript: &mut impl Transcript<E>,
    ) -> Result<GKRClaims<Evaluation<E>>, BackendError<E>>
    where
        E: ExtensionField,
    {
        ...
    }

    ...
}

## Designs in GKR Circuit and Protocol

Finally, we introduce the designs in the GKR circuit and protocol.

### Building a GKR circuit

In our design, the GKR circuit is a sequence of layers, including sumcheck layers, zerocheck layers and linear layers. For each layer type, we call the corresponding subprotocols. In the chip builder,
1. We assign a number to challenges received from the verifier (except those within a sumcheck/zerocheck protocol) by `pub fn allocate_challenges<const N: usize>(&mut self) -> [Constant; N]`.
2. We number witnesses separately in each layer. Moreoever, we number the base field witnesses and extension field witnesses separately.
3. We also number the evaluations globally and use evaluation expressions to help compute the output evaluation before running the layer protocols.

#### Evaluation reduction among layers
To represent the evaluation reduction from a back layer to a front layer, we exploit an evaluation tape. We assign a position on the evaluation tape for each layer witness, and assign an evaluation expression for each layer output. The evaluation expression is as follows:

/// Evaluation expression for the gkr layer reduction and PCS opening preparation.
#[derive(Clone, Debug)]
pub enum EvalExpression {
    /// Single entry in the evaluation vector.
    Single(usize),
    /// Linear expression of an entry with the scalar and offset.
    Linear(usize, Constant, Constant),
    /// Merging multiple evaluations which denotes a partition of the original
    /// polynomial. `(usize, Constant)` denote the modification of the point.
    /// For example, when it receive a point `(p0, p1, p2, p3)` from a succeeding
    /// layer, `vec![(2, c0), (4, c1)]` will modify the point to `(p0, p1, c0, p2, c1, p3)`.
    /// where the indices specify how the partition applied to the original polynomial.
    Partition(Vec<Box<EvalExpression>>, Vec<(usize, Constant)>),
}

After we finish a layer protocol and compute the evaluations, we write them at the corresponding positions. Before running the protocol for a new layer, we compute the output evaluation according to its evaluation expression.

## Example: Building the Tower Circuit

[Here](https://github.com/scroll-tech/ceno/blob/5c75107d14647aaeca500fc1b254200ad0144b0f/gkr_iop/examples/multi_layer_logup.rs) is an example of constructing and generating a proof of tower circuit used in the logup protocol.