In a multi-trace proof with maximum height n_0, the canonical LDE subgroup is g•H_0, a trace over H with height n defined over H = H_0^r (where r = n_0/n is the lifting factor) will be evaluated over g^r•H.
We are interested in supporting pre-processed traces for the Precompile VM, in particular a byte-lookup chip which would provide pre-computed operations such as AND, XOR, etc. This trace would always have height 2^16, and but therefore, the commitment to its LDE would vary depending on the max height of the other traces. Not only does this mean that we need a commitment for all possible max trace heights, but also that we must precompute the LDE of this trace each time we prove it.
The solution is to define a consistent coset shift g corresponding to the maximum coset size. This would be the size of the largest sub group of roots of unity, of size n_max. Therefore, the coset shift for an evaluation domain of size n would be g^{n_max/n}.
As part of this refactor, it may make sense to move the Coset structs to the pcs module, to ensure the same coset shift is used everywhere
In a multi-trace proof with maximum height
n_0, the canonical LDE subgroup isg•H_0, a trace overHwith heightndefined overH = H_0^r(wherer = n_0/nis the lifting factor) will be evaluated overg^r•H.We are interested in supporting pre-processed traces for the Precompile VM, in particular a byte-lookup chip which would provide pre-computed operations such as AND, XOR, etc. This trace would always have height
2^16, and but therefore, the commitment to its LDE would vary depending on the max height of the other traces. Not only does this mean that we need a commitment for all possible max trace heights, but also that we must precompute the LDE of this trace each time we prove it.The solution is to define a consistent coset shift
gcorresponding to the maximum coset size. This would be the size of the largest sub group of roots of unity, of sizen_max. Therefore, the coset shift for an evaluation domain of sizenwould beg^{n_max/n}.As part of this refactor, it may make sense to move the
Cosetstructs to the pcs module, to ensure the same coset shift is used everywhere