Road to PIVX 5.0 with zk-SNARKs

Preface

Media Press Release: https://pivx.org/zk-snarks-coming-to-pivx/

With the recent 4.0 core wallet release (Dec 18th, 2019), PIVX has made significant strides toward improved usability and adaptability through an improved Qt user interface built from scratch. Now, we are finally ready to make an announcement on the main focus area of the PIVX project: that is, Privacy.

In the selection process for PIVX’s next privacy protocol, an evaluation of the protocols used in the past was conducted and led us to highlight some desirable attributes for further research to be included in the new protocol such as:

Small and fast verifiable proofs
Merkle tree membership proofs
Arithmetic circuits
Non-fixed units for hidden amount
Trustless setup possibility

It also had to have a cryptographic construction and code flow that is proven to be effective in practice over an extended period of time, overseen by recognized authors, professors, and reviewers from the broader cryptographic community.

This concluded into a single natural progression for our work that we are excited to share with you now: Sapling Protocol [1] using Groth16 [2] zk-SNARKs [3] zero-knowledge proofs

Introduction to Zero-Knowledge Cryptography and zk-SNARKs

Zero-Knowledge proof is a cryptographic method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying (or unknowingly leaking) any information apart from one simple statement: that the statement being made is indeed true. A Zero-Knowledge protocol thus allows you to do something REALLY impressive. To prove that you know something without revealing what that something is. Put another way, let’s say you have knowledge of something, but do not want to share it (for a plethora of reasons. Security protocols, preventing hacking, etc). But you NEED to authenticate to another party/person/entity/computer that you indeed KNOW that. Dilemma. How do you do that without giving away that secret? That’s the very definition of “zero knowledge” -no (“zero”) information about the secret is revealed, but the second party (or any other party that needs to validate) is convinced (in full) that you know the information/data/details (that secret).

Why does this matter? Why would anyone need to prove that they know something without telling what that something is?
When you don’t trust the other person
When you trust the other person but don’t want PERSONAL details floating around online
When you are “neutral” about trusting the other person but need to complete some transaction.
When you need to persuade another person that you DO have/know something, and can demonstrate it in a mathematical and computational sound manner.

Let’s now apply this to PIVX and cryptocurrency transaction:

You want to make a purchase (online, or in a store). Obviously, the retailer needs to know you have the funds and that the funds can get sent. Otherwise, there is no transaction that can take place. SO, you need to demonstrate (prove) that you have enough money to pay for that item. BUT, you but you probably do NOT want to disclose the exact amount of your total holdings/account balance, etc to that individual/retailer. By using a Zero-Knowledge proof, this information (PROOF of your funds) can thus be transmitted and proven to be true without disclosing anything else. Your personal information is safe. Your identity is safe. Your total balance is safe. The retailer is satisfied (yes, you have the funds, thank you!) and you are satisfied you’ve demonstrated you have the sufficient funds to complete the transaction, knowing no other information was transmitted (or leaked or obtained by the retailer).

Sapling / zk-SNARKS (Groth16)

To start, zk-SNARK or, Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, refers to a method of proof construction where an individual has the ability to prove possession of certain information (e.g. private key) without having to reveal that information to another party anonymously and thus not have any interaction. So, zk-SNARKS are a way to perform a “zero-knowledge” transaction – a proof that allows two parties to prove that a statement between a prover and verifier is true, nothing more.

Sapling is an advanced privacy-enabling protocol developed by the Electric Coin Company [4], creator of Zcash [5], that combines all of the above highlighted technical aspects, along with a new cryptographic construction, standardizing a fully functional Decentralized Anonymous Payment (DAP) scheme leveraged on a novel form of zero-knowledge cryptography called the Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKS).

Sapling adds new highly usable types of transactions to the standard utxo-based blockchain that enable preserving the invisibility of transactional (meta) data while allowing the generation of zk-SNARKs proofs as small as 144 bytes within a matter of seconds on a low powered home computer. Thanks to this massive performance improvement in Sapling, private transactions become actually practical with < 1 second (~500ms) needed to execute a private transaction. On the receiving side, it should take the recipient <1 second (~10 ms) to verify that transaction. These times place a private transaction into the realms of acceptable when it comes to large scale transaction and verification times for global commerce.

Unlike the previous, now defunct Zerocoin protocol [6], Sapling does this in a much more complete fashion by hiding not only the sender’s data but also of the receiver, as well as the amount transacted, leading to a much more complete privacy.

Sapling Keys

The keys Sapling provides are slightly different from ones that were used in PIVX previously. With Sapling, an individual generates what is called a “spending key” – allowing them to perform a payment (what is the equivalent of having a secret/private key) and a “viewing key” which allows any individual who holds this key to see the payments received or emitted.

This viewing key can be thought of then as a public “statement” – for example it can be shared with an escrow attorney, regulator, etc for compliance purposes. However, one is not required to also share the spending (or private key).

Now, let’s say you want to receive a payment. You can generate an address from that viewing key and relay that to the individual sending funds. What is really nice about Sapling addresses is that they are diversified. With a single viewing key you can create or derive brand new addresses which in no way correlate to the previous one.

