Skip to Content.
Sympa Menu

bluesky - Freenet's hashing algorithm

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: hal AT finney.org
  • To: bluesky AT franklin.oit.unc.edu
  • Subject: Freenet's hashing algorithm
  • Date: Thu, 15 Feb 2001 14:43:05 -0800


Ted Anderson, <ota AT transarc.com>, writes:
> For publishing, the use of CHKs means that data can be delivered to the
> reader, or to a congenial jurisdiction, via any and all means available
> without risk of compromising the data's integrity or utility to the
> consumer. Email, CD-ROMs by mail, Tee-shirts, or carrier pigeon all can
> be used in a pinch to avoid exposing the author's address. Once it
> arrives, if it has the right hash it is the right data, no questions
> asked.

This is one of the big advantages of content based hash schemes.

Freenet delivers the data by streaming it back through the chain of nodes
that the request followed to find the data. Each node in the back chain
caches the data as it passes through. This serves to spread popular
data throughout the network, one of the design goals of Freenet.

However this mechanism is vulnerable to spoofing. A node which supplies
bogus data in response to a request might not have the failure detected
until the entire data packet has been received and hashed. This could
tie up considerable network resources.

In order to avoid this, Freenet adopts a hash based on the paper by
Gennaro and Rohatgi, "How to Sign Digital Streams", from Crypto 97.
The idea is that you break your data up into blocks, and then create a
chained hash. Hash the last block and store the hash with the preceding
one; hash that block (including the stored hash) and store that with
the next preceding one; and so on, up to the first block. The hash
of the first block (with its stored hash of the rest of the message)
is the content hash of the message as a whole.

With this mechanism, the data can be check for compliance with the
hash as each block is received. The worst a misbehaving node can do is
to return incomplete data, cutting off before the last block is sent.
It also means that a node cannot falsely respond to a request unless it
has at least a prefix of the requested data, which reduces the possible
impact on the network.

I don't know if this kind of hash would be suitable for other networks,
but perhaps it would be helpful in some cases.

Hal




Archive powered by MHonArc 2.6.24.

Top of Page