zero knowledge proofs

Part 2 of 2: Zero Knowledge Proofs - Implementations and Applications (Zcash to Ren)

Feb 10, 2019, 3:11PM
18 min, 49 sec READ

A brief overview of zero-knowledge proof implementations/applications in blockchain-based systems (e.g., Ethereum, Zcash, Leverj, Coda, REN).

This is part two of a two-part series on zero-knowledge proofs. Part one examines in detail the family of cryptographic protocols known as zero-knowledge proofs including zk-SNARKS AND zk-STARKS. We recommend starting there.

Zcash: Bitcoin + Zerocoin. Implementation Specifics.

Zcash, a well-known and established early player in the cryptosphere, essentially builds upon Bitcoin's codebase (i.e., is a Bitcoin fork), extending the Bitcoin protocol with the added capacity to optionally cloak regular BTC transactions in a separate pool (of confidential ones) that hides from public view information about sender, receiver, balances or value transacted (allowing for selective disclosure to chosen parties under circumstances that require it). In that aspect, Zcash integrates the Zerocash protocol/cryptographic scheme (a peer-reviewed protocol for decentralized anonymous e-cash, originally proposed by Matthew Green in 2013) into a Bitcoin consensus protocol.

ZCash transaction pools: regular and shielded.

Generating the SNARK public parameters (the initial public/private key pair, the private part of which is to be destroyed) of Zcash takes place through a multi-party computation protocol (MPC) referred to as "the ceremony." Several participants each generate one shard of the public/private key set, then combine the public shards to generate the public parameters of the Zcash network and destroy the private shards (the MPC protocol ensures that as long as at least one of the six shards is destroyed the toxic waste will be impossible to recreate). 

Zcash node client.

Zero-knowledge transactions in Zcash are validated by turning the validation function into an equivalent arithmetic circuit, breaking down the logical steps into the smallest possible operations that could represent them. A matching constraint system (Rank 1 Constraint System, abbreviated R1CS) is then constructed to ensure correctness and everything gets bundled and translated into the polynomial language of a Quadratic Arithmetic Program (QAP), followed by the arbitrary checks of polynomials at randomly chosen sites in order to verify the proof. The process of constructing zk-SNARKs in Zcash is described in more detail here, while Vitalik Buterin explains QAPs in a blog post here.

Example of a transaction between shielded addresses from the Zchain block explorer.

Zcash launched in 2016 with well-known cryptographer, security specialist, and cypherpunk Zooko Wilcox as CEO. Aside from Professor Eli Ben-Sasson as the founding scientist, other notables names associated with the project include Arthur Breitman (Tezos) and Vitalik Buterin as advisors. The Zcash community forum can be found here and the updated protocol specification (November 14, 2018) here

ZClassic, a fork off Zcash, differs from its predecessor in that there are no founders fees (as with Zcash, where founders take 20% of the rewards for the first 4 years leading to a significant concentration of the supply) and all rewards go directly to the miners instead. Apart from that, ZClassic (ZCL) uses the same trusted parameters as Zcash. ZenCash is yet another branch off along the lines of ZClassic which tries to expand the ZK functionality (utilizing the same libsnark libraries) to include other trivial applications such as publishing, storage, secure chat, a treasury system, etc. ZenCash works with IOHK in researching and developing the specifications of some of its system components (such as the treasury system, DAG-like scalability solutions, etc.) and both it and, fairly recently, also Ethereum Classic (likewise IOHK affiliated) suffered 51% attacks which seriously put into question the viability of Proof-of-Work consensus systems.

Ethereum: Applications in Smart Contracts and dApps, Financial Engineering, Off-Chain Computations With Reliable On-Chain Verifications

The Ethereum Metropolis protocol upgrade introduced the ability to efficiently verify zk-SNARKs on-chain (allowing for certain contract variables to be effectively made private). So, rather than storing secret information on-chain, it can instead be stored with the users who are able to prove they are behaving in accordance with the rules of the contract via SNARKs (with each use requiring their own trusted setup, though once a circuit for a function exists it can easily be reproduced). 

