Conditional Statements

The misleading inclusion of the "if" statement in Circom, and the use of multiplexers to actually compute branching logi

If you go by the Circom docs, you will be mislead into believing you can quickly create conditional, branching logic using the if operand. This is one of the quickest ways to run into an Error: non-quadratic constrains not allowed! error. In this section, we will explain the use of Multiplexers in Circom to accomplish branched logic.

What is a Multiplexer?

Time-Division Multiplexer for Analog TV Channels http://www.gordostuff.com/2011/11/digital-multiplexing-time-division.html

A multiplexer, AKA "MUX", is a way to pass multiple signals through a single interface. In electrical engineering, one use of a a multiplexer is to encode many different TV channels into a single stream of data for transmission where the recipient can multiplex between channels for their desired output signal. A multiplexer in an arithmetic circuit is similar- it allows us to take multiple different signals as input, outputting only one chosen input signal.

Why do I Care About Multiplexers?

Use of if statements will quickly cause circuits that have non-quadratic constraints. This is a consequence of trying to compute one branch of logic without trying to compute the other branch. Essentially, in Circom you must compute all conditional branches of logic and multiplex them to choose the branch you want to proceed with. This is undoubtedly quite expensive, especially as the need for conditional branching switches from binary "if" statements to something closer to a "switch case". Nonetheless, multiplexing between N possibilities is entirely feasible. Circomlib contains multiple different MUX types showing up to 4 orders- if you really need more than 16 potential branches, you can explore how the underlying MultiMux template might be resized for your needs. This is likely only in the case of extreme switch cases and would likely be highly inefficient if further conditional / branching logic was applies from this point without R&D.

Example

Here we provide an example of how one might (incorrectly) attempt to do conditional logic with a Battleship game's hit detection, as well as the correct way to multiplex conditional logic in this case.

See the circomlib > Multiplexing section for more information on the application of multiplexers in the wild.

Multiplexing

Incorrect Conditional Logic Computation

DO NOT DO THIS!!!!

template HitShip(n) {

    signal input ship[3]; // x, y, z to hitscan from
    signal input shot[2]; // x, y, to hitscan with
    signal output hit; // 0 if not hit, 1 if hit
    
    var _hit = 0;
    if (ship[2] == 0) {
        for (var i = 0; i < n; i++) {
            var _x = (ship[0] + i == shot[0]);
            var _y = (ship[1] == shot[1]);
            _hit += 1 * (_x == 1 && _y == 1);
        }
    } else {
        for (var i = 0; i < n; i++) {
            var _x = (ship[0] == shot[0]);
            var _y = (ship[1] + i == shot[1]);
            _hit += 1 * (_x == 1 && _y == 1);
        }
    }
    hit <== _hit;
}

Correct Conditional Logic Computation

DO THIS!!!!

template HitShip(n) {

    signal input ship[3]; // x, y, z to hitscan from
    signal input shot[2]; // x, y, to hitscan with
    signal output hit; // 0 if not hit, 1 if hit

    /// COMPUTE HORIZONTAL SHIP ORIENTATION HIT SCAN CASE
    var hHit = 0;
    for (var i = 0; i < n; i++) {
        var _x = (ship[0] + i == shot[0]);
        var _y = (ship[1] == shot[1]);
        hHit += 1 * (_x == 1 && _y == 1);
    }
    /// COMPUTE VERTICAL SHIP ORIENTATION HIT SCAN CASE
    var vHit = 0;
    for (var i = 0; i < n; i++) {
        var _x = (ship[0] == shot[0]);
        var _y = (ship[1] + i == shot[1]);
        vHit += 1 * (_x == 1 && _y == 1);
    }

    /// MUX TO CONDITIONALLY SELECT SHIP ORIENTATION HIT SCAN
    component mux = Mux1();
    mux.c[0] <-- hHit; // assign
    mux.c[1] <-- vHit;
    mux.s <== ship[2];
    hit <== mux.out;
}