Problem statement: https://hackmd.io/@axiom/rkIujYOt2
My Solution: https://gist.github.com/0xSachinK/dcc5e594aa817d2ca2dc99e3b490d637

# My Approach: Utilizing Local and Global Masks Filtering

While working within the constrained framework of zero-knowledge proof systems, we can't use traditional control flow operations. Instead of normal execution, we're working with a "computation trace", which requires us to flatten the path. This limitation required me to develop solutions that rely on polynomials to solve the puzzle. It led me to come up with an approach involving the use of global and local masks for filtering tuples from an input array.

## Step 1: Introduction of Global and Local Masks

The main components of my solution are two types of masks: global and local. The global mask's job is to go through the input array and flag tuples whose first entry is the same as the match value.

However, it was also essential to keep the original order of these matching tuples. That's where local masks come in.

Local masks are arrays that flag all the positions that have the same prefix sum for each index in the input array.

## Step 2: Role of Local Masks in Maintaining Order

An interesting insight to note here is that, for a given prefix sum, there may be several tuples flagged in the local mask. However, only the first tuple that contributes to that prefix sum would have a "1" in the global mask. All subsequent tuples with the same prefix sum would have a "0" in the global mask, as they didn't contribute to that sum.

The act of element-wise multiplying the local masks with the global mask gives us a new mask. This resultant mask has "1"s only at the positions of the matching tuples, and importantly, they are in their correct order of appearance.

### Example

Let's consider an example where `match` is `3`, and the first entry of each tuple in the input array `in[i][0]` is `[3, x, x, 3, x, 3, x]` (where `x` indicates a don't care random value), and the second entry is `in[i][1]` is `[1, x, x, 2, x, 3, x]`.

- in[i][1]: `[1, x, x, 2, x, 3, x]`
- Global mask: `[1, 0, 0, 1, 0, 1, 0]`
- Prefix sum array: `[1, 1, 1, 2, 2, 3, 3]`

The local mask for `i = 0` is `[1, 1, 1, 0, 0, 0, 0]` as there's a "1" at all values where the prefix sum array equals `i + 1`. Multiplying the global mask with this local mask gives `[1, 0, 0, 0, 0, 0, 0]`.

Similarly, the local mask for `i = 1` is `[0, 0, 0, 1, 1, 0, 0]`. After multiplying the global mask with this local mask, we get `[0, 0, 0, 1, 0, 0, 0]`.

For `i = 2`, the local mask is `[0, 0, 0, 0, 0, 1, 1]`. Once we multiply this with the global mask, the result is `[0, 0, 0, 0, 0, 1, 0]`.

This step-by-step process illustrates how local masks operate in conjunction with global masks to maintain the correct order of the matching tuples in the output.

## Step 3: Managing Non-Quadratic Constraints and finalzing the output

Next, I multiply this mask with the second entries of the input array. This gives us the correct output array where each element is either a matching second entry from the input array or zero. Using local masks guarantees that the resulting tuples in the output maintain their relative order from the input.

However, implementing this directly in Circom would trigger a `Non-quadratic constraints error` because we're essentially multiplying three signals: local_mask, global_mask, and the second entries of the input array.

I managed to sidestep this issue by using intermediate signals to store the outputs of applying the global mask. Then, I applied the local masks to that intermediate signal. This enabled me to keep things simple and efficient, while preventing any errors.

By employing this unique masking technique and clever use of intermediate signals, I was able to efficiently filter tuples from an input array, preserving the original order, and successfully bypassing the constraints of the zero-knowledge proof systems. It was challenging, but also a fun journey of exploration and learning!