## Problem Statement

This puzzle is to write a Circom circuit constraining filtering from an array of tuples. The objective is to minimize the non-linear constraint count.

This writeup explains my thinking process and the solution.

The template to fill:

// Inputs:
// * `in` is a fixed length array of 100 tuples
// * `match` is a arbitrary input value
// Outputs:
// * `num_match` is the number of elements of `in` whose first entry 
//   matches `match`
// * the first `num_match` entries of `out` are the tuples in `in` 
//   whose first entry agrees with `match`.  the remaining entries
//   in `out` are 0-padded.
template Filter() {
    signal input in[100][2];
    signal input match;
    
    // Fill in your solution here
    
    signal output num_match;
    signal output out[100][2];
}

Note that there is no requirement to preserve the order of the matched tuples in `out`. For example, if `in` is `[[1,2], [3,4], [1,5]]` and `match` is `1`, then both

* `[[1,2], [1,5], [0,0]]`
* `[[1,5], [1,2], [0,0]]`

should be correct `out` values

## Approach

The approach is to break the problem into two sub-problems:

1. Find a matching tuple in array
2. Remove a matching tuple from array

By repeating these steps, we will extract all matching tuples from the input array.

## Step 1: Finding a matching tuple
### Template parameters
I started with writing a template that finds and returns one matching tuple from the input array.

A tuple is an order pair of two numbers, and the goal is to find a tuple whose first entry agrees with `match` in the input array of tuples `n`:

template FindTuple(n) {
    signal input in[n][2];
    signal input match;
    
    // Find a tuple `x` in the array `in` of size n 
    // such that x[0] == `match`

    signal output value; // output the tuple's second entry
    signal output index; // output the tuple's index in `n`
}

To make this template more generic, I added `tuple_i` ("tuple index") parameter.

`tuple_i` is an index of the tuple's element that the template searches against. `tuple_i` must be either zero or one. Because the task is to filter against the first entry, `tuple_i` will be set to zero. Introducing `tuple_i` parameter has no effect on the number of constraints.

A generic version of `FindTuple` template:

template FindTuple(n, tuple_i) {
    signal input in[n][2];
    signal input match;
    
    // Find a tuple `x` in the array `in` of size n 
    // such that x[tuple_i] == `match`

    signal output value; // output the tuple's (1-tuple_i) entry
    signal output index; // output the tuple's index in `n`
}

The implementation of `FindTuple` uses two running arrays `match_index` and `match_value` to keep track of the found tuples' indices and values. The last elements of these arrays are returned as output. As a result, `FindTuple` always returns the index and value of the _last_ found tuple.

template FindTuple(n, tuple_i) {
    signal input in[n][2];
    signal input match;

    signal match_index[n+1];
    signal match_value[n+1];
    
    match_index[0] <== n;
    match_value[0] <== 0;

    component eq[n];
    for (var i = 0; i < n; i ++) {
        eq[i] = IsEqual();
        eq[i].in[0] <== match;    
        eq[i].in[1] <== in[i][tuple_i];
				
        match_index[i+1] <== match_index[i] + eq[i].out * (i - match_index[i]);
        match_value[i+1] <== match_value[i] + eq[i].out * (in[i][1-tuple_i] - match_value[i]);
    }

    signal output value <== match_value[n];
    signal output index <== match_index[n];
}

Note that if no element is found, `FindTuple` returns zero as a value and `n` as an index. To check that an element was found, a caller needs to check that the returned index is less than `n`.

## Step 2: Remove a matching tuple

Applying `FilterTuple` to the same input will always return the same tuple. To fix this, we can increment the first entry of the found tuple. It will ensure that this tuple will not be matched again because its first entry $\ne$ `match` anymore.

`IncrementValueInTuple` increments `tuple_i`-th entry of the tuple at position `index` (as with `FindTuple`, it must be `0` or `1`). The remaining tuples are returned unchanged.

