Nick Szabo -- Quorum Systems

Quorum Systems

Introduction

N parties, comprising the set U ("universe"), want to engage in a protocol. These parties can form coalitions to gang up on each other. The set of possible coalitions is just the set of all subsets of U, C = 2^U.

The protocol designer should first specify what coalitions are to be allowed and forbidden. If the parties have rational self-interest, only coalitions whose members have an incentive to not collude, to either compute an incorrect result, or to violate the privacy of any player, should be allowed the potential to disrupt the protocol. Invoking "incentive" implies an economic or game-theoretic analysis of coalitions, which will be considered in a future article.

For now, we just observe that the protocol designer needs to draw from C a set of allowed ("good") coalitions GC. Any set of parties in GC is a coalition sufficient to successfully complete the protocol. Also draw from C set disjoint from GC of disallowed ("bad") coalitions BC which cannot be allowed the opportunity to disrupt the protocol. If GC union BC = C then we say that the partition is unambiguous. Also, the sets in GC are the complements of the sets in BC, and vice versa.

To produce a secure protocol, these coalitions need to meet certain criteria. Particularly interesting is the quorum system, a set of good coalitions, every member of which intersects in at least one party. Each quorum can act on behalf of the system to complete the protocol. Intersection facilitates consistency across quorums. For example, if an operation occurs in two quorums, then at least one party observes both. Indeed, a fault-tolerant or secure quorum system intersects in a set containing sufficiently many parties to guarantee correctness. See, for example, the masking and dissemination quorum systems used by Malkhi & Reiter [MR97] to design a replicated database secure against Byzantine faults by bad coalitions.

[BW98], following the trail blazed by among others [HM97] and [NW96], have shown that if any single party can be trusted with correctness, then a quorum system is necessary and sufficient for the privacy of inputs to a multiparty computation[S97] against resource unbounded adversaries. Classical analysis of multiparty computation concluded that a threshold of more than half of the parties is necessary and sufficient for private computation. This is just a special case of BW98 result. Any threshold system whose threshold exceeds N/2 is also a quorum system -- there are only N parties, so two coalitions of size >N/2 must contain at least one party in common, thus forming a quorum system.

The classical analysis also concluded that a majority threshold is necessary and sufficient for _correct_ multiparty computation, i.e. secure against active Byzantine faults in minorities with polynomial amounts of resources. A two-thirds majority is necessary against resource unbounded adversaries. I am aware of no correctness result as yet for quorum systems in multiparty computation.

Constraint Families

Masking

First let's consider quorum systems which intersect, not just in a single party, making them intolerant to any faults in these parties, but rather in enough parties to complete the protocol in a way tolerant of up to f faults, f>0. One way to do this is called masking which constrains quorum systems to satisfy the following:

M1: None of the sets of correct servers which contain the latest value is a bad coalition. To achieve this, any quorum intersection minus any bad colation should not be a subset of any other bad coalition. Formally: for all Q1,Q2 element of GC and all B1,B2 element of BC, (Q1 intersect Q2) - B1 is not a subset of B2.

M2: No bad coalition can disable all quorums. Formally: for all B element of BC there exists some Q element of GC such that B and Q are disjoint.

These constrains are suficient to ensure that a replicated database is updated consitently and correctly, iff |U|>4f.

Dissemination

To get a dissemination quorum system we relax the first constrain. Now we just want every intersection to not be contained in any bad coalition:

D1: Any quorum intersection is not a subset of any bad coalition. Formally: for all Q1,Q2 element of GC and all B element of BC, (Q1 intersect Q2) is not a subset of B.

D2: No bad coalition can disable all quorums. Formally: for all B element of BC there exists some Q element of GC such that B and Q are disjoint.

These constrains are sufficient to ensure that a replicated database is updated consistently, iff |U|>3f. Correctness of the data must be ensured by some other means, e.g. external signing and verification of digital signatures.

Particular Classes

Threshold

If BC = {B subset of U:|B|=f,n>4f}, then QC = {Q subset of U:|Q| = ceiling((n+2f+1)/2)} is the threshold masking quorum system for BC. If n>3f, then a the threshold dissemination quorum system for BC is given by |Q|=ceiling((n+f+1)/2).

Grid

Suppose |U|=k². The parties can be arranged into a k*k grid. Then a grid masking quorum system for BC = {B subset of U: |B| = f, 3f+1 < k}. is given by QC= {Cj union (union of all Ri: Ii,{j} subset of {1,...,k}, |I|=2f+1)} A grid dissemination quorum system is the same as in the masking case, except |I|=f+1.

Partition

Here we partition U into m clusters, and express the assumption that at any time, at most one cluster is faulty. Thus BC= {B1, ...,Bm} is a partition of U. Then the partition masking quorum system is given by m>4, QC= {union Bi: I subset of {1,...,m},|I|= ceiling((m+3)/2)} and the dissemination quorum system is given by m>3, QC= {union Bi: I subset of {1,...,m},|I|= ceiling((m+3)/2)}

Crumbling Wall

This falls short of dissemination or masking but is also more efficient. The parties are arranged in rows of various widths. A quorum is the union of one full row and one party from every row below the full row. Many of the quorums in a crumbling wall are small minorities; often of O(log|U|).

Conclusion

The study of coalitions, and in particular quorum systems, provides a seemingly comprehensive theory of multiparty protocols which goes well beyond the confining linear world of thresholds.

Ref:

BW98  D. Beaver and A. Wool, "Quorum-based Secure
Multi-Party Computation", Eurocrypt '98, also at 
http://www.transarc.com/~beaver/research/publications/biblio.html#mpp

HM97  M. Hirt and U. Maurer, "Complete characterization
of adversaries tolerable in secure multi-party computation",
16th ACM PODC

M91  R. Myerson, _Game Theory: Analysis of Conflict_

MR97   D. Maklhi & M. Reiter, "Byzantine Quorum Systems",
21st ACM STOC, also at http://www.research.att.com/~dalia/
For an important application of Byzantine tolerant replication, see
http://szabo.best.vwh.net/securetitle.html

NW96  M. Naor and A. Wool, "Access control and signatures
via quorum secret sharing", 3rd ACM Conf. on Computer and
Communications Security

S96  On secure credit reporting, virus list distribution, etc.: 
http://szabo.best.vwh.net/negative_rep.html

S97  A gentle introduction to multiparty computation
and its potential applications: http://szabo.best.vwh.net/msc.html

S98 Secure property titles: http://szabo.best.vwh.net/securetitle.html