fix: padding for negatively signed permutation sorts

[DavePearce]

There is currently an outstanding and unresolved issue around padding for permutation sorts with negative (sorting) signs (see here). For example, something like this is broken:

(module m1)
(defcolumns X)
(defpermutation (Y) ((- X)))

The problem is that the trace can always be padding with 0 at the beginning, thus breaking the sorting criteria for Y.

Mitigation

This is less of a problem when the first column of a permutation is positively signed. For example, something like this:

(module m1)
(defcolumns A B)
(defpermutation (X Y) ((+ A) (- B)))

Then for a trace like this:

{ "m1.A": [1,1,2,3], "B": [40,56,65,90] }

This is accepted correctly because a spillage value of 0 for A ensures we can accept a padded trace like this:

{ "m1.A": [0,0,1,1,2,3], "m1.B": [0,0,40,56,65,90] }

However, we can still construct a problematic trace such as:

{ "m1.A": [0,0,0,0], "m1.B": [40,56,65,90] }

Here, again, we are given an incorrect spillage value for B.

Solutions?

• (Padding Prepend / Append). One idea is to enable prepending and appending of padding data (i.e. so the 0 could be appended for negatively signed columns). This is problematic, however, for the case where we have a single delta column capturing both negatively and positively signed columns.