Articles in the News category

Least Authority Performs Incentive Analysis For Ethereum

Our mission at LeastAuthority is to bring verifiable end-to-end security to everyone.

As part of that mission, in addition to operating the S4 secure storage service, we also run a security consulting business. We LeastAuthoritarians have extensive experience in security and cryptography, and other companies sometimes hire us to analyze the security of their protocols and software.

Our most recent consulting client is Ethereum.

Ethereum is innovating in many ways, both in the technical design of the cryptocurrency itself, and in their engineering process. As part of the testing phase building up to Ethereum's release, they are performing a large scale security audit, involving contributions from many independent investigators, including Least Authority.

Our contribution is not a “security audit” per se, although we did find and report some implementation-specific bugs.

Instead, we took an in-depth critical look into two fundamental and innovative aspects of Ethereum's design: the new proof-of-work puzzle, Ethash, and the gas mechanism. Both of these features are inherently incentive-oriented. The proof-of-work puzzle is designed to encourage a large number of independent users to participate, yet to discourage "mining centralization" which is currently rampant in Bitcoin. For example, it would be considered a severe failure of the incentive mechanism if, in a year following Ethereum's release, there turns out only to be a single large Ethereum miner, crowding out other potential miners! Similarly, the gas mechanism is about encouraging users to make efficient use of common resources (e.g., storage in the blockchain and compute cycles available to validate transactions). For both of these, we're interested in answering similar questions: are the incentives of users well aligned? Can a greedy attacker profit by deviating from the protocol?

This has been fun for us because we've gotten to study in very close detail several aspects of how Ethereum works, and gotten to see their engineering process in action. We're impressed with many aspects of their engineering process, such as how all the work is done "in the public", so we could follow along as they release in-development code. Also they have several different implementations in different languages, by different teams. Lots of bugs are caught that way.

Today we're releasing our final report, which summarizes our findings and explains the steps Ethereum has taken in response. In general, we found the Ethereum virtual machine and gas mechanism to be well designed, and most of the hazards in contract composition are readily fixed. Based on our cost analysis of hardware configurations, the Ethash puzzle is likely to be GPU-friendly with minimal potential for improvement using customized hardware designs. As supplemental materials we also include tools for visualizing the storage trie structure and demonstrations of attacks using pyethereum as a simulator.


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.)


Reset The Net with the Upgraded Simple Secure Storage Service

“Reset The Net!” is a broad coalition of many businesses, organizations, and individuals. We're empowering people to protect themselves on the Internet by using end-to-end encryption.

Least Authority is a team of computer security professionals dedicated to providing freedom-compatible storage. For us that means end-to-end-encryption and Free and Open Source code. Always.

In support of “Reset The Net!” we have upgraded our Secure Simple Storage Service (S4), reduced the price by 50%, and included unlimited personal data storage in the cloud.

S4 uses the Least Authority File System, a technology designed with user security in mind, and built from the ground up to provide that security as well as we know how.

Such tools allow the user to store data on the Internet without any third party (even us!) breaching the confidentiality or integrity of the data. This keeps the power where it belongs, in the hands of the user.

We are pleased to announce S4 as a command-line utility, and we are presently developing a Dropbox-esque friendly file-syncing utility named “Magic Folders”.

If you're comfortable with the command line, you can take part now with a free 30-day trial and continued service at half the previous price. By using Least Authority's secure cloud storage service, you're becoming a supporter of the further development of the Free and Open Source crypto system, and you're getting a great tool right now for your own use.

This video demonstrates its use:



Does that look like the product for you?



Not familiar with the command line? Don't worry we have a product in the works for you! Give us your email and we'll let you know when Magic Folders is ready!


Least Authority Performs Security Audit of GlobaLeaks

At Least Authority, our mission is to bring verifiable end-to-end security to everyone. As a part of this mission, we provide security consulting services to free and open-source software projects. We also run a verifiably-secure cloud backup system, S4.

In the past, we've performed successful security audits of SpiderOak's Crypton project and of Cryptocat. Continuing this series of security audits, we've completed an audit of the GlobaLeaks whistleblowing framework.

This audit was funded by the Open Technology Fund (OTF). Regular security audits are an important part of the development of any software, and free and open source internet freedom software is certainly no exception. We applaud OTF for funding these highly beneficial audits.

Audit Results

Protecting whistleblowers is no easy task, especially since they may be up against powerful adversaries (governments, corporations, and criminal organisations) and the consequences of getting caught may be grave. It's unlikely that a single technical solution to this problem exists. To keep whistleblowers safe, any technical solution needs to be paired with OPSEC education.

One of the things we liked about the GlobaLeaks project is that it has OPSEC education and checks built right in to the user interface.

We identified several security issues in the GlobaLeaks software. You can read about each issue in the audit report. The issues have been addressed by the GlobaLeaks team in the latest stable version.

Further Reading

The full audit report: Report of Security Audit of GlobaLeaks.

The GlobaLeaks wiki page: LeastAuthority Report.

Tickets in the GlobaLeaks bug tracker for each of the issues we identified.


Page 1 / 2 »