Articles tagged "zerocash"

Privacy Technologies for Bitcoin

Introduction

The world still needs Zerocash even though we now have Confidential Transactions.

A message from Zooko Wilcox-O'Hearn:

At Least Authority, our mission is to bring verifiable end-to-end security to every user of the Internet. As a part of this mission, we are working on something that we can't announce yet, but it involves the Zerocash protocol for private Bitcoin transactions.

Recently Blockstream announced Sidechains Elements, which includes a privacy protocol named Confidential Transactions. We invited the lead author of Confidential Transactions — Greg Maxwell — and the authors of the Zerocash Protocol to help us explain how Confidential Transactions compares to Zerocash.

In short, Zerocash offers privacy properties that Confidential Transactions does not. Most notably, Confidential Transactions only protects transaction values, whereas Zerocash also protects sender and receiver addresses – but at the cost of extra cryptographic novelty. In addition, there are other engineering and cryptography tradeoffs between the two.

—Zooko Wilcox-O'Hearn, Founder and CEO of LeastAuthority

Overview

Zerocash (ZC) and Confidential Transactions (CT) are both ledger protocols: they can be used to improve the privacy of any given ledger system, whether that’s in Bitcoin sidechains, centralized ledgers, or even Bitcoin itself. Zerocash was introduced as a proposed extension to Bitcoin, or a Bitcoin-like system, and Confidential Transactions was introduced as a potential Bitcoin sidechain feature as part of Blockstream Elements.

At a high level, the goal of Confidential Transactions is to hide the value of transactions, but it does not hide the participants of a transaction. The metadata of who-has-paid-whom is often more sensitive than the balances. It is possible to combine CT with other techniques (such as CoinJoin mixing) to improve participant confidentiality, although care must be taken to ensure the two schemes interact securely, and the degree of privacy depends on how many mixing transactions occur.

By contrast, in Zerocash provides full privacy for both transaction value and participants.

Finally, an important high-level distinction between the two protocols is that Confidential Transactions have flexible security parameters per transaction, whereas Zerocash has uniform security across the whole system. This may lead to important systemic impacts.

Table 1. Comparing Ledger Privacy Protocol Characteristics

Example Protocols What's Confidential
Sender/Receiver Amount
Zerocash
Confidential Transactions  
CoinJoin, Cryptonote, Bitcoin Mixers ✔? [1]  
[1]We list several schemes which strive for sender/receiver confidentiality, but do not make claims about their security.

Comparison

Here we briefly compare the two approaches, showing their relative strengths and weaknesses, first in a summary Table 2, followed by more explanation.

Table 2. Zerocash and Confidential Transactions At A Glance

  Confidential Transactions Zerocash
Confidentiality Only Amounts Participants and Amounts
User Flexibility Fine-Grained All-or-nothing
Transaction Size [2] ~5000 bytes ~1000 bytes
Proof Size [2] ~2500 bytes 288 bytes
Proving Cost [3] ~100's/sec ~one per minute
Verification Cost [3] ~100's/sec ~100's/sec
Pruning Support Inherent Support None Implemented
Cryptographic Basis ECDLP, Random Oracles Knowledge of Exponent, KEA
Peer Review Community Review Published peer-reviewed conference proceedings [4]
Code Auditability Open Source Not Yet Public
Parameter Setup Not Vulnerable Complex, Potential for Compromise [5]
[2](1, 2) For these sizes we consider a “standard” transaction shape with two inputs and two outputs. There are important caveats, see Transaction Size and Proof Size explanations below.
[3](1, 2) These are rough approximations of a single core on a relatively recent machine; the important take-away is the large relative cost of Zerocash proofs. See Proving Cost below.
[4]See Peer Review below for references.
[5]New research substantially improves this security, see Parameter Setup below.

Explanation

Confidentiality. Confidential Transactions hide transaction values whereas Zerocash hides all transaction information (except for timing).

Both Zerocash and Confidential Transactions hide the amount of money transferred in transactions. However, CT does not hide the address of the sender and the receiver. So “Transaction Graph Analysis” techniques like [a], [b], [c], [d], and [e] may still potentially be used to connect and trace them to endpoints like exchanges.

Transaction graph analysis can potentially be thwarted by mixing, for example by using CoinJoin. But mixing comes with a variety of other implementation challenges, security hazards, and costs; in particular, mixing adds to blockchain bloat, and mixing is not implemented in Elements.