While Zcash limits its scope of application to shielded UTXO coin payments and as such uses the same circuit/computation for every task in its zk-SNARK system setting, zk-SNARKs in Ethereum are not limited to a single computational problem but allow anyone to set up a specific zk-SNARK system for their specific function without having to launch a separate blockchain for the purpose (allowing for arbitrary off-chain computations to be verified on-chain). Some of the various applications of ZKP in Ethereum, including most recent developments, are illustrated and summarized in a nutshell in the examples that follow. These include a general purpose zk-SNARKs toolkit for on-chain verification of proofs (to be embedded in smart contracts), private and confidential transactions of Ethereum-based assets, loginless ZKP authentication schemes, etc.  

ZoKrates: A toolbox for zk-SNARKs on Ethereum

ZoKrates is a circuit compiler for zkSNARKs (developed by Cornell Blockchain) used for creating programs off-chain and linking them to the Ethereum blockchain, thereby expanding the capabilities of one's dApp. SNARKs allow for verifying computations on-chain for a fraction of the cost of running them and having an entire world (all nodes on the network) simultaneously execute them in order to verify their validity (something that is obviously impractical). The verification costs of zkSNARKs, in other words, are independent of their computational complexity (thus, block complexity limits also do not apply in zkSNARK formulations, allowing for throughput to be increased). 

With Byzantium, Ethereum introduced the zkSNARK precompiles (i.e., Elliptic Curve addition, scalar multiplication, pairing checks, etc.) that provide the necessary usable abstraction and tooling for zkSNARKs which allow for seamless integration with Ethereum (from program code specification to on-chain verification of the execution of the program code). 

ZoKrates provides a domain-specific high-level language with Python-like syntax for more conveniently specifying computations in a more abstract way (than arithmetic circuits or R1 constraint systems, though still somewhat closely resembling them). The compiler transforms these programs into provable constraint systems (arithmetic circuits similar to a sudoku puzzle) that allow for execution to be verified on-chain and from which the zkSNARK is generated. The package includes tools for setup phase, witness computation (finding a corresponding solution to the given constraint system), the proof generation itself and smart contract verification (as Solidity code that can be used to verify the computation on-chain, usually exported in the current working directory as verification.sol).

Jacob Eberhart giving a presentation about ZoKrates at an Ethereum Developers Conference (showing a sketch of the ZoKrates internal architecture).

The high-level language supports a primitive type (positive numbers), imperative statements and assertions, loops (for), conditionals (if-else) and defining of functions. Gas costs for on-chain verifications vary a bit depending on the number of input parameters given with the proof, but the main cost is constant and rather high (but remains fairly uniform, regardless of the complexity of the computation).

# compile
./zokrates compile -i new_program.code
# perform the setup phase
./zokrates setup
# execute the program
./zokrates compute-witness -a 337 113569
# generate a proof of computation
./zokrates generate-proof
# export a solidity verifier
./zokrates export-verifier

The above are the commands of the provided command-line interface for compiling code into an internal representation of arithmetic circuits. The program is compiled and executed off-chain, computing a witness for the compiled program (creating a witness file in ./witness) and generating a trusted setup for it (creating a proving key and a verifying key found at ./proving.key and ./verifying.key). 

The ZoKrates documentation is available here

Zk-Dai: Private Transactions of Stable Assets (MakerDAO Managed Insurance Derivatives)

A great example of how ZoKrates can be used is the zk-SNARK-based Dai transaction framework developed by a team at the recent ETHSingapore hackathon. ZkDai is a zero-knowledge implementation of MakerDAO's Dai - a stablecoin dynamically soft-pegged to the US dollar and managed by the Maker DAO (the MKR token holders), Ethereum's "central bank." 

A quick demonstration of manually creating a zkDai note using ZoKrates, Kyber swap, Truffle, and MetaMask.

The dApp uses Kyber swap to convert an amount or total value of tokens into Dai and then generates a proportionate value of zkDai (as a secret note) on-chain. A note is represented as a tuple of the public key of the note owner and the value of the note in Dai: 

