PIVX - The World’s First Bulletproofs Implemented Zerocoin Protocol

PIVX is excited to announce the world’s first Bulletproofs implemented Zerocoin protocol” that has just been made public in our PIVX GitHub. It has been developed by the PIVX core development team (mainly Random Zebra & Furszy) with the cryptography work done by cryptographers Mary Maller & Jonathan Bootle where the signature of knowledge algorithm has been changed drastically to enable much smaller proof sizes. This change results in significant reductions of Zerocoin transaction size, blockchain growth rate and improved verification time. We welcome all auditors to review the code and will also follow up to ensure it gets third-party audits. Once the core wallet version 3.2 is released, this build can also be tested on our updated testnet.
What’s the big deal?

The main goal of the project was to improve the efficiency and scalability of the Zerocoin Protocol. In particular, we were aiming at reducing – so-called, “communication costs” (the amount of exchanged data in each session, which ultimately is data that is recorded forever into the blockchain). More specifically each zerocoin spend transaction required more than 20 kB space. It contains, among other things, two zero knowledge proofs (the Accumulator Proof of Knowledge, which takes about 5kB, and the Serial Number Signature of Knowledge, which took almost 14kB). We worked on the latter. We have re-modeled the problem as something known as an “arithmetic circuit”. Arithmetic circuits are a generalized method for describing problems from complexity theory.

There is a wealth of zero-knowledge algorithms designed for proving knowledge of a solution to an arithmetic circuit in the cryptographic literature. We choose to use Bulletproofs because these are well suited to smaller circuits, such as ours and are very efficient.

Bulletproofs were invented by Bootle, Cerulli, Chaidos, Groth, and Petit and improved by Bunz, Bootle, Boneh, Poelstra and Maxwell. As the Standford site states:

Bulletproofs are short non-interactive zero-knowledge proofs that require no trusted setup. A bulletproof can be used to convince a verifier that an encrypted plaintext is well formed. For example, prove that an encrypted number is in a given range, without revealing anything else about the number. Compared to SNARKs, Bulletproofs require no trusted setup. However, verifying a bulletproof is more time consuming than verifying a SNARK proof.

Bulletproofs are designed to enable efficient confidential transactions in Bitcoin and other cryptocurrencies. Bulletproofs have many other applications in cryptographic protocols, such as shortening proofs of solvency, short verifiable shuffles, confidential smart contracts, and as a general drop-in replacement for Sigma-protocols. To our knowledge, this is the first (and only) application of Bulletproofs to the zerocoin protocol signature of knowledge.

With this technique we were able to shrink the size of the signature of knowledge from 14 kB to about 4 kB (a 71% reduction in communication costs) thus making the whole spend transaction half the size (about 10 kB).

This was achieved while maintaining performance (times required to produce/verify the spend) comparable, if not slightly better, than the old protocol (despite the increased complexity and computational costs).

Next iteration of the protocol, currently in development, involves the Accumulator Proof of Knowledge and further improvements to the Serial Number Signature of knowledge.

https://pivx.org/the-worlds-first-bulletproofs-implemented-zerocoin-protocol/