An Introduction to zk-SNARK: Plonkup

04 January 2022Alexander Miles
  • Anoma Tangram
  • cryptography

As a consolidation of the Plonk and Plookup proving schemes, Plonkup represents an evolved zk-SNARK that provides a more efficient and scalable zero-knowledge solution.

Abstract

Zk-SNARKs offer impressive privacy contributions to blockchains and their users. As evolved zero-knowledge proofs, they enable considerable improvements for preserving secrecy of transactional information that could be exploitative to the sender and receiver. However, proof circuits thus far have been plagued with inefficiencies, mostly due to their computational intricacies which result in restricted performance. Plonkup combines the Plonk and Plookup proving schemes to deliver a more efficient proof circuit for hash functions. Distinguished by its utilization of non-arithmetic gates called “lookups” to help model hash functions in a circuit more efficiently, Plonkup establishes a zk-SNARK that provides blockchains with a more scalable zero-knowledge solution.

Introduction

Anoma utilizes zero-knowledge proofs, specifically zk-SNARKs and the advancements of this cryptographic primitive, to give users the ability to safe-guard financial information that could otherwise be exploited. Zk-SNARKs empower a novel form of privacy, where one can prove knowledge of certain information without revealing it. In addition, the proof construction removes the need for any direct interaction between the prover and verifier, further increasing the privacy threshold. This is achieved through a proving process that requires solving mathematical equations in an arithmetic circuit, resulting in a system that enables public verification of private data. By leveraging the evolution of cryptography in zk-SNARKs, Anoma’s ecosystem and underlying protocols provide privacy-preserving technology that allows users of the protocol to transact without revealing their personal information.

A short review of zk-SNARKs

Zk-SNARKs (also known as “Succinct Non-Interactive Arguments of Knowledge) enable users to send shielded transactions, effectively encrypting the sender and receiver, and the value exchanged - all of which aren't publicly visible. Thus, the transaction validity function that enables this operation must conclude whether the transaction is valid or not, without revealing any information that could lead to the identification of the user. On a high level, the proof that needs to be constructed in order to verify that a transaction is valid or not is facilitated by transforming what one wants to prove into a mathematical equivalent. These equations can be evaluated on a contending solution. The theoretical guarantee that arises from satisfying these properties ensures nothing about the data is ever learned, hence zero knowledge proofs.

The process of validating transactional information without revealing any information about it is computationally demanding. Zcash made considerable improvements to this process with the Sapling circuit, a network upgrade where shielded transactions were made more efficient. Groth16 was the underlying proving system that decreased the required amount of proof elements (the components that require proving) to complete a proof resulting in increased computational performance. Anoma utilizes zk-SNARKs with a Groth16 proving system in its original multi-asset shielded pool (MASP). As an extension of the Sapling circuit, MASP allows all assets to share the same shielded pool, increasing the anonymity set for users. MASP enables strong privacy guarantees for all assets transacting in the same shielded pool.

As an evolving product, the MASP’s underlying architecture is continuously being updated and improved. Over the last several months, a new proving system has been in development that could also be used in the MASP protocol. Dubbed “Plonkup," it combines Plonk (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge) and plookup (simplified polynomial protocol for lookup tables) to enhance the cryptographic primitives used in the multi-asset shielded pool as well as other products in the Anoma ecosystem, further advancing the effectiveness and capabilities of zk-SNARKs.

The construction of zk-SNARKs

Before explaining the distinguishing aspects of Plonkup, it is important to understand the existing composition of zero knowledge proofs. The concept entails creating logical bits of information from input values that can be computed to create a proof. Circuits are used to break down these steps into manageable operations. Similar to a boolean circuit, where the circuit model carries out mappings from specific inputs to specific outputs using AND/OR logic, zero knowledge proofs are made of up gates and wires using arithmetic operations. Gates symbolize operations (like addition or multiplication) and wires are responsible for transmitting data to and from a gate. Many proof circuits are associated with the function it computes (in this case certain hash functions).

Zk-SNARKs are designed to check the satisfaction of relations, and circuits are a suitable way to represent that. However, zero knowledge proof circuits are demanding to calculate and require a significant amount of computing power. This results in increased latency and high costs for the system responsible for executing transactions containing proofs. The underlying blockchain suffers from a decrease in performance and transaction throughput, especially when a prover is trying to generate a lot of transactions, whereas users sustain higher fees as an outcome of the computing power required for verification.

Transaction validity functions are a result of the translation of data by creating mathematical equivalents that establish an arithmetic circuit for verifying that these input values (which are private and thus never revealed) satisfy the desired properties via a constraint system. The more input values, the higher the complexity, which results in verifiers needing to check more constraints. Thankfully, a property of polynomials allows a verifier to check many constraints at once if those constraints are encoded into a few large polynomials. From there, a variety of mathematical techniques are used (like Groth16) to “hide” the evaluation process, which allows the verifiers to prove the validity of a transaction without exposing data that in turn could be exploited [1].

One of the concepts utilized by ZCash in the Sapling circuit that enables the ‘zero knowledge’ capabilities happens when users publish a “commitment,” which are stored as hashes. A commitment can be understood as a UTXO (Unspent Transaction Output) - an unspent balance on the blockchain - or more simply a “note.” It signifies a commitment to a new note which is created by a new payment (in this case a shielded one). Wallets are the user-friendly interface that displays all the UTXOs one owns, which amounts to a user's final wallet balance. Thus, UTXOs are nothing more than a locked up asset, amount, and spend authorization information. When a transaction is made, The sender’s UTXO is always consumed in their entirety and the new ‘change UTXO’ represents the new amount they have after a transaction is made. In parallel, another UTXO is produced which is what the receiver will obtain (the recipient amount).

