about_zkrepl.md

Open this in zkREPL →

This file can be included into other zkREPLs with include "gist:1687b3393262984ed9c46f8146e5ae90";

main.circom

pragma circom 2.1.4;

include "circomlib/comparators.circom";

/*

Inputs:
---------
- in: Array of tuples
- match: Arbitrary value that defines a match condition 

Outputs:
---------
- num_match: Number of elements of `in` whose first entry matches `match`
- out: Array of tuples in which the first `num_match` entries are the tuples in `in` for which the `match` condition is satisfied
The remaining entries are 0-padded

Functionality:
--------------
1. Find the indexes of `in` that satisfies the `match` condition
2. Start a loop for each element of `in`
3. For each loop round find the next available matching tuple and sequentially add it to `out`. When there are no longer matching tuples pad `out` with 0.
4. At the end of each loop round increase `num_match_added_to_out` if and only if a matching tuple was added to `out`
5. After the loop has ended, assign the value of the variable `num_match_added_to_out` to `num_match`

Number of non-linear constraints (per instantiation): 
--------------
40200

*/
template Filter () {
    signal input in[100][2];
    signal input match;    
    signal output num_match;
    signal output out[100][2];

    signal matching_indexes[100];

    component find_matching_indexes = FindMatchingIndexes();

    for(var i=0; i<100; i++) {
        find_matching_indexes.in[i] <== in[i][0];
    }

    find_matching_indexes.match <== match;

    matching_indexes <== find_matching_indexes.out;

    var num_match_added_to_out;

    component perform_assignment_cycle[100];

    for(var i=0; i<100; i++) {

        perform_assignment_cycle[i] = PerformAssignmentCycle();
        perform_assignment_cycle[i].num_match_added_to_out <== num_match_added_to_out;

        for(var z=0; z<100; z++) {
            perform_assignment_cycle[i].in[z][0] <== in[z][0];
            perform_assignment_cycle[i].in[z][1] <== in[z][1];
        }

        perform_assignment_cycle[i].matching_indexes <== matching_indexes;

        out[i][0] <== perform_assignment_cycle[i].tuple_to_assign[0];
        out[i][1] <== perform_assignment_cycle[i].tuple_to_assign[1];

        num_match_added_to_out += perform_assignment_cycle[i].new_match_added;    
    }

    num_match <== num_match_added_to_out;
}

/*

Inputs:
---------
- in: Array of values
- match: Arbitrary value that defines a match condition 

Outputs:
---------
- out: Array of binary values. 
A `0` value at index `i` of the array indicates that the matching condition is not satisfied at index `i`
A `1` value at index `z` of the array indicates that the matching condition is satisfied at index `z`

Functionality:
--------------
1. Start a loop for each element of `in`
2. For each loop check that `in[i]` is equal to `match`
3. Assign the binary output to `out[i]`

Number of non-linear constraints (per instantiation): 
--------------
200

*/
template FindMatchingIndexes() {
    signal input in[100];
    signal input match; 
    signal output out[100];

    component is_equal[100];

    for(var i=0; i<100; i++) {

        is_equal[i] = IsEqual ();

        is_equal[i].in[0] <== in[i];
        is_equal[i].in[1] <== match;

        out[i] <== is_equal[i].out;
    }
}

/*

Inputs:
---------
- num_match_added_to_out: Indicates the number of matching tuples added to `out` up to this point
- in: Array of tuples
- matching_indexes: Array of binary values

Outputs:
---------
- tuple_to_assign: Tuple to be assigned to `out. If no matching condition was found, it is a 0-padded tuple
- new_match_added: Binary value that indicates if a new matching condition was found or not in the cycle

Functionality:
--------------
1. Start a loop for each element of `in`
2. For each loop round increase the variable `num_match_spotted_in_cycle` by 1 if and only if the corresponding index is a match
3. For each loop round verify that a matching condition was found and, if, verify that the corresponding tuple hasn't been added to `out` yet
4. If a new matching condition was found, add the corresponding tuple to the running sum. If no matching condition was found, add a 0-padded tuple to the running sum
5. Increase the `new_match` variable by 1 if and only if a new matching condition was found.
6. Increase the `num_match_spotted_in_cycle` by 1 if and only if a new matching condition was found. This is a trick added to avoid that the `is_new_match`
condition would be satisfied for two consecutive loop rounds in the case in which a matching tuple is followed by a non-matching tuples.
In particular, `is_new_match` would return true in that case. Consider that we only want to find 1 new matching condition per assignment cycle, increasing 
`num_match_spotted_in_cycle` by 1 after the first matching condition was found, would guarantee that `is_new_match` would never return true again for that cycle.

Number of non-linear constraints (per instantiation): 
--------------
400

*/

