Machinations


Workshop on Modern Massive Data Sets (MMDS)
July 16, 2014, 9:20 pm
Filed under: Uncategorized | Tags: , ,

[The following blog report on MMDS’14 was written by my student Mahdi Zamani - Ed]

Recently, I attended the MMDS workshop hosted by UC Berkeley. The workshop consisted of 40 talks distributed in four days and a poster session. It focused on algorithmic and statistical problems in large scale data analysis and brought together researchers from several areas including computer science, mathematics, statistics, and Big Data practitioners. In the third day of the workshop, I presented a poster about our recent work on multi-party sorting of large data sets. The following is a brief summary of a few talks that seemed interesting to me and my current research projects. The workshop program is available here.

Dan Suciu from University of Washington talked about running queries on very large databases. He argued that traditionally database queries were measured in terms of disk I/O but in Big Data query processing, since the database is store on distributed clusters, communication is the bottleneck. Now, the problem is to run a query on p servers via a Massive Parallel Communication (MPC) model, where the goal is to minimize the load on each server. In this model, the database records are partitioned among p servers each getting M/p, where M is the total number of records. Then, the database operations (like SQL joins) are performed on the partitions. As an example, Dan mentions a popular operation in Big Data analysis called triangle that is defined over three relations: Q(x,y,z)=R(x,y) join S(y,z) join T(z,x). Using a naive approach, this query can be computed in two communication rounds, doing two separate joins. But, surprisingly, it can be computed in a single communication round with reasonable load on each server using a simple technique described by Dan in [3].

Stanley Hall Auditorium

Bill Howe from University of Washington talked about Myria, a web-based framework written in Java for Big Data query processing. He is motivated by the fact that at least we, as scientists, spend more than 90% of our time handling data for our experiments rather than designing new techniques and algorithms  (I think by scientists he means practitioners here. I believe theoreticians spend much less time working with data :). Bill explains that although current Hadoop optimizations are more than 100 times faster than Hadoop itself, we still need faster and simpler frameworks that can be at least used by non-expert scientists. The main idea behind Myria is to blur the distinction between relational algebra and linear algebra. In other words, every query in the relational domain is translated to simple linear algebraic equations that can be computed very fast. Myria provides an imperative-declarative language that runs queries in parallel.

Yiannis Koutis from University of Puerto Rico talked about spectral algorithms for mining data from large graphs. Spectral analysis is an important tool for graph partitioning, where the set of vertices of a large graph is divided into smaller components such that the number of edges running between separated components is small. This is often an important subproblem for complexity reduction or parallelization. A cut that provides the smallest number of such edges is called the sparsest cut. Such a cut bisects the graph into the most important components. Given an adjacency matrix A of a graph G, the general idea behind spectral graph partitioning is that the eigenvector associated with the second smallest eigenvalue of the Laplacian matrix L of A is the sparsest cut of G (given a matrix A and the degree matrix of A denoted by D, the Laplacian matrix of can be computed as L=D-A). Since finding the exact eigenvalues of the Laplacian matrix is often computationally intensive, Yiannis argues that one can find a good (small) sparse cut by approximating the eigenvalues. However, it is an open problem whether one can find better cuts using another technique with similar computational costs. At the end of the talk, I asked Yiannis whether probabilistic methods (such as random walks) are slower than spectral methods. He answered that probabilistic methods are usually local, and global random walks are often much slower than global spectral analysis.

David Woodruff from IBM Almaden Research talked about an optimal CUR matrix decomposition technique. Given a matrix A, the goal is to find three matrices C, U, and R such that A=C.U.R. A solution to this problem can be used in many applications such as recommendation systems. For example, Netflix is interested in fast techniques for decomposing its huge users-by-movies matrix into a matrix of the most important users and a matrix of the most important movies. Since the exact decomposition is often very computationally expensive, an approximation is calculated instead. Although there are fast randomized algorithms for solving this problem (e.g., [2]), David proposes their asymptotically-optimal deterministic algorithm published recently in STOC 2014 [1].

