Table of Contents
- Introduction
- Notation and Preliminaries
- Recursive Proofs Composition Overview
- Proof-Carrying Data
- Cycles of Elliptic Curves
- Brief Survey: Recursive Proofs Protocols
- Conclusion
- References
- Appendix A: Pairing Cryptography
- Contributors
Introduction
In pursuit of blockchain scalability investigation in this report focuses on the second leg of recursive proofs composition: “proofs that verify other proofs”.
Recursive proofs composition is like a huge machinery with many moving parts. For the sake of brevity, the aim here is to present only the most crucial cryptographic tools and techniques required to achieve recursive proofs composition.
Amortization strategies that recursive proofs use to accomplish reduced verification costs are enabled by a powerful tool called a Proof-Carrying Data or PCD, first introduced by Alessandro Chiesa in his PhD thesis [4]. The resulting proof system is made efficient and more practical by the use of a technique that utilises cycles of elliptic curves, first realised by Eli Ben-Sasson et al [2]. These two are what the report hinges around.
The details of recursive proofs composition are in the mathematics. So effort is taken to simplify concepts, while keeping technical reader’s interests in mind. At the end the reader will appreciate the power of recursive proofs composition, how it uses PCDs and cycles of elliptic curves, as well as why it needs the two to achieve significant blockchain scalability.
Notation and Preliminaries
Notation and terminology in this report is standard. But in order to achieve a clear understanding of the concept of cycles of elliptic curves, a few basic facts about elliptic curves are herein ironed out.
Fields and Elliptic Curves
A field is any set
Note that in blockchain research papers an elliptic curve refers to what is actually an elliptic curve group. This can cause confusion especially when talking about the scalar field as opposed to the base field.
-
In Mathematics an elliptic curve
over a field generally refers to a locus, that is the curve formed by all the points satisfying a given equation. For example, an equation of the form where and are elements of some field , say the rationals , the reals or the complex numbers Such a field is referred to as the base field for . -
The fields;
, and ; are infinite sets and are thus not useful for cryptographic purposes. In cryptography, base fields that are of practical purposes are preferably finite and of a large prime order. This ensures that the discrete log problem is sufficiently difficult, making the cryptosystem secure against common cryptanalytic attacks. -
Note that all finite fields are either of prime order or power of a prime. So then any finite field
is either or for some prime number . See [6, Lemma 3.19] for the proof of this fact. Actually, it can be shown that the orders of their respective multiplicative groups and are and , [6, Proposition 6.1]. -
An elliptic curve group
is formed by first defining ‘addition’ of elliptic curve points, picking a point on the curve and using it to generate a cyclic group by doubling it, , and forming all possible scalar multiples . The group ‘addition’ of points and doubling are illustrated in Figure 1 below. All these points generated by together with the point at infinity, , form an algebraic group under the defined ‘addition’ of points.
- Once an elliptic curve group
is defined, the scalar field can be described. The scalar field is the field that is isomorphic to (i.e., has the same order as) the largest cyclic subgroup of the elliptic curve group . So then, if the order of the elliptic curve group is a prime , then the scalar field is . The order of the elliptic curve group is denoted by .
Ultimately, unlike an elliptic curve
#### Example 1
Consider the curve
In accordance with literature, an elliptic curve group
Arithmetic Circuits and R1CS
A zero-knowledge proof typically involves two parties,
the prover
Arithmetic circuits are computational models commonly used when solving NP statements.
The general process for a zero-knowledge proof system is to convert
the set computation or statement being proved into an arithmetic circuit
Recursive Proofs Composition Overview
In their recent paper [1], Benedikt Buenz et al. report that, “Recursive proofs composition has been shown to lead to powerful primitives such as incrementally-verifiable computation (IVC) and proof-carrying data (PCD).” Thus recognising the two main components of recursive proofs composition, IVC and PCD. The former was adequately investigated in [9], and the latter is now the focus of this report.
Verification Amortization Strategies
These strategies are briefly mentioned here but their detailed descriptions can be found in [9].
Verifiable Computation allows a verifier to delegate expensive computations to untrusted third parties and be able to check correctness of the proofs these third parties submit.
Inductive proofs take advantage of whatever recursion there may be in a computational problem. And due to the Principle of Mathematical Induction, a verifier need only check correctness of the “base step” and the “inductive step”. Making this a powerful tool when it comes to saving verification costs.
Incrementally Verifiable Computation is the strategy where, in addition to delegating computations to several untrusted parties, the verifier does not execute verification as often as he receives proofs from third parties but rather collects these proofs and only executes a single proof at the end.
Nested Amortization, the strategy here is to reduce the cost of an expensive computation to a sub-linear cost (logarithmic relative to the cost of the original computation) by collapsing the cost of two computations to a cost of one.
Proof-Carrying Data
Recursive proofs composition uses an abstraction called proof-carrying data (PCD) when dealing with distributed computations. These PCDs are powerful tools that enable practical implementation of the above verification amortization strategies.
What is a PCD?
Proof-Carrying Data, or PCD, is a cryptographic mechanism that allows
proof strings
Such proofs
An obvious example of a distributed computation in PoW blockchains is mining. And of course, the integrity of any PoW blockchains relies on the possibility for proper validation of the PoW.
Trustlessness via PCDs
A PCD achieves trustlessness in the sense that untrusted parties carry out
distributed computations, and a protocol compiler
Since a PCD is equipped with a protocol compiler
- mutually distrustful parties can perform distributed computations that run indefinitely, and
- due to proof strings attached to all previous messages, any node
can verify any intermediate state of the computation and propagate a new message with its proof string attached to it.
It now becomes clear how recursive proofs composition accomplishes blockchain scalability. Any new node can take advantage of IVC and a PCD to succinctly verify the current state of the blockchain without concern about the chain’s historical integrity.
The PCD abstraction is no doubt the very secret to achieving blockchain scaling especially via recursive proofs composition.
Cycles of Elliptic Curves
Given the above discussion on PCDs, note that the cryptographic technique of using a cycle of elliptic curves is not much about scalability but rather about efficiency of arithmetic circuits. The main trick is to exploit the proof system’s field structure.
Why Cycle of Elliptic Curves?
Why then the need for a second elliptic curve that warrants the use of a cycle of elliptic curves?
The reason a second elliptic curve is needed is due to the inherent field structure of elliptic curves. There are two practical aspects to carefully consider when choosing fields for the underlying Elliptic Curve Cryptosystem of a blockchain;
- firstly, the best field arithmetic for arithmetic circuits that are instantiated with
, and - secondly, the possible or mathematically permissible orders of the scalar field of
.
The Native Field Arithmetic
When instantiating a proof system’s arithmetic circuit using an elliptic curve
For an elliptic curve
- the base field is
and so its arithmetic consists of addition modulo and multiplication modulo , - the scalar field is
, where is the prime order of the largest subgroup of , so in this case the arithmetic consists of addition modulo and multiplication modulo .
The question now is which arithmetic is better to use in a circuit instantiated with
Example 2
Consider the elliptic curve
Remark: For practical purposes the order of the base field is always a large prime, and
thus the infinite field of rationals
The Order of the Scalar Field
For any finite field
By definition, the scalar field
It is thus mathematically impossible for the scalar field
No Prover-Verifier Dichotomy
In the envisaged proof-of-proofs system using recursive proofs composition, the tremendous accomplishment is to allow every participant to simultaneously be a prover and a verifier. However, this presents a serious practical problem.
Note the following common practices when implementing proof systems (gleaning information from [15]);
- The proof system is instantiated with an elliptic curve
over a base field - The most natural field arithmetic for the arithmetic circuit is the scalar field’s,
-arithmetic - When computing operations on elliptic curve points inside the proof system verifier, the
base field arithmetic is used. i.e., verifier uses
-arithmetic.
Normally, when there is a clear dichotomy between a prover and a verifier, the use of two distinct field arithmetics would not be an issue.
“But here we are encoding our verifier inside of our arithmetic circuit; thus,
we will need to simulate
Basically, the problem is that there is no efficient way to use both field arithmetics when there is no prover-verifier dichotomy.
The ideal solution would be choosing the elliptic curve
The adopted solution is to find a second elliptic curve, say
The proof system aimed at is illustrated in Figure 3 below.
Pairing-friendly Elliptic Curves
It was Groth in [18] who first constructed “a pairing-based (preprocessing) SNARK for arithmetic circuit satisfiability, which is an NP-complete language”. But when it comes to a scalable zero-knowledge proof system, it was Ben-Sasson et al in [2] who first presented a practical recursive proofs composition that uses a cycle of elliptic curves.
Definition 1:
Given an elliptic curve
Definition 2:
For secure implementation of pairing-based cryptographic systems, elliptic curves with small embedding degree
According to Freeman et al [14], “pairing-friendly curves are rare and thus require specific constructions.” In the same paper, the authors furnish what they call a “single coherent framework” of constructions of pairing-friendly elliptic curves.
The Coda blockchain [19] is an example of a deployed protocol using the Ben-Sasson approach in [2]. It uses pairing-friendly MNT curves of embedding degrees 4 and 6.
Amicable Pairs of Elliptic Curves
According to Bowe et al in [8], pairing-based curves of small embedding degree like MNT constructions used in Coda require curves of size approaching 800 bits for 128-bit security level.
Previously, constructions of pairing-friendly curves were mostly restricted to embedding degrees
Some researchers, such as Chiesa et al [21], do not make much distinction between a cycle of pairing-friendly elliptic curves and Aliquot cycle of elliptic curves (to be defined below). It is perhaps due the fact that, unlike pairing-friendly curves, Aliquot cycles are more concerned with elliptic curves of prime orders.
Minimum required properties for a second elliptic curve that forms an Amicable Pair with the
elliptic curve group
- the second curve must also be of a large prime order,
- it must be compatible with the first curve in the sense that the verifier operations can be efficiently carried out in it, and
- its Discrete Log Problem must be comparably as difficult as in the first curve
.
An elliptic curve
Definition 3: [16]
An Aliquot Cycle of an elliptic curve
An Aliquot cycle as defined above has length
Definition 4: [16]
An Amicable Pair of an elliptic curve
Thus an Amicable pair is basically an Aliquot cycle of length
Depending on the curve at hand, and unlike pairing-friendly curves, some curves have a large number of amicable pairs.
For instance, in [16], Silverman and Stange report that the curve of
See Figure 3 above for a simplified depiction of a recursive proofs system using an Amicable pair of elliptic curves.
Brief Survey: Recursive Proofs Protocols
There are two recursive proofs protocols using amicable pairs of elliptic curves that are of keen interest; Coda and Halo. The Sonic protocol is mentioned here because it is a close predecessor of Halo, and it utilises a few Bulletproofs techniques.
Coda Protocol
The Coda Protocol seems to be more successful at scalability than Halo, though the two have fundamental differences. It is claimed in [19] that Coda can handle a throughput of thousands of transactions per second. And this could perhaps be attributed to its architecture, a decentralized ledger instead of a typical blockchain.
Coda follows Ben-Sasson et al’s approach to cycle of curves by constructing two SNARKs, Tic and Toc, that verify each other. Note that this means the recursive proofs composition circuit, as seen in Figure 3, is actually a two-way circuit.
The main disadvantage of Coda is that it uses a trusted setup. But also, to achieve 128-bit security at low embedding degrees it requires 750-bit-sized curves.
Sonic Protocol
The Sonic protocol aims at providing zero-knowledge arguments of knowledge for the satisfiability of constraint systems representing NP-hard languages [[23]]. Its constraint system is defined with respect to a two-variate polynomial used in Bulletproofs, originally designed by Bootle et al [24].
It is basically a zk-SNARK that uses an updatable Structured Reference String (SRS). It achieves non-interaction via the Fiat-Shamir transformation. The SRS is made updatable not only for continual strengthening, but also to allow reusability. Unlike the SRS used in Groth’s scheme [18] which grows quadratically with the size of its arithmetic circuit, Sonic’s only grows linearly.
Sonic is built from a polynomial commitment scheme and a signature of correct computation. The latter primitive seems to achieve what a PCD does, allowing a third party helper to provide solutions to a computation as well as proof that the computation was correctly carried out.
Lastly, Sonic makes use of an elliptic curve construction known as BLS12-381 in order to achieve 128-bit security at the minimum [[23]].
Halo Protocol
Although Halo is a variant of Sonic, the two differ mainly in that Halo uses no trusted setup. It however inherits all Bulletproofs techniques that Sonic employs, including the polynomial commitment scheme and the constraint system.
Halo has been adjusted to leverage the nested amortization technique. It also uses a modified version of the Bulletproofs inner-product proof, which is appropriately adopted to suit its polynomial commitment scheme and the constraint system [11].
An Amicable pair of 255-bit sized curves, named Tweedledee and Tweedledum, are employed in Halo, see [11, Section 6.1]. Again, the target security level is 128-bit.
In [1] the authors purportedly present a collection of results that establish the theoretical foundations for a generalization of the approach used in Halo.
Halo is no doubt the closest recursive proofs protocol to Bulletproofs, and hence of keen interest to Tari for possibly developing a recursive proofs system that achieves scaling of the Tari Blockchain.
Conclusion
Recursive proofs composition is not only fascinating but also powerful, even as evidenced by real life applications such as the Coda Protocol and the Halo Protocol.
This report completes the necessary theory needed to understand what is recursive proofs composition, what it entails, how its various components work, and why the technique of cycles of curves is necessary.
Thus it still remains to consider the feasibility of designing and implementing a recursive proofs composition that can achieve significant scalability for the Tari Blockchain or Tari DAN.
Since Curve25519 has enormous embedding degree, which is in the order of
The big take away from this research work is the PCD and what it is capable of. Buenz et al say, “PCD supports computations defined on (possibly infinite) directed acyclic graphs, with messages passed along directed edges” [1]. This together with the Coda example imply that an ingenious combination of a DLT and a PCD for Layer 2 could achieve immense blockchain scalability.
References
[1] B. Buenz, P. Mishra, A. Chiesa and N. Spooner, “Proof-Carrying Data from Accumulation Schemes”, May 25, 2020 [online]. Available: https://eprint.iacr.org/2020/499.pdf. Date accessed: 2020‑07‑01.
[2] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Scalable Zero Knowledge via Cycles of Elliptic Curves”, September 18, 2016 [online]. Available: https://eprint.iacr.org/2014/595.pdf. Date accessed: 2020‑07‑01.
[3] A. Chiesa and E. Tromer, “Proof-Carrying Data and Hearsay Arguments from Signature Cards”, ICS 2010 [online]. Available: https://people.eecs.berkeley.edu/~alexch/docs/CT10.pdf. Date accessed: 2020‑07‑01.
[4] A. Chiesa, “Proof-Carrying Data,” PhD Thesis, MIT, June 2010. [online]. Available: https://pdfs.semanticscholar.org/6c6b/bf89c608c74be501a6c6406c976b1cf1e3b4.pdf. Date accessed: 2020‑07‑01.
[5] E. Ben-Sasson, A. Chiesa, P. Mishra and N. Spooner, “Proof-Carrying Data from Accumulation Schemes”, May 25, 2020 [online]. Available: https://eprint.iacr.org/2020/499.pdf. Date accessed: 2020‑07‑06.
[6] A. Landesman, “NOTES ON FINITE FIELDS”, [online]. Available: https://web.stanford.edu/~aaronlan/assets/finite-fields.pdf. Date accessed: 2020‑07‑06.
[7] E. Ben-Sasson, “The ZKP Cambrian Explosion and STARKs” November 2019 [online]. Available: https://starkware.co/decks/cambrian_explosion_nov19.pdf. Date accessed: 2020‑07‑05.
[8] S. Bowe, J. Grigg and D. Hopwood, “Halo: Recursive Proof Composition without a Trusted Setup” [online]. Available: https://pdfs.semanticscholar.org/83ac/e8f26e6c57c6c2b4e66e5e81aafaadd7ca38.pdf. Date accessed: 2020‑07‑05.
[9] Tari Labs University, “Amortization of Bulletproofs Inner-product Proof”, May 2020 [online]. Available: https://tlu.tarilabs.com/cryptography/amortization-of-bulletproof-inner-product-proof. Date accessed: 2020‑07‑06.
[10] P. Bartlett, “Lecture 9: Elliptic Curves, CCS Discrete Math I”, 2014 [online]. Available: http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_discrete_f2014/ccs_discrete_f2014_lecture9.pdf. Date accessed: 2020‑07‑06.
[11] S. Bowe, J. Grigg and D. Hopwood, “Halo: Recursive Proof Composition without a Trusted Setup”, Electric Coin Company, 2019 [online]. Available: https://pdfs.semanticscholar.org/83ac/e8f26e6c57c6c2b4e66e5e81aafaadd7ca38.pdf. Date accessed: 2020‑07‑06.
[12] M.C. Welsh, “ELLIPTIC CURVE CRYPTOGRAPHY” REUpapers, 2017, [online]. Available: http://math.uchicago.edu/~may/REU2017/REUPapers/CoatesWelsh.pdf. Date accessed: 2020‑07‑07.
[13] A.V. Sutherland, “Elliptic Curves, Lecture 9 Schoof’s Algorithm”, Spring 2015, [online]. Available: https://math.mit.edu/classes/18.783/2015/LectureNotes9.pdf. Date accessed: 2020‑07‑07.
[14] D. Freeman, M. Scott and E. Teske, “A TAXONOMY OF PAIRING-FRIENDLY ELLIPTIC CURVES”, [online]. Available: https://eprint.iacr.org/2006/372.pdf. Date accessed: 2020‑07‑07.
[15] M. Straka, “Recursive Zero-knowledge Proofs: A Comprehensive Primer” [online], 2019‑12‑08. Available: https://www.michaelstraka.com/posts/recursivesnarks/. Date accessed: 2020‑07‑07.
[16] J.H. Silverman and K.E. Stange, “Amicable pairs and aliquot cycles for elliptic curves” [online], 2019‑12‑08. Available: https://arxiv.org/pdf/0912.1831.pdf. Date accessed: 2020‑07‑08.
[17] A. Menezes, “An Introduction to Pairing-Based Cryptography” [online]. Available: https://www.math.uwaterloo.ca/~ajmeneze/publications/pairings.pdf. Date accessed: 2020‑07‑11.
[18] E. Groth, “On the Size of Pairing-based Non-interactive Arguments” [online]. Available: https://eprint.iacr.org/2016/260.pdf. Date accessed: 2020‑07‑12.
[19] I. Meckler and E. Shapiro, “Coda: Decentralized cryptocurrency at scale” O(1) Labs whitepaper. May 10, 2018. [online]. Available: https://cdn.codaprotocol.com/v2/static/coda-whitepaper-05-10-2018-0.pdf. Date accessed: 2020‑07‑12.
[20] P.L.M.N. Barreto, M. Naehrig, “Pairing-Friendly Elliptic Curves of Prime Order” [online]. Available: https://eprint.iacr.org/2005/133.pdf. Date accessed: 2020‑07‑12.
[21] A. Chiesa, L. Chua and M. Weidner, “On cycles of pairing-friendly elliptic curves” [online]. Available: https://arxiv.org/pdf/1803.02067.pdf. Date accessed: 2020‑07‑12.
[22] S. Bowe, “Halo: Recursive Proofs without Trusted Setups (video)”, Zero Knowledge Presentations Nov 15, 2019 [online]. Available: https://www.youtube.com/watch?v=OhkHDw54C04. Date accessed: 2020‑07‑13.
[[23]] M. Maller, S. Bowe, M. Kohlweiss and S. Meiklejohn, “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings,” Cryptology ePrint Archive: Report 2019/099. Last revised July 8, 2019. [online]. Available: https://eprint.iacr.org/2019/099
[23]: https://eprint.iacr.org/2019/099 “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings”
[24] J. Bootle, A. Cerulli, P. Chaidos, J. Groth and C. Petit, “Efficient Zero-knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting” [online]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 327‑357. Springer, 2016. Available: https://eprint.iacr.org/2016/263.pdf. Date accessed: 2019‑12‑21.
Appendix A: Pairing Cryptography
Pairing-based cryptographic systems are defined on pairings like the Weil pairing and the Tate pairing all
characterised by a bilinear mapping defined on a pair of groups; an additively group including
a special element
Although applications of pairing-based cryptography were known for a long time in the form of one-round three-party key agreements, they became more popular with the emergence of identity-based encryption.
Let
Definition A1: [17]
A bilinear pairing on
(a) (bilinear) For all
(b) (non-degeneracy)
(c) (computability) The map
One of the most important properties of the bilinear map
Take the Boneh-Lynn-Shacham short signature, or BLS-signature, as an example of a pairing-based cryptographic primitive.
Example A1
The BLS-signature uses a bilinear map
- Alice randomly selects an integer
and creates a public key where is generator of the group . - Alice’s BLS-signature on a message
is where and a hash function .
How can Bob or any party verify Alice’s signature?
- By first computing
and then check if
This is why the verification works,
See the diagram below that illustrates the verification.