The Electric Coin Company (ECC) says it has discovered a new way to scale blockchains with “recursive proof composition”, proof to verify the entirety of a blockchain in a single function. For ECC and zcash, the new project, Halo, may hold the key to large-scale privacy.
A zero-knowledge evidence-based privacy coin called zk-SNARK, the current underlying protocol of zcash relies on “trust configurations”. These mathematical parameters have been used twice in the short history of zcash: when it launched in 2016 and when the first big protocol change, Sapling, in 2018.
Zcash hides transactions through zk-SNARKs but creating initial parameters remains a problem. By not destroying the mathematical basis of a transaction – the trust configuration – the holder can produce forged zcash.
Related: As crypto markets cool, who will pay for open source code?
In addition, the elaborate “ceremonies” that the zcash community undergoes to create the configurations of trust are costly and constitute a weak point for the entire system. The use of trust configurations with zk-SNARK was well known even before zcash’s debut in 2016. While other research has failed to close the gap, recursive evidence makes trust configurations a thing. from the past, says the ECC.
Speaking to CoinDesk, ECC engineer and Halo inventor Sean Bowe said composing recursive proofs was the result of years of work – on his part and others – and months of personal frustration. . In fact, he almost gave up three times.
Bowe started working for ECC after his interest in zk-SNARKs was noticed by ECC CEO and zcash co-founder Zooko Wilcox in 2015. After helping launch zcash and his first significant protocol change with Sapling, Bowe switched to full-time research with the company.
Prior to Halo, Bowe worked on a different zk-SNARK variant, Sonic, requiring only one trust setup.
Related: Zcash Electric Coin Co. Developer Reveals First Quarter Financial Loss
For most cypherpunks, this is one too many.
“People that we are also starting to think as early as 2008, we should be able to have evidence that can verify other evidence, what we call recursive evidence composition. This happened in 2014, ”Bowe told CoinDesk.
Proof, proof and more proof
Essentially, Bowe and Co. discovered a new method to prove the validity of transactions, albeit masked, by compressing compute data to the bare minimum. As the ECC article says, “evidence capable of verifying other instances of itself.”
Blockchain transactions such as bitcoin and zcash are based on elliptical curves with points on the curve serving as the basis for public and private keys. The public address can be thought of as the curve: we know what the elliptical curve looks like in general. What we don’t know is where the private addresses that reside on the curve are.
It is the function of zk-SNARKs to communicate on private addresses and transactions – if an address exists and where it exists on the curve – anonymously.
Bowe’s job is similar to bulletproof, another zk-SNARK that doesn’t require any trust setup. “What you should think of when you think of Halo is like recursive bulletproofs,” Bowe said.
From a technical point of view, bullet-proofs rely on the “domestic product argument”, which relays certain information about the curves to each other. Unfortunately, the argument is both very expensive and time consuming compared to your typical zk-SNARK check.
By proving multiple zk-SNARKs with just one, a task thought to be impossible until Bowe’s research, computational energy is reduced at a fraction of the cost.
“People have thought of bullet proofs in addition to bullet proofs. Problem, the bulletproof checker is extremely expensive because of the internal product argument, ”Bowe said. “I’m not exactly using bullet proofs, I’m using a previous idea that bullet proofs are built on.”
In fact, Bowe said recursive evidence means you can prove the entire bitcoin blockchain in less space than a bitcoin blockhead takes up – 80 bytes of data.
The future of zcash
Writing on Twitter, Wilcox said his company is currently investigating the implementation of Halo as a Layer 1 solution on zcash.
Layer 1 solutions are implementations in the code base that make up a blockchain. Most scaling solutions, like Bitcoin’s Lightning Network, are Layer 2 solutions built on top of the state of a blockchain. ECC’s interest in turning Halo into a Layer 1 solution is testament to the originality of the discovery as it will reside alongside code copied from the creator of Bitcoin himself, Satoshi Nakamoto.
ECC is exploring the use of Halo for Zcash both to eliminate trust configuration and to scale Zcash at Layer 1 using nested proofreading.
– zooko (@zooko) September 10, 2019
Since the early days of privacy coins, scaling has been a controversial issue: with so much data needed to hide transactions, how do you grow a global network?
Bowe and the ECC claim that recursive proof solves this dilemma: With just one proof needed to verify an entire blockchain, data problems could be a thing of the past:
“Privacy and scalability are two different concepts, but they fit together well here. About 5 years ago, academics were working on recursive snarks, some verifiable proof or some other proof [and even] verify several proofs. So what [recursive proof composition] means you only need one proof to verify an entire blockchain.
Of course, it’s not about grade two algebra: Bowe told CoinDesk that the proof alone took almost nine months of gluing various coins together.
A new way to tie
Another implication of recursive proof is the amount of data stored on the blockchain. Since the entire ledger can be checked in a single function, integrating new nodes will be easier than ever, Bowe said.
“You’re going to see blockchains that have a much higher capacity because you don’t have to communicate the whole story in one. The state chain remains to be seen. But if you want the whole network, you don’t need to download the entire blockchain.
While state chains should always be monitored for basic transaction verification, syncing the entire history of a blockchain – over 400 GB and 200 GB for Ethereum and Bitcoin respectively – becomes redundant.
For zcash, Halo means easier hard forks. Without reliable configurations, says ECC research, “proofs of state changes need only refer to the last proof, which removes the old history forever.”
When asked where his discovery stands compared to other advancements, Bowe spoke about its practicality:
“Where does that fit into the big scheme of things when it comes to cryptocurrency?” It is a cryptographic tool for compressing calculations… and scaling protocols. “
Image of the Rubix Cube via Shutterstock