0xMiden / 0xMiden/air-script

Randomize checking of each optimization pass

オープン
#475 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
Rust
スター
96
フォーク
39
PR マージ指標
30日以内にマージされた PR はありません

説明

With each optimization pass, we are running the risk that our transformations might have a bug that would lead to an invalid set of constraints.

As an extra precautionary measure, we should try to check that each successive pass ensures the correctness of the transformation. I *think* we could implement this as an internal check in each pass.

The idea is to again use randomized polynomial identity testing. Given a list of expressions $f_1, \ldots, f_n$, which get transformed into $g_1, \ldots, g_n$, we should make sure that $f_i(r) = g_i(r)$ for some randomly sampled $r$ from a large enough field (`QuadFelt` seems the safest, although we can repeat the test with multiple random `Felt`).

This technique is easy when an optimization pass simply maps one constraint to another, but is more complicated if we are reordering or removing redundant constraints. It seems like we would need some extra logic to be able to accurately compare the the set of input and set of output expressions as a whole.

Making our transformations more robust in this way would give us way more confidence in our pipeline. Applying this test to our dummy examples may not catch all mistakes, but for our main use case which is writing the Miden VM constraints, we could be sure that the generated code matches the initial description.

Moreover, this should make it much easier to audit the compiler since we could focus mainly on whether this randomized test is correct, rather than having to check that the individual optimizations are sound.

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

Look at the optimization passes in the compiler pipeline, likely in a directory like `src/optimization`. Understand how each pass transforms constraints. The test involves sampling random field elements (QuadFelt, Felt) and evaluating input and output expressions. Start by implementing a helper for randomized polynomial identity testing on a single pass. Check existing tests for dummy examples and Miden VM constraints to see the integration point.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
rust
領域
compilers
issue の種類
機能追加
難易度
4/5
見積もり時間
3〜5日
活発さ
停滞
明瞭さ
おおむね明確
初心者へのやさしさ
35/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。