User Flexibility. Zerocash is an “all-or-nothing” protocol. There is only one level of security, and that provides confidentiality against unauthorized parties for both amounts and sender/receiver addresses. Users cannot alter this.

(Note: users of Zerocash can make their transaction records transparent to chosen authorized parties. The discussion about security levels here is only about the level of security that the system provides against snooping by unauthorized parties. Zerocash is designed to provide nothing but maximal security against snooping by unauthorized parties.)

By contrast, Confidential Transactions allows per-transaction security tuning, such as by trading off some amount of confidentiality for smaller overhead [6].

This is a fundamental difference that affects usability, systemic behavior, and many implementation issues. A usability difference might be that in a CT system, a recipient may need to distinguish “how much privacy” comes with the sender's amount, whereas in Zerocash there is a known “standard amount of privacy”.

There may be systemic impacts: if many users opt to turn down their privacy settings, then the few users who leave them high may draw unwanted attention.

Finally, there are many implementation details this difference affects. For example, all Zerocash transactions have the same shape (number of inputs and outputs) and size to aide in indistinguishability, whereas each CT transaction may have a different shape. This also may have usability impact because if a user wants to split a value into many new values, for example, their software must use multiple Zerocash transactions, whereas CT software may choose to use either a single transaction or more depending on other privacy or performance goals.

[6]Note: Even when a protocol is flexible, it's possible to enforce a stricter use of a protocol with the ledger consensus rules, so long as that stricter check relies only on ledger-public information.

Transaction Size. Both systems use transactions which contain some metadata along with one or more proofs related to the inputs or outputs.

Zerocash has only one transaction shape with 2 inputs and 2 outputs, which is the minimum for splitting and joining values [7]. Note also that most payments require 2 outputs to account for change back to the sender.

For this standard transaction shape, the on-chain cost (blockchain bloat) of a typical CT transaction is higher than that of Zerocash.

However, for other transactions, especially “sweep” transactions with 1 output and N inputs, a CT transaction is much smaller because range proofs are unneeded.

Additionally, CT supports transactions with any number of inputs or outputs, whereas ZC has a fixed shape.

[7]The Zerocash protocol could be extended to allow more inputs and more outputs. This article only considers the current published protocol.

Proof Size. The size of a full CT proof is, by default, 2.5Kb, compared to 288 bytes for Zerocash. However, when a transaction has only a single output, range proofs can be omitted from a transaction, and the remaining proof structure requires only a single 33 byte Pedersen commitment.

The proof size for CT can also be run in ‘reduced size’ modes, although this comes with a privacy tradeoff since it reveals more information about balances. The Zerocash proof size reflects “full privacy” mode, and there is no way to decrease the level of protection.

Finally, some of the CT proof can be recycled for a dual use, since it can contain an encrypted message from the sender to recipient.

Proving Cost. The time it takes to create a transaction is much larger in Zerocash than in CT, although both take longer than ordinary Bitcoin transactions. We believe both are tolerable. Given these two state-of-the-art approaches, there remains a tradeoff between cost and privacy.

Verification Cost. The transaction verification costs for both ZC and CT transactions are higher than for Bitcoin, but both are likely tolerable. On a desktop benchmark, a single thread can validate 175 ZC pour transactions per second.

Pruning Support. CT provides pruning inherently, whereas ZC does not have pruning currently.

Pruning allows a “full node” (i.e. a node that independently validates every new transaction block) to reduce its storage costs by forgetting about previously-spent transactions. In CT, a transaction output is publicly known to be either spent or unspent, just as in Bitcoin, and therefore Bitcoin-style pruning works “out of the box”.

By contrast Zerocash requires verifiers to remember a unique identifier for every spent value, and in the current design this set grows indefinitely. The paper presents potential optimizations which can mitigate these storage requirements by making various tradeoffs (Sections 8.3.1 and 8.3.2 of the Zerocash paper in Peer Review).

Choices around pruning involve other nuanced trade-offs. For example, systems which allow pruning spent outputs necessarily expose information about the transaction graph and constrain what kinds of sender/receiver graph confidentiality is possible.

