Breaking-the-O(n2)-Bit-Barrier-Scalable-Byzantine-Agreement-突破O(N2)位垒的可扩展的拜占庭协议课件

1、Breaking the O(n2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary Valerie King Jared SaiaUniv. of VictoriaUniv. of New Mexico Canada USABreaking the O(n2) Bit BarrierByzantine Agreement Each proc. starts with a bit; Goal: All procs. decide the same bit, which must match at leas

2、t one of their initial bits.t= # of bad procs. controlled by malicious AdversaryByzantine Agreement Byzantine agreement for large scale networksIf you could do it practically, you would!Why?Protecting against malicious attacks Organizing large communities of usersMediation in game theoryFundamental

3、building blockByzantine agreement for large Our ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMess

4、age passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronous w/ rushing adv

5、.Private random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t

6、n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.

7、Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if

8、it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversaryResilience: t n(1/3-)Limit on # bits sent by good procs.:Bad procs can send any #.Our ModelProcs=1,2,nOur ModelProcs=1,2,nMessage passing: A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdap

9、tive adversaryResilience: t 0(Implication of Dolev Reischuk)ImpossibilityAny BA (randomizeOur resultsTheorem 1: (BA) For any consts. c, , there is a const. d and a (1/3- )n resilient protocol which solves BA with prob. 1-1/nc using(n1/2) bits per processor in O(logd n) roundsOur resultsTheorem 1: (B

10、A) ForAlsoTheorem 2: (a.e.BA) For any consts. c, , there is a const. d and a (1/3- )-resilient protocol which brings 1-O(1/log n) fraction of good procs to agreemt with prob. 1-1/nc using (1) bits per proc. in O(logd n) rounds AlsoTheorem 2: (a.e.BA) For anPrevious workAn expected constant number of

11、 rounds suffice. (Feldman and Micali 1988) All previously known protocols use all-to-all communication Previous workKEY IDEA: The power of a short somewhat random stream SS= s1 s2 sk be short stream of numbers. Some a.e. global random numbers, some numbers fixed by an adversary which can see the pre

12、ceding stream when choosing. - S can be generated w.h.p.KEY IDEA: The power of a shorTalk outlineI: Using S to get a.e. BAII Using S to go from a.e. BA to BAIII Generating STalk outlineI: Using S to get Rabins BA with Global Coin GCtn/3 Set vote all procs.Maj - majority bit from othersFract 2/3 agre

13、e on bit then vote -Maj Else if GC =1 set vote - 1; else set vote - 0 Rabins BA with Global Coin GScalable a.e.BA with a.e.Global Coin GCt 2/3+ /2-Scalable a.e.BA with a.e.Globausing S instead of GC-a.e.BA whpFor i=1,k, generate bit si and run a.e. BA using si for a.e.global coinIt suffices that clo

14、g n bits of S are known a.e. and random using S instead of GC-a.e.BII: Using S to go from a.e. BA to BAIdea: Query random set of procs to ask bit. Since almost all good procs agree, majority should give correct answer.Works if bad procs have communication bound But in our model, the adversary can fl

15、ood all procs with queries!Use s to decide which queries to answer.II: Using S to go from a.e. BAII: Using S to go from a.e. BA to BALabels= 1,.,n1/2 FOR each number s of S=Labelsk :Each proc. p picks (n1/2) random queries and sends label to proc. q answers only if label= s (and not overloaded)if 2/

16、3 majority of ps queries with the same label are returned and agree on v, then p decides v.IT SUFFICES TO HAVE AN a.e. AGREED upon S with a RANDOM subsequence!II: Using S to go from a.e. BIII Generating SIII Generating SSparse network Tree of robust supernodes of increasing size with links: procs in

17、 child - procs in parent node procs in parent node-leaves of subtrees All procs.Supernodes and links generated usingaveraging samplers Sparse network Tree of robust Arrays of rand. #sEach proc pi generates array Ai of rand #s and secret shares it with its leaf node.#s in arrays are revealed as neede

18、d to elect which remaining parts of arrays will be passed on to parent node. A1A2Arrays of rand. #sEach proc pFeiges alg carried out in each node Each candidate picks a bin;winners=lightest bins contents 123456- Requires agreement on all bin choices.Feiges alg carried out in eacElections of arrays i

19、n nodeWe use scalable a.e. BA;bin numbers and S given by numbers from sequence of winning arrays of children. s1s2Elections of arrays in nodeWe As array moves up, secret shares are split up among more procs on higher levels and erased from children so that adversary cannot learn a large fraction of

20、arrays promoted to a higher level by taking over a small sets of processors on lower level.As array moves up, secret sharSecrets are revealed as needed: by reversing and duplicating communication down every path, reassembling shares at every leaf of subtree.so that adversary cannot prevent secret fr

21、om being exposed by blocking a single path.Secrets are revealed as neededLeaves are sampled (det.) by procs in subtree root to learn secret valueLeaves are sampled (det.) by pGeneration of a short SOnly a polylog number of arrays are left at each of the polylog children of the root. These form SWhen agreement on all of S is needed, a.e. BA can be run using supplemental bits. Generation of a short SOnly a Conclusions