Xavier Amatriain from Netflix talked about current Big Data challenges of his company. Until 2007, the company had over 100 million movie ratings and now it holds about 5 billion ratings. The company currently has 44 million users around the world and holds more than 5 billion hours of movies. The users play about 50 million movies and submit 5 million ratings per day. This contributes to about 32% of US daily downstream traffic. From this huge pile of data, Netflix needs to extract ranking and similarity information about the movies. Their main approach to this end is to employ distributed machine learning algorithms. Xavier argues that in today’s world more data sometimes beats better algorithms. He backs up his claim by a quote from Peter Norving, Director of Research at Google: “Google does not have better algorithms, only more data” (see this). Xavier continues by arguing that training algorithms can run in parallel because training data are often independent of each other. He also describe how they have scaled their algorithms by distributing at three different levels: across regions or subsets of the population, at the hyperparameter optimization stage, and at the model training level.

[A polished version of this report is available here - Ed]

References

[1] Christos Boutsidis, David P. Woodruff: “Optimal CUR Matrix Decompositions”, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 353—362, 2014. URL: http://doi.acm.org/10.1145/2591796.2591819.

[2] Michael Mahoney, Petros Drineas: “CUR Matrix Decompositions for Improved Data Analysis”, Proceedings of the National Academy of Sciences, pp. 697—702, 2009.



Game Theory and Evolution
June 24, 2014, 8:14 pm
Filed under: Uncategorized | Tags: , , ,

The Game Theory of Life is a nice writeup of a recent PNAS paper Algorithms, Games and Evolution by Chastaina, Livnatb, Papadimitriou and Vazirani.  As a CS researcher with an amateur’s interest in biology, I really enjoyed this paper.

The paper shows a certain equivalence between two algorithms.  The first algorithm, I’ll call “evolution”.   This is an approximation (using replicator dynamics) to what happens in real Evolution in nature.  The second algorithm is the multiplicative weight update algorithm (MWUA) which we all know and love in CS.  MWUA is also known as weighted majority or winnow to many people in CS theory.

The paper proves that the outputs of “evolution” are equivalent to MWUA. They then show this implies that “evolution” is equivalent to a process that tries to maximize utility *plus* entropy (equation 3 in the paper). The utility part is not surprising since we’d certainly expect Evolution to be concerned with it.  The “plus entropy” part is surprising, and perhaps explains the surprising diversity of life.  Essentially sexual replication in the “evolution” algorithm is what gives rise to this additional entropy part.

I think it’s a pretty interesting paper. Intuitively, it proves that a simple kind of genetic algorithm (i.e. “evolution”) will give equivalent results to the MWUA (i.e. see the equivalence of Figures 1 d) and 2 d) in the paper). A nice result from the CS perspective.  However, there are a few “rah rah computer science” comments in the paper that may turn off some biologists.

I think the key thing that would really impress biologists would be making the “evolution” algorithm more realistic.  To do this would require improving Nagylaki’s theorem which is used in the paper for analyzing the “evolution” algorithm. The authors claim Nagylaki’s theorem can already be used to handle diploidy and partial recombination. Mutation is an area mentioned for future work. Modeling the interaction of organisms seems much harder. It’ll be interesting to see the followup work on this paper.

 



Secure Multiparty Computation Workshop
June 22, 2014, 10:48 pm
Filed under: Uncategorized | Tags: , ,

Last month I went to a  workshop on secure multiparty computation that was organized by IARPA.  I’ve had mixed luck with these types of workshops that are organized by funding agencies.  However, this one was pretty good, because of the timeliness of the topic, well-prepared talks, and the fact that the participants were some of the big names in security and MPC.

This was also one first times I’ve visited and given a talk at MIT, which was a lot of fun.  Many of the talk slides are included in the workshop link above.

 



Latest SIGACT Distributed Computing Column
May 29, 2014, 3:04 pm
Filed under: Uncategorized | Tags: ,

The June 2014 edition of the Distributed Computing Column in SIGACT News is devoted to a review article on Transactional Memory by Gokarna Sharma and Costas Busch. An archive of the column is available online at:

https://parasol.tamu.edu/~welch/sigactNews/

Also, if you, like me, are having difficulty obtaining the full version of the March 2014 column, which reviewed a Dagstuhl seminar on Consistency in Distributed Systems by Bettina Kemme, G. Ramalingam, Andre Schiper, and Marc Shapiro, you can get it at the archive.