Cryptographic Basis. CT and ZC rely on different cryptography. On the one hand, CT relies on a variant of Schnorr signatures, whose security can be based on either the elliptic-curve DL problem (ECDLP) and the Random-Oracle (RO) assumption. On the other hand, ZC relies on zkSNARKs whose security is based on variants of the Knowledge Of Exponent (KoE) assumption for bilinear groups (instantiated via certain pairing-friendly elliptic curves). Both the RO and KoE assumptions have been studied by cryptographers for over two decades, but only the former has seen widespread deployment in practice.

Peer Review. CT is a new application of well-understood cryptographic primitives, and has been reviewed informally by industry experts.

The Zerocash protocol has been published in a peer reviewed academic conference, as well as building on prior published work. Additionally published work on Parameter Setup was presented at a conference this year:

zkSNARKs have been covered by many peer-reviewed publications.

Code Auditability. CT is open source. The ZC code is not yet public, although a fundamental component, libsnark is currently open source.

The community behind these projects highly value open source software. It is crucial that security-related software, especially for critical infrastructure such as global transaction systems, is auditable by the public.

The ZC authors intend to release an open source prototype.

Parameter Setup. CT has very simple one-time initial parameter selection which is amenable to common “nothing up my sleeve” selection techniques. Zerocash has complex one-time initial parameter setup which is vulnerable to compromise.

The Zerocash authors have presented new research on a secure multi-party computation to improve the parameter setup security. This new setup distributed protocol provides the guarantee that if even one party involved in the setup follows the protocol correctly, then the setup is secure. (Conversely all participants must be compromised for parameter compromise.)

Conclusion

Confidential Transactions and Zerocash are two protocols for augmenting ledgers with better privacy. Confidential Transactions only protects transaction values, whereas Zerocash also protects sender/receiver addresses.

In Zerocash, all coins are equal, and values are truly fungible. Users are presented with an all-or-nothing security choice and only a single security level to understand. In Confidential Transactions, users have more flexibility and can tune privacy knobs for their individual needs, and as a result transactions are distinct and have history, and users (or their software) needs to manage fine-grained security levels.

From a system-wide perspective, Zerocash's all-or-nothing security level means all users have strong privacy, even when it's not critical for them. In Confidential Transactions it may be that only users with strong privacy needs have strong privacy, and if this set of users is small enough it may endanger their privacy.

Each has costs and tradeoffs on top of the underlying ledger, related to fundamental security assumptions, maturity of cryptographic techniques, amount of blockchain bloat, proving and verifying costs, and burdens on senders or recipients.

The authors agree that both Zerocash and Confidential Transactions should be pursued – as well as other future innovations! – to have the best chance of providing strong financial privacy and fungibility.

— Alessandro Chiesa (Zerocash), Andrew Miller (LeastAuthority), Christina Garman (Zerocash), Eli Ben-Sasson (Zerocash), Eran Tromer (Zerocash), Greg Maxwell (Blockstream), Ian Miers (Zerocash), Madars Virza (Zerocash), Matthew D. Green (Zerocash), Nathan Wilcox (LeastAuthority), Zooko Wilcox-O'Hearn (LeastAuthority)

Thanks to Gordon Mohr for review and comments.

References

[a]Ron, Dorit, and Adi Shamir. Quantitative analysis of the full bitcoin transaction graph. Financial Cryptography and Data Security. 2013. http://eprint.iacr.org/2012/584
[b]Reid, Fergal, and Martin Harrigan. An analysis of anonymity in the bitcoin system. Security and Privacy in Social Networks. 2013. http://arxiv.org/abs/1107.4524
[c]Spagnuolo, Michele, Federico Maggi, and Stefano Zanero. Bitiodine: Extracting intelligence from the bitcoin network. Financial Cryptography and Data Security. 2014. http://www.ifca.ai/fc14/papers/fc14_submission_11.pdf
[d]Ron, Dorit, and Adi Shamir. How Did Dread Pirate Roberts Acquire and Protect His Bitcoin Wealth?. Financial Cryptography and Data Security. 2014. https://www.ifca.ai/fc14/bitcoin/papers/bitcoin14_submission_2.pdf
[e]Koshy, Philip, Diana Koshy, and Patrick McDaniel. An analysis of anonymity in bitcoin using p2p network traffic. Financial Cryptography and Data Security. 2014. https://fc14.ifca.ai/papers/fc14_submission_71.pdf

A Bug in libsnark

