Paper 2023/661

Study of Arithmetization Methods for STARKs

Tiago Martins, Three Sigma
João Farinha, Three Sigma

This technical paper explores two solutions for arithmetization of computational integrity statements in STARKs, namely the algebraic intermediate representation, AIR, and is preprocessed variant, PAIR. The work then focuses on their soundness implications for Reed-Solomon proximity testing. It proceeds by presenting a comparative study of these methods, providing their theoretical foundations and deriving the degree bounds for low-degree proximity testing. The study shows that using PAIR increases the degree bound for Reed-Solomon proximity testing, which affects its soundness and complexity. However, the possibility of reducing the degree bound with multiple selector columns is also explored, namely by following an approach based on the decomposition of the selector values. Focusing on performance optimization, the work proceeds by qualitatively comparing computational demands of the components of both arithmetization methods, particularly their impact on the low-degree extensions. The paper concludes that, while PAIR might simplify constraint enforcement, it can be easily translated to AIR, and system testing with benchmarks is necessary to determine the application-specific superiority of either method. This work should provide insight into the strengths and limitations of each method, helping researchers and practitioners in the field of STARKs make informed design choices.

Note: The work was developed as part of an ongoing research at Three Sigma (

Available format(s)
Cryptographic protocols
Publication info
STARKsArithmetizationAIRPreprocessed AIRRPTDegree boundSelector columns
Contact author(s)
tiago s martins @ tecnico ulisboa pt
joaoanf @ hotmail com
2023-07-28: last of 4 revisions
2023-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tiago Martins and João Farinha},
      title = {Study of Arithmetization Methods for STARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/661},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.