[0xEA]

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.

[agwa]

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.

[cespare]

But the NaCl key is randomly generated for each connection.