template IncrementValueInTuple(n, tuple_i) {
    signal input in[n][2];
    signal input index;    
   
    signal output out[n][2];
	component e[n];
	for (var i = 0; i < n; i++) {
		e[i] = IsEqual();
		e[i].in[0] <== i;
		e[i].in[1] <== index;

		out[i][tuple_i] <== in[i][tuple_i] + e[i].out;
		out[i][1-tuple_i] <== in[i][1-tuple_i];
	}
}

Note that integer overflow is not a problem because all signals are finite field elements.

## Step 3: Filter template

On each step, `Filter` template performs the following steps `n` times:

1. Uses `FindTuple` to search for a tuple.
* If a tuple is found, store it in `out`
* Else, store `[0,0]` in `out`
2. Uses `IncrementValueInTuple` to increment the first entry of the tuple, so it won't be found again. If a tuple was not found on step 1, no increment will happen.

On the first iteration, `FindTuple` and `IncrementValueInTuple` are applied to the original input array `in`. On subsequent iterations, they are applied to the result of the last `IncrementValueInTuple` to avoid finding the same tuple.

`num_match` is computed using a helper `CalculateTotal` template.

`Filter` template is parametrized with the length of the array (`n`).

template Filter(n) {
    signal input in[n][2];
    signal input match;    
       
    signal output out[n][2];
	
    component ft[n]; // `FindTuple`
    component index_check[n]; // `LessThan`
    component inc[n]; // `IncrementValueInTuple`
    
    // to compute `num_match` output
    component match_count = CalculateTotal(n); 
	
    // compute i-th tuple of `out`
    for (var i = 0; i < n; i++) {
        // try to find the next matching tuple
    	ft[i] = FindTuple(n, 0);		
    	if (i == 0) {
            // if this is the first iteration, look in `in`
            ft[i].in <== in;
    	} else {
            // else, look in the output of the latest `inc`
            ft[i].in <== inc[i-1].out;
    	}
        // set the `match` value
        ft[i].match <== match;

        // check whether `FindTuple` found something or not
        // if there was a match, ft[i].index must be less than n
        index_check[i] = LessThan(7);  // length of expected `in` is 100
        index_check[i].in[0] <== ft[i].index; 
        index_check[i].in[1] <== n;

        // write the tuple returned by `FindTuple` to the output 
        // or write [0,0] if no tuple was not found
        out[i][0] <== match * index_check[i].out;
        out[i][1] <== ft[i].value * index_check[i].out;
        
        // add 1 to `match_count` if a tuple was found
        // add 0 to `match_count` if a tuple was not found
        match_count.in[i] <== index_check[i].out; 

        // exclude found tuple by +1 its first entry
        inc[i] = IncrementValueInTuple(n,0);
        if (i == 0) {		
            // if this is the first iteration, increment in `in`
            inc[i].in <== in;
        } else {
            // else increment in the latest output of `inc`
            inc[i].in <== inc[i-1].out;			
        }
        // index of the found tuple
        inc[i].index <== ft[i].index;
        // if no tuple found, ft[i].index == n, no tuple will be incremented
					
    }
    // output the number of matched tuples
    signal output num_match <== match_count.out;
}

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

    signal sums[n];

    sums[0] <== in[0];

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

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

component main { public [ in, match ] } = Filter(100);

zkRepl gist with some test data is available here: https://zkrepl.dev/?gist=0f57ca1075cdc2ee538227c67b7231e5

## Number of non-linear constraints

For `n = 100`, the circuit has 60.9k non-linear constraints.

$ circom circuits/filter.circom --r1cs --wasm --sym --c

template instances: 8
non-linear constraints: 60900
linear constraints: 0
public inputs: 201
public outputs: 201
private inputs: 0
private outputs: 0
wires: 61002
labels: 202404

This solution has a quadratic number of constraints. This can probably be reduced reduce down to $O(nlog(n))$. There also should be some room for reduction of the constants, e.g. by optimizing `LessThan` for a constant comparison.