How To Scale A Blockchain: New Advances In Recursive Composition of zk-SNARKs

Read on HALO

Introduction

What if I told you I could prove that I knew a value (x) without ever revealing x, but merely the validility of the statement.

You would probably think about it and wonder how thats possible. How can I prove, lets say, that I know the preimage of a hash, without ever revealing the preimage?

You could commit to the hash and then show the verifier the preimage, but in this case, you are still revealing x.

This is Zero-Knowledge Proofs and not until recently have the advances in this part of cryptography have had a major impact, and yet they are still underutilized.

Feel free to skip ahead if you already understand parts.

A Brief Introduction To Blockchains

Blockchain Technology and its use in cryptocurrencies such as Bitcoin, Ethereum, Neo, Monero, and Zcash has become a major talking point. At family discussions, I have been asked about Bitcoin and whether people should invest myself, and personally, it took me a large amount of time, maybe even years, to fully understand why blockchains are so important and the fundamental problem they solve.

Trust.

In most situations, we have to trust a third-party to process a payment, like Paypal, Venmo, or a Bank for example. In these situations, the third-party has quite some control over your money, and not only is your privacy for transactions ruined, but so is the security, as this third-party has full control over your money.

Scalability: An Issue With Blockchains

When I say scalability, what do I actually mean. To understand this, you must understand how a Blockchain works.

A Blockchain is a line of connected "blocks", each one with its own cryptographic hash linking them all together. Each new block requires a consensus mechanism, such as Proof of Work, or solving hard computational problems using your computer.

Scalability is the problem where after time, verifying the blockchain becomes difficult. Blockchains are ever-increasing, so they grow in size and to completely verify one takes downloading every block.

In terms of Scalability, a major problem becomes the size, often more than 50GB and ever-increasing, and verification time, which can take hours to days when verifying the blockchain.

Whats a Trusted Setup?

A Trusted Setup is a requirement for many zero-knowledge protocols. It involves a trusted party being required to create the setup for the zero-knowledge proofs to occur. Some zero-knowledge proofs, like Bulletproofs or ZK-STARKs, require no trusted setup at all.

In a trusted setup, you must trust that the individual or parties that setup the protocol, and believe they are not malicious or compromised, otherwise, the whole security of the system is compromised.

Recursive Composition of zk-SNARKs

zk-SNARKs, or Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge, are a big deal. They allow the proving of the knowledge of a certain value without ever revealing what that value is, only that the prover knows what the value is. It also does this without needing interaction between the prover and verifier, the non-interactive part of SNARKs.

Recursive Composition of zk-SNARKs is a whole nother beast. Imagine if I told you I could prove the validility of a statement that proves the validlilty of a statement and do this recursively, so that the size of the proof would remain constant in size.

This is what projects like CODA aim to do.

In a blockchain sense, this could keep the size of a blockchain constant, and so little that everyone can verify the blockchain by only downloading its current state.

The size of the blockchain remains fixed, constant in size. In CODA's case, the size remains at a steady 22kb, compared to most blockchains that overtime grow well over 50-100GB, and in time will reach TBs.

HALO: Recursive Proof Composition without a Trusted Setup

HALO, released by the same team who created Zcash, is a new method of recursive composition of zk-SNARKs without requiring a trusted setup and by using traditional elliptic curve cryptography as opposed to prime-order elliptic curves.

Sean’s discovery involves “nested amortization”— repeatedly collapsing multiple instances of hard problems together over cycles of elliptic curves so that computational proofs can be used to reason about themselves efficiently, which eliminates the need for a trusted setup.

Conclusion

zk-SNARKs, and related zero-knowledge proof algorithms show promising applications in Blockchains by reducing the size of proofs, allowing for recursive composition of proofs, and increasing privacy.

Advances in Zero-Knowledge Proofs, and especially the recursive composition of them, show promise for Blockchain Technology and the future of them.

Visit Homepage