The construction of zk-SNARKs, that is, zero-knowledge succinct non-interactive arguments of knowledge, is the subject of this paper. The reader should be aware that “succinct” is a relative term: the authors note that, in a particular context, their methodology uses a 55 MB key and 993 MB of working memory, whereas their previous solution [1] requires 3.1T MB of memory to verify a T-step computation, and hence their solution is more space-efficient when T>321. The word “scalable” in the title refers to the fact that the working memory does not depend on T, and that the running time is (quasi)-linear in T. zk-SNARKs have been known to be theoretically constructible since a recent study [2], based on bootstrapping from a collision-resistant hash function and a pre-processing zk-SNARK. This paper is about the challenges faced in doing such a construction with any pretense at efficiency. The details are pretty technical: the main ingredients follow.

(1) The native NP language whose membership is proved/verified by the zk-SNARK is the satisfiability of F-arithmetic circuits, for a certain finite field F.

(2) The underlying pre-processing zk-SNARK consists largely of operations in an elliptic curve over a finite field F’. Ideally F=F’, but the authors show that this is impossible. Hence, the authors construct a pair of curves (the “cycle” of the title) such that the number of points on the elliptic curve over F is the size of F’, and vice versa. The authors have explicitly constructed such a pair (satisfying all the usual cryptographic constraints!) with high powers of 2 dividing both (number of points -1), at the (one-off) cost of 610,000 core-hours.

(3) Although projective coordinates on elliptic curves are easier to compute, the authors state that affine coordinates are easier to verify, and hence opt for these.

(4) The hash function has to be efficiently verifiable. Therefore, rather than standard ones like SHA-256 or Keccak, they use subset-sum functions over (the additive group of) F, again leveraging the field structure. This means that the hash function can be verified in fewer than 300 gates, rather than the 13,000 of Braun and colleagues [3], who also used subset-sums.

The paper concludes with a good list of open questions.