Comment by 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.