Generate locally unique nonces (number-only-used-once) in distributed Elixir.

Locally unique means that the nonces are unique within your application/database/domain, as opposed to globally unique nonces that are unique across applications/databases/domains, like UUIDs.

Nonce types

Several types of nonces can be generated, although they share their basic composition. The first 42 bits are a millisecond-precision timestamp (allows for ~139 years of operation), relative to the NoNoncense epoch (2025-01-01 00:00:00 UTC) by default. The next 9 bits are the machine ID (allows for 512 machines). The remaining bits are a per-machine counter.

Counter nonces

• Features: unique.
• Generation rate: very high.
• Info leak: medium (machine init time, creation order).
• Crypto: technically suitable for block ciphers in modes that require an IV that is unique but not necessarily unpredictable (like CTR, OFB, CCM, and GCM), and some streaming ciphers. Only when some info leak is acceptable.

Counter nonces are basically a counter that is initialized with the machine (node) start time. An overflow of a nonce's counter bits will trigger a timestamp increase by 1ms, implying that the timestamp effectively functions as an extended counter. Because the timestamp can't exceed the actual time (that would break the uniqueness guarantee), new nonce generation throttles if the timestamp catches up to the actual time.

That means that the maximum sustained rate is 8M/s per machine for 64-bits nonces (which have 13 counter bits). In practice it is unlikely that nonces are generated at such an extreme sustained rate, and the timestamp will lag behind the actual time. This creates "saved up seconds" that can be used to burst to even higher rates. For example, if the first nonce is generated 10 seconds after initialization, 10K milliseconds have been "saved up" to generate 80M nonces as quickly as hardware will allow. Benchmarking shows rates in the tens of millions per second are attainable this way.

96/128 bits counter nonces have such large counters that they can be generated at a practically unlimited sustained rate of >= 2^45 nonces per ms per machine, meaning they will never catch the actual time, and the practical rate is only limited by hardware.

Sortable nonces (Snowflake IDs)

• Features: unique, time-sortable.
• Generation rate: high.
• Info leak: high (creation time, creation order).
• Crypto: not recommended. They leak more info than counter nonces but are slightly slower to generate.

Sortable nonces have an accurate creation timestamp (as opposed to counter nonces). This makes them equivalent to Snowflake IDs, apart from the slightly altered bit distribution of NoNoncense nonces (42 instead of 41 timestamp bits, 9 instead of 10 ID bits, no unused bit).

This has some implications. Again, 96/128-bits sortable nonces can be generated as quickly as your hardware can go. However, the 64-bits variant can be generated at 8M/s per machine and can't ever burst beyond that (the "saved-up-seconds" mechanic of counter nonces does not apply here). This should of course be plenty for most applications.

Encrypted nonces

• Features: unique, unpredictable.
• Generation rate: medium (scales well with CPU cores).
• Info leak: none.
• Crypto: same as counter nonces, but no info leaks. Additionally, suitable for block cipher modes that require unpredictable IVs, like CBC and CFB.

These nonces are encrypted in a way that preserves their uniqueness, but they are unpredictable and don't leak information. For more info, see nonce encryption.

Usage

Note that NoNoncense is not a GenServer. Instead it stores its initial state using :persistent_term and its internal counter using :atomics. Because :persistent_term triggers a garbage collection cycle on writes, it is recommended to initialize your NoNoncense instance(s) at application start, when there is hardly any garbage to collect.

# lib/my_app/application.ex
# generate a machine ID, start conflict guard and initialize a NoNoncense instance
defmodule MyApp.Application do
  use Application

  def start(_type, _args) do
    machine_id = NoNoncense.MachineId.id!(node_list: [:"myapp@127.0.0.1"])
    :ok = NoNoncense.init(machine_id: machine_id)

    children =
      [
        # optional but recommended
        {NoNoncense.MachineId.ConflictGuard, [machine_id: machine_id]}
      ]

    opts = [strategy: :one_for_one, name: MyApp.Supervisor]
    Supervisor.start_link(children, opts)
  end
end

Then you can generate nonces.

# generate counter nonces
iex> <<_::64>> = NoNoncense.nonce(64)
iex> <<_::96>> = NoNoncense.nonce(96)
iex> <<_::128>> = NoNoncense.nonce(128)

# generate sortable nonces
iex> <<_::64>> = NoNoncense.sortable_nonce(64)
iex> <<_::96>> = NoNoncense.sortable_nonce(96)
iex> <<_::128>> = NoNoncense.sortable_nonce(128)

# generate encrypted nonces
# be sure to read the NoNoncense docs before using 64/96 bits encrypted nonces
iex> <<_::64>> = NoNoncense.encrypted_nonce(64, :crypto.strong_rand_bytes(24))
iex> <<_::96>> = NoNoncense.encrypted_nonce(96, :crypto.strong_rand_bytes(24))
iex> <<_::128>> = NoNoncense.encrypted_nonce(128, :crypto.strong_rand_bytes(32))

Uniqueness guarantees

Nonces are guaranteed to be unique if:

• Machine IDs are unique for each node (NoNoncense.MachineId and NoNoncense.MachineId.ConflictGuard can help there).
• Individual machines maintain a somewhat accurate clock (specifically, the UTC clock has to have progressed between node restarts).
• (Sortable nonces only) the machine clock has to be accurate.

Nonce encryption

By encrypting a nonce, the timestamp, machine ID and message ordering information leak can be prevented. However, we wish to encrypt in a way that maintains the uniqueness guarantee of the input counter nonce. So 2^64 unique inputs should generate 2^64 unique outputs, same for the other sizes.

IETF has some wisdom to share on the topic of nonce encryption (in the context of ChaCha20 / Poly1305 nonces):

Counters and LFSRs are both acceptable ways of generating unique nonces, as is encrypting a counter using a block cipher with a 64-bit block size such as DES. Note that it is not acceptable to use a truncation of a counter encrypted with block ciphers with 128-bit or 256-bit blocks, because such a truncation may repeat after a short time.

There are some interesting things to unpick there. Why can't we use higher ciphers with a larger block size? As it turns out, block ciphers only generate unique outputs for inputs of at least their block size (128 bits for most modern ciphers, notably AES). For example, encrypting a 64-bit nonce with AES would produce a unique 128-bit ciphertext, but that ciphertext can't be reduced back to 64 bits without losing the uniqueness property. Sadly, this also holds for the streaming modes of these ciphers, which still use blocks internally to generate the keystream. That means we can just use AES256 ECB (we only encrypt one block) for 128-bit nonces.

However, for 64-bit nonces we are limited to block ciphers with 64-bit block sizes. There are only a few of those in OTP's :crypto module, namely DES, 3DES, and BlowFish. DES is broken and can merely be considered obfuscation at this point, despite the IETF quote (from 2018). BlowFish performs atrociously in the OTP implementation (~30 times worse than AES, dropping from ~1.8M ops/s to 60K ops/s) to the point where it can realistically form a bottleneck. 3DES seems like the least worst option, and practical attacks on it are mainly aimed at block collisions (within a message) which doesn't apply here. Still, it's old.

For 96-bit nonces there are no block ciphers whatsoever to choose from. All we can do is generate a 64-bits nonce and postfix 4 zero-bytes. That way the nonce is unique, and while the last 4 bytes are predictable, the nonce as a whole is not and no message ordering information leaks.