Converge

Converge is the prototype exchange format for versioned node. It provides fully featured blobs and versions, including braid migration, in encrypted and unencrypted flavors. The encoding with atlv is compact and simple to parse and build. And the cryptography is arranged for compact and efficient implementations.

Capabilities

read capabilities in converge are symmetric encryption keys, write capabilities are secret keys for a signature algorithm. fetch capabilities for blobs are hash digests, signatures for versions, and public key for the signature algorithm for blobs.

Converge also introduces a few more capabilities in certain circumstances. The read-fetch capability is an encryption key derived from the read capability that is used to encrypt/decrypt the fetch capabilities on a node. The migrate capability is a signature scheme secret key that is used to sign a key-rotation certificate for a braid.

Capability Encoding

When encoded with atlv, individual capabilities are individually encoded with a tagged union (indicating the generation) containing a binary field with the key. For example, a plain fetch capability for a 1st generation blob would be encoded as:

union[1]      # generation 1
  binary[32]  # the blake3 hash
    64"9wuAnDJdrwO3ljnV6oZSPjH3cOAOzEoDzyIxrd2dXSM="

When necessary, these capabilities are wrapped in another tagged union to indicate their type. For instance, that same fetch capability, encoded in a context where it’s not known to be for a blob, would be:

union[0]        # fetch-blob capability
  union[1]      # generation 1
    binary[32]  # the blake3 hash
      64"9wuAnDJdrwO3ljnV6oZSPjH3cOAOzEoDzyIxrd2dXSM="

Each type of capability has an assigned tag:

Capability Sorting

Masked nodes store their fetch capabilities as sorted sets, to minimize leaked information. This requires ordering fetch capabilities from least to greatest.

The tag of the fetch capability is compared first, blobs less than versions less than braids, then the generations are compared, and finally the content of the hash digest, signature, or public keys. As all fetch capabilities of the same type and generation have the same length, this is equivalent to a lexicographical ordering of the atlv-encoded capabilities.

Blobs

There are a few different types of blobs, depending on the encryption requirements. Each type of blob is available for each set of encryption primitives.

Blob Cryptography

Blobs require two cryptographic constructions, a hash function family and a deterministic authenticated cipher.

Clear Blobs

Clear blobs do not encrypt their data or the identifies of the nodes they link to. While this renders them unsuitable for most applications, it might be required for others, such as early boot and some amateur radio networks¹.

Clear Blob Outer Structure

array[4]
  id: binary[]         # the fetch hash
  data: binary[]       # the plaintext data
  links_ct: binary[]   # the encrypted links
  fetchcaps: array[]   # the list of fetch capabilities
    union[0-2] union[] binary[]
    ...

The id field, which is the fetch capability for this blob, is a hash digest. It is a staged hash of the domain separator “Converge Clear Blob Fetch”, the concatenated data and links, and the concatenated generation and fetch capabilities. Each input except the domain is atlv-encoded.

stagedHash("Converge Clear Blob Fetch", data, links_ct, gen || fetchcaps);

The data and fetch capabilities are all unencrypted.

Clear Blob Inner Structure

The links ciphertext is convergently encrypted, using the atlv-encoded generation, data, and fetch capabilities as context.

encryptConvergent( "Converge Clear Blob", links
                 , hash(data) || hash (gen || fetchcaps)
                 , write_cap);

Inside the links ciphertext is another atlv-encoded structure.

readcaps: array[]
  binary[]           # the read key of a link
  ...
writecaps: binary[]  # the encrypted write keys

The read capability is formed from the raw key and the generation of the corresponding fetch capability. The ith entry goes with the ith fetch capability.

The write capabilities are stored within another layer of encryption. If no write capability was used while creating the blob, there can be no write capabilities, and the ciphertext is empty. If there are, the write capabilities are atlv-encoded and encrypted with a key derived from the supplied write capability, with the data, read capabilities, generation, and fetch capabilities as context.

encrypt( "Converge Clear Blob Write"
       , keyFromKey("Converge Clear Blob ReadWrite", write_cap)
       , writecaps, hash(data) || hash(readcaps) || hash (gen || fetchcaps) );

Write Capability Encoding

The encrypted write capabilities are encoded as a sequence of atlv values. The ith entry goes with the ith link in the next layer out.

