Witness generation

Here, we describe the circuit for the external audit, and the process of witness generation. The baseline is the following:

1. Use PlonKish arithmetization.
2. Follow the MPC process, every time the sorting is done, constrain the new array to be a permutation of a previous array, and to be sorted (which is a local check).
3. For comparisons, ignore bit decompositions produced by MPC and use a separate lookup argument. Producing lookup argument witness (say, using an argument from halo2) is not exactly trivial, but can be done.

The size of the circuit can be done $\sim \log(m)$ smaller by doing some additional work in MPC (one could, theoretically, skip the whole 2nd phase, by just requiring that the non-nullified votes in phase $1$ are ordered in a way that respects composition of votes, with batches starting only with either depth 0 votes or votes without left neighbor). However, obtaining such permutation in MPC is non-trivial, and likely will produce at least an undesirable $\log(m)$ overhead.