Enjoy!

– Jennifer Welch



Leslie Lamport Wins Turing Award
March 28, 2014, 10:40 pm
Filed under: Uncategorized | Tags: , ,

Long overdue (both the award and my reporting of it here)



Workshop on Applied Multi-Party Computation

Following is a very nice report of a Workshop on Applied Multiparty Computation at which my students Mahnush Movahedi and Mahdi Zamani gave talks.  Enjoy.    –   Jared

Workshop on Applied Multi-Party Computation: A Summary

Mahnush Movahedi and Mahdi Zamani

Recently, we attended a great workshop on applied Multiparty Computation (MPC) hosted by Microsoft Research Redmond and organized by Seny Kamara and Payman Mohassel. The workshop consisted of 21 talks distributed in two days and mostly focused on practical applications of MPC. Although most talks were very interesting and valuable, we decided to summarize only those that were more related to our current research. For a great summary of the entire workshop, see the related posts in MPC Lounge blog by a team from Aarhus Crypto Group.

Secure Computation in 2029: Boom, Bust, or Bonanza (keynote speech), David Evans, University of Virginia

David gave a great talk about the past and future of MPC. He started with a few interesting predictions about where MPC will be in the year 2029 (15 years from now). He explained that the reason for choosing 2029 is inspired by an essay by Neil DeGrasse Tyson and some experiments indicating that scientific developments double every 15 years (see this for example). Using Google Scholar, David showed that until 1999, the number of papers published about MPC was about 160 while this number increases to about 700 until 2013. He justified the doubling time of 15 years again by referring to an interesting paper by Shafi Goldwasser in PODC 1997, where she correctly predicted a similar growth for MPC.

figure david-evans.jpg

Figure 1. David Evans

In order to predict the development of MPC in 2029, David estimated the U.S. government investment on MPC in the past 1-2 years to be about $100 million, which is roughly about the annual investment spent by the government on art fields [A] . He then made three exciting predictions about MPC in 2029.

  • Claim 1. The MPC industry should be bigger than anti-malware industry in 2029. David justified this by extrapolating investments on IT security and predicting that it will probably decrease by 2029 due to progress in developing secure software.
  • Claim 2. High cost will no longer be the main impediment to the widespread use of MPC (at least for two-party computation). He explained this by estimating the cost of securely comparing two genomes (e.g. in genetic matchmaking) using MPC in 2004 (which is about $100 million) and estimating its cost in 2029 (which is about $0.001). For security against a malicious adversary, this cost in 2004 is estimated to be about $80 billion while in 2029 it is predicted to be about $0.005 per secure comparison.

figure secure-sequencing-passive.png
Figure 2. Estimated cost of building MPC for genome
comparison in the semi-honest model (courtesy of David Evans).
  • Claim 3. We don’t yet know what the “killer app” for MPC is and it’s probably not privacy. David argues that the amount of money people pay for privacy is usually very small. So, he predicts that the killer app for MPC will not just use MPC for privacy, and there are aspects of MPC that will probably be very useful in some applications. There was a panel on the business case for MPC after David’s talk, where people discussed more about the killer app for MPC. The panel’s video is available here.
David finally stated three things that really matter for the future of MPC.
  • What if the outputs leak? In MPC, the output of computation is revealed to everyone. This output may leak some information to the adversary. Is there a way to measure or limit this leakage?
  • How to ensure users accept and trust the MPC-based application?
  • How to implement MPC with low (human) cost?
David finished his presentation by talking about his recent book Dori-Mic and the Universal Machine!, which is for any “toddler who is falling behind in theoretical computer science” and in general for curious children of all age! Watch David’s presentation here.

Broadcast (and Round) Efficient Secure Multiparty Computation, Juan Garay, Yahoo! Labs

Juan started with a history of MPC for arithmetic circuits using the share-compute-reveal paradigm, where a certain fraction of parties are malicious. In this paradigm, inputs are first secret-shared among all parties using a Verifiable Secret Sharing (VSS) scheme. In order to get the sum of all inputs, each party simply adds its shares locally to find a share of the sum. On the other hand, the product of input shares is not necessarily a valid share of the product of the inputs. Beaver [2] solves this by precomputing a multiplication triple in an offline phase and using it to compute a share of the product in the online phase.

