# Variable Length Subarray Selection in Circom

by [Namra Patel](twitter.com/namrajpatel), February 27th, 2023, Waterloo, Canada.

## Task

Write a circom circuit that constrains variable length subarray selection. Use the following template:

// start, end lie in [0, 1000)
// the first values of out are the values at indices [start, end) of in
// the remainder of out is 0-padded
template VarSubarray() {
    signal input in[1000];
    signal input start;
    signal input end;
    
    // Fill in your solution here
    
    signal output out[1000];
}

## Solution

The task requires us to constrain three main things so we'll break the solution into three parts to handle each of the three constraints. The final circuit code is provided at the bottom of this document.

### Part 1: Selecting a Variable Length of Indices from an Array

In Circom, input signals are unknown at constraint time and as such cannot be used as conditionals in if statements or for things like array indexing. This means that we cannot trivially loop through the entire `in` array and copy elements into the `out` array when the loop is between `start` and `end`.

**Array element selection in Circom**

Instead, we can write a short circuit called `AtIndex` that takes the `in` array, and an `index` that we want to select from that array, and returns the element at that index in its output using a clever technique where we:
- Loop over the indexes of the array
- Check if the index the loop is at is equal to the index we are looking for by using the [`IsEqual` comparator circuit](https://github.com/iden3/circomlib/blob/cff5ab6288b55ef23602221694a6a38a0239dcc0/circuits/comparators.circom#L37)
- Pass `isEqual * array[i]` into the `CalculateTotal` circuit's `in[]` array
- The `CalculateTotal` circuit will sum all the elements in its `in[]` array, and return the sum. This means it will sum `0 + 0 + ... + ourSelection` and thus return the element at the `index` provided to the `AtIndex` circuit
- Return the sum from `CalculateTotal` (the element we were looking for)

This is essentially a clever technique that lets us overcome the limitation in Circom where we cannot index arrays using signals. Instead we simply use helper circuits that sum all the signals in the array multiplied by whether their index is equal to the target index we are looking for.

**Variable length element selection**

Now that we know how to select one element from our array, the question becomes, how can we select a variable number of elements between a start and end index provided as signals?

We do the following:
- Loop over the entire 1000 index array
- For each index, check if we are within the range of `end - start` where we want to select the subarray, or outside of it where we want to 0-pad, using the `LessThan` comparator circuit
- ```
rangeChecks[i] = LessThan(10);
rangeChecks[i].in[0] <== start + i;
rangeChecks[i].in[1] <== end;

- For each index, use the `AtIndex` circuit to retrieve the value at that index, then multiply that selection by whether or not we were within the range of the subarray indices, and set that value to out[i]
    - ```
        // If we are out of (end - start) range, out[i] <== 0
        // If we are in the range, out[i] <== our selection
        out[i] <== selections[i].out * rangeChecks[i].out; 

- The result of this is an `out[1000]` array where the subarray that we wanted to select is left aligned and the remainder of the indices are 0-padded.

### Part 2: Require that `start` >= 0

The second requirement of our task is that the input signal `start` is greater than or equal to 0. We can constrain this simply by using the `GreaterEqThan` comparator circuit and checking that `start` is greater than or equal to 0 as follows:

// Require that start >= 0
component startCheck = GreaterEqThan(10);
startCheck.in[0] <== start;
startCheck.in[1] <== 0;
startCheck.out === 1;

We initialize the `GreaterEqThan` with 10 bits because we want to support numbers up to from 0-1000.

### Part 3: Require that `end` < 1000

The last requirement of our task is that the input signal `end` is less then 1000. We can constrain this by using the `LessThan` comparator circuit and requiring that end` is less then 1000` as follows:

 // Require that end < 1000
    component endCheck = LessThan(10);
    endCheck.in[0] <== end;
    endCheck.in[1] <== 1000;
    endCheck.out === 1;

We initialize the `LessThan` with 10 bits because we want to support numbers up to from 0-1000.

### Potential improvements

One very obvious and meaningful improvement that could be made to this implementation, given more time and knowledge, is by not requiring the main for-loop to execute 1000 times regardless of how large the subarray we are selecting is. In my current implementation, if the subarray is 10 integers long, the loop only **needs** to run 10 times for the task to be complete, but I have made the for-loop run 1000 times regardless of length to handle the edge case that a user wants to select a very large subarray—up to 1000 integers in length.

I've left it this way because I don't yet know how to make the for-loop run only the amount of times required by subarray length in Circom, but surely this can be done and offer extrordinary improvements in time complexity.

### Final circuit

Note: In my experience the REPL can be buggy with my circuit, it often runs out of memory because it is unoptimized. If you want to ensure that the code does work, change the number "1000" to "50" (or the length of the subarray you're looking for) in line 46. The circuit will run relatively fast at that point.

[REPL Link](https://zkrepl.dev/?gist=0142031001199409901cb414ade2b909)

pragma circom 2.1.2;

include "circomlib/comparators.circom";

template CalculateTotal(N) {
    signal input in[N];
    signal output out;

    signal outs[N];
    outs[0] <== in[0];

    for (var i=1; i < N; i++) {
        outs[i] <== outs[i - 1] + in[i];
    }

    out <== outs[N - 1];
}

template AtIndex(N) {
    signal input array[N];
    signal input index;

    signal output out;

    component result = CalculateTotal(N);
    for (var i = 0; i < N; i++) {
        // Check if i == index
        var isEqual = IsEqual()([i, index]); 
        // Pass the element in as non-zero value if isEqual == true
        result.in[i] <== isEqual * array[i]; 
    }

    out <== result.out; // Return the 
}

template VarSubarray() {
    signal input in[1000];
    signal input start;
    signal input end;
    signal output out[1000];

    // Select the elements at the indexes between start and end, and 0-pad the rest
    component selections[1000];
    component rangeChecks[1000];

    for(var i = 0; i < 1000; i++) {
        // Check that start + i < diff
        rangeChecks[i] = LessThan(10);
        rangeChecks[i].in[0] <== start + i;
        rangeChecks[i].in[1] <== end;

        // Get the element at index: start + i
        selections[i] = AtIndex(1000);
        selections[i].array <== in;
        selections[i].index <== start + i;

        // If we are out of (end - start) range, out[i] <== 0
        // If we are in the range, out[i] <== our selection
        out[i] <== selections[i].out * rangeChecks[i].out; 
    }
    
    // Require that start >= 0
    component startCheck = GreaterEqThan(10);
    startCheck.in[0] <== start;
    startCheck.in[1] <== 0;
    startCheck.out === 1;

    // Require that end < 1000
    component endCheck = LessThan(10);
    endCheck.in[0] <== end;
    endCheck.in[1] <== 1000;
    endCheck.out === 1;
}

component main { public [ in, start, end ] }  = VarSubarray();

/* INPUT = {
    "in": ["5", "4", "8", "9", "6", "2", "1", "6", "6", "2", "5", "1", "1", "4", "5", "3", "1", "4", "8", "9", "2", "4", "8", "5", "7", "5", "2", "2", "8", "9", "8", "4", "7", "5", "9", "2", "3", "9", "7", "6", "7", "3", "6", "2", "9", "4", "4", "6", "9", "8", "7", "2", "8", "4", "5", "3", "1", "8", "4", "9", "4", "3", "3", "9", "7", "1", "5", "5", "6", "3", "7", "5", "4", "6", "6", "1", "2", "1", "8", "6", "9", "4", "8", "2", "3", "1", "1", "7", "9", "4", "9", "6", "1", "7", "2", "9", "6", "5", "1", "4", "7", "9", "5", "3", "4", "6", "6", "9", "7", "6", "6", "3", "6", "1", "7", "6", "7", "6", "8", "9", "3", "7", "4", "3", "9", "7", "2", "8", "7", "8", "6", "9", "3", "2", "1", "6", "8", "3", "5", "7", "2", "6", "3", "1", "2", "9", "6", "7", "6", "2", "4", "4", "1", "1", "6", "3", "5", "7", "1", "1", "9", "9", "8", "7", "3", "3", "3", "3", "6", "6", "9", "9", "7", "1", "9", "6", "5", "8", "9", "8", "5", "5", "8", "1", "6", "8", "4", "8", "2", "2", "7", "2", "5", "3", "4", "2", "9", "8", "4", "2", "1", "8", "8", "5", "3", "4", "7", "1", "1", "5", "7", "3", "6", "1", "5", "1", "1", "1", "2", "7", "5", "5", "2", "3", "8", "7", "3", "9", "8", "1", "7", "1", "3", "5", "2", "7", "5", "4", "2", "8", "3", "1", "9", "1", "9", "7", "9", "6", "2", "4", "2", "7", "6", "9", "1", "3", "1", "9", "9", "2", "8", "9", "1", "4", "7", "4", "2", "7", "7", "1", "7", "7", "9", "5", "9", "1", "1", "2", "8", "6", "6", "7", "8", "6", "6", "3", "1", "7", "3", "3", "8", "5", "8", "1", "9", "7", "6", "2", "5", "2", "8", "1", "4", "8", "8", "5", "6", "4", "2", "5", "7", "2", "7", "7", "7", "3", "7", "9", "8", "7", "2", "9", "1", "7", "9", "3", "6", "9", "7", "7", "8", "9", "6", "2", "7", "4", "2", "6", "7", "3", "5", "6", "5", "2", "3", "4", "2", "6", "5", "7", "5", "6", "4", "2", "1", "9", "2", "6", "2", "4", "4", "7", "7", "7", "6", "5", "9", "4", "3", "6", "6", "9", "6", "5", "7", "6", "3", "8", "4", "4", "4", "2", "4", "1", "3", "7", "7", "1", "3", "1", "6", "7", "7", "8", "5", "4", "4", "1", "3", "3", "3", "8", "1", "8", "9", "4", "2", "4", "7", "5", "5", "8", "7", "2", "2", "9", "7", "1", "9", "6", "3", "2", "7", "7", "7", "6", "3", "1", "6", "6", "6", "4", "1", "7", "7", "3", "9", "2", "1", "5", "7", "7", "1", "3", "6", "2", "1", "2", "1", "4", "5", "3", "2", "1", "7", "1", "6", "9", "1", "9", "3", "7", "4", "7", "5", "8", "1", "6", "9", "7", "6", "7", "4", "8", "9", "9", "3", "1", "7", "6", "5", "6", "1", "5", "5", "8", "9", "1", "4", "4", "6", "8", "8", "8", "2", "8", "6", "6", "2", "7", "7", "5", "5", "1", "3", "6", "7", "3", "1", "3", "1", "9", "6", "6", "4", "3", "8", "2", "9", "4", "6", "5", "4", "8", "5", "4", "7", "9", "2", "1", "9", "6", "3", "8", "5", "7", "7", "9", "2", "3", "1", "3", "1", "2", "7", "6", "1", "5", "5", "6", "7", "3", "5", "8", "3", "2", "5", "1", "1", "5", "3", "2", "7", "2", "6", "1", "4", "8", "6", "1", "7", "3", "5", "8", "6", "3", "9", "1", "6", "1", "8", "8", "4", "4", "6", "2", "2", "9", "4", "8", "9", "6", "1", "8", "7", "9", "2", "7", "5", "6", "1", "3", "3", "7", "4", "9", "4", "9", "1", "3", "3", "1", "1", "7", "2", "4", "5", "5", "4", "6", "6", "9", "4", "7", "6", "4", "3", "5", "9", "2", "9", "9", "1", "8", "1", "5", "7", "9", "3", "5", "1", "8", "7", "7", "4", "4", "6", "7", "2", "1", "8", "4", "6", "1", "8", "6", "6", "7", "9", "5", "7", "7", "4", "6", "8", "6", "8", "3", "1", "7", "3", "3", "1", "6", "9", "9", "9", "4", "8", "7", "1", "9", "1", "7", "5", "7", "3", "7", "7", "9", "7", "6", "5", "3", "6", "6", "4", "6", "9", "9", "7", "8", "8", "7", "8", "2", "3", "8", "2", "6", "5", "9", "8", "6", "3", "2", "5", "5", "4", "3", "2", "4", "3", "9", "2", "2", "5", "2", "7", "4", "7", "6", "9", "7", "8", "5", "2", "9", "4", "9", "9", "3", "4", "3", "7", "4", "9", "9", "8", "2", "8", "8", "5", "4", "4", "5", "7", "1", "4", "1", "4", "4", "8", "4", "9", "2", "2", "2", "8", "2", "1", "1", "8", "3", "7", "6", "5", "1", "7", "6", "8", "3", "3", "6", "3", "3", "2", "2", "1", "8", "6", "4", "9", "6", "8", "4", "5", "7", "5", "1", "4", "1", "6", "6", "4", "8", "5", "6", "6", "5", "9", "8", "1", "7", "5", "4", "4", "7", "2", "2", "3", "2", "7", "5", "4", "5", "1", "5", "7", "8", "3", "7", "8", "1", "2", "4", "4", "5", "6", "4", "1", "1", "8", "9", "8", "4", "1", "1", "7", "1", "9", "5", "1", "5", "9", "3", "9", "5", "5", "4", "7", "8", "4", "7", "3", "7", "1", "7", "9", "5", "9", "5", "3", "8", "3", "9", "8", "1", "8", "6", "5", "6", "9", "7", "2", "9", "5", "2", "6", "7", "6", "5", "1", "8", "2", "4", "4", "8", "4", "2", "5", "3", "5", "8", "2", "4", "1", "8", "4", "3", "4", "8", "3", "8", "7", "6", "7", "4", "8", "1", "9", "4", "7", "5", "7", "7", "8", "4", "2", "6", "3", "2", "8", "9", "2", "7", "1", "2", "1", "5", "9", "9", "5", "3", "7", "7", "1", "3", "9", "3", "8", "7", "7", "2", "2", "5", "4", "1", "5", "1", "5", "8", "8", "2", "4", "4", "1", "5", "4", "2", "1", "3", "5", "6", "1", "7", "2", "1", "1", "2", "7", "5", "5", "6", "4", "3", "4", "8", "7", "3", "9", "7", "4", "1", "2", "5", "8", "8", "4", "7"],
    "start": "10",
    "end": "20"
} */