What is ZEXE? (Part II)

ZEXE Design Strategy

ZEXE is a scheme for privacy-preserving, decentralized applications such as decentralized exchanges. It is designed to utilize a ledger-based system, and support multiple functionalites. These include user-defined fungible assets, cross-application communication, and public auditability. And of course, all of these are to be achieved in a zero-knowledge manner.

In order to realize the above goals, ZEXE breaks from existing private blockchains in several ways.

1. ZEXE provides a shared execution environment where multiple applications interact on the same ledger.
2. The content of a transaction is no longer restricted to transfers of value, but instead represents a more general data unit called a record. Moreover, users can define their own functions with associated predicates that stipulate conditions under which assets can be spent, without the need to request permission to do so.
3. Rather than an on-chain execution environment, ZEXE opts for offline computations that generate transactions and attach to each transaction a zero-knowledge proof that attest to their correct execution.
4. The result is a protocol for a new cryptographic primitive dubbed decentralized private computation (DPC).

Zerocash Transactions

The first real-world system which used commitment schemes and zero-knowledge proofs to provide privacy was Zerocash. A Zerocash transaction tx is an ‘operation’ that consumes old coin commitments as inputs, and outputs commitments of newly created coins together with a zero-knowledge proof which attests to correct transaction computations. See Fig. 1, below.

On the ledger, each transaction consists of:

1. The serial numbers of the consumed coins, { sn₁, sn₂, … , snₘ},
2. Commitments of the created coins, { com₁), com₂), … , comₙ) } , and
3. A zero-knowledge proof π attesting to two facts,

(i) that the serial numbers consumed belong to coins created in the past (without identifying which ones, thus ensuring privacy for parties to a transaction),

(ii) that the commitments contain new coins of the same total value of coins consumed (ensuring the overall economic integrity of the system).

That’s how the Zerocash system uses zero-knowledge proofs to ensure once-off consumption of coins, and consequently prevent double-spending. See Figure-1 below.

Note that indices of the coin commitments in Fig. 1 above are not repeated. The three new commitments are labelled 4, 5, and 6, and not 1, 2, and 3, in order to signify uniqueness of commitments. Similarly, every coin has a unique serial number sn, and no two coins can share a serial number.

A Zerocash transaction is therefore private because it only reveals how many coins were consumed and how many were created, but the value of the coins is kept secret. As previously mentioned, this provides data privacy. And, in the case of Zerocash being a single functionality protocol, function privacy is achieved by default because there is no need to distinguish one function from another.

Extending the Zerocash Computational Model

Zerocash was a breakthrough with regard to privacy for distributed ledger systems. But unfortunately, the scheme is limited in the functionality it provides. What if we wanted to do more than a simple private transfer of assets?

Take Ethereum, for instance, which supports thousands of separate ERC-20 “token” contracts, each representing a distinct currency on the Ethereum ledger. In handling all the various cross currency transactions, many function calls are involved and these are each embedded to specific applications. But since every application’s internal state is public, so is the history of function calls associated with each.

Even if each of these contracts would individually adopt a zero-knowledge protocol such as Zerocash to hide details about token payments, the corresponding transaction would still reveal which token was being exchanged. Consequently, although inputs and outputs of state transitions are hidden and thus achieve data privacy, the transition functions being executed are in the open. Thus, achieving function privacy in the model of Ethereum is not possible.

ZEXE was motivated by this exact problem. In ZEXE, the goal is not only to provide data privacy (as in Zerocash) but also functional privacy. So a passive observer of the blockchain wouldn’t know anything about the application being run, nor be able to identify the parties involved. Therefore, the ZEXE model can support rich applications such as private dApps, dark pools, and private stablecoins. The programming model also allows multiple applications to interact on the same ledger, as well as promoting user-defined functions in order to achieve a totally decentralized system.

The Verifier’s Dilemma

Another appealing attribute of ledger-based systems is auditability. Whether one is a regulator or new user of a blockchain, the ability to easily verify the veracity of historic transactions is crucial.

Unfortunately, many ledger-based systems achieve public auditability via direct verification of state transitions. And such a verification method of transactions regrettably involves re-execution of the associated computations. The problem with this method is that large computations take a long time to be completed, leaving the network prone to denial-of-service (DoS) attacks.