figure juan-garay.png

Figure 3. Juan Garay

In order to perform VSS in a point-to-point network, parties should have access to a broadcast channel, which ensures that all parties receive the same message broadcast by the sender. Juan argues that due to the lack of an efficient broadcast channel, VSS schemes should be measured in terms of broadcast complexity, and the goal should be to minimize the number of broadcasts in VSS. Juan defined a relaxed type of secret sharing called Weak Secret Sharing (WSS), where the recipients reconstruct either the value jointly held by them or a special symbol ⊥ indicating that the dealer is malicious. He then defines VSS by extending the definition of WSS such that the recipients always reconstruct the joint value even if there is cheating in the reconstruction phase.

Juan presented a linear VSS protocol for an unbounded static adversary (t<n/2 ). The protocol uses only two broadcasts in the sharing phase and none in the reconstruction—what he calls a (2,0)-broadcast VSS. This is achieved by increasing the number of rounds in the sharing phase, which makes their protocol (20,1)-round. He compares this to the state-of-the-art VSS protocol of Kumaresan et al. [10] that is a (2,2)-broadcast and (3,2)-round VSS. They first construct a (2,1)-broadcast WSS protocol and then use its sharing phase to build a (3,0)-broadcast, (9,1)-round VSS based on the construction of Rabin and Ben-Or [13]. The number of broadcasts is reduced further to build a (2,0)-broadcast VSS using the moderated VSS of Katz and Koo [8], where the dealer acts as the moderator to simulate broadcast. Such a broadcast is called a modercast. At the end of his talk, Juan explained that their VSS scheme can be used for constructing efficient pseudosignatures, an information-theoretic analogue of digital signatures introduced by [4]. Such signatures can be created in a setup phase to be used for simulating future invocations of broadcast or constructing efficient anonymous channels. Watch Juan’s presentation video here.

 Asynchronous MPC with t<n/2 Using Non-Equivocation, Aniket Kate, MMCI, Saarland University

Aniket presented work on Asynchronous MPC (AMPC), where it is assumed that all messages sent by the parties are eventually delivered but with indefinite delays. In the synchronous setting, MPC has been solved with t<n/2 malicious parties (with cryptographic assumptions) but in the asynchronous setting, the best known algorithm tolerates t<n/3 malicious corruptions. These resiliency bounds are primarily due to the limitations of implementing a reliable broadcast channel that is necessary for constructing an Asynchronous Verifiable Secret Sharing (AVSS) protocol.

In order to verify correctness of a sharing, parties need to prevent the adversary from equivocation, which means making conflicting statements to different parties. A mechanism that makes equivocation impossible is called non-equivocation, which can also be transferable to allow a receiver to verifiably transfer the authenticated statement to other parties. Non-equivocation can be implemented using an increment-only counter and a digital signature oracle, which can be constructed using trusted hardware modules readily available in commodity computers and smartphone devices [12].

Their AMPC improves the resiliency bound from t<n/3 to t<n/2 and improves the communication complexity from O(n4κ) to O(n3κ) when compared to the state-of-the-art AMPC of Beerliova et al. [3], where κ is the security parameter. The protocol assumes the existence of a transferable non-equivocation mechanism, which the authors believe is more practical than a synchronous broadcast round assumed by [3]. Watch Aniket’s presentation video here.

Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation, Mahnush Movahedi, University of New Mexico

Mahnush motivated her talk by the fact that guaranteeing synchrony in most real applications is difficult and even impractical. Thus, in order to use MPC in such applications, certain techniques are required to deal with asynchrony in a malicious setting. One can design a scalable MPC protocol in this setting by delegating computation of each gate to a logarithmic set of parties called a quorum, in which at most a certain fraction of parties are malicious. The quorum then computes the gate using any MPC protocol. Mahnush explained that distribution of communications and computations among several quorums requires incorporating extra coordination efforts between parties, which they handle using a number of efficient tools and techniques.

figure mahnush-movahedi.jpg

