Building on Bulletproofs

Preface

In this post, I will explain how the Bulletproofs zero knowledge proof protocol works, as well as talk about the confidential asset protocol and confidential smart contract language we are building using Bulletproofs.

Background

Zero-knowledge range proofs are a key building block for confidential transaction systems, such as Confidential Transactions for Bitcoin, Chain’s Confidential Assets, and many other protocols. Range proofs allow a verifier to ensure that secret values, such as asset amounts, are nonnegative. This prevents a user from forging value by secretly using a negative amount. Since every transaction involves one or more range proofs, their efficiency, both in terms of proof size and verification time, is key to transaction performance.

Definitions

Commitment — a commitment Com(m) to message m is hiding, which means it does not reveal m. It is also binding, which means that if you make a commitment to m, you cannot open it to a different message m’. In the context of Bulletproofs, commitment refers to a Pedersen commitment, which has the additional property of being additively homomorphic, which means that Com(a) + Com(b) = Com(c) only if a + b = c.

Range Proof

Oleg Andreev’s stylized illustration of the Bulletproofs range proof protocol

Inner Product Proof

In the range proof section, I mentioned that our goal was to create a statement in the form of an inner product, for efficiency reasons. Let’s go into more detail on what an inner product is, and how we can prove an inner product efficiently!

Aggregated Range Proof

Aggregated range proofs are great for performance, because they allow m parties to produce an aggregated proof of their individual statements (m range proofs), such that the aggregated proof is smaller and faster to verify than m individual range proofs. The protocol for creating aggregated proofs is slightly more complex than creating individual range proofs, and requires a multi-party computation involving the parties. In our implementation, we used a centralized dealer to coordinate the communication between the m participating parties.

Constraint System Proof

A constraint system is a collection of two kinds of constraints:

A two-shuffle gadget, which adds constraints over variables that enforce that {C, D} are a valid shuffle of {A, B}.

Cloak

The goal of a Confidential Assets scheme is to make transactions in which the asset value and asset type are kept hidden, thereby allowing for multi-asset transactions in which external observers cannot deduce what is being transacted but can verify that the transactions are correct. Cloak is a Confidential Assets scheme built using Bulletproofs.

ZkVM

The goal of ZkVM is to make a smart contract language that allows for confidentiality. It builds upon previous smart contract language work, aiming for an expressive language that runs in a safe environment and outputs a deterministic log. It uses Cloak to validate that encrypted asset flows are correct, and uses Bulletproofs constraint system proofs to add constraints that values are being operated on and contracts are being executed correctly.

Summary

Overview of how the pieces of this post fit together

Acknowledgements

I worked with Henry de Valence and Oleg Andreev to understand and implement the Bulletproofs paper, as well as design and implement the Cloak protocol. The protocol research team at Interstellar is currently designing and implementing ZkVM.

--

--

Cryptographer, climber, explorer. Previously working on ZK proofs at Chain/Interstellar, now on Google’s cryptography security team.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cathie Yun

Cryptographer, climber, explorer. Previously working on ZK proofs at Chain/Interstellar, now on Google’s cryptography security team.