• A zero-length binary means that there is no write capability.
• A zero-length array indicates the same write capability as the current blob.
• Otherwise, the raw write key matching the generation of the read and fetch capabilities is encoded as a greater-than-zero length binary.

Masked Blobs

Masked blobs encrypt the data of the node along with the links, and separately encrypt the fetch capabilities. This is the general purpose immutable node.

Masked Blob Outer Structure

array[3]
  id: binary[]            # the fetch hash
  body_ct: binary[]       # the encrypted data and links
  fetchcaps_ct: binary[]  # the encrypted fetch capabilities

The id field, which is the fetch capability for this blob, is a hash digest. It is a staged hash of the domain separator “Converge Masked Blob Fetch”, the body ciphertext, the concatenated generation and fetch capabilities ciphertext. Each input except the domain is atlv-encoded.

stagedHash("Converge Masked Blob Fetch", body_ct, gen || fetchcaps_ct);

Masked Blob Fetch Capabilities

The fetch capabilities are encrypted with the read-fetch capability, a key derived from the read capability (including the generation). with the generation as context. Inside that ciphertext the fetch capabilities are sorted least to greatest.

encrypt( "Converge Masked Blob Fetch"
       , keyFromKey("Converge Masked Blob ReadFetch", read_cap)
       , fetchcaps, hash(body_ct) || hash(gen));

Masked Blob Inner Structure

The body ciphertext is convergently encrypted, using the atlv-encoded generation, and unencrypted fetch capabilities as context.

encryptConvergent( "Converged Masked Blob", body
                 , hash(gen || fetchcaps)
                 , write_cap);

Inside the links ciphertext is another atlv-encoded structure.

data: binary[]           # the blob's data
links: array[]
  union[index] binary[]  # the index and read key of a link
  ...
writecaps: binary[]      # the encrypted write keys

The index of each link indicates which fetch capability from the top-level fetchcaps field to use. A single fetch capability may be referenced multiple times. The read capability is formed from the raw key and the generation of the indicated fetch capability.

The write capabilities are stored within another layer of encryption. If no write capability was used while creating the blob, there can be no write capabilities, and the ciphertext is empty. If there are, the write capabilities are atlv-encoded and encrypted with a key derived from the supplied write capability, with the data, links, generation, and fetch capabilities as context.

encrypt( "Converge Masked Blob Write"
       , keyFromKey("Converge Masked Blob ReadWrite", write_cap)
       , writecaps, hash(data || links) || hash(gen || fetchcaps) );

The encrypted write capabilities are encoded the same as clear blobs, as specified by Write Capability Encoding.

Blob Summaries

The fetch capability generation of clear and masked blobs are arranged such that a summary of their content can be stored with their (possibly encrypted) fetch capabilities.

array[3]
  fetchcap: union[gen] binary[]  # the generation and hash
  summary: binary[]              # the initial hash of the data and links
  fetchcaps: value               # the fetch capabilities

This structure can be verified by concatenating the summary with the hash of the concatenated gen and fetchcaps, and comparing the output to the fetchcap.

Versions

Like with blobs, there are a few different types of versions, depending on the encryption requirements. Each type of version is available for each set of encryption primitives.

Version Cryptography

Versions require a signature family and a deterministic authenticated cipher (but do not use convergent encryption).

Clear Versions

Clear versions do not encrypt their data or the identifies of the nodes they link to. While this renders them unsuitable for most applications, it might be required for others, such as early boot and some amateur radio networks.

Clear Versions Outer Structure

array[6]
  version: binary[]   # the fetch signature
  braid: binary[]     # the fetch public key
  data: binary[]      # the plaintext data
  links_ct: binary[]  # the encrypted links
  fetchcaps: array[]  # the list of fetch capabilities
    union[0-2] union[] binary[]
    ...
  parents: array[]    # the list of parent version fetch capabilities
    union[] binary[]
    ...

The version field, which is the fetch capability for this version, is a signature over the domain separator “Converge Clear Version Fetch”, the concatenated data and links, and the concatenated generation, fetch capabilities, and parents. Each input except the domain is atlv-encoded.

stagedSign( "Converge Clear Version Fetch", write_key
          , data || links_ct, fetchcaps, gen || parents);

The braid field, which is the fetch capability for the entire braid to which this version belongs, is the public key for the signature algorithm.

The data, fetch capabilities, and parent versions are all unencrypted.

Clear Version Inner Structure

The links ciphertext is encrypted with the read capability, using the atlv-encoded data, generation, fetch capabilities, and parents as context.

encrypt( "Converge Clear Version", read_key, links
       , hash(data) || hash(fetchcaps) || hash(gen || parents));

Inside the links ciphertext is another atlv-encoded structure.

readcaps: array[]
  binary[]               # the read key of a link
  ...
parentreadcaps: array[]  # the read keys for parent links
  (array[0] | binary[])
  ...
writecaps: binary[]      # the encrypted write keys

The read capability is formed from the raw key and the generation of the corresponding fetch capability. The ith entry goes with the ith fetch capability.

The parentreadcaps are stored using the same format as the write capabilities, but reference the read capability for this version rather than the write capability. That is, a zero-length array indicates that the linked parent uses the same read capability as this version.

The write capabilities are encrypted with a key derived from the write capability of the version, with the read capabilities, parent read capabilities, generation, fetch capabilities, and parent fetch capabilities as context.

encrypt( "Converge Clear Version Write"
       , keyFromKey("Converge Clear Version ReadWrite", write_cap)
       , writecaps, hash(data) || hash(readcaps || parentreadcaps)
                 || hash(fetchcaps) || hash(gen || parents));

The encrypted write capabilities are encoded the same as clear blobs, as specified by Write Capability Encoding.

Masked Versions

Masked versions encrypt the data of the node along with the links, and separately encrypt the fetch capabilities.

Masked Version Outer Structure

array[5]
  version: binary[]       # the fetch signature
  braid: binary[]         # the fetch public key
  body_ct: binary[]       # the encrypted data and links
  fetchcaps_ct: binary[]  # the encrypted fetch capabilities
  parents: array[]        # the list of parent version fetch capabilities
    union[] binary[]
    ...

The version field, which is the fetch capability for this version, is a signature over the domain separator “Converge Clear Version Fetch”, the body ciphertext, and the concatenated generation, fetch capabilities, and parents, with a final ratchet. Each input except the domain is atlv-encoded.

stagedSign( "Converge Masked Version Fetch", write_key
          , body_ct, fetchcaps_ct, gen || parents);

The braid field, which is the fetch capability for the entire braid to which this version belongs, is the public key for the signature algorithm.

Masked Version Fetch Capabilities

The fetch capabilities are encrypted with the read-fetch capability, a key derived from the read capability. with the generation and parent fetch capabilities as context. Inside that ciphertext they must be sorted least to greatest.

encrypt( "Converge Masked Version Fetch"
       , keyFromKey("Converge Masked Version ReadFetch", read_cap)
       , fetchcaps, hash(body_ct), hash(gen || parents));

Masked Version Inner Structure

The body ciphertext is encrypted with the read capability, using the atlv-encoded generation, fetch capabilities, and parents as context.

encrypt( "Converge Masked Version", read_key, body
       , hash(fetchcaps) || hash(gen || parents));

Inside the body ciphertext is another atlv-encoded structure.

data: binary[]           # the version's data
links: array[]
  union[index] binary[]  # the index and read key of a link
  ...
parentreadcaps: array[]  # the read keys for parent links
  (array[0] | binary[])
  ...
writecaps: binary[]      # the encrypted write keys

The index of each link indicates which fetch capability from the top-level fetchcaps field to use. A single fetch capability may be referenced multiple times. The read capability is formed from the raw key and the generation of the indicated fetch capability.

The parentreadcaps are stored using the same format as the write capabilities, but reference the read capability for this version rather than the write capability. That is, a zero-length array indicates that the linked parent uses the same read capability as this version.

The write capabilities are encrypted with a key derived from the supplied write capability, with the data, links, parent read capabilities, generation, fetch capabilities, and parent fetch capabilities as context.

encrypt( "Converge Masked Version Write"
       , keyFromKey("Converge Masked Version ReadWrite", write_cap)
       , writecaps, hash(data || links || parentreadcaps)
                 || hash(fetchcaps) || hash(gen || parents));

