View Single Post
  #16 (permalink)  
Old January 11th, 2002
Moak's Avatar
Moak Moak is offline
Guest
 
Join Date: September 7th, 2001
Location: Europe
Posts: 816
Moak is flying high
Post Hashs in Queries (SMALL != HUGE)

Hi,
I thought more about hashs in Gnutella Queries. I personally think they should be as small as possible, because I expect a increased Query/Queryhit traffic from new clients with features like automatic resume and multisegmented downloads. While automatic requeries are a key technology for those features, the Query traffic especially for hash wil increase. Perhaps it will be also necesarry to group multiple searches together into a single message (multiple searches in one Gnutella Query to avoid repeated sending of Gnutella descriptor header, 23 bytes + more repeated payload). A small query/hash will be necessary in my eyes, as small as possible.

Different people have different ideas of a small hash. It should be still unique enough to fit our needs, common are AFAIK those suggestions:

* CRC-32, size 32 bit (256 hashs/KB *) [1]
* MD5, size 128 bit (64 hashs/KB) [2]
* SHA1, size 160 bit (51.2 hashs/KB) [3]
* Tiger, size 192 bit or truncated to 128 or 160 (42.6 hashs/KB) [4]
* Snefru, 256 bit (32 hashs/KB) [5]

I'm not sure about which hash to use (prefered). There seems to be nothing between 32 bit (CRC-32) and 128 bit (MD5) length. CRC32 will be not unique enough within a typical Gnutella horizon, better start to use MD5 or higher. Is it possible to truncate a big hash to e.g. 64 bits, does this make sense? I'm not familiar with cryptography, this is only a short summary... perhaps someone else wants to add some more qualified comments? :-)

At least the hash should be IMHO pure binary in inside the query (not BASE32 encoded which blows up the size again), in HTTP headers it might be BaseWhatever encoded to gain highest HTTP/1.x compatibilty. I think indexing speed is secondary [6]. Indexing local shared files can be performed in background on first startup (meanwhile the client does not answer with own hashs, but can allready search for).

* = pure binary hash, not included are descriptor headers or other protocol overhead

[1] CRC-32 - http://www.ietf.org/rfc/rfc1510.txt (ISO 3309)
[2] MD5 - http://www.faqs.org/rfcs/rfc1321.html
[3] SHA1 - http://www.faqs.org/rfcs/rfc3174.html
[4] Tiger - http://www.cs.technion.ac.il/~biham/Reports/Tiger/
[5] Snefru - http://www.faqs.org/faqs/cryptography-faq/part07/
[6] Hash Indexing Speed - http://groups.yahoo.com/group/the_gdf/message/1970

Last edited by Moak; January 11th, 2002 at 02:39 PM.
Reply With Quote