How does this affect help maintain privacy? By having uncorrelated receiving addresses, an individual thus prevents the potential leak of privacy whereby from one public key – it would be possible for different entities/individuals that are making payments to uncover the identity of the person being paid.

Sapling vs Zerocoin

In comparison with the previously used Zerocoin protocol, Sapling shares the same zero-knowledge concept but has been extended by creating a framework over zk-SNARKs to chain several statements in a single mathematical circuit that can be proven in a zero-knowledge manner.

Key advantages of Sapling:

Smaller and Faster – With Sapling using the Groth16 construct, each spend is only around 0.3KB; up to 70x smaller than what was possible with the Zerocoin protocol (at 22KB) while having a shorter verification time of under 6ms.

Easier to Use – With Sapling, users can simply manage privacy and/or transparency of every single transaction and its balance based on just the type of payment address used.

Enhanced Usability – With Sapling, users will be able to send or receive any coin amounts including decimals without being limited to set denomination unit sizes nor count as it was with Zerocoin.

Wider Acceptance – Sapling has been reviewed by a much wider cryptography audience with greater support.

More Potential – zk-SNARKS construction can be used in other areas such as program execution, and thus it is not as isolated in use as Zerocoin was. This also denotes broader acceptance, as well as continuous research and developments.

Sapling uses a public / private coin distinction approach similar to the Zerocoin protocol in order to break transaction traceability, but it has some key differences in how it is achieved and used by the end-user for both types of transactions.

In practice, Sapling achieves this by having two new types of addresses; Shielded (z) and Transparent (t) with following common transaction types:

Transparent Address (t) to Shielded Address (z) = Shielding Transaction
Shielded Address (z) to Shielded Address (z) = Shielded Transaction
Shielded Address (z) to Transparent Address (t) = De-shielding Transaction
Transparent Address (t) to Transparent Address (t) = De-shielded Transaction

So unlike Zerocoin, Sapling allows a full private transaction between two shielded addresses, as well as a more logical method of converting between two different types of coin’s privacy states.

There are also more advanced types of transactions, that can send coins to both the private address and a public address at the same time, enabling privacy of the balance while making certain details of the transaction public that demand/require them. (such as government or exchange transactions)

Additionally, Sapling allows multiple payments from multiple different sender addresses to be received by a single shielded address while maintaining privacy on the blockchain. It also allows efficient creation of payment addresses, where they all have the same full viewing key and incoming viewing key, which minimizes the blockchain scanning load of their transactions.

All in all, this system allows for a much more intuitive and user-transparent method of transacting the privacy-enabling zerocoins without the need for complex minting management that was necessary with the use of Zerocoin protocol.

The PIVX team believes that Sapling, with years of research and development put into it by numerous recognized developers and cryptographers, is the best-fit privacy protocol to achieve our needs for now, and into the future.

PIVX 5.0 Integration Phase

Now with PIVX, adding in the complexity of Proof of Stake (PoS), Cold Staking [7], tier two masternode network, along with its governance system, this will become quite an advanced implementation; in fact, it will be a world-first attempt at implementing Sapling / zk-SNARKs on a mainnet full-time PoS blockchain.

The initial integration phase is about ensuring that Sapling can be made to provide a complete privacy layer to PIVX. As expected, this will not only involve backend changes of radical magnitude but also a significant amount of GUI changes to the Qt wallet as well as developer operation configurations such as its associated libraries and Gitian setup, thus adding to the complexity of the integration and effort involvement.

Afterward, PIVX will aim to implement the new privacy protocol into the mobile realm, allowing for anonymous light transactions on the go simply with the use of the mobile wallet that incorporates the new privacy protocol.

In addition to the work mentioned above, there are many other research areas that may be conducted along the way or after such as private masternode collateral, private governance voting, private staking, and more.

But that’s not all. PIVX will also conduct further research on a major cryptographic component in an aim to implement a Trust-less setup; as described in the next section.

Beyond Trusted

Although it’s too early to be certain of the exact construct that will be used in the future, and while Sapling’s large 88 participants [8] multi-party computation (MPC) [9] is assumed highly secure in its construct, PIVX will strive to achieve a trust-less setup of Sapling in the near future; post initial implementation.

Some trust-less constructs being researched currently for this are Halo [10], Spartan [11], and SuperSonic [12].

What this means is that PIVX is aiming to remove the reliance on a trusted cryptographic proof that was created by random participants, in order to achieve a trustless zk-SNARKs proof setup, leading to post-quantum resistance before they become a significant risk.

Zerocoin Support Deprecation

Since the inception of Zerocoin protocol into PIVX back in 2017, we have had many progressive versions of zerocoins (zPIV), that had different levels of capability and support.

zPIV v1 = Zerocoin protocol inception.
zPIV v2 = Zerocoin protocol with hashed pub key serial.
zPIV v3 = Zerocoin protocol with zPIV v2 public spend.
zPIV v4 = Zerocoin protocol with zPIV v1 & v2 public spend using Schnorr signature.

