Arithmetization of Σ¹₁ Relations in Halo 2 Paper

Arithmetization of Σ¹₁ Relations in Halo 2 Paper


We are pleased to announce the first published paper by Orbis Labs. Arithmetization of Σ¹₁ relations in Halo 2 by Morgan Thomas, our CTO, presents an easy and error-free method for compiling (“arithmetizing”) relations into Halo 2 arithmetic circuits.

This paper introduces Σ¹₁ (sigma one one) arithmetization: a mathematical theory which describes how to compile classes of statements into a form where those statements are provable using Halo 2 zk-SNARKs. Halo 2 zk-SNARKs can only prove statements which are expressed in a particular way, as an "arithmetic circuit." Translating statements into arithmetic circuits by hand is difficult and error-prone. This research provides, as far as we know, the first automatic, provably correct process for translating classes of statements, written in English-like mathematical notation, into arithmetic circuits. This will greatly reduce the effort required to build and validate zk-SNARK proving processes on Orbis and other projects.

We look forward to our future publications which will further outline the techniques and technologies we are using to build Orbis, the first general-purpose layer 2 zk-rollup scaling solution for Cardano.