Figure 4. Mahnush Movahedi

In a setup phase, a set of n quorums are created using the quorum building algorithm of King et al. [9] optimized with the Byzantine agreement scheme of Braud-Santoni et al. [6], which costs soft-O(1) bits per party. Mahnush argued that the parties in each quorum require a mechanism to coordinate with other quorums on when to start computation on asynchronous inputs. In other words, they need to wait for sufficient number of inputs to be received until they start the computation.

To this end, they propose to count the number of ready inputs using a distributed data structure called a τ -counter, where τ=n−t is the threshold on the number inputs to be received before the circuit is evaluated, and t<n/8 is the number of malicious parties. Using a τ -counter, MPC can be solved without assuming any synchrony points in the algorithm.

In order to send the output of each quorum to the next quorum, parties in the first quorum generate a joint random number and simply mask the output by adding it to the random number. This ensure that no coalition of malicious parties can get together to learn the intermediate outputs. Parties of the next quorum then participate in an MPC to unmask the inputs and evaluate the associated gate over the inputs. The protocol requires each party to send soft-O(m/n) bits and compute soft-O(m/n) operations, where m is the size of the circuit. Watch Mahnush’s presentation video here.

Secure Collaborative Statistics in Credit Rating Using Linear Programming, Tomas Toft, Aarhus University

At the start of his talk, Tomas described how MPC can be used to implement a secure collaborative credit rating for Danish dairy farmers who are willing to get loans. Credit rating is one of the interesting classical problems that is solved using MPC. Tomas described how this problem can be modeled by linear programming. A linear program consists of n variables and m constraints and the goal is to maximize an objective function. A solution for a linear program is an assignment to the variables such that the constraints hold.

One well-known strategy for solving linear programs is the simplex method. Tomas argued that despite an exponential worst-case complexity, simplex is efficient in practice and can be easily implemented since it only requires integer arithmetic operations and comparisons. Their protocol solves the linear programming problem using black-box access to secure modulo arithmetic of Damgard et al. [7] along with additional sub-protocol for comparison (see Lipmaa and Toft [11]).

To solve a linear program for n=285 variables and m=4 constraints, the presented protocol requires 2mn+6m2+n≃2700 multiplications and n+3m≃300comparisons. A Java implementation of their protocol that uses Amazon’s cloud services shows that the running time for this computation is around 5 minutes. The implementation is being demoed for actual banks using real data which allows bankers to jointly rank the farmers based on their credit scores. For more information about Tomas motivation for this problem see another blog post about his talk here.

Securely Solving Standard Network Flow Problems with Secure Multi-Party Computation, Abdelrahaman Aly, C.O.R.E., Univesité catholique de Louvain

Abdel introduced a new class of problems in which a graph is shared between parties as their inputs. The parties want to evaluate a function such as max-flow or shortest path over this shared graph. In most combinatorial problems such as various graph problems, the execution path depends on the input data. Thus, even if all input data are appropriately shared or encrypted among the parties, the execution path itself may reveal some information to the adversary.

As an example for a branching that depends on a secret input, Abdel mentioned a counter loop, where the stopping condition is dependent on the input. In this example, the adversary can exploit branching patterns and running time of the algorithm in order to obtain some information about the secrets if this loop is implemented in a non-secure traditional way. Thus, it is necessary to translate the traditional (non-secure) algorithms on graphs to secure versions. Unfortunately, this translation process increases the computation cost of the algorithm. This overhead depends on the type of the algorithm and graph. For example, the asymptotic complexity of the traditional Edmonds-Karp algorithm to find max-flow is O(|V|^2|E|) and its optimized version is O(|E|^2|V|) , while the complexity of its secure version is O(|V|^5) , where |V| and |E| are the number of vertices and edges in the graph respectively. Unfortunately, the actual costs of their protocol is still very high for practical purposes.

MPC in Large Networks with an Application to Anonymous Broadcast, Mahdi Zamani, University of New Mexico

