Introduction encoding

[jazzz]

Problem

Keys required to initiate an Inbox handshake need to be encoded need to be bundled for easy distribution. The bundle is distributed out-of-band so the introduction has UX implications.

Data required to be transferred.

• Installation PublicKey
• Ephemeral PublicKey
• Signature

[jazzz]

Code Ref: https://github.com/logos-messaging/libchat/blob/main/conversations/src/inbox/introduction.rs

[osmaczko]

Let's agree on high-level requirements first.

1. Transport & Representation

   1. The Introduction Bundle MUST be representable as plain text.
   2. The textual representation MUST use a well-defined, unambiguous encoding suitable for arbitrary transport channels (e.g., chat systems, social media, copy-paste, offline transfer).
   3. The textual encoding MUST be space-efficient and SHOULD use a high-density binary-to-text encoding.
   4. The encoding SHOULD be URL-safe and copy-paste safe.
   5. The encoding SHOULD tolerate line wrapping and reflow commonly performed by chat applications.

2. Encoding Properties

   1. Encoding overhead (metadata and framing) MUST NOT exceed approximately 5–10% of the mandatory cryptographic material.
   2. The encoding MAY be binary internally and transformed into text via a deterministic binary-to-text encoding.
   3. The encoding MAY be canonical, but canonicalization MUST NOT be strictly required for correctness.

3. Longevity & Interoperability

   1. The Introduction Bundle MUST be decodable and verifiable by implementations written independently.
   2. The format MUST support forward evolution without breaking existing implementations unnecessarily.

4. Versioning

   1. The Introduction Bundle MUST be explicitly versioned.
   2. The versioning scheme SHOULD support semantic evolution, including the ability to introduce breaking changes intentionally.
   3. Unsupported versions MUST result in rejection.

5. Cryptographic Agility

   1. The Introduction Bundle MUST be self-describing with respect to cryptographic primitives.
   2. The format MUST support changes to key agreement schemes, signature algorithms, and key formats without requiring a redesign of the encoding.
   3. The introduction of new cryptographic algorithms, schemes, or key formats MUST be additive.

6. Verification Semantics

   1. The Introduction Bundle MUST allow a receiver to verify that it was generated by the holder of a specific identity key.

7. Implementation Practicality

   1. The format MUST be straightforward to implement in common systems programming and application languages (including Nim, C++, Rust, Go, JS/TS).
   2. The format SHOULD rely on widely available, well-maintained libraries where possible.
   3. The format MUST NOT require bespoke parsing rules that are difficult to implement consistently across languages.

8. Security Posture

   1. The Introduction Bundle MUST fail closed: malformed, unsupported, or unverifiable bundles MUST be rejected.
   2. The format SHOULD allow future security requirements to be enforced via explicit versioning rather than implicit interpretation changes.

9. Non-Goals

   1. The Introduction Bundle is NOT REQUIRED to be optimized for manual entry.
   2. The Introduction Bundle is NOT REQUIRED to be human-readable.
   3. The Introduction Bundle is NOT REQUIRED to maintain byte-level stability across semantically identical encodings.

[osmaczko]

Binary Encoding Comparison

Criteria	TLV (Custom)	Protobuf	CBOR
Efficient transport	🟢 Excellent. Minimal overhead; tags and lengths only. Size-optimal if carefully designed.	Very good. Compact varint tags and lengths; small overhead relative to payload.	Very good. Compact binary representation; slightly higher overhead than TLV in some cases.
Schema evolution (forward & backward compatibility)	Manual. Fully possible but must be designed and enforced by the spec and implementations.	🟢 Excellent. Built-in forward/backward compatibility via field numbers and unknown-field handling.	Good. Natural support via maps/arrays, but compatibility rules are convention-based rather than enforced.
Canonicality & signing semantics	Explicit. Canonicality and signing rules must be fully specified, but can be made unambiguous.	Non-canonical by default. Requires explicit rules (or exact-bytes signing) to avoid ambiguity.	🟢 Strong. Deterministic CBOR provides built-in canonical encoding suitable for signing.
Implementation cost	High. Custom parsing, validation, and evolution rules in every language; higher risk of subtle bugs.	🟢 Low. Code generation, stable APIs, and well-understood semantics across languages.	Medium. Libraries exist, but deterministic mode and conventions add complexity.
Tooling & ecosystem maturity	Low. No standard tooling; debugging and evolution are manual.	🟢 Excellent. Mature, widely used tooling, codegen, linters, and long-term support.	Medium. Good library availability, but ecosystem is less uniform and less familiar to many developers.

