varSubArray_100.circom

pragma circom 2.1.2;

include "circomlib/comparators.circom";

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

    component isWithinStartEndRange[n];
    component quinSelector[n];
    component modulo[n];

    var y = 0;
    var z = start;
    while(y < n){

        // fetch value with index z modulo n from array in
        quinSelector[y] = QuinSelector(n);
        modulo[y] = Modulo(n);
        var k;
        for (k=0; k<n; k++) {
            quinSelector[y].in[k] <== in[k];
        }
        modulo[y].in <== z;
        quinSelector[y].index <== modulo[y].out;

        // evaluate whether the index z is within the range [start, end)
        isWithinStartEndRange[y] = IsWithinStartEndRange();
        isWithinStartEndRange[y].index <== z;
        isWithinStartEndRange[y].end <== end;

        // if it is in the range add the corresponding value to the out array, if not add 0
        out[y] <== quinSelector[y].out * isWithinStartEndRange[y].flag;
        y++;
        z++;
    }     
}

template QuinSelector(choices) {
    signal input in[choices];
    signal input index;
    signal output out;

    // Ensure that index < choices
    component lessThan = LessThan(10);
    lessThan.in[0] <== index;
    lessThan.in[1] <== choices;
    lessThan.out === 1;

    component calcTotal = CalculateTotal(choices);
    component eqs[choices];

    // For each item, check whether its index equals the input index.
    for (var i = 0; i < choices; i ++) {
        eqs[i] = IsEqual();
        eqs[i].in[0] <== i;
        eqs[i].in[1] <== index;

        // eqs[i].out is 1 if the index matches. As such, at most one input to
        // calcTotal is not 0.
        calcTotal.nums[i] <== eqs[i].out * in[i];
    }

    // Returns 0 + 0 + ... + item
    out <== calcTotal.sum;
}

// This circuit returns the sum of the inputs.
// n must be greater than 0.
template CalculateTotal(n) {
    signal input nums[n];
    signal output sum;

    signal sums[n];
    sums[0] <== nums[0];

    for (var i=1; i < n; i++) {
        sums[i] <== sums[i - 1] + nums[i];
    }

    sum <== sums[n - 1];
}

// This circuit takes an input (in) and return in mod n.
template Modulo(n) {
    signal input in;
    signal q;
    signal output out;

    out <-- in%n;
    q <-- in\n; //where '\' is the integer division operator
    in === q*n + out; //this works!

}

template IsWithinStartEndRange() {

    signal input index;
    signal input end;

    signal output flag;

    component lessThan = LessThan(10);

    lessThan.in[0]<== index;
    lessThan.in[1]<== end;

    flag <== lessThan.out;

}

component main = VarSubarray(100);

/* INPUT = {
    "in": [
  55, 45, 71, 36, 24, 72, 77,  9,  3,  3, 37, 37,
  67, 83, 18, 69, 12,  1, 89, 97, 45, 17, 40, 27,
  92, 10, 37, 77, 45,  2, 39, 15, 60, 72, 30, 66,
  73, 63, 14, 17, 51, 20, 41, 91, 23, 29, 60, 60,
  29, 31, 11, 13, 20, 26, 18, 31, 82, 50, 81, 33,
  18, 21, 94, 73, 84, 77, 17,  6, 96,  9, 16, 41,
   7, 57, 46, 58, 49, 97, 41, 65,  4, 13, 78, 19,
   9, 15, 93, 62, 10, 64, 95,  4, 47, 92, 33, 93,
  29, 49, 92, 17
],
    "start": 4,
    "end" : 12
} */

varSubArray_100.md

Open this in zkREPL →

This file can be included into other zkREPLs with include "gist:6ab5ca19e0aa9d37cd8f5371afae52af";