zkSummit12

ZK12 is happening on October 8th 2024 in Lisbon. Join us to meet with top thinkers and builders to discuss the latest in zero knowledge research, zk use-cases, cryptographic primitives, privacy and maths.

This one-day event will consist of a mixture of topic oriented talks & workshops. Apply now!

The event is brought to you by Zero Knowledge Podcast, a show hosted by Anna Rose which explores zero knowledge systems and the decentralized technology powering Web3 and the community building it.

Find out more

See all videos of previous summits on our Youtube Channel. More information, check the zkSummit website and follow @zeroknowledgefm on Twitter.

by Anna Rose

What is ZEXE? (PART III)

DPC Recap

The idea of the records nano-kernel is Core to ZEXE, and enables a new cryptographic primitive called decentralized private computation (DPC). DPC is an application-ready framework that any developer can use to build custom applications. Transactions in the DPC scheme are executed in compliance with the RNK. These are decentralized by definition, since the RNK gives users control in determining the conditions under which their assets can be consumed through custom birth/death predicates.

The Record Nano-Kernel

Continuing to unravel ZEXE’s design, the next design-step was to strike a balance between the two aforementioned extremes in design. That is, supporting arbitrary functions, and using tags to identify functions.

Recall that the aim with ZEXE is to have concurrent processes share a ledger without violating the integrity or confidentiality of one another. An operating system of sorts is therefore needed to manage user-defined functions. Such management entails

providing process isolation
determining data ownership
handling inter-process communication.

ZEXE’s authors decided to formulate a minimalist shared execution environment that imposes simple, yet expressive, rules on how records may interact. That is, a “nano-kernel” that manages records, and hence called the Records Nano-Kernel (RNK). The RNK enables the management of records by allowing users to define special functions that inspect legitimacy and validity of records being consumed or created. So, records can only participate in transactions if they satisfy these functions.

Consequently, a record carries more information than usual. It contains a data payload, together with two user-defined functions called predicates, a birth predicate which is executed when r is created, and a death predicate which is executed when r is consumed.

By suitably programming these two predicates, a user fully dictates the conditions under which a record r is created or consumed. Predicates of all records that are involved in a transaction are given the transaction’s local data, as a common input. The transaction’s local data contains; every record’s contents, a transaction memorandum (i.e., the publicly revealed piece of shared memory), an auxiliary input (i.e., the memory piece kept hidden), and any other construction-specific data.

So, each predicate can independently check if the local data is valid according to its own logic. That way a record can protect against other records that may contain ‘bad’ birth or death predicates, since those should evaluate to ‘False’ given local data intended for another function.

As before, zero-knowledge proofs guarantee that both the death predicates of consumed records and birth predicates of created records are satisfied.

Predicate Examples under the RNK

The next examples illustrate how the RNK can be used to design applications, such as custom assets and conditional exchanges.

Example 1: Custom “Tokens” or Digital Assets

Consider the use case of custom digital assets. In this case, we want to create assets and subsequently conserve them. So we can use records with payloads that encode assets identifiers id, the initial asset supply v, and a value v. That is, payload=(id,v,v=v).

We fix the birth predicate in all such records to be a mint-or-conserve function, MoC. This means MoCis responsible for creating a new supply of a new asset and subsequently conserving the value. A record with the asset identifier id is either creating the initial supply of a new asset (“mint”) OR ensuring the total supply of the asset in circulation does not increase during a transfer between parties (“conserve”). The point here is that a record does not create an asset, but is in a way itself an asset!

Example 2: Conditional Exchanges

In addition to creating custom assets, users can program death predicates of records to enforce conditions on how assets can be consumed, and thus realising a conditional exchange with other parties.

If Alice wishes to exchange 100 units of an asset with id_1 for an equivalent 50 units of asset id_2, she creates a record r with 100 units of id_1 whose death predicate stipulates that any transaction tx consuming r must also create another record, consumable only by Alice with 50 units of asset id_2.

She then publishes out of band information about r for anyone to subsequently claim it by creating a transaction in which the exchange is carried out.

By design, death predicates are arbitrary and thus various access policies can be realised. For example, a user can enforce that a transaction redeeming a record

must be authorised by two-of-three public keys (i.e., using some multi-party computation),
becomes valid only after a given amount of time has lapsed since its creation (using time-locks), or
must reveal the pre-image of a hash function.