Mahdi argued that MPC with many players is becoming of increasingly importance, with the growth of modern networks. He suggested that it is possible to perform secure computations efficiently over such large networks. One motivation is that MPC can be used to protect freedom of speech in large social networks like Twitter by providing anonymous communication. In addition, MPC in large networks could be used for analysis of massive data. He proposed an MPC protocol that is secure against a malicious adversary corrupting up to a 1/10 fraction of the parties. Their protocol sends in average O(mlog^3 n) bits and computes O(mlog^4 n) operations in O(d) rounds, where m is the size of the circuit with depth d .

figure mahdi-results.png

Figure 5. Mahdi’s microbenchmark results

Mahdi proposed a method to reduce the communication cost of their protocol by performing local communications in logarithmic-size groups of parties called quorums, where the number of adversary-controlled parties in each quorum is at most a certain fraction. The quorums are created in an offline phase using the Byzantine agreement protocol of Santoni et al. [6]. The offline phase also uses the fully homomorphic encryption protocols of Brakerski et al. [5] to evaluate a small-depth circuit. This is done to generated a sufficient number of Beaver [2] multiplication triples.

In the online phase, each input is secret shared in a quorum using Shamir’s secret sharing scheme. Each gate of the circuit is computed by a quorum over shares, where multiplication is performed using Beaver’s triples. Parties in the quorum send the result of this computation to all quorums associated with gates that need this result as input. It is necessary to securely send the output from one quorum to another without revealing any information to any individual party or to any coalition of adversarial parties. Mahdi solves this by creating fresh shares of the output for the target quorum, where the new shares are values of a new random polynomial that still evaluates to the (secret) output at 0.

Mahdi argued that the anonymous broadcast problem can be reduced to the problem of Multi-Party Sorting (MPS), where parties want to jointly sort their inputs. In order to perform MPS, they compute the sorting network of Batcher [1]. At the end of his talk, Mahdi showed some microbenchmark results for several runs of MPS using their MPC protocol. As an example, for a network with about 30 million parties, each with a 20 -byte input, their protocol requires each party to send 5 kilobytes on average per item sorted.  See figure 5.

MEVAL: A Practically Efficient System for Secure Multi-party Statistical Analysis, Koki Hamada, NTT Secure Platform Laboratories

Koki described an implementation of an MPC protocol called MEVAL (Multi-party EVALuator), which is optimized for statistical analyses. His talk described the techniques they have used to make their protocol efficient and the experiments conducted for evaluating the system. The computation in MEVAL is performed over values shared using Shamir’s secret-sharing scheme among three parties, where at most one of them is controlled by a passive adversary. MEVAL can also be used in a server-based setting, where all clients share their inputs between three servers. One application of such a setting is secure outsourcing of data storage.

Koki mentioned that the protocol has been carefully implemented in order to achieve high efficiency. Some of the techniques used for this purpose are asynchronous processing, pseudorandom secret sharing, and optimized field operations. Koki argued that the main idea behind asynchronous implementation is to enable better resource usage by using both computation and communication resources at the same time in parallel instead of using them sequentially. This helps MEVAL to decrease its running time significantly. MEVAL achieves 8.7 million multiplications per second, and it can sort one million values in less than 7 seconds.

figure wampc-caspian.jpg

Figure 6. A great dinner with (from right to left)
Saeed SadeghianArash AfsharYan Huang,
Elaine Shi, and David Evans.

References

[1] K. E. Batcher: “Sorting networks and their applications”, Proceedings of the April 30—May 2, 1968, spring joint computer conference, pp. 307—314, 1968.

[2] Donald Beaver: Efficient Multiparty Protocols Using Circuit Randomization inAdvances in Cryptology — CRYPTO ’91 (Feigenbaum, Joan, ed.). Springer Berlin Heidelberg, 1991.

[3] Zuzana Beerliová-Trubı́niová, Martin Hirt, Jesper Buus Nielsen: “On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols”, Proceedings of the 29th Symposium on Principles of Distributed Computing, pp. 211—218, 2010.

