Announcing Zerochain: Applying zk-SNARKs to Substrate

The first implementation of a privacy-preserving and account-based blockchain.

By Osuke(@zoom_zoomzo)

We are very excited to announce Zerochain which is a privacy-preserving blockchain on Substrate.

Zerochain is basically designed to store encrypted data. Usually, all data on blockchain is public and everyone can see it, while the data on Zerochain is encrypted so that no-one can see the data without the key for decryption.

Zerochain is built on Substrate which is the blockchain framework developed by Parity, and also using the bellman library developed by Zcash for zero-knowledge proof system. I appreciate these great implementations.

All implementations of Zerochain is an OSS, so you can see all of the code on GitHub and try running it, sending confidential transaction.

Basic features of Zerochain

A goal of Zerochain project is to be the infrastructure for developing decentralized applications using lots of kind of privacy-preserving computation and encrypted data.

The most obvious example of “the decentralized application for privacy-preserving” is confidential payment. For instance, the balance stored in smart contracts on ethereum is public, it is like the details of your bank account made public via the Internet.

All balances on Zerochain are encrypted to solve the above privacy problems.

Encrypted balance on Zerochain

Similarly, all transferred amounts are also encrypted, so anyone cannot see it.

Confidential payment on Zerochain

All information tied with accounts would not be public because the additive homomorphic property allows computation on ciphertexts for updating the encrypted balances. It is a basic idea for privacy-preserving in Zerochain that all data on blockchain would be encrypted (quite simple, isn’t it?).

Some of the most famous examples of privacy-preserving blockchains would be Zcash, Monero, and Grin. These take different zero-knowledge approaches, but all of these are UTXO-based blockchain. On the other hand, Zerochain is an account-based blockchain. The point is that the elements of Key-Value mappings are encrypted.

Zerochain is a first account-based blockchain implementation for privacy-preserving.

In addition, the pros of account-based are followings.

  • The optimization for the zero-knowledge proving cost

The cost of zero-knowledge proving usually represents as a number of constraints (similar to a number of multiplication gates in an arithmetic circuit).

The zero-knowledge proving in Zcash(Sapling) is 106,604 constraints. On the other hand, it is 18,278 constraints in Zerochain. It achieves reducing by 83 %! (w/o address anonymity)

  • The optimization for the on-chain storage cost

One of the big problem in UTXO-based is that the storage cost would be getting bigger and bigger because of the increasing UTXO and other metadata. But Zerochain is not the case because it is account-based, the encrypted balances are just overwritten for each transaction.

  • The flexibility for the privacy-preserving applications

UTXO-based is highly suitable for only payment. As I said above, Zerochain aims for being infrastructure for privacy-preserving Dapps, so more flexibility would be needed. Account-based is so much easier to add various functionalities like confidential whitelists for assets, anonymous voting, and hopefully arbitrary computation.

However, there are some cons for account-based which are like complex implementation for anonymous transactions and necessity protecting from front running attacks.

Zerochain and Substrate

As I said above, Zerochain is based on Substrate which is basically a blockchain framework. In particular, the core blockchain logics like the p2p network and consensus algorithm are provided by Substrate, and the privacy-protecting logics are provided by Zerochain top of it.

Zerochain on Substrate

Zerochain is a first implementation of privacy-preserving blockchain on Substrate. In the future, Zerochain would work as a privacy-preserving blockchain connecting to Polkadot network.

You can find more details of substrate here: https://docs.substrate.dev/

Dive into Zerochain

Zerochain has mainly three core techniques which are key components, encryption algorithm, and zero-knowledge proof system. I will describe these high-level schemes.

Key components

In Zerochain, a couple of key pairs are provided in order to get a privacy-preserving property and various authorities.

Key components

Basically, the authority level for keys is getting weaker as it goes bellow and each key has the specific features.

  • Origin Key: same as the secret key of usual blockchain(e.g. ethereum)
  • Proof Generation Key: the key for using computing zero-knowledge proofs
  • Signing Key: one-time key for signing a transaction to get anonymity
  • Verification Key: one-time key for verifying a signature to get anonymity
  • Decryption Key: the key for decrypting the transferred amounts and balances
  • Encryption Key: the key for encrypting the transferred amounts and balances (alias for address)

