Although lot of people (including me) have mentioned Digital Stamps, or remailer postage, when describing advanced remailers, I've yet to see a good description of a practical remailer postage mechanism. I assume it will be (or has been) modeled after one of the Chaumian digital cash protocols. If there has been work done on a remailer postage mechanism, could somebody post the details? (or a reference) Here's what I think would make up a practical remailer postage mechanism: I think that each remailer should issue its own stamps, rather than using a central digital postage service. The existence of a centralize digital postage service creates a single point of failure for the entire remailer system. It also complicates the protocol needed to validate digital stamps and check for double spending. Of course, having each remailer issue its own stamps would increase the complexity for the users of the remailer system. However, I believe the increased user-side complexity can be completely hidden within a good set of scripts (e.g. the scripts could maintain a subdirectory for each remailer to hold stamps for that remailer). If all digital stamps have the same "denomination", then the protocol for obtaining stamps can be greatly simplified. You wont need to engage in a cut-and-choose protocol with the remailer (see page 121, Digital Cash Protocol #4, Applied Cryptography). To obtain 100 stamps from R1, Bob would generate and blind 100 uniqueness strings (random numbers large enough that they are unlikely to collide with anyone else's) and send them all to R1. R1 would simply sign all 100 of them and send them back. Bob would unblind them and store them in his "R1_stamps" subdirectory. Given the low value of individual stamps, it is probably not necessary to try to determine who is attempting to double spend stamps. Therefore, stamps wouldn't need the identity strings used in Digital Cash Protocol #4. Also, since the remailer is both "bank" and "merchant", there's no chance of the "merchant" cheating the "bank". ... When Bob wants to route a message through R1, he place an R1 stamp at the appropriate level within the nested envelopes. These stamps can also be used in SASE's. When R1 receives a stamped message (or SASE) it will check the signature of the stamp. If the signature doesn't verify, R1 discards the message. If the signature verifies, R1 checks the uniqueness string against his archive of "used" stamps. If the uniqueness string is present in the archive, the stamp has already been used and the message will be discarded. If the uniqueness string is not present in the archive, R1 will route the message on to the next hop. Finally, R1 places the uniqueness string in his "used stamp" archive. Seems simple enough. The major sticking point (to me) is the remailer's "used stamp" archive. This could grow to be very large. Something needs to be done to keep the archive from getting too large. One idea is to have the remailer periodically change the key it uses to sign stamps. Changing the "stamp validation key" effectively invalidates all unused stamps signed by that key. If you haven't used the stamp by that time, you're out of luck. The remailer can purge its "used stamp" archive whenever it changes its "stamp validation key". Of course, invalidating peoples' unused stamps out from under them is not a nice thing for a remailer to do. The remailer could provide a mechanism whereby people could get new stamps from old, unused stamps. To make this work, the remailer would have to retain the previous "used stamp" archive for a while to give people a chance to get new stamps. However, there still needs to be a limit on how long the remailer retains the "used stamp" archives for old validation keys. If you wait too long, you would lose any chance to get new stamps from old. Comments welcome. Jim_Miller@suite.com