Nullifiers are attached to commitments in a way that requires them to be revealed when a particular commitment is spent, thus preventing double-spending. Preventing double-spending in this context means making sure that once a shielded note is spent, another transaction can't spend the same note again (without revealing when a note is spent). When Alice sends Bob a shielded payment, Alice proves that she owns a UTXO to provide proof of spending power (i.e. Alice has the authority to spend the funds). The nullifier is then published as the preconditions are met for spending, enabling the blockchain to verify that it has not been spent before [2]. Although hashes are ubiquitous in the blockchain space and fundamental to privacy preservation, it is the zk-SNARK circuit as described above that empowers shielded transactions that don’t reveal any identifying information about the transaction itself.

What is Plonkup?

The Plonkup protocol is a zk-SNARK that combines the benefits of the Plonk and Plookup proving schemes. As an evolved proving system, Plonkup retains the privacy and scalability of preceding protocols but substantially increases efficiency. As a result, it saves space on the blockchain which enables a greater range of devices to participate in the network and even allows more flexible design choices for blockchain architectures.

Distinguishing Plonkup

As discussed before, zero knowledge proof circuits are resource-intensive. Furthermore, with previous proving systems like Groth16 and Plonk, there are some difficulties creating proofs of statements that include hash functions. This is because computing hash functions requires a lot of bitwise operations when using ordinary arithmetic. Zk-SNARKs are programmed with circuits that are expressed using ordinary arithmetic over a finite field. The elements of this field are large -at least 256 bits and often higher. To do bit-wise arithmetic in this field requires using one of these large field elements to represent each bit, which is terribly inefficient. In addition, the power it takes to calculate these hash functions makes them the most expensive component of a proof circuit, which also limits the amount of devices that can be used to participate in the proving system.

Plonkup solves this by employing "non-arithmetic" gates called “lookups” to help model hash functions in a circuit more efficiently. As a simplified, more elegant permutation argument, Plonkup integrates the advantages of Plonk (small proofs, fast verification and universal setup) with the additional function of lookups (from Plookup) to reduce circuit size. Lookups are then used as a custom gate inside of Plonk. A gate is a relationship that a row of the prover’s private inputs must satisfy. Plonkup supports arithmetic gates and lookup gates which can also be understood as constraints. Lookups are tables of precomputed values where the prover can show they have a row of that table without showing which row they have. In essence, lookups bypass the need for bit by bit arithmetic as the tables provide the values needed to satisfy the proof. Although complex, this concept is similar to having access to a list of functions (historically at the end of math textbooks) with the corresponding values which was used before the inception of calculators to provide a more accessible overview (and more efficient) for retrieving answers.

Figure 1
Figure 1: The Plonkup protocol analogized as a switchboard to represent gates and wires.

Another way of thinking about Plonkup is relating it to a switchboard as displayed in figure 1 and as presented in ZK Hack workshop 4. The switchboard includes three different types of gates: addition in green, multiplication in blue and lookup in orange. To be a part of a row (ex. A1-D1) means they must satisfy a particular constraint (in this case an additional constraint: A + B = C + D). For the lookup gate, the tuple must be a row in the table. From there, the gates can be connected (as shown in the right switchboard via “patch cables”). For example, you can connect to the two variables C1 and A2 where C 1= A2 which shows they need to have the same value enabling inter-gate connection.

Although Plonkup cannot be distinguished by its commitment scheme as it resorts to polynomial-based commitments, it inherits a from Plonk the property that any polynomial commitment scheme can be used with it, such as Kate commitments for small proofs and quick verification, Inner Product commitments for recursion and no trusted setup, or FRI for quantum resistance and no trusted setup (see below).

Plonkup and Anoma

Plonkup is an exciting evolution in the development of zk-SNARKs and also constitutes a crucial element in the Anoma stack. Specifically, it enables important aspects related to the privacy pillar of Anoma, allowing people to conduct transactions without publicly disclosing the contents of these exchanges. As MASP is the underlying circuit for shielded transactions on Anoma and already utilizes zk-SNARKs as an extension of the Sapling circuit, Plonkup will upgrade the MASP’s proving system to increase efficiency and simplify operability. By creating lookup gates for hash functions, the Blake2 hash utilized in MASP will be enhanced, eradicating a lot of bit by bit arithmetic needed for a proof circuit.

Furthermore, previous alterations to the protocol would necessitate a new trusted set up. Referred to as an ‘inaugural ceremony,’ a trusted setup is the establishment of the initial parameters which allow users to construct and verify transactions. However, the phase of conceiving such parameters requires the trusted party that creates the parameters also destroys them to prevent malicious behaviour such as creating counterfeit tokens. As Plonkup shares the advantage of universal setup from Plonk, this must only be done once and allows all the circuits used in Anoma to share the same trusted setup.

As Plonkup develops, additional features could be added. For example, early examination of Halo-style proofs presents a compelling opportunity for merging aspects of accumulation and recursion. For example, this could allow transaction clustering, where a single proof could be utilized to prove a particular cluster. This would result in more effective proving processes and provide more dynamic scalability for Anoma.

Conclusion

Built on years of cryptographic research, Plonkup introduces a new zk-SNARK that enhances efficiency, security and scalability. As a combination of the Plonk and Plookup proving schemes, it shares the benefits of both implementations, substantially decreasing circuit size for completing proofs.

Plonkup plays a crucial role in providing privacy on Anoma. As a foundational proving system, it provides a cryptographic backbone for a protocol which allows users to retain financial sovereignty. As an open source library, it also provides a tangible mechanism for dissolving elements of surveillance capitalism beyond its applications in Anoma.

Bibliography

  1. What are zk-SNARKs?, accessed: 2021-12-15
  2. Privacy Coins and zk-SNARKs: How Do They Work?, accessed: 2021-12-15

Explore Further: