SNARK Lower Bounds via Communication Complexity

This chapter delves into the intricate world of Succinct Non-interactive Arguments of Knowledge (SNARKs) and their verification times, focusing on the polynomial commitment schemes Hyrax, Bulletproofs, and Dory. The authors isolate the information-theoretic cores of these schemes and model them as communication protocols, leveraging known and new lower bounds to provide strong evidence that these schemes have optimal verifier time. The chapter begins with an overview of SNARKs and their components, highlighting the interplay between information-theoretic and cryptographic elements. It then introduces the concept of communication complexity and its relevance to understanding the verification times of these schemes. The authors present their contributions, which include exposing the information-theoretic cores of Hyrax, Bulletproofs, and Dory, and providing evidence that certain commitment schemes are optimal in terms of verification time. The chapter also discusses the implications of these findings, including the resolution of a long-standing open question about the inherent linearity of the Bulletproofs verifier. The text concludes with a summary of results and suggestions for future research directions, emphasizing the potential for extending these findings to other polynomial commitment schemes and cryptographic protocols.