# Overview of the Halo2 Challenge API and Random Linear Combinations (RLC)

###### tags: `explainers`

We introduce the concept of the **Challenge API** in vanilla (PSE) Halo2 and then discuss an important application of this API to a technique around **random linear combinations (RLC)**. This is a new feature only introduced in the Privacy Scaling Exploration's fork of Halo2.

## Recap of "basic" Halo2

We start by reviewing the basic idea around Halo2 with PLONKish arithmetization. The Prover supplies a bunch of witness values in a table:


(We ignore everything else besides witness assignment in this discussion.) The Prover then takes each column of the table, converts the column to a polynomial, and then *commits* to the polynomial via some polynomial commitment scheme.

In the interactive version of a ZK proving scheme, the Verifier would now send the Prover some random numbers, which the Prover would then use to do things like [permutation arguments](https://zcash.github.io/halo2/design/proving-system/permutation.html) and proofs of polynomial openings.

However in practice we never use the interactive version. Instead, the Prover simulates the Verifier's random queries using the Fiat-Shamir transform. At first pass, this means the Prover needs to hash all witness values to produce a random **challenge**. In practice, we don't need to hash all the witnesses, we just need to hash *commitments* to all the witnesses. Since we already have polynomial commitments of each column, we can just hash those. This hash becomes the stand-in for the random challenge sent by the Verifier.

We have just described a Challenge API with a single "phase". This is already what is done whenever you generate a proof in Halo2 -- it's just that the challenge generation is done on the backend and hidden from the user.

## Multi-phase challenges

Here is a common problem: inside a ZK circuit, the Prover wants to compute witness values that depend on a (pseudo-)random number.

How do you access randomness inside a circuit? In an interactive protocol, you can ask the Verifier for a random challenge. For this to work, you must commit to all witness values you've generated so far, ask the Verifier for a random number, and then use that random number in subsequent witness computations.

In a non-interactive protocol, we use Fiat-Shamir again: you commit to all witnesses so far and hash the commitments to get a random challenge value. You can now use this random challenge as part of subsequent witness computations.

Halo2 provides an explicit API for generating these random challenges: when you design your circuit, you partition the columns into "phases".


During witness generation, the Prover first computes all witness values in columns in First Phase. Then on the backend they commit to those columns via the polynomial commitment scheme. They hash those commitments to get a challenge value $\theta$. Now the Prover continues to do witness generation of all values in the Second Phase, where they can use $\theta$ as part of the calculations. More specifically, $\theta$ can be referenced as part of any custom gate constraints.

### Technical details

#### Configuration
Let's look at an [example](https://github.com/privacy-scaling-explorations/halo2/blob/main/halo2_proofs/examples/shuffle.rs#L64) in vanilla/raw Halo2:

Here's how to define a column in Second Phase during configuration.

// Second phase
let z = meta.advice_column_in(SecondPhase);

Similar to `Column`s and `Selector`s, your configuration will need to keep track of the `Challenge` struct.

struct MyConfig {
    // ..other stuff
    theta: Challenge,
}
// ...
fn configure<F: Field>(meta: &mut ConstraintSystem<F>) -> Self {
    let theta = meta.challenge_usable_after(FirstPhase)
// ...

You can then get an expression from the challenge `theta` to use as part of a custom gate definition; see [here](https://github.com/privacy-scaling-explorations/halo2/blob/17e9765c199670534c0299c96128d0464a188d0b/halo2_proofs/examples/shuffle.rs#L82).

#### Witness generation: PSE version

In order to compute the witness values in Second Phase, you need to know the actual value of the challenge. During [synthesize](https://github.com/privacy-scaling-explorations/halo2/blob/17e9765c199670534c0299c96128d0464a188d0b/halo2_proofs/examples/shuffle.rs#L149) you can get a `Value<F>` for this challenge by calling

    let theta = layouter.get_challenge(config.theta);

where `config.theta` has type `Challenge` and `theta` has type `Value<F>`.

**But wait!** In `synthesize` you can assign witness values to columns across all phases in any order you'd like. How does the API actually compute the challenge value? There is a dirty secret: the Halo2 backend will run `synthesize` *twice* (assuming you have two phases):
1. On the first run, `layouter.get_challenge(config.theta)` returns `Value::unknown()`. It assigns witnesses to *all* columns, but values in Second Phase columns don't matter / they can be unknown.
2. The backend commits to First Phase columns, hashes the commitments, and now has a challenge value for `theta`.
3. On the second run, `layouter.get_challenge(config.theta)` returns the correct challenge value. *All* witness values are re-generated, including those in First Phase. Now witness values in Second Phase will be calculated using the actual challenge value.

**Pros:**
* Synthesize function logic does not need to worry about division of columns into phases. Generally a nicer dev experience.

**Cons:**
* Witness generation is twice as slow since it's run twice.

#### Witness generation: Axiom version

The con of calling witness generation twice (or three times if three phases 😱) is clearly undesirable. In an ideal setting, we get the best of both worlds by creating an API where all functions involving multiple phases are called concurrently asynchronously. These async functions would then all wait for a broadcast of the challenge value before continuing with witness generation. This would involve significant engineering changes, so we are not there yet.

In Axiom's [fork](https://github.com/axiom-crypto/halo2/tree/axiom/dev) of Halo2, we opt to solve the witness generation problem, albeit at some cost to the developer experience:

We add a function [`next_phase`](https://github.com/axiom-crypto/halo2/blob/2e9c8724604c926efff139d7d44dbeebfd8d960b/halo2_proofs/src/circuit.rs#L371) that allows the Prover to tell the backend to commit to all columns in a Phase *during witness generation*. This means you can call

region.next_phase()

during `synthesize`. The developer now needs to separate a two-phase function `fn_name` into

fn_name_phase0(...)
fn_name_phase1(...)

where `fn_name_phase{i}` only does witness generation for cells in columns of the `{i+1}`th Phase.

During `synthesize`, they can
* call `fn_name_phase0()` to fill in witnesses for FirstPhase columns
* call `region.next_phase()` to commit to those columns
* call `region.get_challenge(config.theta)` to get the random challenge value equal to the hash of commitments
* use this random challenge in `fn_name_phase1()` to fill in witness for SecondPhase columns

In this process, the entire `synthesize` function only needs to be called once!

## Random linear combinations (RLCs)

Consider the following problems:
1. You have two byte strings `a, b` as witnesses. You want to compute the boolean value `a == b` in your circuit.
2. You have three byte strings `a, b, c` as witnesses. You can to check that `a . b == c` in your circuit, where `.` denotes concatenation.

While there are fun solutions to these problems (exercise!) in the single phase Halo2 API (or in any other proving system), they are still rather costly in terms of increasing overall circuit size (and hence performance).

The multi-phase challenge API provides us a very powerful new technique for these types of problems:

Let us have an in-circuit random challenge $\gamma$. For a fixed length byte string $a$ of length $n$ we define $$\mathsf{RLC}(a,n) = a_0 \cdot \gamma^{n-1} + a_1 \cdot \gamma^{n-2} + \dotsb + a_{n-1} = \sum_{i=0}^{n-1} a_i \cdot \gamma^{n-1-i}.
$$
Returning to the previous problems:
1. Assume for simplicity $a,b$ are fixed length strings of the same length $n$ (variable length can be dealt with with some additional work). Then $\mathsf{RLC}(a,n) = \mathsf{RLC}(b,n)$ implies $a = b$ with very high probability.
2. Assume $a,b,c$ are fixed length strings of lengths $n_a, n_b, n_c$ such that $n_a + n_b = n_c$. Then $\mathsf{RLC}(a,n_a)\cdot \gamma^{n_b} + \mathsf{RLC}(b, n_b) = \mathsf{RLC}(c, n_c)$ implies $a . b = c$ with very high probability.

The proof of both statements is by considering both sides as polynomials in a variable $\gamma$ and then applying the Schwartz--Zippel lemma.

### Axiom's RLC implementation

We provide an implementation of a gate for RLC computations using the Halo2 challenge API in [`axiom_eth::rlp::rlc`](https://github.com/axiom-crypto/axiom-eth/blob/axiom-dev-0406/src/rlp/rlc.rs). We give an overview of the idea.

Firstly, we use our usual `halo2-base` [simple gate](https://docs.axiom.xyz/zero-knowledge-proofs/getting-started-with-halo2#simplified-interface) for columns in FirstPhase.

We add a new column in SecondPhase with an accompanying selector:

| RLC Advice | RLC Selector |
| -------- | -------- |
| $a_0$ | $s_0$ |
| $a_1$ | $s_1$ |
| $a_2$ | $s_2$ |

We create a new custom gate on these two columns imposing the constraint
$$s_0 \cdot (a_0 \cdot \gamma + a_1 - a_2) == 0.
$$ [Here](https://github.com/axiom-crypto/axiom-eth/blob/6d2a4acf559a8716b867a715f3acfab745fbad3f/src/rlp/rlc.rs#L66) is the gate definition.

Now for example we can constrain the computation of $out = a_0 \cdot \gamma^2 + a_1 \cdot \gamma + a_2$ using
| RLC Advice | RLC Selector |
| -------- | -------- |
| $a_0$ | 1 |
| $a_1$ | 0 |
| $a_0 \cdot \gamma + a_1$ | 1 |
| $a_2$ | 0 |
| $out$ | 0 |

Lastly, if we want to take $out$ from this column and do computations on it using functions provided by `GateChip` or `RangeChip`, we must now use a new SecondPhase column with the `halo2-base` simple gate constraint on that column. We can no longer use the FirstPhase column because any witness values involving $\gamma$ must belong in SecondPhase.

Just like with `GateChip` and `RangeChip`, we have implemented a [`RlcChip`](https://axiom-crypto.github.io/axiom-eth/axiom_eth/rlp/rlc/struct.RlcChip.html) with commonly used functions related to RLC computations. These functions include:
* `compute_rlc`
* `compute_rlc_fixed_len`
* `constrain_rlc_concat`
* `constrain_rlc_concat_var`
* `rlc_pow`

To use `RlcChip` within `axiom-eth`, you need to create a circuit using either [`RlcCircuitBuilder`](https://github.com/axiom-crypto/axiom-eth/blob/6d2a4acf559a8716b867a715f3acfab745fbad3f/src/rlp/tests.rs#L309) or [`KeccakCircuitBuilder`](https://github.com/axiom-crypto/axiom-eth/blob/6d2a4acf559a8716b867a715f3acfab745fbad3f/src/keccak/mod.rs#L640) (we will not discuss keccak here).

An example of how to create such a circuit can be found [here](https://github.com/axiom-crypto/axiom-eth/blob/6d2a4acf559a8716b867a715f3acfab745fbad3f/src/rlp/tests.rs#L54). The most notable point is that due to the fact that `RlcChip` should be used in SecondPhase after FirstPhase columns have been committed to and a challenge $\gamma$ is calculated, the `RlcCircuitBuilder` streamlines this process by taking a Rust closure having `RlcChip` as one of the closure arguments. This way you do not need to deal with creating an `RlcChip` yourself, you just need to supply the function that uses it for SecondPhase witness generation:

        let synthesize_phase1 = move |builder: &mut RlcThreadBuilder<F>, rlc: &RlcChip<F>| {
            // the closure captures the `inputs` variable
            log::info!("phase 1 synthesize begin");
            let gate = GateChip::default();

            let (ctx_gate, ctx_rlc) = builder.rlc_ctx_pair();
            let rlc_trace = rlc.compute_rlc((ctx_gate, ctx_rlc), &gate, inputs, len);
            let rlc_val = *rlc_trace.rlc_val.value();
            dbg!(rlc_val);
        };

Here `builder.rlc_ctx_pair()` gives two `Context`s, which can be thought of as memory banks storing witness values and other constraints. Then `ctx_gate` corresponds to the SecondPhase column with `halo2-base` simple gate, and `ctx_rlc` corresponds to the SecondPhase RLC advice column above.