Rabin fingerprint

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Rabin fingerprinting scheme is a method for implementing fingerprints using polynomials over a finite field. It was proposed by Michael O. Rabin.[1]

Scheme[edit]

Given an n-bit message m0,...,mn-1, we view it as a polynomial of degree n-1 over the finite field GF(2).

 f(x) = m_0 + m_1 x + \ldots + m_{n-1} x^{n-1}

We then pick a random irreducible polynomial p(x) of degree k over GF(2), and we define the fingerprint of m to be the remainder r(x) after division of f(x) by p(x) over GF(2) which can be viewed as a polynomial of degree k-1 or as a k-bit number.

Applications[edit]

The Low Bandwidth Network Filesystem (LBFS) from MIT uses Rabin fingerprints to implement variable size shift-resistant blocks. [2] The basic idea is that the filesystem computes the cryptographic hash of each block in a file. To save on transfers between the client and server, they compare their checksums and only transfer blocks whose checksums differ. But one problem with this scheme is that a single insertion at the beginning of the file will cause every checksum to change if fixed-sized (e.g. 4 KB) blocks are used. So the idea is to select blocks not based on a specific offset but rather by some property of the block contents. LBFS does this by sliding a 48 byte window over the file and computing the Rabin fingerprint of each window. When the low 13 bits of the fingerprint are zero LBFS calls those 48 bytes a breakpoint and ends the current block and begins a new one. Since the output of Rabin fingerprints are pseudo-random the probability of any given 48 bytes being a breakpoint is 2^{-13}. This has the effect of shift-resistant variable size blocks. Any hash function could be used to divide a long file into blocks (as long as a cryptographic hash function is then used to find the checksum of each block): but the Rabin fingerprint is an efficient rolling hash, since the computation of the Rabin fingerprint of region B can reuse some of the computation of the Rabin fingerprint of region A when regions A and B overlap.

Note that this is a problem similar to that faced by rsync.

See also[edit]

References[edit]

  1. ^ Michael O. Rabin (1981). Fingerprinting by Random Polynomials (PDF). Center for Research in Computing Technology, Harvard University. Tech Report TR-CSE-03-01. Retrieved 2007-03-22. 
  2. ^ Athicha Muthitacharoen, Benjie Chen, and David Mazières "A Low-bandwidth Network File System"

External links[edit]