What is ZEXE? (Part I)

Introduction

Distributed-ledger systems have become popular since the advent of cryptocurrencies. A typical distributed ledger scheme is built on a technology called blockchain, which is distinguished by a specific data structure that keeps records of transaction information in the form of blocks. These blocks of data are “chained” or linked together by a cryptographically computed number called a hash, and this hash uniquely identifies a given block.

Despite their growing popularity, distributed ledger systems schemes typically provide only limited privacy. Also, schemes that do provide privacy are typically limited in their expressiveness in terms of programs they support.

It was this problem that motivated privacy researchers (including several ZCash founding scientists) to come up with a scheme they called ZEXE, or Zero-knowledge EXEcution. ZEXE is the first ledger-based scheme in which applications can be executed trustlessly, privately, and scalably.

Although Aleo was founded by several of ZEXE’s authors, and the research is a key part of its computational model, Aleo is more than just ZEXE. It goes beyond by providing a full stack approach for writing private applications.

Nonetheless, ZEXE is a core component within Aleo. It has however remained relatively unknown outside of research circles. The purpose of this series of articles is therefore to provide additional context behind ZEXE’s design strategy, what it enables, and a description of real world applications that could be built using it.

Preliminaries

In order to appreciate ZEXE’s design, it is crucial to first understand a bit more about how cryptocurrencies work under the hood. So first, we begin with some additional context, and explain the underlying cryptographic primitives that make ZEXE possible.

Thus, in the next section, we’ll discuss some key concepts concerning privacy for cryptocurrencies, as well as two cryptographic primitives that are a key part of ZEXE and other privacy models: commitment schemes and zero-knowledge proofs.

Data Privacy and Function Privacy

In cryptocurrencies, a transaction is a record of some exchange of value, in the form of digital assets, from one wallet address to another. For example, a Bitcoin transaction is comprised of three parts; an input, an output and the amount being sent, although the amount is actually reflected as part of the output.

So if Bob is sending 50 BTC to Alice, then

1. the input is the old BTC address from which Bob initially received the 50 BTC, the previous transaction’s hash, and the signature of whoever signed those coins over to Bob
2. the amount is the 50 BTC that Bob is sending
3. the output often includes the above amount, Alice’s address, the hash of this current transaction, and Bob’s signature.

Anyone viewing the Bitcoin ledger can see this transaction information. Although the names of Bitcoin owners are not explicitly recorded, it is not difficult for a determined attacker with modest computing power to eventually associate addresses to real owners. For this reason, Bitcoin is pseudonymous, and doesn’t actually provide real privacy.

To address this problem, private cryptocurrencies like Monero use stealth addresses. That is, for each transaction, the sender A of coins chooses a random one-time address for the recipient B. By using stealth addresses only the sender and receiver can determine where a payment was sent. This is one way to introduce better privacy than Bitcoin.

Account-based systems such as Ethereum have even worse privacy properties, since each public key is repeatedly used as an address. However, Ethereum does provide additional programmability which other privacy schemes have largely lacked.

Commitment Schemes

A commitment scheme has the following three steps:

1. Key generation: (pk, vk)←key. The key generation algorithm outputs a pair of keys, the prover’s key pk and the verifier’s key vk, each is sent to the prover P and verifier V, respectively.
2. Commitment phase: (com, d)←Com(pk, m). The algorithm Com takes as input the prover’s key and the message to be committed. It then outputs the commitment com as well as an opening value d, to be sent to V only during the verification phase. The commitment com is sent to V.
3. Verification phase: b←Ver(vk, com, m, d). The algorithm Ver takes the verification key vk, commitment com, original message m and opening value d , as inputs. It outputs a boolean b, that is, either a success or failure.

Zero Knowledge Proofs

A zero-knowledge proof involves two parties, a prover P and a verifier V. The verifier V challenges the prover P to solve a given mathematical puzzle. The prover P then solves the puzzle but instead of sending the solution w to V, she creates a proof π that should convince V that she has correctly solved the puzzle without disclosing any information about her solution.

The main aim of zero-knowledge proofs is to enable V to easily ascertain the veracity of P ’s proof π and thus proceed with the transaction.

For a payments-use case as in Bitcoin, in order for any transaction to occur between two parties, the sender needs to commit to paying a certain value to the recipient. A commitment scheme is therefore needed to make a commitment which should be binding to the sender. But the scheme also needs to be hiding to the receiver in order to be properly zero-knowledge. That is, it should be infeasible for the recipient to determine the exact amount of the value committed unless the sender discloses it (i.e., sends to the recipient the secret key to reveal the amount).

So for Alice to privately send coins to Bob she needs to do two things:

• First, she uses a commitment scheme to ‘encrypt’ the value of the coins she wants to send to Bob. The committed value is not only hidden but also binding to A.
• Second, Alice creates a zero-knowledge proof π that attests to the fact that Alice is in possession of the coins she wants to send to Bob, yet which reveal nothing about the transaction.

Alice then publishes her commitment together with the corresponding zero-knowledge proof π.

Note that by implementing a commitment scheme and zero-knowledge proof as described above, one succeeds in hiding the inputs and outputs of a state transition, but not which transition function was being executed. This achieves data privacy because the sender, the receiver, and the amount being sent are all hidden.

In Part II, we’ll cover the ZEXE design strategy, and how the scheme implements the basic zero knowledge primitives to enable a powerful new paradigm: decentralized private computation.