But with the release of 5.0, the Zerocoin protocol will be replaced with Sapling and zk-SNARKs, which will result in the removal of support for all previous zPIV versions. Coincidentally, the new zerocoin that will be spawned under Sapling will be versioned as zPIV v5.

Due to this, we would like to advise that anyone with a positive zPIV balance to convert (spend) all zPIV back to PIV using the latest 4.x wallet prior to 5.0 release in order to retain access to the coins after the expected Sapling-activation hard fork. We will make a separate announcement on this with follow up reminders in hope to notify all zPIV owners before 5.0 is released.

Appendix. A

Privacy Evolution of PIVX

The following section presents how the PIVX privacy protocol evolved since its inception, including each of the researched and implemented steps. By learning the past, we can prepare for a better future.

1. Mixing “Obfuscation” Service – Coinjoin

In the beginning, this project had an early attempt at privacy, privacy by obfuscation; and was achieved by mixing transactions using a decentralized CoinJoin [13] service on top of tier two masternode network. By joining different owners’ outputs in a single transaction; the total amount to be sent was divided into several partial amounts of identical sizes and assigned to its own addresses.

This approach had obvious technical drawbacks as well as limited privacy capability. But it was a good first step into the blockchain transaction privacy.

2. First zero-knowledge proof protocol – Zerocoin

After an extended research period in 2017, PIVX decided to be one of the pioneers by implementing a customized version of one of the new zero-knowledge proof-based privacy protocols for native blockchains that the ecosystem had at that time; the Zerocoin protocol.

As proposed in 2013 by Miers et. al.; the Zerocoin protocol enabled transactions graph untraceability, and thereby origin anonymity, breaking the linkage between the inputs and the outputs on the public blockchain data. Using RSA accumulators, Pedersen commitments, and a predefined set of coin denominations to burn (mint) and create (spend) new exactly equivalent value coins.

This raw protocol had some drawbacks that were further researched and improved over time, like the storage space needed, large spend size, its limitation on amounts that it could send, and the trusted setup based on the 2048-RSA number.

Subsequent work was conducted by the PIVX development team into the zerocoin message serialization code to decrease the zerocoin spend size from 25KB to 21KB; which at the time was a significant 16% improvement over the original size.

3. For mobility – Zerocoin Light Node Protocol

New research and implementation, named Zerocoin Light Node Protocol (ZLNP) [14] was conducted in 2018 by PIVX to enable the capability to mint and spend zerocoin on less powerful mobile devices. With the use of round-robin style multi-party computation decoy process to minimize the amount of data required to perform the calculation, this for the very first time enabled mobile wallets to perform untraceable transactions utilizing the zerocoin protocol.

In this work, the need of a different membership proof structure instead of the RSA accumulator proofs became evident. The Merkle tree membership proof appeared in the scope for the very first time.

4. Zerocoin Small Signature of Knowledge – Bulletproofs

In collaboration with UCL (at the time) cryptographers Mary Maller and Jonathan Bootle, the PIVX team designed and implemented a new signature of knowledge (SoK) to drastically reduce the communication costs of zerocoin spends.

In order to do so, the proof of knowledge of the coin secret values has been modeled as a proof of knowledge of a solution to an arithmetic circuit. By rephrasing our problem in this manner, we were able to use the state-of-the-art non-interactive zero-knowledge proof protocol as presented in the PIVX GitHub’s Bulletproofs tree [15], reducing the size of the signature of knowledge by over 75% resulting in a 50% reduction on the total spend size. Thus, a zerocoin spend that previously occupied 21kb on-chain became ~10kb after this work!

NOTE: While fully functional, the new protocol was never integrated into the PIVX wallet as zerocoin was disabled before this significant research could be properly reviewed and implemented.

5. Zerocoin Trustless Setup
(Another work conducted in collaboration with Mary Maller and Jonathan Bootle)

— New membership proof, goodbye RSA accumulator —

Summarizing what this protocol does at a high level; it involved moving to a different membership proof written by Bayer and Groth (with Bootle’s optimizations) [16]. Instead of using the RSA accumulator for the coin’s membership proof, it uses a zero-knowledge argument for polynomial evaluation. This means that there is a public polynomial determined by the coins, inserted into the bulletproof protocol for showing the correctness of the serial number, and proving membership only if the polynomial evaluates to zero.

Like bulletproofs, the public parameters for this scheme are just random group elements that can be generated in a trustless manner. Relying on the discrete-log assumption and the random oracle model.

NOTE: While this research work was mostly finished, and several prototypes alongside the Bulletproofs work were created, it was never integrated into the PIVX wallet as zerocoin was disabled before this significant research could be properly reviewed.

Postface

This document acts as the next PIVX privacy protocol milestone establishment. In the upcoming articles, the team will be releasing further information about Sapling, including the first integration into our network prototype work, a FAQ, and delve deeper into possible future goals such as the trustless setup, lightweight privacy protocol for mobile applications, private governance and masternodes system, amongst other awesome ideas.