The encrypted write capabilities are encoded the same as clear blobs, as specified by Write Capability Encoding.

Version Summaries

The fetch capability generation of clear and masked versions are arranged such that a summary of their content can be stored with their (possibly encrypted) fetch capabilities and parents.

array[3]
  version: union[gen] binary[]  # the generation and signature
  braid: binary[]               # the public key
  summary: binary[]             # hash of the data and links
  fetchcaps: value              # the fetch capabilities
  parents: array[]              # the parent fetch capabilities
    union[] binary[]
    ...

This structure can be verified by concatenating the summary with the hash of the fetchcaps and hash of the concatenated gen, and parents, and then verifying the signature over that with the version and braid.

Finals

Finals enable key rotation. They allow the originator of a braid to mark a particular version as the last one, and indicate a successor braid to transition to. They may convey read capabilities to those that can currently read versions of the braid, but they can not convey write capabilities.

array[]
  version: union[gen0] binary[]    # the last valid version of the braid
  summary: binary[]                # the extract of the last valid version
  braid: union[gen1] binary[]      # the fetch cap for the new braid
  readcap_ct: binary[]             # an optional encrypted read cap
  commitment: binary[]             # any data needed to verify the authority
  authority: union[gen2] binary[]  # the public key of the authority
  signature: union[gen2] binary[]  # a signature of this data by the authority

As hinted above, the generations of the old braid, new braid, and signing key may all be different.

Finals don’t show up in versioned nodes directly, but are reflected in that a request for the most recent version of a braid might return a version from an entirely different braid, and a braid may suddenly become read-only.

The summary of the last version is extracted just before verifying, such that the final version can be verified as being part of the old braid by injecting the summary and immediately verifying it.

The public key for the braid can be reconstructed from the commitment and the authority. The typical way to do this is using committed keys, but future generations may specify their own method.

The read capability for the new braid is encrypted with the read capability for the current braid, using the final version, target braid, commitment, and authority as context.

encrypt( "Converge Final Read", old_read_key, optional_new_read_key
       , version || summary || braid || commitment || authority );

The signature on the final is generated using the private key corresponding to the public key listed on the final. It is on the concatenation of the final version, summary, new braid, and the read capability ciphertext.

stagedSign( "Converge Final", authority
          , version || summary || braid || readcap_ct);

Generations

There are currently two defined generations.

Further generations will be added when post-quantum signature schemes become settled, additional types are defined, or vernode storage formats other than converge are defined. Generations for other node storage formats will begin at 64, and allocate 64 generations to each format. The 65th block of generations (4096-4159) is reserved for private and experimental use.

Cryptography

Hash Function Family

Converge can use any cryptographic hash function with collision resistance. Hashes with resistance to length extension attacks are preferred, but not required, as every final field has a fixed length.

Hashes are used in two modes, with and without a domain separator. For hash functions that do not have a specification for domain separation, the domain separated mode should prefix the input with the hash of the domain, and the plain mode should prefix the input with an equivalent length of null bytes.

• hash(domain, buf) hashes the buffer in a specific domain
• hash(buf) hashes the buffer without a domain

In many cases, converge hashes a number of buffers in two stages. First hashing each buffer with no domain, and then hashing the concatenation of those hashes with a domain. This may be denoted by a varadic function, stagedHash(domain, buf0, buf1, ...), equivalent to hash(domain, hash(buf0) || hash(buf1) || hash(...)).

blake3

Blake3 is a well-known hash function that is very fast on a variety of hardware and not vulnerable to length extension attacks.

• hash(domain, buf) hashes using the key derivation mode.
• hash(buf) hashes with the normal mode.

Signature Family

A signature family is similar to a hash function family, but is a secret-public key signature scheme instead of a hash function.

The following operations are required:

• keyFromKey(domain, key_material) derives a secret key from some high-entropy key material.
• toPublic(secret_key) derives the public key from the secret key.
• sign(domain, secret_key, buf) sign a buffer with a secret key.
• verify(domain, public_key, signature, buf) verifies that the signature was produced with the secret key corresponding to this public key.

Like with hash functions, converge often hashes a number of buffers and then signed the concatenation of their hashes. This can be denoted as a varadic function, stagedSign(domain, secret_key, buf0, buf1, ...). The complimentary verification operation is similarly denoted with stagedVerify(domain, public_key, signature, buf0, buf1, ...).

The signature scheme is required to be entirely deterministic.

There are some additional requirements covered in Committed Keys.

r255b3

r255b3 is a traditional Schnorr signature scheme based on the Ristretto255 prime order group and the Blake3 hash function. It has a signature size of 48 bytes, and 32 byte secret and public keys.

Deterministic Authenticated Cipher

Deterministic authenticated cipher is an encryption scheme with some slightly unusual properties. In particular, it is fully deterministic, the same inputs always yield the same outputs. This is required for automated synchronization in a delay-tolerant environment, but technically prevents it from being secure against an adaptive chosen plaintext attack. Otherwise, it must meet the usual AEAD requirements with the addition of key commitment.

Converge requires four functions of these ciphers:

• keyFromPlaintext(domain, plaintext, context, convergence) derives a key unique to the domain and convergence domain from the plaintext and the associated data.
• keyFromKey(domain, key_material) derives a key from a fixed domain string and some other key material.
• encrypt(domain, key, plaintext, context) takes such a key, the plaintext, and the associated data, and produces a ciphertext,
• decrypt(domain, key, ciphertext, context) takes a key, the ciphertext, and the associated data, and returns the plaintext if the checks pass, and nothing otherwise.
• encryptConvergent(domain, plaintext, context, convergence) derives the key using keyFromPlaintext and then encrypts, returning both the created key and the ciphertext. Ciphers may specify an optimized version of this that, for example, encrypts in fewer passes than the general version.

xchacha8-blake3-iv

XChaCha8-Blake3-IV combines the extended-nonce 8-round variation of the IETF ChaCha20 with a truncated Blake3 digest as the IV to form a deterministic authenticated encryption with associated data scheme with a 24-byte tag.

keyFromPlaintext takes a blake3 hash function with the domain over the hashes of the plaintext and context followed by the string “Convergent Key for XChaCha8-Blake3-IV” and the convergence domain.

keyFromKey initializes a blake3 staged hash function with the domain, feeds in the provided key material, ratchets, feeds in the string “Derived Key for XChaCha8-Blake3-IV” and crunches.

encrypt takes a blake3 hash function with the domain over the hashes of the plaintext and context followed by the string “Nonce for XChaCha8-Blake3-IV” and the encryption key, takes the first 24 bytes, and uses that at the initialization vector for XChaCha8 encryption.

decrypt decrypts the ciphertext using XChaCha8 with the key, then performs the same hash on the plaintext and context to derive the nonce. if the first 24 bytes of the hash match the initialization vector, the plaintext is returned, otherwise an error is returned.

This allows for an optimized version of encryptConvergent that can derive the key and nonce in a single pass over the ciphertext.

Committed Keys

Converge can use specially constructed secret and public keys to commit them to a verifying key. This imposes some additional requirements on signatures. Namely, an additional type and a pair of operations that can irreversibly transform a valid secret-public key pair into another valid secret-public key pair, and a means to derive that scalar from a public key and a public key from some other signature scheme. The general scheme is committing to obsolescence.

class Committed s where
  derive_scalar :: Domain -> PublicKey s -> PublicKey c -> Scalar s
  scale_public :: Scalar s -> PublicKey s -> PublicKey s
  scale_secret :: Scalar s -> SecretKey s -> SecretKey s

To generate a key pair, first generate a commitment key pair. Then derive a scalar from the public half and the verifying key. Then use that scalar to scale the commitment key pair into the in-use key pair.

When it is time to migrate to a new key, release the commitment public key, and sign the final with the verifying key associated with it. Anyone who receives that final can then derive the public key for themselves (and verify the signature) to establish its authenticity.

r255b3

As r255b3 uses ristretto255 scalars as secret keys and ristretto255 points as public keys, the scalar type for committed keys is the same as the secret key. That is a ristretto255 scalar.

derive_scalar uses a blake3 key derivation hash with the domain to hash the serialization of the two public keys, and then reduces that to a scalar.

scale_public is scalar multiplication of the public key, while scale_secret is multiplication on ristretto255 scalars.