Paper 2021/1063

Cairo – a Turing-complete STARK-friendly CPU architecture

Lior Goldberg, Shahar Papini, and Michael Riabzev

Abstract

Proof systems allow one party to prove to another party that a certain statement is true. Most existing practical proof systems require that the statement will be represented in terms of polynomial equations over a finite field. This makes the process of representing a statement that one wishes to prove or verify rather complicated, as this process requires a new set of equations for each statement. Various approaches to deal with this problem have been proposed. We present Cairo, a practically-efficient Turing-complete STARK-friendly CPU architecture. We describe a single set of polynomial equations for the statement that the execution of a program on this architecture is valid. Given a statement one wishes to prove, Cairo allows writing a program that describes that statement, instead of writing a set of polynomial equations.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
CairoSTARKzkSTARKproof systemzero knowledgeprogramming languagecompilation
Contact author(s)
lior @ starkware co
spapini @ starkware co
michael @ starkware co
History
2021-08-16: received
Short URL
https://ia.cr/2021/1063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1063,
      author = {Lior Goldberg and Shahar Papini and Michael Riabzev},
      title = {Cairo – a Turing-complete STARK-friendly CPU architecture},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1063},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1063}},
      url = {https://eprint.iacr.org/2021/1063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.