The PSE's zkEVM circuits have a variety of helpful 'gadgets' for various functionalities.

One of these is the LTChip gadget, which is used for checking, given inputs lhs and rhs, whether lhs < rhs holds true. It can be used as a helper as a part of various larger circuits, something like this:

    
    struct SomeLargerCircuitConfig<F> {
        q_enable: Selector,
        ....
        ....
        check: Column<Advice>,
        lt: LtConfig<F, NUM_BYTES>
}

Here, LTConfig is the configuration for the gadget as defined in the zkevm-circuits. But how does it look like and work under the hood and what limitations does it possess?

Analysing LTConfig

The default LTConfig is defined in the following manner:

/// Config for the Lt chip.
#[derive(Clone, Copy, Debug)]
pub struct LtConfig<F, const N_BYTES: usize> {
    /// Denotes the lt outcome. If lhs < rhs then lt == 1, otherwise lt == 0.
    pub lt: Column<Advice>,
    /// Denotes the bytes representation of the difference between lhs and rhs.
    pub diff: [Column<Advice>; N_BYTES],
    /// Denotes the range within which each byte should lie.
    pub u8: Column<Fixed>,
    /// Denotes the range within which both lhs and rhs lie.
    pub range: F,
}

What this means is that the configuration looks something like this:

lt	diff[0]	diff[1]	diff [2]	…	diff[N_BYTES-1]	u8
1	0xff	0xff	0xff	…	0xff

The column contains a lookup table u8 which can be used to perform a range check on the value of each byte, 1 advice column for the lt status (1 if lhs<rhs and 0 otherwise) and the 2^N_BYTES advice columns for the difference.

diff[0], diff[1], diff[2] .... diff[N_BYTES-1] denote the respective bytes of the difference of the LHS and RHS.

How is this difference calculated and hence, how is the circuit constrained?

Remember the range field in the LTConfig struct? This will come into play now. range is defined as NUM_BYTES*8 (basically the decimal range in which the LHS and RHS will lie)

This difference is calculated using the following high level logic:

if lhs < rhs: 
    difference = lhs - rhs + range
else
    difference = lhs - rhs

What this logic does is that it prevents overflow by adding range in case lhs<rhsand this comes in handy when constraining the circuit as well.

Now, we constrain the "larger" circuit with the following conditions:

1. Check the fact that, given inputs lhs and rhs to the circuit, lhs - rhs - difference + (range*lt) == 0

2. The lt value is a boolean.

So what's the issue?

We use this gadget in Summa, and the main issue here is that this 'horizontal' approach results in a huge number of advice columns.

Specifically, for our use case, N_BYTES = 31 and hence this results in 31 advice columns for difference in the LTChip alone. We need to reduce this to 3.