Intro to AIR development

Celestia’s zk blob inclusion proofs are powered by SP1, and it spends hundreds of thousands of riscV cycles on serialization. This overhead made me wonder if a custom AIR for blob inclusion proofs could have impressive savings- either as a standalone STARK, or as an SP1 precompile.

To develop such an AIR, first you obtain an AIR for sha256, adapt it to compute merkle proofs, and finally perform NMT-specific checks.

SP1 has a sha256 precompile; it’s a AIR circuit that computes sha256 hashes, and performs memory IO with the SP1 zkVM.

Plonky3 has a bunch of different AIRs for hash functions, but no standalone air for sha256.

I decided to pull the sha256 code out of SP1, and bring it into vanilla Plonky3 as a learning excersize.

Scaffolding a sha256 AIR

• Copy-pasted columns and “operation” structs from SP1’s sha256 into my vanilla plonky3 AIR.
  • columns.rs
• Note that the “operation” columns reference these ByteRecord things, which appear to be some SP1-specific optimizations, maybe related to lookup arguments for range checks or something like that.
• In our vanilla Plonky3 approach, we will remove these optimizations and end up with a “pure” vanilla plonky3 sha256 implementation
  • Likely, this will involve doing range checks as standard gates in the AIR.
• Then, as a learning excersize, we will re-implement these optimizations, and explore techniques like cross-table lookups, permutation argument, and regular lookups.