|
Register | FAQ | The Twelve Commandments | Members List | Calendar | Arcade | Find the Best VPN | Today's Posts | Search |
General Gnutella Development Discussion For general discussion about Gnutella development. |
| LinkBack | Thread Tools | Display Modes |
| |||
Tamaha, Hi, Base32 does not reduce the number of bits, it change the way it is display/send. For example: 2 is "01" in Base 2. Both "2" and "01" contain the exact same information it's just display in another way. Base32 and Base64 convertion are use to assure that datas can travel to different OS/Computer and still be the same value. |
| |||
Wrong? I guest you don't understand. Yes Base32 use 5 bits, but when it encode 11111111 (255) it does not scrapt the remaining 3 bits, like i previously explain it only change how they are send. In this case 255 would be send with 00011111 then 00000111. So sending Byte 32 and Byte 8 in BASE32 is the same as sending Byte 255 in Base255 But the result is the same the value is 255. Changing the Base DOES NOT CHANGE THE VALUE, it change how it's display. Otherwise it's not a base change it's a value change. Marc. |
| ||||
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. |
| ||||
PS: Some ppl suggest to combine a small CRC hash with filesize (which is allready in Queryhits, not in Queries or other Gnutella descriptors).... let's play around with this idea. This would be a 32 bit hash + 32 bit filesize (taken from Gnutella protocol v0.4) = 64 bit key to use. Perhaps it would be more unique to use a real hash of 64 bit instead of the 64 bit CRC+filesize combo, e.g. an truncated MD5? Here an overview of minimum possibilities: * CRC-32, size 32 bit * CRC-32 filesize combo, size 64 bit * MD5 truncated, size 64 bit * MD5, size 128 bit Notes: I have choosen MD5 in this case, because it is the smallest and fastest compared to other hashs (SHA1, Tiger, Snefru). The CRC-32 alone is too small. The CRC-filesize combo might be enough, the truncated 64 bit MD5 might be mathematically more unique while it wastes 32 bit information in Queryhits (not in Query, GET, PUSHS). The next higher alternative is a 128 Bit MD5, e.g FastTrack uses an MD5 hash AFAIK. I'm not sure if a minimum alternative is the best solution for Gnutella's future. Perhaps a 64 bit key does make us happy now, in future with more superpeers and bigger horizons we might want to have a bigger hash (MD5 or SHA1)? An possibility could be an encoding alla HUGE. The hash has an prefix telling the hash type. For binary Gnutella messages (Query/Queryhits) this could be a payload like: byte 0 = hash type, more bytes = binary hash. The protocoll defines a list of known hash, while clients need a common solution, this list will be short, e.g start with CRC-filesize combo today and use SHA1 in future. In HTTP-alike Gnutella messages we can work with encoded hashs (not binary), similar to the HUGE proposal [1]. Conclusion: I have none. I suggest to implement and test a minimum solution (CRC32-filesize combo) and a bigger hash (MD5 or SHA1) for a while. With more experience in a real world environment we can hopefully find a suitable solution. Feedback, tests and mathematical analysis are welcome! [1] "HUGE" - http://groups.yahoo.com/group/the_gd...roposals/HUGE/ (Yahoo account required) Last edited by Moak; January 12th, 2002 at 07:54 AM. |
| ||||
PPS: Here is a summary why using Base32 or Base64 encoding in HTTP-style requests/headers. ------ snip ------ From http://groups.yahoo.com/group/the_gdf/message/2442: - We could choose any encoding, but... - Base32 is useful for compatibility with URLs and domain names, so... - We might as well use it in protocol-fields, saving extra conversions and developer inconvenience. ------ snap ------ Which sounds logical... BUT.... at least we could also use Base64 after having a '?' in the location/URN. A HTTP GET could look like this: Definition: GET /get/hash?[URN] HTTP/1.0 Base32: GET /get/hash?sha1:BCMD5DIPKJJTG2GHI2AZ9HG7HZUN5ZPH HTTP/1.0 Base64: GET /get/hash?sha1:/9n6YmKqNRmcLIiKC+2xRccm68 HTTP/1.0 Right now I prefer Base64 for HTTP encoding (it's smaller then Base32), binary encoding inside binary Gnutella binary messages and a smaller hash than SHA1. Last edited by Moak; January 12th, 2002 at 04:41 PM. |
| |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Gnutella Protocoll v0.7 Proposal | Moak | General Gnutella Development Discussion | 41 | August 17th, 2002 11:55 AM |
gnutella development plans | Iamnacho | General Gnutella Development Discussion | 11 | March 9th, 2002 07:21 PM |
My Proposal for XoloX!!! | Unregistered | User Experience | 1 | February 6th, 2002 09:11 AM |
Xolox and Gnutella development | Moak | Rants | 6 | November 25th, 2001 07:05 AM |
---a Radical Proposal--- | Unregistered | General Gnutella / Gnutella Network Discussion | 0 | September 21st, 2001 01:08 PM |