Early smart contract blockchains such as Ethereum addressed this problem through the mechanism of gas, making users pay for longer computations, acting as a deterrent against DoS attacks. The drawback with this approach is that verification is still expensive. Furthermore, unlike solving the Proof-of-Work puzzle to find the next block, verifying transactions isn’t profitable. This is the quandary known as the Verifier’s Dilemma. In the past, this problem has caused forks in prominent blockchains like Bitcoin and Ethereum.

Unlike other blockchains, program execution in ZEXE occurs off-chain. Furthermore, by using zk-SNARKs, verification of proofs is cheap for the on-chain miners or validators. Therefore, ZEXE is effectively a solution to the Verifier’s Dilemma.

Achieving Zero Knowledge Execution

We begin with Zerocash, a protocol designed for applications with single functionality, that is, a transfer of value within the same currency. Zcash is one example of a cryptocurrency system that uses the Zerocash protocol. It uses zero-knowledge proofs (zk-SNARKs) to achieve privacy. The goal of ZEXE is to extend this protocol beyond single applications to any arbitrary program.

Records as Data Units

The first step is a switch from coins to records as data units. That is, instead of just an integer value, a record stores some arbitrary data payload. So instead of a simple transfer of value as in Zerocash, ZEXE works with arbitrary functions , as long as they are known to everyone in advance.

This change enables ZEXE to support arbitrary programs. But what about privacy?

In the public’s eye, a transaction can again be imagined as an operation that consumes old record commitments, and outputs newly created record commitments together with a zero-knowledge proof.

The structure of a record is illustrated in Figure 2 below:

At creation of a record, its commitment is published on the ledger, and its serial number is published only after the record is consumed. This time, the zero-knowledge proof attests that applying the function on the old records produced the new records.

As in the Zerocash case, each transaction on the ledger consists of,

1. The serial numbers of the consumed records, { sn_(old₁), sn_(old₂), … , sn_(oldₘ) },
2. Commitments of the created records, { com_(new₁), com_(new₂), … , com_(newₙ) } , and
3. A zero-knowledge proof π attesting to two facts,

(i) first, that the serial numbers belong to records created in the past (without disclosing the records),

(ii) second, that the commitments contain new records of the equivalent total value of records consumed.

Supporting Arbitrary Functions

The second step is to enable multiple users to freely define their own functions and allow the functions to interact without any rules. This could be achieved via the same approach outlined in the previous step. That is, by allowing a user to fix a single function Φ that is universal, and then interpret data payloads dpᵢ as user-defined functions Φ = dpᵢ that are provided as inputs to Φ.

Using zero-knowledge proofs as in Zerocash would ensure function privacy. However, merely allowing users to define their functions does not in itself result in any useful functionality overall.

Function privacy, in this scenario, creates problems because there is no way for users to determine whether a given record was created according to any given function in a legitimate way. And given the inevitable presence of malicious users, honest users are therefore not protected from all sorts of fraud.

This particular design approach, of unrestrained freedom in users freely defining functions, is of course an extreme. The lack of rules that govern how user-defined functions can interact is the very root of its failure. But can this idea be salvaged? The answer is yes, and we see how in the next section.

Using Tags to Identify Functions

The third step in this design journey is to introduce unique identifiers to each user-defined function, Φ. That is, we include a function identification-tag to each record and use the id-tag as a way to determine which function was used to create the record. This can be done in a zero-knowledge manner. Perhaps the id-tag is defined as a hash value of the function Φ evaluated at a given value vᵢ. That is, idᵢ = H(Φ (vᵢ)). And hence, each function Φ will have a unique id-tag idᵢ if the hash function is collision-resistant.

Since having ‘no rules’ was the root problem in the foregoing fraud-riddled approach, one rule can be enforced in this case. That is, only records with the same id-tag are allowed to cooperate in the same transaction.

Zero-knowledge proofs can guarantee that records participating in the same transaction indeed have the same function id-tag. This will guarantee that only records created by the same function participate in the same transaction.

Although this type of a system provides reasonable functionality, it suffers from a complete and total process segregation. As a result, even a simple coin swap cannot be achieved. But, it represents a step in the right direction.

In Part III, we’ll discuss how the records nano-kernel enables a new cryptographic primitive called decentralized private computation (DPC), an application-ready framework that any developer can use to build private applications.

---

by Anna Rose