Skip to content

Witness index for native multilinear extensions

Jim Posen requested to merge jimpo/2024-06-19-new-witness-index into main

This MR introduces a new witness index that can return MultilinearExtension witnesses for heterogeneous fields. This is a potential solution to an issue in the example SNARKs where we must have a trace witness struct in addition to the trace oracle and the witness index. The witness index seems like it should be enough but is insufficient because the PCS needs direct access to MultilinearExtension, not the type-erased form of MultilinearPoly .

This new index exploits the fact that Underlier types can be packed into different extensions and a small amount of unsafe lifetime transmutation to provide a witness that can return native witness polynomials for a variety of fields.

The motivation is to help improve the patterns used in SNARK examples that require TraceOracle and TraceWitness structs to implement methods returning the committed polynomials in the same order, for each committed tower height. With the new index, trace generation can put all of the trace data in a MultilinearExtensionIndex and the prove routine can look up the committed polynomials by oracle ID. This works quite nicely.

There are some painful consequences to this however. Using the new MultilinearExtensionIndex forces the code to use the new pattern of constructing packed fields from an UnderlierType via PackScalar -- it is very difficult to write code that is generic over packed fields natively now. This also broke in several places where the witnesses are field elements themselves, not PackedType<U, F>. Most notably, I could not make the lasso example work because prodcheck, msetcheck, and lasso all use witnesses where the packed fields are themselves fields.

Because I could not upgrade all the code in one shot, I left the old MultilinearWitnessIndex around and marked it deprecated.

Merge request reports