Skip to content

avm: polynomials to be shifted make you add an empty row which increases a full trace of 2^16 to 2^17 #7966

@fcarreiro

Description

@fcarreiro

There are some assertions when getting the shifted version of a polynomial.

This forces us to add an empty initial row. Then, if we had a trace of 2^16 (e.g., with the AND/XOR/OR lookup table in column form), adding this single row tips us over to 2^17.

In principle, we might be able to just add a row to the polynomials to be shifted, but to do that in a way that doesn't break alignment with the rest of the table, we'd have to add the row to the whole subtrace. Other approach could be assuming that there are no shifts in fixed tables (precomputed) and not shift those. This might be easier (we merge all non-fixed tables, then add row, then merge fixed tables).

However, a more conceptual question remains: why are those zeroes needed at all? Some time ago @ludamad told me this had to do with a "shift" actually being transforming a poly of degree k to degree k-1 by removing the constant term. Then the asserts ask for the constant term to be 0. I don't see why this is needed, seems like truncation should be fine but I should ask around.

Metadata

Metadata

Assignees

Labels

C-avmComponent: AVM related tickets (aka public VM)

Type

No type
No fields configured for issues without a type.

Projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions