Transcript Group Spreading

Group Spreading: A
Protocol for Provably Secure
Distributed Name Service
Christian Scheideler
Dept. of Computer Science
Johns Hopkins University
Joint work with Baruch Awerbuch
Name Service
Peer: entity with a unique identity, i.e. identified by
(Name(p), IP(p))
Goal: provide name service, i.e. each execution of
Lookup(name) returns IP(p) of the peer p with
Name(p)=name, or NULL if there is no such peer
Robust Distributed Name Service
2
Name Service
Static set of peers.
Easiest solution: every peers knows every
other peer.
Problem: not scalable!
Better solution: peers organize in a
searchable overlay network of low degree.
Robust Distributed Name Service
3
Chord
[Stoica, Morris, Karger, Kaashoek, and Balakrishnan ’01]
Idea: organize peers in cycle according to
hash function h:Names
[0,1).
0.28
0.43
Robust Distributed Name Service
0.58
4
Hypercubic Shortcuts
1
0
+1/2
+1/4
fingers
+1/8
+1/16
x
Robust Distributed Name Service
5
Hypercubic Pointer Structure
Robust Distributed Name Service
6
Lookup Operation
Lookup(name): ~log n number of hops
Pure
Can
Chord
alsocannot
handlehandle
dynamic
adversarial
set of peers.
peers!!
Robust Distributed Name Service
7
Distributed Name Service
Dynamic set of peers, some adversarial.
Operations:
Join(p): peer p wants to join the system
Leave(p): peer p wants to leave the system
Lookup(name): returns IP(p) of the peer p with
Name(p)=name, or NULL if there is no such peer
Goal: Provide provably survivable distributed name
service
Robust Distributed Name Service
8
Prerequisites
Certification authority:
certifies (Name,IP) pairs so that collisions
are avoided
prevents adversarial peers from taking
over identity of honest peers
cannot prevent adversarial peers from
registering (potentially many) own pairs
Allow
Fighting
adversary
at this front
to have
is fighting
infinitely
themany
wrong
identities,
battle!
but resources finite!
Robust Distributed Name Service
9
Correctness
Once Join(p) or Leave(p) terminates in p, it is called
completed.
p is called a member once Join(p) has completed.
p ceases to be a member once it initiates Leave(p).
Lookup(name) request executed correctly:
If an honest peer p with Name(p)= name is currently a
member of the system, returns IP(p).
Otherwise, if such a peer has never been in the system
or completed Leave(p) , returns NULL.
Otherwise, returns IP(p) or NULL.
Robust Distributed Name Service
10
Efficiency
Time unit: max time a message needs to travel
from one honest peer to another
An overlay network operation is called
work-efficient if it is completed using a comm
volume of at most polylog(n) bits
time-efficient if it is completed in at most
polylog(n) time units
Overlay network maintainance should only need
polylog(n) bits of comm per time unit per peer
Robust Distributed Name Service
11
Peer-to-Peer Name Service
Problem: adversarial peers a priori indistinguishable
from honest peers
Idea: randomly distribute
peers in overlay network
[CAN,Chord,Pastry,…]
Strategy: use pseudorandom hash function
h:Names
[0,1)
Robust Distributed Name Service
12
Peer-to-Peer Name Service
Place peer p at h(name(p)) in [0,1):
randomly distributes honest peers
may not randomly distribute adversarial
peers
Robust Distributed Name Service
13
Peer-to-Peer Name Service
Problem: adversarial peers can isolate
honest peers
Chord: connect to
direct neighbors
closest successor of
i
h(Name(p))+1/2
Robust Distributed Name Service
14
Peer-to-Peer Name Service
Alternative:
Assign each peer p to a random ID(p) in
[0,1)
Robust Distributed Name Service
15
Peer-to-Peer Name Service
New attempt:
Assign each peer p to a random ID(p)
Limit lifetime of a peer
Robust Distributed Name Service
16
Peer-to-Peer Name Service
So good approach:
Assign random IDs
Enforce limited lifetime
But:
How to interconnect the peers?
How to generate random IDs?
How to enforce limited lifetime?
How to implement operations?
Robust Distributed Name Service
17
Peer-to-Peer Name Service
How to interconnect the peers?
Region approach: each peer has several nodes,
each node v maintains rv=log n - loglog n + Q(1)
1
Region: interval of
size 1/2r starting
at an integral
multiple of 1/2r.
0
+/- 1/2
-1/4
+1/4
-1/8
1/2rv =
Q(log n / n)
+1/8
x
Robust Distributed Name Service
18
Peer-to-Peer Name Service
How to generate random IDs?
Group approach: each peer maintains Q(log n)
nodes, ID of new node generated by region
a)
b)
R
c)
R
Robust Distributed Name Service
R
19
Peer-to-Peer Name Service
How to enforce limited lifetime?
Lifetime approach:
Join operation implemented s.t. it either
terminates in Q(log n) steps or does not
succeed
Honest nodes take median of age views of
a node reported by nodes in region
Honest nodes cut connections to nodes
that are more than L=Q(log n) steps old
Robust Distributed Name Service
20
Peer-to-Peer Name Service
How to implement operations?
Join(p): p contacts a peer q in the system,
q includes Q(log n) nodes for p into the
system, from there p inserts entry
(Name(p),IP(p)) into relevant region and
takes over maintenance of its nodes
Leave(p): p deletes entry (Name(p),IP(p))
and leaves the system
Lookup(name): region routing, majority
decision
Robust Distributed Name Service
21
Assumptions
adversary e/log n - bounded
join/leave rate of peers is O(1/log2 N)
honest peers have infinite bandwidth (no DOS)
assumptions about messages…
A peer is honest if
it is not under the control of the adversary at any
time,
it is reliable, and
it contacted an honest peer in order to join the
network.
Robust Distributed Name Service
22
Related Work
Classical distributed computing: Byzantine
agreement, two-phase commit, linear overhead
Proactive security: uses coding to protect data in
dynamic environment, linear overhead
Fixed-topology networks: only fail-stop faults, no
Byzantine behavior
Hash-based P2P networks: hinge on assumption
that IDs are random
Random or unpredictable placement (Freenet,
Gnutella): hard to attack, but hard to find data
Robust Distributed Name Service
23
Related Work
[Sit and Morris 2001]: investigate various attacks
and defenses including routing attacks, storage
and retrieval attacks, DoS, and join/leave attacks
[Castro, 2001]: replication algorithm tolerating
Byzantine faults as long as 1/3 fraction of
replicas faulty
[Douceur, 2002]: Sybil attacks (adversaries forge
multiple identities)
[Castro, Druschel, Ganesh,… 2002]: strategies
for secure nodeID assignment, routing table
maintenance, and message forwarding
BUT: no provably robust overlay construction
Robust Distributed Name Service
24
Comparison
Group Spreading: e/log N-bounded adversary
Enforced Spreading: e-bounded adversary
N
Trust-but-Verify
work
overhead
Group Spreading
polylog(N)
Enforced Spreading
0
fraction of adv nodes
e/log N
Robust Distributed Name Service
e
1/2
25
Conclusions
It is possible to come up with provably
robust overlay network constructions!
Analysis hard…
Model still unrealistic, but Rome was also
not built in one day 
Questions????
Robust Distributed Name Service
26
STOC 2005
When: May 22-24, 2005
Where: Baltimore, MD, USA
Submission deadline: Nov 4, 5:59 pm EST
Web Site: www.cs.jhu.edu/~stoc05
Robust Distributed Name Service
27