0xMiden / 0xMiden/air-script

Express and check expression degree

Offen
#474 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
Vorherrschende Sprache
Rust
Sterne
96
Forks
39
PR-Merge-Kennzahlen
Keine gemergten PRs in 30 T.

Beschreibung

When we write down constraints in our documentation we often will write something like
- $f \gets \mathsf{flag}( f_1, \ldots, f_n) \| \deg = d$
- $\mathsf{constraint}(v_1, \ldots, v_n) = 0 \| \deg = d$

These degree hints are very useful to ensure we are not blowing past the maximum supported degree (in our case 9). However, without actually implementing them, we have to manually check if they are correct and they might contain mistakes.

In AirScript, it could be useful to support syntax for specifying the expected degree and then have it be checked by the compiler.
- `let f = flag(v_1, ..., v_n) | deg d`
- `ev constraint([v_1, ..., v_n]) { ... } | deg = d`
- `enf constraint(v_1, ..., v_n) when f | deg = d`

The easy approach to checking the degree is by evaluating the expression graph and counting the multiplications. But this might erroneously complain if we specify a degree we know is correct but is technically lower than what would be computed in this naive way. For example the expression $s \cdot f + (1-s) \cdot f$ would have degree $\deg(s) + \deg(f)$ when in fact it has degree $\deg(f)$ since the $s$ cancel out.

It seems like there exists an established way of computing the actual degree of a multivariate expression using a randomized polynomial identity test which output the degree with high probability, thought I haven't taken the time to fully understand how it works. This is left as exercise to the assignee.

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

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