Comprehensive Explanation

dual-indexed-codes

Technical Definition

Dual-indexed codes represent a specialized encoding mechanism within the CESR (Composable Event Streaming Representation) framework, specifically designed to address the common use case of thresholded multi-signature schemes. This compact coding approach provides an efficient method to associate each signature with its corresponding public key through embedded indexing, eliminating the need for separate mapping structures while maintaining CESR's composability properties.

Formal Definition

A dual-indexed code is a two-character text domain primitive in CESR that encodes both:

1. The signature type and encoding scheme (first character)
2. An integer index reference to a public key in an ordered set (second character)

This encoding scheme is optimized for signatures with a 64-byte raw binary size, which results in a pad size of 2, naturally accommodating the two-character text code structure required for efficient stream processing.

Purpose in KERI/ACDC

In KERI multi-signature scenarios, particularly those involving threshold signature schemes, multiple signatures from different keys may be required to authorize an establishment event or interaction event. The dual-indexed code provides an elegant solution for:

• Compact representation: Associates each signature with its corresponding public key without requiring full key material
• Ordered key sets: Enables efficient lookup by indexing into a pre-established ordered set of public keys
• Stream efficiency: Maintains CESR's streaming properties while carrying signature attribution metadata
• Verification optimization: Allows validators to quickly identify which public key corresponds to each signature

Cryptographic Properties

Underlying Signature Schemes

Dual-indexed codes are designed to work with popular signature formats that produce 64-byte raw binary signatures. This size characteristic is fundamental to the encoding scheme's efficiency. Common signature schemes that fit this profile include:

• Ed25519 signatures: 64-byte signatures from EdDSA using Curve25519
• ECDSA signatures: Certain elliptic curve signature formats
• Other 64-byte signature schemes: Any cryptographic signature producing 64 raw bytes

Security Properties

The dual-indexed code mechanism itself does not alter the cryptographic security properties of the underlying signatures. Instead, it provides:

• Integrity preservation: The index association is cryptographically bound through the signature verification process
• Non-repudiation: Each signature remains individually verifiable against its indexed public key
• Threshold enforcement: Supports verification of threshold requirements in multi-sig schemes
• Duplicity detection: Enables detection of conflicting signatures from the same key index

Key/Output Sizes

• Raw binary signature size: 64 bytes (512 bits)
• Pad size: 2 (derived from 64-byte alignment in Base64 encoding)
• Text code length: 2 characters
• Index encoding: Single Base64 character (6 bits, supporting indices 0-63)

Data Format & Encoding

CESR Encoding Structure

The dual-indexed code leverages CESR's text domain encoding to achieve efficient signature-to-key mapping:

Two-Character Code Composition

First Character (Selector and Type Code):

• Acts as the derivation code identifying the signature type
• Specifies the cryptographic algorithm or suite used
• Determines how the signature should be interpreted and verified
• Maintains CESR's self-framing property

Second Character (Base64-Encoded Index):

• Contains the integer index as a Base64-encoded value
• Points to the specific public key in an ordered set
• Supports indices from 0 to 63 (single Base64 character range)
• Enables immediate key lookup without additional metadata

Text Domain Representation

In CESR's text domain, a dual-indexed code appears as a two-character prefix followed by the Base64-encoded signature data:

[Type Code][Index][Base64 Signature Data]

For example, if the type code is 'A' and the index is 3 (Base64 'D'), the complete encoded signature would begin with "AD" followed by the signature's Base64 representation.

Binary Domain Representation

In CESR's binary domain, the dual-indexed code maintains equivalent information density:

• The type code and index are encoded in the binary primitive header
• The 64-byte raw signature follows the header
• The pad size of 2 ensures proper alignment for binary stream processing

Composability Properties

Dual-indexed codes maintain CESR's critical text-binary concatenation composability property:

• Any set of dual-indexed signatures can be concatenated in the text domain
• The concatenated stream can be converted to the binary domain and back without loss
• Self-framing structure enables cold-start stream parsing
• Group codes can aggregate multiple dual-indexed signatures for efficient processing

Usage in KERI/ACDC

Multi-Signature Event Signing

Dual-indexed codes are primarily used in KERI establishment events that require multiple signatures:

Inception Events

When creating a multi-sig AID, the inception event may include signatures from multiple initial controlling keys. Each signature uses a dual-indexed code to indicate which key from the initial key set produced that signature.

Rotation Events

The 2022 evolution of KERI's rotation rules created the forcing function that necessitated dual-indexed codes. The new rotation mechanism allows:

• Rotation to keys not in the prior next key digests
• Verification against both prior-next-threshold and current-signing-threshold
• Single-rotation control authority changes

