1、Breaking the O(n2)Bit Barrier:Scalable Byzantine Agreement with an Adaptive Adversary Valerie King Jared SaiaUniv.of VictoriaUniv.of New Mexico Canada USA Each proc.starts with a bit;Goal:All procs.decide the same bit,which must match at least one of their initial bits.t=#of bad procs.controlled by
2、malicious AdversaryByzantine agreement for large scale networksIf you could do it practically,you would!Why?Protecting against malicious attacks Organizing large communities of users Mediation in game theoryFundamental building blockOur Model Procs=1,2,n Message passing:A knows if it receives from B
3、 Synchronous Private random bits Private channels Adaptive adversary Resilience:t n(1/3-)Limit on#bits sent by good procs.:Bad procs can send any#.Our Model Procs=1,2,n Message passing:A knows if it receives from B Synchronous Private random bits Private channels Adaptive adversary Resilience:t n(1/
4、3-)Limit on#bits sent by good procs.:Bad procs can send any#.Our Model Procs=1,2,n Message passing:A knows if it receives from B Synchronous w/rushing adv.Private random bits Private channels Adaptive adversary Resilience:t n(1/3-)Limit on#bits sent by good procs.:Bad procs can send any#.Our ModelPr
5、ocs=1,2,nMessage passing:A knows if it receives from BSynchronous 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,nMessage passing:A knows if it receives from BSynchronousPrivate random bits Private
6、 channelsAdaptive adversaryResilience:t n(1/3-)Limit on#bits sent by good procs.:Bad procs can send any#.Our ModelProcs=1,2,nMessage passing:A knows if it receives from BSynchronousPrivate random bitsPrivate channels Adaptive adversaryResilience:t n(1/3-)Limit on#bits sent by good procs.:Bad procs c
7、an send any#.Our ModelProcs=1,2,nMessage passing:A knows if it receives from BSynchronousPrivate random bitsPrivate channelsAdaptive adversary Resilience:t n(1/3-)Limit on#bits sent by good procs.:Bad procs can send any#.Our ModelProcs=1,2,nMessage passing:A knows if it receives from BSynchronousPri
8、vate random bitsPrivate channelsAdaptive adversaryResilience:t 0(Implication of Dolev Reischuk)Our 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)roundsAlsoTheorem 2:(a.e.BA)For any c
9、onsts.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 Previous work An expected constant number of rounds suffice.(Feldman and Micali 1988)All previously known protocols use all-t
10、o-all communication KEY IDEA:The power of a short somewhat random stream S S=s1 s2 sk be short stream of numbers.Some a.e.global random numbers,some numbers fixed by an adversary which can see the preceding stream when choosing.-S can be generated w.h.p.Talk outlineI:Using S to get a.e.BAII Using S
11、to go from a.e.BA to BAIII Generating S Rabins BA with Global Coin GCtn/3 Set vote all procs.Maj-majority bit from others Fract 2/3 agree on bit then vote-Maj Else if GC=1 set vote-1;else set vote-0Scalable a.e.BA with a.e.Global Coin GCt 2/3+/2-using S instead of GC-a.e.BA whpFor i=1,k,generate bit
12、 si and run a.e.BA using si for a.e.global coinIt suffices that clog n bits of S are known a.e.and random II:Using S to go from a.e.BA to BA Idea: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
13、 in our model,the adversary can flood all procs with queries!Use s to decide which queries to answer.II: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/3 majo
14、rity 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!III Generating SSparse network Tree of robust supernodes of increasing size with links:procs in child-procs in parent node procs in parent node-leave
15、s of subtrees All procs.Supernodes and links generated usingaveraging samplers 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 needed to elect which remaining parts of arrays will be passed on to parent node.A1A2Feiges a
16、lg carried out in each node Each candidate picks a bin;winners=lightest bins contents 123456-Requires agreement on all bin choices.Elections of arrays in node We use scalable a.e.BA;bin numbers and S given by numbers from sequence of winning arrays of children.s1s2As array moves up,secret shares are
17、 split up among more procs on higher levels and erased from children so that adversary cannot learn a large fraction of arrays promoted to a higher level by taking over a small sets of processors on lower level.Secrets are revealed as needed:by reversing and duplicating communication down every path
18、,reassembling shares at every leaf of subtree.so that adversary cannot prevent secret from being exposed by blocking a single path.Leaves are sampled(det.)by procs in subtree root to learn secret valueGeneration of a short SOnly a polylog number of arrays are left at each of the polylog children of
19、the root.These form SWhen agreement on all of S is needed,a.e.BA can be run using supplemental bits.ConclusionsUses of S:Easier to generate than a single random coinflip:S can also be generated w.h.p scalably in the full information nonadaptive adversary model(whereas a single random coinflip cant)A
20、 polylog size S has sufficient randomness to specify a set of n small quorums which are all good w.h.p(submitted to ICDCN)Useful in the asynch alg w/nonadaptive adv(SODA08)Future work(contd)Asynchronous?Towards more practical scalable BA?Bounds on the communication of the bad procs makes the a.e.BA to BA easy.Likely this would simplify the a.e.BA protocolOther problems(SMPC,handling churn and larger name spaces)Other user models(selfish)Questions?
