Fingerprints and hashing
Dear Haskellers Here's a challenge. We are all familiar with the idea of an MD5 checksum, which provides a reliable "fingerprint" for a file, usually 128 bits or so. If the file changes, the fingerprint is (almost) certain to do so too. There are lots of techniques: CRC, shar?, MD5, etc. For various applications (including identifying common sub-expressions, and version tracking in GHC), I'd like a Haskell library that supports simple fingerprint operations. Below I give an informal specification of such a library. I can think of any number of implementations, but I'd like one that is (a) robust and (b) efficient. By "robust" I meant that with, say, a 128-bit fingerprint the chance of accidental collision is truly low; a non-robust implementation uses the 128-bit space in a non-uniform way [trivial example: gets stuck on zero]. Any takers? I bet some of you have this already, in some form. Simon The module signature would be something like this: data Fingerprint instance Eq Fingerprint instance Ord Fingerprint initialPrint :: Fingerprint class Fingerprintable t where fingerPrint :: t -> Fingerprint -> FingerPrint instance Fingerprintable Char instance Fingerprintable Int instance Fingerprintable Word32 -- etc The fingerPrint operation here is expressed in the traditional way: an accumulator (say 128 bits) into which one stuffs successive values (e.g. a byte stream). However, very important, I also want a more compositional form: instance Fingerprintable Fingerprint so that I can do something like fp :: Expr -> Fingerprint fp (App e1 e2) = fp e1 `fingerPrint` fp e2 Yes, I could thread the accumulator, thus: fp' :: Expr -> Fingerprint -> Fingerprint fp' (App e1 e2) p = fp' e1 (fp' e2 p) but I can't *always* do that; or even if I can, I may already *have* a fingerprint for e1 in my hand, and it's painful to re-traverse e1. Think of hash-consing. An obvious implementation of "instance Fingerprintable Fingerprint" is to divide one fingerprint into words, and feed it into the other via the Word32 instance. But it's not clear to me whether or not that is robust. (Incidentally, one could define the class thus: class Fingerprintable t where fingerPrint :: t -> FingerPrint plus plusFP :: Fingerprint -> Fingerprint -> Fingerprint But I think it'd be less efficient if that was the only way, because of all those now-compulsory plusFP operations.) I'd like one other thing: to be able to trade cost for accuracy. I'd like a 128-bit fingerprint with essentially zero chance of having two distinct values that map to the same fingerprint; and a one-word fingerprint that was a lot more efficient, but where collisions would be entirely possible (again hash-consing is an example).
Hi Simon,
We are all familiar with the idea of an MD5 checksum, which provides a reliable "fingerprint" for a file, usually 128 bits or so. If the file changes, the fingerprint is (almost) certain to do so too. There are lots of techniques: CRC, shar?, MD5, etc.
I believe the basic operations are all in the Crypto library: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Crypto-3.0.3 - see Data.Digest.SHA1 and Data.Digest.MD5 - digest is simply another word for fingerprint in this sense. However, your fingerprint stuff sounds a lot more like a request for a Hash function - rather than something that operates over streams of bytes. To get both, I'd recommend something like taking the digest of the data after calling show, or after serialising it to a ByteString with the binary library. Doing it this way means you have no additional need for a FingerPrint class but can reuse the existing Show/Binary class. Thanks Neil
Neil Mitchell wrote:
Hi Simon,
We are all familiar with the idea of an MD5 checksum, which provides a reliable "fingerprint" for a file, usually 128 bits or so. If the file changes, the fingerprint is (almost) certain to do so too. There are lots of techniques: CRC, shar?, MD5, etc.
I believe the basic operations are all in the Crypto library: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Crypto-3.0.3 - see Data.Digest.SHA1 and Data.Digest.MD5 - digest is simply another word for fingerprint in this sense.
The Crypto library does indeed provide those operations, but the implementations are naive and hence extremely slow. Fine for hashing an individual password, but not appropriate for ten thousand identifiers in a compiler. <b
If compositionality is important, at least Rabin's fingerprints are worth considering: http://citeseer.ist.psu.edu/broder93some.html They have the neat property that the fingerprint of a concatenation of strings can be cheaply computed from the fingerprints of the constituents. I think this effectively means that the plusFP operation can be made associative, which might offer optimization opportunities. I remember implementing it some seven years ago when prototyping for a C implementation. The code is lost, though. I can give it a shot again, if this is considered a reasonable algorithm. Lauri
Interesting! The associativity property is the kind of thing I was after. Except that I don't really care if FP(as ++ bs) = FP(as) `plusFP` FP(bs). I only care that the latter is robust in the sense of having low probabilty of collision. So the Rabin scheme does more than I really need (which is probably fine). On page 1 he draws a distinction between fingerprinting and hashing, which relates to my last wish. Does one need a different technique for the two, or is it enough to reduce the number of bits in the Rabin scheme, and thereby get a hashing scheme? Strangely the paper gives no comparison with other fingerprinting schemes. Simon | -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Lauri Alanko | Sent: 11 October 2007 11:27 | To: haskell | Subject: Re: [Haskell] Fingerprints and hashing | | If compositionality is important, at least Rabin's fingerprints are | worth considering: http://citeseer.ist.psu.edu/broder93some.html | | They have the neat property that the fingerprint of a concatenation of | strings can be cheaply computed from the fingerprints of the | constituents. I think this effectively means that the plusFP operation | can be made associative, which might offer optimization opportunities. | | I remember implementing it some seven years ago when prototyping for a | C implementation. The code is lost, though. I can give it a shot | again, if this is considered a reasonable algorithm. | | | Lauri | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell
On Thu, 2007-10-11 at 12:28 +0100, Simon Peyton-Jones wrote:
Interesting! The associativity property is the kind of thing I was after. Except that I don't really care if FP(as ++ bs) = FP(as) `plusFP` FP(bs). I only care that the latter is robust in the sense of having low probabilty of collision. So the Rabin scheme does more than I really need (which is probably fine).
On page 1 he draws a distinction between fingerprinting and hashing, which relates to my last wish. Does one need a different technique for the two, or is it enough to reduce the number of bits in the Rabin scheme, and thereby get a hashing scheme?
Strangely the paper gives no comparison with other fingerprinting schemes.
Simon | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Lauri Alanko | | If compositionality is important, at least Rabin's fingerprints are | worth considering: http://citeseer.ist.psu.edu/broder93some.html
Note that Rabin's fingerprint algorithm is the same as CRC (http://en.wikipedia.org/wiki/Cyclic_redundancy_check). I'm not aware of people using CRCs for hashing inside a program, but they should work fine and be fairly fast. I can think of two caveats. 1) With CRC and a fixed polynomial, it is very easy for an "adversary" to pick multiple inputs that give the same fingerprint/hash code. (Rabin avoids this by picking a random polynomial after the adversary has selected the inputs.) Depending on the application, this may be very important, or it may not matter at all. 2) The straightforward approach for "instance Fingerprintable Fingerprint" works very poorly for CRCs. Considering balanced binary trees with four leaves, and the obvious compositional hash function, then for all a,b,c,d we would have fingerprint ((a,b),(c,d)) == fingerprint ((a,c),(b,d)), and fingerprint ((a,b),(b,d)) == fingerprint ((a,c),(c,d)). To avoid this, the fingerprint would have to include not only the remainder, but the number of bits involved in creating the fingerprint. Then fingerprinting a fingerprint would require time logarithmic in this number of bits. Carl Witty
I am zero training in cryptography, but I would think that if in addition to FP(as ++ bs) = FP(bs) `plusFPFlipped` FP(as) (I think the flipped plusFP def is more intuitive) there also existed a minusFP for all f and x such that FP(bs) = FP(as ++ bs) `minusFP` FP(as) then that might facilitate common subexpression refactorization in the merging of two hashes of memoized expressions. One example of such an minusFP (not recommended) is (foldr xor 0): That xor is its own inverse is no advantage. But xor is associative and (xor 0) is an identity, so FP([] ++ as) = FP(as ++ []) = FP(as) as expected. There must be more robust such monoidal functors out there. Refactorization could be limited to respect substructure boundaries reflected in the serialization. Dan Weston Simon Peyton-Jones wrote:
Interesting! The associativity property is the kind of thing I was after. Except that I don't really care if FP(as ++ bs) = FP(as) `plusFP` FP(bs). I only care that the latter is robust in the sense of having low probabilty of collision. So the Rabin scheme does more than I really need (which is probably fine).
On page 1 he draws a distinction between fingerprinting and hashing, which relates to my last wish. Does one need a different technique for the two, or is it enough to reduce the number of bits in the Rabin scheme, and thereby get a hashing scheme?
Strangely the paper gives no comparison with other fingerprinting schemes.
Simon
| -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Lauri Alanko | Sent: 11 October 2007 11:27 | To: haskell | Subject: Re: [Haskell] Fingerprints and hashing | | If compositionality is important, at least Rabin's fingerprints are | worth considering: http://citeseer.ist.psu.edu/broder93some.html | | They have the neat property that the fingerprint of a concatenation of | strings can be cheaply computed from the fingerprints of the | constituents. I think this effectively means that the plusFP operation | can be made associative, which might offer optimization opportunities. | | I remember implementing it some seven years ago when prototyping for a | C implementation. The code is lost, though. I can give it a shot | again, if this is considered a reasonable algorithm. | | | Lauri | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
One example of such an minusFP (not recommended) is (foldr xor 0):
Obviously I meant that FP = foldr xor 0. minusFP would be a simple unfolding of this. Dan Weston wrote:
I am zero training in cryptography, but I would think that if in addition to
FP(as ++ bs) = FP(bs) `plusFPFlipped` FP(as)
(I think the flipped plusFP def is more intuitive)
there also existed a minusFP for all f and x such that
FP(bs) = FP(as ++ bs) `minusFP` FP(as)
then that might facilitate common subexpression refactorization in the merging of two hashes of memoized expressions.
One example of such an minusFP (not recommended) is (foldr xor 0):
That xor is its own inverse is no advantage. But xor is associative and (xor 0) is an identity, so FP([] ++ as) = FP(as ++ []) = FP(as) as expected. There must be more robust such monoidal functors out there.
Refactorization could be limited to respect substructure boundaries reflected in the serialization.
Dan Weston
Simon Peyton-Jones wrote:
Interesting! The associativity property is the kind of thing I was after. Except that I don't really care if FP(as ++ bs) = FP(as) `plusFP` FP(bs). I only care that the latter is robust in the sense of having low probabilty of collision. So the Rabin scheme does more than I really need (which is probably fine).
On page 1 he draws a distinction between fingerprinting and hashing, which relates to my last wish. Does one need a different technique for the two, or is it enough to reduce the number of bits in the Rabin scheme, and thereby get a hashing scheme?
Strangely the paper gives no comparison with other fingerprinting schemes.
Simon
| -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Lauri Alanko | Sent: 11 October 2007 11:27 | To: haskell | Subject: Re: [Haskell] Fingerprints and hashing | | If compositionality is important, at least Rabin's fingerprints are | worth considering: http://citeseer.ist.psu.edu/broder93some.html | | They have the neat property that the fingerprint of a concatenation of | strings can be cheaply computed from the fingerprints of the | constituents. I think this effectively means that the plusFP operation | can be made associative, which might offer optimization opportunities. | | I remember implementing it some seven years ago when prototyping for a | C implementation. The code is lost, though. I can give it a shot | again, if this is considered a reasonable algorithm. | | | Lauri | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Simon Peyton-Jones wrote:
For various applications (including identifying common sub-expressions, and version tracking in GHC), I'd like a Haskell library that supports simple fingerprint operations.
Note that for CSE and hash-consing, there is a no-collision yet very efficient way of fingerprinting (with a drawback, of course :). The starting point is the question "why does cryptographic hashing work"? I mean, uniquely serializing (gödel numbering) a tree like newtype Exp = Exp (ExpF Exp) data ExpF a = Zero | One | Add a a | Mult a a deriving (Functor, Foldable, Traversable) takes an amount of bits proportional to its size (number of constructors). So, how can we expect a simple 128-bit number to have only few collisions for a collection of medium-sized trees? The answer is that the collection is much too small, no computer will ever be able to count (or construct said trees) from 1 to 2^128 in eons. So, the idea is to use a "local gödel numbering" and uniquely number the and only the trees that are actually constructed (no collisions, but few in numbers). In other words, every new tree created gets the gödel number size collection + 1 and we can simply use type GödelNumber = Word32 assuming that no more than 4G of trees will ever be constructed. For fast hash-consing, the collection itself is a (generalized) trie type Collection = ExpF GödelNumber ~~> Maybe GödelNumber mapping each new top of a tree (constructor + gödel numbers for already known subtrees) to either Just its gödel number or Nothing when it's not in the collection yet. With this, CSE becomes a catamorphism that allocates new gödel numbers if necessary type StateC a = Collection -> (Collection, a) deriving (Monad) cse :: Exp -> StateC GödelNumber cse = cata hashCons hashCons :: ExpF (StateC GödelNumber) -> StateC GödelNumber hashCons x0 = \c0 -> let (c,x) = sequence x0 c0 in case lookup x c of Maybe g -> (c,g) Nothing -> let g = size c + 1; c' = insert x g c in (c',g) where sequence :: ExpF (StateC GödelNumber) -> StateC (ExpF GödelNumber) sequence = Data.Traversable.sequence CSE in the sense that all common subexpressions now have the same gödel number. Of course, the drawback compared to "free-form" fingerprinting is that the fingerprinting and the collection now depend on each other. But for CSE, we have to carry the collection around anyway. I don't know any references for that method since I came up with it myself and haven't searched around yet. Any pointers? Regards, apfelmus
On Oct 11, 2007, at 4:33 PM, apfelmus wrote: ...
So, the idea is to use a "local gödel numbering" and uniquely number the and only the trees that are actually constructed (no collisions, but few in numbers). In other words, every new tree created gets the gödel number size collection + 1 and we can simply use
type GödelNumber = Word32
assuming that no more than 4G of trees will ever be constructed. For fast hash-consing, the collection itself is a (generalized) trie
type Collection = ExpF GödelNumber ~~> Maybe GödelNumber
mapping each new top of a tree (constructor + gödel numbers for already known subtrees) to either Just its gödel number or Nothing when it's not in the collection yet.
With this, CSE becomes a catamorphism that allocates new gödel numbers if necessary ... CSE in the sense that all common subexpressions now have the same gödel number.
Of course, the drawback compared to "free-form" fingerprinting is that the fingerprinting and the collection now depend on each other. But for CSE, we have to carry the collection around anyway.
I don't know any references for that method since I came up with it myself and haven't searched around yet. Any pointers?
Actually, the paper that Lauri cited in his message mentions essentially this technique; this is equivalent to the permutation T() that they impose when fingerprinting a DAG. That citation again: http://citeseer.ist.psu.edu/broder93some.html But it's generally pretty well known. -Jan
Simon Peyton Jones writes:
We are all familiar with the idea of an MD5 checksum, which provides a reliable "fingerprint" for a file, usually 128 bits or so...
For various applications (including identifying common sub-expressions, and version tracking in GHC), I'd like a Haskell library that supports simple fingerprint operations...
Below I give an informal specification of such a library. I can think of any number of implementations, but I'd like one that is (a) robust and (b) efficient. By "robust" I meant that with, say, a 128-bit fingerprint the chance of accidental collision is truly low; a non-robust implementation uses the 128-bit space in a non-uniform way [trivial example: gets stuck on zero]...
The module signature would be something like this:
data Fingerprint initialPrint :: Fingerprint
class Fingerprintable t where fingerPrint :: t -> Fingerprint -> FingerPrint
instance Fingerprintable Char instance Fingerprintable Int instance Fingerprintable Word32 -- etc
The fingerPrint operation here is expressed in the traditional way: an accumulator (say 128 bits) into which one stuffs successive values (e.g. a byte stream).
However, very important, I also want a more compositional form:
instance Fingerprintable Fingerprint
so that I can do something like
fp :: Expr -> Fingerprint fp (App e1 e2) = fp e1 `fingerPrint` fp e2
[For Salil anad Michael: apply the fingerPrint function to a fingerprint]
An obvious implementation of "instance Fingerprintable Fingerprint" is to divide one fingerprint into words, and feed it into the other via the Word32 instance. But it's not clear to me whether or not that is robust...
I'd like one other thing: to be able to trade cost for accuracy. I'd like a 128-bit fingerprint with essentially zero chance of having two distinct values that map to the same fingerprint; and a one-word fingerprint that was a lot more efficient, but where collisions would be entirely possible (again hash-consing is an example).
Simon, If I wanted this functionality, I'd call in the professionals (like Salil Vadhan, Michael Rabin, and Andrei Broder, whom I have cc'ed on this message). You sent this mail to the Haskell list, but I think the Haskell content of this problem is trivial compared to the algorithmic problems you pose. I remember, for example, a problem in the distant past of SRC Modula-3, where fingerprinting did not behave as expected because the source of the fingerprint module was itself fingerprinted. Here are some algorithmic references: http://tinyurl.com/yoeusg, http://tinyurl.com/2a2yfj - Modula-3 code for compositional 64-bit fingerprints, polynomial chosen by (literally) flipping a coin http://citeseer.ist.psu.edu/broder93some.html - Andrei's paper on applications of fingerprinting How does laziness play into this problem? If you don't mind building up a lot of thunks, you can probably just use several fingerprinting algorithms in parallel and then pull just the one you need... Norman
participants (9)
-
apfelmus -
Bryan O'Sullivan -
Carl Witty -
Dan Weston -
Jan-Willem Maessen -
Lauri Alanko -
Neil Mitchell -
Norman Ramsey -
Simon Peyton-Jones