Transactions under the RNK

In ZEXE, generating a transaction involves creating commitments to new records as well as computing unique serial numbers for consumed records (similar to ZCash). Importantly, each commitment to a record requires the record owner’s address public key ‘apk’ and the serial number nonce. Similarly, the serial number of the consumed record r cannot be created without both the serial number nonce r and the owner’s address secret key ‘ask’. The serial number nonce of r is actually an output of a collision-resistant hash function that takes some unique transaction information that created r .

Note that the address secret key ‘ask’ is always taken as an input when the address public key ‘apk’ is generated. A transaction in Bitcoin or Zcash, for instance, allows a user to spend a coin only if she is in possession of the secret key. In ZEXE, the idea is much the same. What the RNK adds to the same condition for spending records is that all relevant predicates, set by the user who created the records to be spent, must be simultaneously satisfied.

The same conditions also govern the creation of zero-knowledge proofs that attests to correctness of the computation of the birth and death predicates over the provided local data. And therefore, if the user knows the secret keys of the records to be consumed and if all relevant predicates are satisfied, then the user can produce a zero knowledge proof to be appended to the transaction.

Figure 4: Illustrates the above description in more detail.

A Note About the RNK

The RNK is not a scripting mechanism, as in Bitcoin, but instead a framework that supports arbitrary programs. These programs can be run either as part of a single transaction, or across multiple transactions — by storing suitable intermediate state or message data in record payloads, or — by publishing that data in transaction memoranda (as plaintext or ciphertext as required).

Transactions can therefore realize any state transition, with consumed records as data read from the blockchain, and newly created records as data written back to the blockchain.

Delegated DPC

Heavy computations can be inevitable for some applications, which can cause problems for devices with limited computing capacity. To solve this problem, ZEXE provides another mode to DPC schemes: delegable DPC (or DDPC) schemes. This allows for time-consuming computations to be delegated to untrusted third parties. These third parties are given the necessary secrets to produce transactions, and submit the transactions back to the user, because the user does not disclose secrets needed to authorise transactions. The tradeoff of DDPC is that it no longer provides functional privacy. However, the operator cannot steal assets or deviate from the user’s signed intent in any way. So DDPC provides an additional option to speed up proof generation and computation time in exchange for slightly reduced privacy.

Conclusion

ZEXE was designed to enable private computation on public ledgers for arbitrary programs. This series of articles has focused on the context in which ZEXE is introduced among ledger-based systems, how transaction information has traditionally been handled in such systems, the number of technical problems that has plagued privacy-preserving ledger-based systems, the design techniques taken to eliminate these problems by the authors, and how these techniques can be implemented to achieve applications with true decentralisation, total privacy, as well as succinct verification.

The paradigm of decentralized private computation guarantees not only data but functional privacy. Execution occurs entirely offline, and published transactions are augmented with zero-knowledge proofs attesting to the correctness of the computation according to the birth/death predicates. Since the user-defined predicates are included in the statement being proved, under the zero-knowledge protocol, function calls are hidden and thus function privacy is achieved. Since these zero-knowledge proofs are succinct and verification is cheap, ZEXE also eliminates the Verifier’s Dilemma.

Beyond privacy, ZEXE’s approach also offers greater scalability compared to other ledger-based systems where the virtual machine is entirely on chain. Even more, newer cryptographic techniques such as recursive proofs composition potentially increase ZEXE’s scalability by orders of magnitude.

ZEXE aims to be a minimal, elegant protocol for supporting fully private applications. It extends prior ideas to achieve both privacy and programmability that heretofore have only been separately achieved by single-application systems. As a result, it provides an ideal platform for decentralized applications such as decentralized finance, gaming, authentication, and more. That’s why we chose to make ZEXE the basis of Aleo.

by Rachel White

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.

ZEXE provides a shared execution environment where multiple applications interact on the same ledger.
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.
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.
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:

The serial numbers of the consumed coins, { sn₁, sn₂, … , snₘ},
Commitments of the created coins, { com₁), com₂), … , comₙ) } , and
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,

The serial numbers of the consumed records, { sn_(old₁), sn_(old₂), … , sn_(oldₘ) },
Commitments of the created records, { com_(new₁), com_(new₂), … , com_(newₙ) } , and
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 Rachel White