Monero Becomes Bulletproof
A complete look at Monero’s current technology stack and the significance of a new proof system called Bulletproofs.
A A couple of weeks ago, we shared some of the findings of our report on Zcash and made strong assertions about its technology. While we never intended for it to be an attack on Monero, it was certainly perceived as such by some in the community — especially after the media picked up the story.
What was overlooked was the fact that, like Zcash, we also see tremendous potential in Monero. We have written positively about Monero in multiple occasions in the past and still see it as one of the few projects that carries fundamental value in this vast sea of vaporware we call crypto.
Nevertheless, we stand by what we said in our public post on Zcash: the use of zk-SNARKs is the only practical way to completely unlink the identities engaged in a digital currency transaction. This assessment is not supposed to be read as controversial nor as an attack on Monero. In fact, I doubt any serious cryptographer would challenge this assumption. But as we recognized in our report on ZEC, there are serious trade-offs with this approach, such as the requirement of a trusted parameter generation ceremony.
The Monero community is clearly at odds with the requirement of trust. However, that has not prevented the project from experimenting with equally sophisticated technologies. There is a misconception in the community at large that Monero is based on established and well-understood technologies, whereas Zcash follows an experimental approach. In reality, however, there’s vibrant experimentation happening on both projects. In fact, as I will describe in this post, Monero and Zcash are about to be become cousins once Bulletproofs activate on Monero’s mainnet on Thursday.
Bulletproofs are a big deal, as they can increase the privacy of digital currency transactions and at the same time dramatically decrease their size. But to fully appreciate the significance of this update, let me first go over the three key pieces of technology that Monero currently employs in order to achieve privacy: Ring Signatures, Confidential Transactions and Stealth Addresses.
The idea behind a Ring Signature scheme is simple, yet very powerful. The true sender of a message combines his or her own signature with multiple other signers to create a unified digital signature. Rather than a single identity, this unified digital signature represents a group. E-cash pioneer David Chaum and researcher Eugene van Heyst first described such a system in a 1991 paper, when they were working with the Dutch government on a cryptographically-sound voting system.
Nearly a decade later, in 2001, Ronald Rivest, Adi Shamir and Yael Tauman expanded the concept of group signatures in a paper called “How to Leak a Secret.” In the paper, they depicted a situation where Bob, an official of the government of Kryptonia, wants to disclose a juicy secret about his country’s Prime Minister to the media, but does not want his identity to be compromised. To do that, Bob creates a ring signature scheme exclusively comprised of government officials, all of which have verified identities & signatures. When a message is signed by any one of them, outside entities can verify that sender is indeed an official, but all members are equally likely to be authors.
As it turns out, Ring Signatures can also be applied to digital currencies. The ring signature scheme described in the seminal CryptoNote white paper is conceptually similar to the system described above, but it specifically uses an implementation of Traceable Ring Signatures devised by researchers Fujisaki and Suzuki in a 2006 paper. This scheme granted more flexibility and privacy to ring signatures, but the basic idea is still the same: to disassociate a specific signer from a message.
The primary goal of a ring signature is to enable the true signer of a message to claim plausible deniability, where each signer in a group has equal chances of being the real signer. It’s as if the police had a list of suspects that may have committed a crime, but no direct evidence that points to a specific person to even begin an interrogation.
Similarly, CryptoNote proposed the use of ring signatures to sign digital currency transactions in a way that protects the privacy of the sender. It cleverly achieves that by pulling signers from past transactions in the blockchain and using their signatures as decoys. As a result, the real signer sending digital currency is mixed with signers of past transactions in the blockchain in an indistinguishable way:
In Monero’s terminology, a decoy signer pulled from historical transactions is called a mixin. The hypothetical transaction above has a mixin count of seven decoy signatures, in addition to the sender’s real signature, and a total ringsize of eight signatures. Note that this is a system of disassociation, where privacy is achieved by disassociating a single sender from a transaction. Sufficient privacy depends upon how many mixins a user decides to add to a transaction.
In Monero’s early history, users could potentially have 0 mixins in their transactions, or in other words, create a ring signature comprised solely of the true sender’s signature. Mining pools used 0 mixins when disbursing funds to constituents, which does not require privacy. However, as the Monero Research Labs originally found out, doing so hurts everyone else’s privacy. At the protocol’s current iteration, there is a mandatory ringsize of 7, but users can decide to increase ringsize as they wish.
In addition to Ring Signatures, Monero also employs an encoding scheme called Confidential Transactions (CT) that hides transaction amounts. They call this combination RingCT and it was activated on Monero’s mainnet in January of 2017. This was significant technical milestone for Monero, and a major divergence from its CrytpoNote origins.
RingCT Encoding != Encryption
To simplify the understanding of complex cryptography, I have used the word encryption in the past to describe NIZKPs in the context of Bulletproofs and zk-SNARKs. I’ve also seen members of the Monero community use the word encryption to describe how RingCT hides transaction amounts. We are all wrong.
Despite popular belief, Confidential Transactions use encoding (which keeps data hidden, immutable and verifiable), instead of encryption (which keeps data hidden and reversible). Here’s a great resource to learn more about the key differences. At a low level, the fundamental basis of Confidential Transactions is a cryptographic primitive for encoding called a Pedersen Commitment. For context, cryptographic primitives are the building blocks of systems that use cryptography and are comprised of well-established algorithms like the SHA-256 hash function.
The Pedersen commitment scheme used in RingCT has an additively homomorphic property, which, put (very) simply, allows multiple decoy inputs to be aggregated through addition. This guarantees that one of the encoded inputs is spendable/valid and that the sender is not double spending funds or creating XMR out of thin air. A by-product of this process is range proof that proves that the amount committed by a given Pedersen Commitment falls within a certain range and is not a negative number.
The Confidential Transactions scheme also requires a special signature across all encoded commits within a transaction; a type of signature called a Borromean Ring Signature. What this means is that when a Monero wallet generates a Ring Confidential Transaction, not only is the signature of all ring members aggregated, but so is the amount of each input, which effectively hides the transaction amount.
This idea dates back to 2013, when Blockstream co-founder and hashcash inventor Dr. Adam Back proposed on BitcoinTalk.org a system of “bitcoins with homomorphic values,” where transaction amounts could be encoded. In cryptography, homomorphism is often used to describe a type of encryption, and this might be why there is confusion as to what RingCT actually does. While CT was mostly envisioned by Greg Maxwell in the context of Bitcoin, the Monero Research Labs has been instrumental in testing this technology, which is beneficial to Bitcoin.
For Monero, the activation of RingCT was one of its most significant updates to date. The adoption of RingCT has undoubtedly improved the way Monero wallets can source decoys because it eliminates the requirement of the value of each mixin input to be of a common denomination, as required by CryptoNote.
Stealth Addresses
And while RingCT marked a big departure from the CryptoNote model, a lot of Monero’s stack is still very much based on it. An interesting proposition from the CryptoNote white paper was the idea of a “wrapped” address to protect receivers, which Monero still uses. Rather than having the receiver’s true address attached to an output and openly displayed, as is the case with Bitcoin, the sender instead can create a temporary one-time address that can only be identified by the receiver.
The term Stealth Address has been used to describe this mechanism and it provides a cleverly designed way to hide a transaction’s destination. Before broadcasting an XMR payment, the sender combines the receiver’s public keys with a random number in a key generating algorithm that creates a one-time key. The addition of randomness obfuscates the receiver’s address, but the receiver can still identify it once the transaction has been sent to the network. Only the true receiver can do that by scanning the blockchain for a specific data point called the key image.
The one-time key generator reference above is based on an Elliptic-curve Diffie-Hellman key exchange, which is a protocol where two parties agree on a key that unlocks a secret. In this case, the key image is an identifier that can only be located and spent by the intended receiver, which agreed on a common key with the sender. When a user sends XMR (or any CryptoNote-based cryptocurrency) to the receiver, there is a single public key associated with that output and only the receiver can recreate its private key counterpart.
A Testnet For Bitcoin Technologies
As mentioned earlier, there seems to be widespread belief that Monero is based on established and well-understood technologies. What we have found is that this assumption is far from true.
In fact, Monero at this time is serving as a stronger testing ground for experimental Bitcoin technologies than Litecoin, which is widely regarded as a “financially incentivized testnet” for Bitcoin. Starting earlier this year, Monero began testing yet another highly sophisticated piece of cryptographic magic: Bulletproofs. This technology is intended to address one of the main drawbacks of RingCT: the size of the range proofs this scheme produces.
After working on the Confidential Transactions scheme, Greg Maxwell, Andrew Poelstra and Pieter Wuille teamed up with researchers from the Stanford Applied Cryptography Group to make it more efficient. Their research focused on applying a non-interactive zero knowledge proof (NIZKP) system to aggregate all the range proofs of a Confidential Transaction and collectively prove their validity.
For context, the basic concept behind a zero-knowledge proof is to cryptographically prove that something exists, without knowing what that something is. This is achieved through a set of challenges that, if completed successfully, can statically prove that a party has a secret, without knowing what that secret is. This is the technology employed by Zcash to entirely shield senders, receivers and the amount of ZEC sent in a transaction.
Relative to zk-SNARKs, the NIZKP system proposed by the Bulletproof white paper has both benefits and drawbacks. On one hand, the use of NIZKP Bulletproofs does not require a trusted setup for parameter generation, like Zcash’s Powers of Tao ceremony. On the other hand, the verification of a Bulletproof is more time consuming than zk-SNARKs.
Beyond improving the privacy assumptions within Confidential Transactions, Bulletproofs have a much lower fingerprint (or size) relative to the proof systems used in blockchain networks today. In fact, much like SegWit, Bulletproofs can be seen as an approach to vertical scalability as they can greatly decrease the size of a cryptographic proof from over 10kB to less than 1kB. The Bulletproof white paper focused on applying NIZKPs to the Bitcoin blockchain and stated that, if implemented, total size of Bitcoin’s UTXO set would be only 17 GB (compared to 160 GB) if Confidential Transactions were to be implemented.
As discussed by MRL researcher Sarang Noether in December of 2017, under the current range proof format, the size of XMR transactions scales mostly linearly depending on the number of outputs (ex: 1 output = 7kB, 2 outputs = 13kB). Under bulletproofs, transaction sizes will then scale logarithmically instead (ex: 1 output = 2kB, 2 outputs = 2.5kB). Therefore, this technology has the potential to greatly contribute to Monero’s scalability.
The space savings granted by Bulletproofs may also enable the implementation of additional obfuscation mechanisms. As I have suggested to MRL, increasing the mandatory number of outputs in a transaction can make it significantly harder to trace balances by analyzing the blockchain. Decoys are used in Ring Signature inputs, but not in a transaction’s outputs. Implementing a system of decoy outputs will certainly increase the size of a transaction, but this increase may be trivial post Bulletproof activation.
Cousins Fight…
An interesting observation for the cryptography nerd: once Bulletproofs activate, Monero and Zcash will become cousins. Both make use of Non-Interactive Zero Knowledge Proofs that conceptually share a common ancestor: the Fiat-Shamir heuristic. Both Zcash and Monero have their fair share of virtues and drawbacks, and while they are often compared against each other, we believe both will succeed in the long run.
Connect with Digital Asset Research
For institutional investors who would like to subscribe DAR’s research, please submit a request for information here.
If you would like to sign up for our free daily newsletter, please sign up here.
Disclosure: this is not financial advice. The author owns both ZEC and XMR.