Note = (ph, v)

What is saved on-chain however is the hash of that note, Hash(pk,v). In order to spend a note, one must zk-prove he knows the secret (private) key that corresponds to pk and the value of the note, producing a ZKP of the note hash on the on-chain registry (that is, a valid proof of the computation C(sk, v) = h, where h is a hash of the note). Zk-Dai notes are spent like UTXOs - notes amounting to the value to be transacted are bundled together and propagated to the receiver in form of a new zkDai note while any remaining leftover value becomes a new note assigned to the owner's key. 

ZkDai is similar to the AZTEC protocol we look into next, as both work via secret notes. These same principles could easily be applied to any other Ethereum asset, bringing a powerful tool for engineering of financial instruments (that introduce unique privacy properties) to the ecosystem.  

AZTEC: Anonymous Zero-knowledge Transactions With Efficient Communication

AZTEC is a ZK protocol on Ethereum that enables confidential transactions via encrypted 'notes' and join-splitting transactions. Instead of zk-SNARK schemes, however, it makes use of Boneh-Boyen signatures to create commitment schemes with highly efficient range proofs. AZTEC notes contain the Ethereum address of the note’s owner and an encrypted representation of how much ‘value’ the note holds ("commitment"), in addition to private information about the value of the note and a viewing key enabling decryption of the note (but not spending).

A crypto-asset that conforms to the AZTEC protocol will contain a note registry, which allows a smart contract to recover the public information of every unspent note that exists at present. A confidential transaction takes place by assigning value and ownership to notes and proving their relationship via AZTEC ZK proofs which the AZTEC token contract will validate and record in its note registry. The AZTEC token smart contract effectively serves as a custodian of the assets (ERC-20 tokens or other) while they are in confidential note form.

The paper of the AZTEC protocol specification is available here

Loginless ZK Authentication Systems (in App-specific Plasma Side-chains)

Leverj, a Plasma side-chain based hybrid exchange (previously written about) makes use of a loginless zero-knowledge authentication scheme on its platform. After registration with the exchange, ZKA (zero-knowledge authentication) is set up and the user is asked to sign a user agreement through the client software app (e.g., MetaMask). The server then validates the signature and creates an account with the respective Ethereum address associated with the API key.

The browser generates the API key using a web3 library alongside an associated secret key which is downloaded client-side without being transferred or stored server-side. The API key is mapped to its corresponding Ethereum account address via an on-chain Registry Contract that tracks key ownership and rights/privileges. The API key represented by the Ethereum address does not have access to a user’s funds but only authorizes trading.

The API key secret is stored in the browser’s local storage, and all requests to the server are signed using this key. This mechanism enables secure communication between user and server while avoiding session cookies thereby eliminating a range of commonly associated attack vectors.

Coda: Constant-Sized Blockchain via a Recursive Composition of zk-SNARKs

In terms of scalability, Coda is an example of a protocol maintaining a constant-sized blockchain (compressed into a tiny snapshot) via zk-SNARKs. In existing blockchain designs, the more people are transacting at a time, the harder and slower verification becomes. Coda makes it possible to effectively verify the entire blockchain while only downloading a small amount of data using a recursive composition of zk-SNARKs (based on cycles of elliptic curves). 

Traditional blockchain (above) and Coda (below).


Coda is developed by O(1) Labs who also maintain an OCaml front-end for writing R1CS (Rank 1 Constraint System) SNARKs for verifiable computation (based on the libsnark back-end) called Snarky

The Coda protocol specification paper (draft) is available here. There is also an Epicenter.tv podcast with CEO Evan Shapiro and CTO Izaak Meckler that covers in more detail the matters of blockchain scalability challenges, the succinct computational integrity technology Coda uses and the domain-specific language for zkSNARK computations (Snarky) employed.

Ren Project: Zero-Knowledge Dark Pools and Cross-Chain Swaps

