Online Review
Keep "replay window" of last K*N messages in binary tree or hash table.
As message rolls out of window, remove from tree/table.
Pull messages with desired hashes out when signature blocks are processed.
Process signature blocks in middle of replay window.
CAVEAT: I haven't implemented this….