On Mon, Apr 28, 2008 at 08:33:08AM -0600, zooko wrote: > > AFAIK some DHTs use order preserving hash functions, but I do not know > > which ones. > > I've never heard of this and would be interested to learn more. > > It's important to distinguish between things which go under the > rubric of "hash functions". All DHTs that I am familiar with use > *cryptographic* hash functions, which are different beasts from the > kind of hash function that you use in data structures. > > There is no such thing as an order-preserving cryptographic hash > function, by definition (preserving order would be a violation of the > intended security properties of a cryptographic hash function).
It feel like you could get some of the properties of a cryptographic hash function along with order preservation if you were willing to tolerate a hash that was larger than the cryptographic security level. Say, something like: CSOPHF(x) = OPHF(x) || SHA-256(x) As long as OPHF has the ordering properties desired, then, treated as a single big-endian integer, you would have an ordered hash function that did have collision and pre-image resistance, though it would not have good psuedorandomness properties (depending on how OPHF behaves). I'm having trouble coming up with a working example of an OPHF at all, though. It seems messy: if you require x < y -> OPHF(x) < OPHF(y), then OPHF would have to have an equally large domain and range (though is this only true if < is a total ordering?) If you relax it to x <= y -> OPHF(x) <= OPHF(y), then all you would do (for lexicographical orderings like integers, bitstrings, ...) is output the first N bits of x, y - which seems a bit trivial. Is there a definition of OPHF that would allow a function that is both useful (length-reducing) and non-trivial? -Jack _______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