A particularly ambitious undertaking utilizing ZKP technologies, Republic Protocol was incepted in 2017 with the purpose of building a decentralized solution for dark pools via secure multi-party computations. Generally, dark pools are mediums for trading derivatives, securities and other financial instruments in a way that maintains trades confidential, hidden from the open purview of the general investing public. Dark pools have been around for the last thirty-five years or so and a lot of exchanges and broker-dealers own dark pools (such as the large independent ones like Liquidnet and Instinet to the more broker-dealer-owned dark pools like J.P.Morgan or Fidelity). Roughly 15% of the volume of equities traded are said to take place on dark pools.

Republic Protocol began as a project aiming to come up with such solutions for the crypto-economy and went on to, in the process, evolve into the Ren Project, as explained in a recent blog post from January, "Ren - The Evolution of a Protocol":

For Republic Protocol, the way to achieve this privacy has been a bespoke secure multiparty computation (sMPC) engine. However, throughout our progress, community and stakeholder feedback has indicated that to realize the full potential of the dark pool, complete end-to-end privacy is needed at every stage of the user journey: keeping balances private, keeping order matching private, and even keeping on-chain settlement private. In response to this, we have evolved our sMPC engine into something more flexible and more powerful and begun research into suites of techniques and tools to achieve this end-to-end privacy. This culmination of these elements will become something far more powerful: Ren, an ecosystem of unstoppable privacy.

The initial approach while building Republic Protocol was to create a bespoke sMPC solution specialized for dark pools. However during the process of building the order matching engine using sMPC, we discovered that design limitations restricting the implementation of important dark pool functionality could be overcome if we created a general purpose virtual machine that was powered by our latest advancements to sMPC technology. This guided us towards building RenVM.

RenVM is the virtual machine and the core component underpinning the entire Ren stack, designed for carrying out any decentralized computation in complete privacy by leveraging a combination of secure multi-party computations (sMPCs) and zkSNARKs. The Ren stack includes a general zero-knowledge transaction layer extended with a cross-chain interoperability layer and a dark pool layer for secret order matching.

 

The Ren stack, underpinned by the RenVM, a virtual machine built around secure multi-party computations and zkSNARKs.

Darknodes in Ren constitute a separate off-chain peer-to-peer network running on a DHT (distributed hash tables) architecture that passively observes the Ethereum blockchain, keeping track of who registers and submits a REN bond (a good behavior bond) on Ethereum. This prevents potentially malicious nodes from coming along and entering the network. The web of darknodes is where computations are executed by individual nodes, complementing the servicing blockchain. While Ren/Republic is initially implemented on Ethereum, it could easily be deployed on any other chain providing similar smart contract functionalities.

zkTransaction Layer

The zkTransactor is a decentralized application deployed to RenVM. A private key is secretly generated for the origin blockchain (e.g., Ethereum) and only the zkTransactor has control over funds sent to it. Users can deposit balances into it (via the associated public key that designates the address) and zkTransactions are made between public addresses by interacting with the zkTransactor (which acts as a kind of autonomous mediator). All balances and transfers that way remain hidden. Users can at any time withdraw remaining balances or funds sent to the zkTransactor.

Such implementation easily resolves possible regulatory issues by supporting zkTransactors specific to different jurisdictions and able to prove compliance while at the same time minimizing potentially negative consequences from loss of privacy.  

SwapperD: A Wallet for Privacy Preserving Cross-Chain Swaps

SwapperD is to be a wallet interfacing with RenVM and zkTransactors that will provide privacy preserving cross-chain swaps seamlessly between different blockchains and ecosystems. By providing yet another mechanism for facilitating cross-chain interoperability, Ren aims to provide a simple, universal method for the entire industry to perform trustless swaps between blockchains, bridging the otherwise currently fragmented ecosystem.

As an audited, open-source tool, SwapperD is designed to be easily integrated into third-party applications serving as a standard for cross-chain settlements. Once zkTransactors have been completed for multiple blockchains, SwapperD will be upgraded to directly use RenVM for more efficient, more powerful, and completely secret cross-chain swaps. 

Dark Pools and Darknodes

