<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, May 28, 2014 at 12:01 PM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

No, I'm just pointing out that the bitmap needs to be sized for MAX<br>
number of messages (2^20 ?), whereas a list of received MACs only<br>
needs to store the ACTUAL number of messages, so whether (MAX * 1 bit)<br>
will be a space savings vs (ACTUAL * 64 bits) is not totally clear to<br>
me (but maybe you can compress the bitmask if sparse?).</blockquote><div><br></div><div>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. Assume lg(N)=20, you get a [L/lg(N)] = 5x space savings right off the bat for p close to 0. Eventually it becomes L/2 = 50x savings when p=0.5, and then as p approaches 1 it becomes [L/lg(N)] = 5x again (because eventually you store just the serial numbers or MACs of unredeemed tokens). You can vary the savings gradually in between the two using compressed bitmap techniques.</div>

<div><br></div><div>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. Also the nice thing is you get to 50x savings at the point where the most storage is required when storing full MACs, so the max storage in this scheme at any point is a full 50x less, and that's regardless of your choice of N.</div>

<div><br></div></div></div></div>