Masks over trace

[weikengchen]

When I am doing the Poseidon coprocessor design, I want to reduce the lookup overhead by packing multiple columns together. To do so, I will be reading c_vals[row], c_vals[row+1], ..., c_vals[row+15] and put them together.

It would be naturally to write the code as follows:

let c_vals = eval.next_interaction_mask(
            ORIGINAL_TRACE_IDX,
            [
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
            ]
        );

However, it turns out that this is not the right way, for the following reason.

• for point (X, Y) from the positive direction, its next point is (X, -Y) on the negative direction, and its next's next point is (X, Y) + "half a circle" (aka, there is a bit reverse), rather than moving forward a single step
• for point (X, Y) from the negative direction, its next point is (X, -Y) + "half a circle" from the positive direction, and its next's next point is (x, y) + "half a circle". Note that this is different from the case of positive direction.

It seems that if one wants to enjoy the benefits of the functionality above, one would need to:

• commit and arrange the rows in the canonical coset regular domain, so that there is no so-called positive or negative directions. The ancient Fibonacci example seems to do so.
• or, be given an additional column to distinguish rows that fall under the positive direction or the negative direction, and be given the option to mask an evaluation on point (X, Y) to (X, -Y) (we do not have such mask at the moment).

[weikengchen]

I am currently experimenting new_canonical_ordered for trace, which can make c_vals as follows work:

let c_vals = eval.next_interaction_mask(
            ORIGINAL_TRACE_IDX,
            [
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
            ]
        );

But generating the interaction trace is a different question.

[weikengchen]

Ok, I think I found the solution:

• commit trace and constant trace using CircleEvaluation::new_canonical_ordered(coset, eval.clone())
• compute the prefix sum differently (by changing the order), which is a bit tricky

and one can then use the masks over trace.