DPC Scheme’s Structural Overview — ZEXE Construction
by Anthony Matlala
In this article we pop open the hood of the ZEXE system in order to have a peek at what underlies this user-empowering system as it provides programmability and total privacy. Yet, it remains fully auditable.
ZEXE, which is short for Zero-knowledge EXEcution, is best described as a platform upon which users can define and run their own private and decentralized applications. The most typical application being a decentralized exchange. What sets ZEXE apart from all other systems that promise privacy is its core, a scheme for executing decentralized private computations (DPC). It is hence simply dubbed, the DPC scheme.
The DPC Scheme’s main functionality, as the engine of ZEXE, is to enable multiple user-defined applications to facilitate transactions, while maintaining both data and function privacy. In particular, it allows users to define private applications where parties can create assets and exchange these assets securely in a zero-knowledge manner.
What’s In This Article?
The purpose of this article is to give a structural overview of the DPC scheme and highlight how its components achieve functional privacy. We therefore — describe the four basic cryptographic primitives required to construct a fully-fledged DPC scheme, outline how these primitives are assembled together in forming the major components of a DPC scheme, and furthermore clarify how the DPC Scheme’s main functionality is achieved. However, in order to appreciate the robustness of DPC schemes, the discussion in here does not aim at specifying cryptographic primitives deployed in implementation.
In a nutshell, the above-mentioned functionality of the DPC Scheme is achieved by; — First, enabling parties to carry out computations that produce transactions offline; — And secondly, these computations are carried out in a way that is consistent with the Records Nano-Kernel (RNK). The RNK is a shared execution environment which ensures that all birth predicates of created records and death predicates of consumed records are satisfied, as well as guaranteeing that a zero-knowledge proof is attached to every transaction a user produces.
The attached zero-knowledge proofs, not only attest to the correctness of the offline computations, but also to the fact that both birth and death predicates of all relevant records in the transaction were satisfied.
The Three Main Data Structures
In terms of data structures, the DPC scheme involves three, namely; records, transactions, and a ledger. A record is the DPC’s basic data unit which can be thought of as some asset. A transaction is a state change whereby some records are consumed and new records are created, and such a transaction is valid only if the death predicates of consumed records and birth predicates of created records are satisfied. The ledger is a public platform on which all transactions are recorded in a distributed manner, and all parties therefore have access to the same copy. Basically, it is a distributed ledger, which in the DPC context is a blockchain.
The DPC Scheme’s Building Blocks
The DPC scheme leverages a zero-knowledge proof system which enables users to carry out transaction computations offline, and publish these transactions in a hidden form on the ledger, together with their zero-knowledge proofs.
Transaction information is hidden in several ways. For instance, instead of publishing the actual consumed records and the identities of record owners, only the serial numbers and the owners’ address public keys appear on the ledger. And if necessary, these address public keys (apk’s) may not be published as they are, but rather their randomised versions. Randomizable signatures are used to attain these randomised apk’s, which doesn’t come as a surprise since apk’s are often interpreted as signatures. The randomisation is very handy, as it helps to circumvent any link-ability of assets to owners across multiple transactions.
Thus far, it may seem like the DPC scheme’s main trick is to execute computations off-line while using zero-knowledge proofs. However, without the deployment of other cryptographic building blocks, the offline computations and zero-knowledge proofs alone would not suffice in solidifying total privacy. It takes three other cryptographic building blocks to achieve this goal. These are; pseudo-random functions (PRFs), collision-resistant hash (CRH) functions, and commitment schemes (CMs) or, at times their extended versions, trapdoor commitment schemes (TCMs).
Commitment Schemes
The latter building block, the commitment scheme, makes it possible for newly created records in transactions to be hidden in the form of commitments, which are not only hiding secret information but are also binding. We have sufficiently discussed what commitment schemes are here. Nevertheless, we note that in cases where there is a need to secure against malleability of transactions, the DPC Scheme replaces the standard commitment scheme with its trapdoor-extended version, TCM.
Pedersen constructed a commitment scheme based on the hardness of extracting discrete logarithms [Ped92], which is popular with privacy-preserving constructions due to its algebraic properties, such as being homomorphic. See Jens Groth’s paper, for an example of a homomorphic Trapdoor Commitment construction.
Pseudo-Random Functions
The DPC Scheme, like other non-interactive schemes, needs a reliable source for randomly selected secret inputs to Setup algorithms. This source comes in the form of a pseudo-random function (PRF), which is a mathematically constructed function whose outputs are random numbers. An important and necessary property of such PRFs is being cryptographically secure — which means it should be improbable to distinguish a sequence of numbers generated by such a PRF from a sequence generated by an ideal random number generator, when given the same seed. NIST has a suite of tests recommended for randomness testing of outputs of pseudo-random number generators like PRFs.
Since consumed records do not appear on the ledger themselves but their serial numbers, each serial number ought to be unique. But, in order to produce one unique serial number for a given record, the DPC Scheme combines as inputs to a PRF, the owner’s address secret key and a serial number nonce. And it is this nonce that provides the uniqueness of a serial number. But since nonces are outputs of hash functions, the real source of their uniqueness is, in fact, the very hash function that produced it. So then, the question is, how do hash functions produce unique nonces?
Collision-Resistant Hash Functions
In a DPC Scheme nonces are unique because, in addition to a hash function being irreversible, it needs to be both computationally injective and collision resistant. Here are descriptions of the two properties.
- A hash function is computationally injective if it always evaluates the same text message to one unique hash value.
- It is collision resistant if no two distinct input messages can evaluate to the same number.
This is actually the power of collision-resistant hash (CRH) functions — that any small alteration to the input message evaluates to a different hash value.
One of the early infamous hash functions is MD5. The MD5 hash was used in the transport layer socket TLS1.2 protocol. However, as soon as researchers reported the existence of collisions, the hash function was phased off for use in internet browsers. Since then, better and more secure hash functions have been constructed. Although there are several proprietary hash functions, the FIPS’s state-of-the-art family of hash functions is SHA-3, also known as Keccak.
The DPC’s Zero-Knowledge Proof System
As mentioned above, the most crucial building block of the DPC Scheme is a cryptographic tool that enables users to produce verifiable computations — in the form of transactions with appended zero-knowledge proofs (ZKPs).
But what are these ZKPs? And what exactly does zero-knowledge mean?
Zero-Knowledge Proof Systems
A typical zero-knowledge (ZK) proof system involves a prover and a verifier, where the role of the prover is to produce proofs that attest to the fact that she knows some secret data w, called the witness. The verifier’s task, on the other end, is to verify the validity of the prover’s proofs. It is called zero-knowledge due to the requirement that proofs sent to the verifier must be convincing without leaking any other information about the witness w.
ZK proof systems can either be interactive or non-interactive. The most preferable being the non-interactive proof systems where both parties, prover and verifier, do not have to be simultaneously online for the duration of the proving and the verification processes. For brevity, it is common practice to refer to non-interactive zero-knowledge proofs as NIZKs.
Intrinsically, a NIZK consists of two algorithms — one for producing proofs and the other for verifying proofs — denoted by NIZK.Prove and NIZK.Verify, respectively.
For simplicity, we use an ‘interactive’ version of a ZKP to describe the two algorithms. It is often easy to see how non-interaction can be introduced in each specific context. The main difference is that — in the interactive case, the verifier has to send a randomly selected number x called a challenge, to the prover — whereas in the NIZK case, the challenge x can be uniquely computed by both parties.
The point here is, in either case, there is a challenge x and a related secret witness w.
The relation between the two is formally called an NP relation, denoted by R. (The ‘NP’ is used here as in NP complete problems, which alludes to the fact a problem can be solved in a non-deterministic polynomial time.) Indeed, the purpose of any proof system is to enable the prover to create a proof that attests to both her knowledge of the correct witness w and the fact that w is related to the verifier’s challenge x. The verifier, knowing that R(w, x) = 1 if the relation R holds true, and R(w, x) = 0 otherwise, can easily test the prover’s claim.
Typically, the prover uses the NIZK.Prove algorithm to do the following,
- Creates a proof prf that attests to the fact that she knows the witness w related to the challenge x.
- Sends the proof prf to the verifier.
On receipt of prf, the verifier uses the NIZK.Verify algorithm to check the correctness of prf as it relates to the challenge x. That is, he tests if the relation R between w and x holds true. He accepts prf as valid if R(w, x) = 1, and rejects it if R(w, x) = 0. Since the verifier does not know w, he needs a special verification algorithm V — that takes the proof prf and the challenge x as inputs — such that, V accepts prf as true if, and only if, R( x , w ) = 1. (Please note that, in the diagrams, proofs are always denoted by the Greek letter ‘pi’ in lowercase.)
The special verification algorithm V depends on the NIZK in context, as well as on the NP relation R involved. An example of such a NIZK is a SNARK, short for “Succinct Non-interactive ARgument of Knowledge.” For the difference between proofs and arguments, please see the addendum titled “Proofs vs. Arguments” at the end of this article.
Recursive Proofs Composition
In order to enhance efficiency of proofs, as well as improving scalability of blockchains, zero-knowledge proof systems are preferably deployed via a technique known as recursive proofs composition. In short, this method enables users (or blockchain nodes) to toggle roles between being verifiers of existing proofs and being provers who produce new proofs. The recursive proofs composition technique allows users to have a ‘validity snapshot’ of the entire history of transactions simply because each proof produced certifies the correctness of all previously verified proofs. This technique scales verification of proofs quite considerably since any new blockchain member need only verify the latest proof.
Recursive proofs composition typically applies to Groth-type pairing-based zk-SNARK, which uses two SNARKs where each SNARK is instantiated on its own special elliptic curve group. The pair of elliptic curve groups involved are chosen in such a way that they are not only compatible but also form what is called an amicable pair of pairing-friendly curves. The two SNARKs form a cycle in the sense that each can be used to verify correctness of proofs produced by the other, and vice versa. The details of this type of elliptic curve groups, their pair of SNARKs, and how they are deployed in a recursive proofs composition scheme, are much more technical for the intended audience of this article. We leave these details for a special article to be published soon. Technically-inclined readers, who are in a hurry to read more about recursive proofs composition, can read one of my previous articles here. Two real life deployments of this technique are the Halo and Coda protocols, or more recently Mina.
Bounded Recursion
ZEXE, however, employs an especially modified recursive proofs composition called bounded recursion. Although still utilising two elliptic curves, the niche here is that, instead of having two SNARKs that can verify each other’s correctness (hence having a ‘cycle’ of proofs as seen in Halo, Coda or Mina), bounded recursion settles for verification that only works in one-way. That is, it always uses a particular SNARK to verify proofs produced by another ‘prover’-SNARK, hence forming a ‘one-way chain’ as opposed to a ‘cycle’. To say the least, it’s like choosing to use a multi-coach train with a one-head motor-powered-coach to travel on a one-way railway circuit, instead of having two motor-powered-coaches on both ends of the train but never travel in the other direction.
Components of the DPC Scheme
The DPC Scheme interweaves the foregoing building blocks into its main components in an ingenious and purposeful way. The components are four algorithms, which we list here in the sequential order they would execute when a typical DPC Scheme session is running. We aim to highlight how the building blocks of DPC Scheme feature in each component.
The Setup Algorithm
The DPC Scheme firstly uses the DPC.Setup algorithm to generate all setup parameters needed to be used in creating valid transactions and their proofs, as well as verification of all transactions. These are parameters needed in initialising the commitment schemes CM and TCM, the CRH, and the Zero-knowledge proof system, often denoted by NIZK (short for Non-Interactive Zero-Knowledge).
Setup Ceremony — Briefly
The process of generating parameters is referred to as a setup ceremony. It has recently become popular to realize such setup ceremonies via multi-party computations (MPCs), which involve hundreds of participants from all over the globe. Most of these participants should ideally not be related to the very custodians of the systems being developed.
Using MPCs, together with other logistic mechanisms such as optimistic pipelining, and participation via web browsers, are proving to be helpful in scaling the number of participants. And thus making it possible for blockchain projects using zk-SNARKs to achieve some degree of decentralization, which has otherwise been illusive.
For a deeper understanding of how setup ceremonies work in the greater scheme of things, as well as a catch-up on how recent projects — including Aleo — have aimed to scale the number of participants, see this article here.
Aleo is most relevant to mention in this article because it is an instantiation of the ZEXE construction. The announcement of its setup ceremony can be found here.
The Address Key Generation Algorithm
Once setup parameters have been generated, each party can use the DPC Scheme’s second component, the DPC.GenAddress algorithm, to generate his or her own key pair; the address secret key (ask) and the address public key (apk).
The generation of the key pairs involves two of the DPC Scheme’s building blocks; the PRF to produce the address secret key, and the commitment scheme CM.Commit to produce the address public key.
The Execution Algorithm
The DPC.Execute algorithm is the third and main component of the DPC Scheme as it entails the entire process of producing verifiable computations. The primary tasks therefore are; executing transactions and producing their accompanying proofs.
A transaction is literally an exchange of assets (i.e., records) — some existing records are consumed and new ones are created — all done in compliance to the RNK. Note that the old records that are being exchanged appear in the ledger as commitments.
Record Consumption: The user who is carrying out the transaction uses a special function L.Prove(), in the ledger interface, to check if each commitment com_i indeed corresponds to a legitimate record r_i in the ledger. The output of L.Prove() is a special witness w_i .
Serial Numbers: A PRF, which takes the record owner’s secret key and the record’s serial number nonce rho_i, is used to output the serial number sn_i of the consumed record r_i.
New Records: A special DPC.RecordConstruct() algorithm is used to output the new record together with its commitment.
New Nonces: A CRH which takes the serial number of the consumed record r_i and some parameters as input, and outputs a unique serial number nonce rho_j of the newly created record r_j.
Ledger State: A ledger interface function L.Digest() computes the hash value of the current state of the ledger L. The output hash value is denoted by st_L, and forms part of the ultimate proof of the transaction.
Proof Production: First, the user constructs the challenge x_e (also called the instance) and the witness w_e with respect to an NP relation R_e. The NIZK.Prove algorithm takes three inputs — x_e and w_e, together with the relevant parameters pp_e — in order to produce the proof prf_e.
The overall output of the DPC.Execute algorithm, for when old records [r_i] are exchanged for new records [r_j], is the transaction tx — which we denote here as a tuple, tx = ([sn_i], [com_i], memo, (st_L, prf_e)), where ‘memo’ is the transaction memorandum. The user who produces the tx publishes it to the ledger L.
The Verify Algorithm
Just as imperative as the previous component, the DPC.Verify algorithm is most crucial to the DPC Scheme’s goal of producing verifiable computations.
Any user who wants to verify the correctness of published proofs, takes elements of the tx and inputs them into the DPC.Verify algorithm in order to test several things. In so doing he checks the following,
- If any of the serial numbers [sn_i] corresponding to consumed records has duplicates in the ledger.
- If each sn_i reflected in tx indeed corresponds to a record r_i that previously existed in the ledger L, by using the ledger interface function L.Contains().
- If the hash value of the ledger state st_L, which appears as part of tx’s proof elements, is valid. Here the verifier uses another ledger interface function denoted by L.ValidateDigest().
- In order to verify the proof prf_e of the NP relation R_e between the challenge x_e (also called the instance) and the secret witness w_e, the verifier uses the NIZK.Verify algorithm.
Conclusion
The four cryptographic building blocks of the DPC schemes are commonly used in privacy-preserving ledger-based systems. Yet, what is key to DPC schemes is the strategic way in which these primitives have been combined and interwoven to suit ZEXE’s distinct design.
We also noted how the four algorithms that constitute a DPC scheme incorporate either two or three of these building blocks or their outputs, in order to achieve its main functionality with full privacy. In addition to an already secure combination of cryptographic primitives, a trapdoor commitment scheme is used to ensure non-malleability.
What’s now left, is plugging-in state-of-the-art cryptographic primitives in order to realize a customised DPC scheme, upon which users can define and run their very own private decentralized applications.
Proofs vs. Arguments
The difference between proofs and arguments is found in a property called soundness, or rather how soundness is achieved.
Soundness has to do with the infeasibility of the adversarial prover to convince the verifier to accept an invalid proof or argument.
Definition 1. A proof system is sound if the probability for the verifier to accept a false proof is less than a third — probability < 1/3.
In other words, the soundness property of a proof system requires that any proof created from a false witness w should not be convincing to the verifier.
There are two important categories of soundness in proof systems, and these are statistical soundness and computational soundness. The distinction between the two categories is determined by the freedom or restrictions the system places on the prover’s computational capacity.
The following informal definitions are taken from Justin Thaler’s thesis.
Definition 2. Statistical soundness gives rise to proof systems where even a computationally unbounded prover cannot convince the verifier of a false statement (except with negligible probability).
Definition 3. Computational soundness gives rise to argument systems where it is required that a polynomial-time bound prover cannot convince the verifier of a false statement.
These two categories define the difference between proofs and arguments. In proofs, there is no bound placed on the prover’s computational capacity, whilst in arguments the prover is computationally bound to polynomial time strategies.
Therefore, a proof satisfies statistical soundness, while an argument satisfies computational soundness.
On ZEXE Documentation
Please note that once a home for the entire documentation of ZEXE is sorted, technical readers can find the extra details of the components of the DPC Scheme in their full mathematical glory. These will include much more detailed discussions on “The DPC’s Bounded Recursion” and the “Security Proof of The DPC Scheme.” … to be published here.
