0xMiden / 0xMiden/air-script

Add support for more general boundary constraints

Offen
#433 9 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
on hold
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

Beitragsleitfaden öffnen

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

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.