Multiplexing

MANDATORY use of the first party conditional signal selector. Do not skip!

For a detailed explanation on why you *need* to use multiplexers, visit the Circom Language > Conditional Statements section:

pageConditional Statements

Conventions

Given N in a gadget MuxN, you can consider the multiplexer to have the following properties:

• N selectors used to to toggle between signals

• 2^n possible input signals

There will always be a single output signal. Given the overwhelming need for Mux1() for general computation where higher order multiplexers are niche, the rest of the section will only consider the use of a 2 input multiplexer. As mentioned in the Conditional Statements section, use of higher order multiplexers could facilitate the need for something like a switch case.

Mux1

There has been a lot of use of multiplexers around this GitBook, so we will keep this example short and to the point. At the risk of beating a dead horse, we want to reiterate that MUX1 IS A REQUIREMENT FOR COMPUTING BINARY CONDITIONAL LOGIC IN CIRCOM.

The mux1.circom component provides a relatively simple interface for a developer to input two signals and return one or the other based on a boolean condition (selector). In order to avoid non-quadratic expressions as cryptically explained in the official Circom docs, a developer using the Circom DSL must entirely compute both branches to their resulting end signal value, then use the multiplexer to toggle between the two signals based on a specific case. The component is shown below:

template Mux1() {
    var i;
    signal input c[2];  // Constants
    signal input s;   // Selector
    signal output out;

    component mux = MultiMux1(1);

    for (i=0; i<2; i++) {
        mux.c[0][i] <== c[i];
    }

    s ==> mux.s;

    mux.out[0] ==> out;
}

This simple gadget can quickly be extended in your code base to facilitate most branching logical conclusions as is expected of a turing-complete programming language. For instance, BattleZips V1 makes use of a multiplexer to choose between the horizontal and vertical axis when compute whether a shot intersects with a ship placement. This is shown in the helper hitShip.circom component:

hitShip.circom

pragma circom 2.0.3;

include "../../../node_modules/circomlib/circuits/mux1.circom";
include "../../../node_modules/circomlib/circuits/bitify.circom";


/*
    Determine whether or not a given ship uses a given x/y coordinate pair
    @param n - the length of the ship
*/
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

    /// HORIZONTAL CONSTRAINT ///
    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);
    }
    /// VERTICAL CONSTRAINT ///
    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 CHOOSE OUTPUT ///
    component mux = Mux1();
    mux.c[0] <-- hHit;
    mux.c[1] <-- vHit;
    mux.s <== ship[2];
    hit <== mux.out;
}

Consider the goal of having ships that can be placed either horizontally or vertically. Given the carrier ship (length 5, 0th index in 5-tuple) placed vertically on the board at (7, 7). This data can be represented as a 3-tuple (x, y, z) where the order inclusion of the ship 3-tuple in the board 5-tuple (see Examples > BattleZips V1) encodes the length of the ship.

Diagram of a case where multiplexing allows us to discard invalid state and choose valid state Z is 1, meaning the ship placement is valid. if Z were 0, the placement would extend off the board.

The placeShip.circom code computes whether or not a ship placement is legal according to our own (arbitrarily defined to our needs) rules. In the BattleZip rule set, ignoring the concept of ship collisions, all cells covered by a ship placement must be within the 10x10 grid. Therefore, situations like the above diagram arise.

As is shown in placeShip.circom or hitShip.circom, we compute both the horizontal and vertical collision and boundary checks. At /// MUX TO CHOOSE OUTPUT /// the z coordinate for the ship placement is used as the Mux1() selector, properly outputting the signal that passes constraints while discarding the signal that fails. Of course, we expect this property to hold in the reverse direction as well, constraining proof generation based on the z axis.

The BattleZips V1 circom-tester test/circuits.js unit testing proves the intended functionality of using Mux1() in shot proofs for horizontal/ verital ship orientation:

Multiplexed Logic Circuit Unit Test

it("Prove valid turn 5: horizontal muxxed miss with vertical hit", async () => {
    // demonstrate miss computation even if z=1 collision when z = 0
    const ships = [
        [1, 1, 1],
        [5, 1, 1],
        [4, 4, 1],
        [1, 7, 1],
        [3, 8, 0]
    ]
    const hash = await mimcSponge.multiHash(ships.flat())
    const shot = [2, 1]
    const hit = 0
    const witness = await shotCircuit.calculateWitness({
        ships,
        hash: F.toObject(hash),
        shot,
        hit
    })
    await shotCircuit.assertOut(witness, {})
})

Intra-Circuit Incremental State Building

"Intra-Circuit Incremental State Building" is quite verbose. Put more directly:

• Iterative/ loop over data repeatedly with potentially different parameters each time

• Mutate stored state each time such that a new loop's beginning picks up where previous loop left off

• All computation is contained within a main component (top level ZK circuit)

Beyond the z axis orientation multiplexer, Mux1() is the interface by which conditional state updates computed in Zero Knowledge are communicated between iterations of the placeShip.circom component. Consider the snippet of this component where the two conditions are computed and then multiplexed:

template PlaceShip(n) {
.
.
.
    /// HORIZONTAL PLACEMENT COLLISION CHECK ///
    for (var i = 0; i < n; i++) {
        boardH[ship[0] + i][ship[1]] += 1;
        var cellVal = boardH[ship[0] + i][ship[1]];
        hCollision.in[i] <-- cellVal * (cellVal - 1) == 0;
    }
    /// VERTICAL PLACEMENT COLLISION CHECK ///
    for (var i = 0; i < n; i++) {
        boardV[ship[0]][ship[1] + i] += 1;
        var cellVal = boardV[ship[0]][ship[1] + i];
        vCollision.in[i] <-- cellVal * (cellVal - 1) == 0;
    }
    /// MUX TO CHOOSE CONSTRAINT ///
    collisionMux.c[0] <== hCollision.out;
    collisionMux.c[1] <== vCollision.out;
    collisionMux.s <== ship[2]; // z coordinate as selector for horizontal/ vertical
    collisionMux.out === expectedCollision.out; // expect 1 if all placements have binary values (no collisions, < 2)
    
    /// ##### INTRA-CIRCUIT STATE MUX HERE ###
    // numberify bitmap
    component toNumH = Bits2Num(100); // horizontal board Bits2Num
    component toNumV = Bits2Num(100); // vertical board Bits2Num
    for (var i = 0; i < 100; i++) {
        toNumH.in[i] <-- boardH[i \ 10][i % 10];
        toNumV.in[i] <-- boardV[i \ 10][i % 10];
    }
    // mux boards to get next state
    boardMux.c[0] <== toNumH.out;
    boardMux.c[1] <== toNumV.out;
    boardMux.s <== ship[2];
    boardOut <== boardMux.out;

Given the board placement computations above, the last "paragraph" of the circuit handles the conditional selection of the horizontal or vertical board signal as generated in a 10x10 variable array, encoded by Bits2Num. Using the multiplexer, we are able to witness a conditional commitment to some encoded piece of data, then work with that new state on the next loop/ increment.