Converge

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

Nodes may be either mutable or immutable, have their content encrypted or unencrypted, and may have their link fetch capabilities encrypted or unencrypted. This yields eight types of nodes for each collection of cryptographic primitives. The read and write capabilities on nodes are always encrypted while the parent fetch capabilities on mutable nodes are always unencrypted.

Blobs

The outer layer of blobs consists of an encrypted inner layer and the set of fetch capabilities.

struct Blob {
  inner: Ciphertext<Inner>,
  links: BtreeSet<FetchCap>,
}

Blob Encoding

Blobs are encoded with atlv, as an array of the inner ciphertext and the set of fetch capabilities. The set of fetch capabilities are also encoded as an array in ascending order.

Blob: 2[*"", FetchCaps]
FetchCaps: *[FetchCap]{asc}

Blob Hashing

The fetch capabilities for blobs are generated in two stages:

1. hash the encoded ciphertext and the links separately.
   • the ciphertext (including the tag with the length) uses the domain converge blob ciphertext generation {n}
   • the links (including the tag with the quantity) uses the domain converge blob links generation {n}
2. hash the concatenation of those hashes together with the domain converge blob fetch capability generation {n}.

In all three cases {n} is the shortest decimal representation of the generation.

Verification of a blob fetch capability is done by generating a fetch capability of the same generation and comparing them.

Blob Summaries

Blob summaries are a verifiable record of the public accessible metadata of a blob, without the data.

struct BlobSummary {
  inner: Hash<Ciphertext<Inner>>,
  links: BtreeSet<FetchCap>,
}

They may be verified in the same manner as blobs, but the ciphertext hash is already computed.

Versions

Versions are almost identical to blobs, with the addition of a list of version fetch capabilities in the outer layer, which indicate the direct parents of this version.

struct Version {
  inner: Ciphertext<Inner>,
  links: BtreeSet<FetchCap>,
  parents: Vec<VersionFetchCap>,
}

The parents need not be of the same braid.

Version Encoding

Version are encoded with atlv, the same as blobs but with the added unsorted array of parent version fetch capabilities at the end.

Version: 3[*"", FetchCaps, Parents]
Parents: *[VersionFetchCap]

Version Signing

The fetch capabilities for versions are generated in two stages:

1. hash the encoded ciphertext, links, and parents separately.
   • the ciphertext (including the tag with the length) uses the domain converge version ciphertext generation {n}
   • the links (including the tag with the quantity) uses the domain converge version links generation {n}
   • the parents (including the tag with the quantity) uses the domain converge version parents generation {n}
2. sign the concatenation of those hashes with the domain converge version fetch capability generation {n}, using the write capability.

In all four cases {n} is the shortest decimal representation of the generation.

Verification of a version fetch capability is done by changing step 2 from sign to verify, using the braid fetch capability, and supplying the current fetch capability.

Version Summaries

Version summaries are a verifiable record of the public accessible metadata of a version, without the data.

struct VersionSummary {
  inner: Hash<Ciphertext<Inner>>,
  links: BtreeSet<FetchCap>,
  parents: Vec<VersionFetchCap>,
}

They may be verified in the same manner versions, but the inner hash is already computed.

Common

The inner layer of both blobs and version, within the encrypted payload, contains the user data and the rest of the capabilities. The read and write capabilities match the order and number of the fetch capabilities.

struct Inner {
  data: Bytes,
  reads: Vec<RawReadCap>,
  writes: Ciphertext<Vec<SomeWriteCap>>,
}

The options for write capabilities are that there is not, a raw one, and that the write capability matches the write capability used to when creating the node. The list of write capabilities are encrypted using the write capability provided during creation. Both the raw read capability nor the raw write capability inherit their generation from the fetch capability they are associated with.

enum SomeWriteCap {
  Absent,
  Inherit,
  Literal(RawWriteCap),
}

Inherited write capabilities are typically used with blobs, but may also be used with versions any time the write capability is the same as the one provided to create it.

Common Encoding

The inner layer is encoded as a series of values, the binary data followed by the read capabilities, with no array wrapper, followed by the ciphertext of the write capability. The read capabilities are the appropriately sized binaries.

Inner: *"" || n(RawReadCap) || Ciphertext<WriteCaps> || …
RawReadCap: *""

Within the write-access-only ciphertext, the write capabilities are encoded as a series of tagged unions, without an array wrapper.

WriteCaps: n(SomeWriteCap) || …
SomeWriteCap: 0#Absent | 1#Inherit | 2#RawWriteCap
Absent: ""
Inherit: ""
RawWriteCap: *""

Additional atlv values may be added following the actual contents of the ciphertexts, in particular for disguising the length of the user data. The recommended padding is one or two binary values containing all zeros. These values must be valid, but must not be validated during parsing.

Common Encryption

Encrypting a node starts with the write capabilities. If no write capabilities are included, the ciphertext is an empty string. Otherwise, a key is derived from the supplied write capability and the encoded list of capabilities is encrypted with the associated data being the encoded user data, the encoded list of read capabilities, the encoded list of fetch capabilities, and (in the case of a version) the encoded list of parents.

In even generations, no more encryption is preformed. But in odd generations, the user data, read capabilities, encrypted write capabilities, and any padding are then encrypted with the associated data of the encoded list of fetch capabilities, and (in the case of a version) the encoded list of parents. For blobs this uses the encrypt_convergent method of the encryption scheme, for versions the read capability is supplied and just the encrypt method is used.

Finals

There is important information in finals that does not get exposed to the application. So while you can rearrange everything in blobs and versions and see the correspondence to the application’s view, for finals that is split between the application’s view of the final and the cryptography.

The first three fields represent the four fields that are exposed to the application, with two of them being encrypted into one. The last three fields form the basis for trusting that this final at all.

struct Final {
  next_braid: BraidFetchCap,
  next_caps: Ciphertext<NextCaps>,
  last_version: VersionFetchCap,
  last_commitment: Commitment,
  last_authority: PublicKey,
  last_signature: Signature,
}

struct NextCaps {
  read: Optional<RawReadCap>,
  write: Optional<SealedWriteCap>,
}

Final Encoding

Finals are encoded as an array of each piece. And the optional capabilities included are encoded without an array.

Final: 6[BraidFetchCap, *"", VersionFetchCap, Commitment, PublicKey, Signature]
NextCaps: Maybe<RawReadCap> || Maybe<SealedWriteCap>
Maybe<T>: 0#"" | 1#T

FinalContent: BraidFetchCap || *"" || VersionFetchCap || Commitment || PublicKey

Final Cryptography

The signature is made over the concatenation of the encoded form of the rest of the content, and is made with the authorizing public key. The commitment demonstrates that the authorizing public key was intentionally used in the creation of the original braid, and may be combined with that authorizing public key to generate it. See Committed Keys for details of how this works.

Cryptography

Converge supports multiple generations of cryptography. Generations 0 to 511 are allocated with even-numbered generations being unencrypted versions of the odd-numbered generations. Generations from 512 to 2111 are reserved for referencing other node exchange formats. The currently defined generations are:

Hashes

Converge uses pretty normal hash functions, augmented by a domain separator, while the inputs to the hash functions are not subject to length extension attacks, hash functions subject to such attacks should not be specified for use with converge.

class Hash h where
  -- | Hash an input.
  hash :: Domain -> Bytes -> h

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 first hashes the domain with normal blake3 hash, and uses that digest as the key for the blake3 keyed hash.

Signatures

Converge can use relatively normal signature algorithms, again augmented with a domain separator.

Converge requires both strong existential unforgeability of messages and signatures for a given public key and existential unforgeability of messages and public keys for a given signature! That is, you must not be able to create a new signature and message tuple that verify with a particular public key unless you have the secret key, and you must not be able to create a public key and message tuple that verify with a particular signature.

class Signature s where
  -- | Generate a secret key.
  derive_secret :: Domain -> KeyDerivationKey -> SecretKey s
  -- | Derive the public key from the secret key.
  derive_public :: SecretKey s -> PublicKey s
  -- | Sign a message with the secret key.
  sign :: SecretKey s -> Domain -> Bytes -> s
  -- | Verify a signature on a message with a public key.
  verify :: PublicKey s -> Domain -> s -> Bytes -> Bool

There are some additional requirements covered in Committed Keys.

schnorr-ristretto255-blake3

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

derive_secret uses the domain for the key-derivation mode of Blake3 to derive a 32-byte value from the key derivation key, and feeds that into the secret key from random bytes function of r255b3. derive_public, sign, and verify are all a standard part of r255b3.

Encryption

Converge uses a somewhat unusual form of encryption: deterministic authorized encryption with additional data. The hard requirement is that two programs on separate machines can reconcile a pair of changes in the same way and be able to issue the same update. Without deterministic encryption, that process is guaranteed to fail.

This necessarily means loosing indistinguishability under the extended chosen plaintext attack, because we want to be able to notice that two nodes are the same, just not learn anything else about them.

class Cipher k where
  -- | Derive a shared encryption key.
  derive_shared :: Domain -> Bytes -> k
  -- | Derive a convergent encryption key.
  derive_convergent :: Domain -> Bytes -> Assoc -> Plaintext -> k

  -- | Encrypt some plaintext (with some additional unencrypted data).
  encrypt :: Domain -> k -> Assoc -> Plaintext -> Ciphertext
  -- | Decrypt some ciphertext (with some additional unencrypted data).
  decrypt :: Domain -> k -> Assoc -> Ciphertext -> Maybe Plaintext

-- | Derive a convergent encryption key and encrypt.
encrypt_convergent
  :: Domain -> Bytes -> Assoc -> PlainText -> (k, Ciphertext)
encrypt_convergent domain context assoc plaintext = (key, ct) where
  key = derive_convergent domain context assoc plaintext
  ct = encrypt domain key assoc plaintext

encrypt_convergent is used for encrypting blobs.

chacha8-blake3-iv

chacha8-blake3-iv combines an 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 12-byte tag.

With further consideration this may revert to xchacha8-blake3-iv, which is the same thing but using the extended nonce ChaCha construction (and so a 192-bit tag/iv).

derive_shared uses the domain for the key-deriving mode of Blake3 to derive a 32-byte value from the key derivation key, and uses that as the key.

derive_convergent uses the domain for the key-deriving mode of blake3 to hash the associated data and plaintext, and then feeds the concatenation of those hashes followed by the convergence context into the key-deriving mode of blake3 with the domain chacha8-blake3-iv key.

encrypt uses the domain for the key-deriving mode of blake3 to hash the associated data and plaintext, and then feeds the concatenation of those hashes into the key-derivation mode of blake3 with the domain chacha8-blake3-iv nonce. the first 12 bytes of that is used as the initialization vector for chach8 encryption with the key.

decrypt decrypts the ciphertext using chacha8 with the key, then performs the same hash on the associated data and plaintext to derive the nonce. if the first 12 bytes of the hash match the iv, the plaintext is returned, otherwise an error is returned.

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

Committed Keys

Converge uses 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, we first generate a commitment key pair. Then derive a scalar from the public key and the verifying key that we wish to associate with this key. We use that scalar to transform our initial key pair into the one we wish to use.

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

schnorr-ristretto255-blake3

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.