a statement from Least Authority

Zooko Wilcox-O'Hearn writing:

About us

At Least Authority, our mission is to bring verifiable end-to-end security to everyone. As a part of this mission, we have been collaborating with with the scientists behind zk-SNARKS, libsnark, and Zerocash. These are some of the most promising new advances in cryptography, and we are exploring whether they can be used to provide more safety and freedom to all users of the Internet.

We're not ready to post about our specific plans, but we want to address the recent news that a bug has been discovered in libsnark.

A bug in libsnark

Recently there was a bug reported by Bryan Parno from Microsoft Research. Because libsnark is used to implement the cryptography in Zerocash, some people have worried that this bug could have led to a critical failure in Zerocash, if Zerocash had already been deployed before the bug was discovered.

We asked some of the authors of libsnark to comment about the bug.

How we work

Before turning the floor over to the libsnark scientists, I'd like to make two points myself:

First, in the long run, having independent scientists like Bryan Parno study the zk-SNARK literature and the libsnark implementation in search of flaws is the right way for a cryptographic innovation like this to get vetted and improved. It is encouraging to see this kind of scientific scrutiny happening, and we are grateful for the work he and other researchers have done.

Second, before we at Least Authority deploy new software or cryptography for our users to rely on, we perform our own internal security audits and solicit external security audits from independent experts. We have not yet performed that process for libsnark, and we would do so before deploying any libsnark-based systems to our users.

If you're interested in our history, here are the reports from some of the security audits that we've performed on behalf of others, and here is a contest we organized for others to find security flaws in our flagship product.

We also notified the authors of another zk-SNARK implementation named snarklib, so that they could fix the bug as it applies to snarklib.

A statement from the libsnark team

Alessandro Chiesa, Eli Ben-Sasson, Eran Tromer, and Madars Virza writing:

Summary:

  • Bryan Parno identified a bug in the R1CS-to-QAP reduction in libsnark.
  • Current libsnark includes a full and general fix, in commit f55afd03.
  • The fix has negligible performance implications when the number of constraints is much larger than the number of inputs, as is typical in SNARK applications, including Zerocash.
  • Known users of libsnark have been notified, so that they may update their code to the latest release.

More details about the bug and its fix:

One of the preprocessing SNARKs in libsnark represents NP statements to be proved as rank-1 constraint systems (R1CS). Internally, a given R1CS is converted into a Quadratic Arithmetic Program (QAP), an algebraic representation of the NP statement. If the R1CS has an input of size n, the QAP includes polynomials A_0,...,A_n over a finite field F and, for the soundness of the SNARK to hold, these polynomials must be linearly independent over F. The R1CS-to-QAP reduction, which converts an R1CS into a QAP, should ensure this independence. Until recently, libsnark’s implementation of that reduction had a bug: it did not explicitly ensure this independence.

This bug does not always manifest, because a R1CS may naturally induce a QAP in which A_0,...,A_n are linearly independent. However, the linear independence should be assured generically for all possible R1CS. The straightforward fix to do so is as follows.

In the following, consider an R1CS with M constraints, N variables, and n inputs. (The n inputs correspond to variables that are fixed to known values by the NP statement; the remaining N-n variables are part of the witness, and can take on any value.) The fix is to add n+1 dummy constraints that ensure that the constructed QAP always has linearly independent A_0,...,A_n. This causes the degree of the constructed QAP to increase from M to M+n+1. (An optimization, not implemented in our code, is to only add as many additional constraints as needed to ensure that the constructed QAP satisfies the desired property; this number is at least 0 and at most n+1.)

The increase has negligible performance implications when M is much larger than n. Our experiments show that this is the case for all the applications that we considered. For both SNARKs for TinyRAM [BCTV14, USENIX Security] and Scalable Zero-Knowledge [BCTV14, CRYPTO], the increase in the number of constraints is at most 0.007%. For Zerocash [BCGGMTV14, S&P], the increase is smaller: 0.00022%. More generally, we believe that M is much larger than n for most interesting applications, e.g., for constraint systems that verify cryptographic computations.

For more details, see Remark 2.5 in the extended version (revised on 9 May 2015) of Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. (Note that the paper is phrased in terms of arithmetic circuits rather than rank-1 constraint systems, so that the paper’s remark and the explanation above differ slightly.)


Page 1 / 1