This flexibility requires dual-indexed codes to clearly identify which keys (current or pre-rotated) are signing the rotation event, enabling proper threshold verification.

Threshold Verification Patterns

In threshold signature schemes, validators use dual-indexed codes to:

1. Extract the index from each signature's second character
2. Lookup the corresponding public key from the ordered key set
3. Verify the signature against the identified public key
4. Count verified signatures toward the threshold requirement
5. Ensure threshold satisfaction before accepting the event

Witness Receipt Signatures

In KERI's witness infrastructure, dual-indexed codes enable efficient representation of witness receipts:

• Each witness in a witness pool has an index
• Witness receipts use dual-indexed codes to identify which witness signed
• KAACE (KERI's Agreement Algorithm for Control Establishment) uses these indices for consensus determination
• The threshold of accountable duplicity (TOAD) is verified using indexed witness signatures

ACDC Credential Signatures

In ACDC (Authentic Chained Data Container) credentials, dual-indexed codes support:

• Multi-sig issuer signatures on credential issuance
• Threshold-based authorization for credential operations
• Compact representation in IPEX (Issuance and Presentation Exchange) protocols

Related Primitives

Indexed Signatures (Sigers)

Dual-indexed codes are a specialized form of indexed signatures (also called "sigers" in KERI implementations). The key distinction:

• Standard indexed signatures: May use variable-length index encoding
• Dual-indexed codes: Specifically optimized for the two-character, 64-byte signature case
• Composition: Both support multi-sig scenarios but dual-indexed codes provide maximum compactness

Count Codes and Group Codes

Dual-indexed codes work in conjunction with CESR count codes and group codes:

• Count codes: Specify how many dual-indexed signatures follow
• Group codes: Enable pipelining of signature groups
• Composition: Multiple dual-indexed signatures can be framed as a group for efficient stream processing

Derivation Codes

The first character of a dual-indexed code is a derivation code that:

• Identifies the cryptographic primitive type
• Specifies the signature algorithm
• Determines verification procedures
• Maintains CESR's self-describing property

Implementation Context

KERIpy Evolution

The introduction of dual-indexed codes in CESR was directly driven by changes in KERIpy, the Python reference implementation of KERI:

Pre-2022 Implementation:

• Control authority changes required two rotation events
• Simpler threshold verification model
• Less flexible key rotation constraints

Post-2022 Implementation:

• Control authority changes possible with one rotation event
• Rotation to keys not in prior next key digests allowed
• Dual threshold verification (prior-next-threshold and current-signing-threshold)
• Dual-indexed codes required to support this enhanced flexibility

This evolution demonstrates how protocol refinements in KERI drive corresponding changes in the underlying CESR serialization mechanisms to maintain security guarantees while improving operational efficiency.

Stream Processing Efficiency

Dual-indexed codes enable highly efficient stream processing:

1. Self-framing: Parser immediately knows the primitive type and length
2. Index extraction: Single character decode provides key reference
3. Parallel verification: Multiple signatures can be verified concurrently
4. Minimal overhead: Two-character encoding minimizes bandwidth and storage

Scalability Considerations

The single-character index encoding limits dual-indexed codes to:

• Maximum 64 keys in the indexed set (Base64 character range)
• Suitable for most practical multi-sig scenarios
• Larger key sets require alternative CESR encoding schemes
• Trade-off between compactness and key set size

Verification Procedures

Validators processing dual-indexed codes follow this procedure:

1. Parse the two-character code:

   • Extract type code (first character)
   • Extract index (second character)
   • Decode index from Base64 to integer

2. Retrieve the indexed public key:

   • Access the ordered key set from the current key state
   • Lookup the key at the decoded index position
   • Verify the key is valid for the event context

3. Verify the signature:

   • Extract the signature data following the two-character code
   • Apply the signature verification algorithm specified by the type code
   • Verify against the indexed public key

4. Threshold validation:

   • Count verified signatures toward threshold requirements
   • Check both current-signing-threshold and prior-next-threshold if applicable
   • Accept event only if all threshold requirements are satisfied

Architectural Significance

Dual-indexed codes exemplify CESR's design philosophy of maximizing information density while preserving composability. By embedding key index information directly in the signature encoding, KERI achieves:

• Reduced protocol overhead: No separate index mapping required
• Enhanced verifiability: Self-contained signature attribution
• Improved scalability: Efficient processing of multi-sig events
• Maintained security: No compromise of cryptographic properties

This encoding technique demonstrates how careful attention to data representation can significantly impact the efficiency and elegance of cryptographic protocols, particularly in streaming and event-driven architectures like KERI.