template PerformAssignmentCycle() {

    signal input num_match_added_to_out;
    signal input in[100][2];
    signal input matching_indexes[100];

    signal output tuple_to_assign[2];
    signal output new_match_added;

    component is_new_match[100];

    var num_match_spotted_in_cycle;
    var new_match;

    component running_sum = RunningSum();

    for(var z=0; z<100; z++) {

        num_match_spotted_in_cycle += matching_indexes[z];

        is_new_match[z] = IsNewMatch();

        is_new_match[z].num_match_spotted_in_cycle <== num_match_spotted_in_cycle;
        is_new_match[z].num_match_added_to_out <== num_match_added_to_out;

        running_sum.in[z][0] <== in[z][0] * is_new_match[z].out;
        running_sum.in[z][1] <== in[z][1] * is_new_match[z].out;

        new_match += is_new_match[z].out;
        num_match_spotted_in_cycle += is_new_match[z].out;
    }

    tuple_to_assign[0] <== running_sum.out[0];
    tuple_to_assign[1] <== running_sum.out[1];

    new_match_added <== new_match;
}

/*

Inputs:
---------
- in: Array of tuples

Outputs:
---------
- out: Tuple

Functionality:
--------------
1. Initialize an intermediate signal `partial_sum` to the value of the first tuple of `in`
2. Start a loop for each element of `in` starting from 1
3. For each loop round add the current tuple of `in` to `partial_sum`. In particular the running sum:
- adds the first element of the tuple to the previous first element of `partial_sum` 
- adds the second element of the tuple to the previous second element of `partial_sum`
4. Assign the accumulated `partial_sum` after the last loop round to `out` tuple

Number of non-linear constraints (per instantiation): 
--------------
2

*/

template RunningSum() {
    signal input in[100][2];
    signal output out[2];

    signal partial_sum[100][2];
    partial_sum[0][0] <== in[0][0];
    partial_sum[0][1] <== in[0][1];

    for (var i=1; i < 100; i++) {
        partial_sum[i][0] <== partial_sum[i - 1][0] + in[i][0];
        partial_sum[i][1] <== partial_sum[i - 1][1] + in[i][1];
    }

    out[0] <== partial_sum[100 - 1][0];
    out[1] <== partial_sum[100 - 1][1];
}

/*

Inputs:
---------
- num_match_spotted_in_cycle: Value that indicates the number of matching conditions spotted in the cycle
- num_match_added_to_out: Value that indicates the number of matching tuples added to `out`

Outputs:
---------
- out: A binary value that indicates if a tuple that hasn't been added to `out` yet was found

Functionality:
--------------
1. Evaluate if the expression `num_match_spotted_in_cycle - num_match_added_to_out` is equal to 1. 
If this expression equals to 1, it means that the next available matching tuple was spotted.
2. Assign the binary result of the evaluation to `out` 

Number of non-linear constraints (per instantiation): 
--------------
2

*/
template IsNewMatch () {
  signal input num_match_spotted_in_cycle;
  signal input num_match_added_to_out;
  signal output out;

  component is_equal = IsEqual();

  is_equal.in[0] <== num_match_spotted_in_cycle - num_match_added_to_out;
  is_equal.in[1] <== 1;

  out <== is_equal.out;
}

component main  = Filter();

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