On Thu, May 29, 2014 at 8:34 AM, Joseph Bonneau <[email protected]> wrote: > On Wed, May 28, 2014 at 12:01 PM, Trevor Perrin <[email protected]> wrote: >> >> No, I'm just pointing out that the bitmap needs to be sized for MAX >> number of messages (2^20 ?), whereas a list of received MACs only >> needs to store the ACTUAL number of messages, so whether (MAX * 1 bit) >> will be a space savings vs (ACTUAL * 64 bits) is not totally clear to >> me (but maybe you can compress the bitmask if sparse?). > > > The serial numbers don't need to be 64 bits, just lg(N) where N is the > number of tokens you can give out before a refresh. The space savings vary > with the percentage of tokens redeemed so far, call it p. The improvement > depends on the length of MAC you're comfortable with, call it L. [...] > > Seems like a worthwhile optimization though since you get 5x minimum > improvement and you can get more depending on how much implementation effort > you want to put into bitmaps.
Oh I see, with serial numbers the server could at a minimum also track them with a blacklist, which would be smaller than a blacklist of MACs due to birthday bound (though I'd expect closer to a 2x difference than 5x). That makes sense, seems like a good optimization. Trevor _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