[osmaczko]

Proposal.

Text form:

logos_ib_<major>_<base64url_no_pad(protobuf(SignedIntroBundle))>

• logos_ib stands for logos identity bundle.
• major is the format major version (start with 1), bumped with breaking-change.
• base64url_no_pad variant is Base64url without padding.

Protobuf definitions (v1):

// Identity public key.
message IdentityKey {
  // Identity public key type/format identifier.
  // Example: 1 = secp256k1 compressed, 2 = Ed25519
  uint32 id = 1;

  // Raw public key bytes, encoded according to id.
  bytes public_key = 2;
}

// Ephemeral public key for key agreement (X3DH), scheme-identified.
message EphemeralKey {
  // Key agreement scheme identifier (complete scheme, not just curve).
  // Example: 1 = ECDH-secp256k1, 2 = X25519
  uint32 id = 1;

  // Raw public key bytes, encoded according to id.
  bytes public_key = 2;
}

// The signed payload (as bytes in SignedIntroBundle).
message IntroPayload {
  // Payload major version. For ib1_: MUST be 1.
  uint32 version = 1;

  // Device identity key.
  IdentityKey installation = 2;

  // One or more ephemerals in sender preference order (for migration).
  repeated EphemeralKey ephemerals = 3;
}

message Signature {
  // Signature algorithm identifier.
  // Example: 1 = ECDSA-secp256k1-SHA256, 2 = Ed25519
  uint32 id = 1;

  // Raw signature bytes, encoded according to id.
  bytes sig = 2;
}

// Single transferable object.
message SignedIntroBundle {
  // EXACT bytes that are signed.
  // MUST be protobuf binary encoding of IntroPayload.
  bytes payload = 1;

  // Signature over ("intro-bundle/ib1\0" || payload).
  Signature signature = 2;
}

[osmaczko]

Further iteration on requirements, mainly driven by the decision that the protocol prefers breaking changes rather than smooth transitions. As a consequence:

• Cryptographic agility is not required. If the key agreement scheme changes, the major version is bumped.
• The binary encoding type is not fixed and may change entirely between versions. For version V1, deterministic encoding is not required, since the introduction bundle is expected to be generated ad-hoc and used only once.
• Verification semantics do not need to be part of the encoding requirements. Verification is defined by the protocol itself, and the encoding remains agnostic to how verification is performed.

Iterated and FURP-ified requirements:

F1. The Introduction Bundle uses a well-defined, unambiguous encoding suitable for arbitrary transport channels.
F2. The Introduction Bundle contains an explicit version identifier.
F3. Implementations can decode Introduction Bundles produced by independent implementations conforming to the same version.

U1. The Introduction Bundle can be safely transmitted through common communication channels such as messaging platforms, social media, copy-paste workflows, and offline transfer.
U2. The Introduction Bundle does not require human readability.

R1. The Introduction Bundle encoding produces deterministic decoding results within the same version.

P1. The Introduction Bundle encoding is space-efficient relative to the encoded payload.

S1. The encoding supports intentional breaking changes between versions.
S2. The encoding should be easy for developers to extend and modify to support rapid iteration.

[osmaczko]

Given the above, the proposed introduction bundle encoding format is as follows:

logos_<namespace>_<version>_<binary-to-text-encoding(binary-payload)>

For V1:

• namespace = chat_intro
• version = 1
• binary-to-text-encoding = base64url_no_pad
• binary-payload = protobuf(IntroBundle)

IntroBundle.proto

message IntroBundle {
  bytes installation_pubkey = 1;
  bytes ephemeral_pubkey    = 2;
  bytes signature           = 3;
}

[jazzz]

logos_<binary-to-text-encoding(binary-payload)>
namespace = chat_intro

I would avoid using delimiters in the namespace. This becomes 'logos_chat_intro_1` which makes it harder/ambiguous to parse.