RenEx is the officially supported dark pool that demonstrates the use of a hidden order book powered by Darknodes (live trading is done at ren.exchange). Defining a standard for a hidden order book would allow any party to set up and deploy their own dark pool exchange customized to their specific purposes and circumstances, each dark pool defining their own set of rules tailored to operate in different jurisdictions with their corresponding regulatory requirements and support for different settlement options, both centralized and decentralized. 

 

A peer-to-peer DHT network mapping keys to values on a blockchain. Ren darknodes form their own separate middleware that routes messages between nodes and maps authorized nodes to their staked REN on the blockchain (which stores value). Darknodes carry out computations between themselves that can then be verified as either valid or invalid on the blockchain via zero-knowledge proofs and zkSNARKs.

Notable Partnerships 

In September last year Ren announced their partnership with TrueUSD (which was then integrated with RenEx), a stablecoin legally backed and redeemable 1:1 with the US dollar. Unlike Tether (USDT), TUSD is directly redeemable for fiat via the app.truecoin.com portal. 

Ren is also one of the two merchants (the other being Kyber) involved in WBTC (Wrapped Bitcoin) that launched on the 31st of January this year.

Founders

Like other similarly oriented startups (e.g., DigixDAO), Republic Protocol is based in Singapore and at the time of running the ICO (in January 2018), CEO Taiyang Zhang was 21 years old. The team, including CTO Loong Wang, is mostly from Australia and the Australian National University. Wang, as can be seen from his LinkedIn profile, specializes in distributed systems and parallel/functional programming. 

Summary and Conclusion

Zero-knowledge proving schemes that preserve the confidentiality of transaction metadata are a crucial component of an open financial system, distributed crypto-economies and the permissionless public record-keeping that coordinates their activity. Various implementations allow for reducing the possible market impact of specific actions and larger orders, establishing dark pools and avoiding the unwanted attention of prying eyes and malicious opportunism. Additionally, they present significant implications for on-chain scalability by substantially minimizing on-chain footprint, moving complex computations off-chain (but being capable of reliably verifying their integrity). 

Other important applications include ensuring appropriate on-chain governance structures by providing verifiable, anonymous voting schemes that prevent information leakage. Using ZKPs, eligible voters can prove their right to cast a ballot without revealing their identity, making the voting system anonymous. In addition, ZKPs allow voters to request a verifiable proof that their vote was included in the final tally by the entity reporting the results. This makes the vote results auditable by the electoral body, even if the votes themselves are not visible on a public blockchain, while guaranteeing that the explicit rules of the procedure and protocol framework are legitimately followed through. 

Other distributed ledgers and system architectures will undoubtedly follow through along and implement their own versions of zero-knowledge proof systems as the space develops, evolves and matures. Either way, the potential applications of ZKP expand way beyond just cryptocurrencies and are subject to continuous ongoing academic and institutional research on many different fronts by many different kinds of actors (e.g., applications to do with security, detecting system sabotage attempts and counterfeiting, malware detection and anti-virus in distributed networks, eliminating the need for many kinds of escrow services, improving authentication systems and access control, more tightly structuring information and data flows and even potential applications in nuclear disarmament talks). 

That concludes part two of our two-part series on zero-knowledge proofs. Part one examines in detail the family of cryptographic protocols known as zero-knowledge proofs including zk-SNARKs and zk-STARKS.

Links and Resources

ZoKrates Gitter and documentation (for zkSNARK constructions on Ethereum).

Clipperz.is is a nice example of a simple SKP app - a zero-knowledge password manager and confidential data vault written in Javascript. Everything submitted is locally encrypted by the browser before transmitted with the passphrase known only to the user client-side. 

Zeroknowledge.fm is a podcast focusing on DLT and ZKP applications.  

Zcash public forum and Rocket chat.

primer on ZKP by Matthew Green

"ZkSNARKs in a Nutshell", a great explanatory paper by Christian Reitwießner.

Horizen (formerly ZenCash) official site.

ZClassic official site.

Disclaimer: information contained herein is provided without considering your personal circumstances, therefore should not be construed as financial advice, investment recommendation or an offer of, or solicitation for, any transactions in cryptocurrencies.