The separating authorities for keys allow these to specify their own features. For instance, you cannot steal the other’s balance just by getting the Decryption Key. You can only decrypt the balance and see what amount of coin he or she has. In other words, Decryption Key works as an auditable key to a specific account.

Additive homomorphic encryption

As I said above, all transferred amounts and balances are encrypted in Zerochain, but you have to compute(add or sub) these with encrypted at the time of the payment.

Zerochain achieves it by using the special encryption algorithm called “Additive homomorphic encryption”. As you can guess from the name, it can compute the addition(or subtraction) with encrypted. More specifically, Zerochain uses “Lifted-ElGamal encryption” to get efficient encryption and additive homomorphic property. (You can think it’s like Pedersen commitment in terms of additive homomorphic property, but Lifted-Elgamal is an asymmetric key encryption algorithm, not a commitment.)

  • Encryption

You can compute the ciphertext like bellow.

ciphertext:

where v: transferred amount, r: pseudorandomness, G: generator point, s: secret key (the corresponding public key: sG)

  • Decryption

You can decrypt it by using the given ciphertext and secret key.

Then, you realize you have to solve the discrete logarithm problem to get the amount “v”. Practically, “v” would be just a small bits integer (like 32bits) and vG(v=1,2,…) are computed in advance. (On the other hand, the secret key “s” and pseudorandom “r” will be a huge number so that one cannot solve the discrete logarithm.)

The decryption of Lifted-ElGamal is not efficient like this, but we chose it as an encryption algorithm in Zerochain due to the efficient encryption and the good compatibility with zero-knowledge proof.

  • Additive homomorphic

Let’s think the case the user has encrypted 10 coins as his balance, then is transferred encrypted 5 coins. That is the addition of ciphertext with v = 10 as balance and v’ = 5 as amount.

This is the same form as the ciphertext you see above. You can get the amount “15” by using secret key “s” in the same way. All the additions of ciphertext are computed on-chain at the time of updating the balance.

Zero-knowledge proof

What is Zero-knowledge proof? From the post of Zcash here.

“Zero-knowledge” proofs allow one party (the prover) to prove to another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself

A bit confusing though, basically that is getting the validity for the data sending to on-chain in the context of the blockchain.

Let’s think the case Alice sends encrypted 10 coins to Bob. In practice, Alice sends just a byte array(64 bytes) to on-chain because it’s encrypted. Can the nodes on the blockchain network validate whether the transaction is valid or not? In other words, does Alice actually encrypt the “10 coins”? Does Alice have more than “10 coins” in her encrypted balance? In addition, can the ciphertext be decrypted only by Alice or Bob?

All the above is impossible for nodes to validate these, just by giving “bytes array”. However, zero-knowledge proof makes it possible. It means zero-knowledge proof can give the validity for the above things without revealing the number of “10 coins”.

zk-SNARK which is a kind of Zero-knowledge proof systems is used in Zerochain. Particularly, the following things are proved and verified in the confidential payment.

  1. A transferred amount is within a valid range. (The amount is not negative.)
  2. A sender balance is within a valid range. (The remaining balance is not negative.)
  3. An encryption algorithm is correct by using the sender’s encryption key and the encrypted amount is correct.
  4. An encryption algorithm is correct by using the recipient’s encryption key and the encrypted amount is correct. (It should be the same value as 3.)
  5. An input balance proving in 2. is actually corresponding to the sender’s remaining balance.
  6. A signature verification key is computed correctly.

The zk-proof proving the above things with the encrypted amount are sent to blockchain and verify it on-chain.

BTW, I highly recommend you to watch the Zero Knowledge Summit #3 Videos (especially Harry’s talk for understanding the low-level SNARKs) to get the picture of Zero-knowledge Proofs.

As a summary, here is a high-level overview of the Zerochain scheme.

For more details, you can find it in the code. Feel free to submit issues and PRs.

What’s coming next?

The alpha-level implementation for confidential payment using zk-SNARKs have been already done, but lack of many basic features like…

  • Protecting from security issues like DoS and front running attacks
  • Computing zk-proofs on a browser as a wasm wallet(it gets better UX but additional security issues might come up)
  • An anonymous payment which is hiding addresses
  • Other zero-knowledge proof systems for mitigating the trusted setup (SONICs, Bulletproofs, zkSTARKs)

Feel free to ask any question. You can find me on Twitter or Gitter.