Byzantine
broadcast is a distributed primitive that allows a specific party to
consistently distribute a message among “n” parties in the presence of
potential corrupt parties of up to t of parties. All known protocols
implementing broadcast of an l-bit message from point – to – point channels
tolerating any t<n byzantine corruptions have communication complexity at
least ā¦ (ln2).
The
presentation showed cryptographically secure and information – theoretically
secure protocol for t < n that communicate O(ln) bits when l is sufficiently large. This is optimal for any
protocol for broadcasting l-bit message.
Model of the Protocol
The
protocol consists of n parties (players) P = {p1………pn} with
some designated party called the sender which is denoted as ps for
some s ∈ {1……….n}. The
parties are connected with a synchronous authentic point – to – point network.
A broadcast protocol allows the sender ps to distribute a value vs
among parties P such that the following conditions satisfy.
Termination:
every correct party pi ∈ P terminates.
Consistency:
all correct parties in P decide on the same value.
Validity:
if the sender ps is correct, then every correct party pi ∈ P decides on
the value proposed by the sender vi = vs
Cryptographic secure block broadcast
protocol
The
protocol employs a collision resistant hash function CRHash. In the beginning
of the protocol the sender broadcasts a hash h = CRhash (vs) of the
value it holds. The goal of the protocol is to ensure that all correct players
learn vs. All parties during the protocol run are divided in
to two sets H and H`. The set H consists of happy players who have
already learned vs and H` who have not. At each round we try to move
a player from H` to H. We select a pair of players px, py
such that px ∈
H and py ∈
H`. Then px sends the value it holds to py. Once
py receives a value from px it verifies if its hash is h.
In the positive case py is included in H and in the negative case the
pair (px,py) is put in disputed set D. Hence in each round,
we either include one player in H or conflicted players in D.
Validity: A correct px ∈ H holds vx
with CRHash (vx) = h and
sends vx to py who
successfully verifies CRHash (vx) = h. If py
finds the hash of vx is h, broadcasts 1 else it broadcasts 0. Hence
if both px and py are honest, py will be added to H and (px,
py) is not added to D . If ps is correct then all honest
players will be in H.
Termination:
At each iteration of the algorithm either H grows or D grows. H is limited by n
and D is limited by n2. Hence number of iterations are limited.
Consistency:
In all iterations all correct parties send correct v value and all correct
parties verify h = CRHash(v) . Hence if atleast one honest party is in H, all correct
parties will end up in H set and no honest party is left in H`. Otherwise
none of the correct parties will be in H and all correct parties output ┴.
A situation where all the correct parties output ┴
is also consistent.
Complexity:
At each iteration of algorithm, either H grows or D grows. Hence the number of
iterations is upper bounded by O(n+d).
Note that d is the number of pairs who have found dispute. This can be O(n2) at maximum if there are
n parties. The total communication cost of the protocol is upper bounded by B(|h|) + (n+d)(|vs| +B(1)), where B(a) is the number of bits communicated using the broadcast
protocol for single valued messages to broadcast a.
Constructing
Broadcast for long messages
In the above described protocol if we
transmit complete message at once , that is if
|vs| =l , then the worst case complexity will be O(ln2) and we end up no better
than any other previous broadcast protocol . But if we use the above protocol as
a sub-protocol to broadcast a long message of length l bit then the
complexity reduces. The key idea is that
the set D holding dispute pairs is
global for each iteration of this sub-protocol. The protocol will be invoked q
times where each invocation transmits |l/q| length of message. Hence the
communication complexity will be
At
the beginning of the protocol D is initialized to null set. The d set keeps
growing if there are disputes in each
iterations. The state of D in previous iteration is carried to next iteration where each iteration
broadcasts l/q length of message. Hence the size of D is sum of all dis where di denotes
the newly added disputes in ith iteration of block transmit. D can be O(n2) at maximum.
It
is evident that above algorithm is optimal when q=n. That is we get O(ln).
Universal
Hash Functions
Consider
a family of functions U = {uk}k∈K
induced with a key set K , where each
function uk maps elements of some set X to a fixed set of
bins Y. The family U is called ∈-universal
if for any two distinct messages v1 and v2
Similar
to the cryptographic case, all parties during the protocol are divided into two sets H and H`. The
difference to the cryptographic case is that the set H is not monotonically
increasing. It may happen that the some players may be added / removed from H
several times. At each iteration of the algorithm we try to move a player from
H` to H. We select a pair of players px, py such that px∈H, py∈H` such that {px,
py} !∈ D.
Then px sends the value it holds to py. Now player py
needs to verify that the value received from px is the value that
correct parties in H hold. In order to do so, py broadcasts a random
key k from ∈
- universal hash function ITHash and then ps broadcast a hash h for
this key. As long as py honestly chooses k uniformly at random with
overwhelming probability correct players will obtain different hashes if they
hold different values. If a party in H U{py} / {ps} holds a
value with a hash h, then the broadcast 1 and 0 otherwise. If every party
broadcast 1 then the iteration was successful and py is added to H.
otherwise some of the parties in H ∪ {py} do not hold the right values
and we search for disputes.
In this protocol the dispute can arise between
any two parties in H. In order to find such disputes one must be able to reason
about history of how H was formed. Thus a history set T will contain pairs of
players (px,py) such that py learned the value
it holds from px. Whenever a
party pj broadcasts zero, it means that the hash value generated by
the sender and party pj is not matching . In such a case we refer to
the history set to see the predecessors of pj from whom message v, which is under dispute
has reached to pj . Among them we check for the parties at which the
transition of broadcast bit has happened from 1 to 0. We add such parties as
dispute pairs in set D. If a dispute occur, then we will set H={Ps}
and T=Ļ.
There
can be at most n consecutive iterations, where no conflict is found. Hence
number or rounds is at maximum O(n+nd).
Hence
communication complexity is O((n+nd) (|vs|) + B
(|h|) + B(|k|) + nB(1))).
Communication complexity of Long Messages
We get O(ln) if we set q=n2
No comments:
Post a Comment