An exploration of constraint systems in verifiable computation

Abstract

(English) The accelerated adoption of digital services has highlighted the need for trust-minimized computation, where parties can verify the correctness of computations without re-executing them or revealing sensitive data. Zero-knowledge proof systems, including SNARKs and STARKs, provide cryptographic guarantees of correctness, privacy, and succinct verifiability, enabling applications in scalable blockchains, privacy-preserving identity systems, and verifiable federated learning. This thesis addresses key inefficiencies in constraint-based zero-knowledge proof systems at the arithmetization layer. The research focuses on two complementary problems: optimizing binary comparisons within Rank-1 Constraint Systems (R1CS), and extending the expressiveness of STARKs through an Extended Algebraic Intermediate Representation (eAIR). The first contribution presents a weighted accumulation method for implementing strict binary comparisons in R1CS. Traditional approaches generate a large number of constraints due to the lack of native comparison and control-flow operations in the R1CS model, forcing costly bit-by-bit decompositions and creating performance bottlenecks. The proposed weighted accumulation method significantly reduces constraint overhead without compromising system security or correctness, achieving substantial efficiency improvements over the lexicographic approach. The second contribution introduces the eSTARK protocol, which extends standard STARKs by enabling the concise handling of complex constraints such as lookups, permutations, and copy constraints. These operations are difficult to encode efficiently in standard AIR. The eSTARK protocol integrates vector commitment arguments and polynomial optimizations, providing a flexible and user-friendly framework for representing a broader class of computations without introducing unnecessary arithmetization overhead. Both contributions address practical limitations of current zero-knowledge proof systems. The first focuses on reducing constraint complexity for common operations, while the second expands the expressiveness of the proof system itself. Together, they demonstrate the importance of arithmetization-level optimizations for improving the efficiency and usability of zero-knowledge proofs. (Català) L’adopció accelerada de serveis digitals ha posat en relleu la necessitat de computació amb confiança mínima, on les parts poden verificar la correcció dels càlculs sense haver de tornar-los a executar ni revelar dades sensibles. Els sistemes de proves de coneixement zero, incloent-hi SNARKs i STARKs, ofereixen garanties criptogràfiques de correcció, privacitat i verificabilitat concisa, permetent aplicacions en blockchains escalables, identitat preservant la privacitat i aprenentatge federat verificable. Aquesta tesi aborda les principals ineficiències en els sistemes de proves ZK basats en restriccions a la capa d’aritmetització. La recerca se centra en dos problemes complementaris: optimitzar les comparacions binàries dins dels Rank-1 Constraint Systems (R1CS) i ampliar l’expressivitat dels STARKs mitjançant una Representació Intermèdia Algebraica Estesa (eAIR). La primera contribució presenta un mètode d’acumulació ponderada per implementar comparacions binàries estrictes en R1CS. Els enfocaments tradicionals generen un gran nombre de restriccions a causa de la manca d’operacions natives de comparació i de control de flux en el model R1CS, obligant a descomposicions costoses bit a bit i creant colls d’ampolla en el rendiment. El mètode d’acumulació ponderada proposat redueix de manera significativa la sobrecàrrega de restriccions sense comprometre la seguretat o la correcció del sistema, aconseguint millores substancials d’eficiència respecte a l’enfocament lexicogràfic. La segona contribució introdueix el protocol eSTARK, que amplia els STARKs estàndard permetent la gestió concisa de restriccions complexes com ara lookups, permutacions i restriccions de còpia. Aquestes operacions són difícils d’encodear de manera eficient en l’AIR estàndard. El protocol eSTARK integra arguments de compromís vectorial i optimitzacions polinòmiques, oferint un marc flexible i fàcil d’utilitzar per representar una classe més àmplia de càlculs sense introduir sobrecàrrega d’aritmetització innecessària. Totes dues contribucions aborden limitacions pràctiques dels sistemes de proves de coneixement zero actuals, amb la primera centrada en reduir la complexitat de restriccions per a operacions comunes i la segona en expandir l’expressivitat del sistema de proves en si. Conjuntament, demostren la importància de les optimitzacions a nivell d’aritmetització per millorar l’eficiència i la usabilitat de les proves de coneixement zero. (Español) La adopción acelerada de servicios digitales ha puesto de relieve la necesidad de computación con confianza mínima, donde las partes pueden verificar la corrección de los cálculos sin tener que volver a ejecutarlos ni revelar datos sensibles. Los sistemas de pruebas de conocimiento cero, incluyendo SNARKs y STARKs, ofrecen garantías criptográficas de corrección, privacidad y verificabilidad concisa, permitiendo aplicaciones en blockchains escalables, identidad preservando la privacidad y aprendizaje federado verificable. Esta tesis aborda las principales ineficiencias en los sistemas de pruebas ZK basados en restricciones a la capa de aritmetización. La investigación se centra en dos problemas complementarios: optimizar las comparaciones binarias dentro de los Rank-1 Constraint Systems (R1CS) y ampliar la expresividad de los STARKs mediante una Representación Intermedia Algebraica Extendida (eAIR). La primera contribución presenta un método de acumulación ponderada para implementar comparaciones binarias estrictas en R1CS. Los enfoques tradicionales generan un gran número de restricciones debido a la falta de operaciones nativas de comparación y de control de flujo en el modelo R1CS, obligando a descomposiciones costosas bit a bit y creando cuellos de botella en el rendimiento. El método de acumulación ponderada propuesto reduce de manera significativa la sobrecarga de restricciones sin comprometer la seguridad o la corrección del sistema, logrando mejoras sustanciales de eficiencia respecto al enfoque lexicográfico. La segunda contribución introduce el protocolo eSTARK, que amplía los STARKs estándar permitiendo la gestión concisa de restricciones complejas como lookups, permutaciones y restricciones de copia. Estas operaciones son difíciles de codificar de manera eficiente en el AIR estándar. El protocolo eSTARK integra argumentos de compromiso vectorial y optimizaciones polinómicas, ofreciendo un marco flexible y fácil de usar para representar una clase más amplia de cálculos sin introducir sobrecarga de aritmetización innecesaria. Ambas contribuciones abordan limitaciones prácticas de los sistemas de pruebas de conocimiento cero actuales, con la primera centrada en reducir la complejidad de restricciones para operaciones comunes y la segunda en expandir la expresividad del sistema de pruebas en sí. Conjuntamente, demuestran la importancia de las optimizaciones a nivel de aritmetización para mejorar la eficiencia y la usabilidad de las pruebas de conocimiento cero.