Add support for more general boundary constraints
- Vorherrschende Sprache
- Rust
- Sterne
- 96
- Forks
- 39
- PR-Merge-Kennzahlen
- Keine gemergten PRs in 30 T.
Beschreibung
### Feature description
As it currently stands, the most general type of boundary constraints are of the form $\frac{f(X) - b(X)}{Z(X)}$ where
1. $f(X)$ is the trace column polynomial,
2. $b(X)$ is a polynomial specifying the boundary values enforced on the aforementioned column,
3. $Z(X)$ is a zerofier polynomial on the enforcement domain associated to the boundary constraint. Currently, this is either $X - g^0$ (i.e., `first`) or $X - g^{-2}$ (i.e., `last`) where we assume one exemption point and $g$ is the trace domain generator.
However, there are situations where we want to have boundary constraints which involve more than just one trace column, say $f_0(X)$ and $f_1(X)$ and a constraint like $\frac{f_0(X) \cdot f_1(X) - 1}{X - g^{-2}}$.
### Why is this feature needed?
This is needed in order to be able to write some constraints where the interaction between components happen through different buses and the consistency of the interactions is enforced through the above kind of boundary constraints.
Beitragsleitfaden
Rechercherichtung
Das Issue beschreibt die Erweiterung von Randbedingungen in einem AIR-Compiler. Beginnen Sie mit dem Lesen des Codes, der Randbedingungen verarbeitet, wahrscheinlich in einem Modul wie `constraints` oder `boundary`. Suchen Sie nach der aktuellen Implementierung von Einzelspalten-Bedingungen und der Polynomdivision-Logik. Verstehen Sie, wie die Zerofier-Polynome konstruiert werden. Entwerfen Sie dann eine Möglichkeit, Mehrspalten-Bedingungen darzustellen und in das Constraint-System zu integrieren. Das Testen umfasst das Erstellen neuer AIR-Skripte, die diese verallgemeinerten Bedingungen verwenden, und die Überprüfung der generierten Proofs.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Tech-Stack
- rust
- Bereich
- compilers
- Issue-Typ
- Feature
- Schwierigkeit
- 5/5
- Geschätzter Aufwand
- Über eine Woche
- Aktivitätsstatus
- Veraltet
- Klarheit
- Größtenteils klar
- Anfängerfreundlichkeit
- 30/100