Hi! Author of this proposal here. I’m loving all the feedback and wanted to address some things: * Yes, nonce tracking is expensive. HTTP request signatures could be used instead of nonces—they’re just not fully fleshed out yet, from what I can tell. And a lot of other crypto systems we rely on in Web traffic today also assume proper nonce tracking. Fortunately you only need to track distinct nonces per established s…
The client can generate the next nonce by incrementing the previous nonce value.
The server only needs to remember the highest nonce it's ever seen, for a particular session, and reject any new nonces less than or equal to it. O(1) in time and space, and no need for anything clever like bloom filters.
Edit: One issue I can see with this approach would be, what if requests arrive (or are processed) out-of-order? You'd perhaps want to track a small window of nonces to account for this.