Transcript AGRID Project Presentation - Department of Electrical Engineering

Sunday, Nov.7, 2004
Freenet
Freenet - A Distributed
Anonymous Information
Storage and Retrieval System
Topics in Reliable Distributed
Computing
Yoav Levy 2004
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 1 of TBD
Sunday, Nov.7, 2004
Freenet
Freenet – Presentation Outline
•
•
•
•
Motivation & Goals
Anonymity & Censorship Resistant Networks
Small World Phenomena
Architecture
–
–
–
–
Keys - content-hash (CHK) and signed-subspace (SSK) keys
Search
Routing: the small-world paradigm
Storage Management
• Freenet Performance
• Comparing with Other Systems
• Free Discussion
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 2 of TBD
Sunday, Nov.7, 2004
Freenet
Sources
• Protecting Free Expression Online with Freenet
– I. Clarke, T. Hong, O. Sandberg
– IEEE Internet Computing, January 2002:
http://freenet.sourceforge.net/papers/freenet-ieee.pdf
• Performance in Decentralized File-sharing Networks
– T. Hong. In Proc. of the O’Reilly Peer-to-Peer Conference, San
Francisco, California, February 14-16, 2001
• Censorship Resistant P2P Content Addressable Networks
– A. Fiat & J Saia 2002
• Navigation in a small world
– Jon M. Kleinberg, Nature, Aug. 2000
• Freenet explained: http://freenetgw.bishopston.net/freenetexplained
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 3 of TBD
Sunday, Nov.7, 2004
Freenet
Freenet – Goals & Motivation
• Preserving the privacy of information
producers, consumers, and holders
– Resistance to information censorship
– Can Freenet withstand hackers? The government?
• High availability and reliability through
decentralization
– The Slashdot effect
– Efficient, scalable, and adaptive storage and
routing
– Resistance to denial attacks
• What are the current trends?
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 4 of TBD
‫‪Sunday, Nov.7, 2004‬‬
‫‪Freenet‬‬
‫…‪From the Press‬‬
‫"‪...‬האם אין זה מתבקש‪ ,‬שטכנולוגיית החלפת הקבצים‬
‫תכבוש גם את שידורי הטלוויזיה ותנסה להעביר אותם דרך‬
‫האיטרנט לכל דורש ובלא תשלום?"‬
‫"‪...‬כל מה שצריך לעשות הוא לחבר את הטלוויזיה‬
‫למחשבןלהשתמש בתוכנה מתאימה שתפאשר להפיץ את‬
‫השידור בין מאות ואלפי גולשים‪ ,‬שכל אחש מהם ישמש‬
‫תחנת ממסר קטנה‪ ,‬המפזרת את עוצמת העיבוד ורוחב הפס‬
‫הנדרשים להפצת שידור הטלויזיה‪".‬‬
‫יובל דרור‬
‫הארץ ‪2.11.2004‬‬
‫‪Slide 5 of TBD‬‬
‫‪Faculty of Electrical Engineering, Technion‬‬
‫‪Yoav Levy‬‬
Sunday, Nov.7, 2004
Freenet
BPI wins court order against British
P2P
users
(Oct.
14
2004)
“British Phonographic Industry, the UK equivalent of
the RIAA, has won the first court round in its fight
against British P2P users, when British courts
granted a court order against 28 P2P users BPI raided
earlier this month. The court order means that users'
ISPs have to hand over users' personal details
(names and addresses) within 14 days to the BPI.
According to BPI's claims, all of the users now sued
are so-called "heavy uploaders", people who
cotribute to P2P networks by sharing vast amounts
of music rather, rather than downloading tracks.”
Source: BBC
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 6 of TBD
Sunday, Nov.7, 2004
Freenet
The Effect of File Sharing on Record Sales - An
Empirical Analysis (March 2004)
"We consider the specific case of file sharing
and its effect on the legal sales of music. A
dataset containing 0.01% of the world’s
downloads is matched to U.S. sales data for a
large number of albums…Downloads have
an effect on sales which is statistically
indistinguishable from zero, despite rather
precise estimates.”
Felix Oberholzer (Harvard Business School), Koleman Strumpf (UNC
Chapel Hill)
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 7 of TBD
Sunday, Nov.7, 2004
Freenet
Remailers and Mixnets
• Traceable remailers
– Keeping internal lists of senders – enables replies
– Pseudonymous remailers – use cryptography
– Problems?
• Anonymous remailer
– Do not keep any list
– Is this really safe?
• Mixmaster
– By Lance Cottrell
– Scrambles message contents
• Mixnets
– Introduced by David Chaum
– A network composed of “mixers” - is a third party that combines and
forwards messages from several senders to several recipients
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 8 of TBD
Sunday, Nov.7, 2004
Anonymity & Censorship Resistant
Networks
Freenet
• A work by A. Fiat & Jared Saia
• A content addressable network is defined as a
distributed, scalable, indexing scheme for peer-topeer networks.
• Random vs. Adversarial: Resistance to Adversarial
Node Deletion
• P2P robust against random attacks “by design”
• Tapestry used within Oceanstore, robust against
random faults
• Spam Resistance
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 9 of TBD
Sunday, Nov.7, 2004
Freenet
Navigation in a small world
• The small-world model
– Milgram: six degrees of separation
– Watts: between order and randomness
• short-distance clustering + long-distance shortcuts
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 10 of TBD
Sunday, Nov.7, 2004
Freenet
Webometrics
• Ademic 1999 (.edu
research)
• AltaVista crawl
(1999)
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 11 of TBD
Sunday, Nov.7, 2004
Freenet
Chaos & The Power Law Effect
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 12 of TBD
Sunday, Nov.7, 2004
Freenet
Technical Issues
• Success Rates
– Can we find the data?
– Length of query paths
• Scalability
– Logarithmic / linear / polynomial
• Robustness
– Participants are unreliable
– Different failure modes possible
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 13 of TBD
Sunday, Nov.7, 2004
Freenet
Architecture
• Each participant hosts a local data store as
well as a routing table
• Requests for files are made using location
independent keys
• Routing is propagated through chain of proxy
requests
• Graph structure adapts and evolves over time
• Files may migrate between nodes
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 14 of TBD
Sunday, Nov.7, 2004
Freenet
Key Based Searching
• Content-hash keys (CHK):generated by hashing the
contents of the file to be stored
– Gives every file a unique absolute identifier
– Identical copies of a file inserted by different people
automatically coalesced
• Signed-subspace key (SSK): sets up a personal
namespace that anyone can read but only its owner
can write to
– Used as a “human” filename (as opposed CHK that may be
thought of as i-nodes)
– Enable easy file updates
– Facilitate trust by guaranteeing that the same
pseudonymous person created all files in the subspace,
even though the subspace is not tied to a real-world
identity
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 15 of TBD
Sunday, Nov.7, 2004
Freenet
Retrieving Files
• How do we locate the keys?
– Hypertext spider
– Indirect files – published with KSK of search
words
– Publish bookmarks
• File retrieval
– Request forwarded to node in RT with closest
lexicographic match for the binary key
– Request routing follows steepest-ascent hill
climbing: first choice  failure  backtrack 
second choice
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 16 of TBD
Sunday, Nov.7, 2004
Freenet
Retrieving Files (contd.)
c
a
b
f
e
d
• Request thread length controlled by use of timers
and number-of-hops
• Files are cached all along the retrieval path
– Performance pro or con?
• Self-reinforcing cycle – results in key expertise
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 17 of TBD
Sunday, Nov.7, 2004
Freenet
Self Reinforced Routing
• Snapshots using 300
requests with hops = 500
• As network converges it
drops to 6 - “six degrees
of separation”
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 18 of TBD
Sunday, Nov.7, 2004
Freenet
Publishing
• Similar to retrieval but, 2 step process
– Detect collisions – ‘all clear’ if no collision
– Publish to node in RT with closest key match
• Are CD and publish paths same?
– Can result in collision during publish step
• Inserts allow new nodes to advertise
themselves
 Key-squatting is not effective
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 19 of TBD
Sunday, Nov.7, 2004
Freenet
Data Management
• Finite data stores - nodes resort to LRU
• Routing table entries linger after data eviction
• Outdated (or unpopular) docs disappear
automatically
• Bipartite eviction – short term policy
– New files replace most recent files
– Prevents established files being evicted by attacks
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 20 of TBD
Sunday, Nov.7, 2004
Freenet
Network Growth
• New nodes have to know one or more guys
• Problem: How to consistently decide on what
key the new node specializes in?
– Needs to be consensus decision – else denial
attacks
• Advertisement  IP + H(random seed s0)
– Commitment - H(H(H(s0) ^ H(s1)) ^ H(s2))…….
– Key for new node = XOR of all seeds
• Each node adds a RT entry for the new node
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 21 of TBD
Sunday, Nov.7, 2004
Freenet
Network Growth
• Key assigned to
new nodes = H(IP)
• Scales as log(n)
until n ~ 40000
• At 40000, RTs are
full
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 22 of TBD
Sunday, Nov.7, 2004
Freenet
Fault Resilience
• Median path length
< 20 at 30% node
failures?
• N/w becomes
ineffective at 40%
failures ???
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 23 of TBD
Sunday, Nov.7, 2004
Freenet
Links in the small world
• “Scale-free” link distribution
P(n) ~ 1/n 1.5
– P(n) = 1/n k
– most nodes have only a few connections
– some have a lot of links
• important for binding disparate regions together
• e.g. Tim O’Reilly
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 24 of TBD
Sunday, Nov.7, 2004
Freenet
The importance of routing
• Existence of short paths is not enough – they
must be found
• Adaptivity helps Freenet find good paths
• Compare: a random-routing network
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 25 of TBD
Sunday, Nov.7, 2004
Freenet
Scalability
• Real-world networks are much larger
– nearly 400,000 downloads of Freenet
– 50 million Napster users
• How well does Freenet scale?
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 26 of TBD
Sunday, Nov.7, 2004
Freenet
Random failure
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 27 of TBD
Sunday, Nov.7, 2004
Freenet
Targeted attack
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 28 of TBD
Sunday, Nov.7, 2004
Freenet
Security & Privacy
• Is true anonymity guaranteed?
• File integrity - KSK vulnerable to dictionary
attacks
• DOS attacks – Hash Cash to slow down
• Attempts to displace valid files are
constrained by the insert procedure
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 29 of TBD
Sunday, Nov.7, 2004
Freenet
Other Systems
• Queries
– Freenet, Chord - routed queries
– Napster - centralized lookup: simple, but O(N) state and a
single point of failure
– Gnutella – flooded queries: robust, but worst case O(N)
messages per lookup
• Freenet and Chord
– Unlike Chord, Freenet does not guarantee that a query will
return a specific document that exist on the network.
– Unlike Chord, Freenet does not assign keys to specific
nodes, thus maintaining data store anonymity
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 30 of TBD
Sunday, Nov.7, 2004
Freenet
Other Systems (Contd.)
• Freenet and Gnutella
– Both Gnutella and Freenet are distributed Information systems.
– They differ significantly in both goals and implementation.
– Basically,
• Each is a system for searching for information
• Each returns information without telling you where it came from
• Freenet and Publius
– Both provide publisher anonymity, deniability, and censorship
resistance
– Freenet provides anonymity for retrievers and servers, as well
– Cost is high: data must be cached at many nodes
– Publius provides persistence of data, Freenet does not
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 31 of TBD
Sunday, Nov.7, 2004
Freenet
Free Discussion
• Does the solution answer the requirements?
The need?
• Paper Strengths & Weaknesses
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 32 of TBD
Sunday, Nov.7, 2004
Freenet
Thank You!
Yoav Levy
Faculty of Electrical Engineering, Technion
Slide 33 of TBD