nacl says that for security each nonce/key pair must be unique for each message. If you send a "HELO" message, for example first, you've made it possible to build a pretty simple rainbow table if nonce just starts at 0 or 1. That said, it would seem that the first nonce being random and then incremented would likely work well.
A rainbow table? The key space is 2^256. If you're talking about building a table containing the ciphertext of "HELO" with all possible keys, that's totally infeasible. As you correctly state, NaCl requires each nonce/key pair to be unique. If you start the nonce at 0 for a given key and increment it for each message, as is commonly done, that satisfies the requirement and is secure.
- Any rough benchmarks vs. TLS? Or even just back-of-the-envelope math/reasoning behind the claim in the opening paragraph: "without the overhead of TLS".
- Instead of generating 24 PRNG bytes for each message to use as the NaCl nonce, why not use the sequence number each message is assigned anyway?