Bulletproofs++: A Step Towards Fully Unlinkable Transactions With Multiple Asset Types
Blockstream Research

Bulletproofs++: A Step Towards Fully Unlinkable Transactions With Multiple Asset Types

Liam Eagen

Update: Bulletproofs++ has been accepted to Eurocrypt 2024, the Annual International Conference on the Theory and Applications of Cryptographic Techniques.

Privacy and security go hand in hand, as complementary and user-valued properties for Bitcoin. At Blockstream, we have been at the forefront of developing a range of methods to improve privacy for Bitcoin users, from wallet best practices in Green and Jade to developing MuSig2 and Confidential Transactions (CT). While vanilla Bitcoin transactions offer limited privacy, confidential transactions have made notable progress by keeping transaction amounts shielded. However, full anonymity remains elusive, and we describe here some new applied research paths towards that privacy target.

Fully unlinkable transactions, capable of shielding both the amount and transaction graph, have become increasingly of interest since Bitcoin’s inception. While cryptocurrencies like Monero and ZCash have achieved enhanced privacy with ring signatures and SNARKs, neither has enabled full anonymity with support for multiple asset types. Before full anonymity can be taken up, a crucial step lies in the advancement of Bulletproofs++ (BP++). This improvement aims to enhance the efficiency of confidential transactions while preserving its current multi-asset support without the need for a trusted setup.

Bulletproofs++ is a new, more efficient discrete log-based signature execution system, enabling us to improve the space efficiency of confidential transactions. Confidential transactions enable users to retain the privacy of their transaction amount, ensuring that the net flow of funds in a transaction is zero. To prevent secret inflation and “negative” outflow, confidential transaction protocols use range proofs to prove that each output amount falls within a positive range.

Early Privacy Preserving Protocols: Confidential Transactions

The current CT protocol deployed on Liquid uses Borromean Ring signatures for range proofs and Confidential Assets to support multiple asset types. This is one of the earliest deployed privacy preserving transaction protocols, and traces its roots directly to Greg Maxwell’s earliest work on zero-knowledge proofs and Bitcoin. Since then, zero-knowledge proofs have experienced an unprecedented level of development. Blockstream continues to play an active role in the broader zero-knowledge proof research ecosystem, in particular in the development of Bulletproofs (BP). BP was a landmark construction as it was the first to achieve concretely small proof sizes without a trusted setup.

Bulletproofs++: Compactness and Efficiency Improvement

The ability to store, transact and verify transactions cheaply is essential for any blockchain application. Naturally, we want any proof system used for private transactions to be as small and efficient to verify as possible, to limit the amount of data stored on the blockchain. BP++’s 64-bit range proof size is only 416 bytes, which is 39% smaller than BP and 10 times smaller than current Liquid range proofs. The reduced proof sizes would reduce the transaction fees and node storage requirements. On a regular commodity laptop, verification and proving of BP++ range proofs are about four times faster than BP, making BP++ more efficient for blockchain verification. Each BP++ range proof is about the size of seven Schnorr signatures and can be verified in the time it takes to verify 20 Schnorr signatures. Through BP++, we will bring all the improvements of BP and these additional improvements to Liquid.

In current Liquid CTs and BPs range proofs, we prove a value lies in a range by proving knowledge of the bits of the value. For example, to prove a value lies in [0, 2^64 -1] we would prove knowledge of 64 bits. Bulletproofs++ allows us to use larger bases, which reduces the number of digits we need to represent a number. For example, a value in [0, 2^64 - 1] can be represented using only 16 hex digits, a 4x reduction compared to bits. This is made possible using a novel technique called the reciprocal argument, which can implement a lookup argument. The reciprocal argument when instantiated as lookup is also known as the log derivative lookup argument.

Multiple Asset Support and The Reciprocal Argument

The reciprocal argument is a technique used within the Bulletproofs++ protocol to enable support for multiple assets in the same transaction. It essentially allows different types of tokens to participate in the transaction while keeping the types of all inputs and outputs private. The idea can be explained by using an analogy of a table inside a zero-knowledge proof.

We can think of the reciprocal argument as a way to use a table inside a zero-knowledge proof; given an index and an amount we can add or subtract that amount from the table at that index. Each input and each output of a transaction has a type and an amount. To check that all the amounts of each type balance, we will go through each input and add the amount to the table at the index given by the type. Then, we will go through each output and remove the amount from the table at the index given by its type. The transaction balances only if all the entries of the table are zero.

In pseudo code:

# Start with empty table
T = {}

# Add all the inputs
for (v, t) in I:
    T[t] += v

# Remove all the outputs
for (v, t) in O:
    T[t] -= v

# Check all the amounts in the table are zero
for (t, v) = T.items():
    assert(v == 0)

A Bulletproofs++ Implementation

Currently, we have merged the first of two PRs into libsecp256k1zkp implementing the norm argument. This builds on BP’s inner product argument and is the underlying primitive that gives BP++ their small size. Next, we'll merge the second PR that supports range proofs. After that, we will implement support for multiple assets and the necessary proofs to privately migrate existing assets to the BP++ asset format. Implementing in libsecp256k1zkp allows us to take advantage of the state-of-the-art performance of libsecp and easily deploy on Liquid.

Longer term, using the new flexibility of BP++ and some research directions at Blockstream, we see a path to robustly private transactions on Liquid, and potentially Bitcoin, which can also provide unlinkability between transactions and shield amounts (and shield types of assets in Liquid).

Unlinkable transaction protocols are at the cutting edge of zero-knowledge proof research, especially when implemented without a trusted setup. BP++ will form the confidential core of a multi-asset, unlinkable transaction protocol for Liquid.

In addition to the CT core, which will use the techniques developed in BP++, unlinkable transactions require proving much more complex statements. This area is still under active research.

Privacy has always been an important part of the Bitcoin ethos; money requires fungibility and fungibility requires privacy. Our goal is to bring this privacy to the Bitcoin ecosystem, with BP++ as the first step. Targeting Simplicity for an implementation of BP++ will allow any project that supports Simplicity to integrate and interoperate with BP++.

To learn more, read the latest version of the “Bulletproofs++: Next Generation Confidential Transactions via Reciprocal Set Membership Arguments” paper, currently hosted and freely available on the IACR eprint archive, and review our work-in-progress implementation on GitHub.

If you have specific preferences, please, mark the topic(s) you would like to read: