# 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:

- 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}`

- the ciphertext (including the tag with the length) uses the
domain
- 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:

- 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}`

- the ciphertext (including the tag with the length) uses the
domain
- 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:

Generations | Hash | Signature | Cipher |
---|---|---|---|

0 and 1 | blake3 | schnorr-ristretto255-blake3 | chacha8-blake3-iv |

## 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.