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 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 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 Columns and Selectors, 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.

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 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 of Halo2, we opt to solve the witness generation problem, albeit at some cost to the developer experience:

We add a function next_phase 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}+\cdots +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. We give an overview of the idea.

Firstly, we use our usual halo2-base simple gate 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 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 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 or KeccakCircuitBuilder (we will not discuss keccak here).

An example of how to create such a circuit can be found here. 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 Contexts, 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.