A Bloom or cuckoo filter would allow for efficient tracking of nonces (depending if the security model prefers false positives with 4xx/resend, or false negatives)