[4] Birgit Pfitzmann, Michael Waidner: Information-theoretic Pseudosignatures and Byzantine Agreement for t≥n/3 . 1996. Technical Report RZ 2882 (#90830), IBM Research.

[5] Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: “Fully Homomorphic Encryption Without Bootstrapping”, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309—325, 2012.

[6] Nicolas Braud-Santoni, Rachid Guerraoui, Florian Huc: “Fast Byzantine Agreement”, Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 57—64, 2013.

[7] Ivan Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias: “Multiparty Computation from Somewhat Homomorphic Encryption”, Advances in Cryptology — CRYPTO 2012, pp. 643—662, 2012.

[8] Jonathan Katz, Chiu-Yuen Koo: On Expected Constant-Round Protocols for Byzantine Agreement in Advances in Cryptology – CRYPTO 2006 (Dwork, Cynthia, ed.). Springer Berlin Heidelberg, 2006.

[9] V. King, S. Lonergan, J. Saia, A. Trehan: “Load balanced Scalable Byzantine Agreement through Quorum Building, with Full Information”,International Conference on Distributed Computing and Networking (ICDCN), 2011.

[10] Ranjit Kumaresan, Arpita Patra, C.Pandu Rangan: The Round Complexity of Verifiable Secret Sharing: The Statistical Case in Advances in Cryptology – ASIACRYPT 2010 (Abe, Masayuki, ed.). Springer Berlin Heidelberg, 2010.

[11] Helger Lipmaa, Tomas Toft: Secure Equality and Greater-Than Tests with Sublinear Online Complexity in Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. URL http://dx.doi.org/10.1007/978-3-642-39212-2_56.

[12] Michael Backes, Fabian Bendun, Ashish Choudhury, Aniket Kate: Asynchronous MPC with t<n/2 Using Non-equivocation. Cryptology ePrint Archive, Report 2013/745, 2013.

[13] Tal Rabin, Michael Ben-Or: “Verifiable secret sharing and multiparty protocols with honest majority”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 73—85, 1989.


Copyright (C) 2014 Mahnush Movahedi and Mahdi Zamani
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear the full citation. Abstracting with credit is permitted. This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.


Bitcoin and Byzantine Agreement
February 12, 2014, 8:59 pm
Filed under: Uncategorized | Tags: , ,

Last month, Marc Andreessen wrote a thought-provoking article on bitcoin for the New York Times.  Interestingly, early in the article he mentions Byzantine agreement (albeit by the more colorful name of the Byzantine Generals Problem):

“Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem. To quote from the original paper defining the B.G.P.: “[Imagine] a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.

Many other articles give details of the theoretical aspects of bitcoin (the second with quotes from distributed computing luminaries like Jim Aspnes and Nancy Lynch). [1]

When Marc Andreessen mentions Byzantine agreement in the New York Times, it gets my attention.  I’m far from an expert on bitcoin, but from what I can tell, the system is faced with a Byzantine agreement (BA) problem when maintaining logs of currency transactions.  This BA problem occurs over a huge network, so a solution that uses all-to-all communication is infeasible.  To circumvent this, bitcoin uses an algorithm that trades off computation for communication.

In particular, bitcoin’s algorithm for BA uses proof-of-work. Instead of each node sending out a vote, only those nodes that are able to solve a computational puzzle send out their votes.  If the puzzle is hard enough,  only a small number of nodes send out votes and communication is low.  Of course, each vote contains a small proof that the node solved an instance of the puzzle.  This approach works provided that the computational effort exerted by the “good” nodes is twice the computational effort exerted by the bad nodes.

However, there are two issues with using proof-of-work. One is ensuring there is an incentive for the good nodes to work to solve a large fraction of the puzzles.  Bitcoin uses a clever approach: reward users that solve puzzles with their own bitcoins. However, this is very application-specific, and it’s unclear if bitcoin’s BA algorithm would work for other systems where there is no obvious way to incentivize computational work.

Second,  proof-of-work wastes computational resources. Arguably, many  BA algorithms waste communication resources, so maybe this is a fair tradeoff.  However, one has to wonder if there is a more efficient way to tolerate bad nodes.  In particular, it’d be nice to have a scheme where the computation done by the good nodes is some function of the computation done by the bad nodes.  One could hopefully show this via something like resource competitive analysis. Resolving whether or not this is possible is I think one of the more interesting research problems related to bitcoin’s approach to Byzantine agreement.

[1] See also this rebuttal to Andresseen’s article




Follow

Get every new post delivered to your Inbox.