As Jim points out, Matthew's scheme for one-bit-per-stamp has the problem that it requires non-anonymous stamps. Jim suggested a variant on Chaum's digital cash where the stamp numbers would be re-blinded by the recipient so that the remailer would not recognize them (but could verify their validity). Matthew's bitmap idea could still be used, though. The incoming stamp numbers could be hashed down to, say, 24 bits. This could then be an index into a 2^24-bit file, which would take 2 MB. Set the bit when the stamp is used, and reject the mail if the bit is already set. Granted, this would create false rejections. But email is already not perfectly reliable. You could send 160,000 messages before you had as many as 1% false rejections (2^24 / 100). I think this would be better than trying to save this many digital stamps and check through the list each time for duplications. Hal