Underlying Algorithms

Indexed signatures in KERI primarily use Ed25519 digital signatures, which provide:

• SUF-CMA security: Strong Unforgeability under Chosen Message Attack
• Deterministic signing: Same message and key always produce the same signature
• Fast verification: Efficient batch verification capabilities
• Small signatures: 64-byte signature output

The Ed25519 algorithm operates on the Curve25519 elliptic curve and uses:

• SHA-512 for hashing operations
• EdDSA (Edwards-curve Digital Signature Algorithm) signature scheme
• 32-byte private keys and 32-byte public keys

Security Properties

Indexed signatures inherit the security properties of their underlying signature algorithm:

Non-repudiation: Only the holder of the private key at the specified index could have created the signature, providing cryptographic proof of authorship.

Integrity protection: Any modification to the signed data invalidates the signature, ensuring tamper-evidence.

Index binding: The index is cryptographically bound to the signature through the CESR encoding structure, preventing index substitution attacks.

Threshold compatibility: Multiple indexed signatures can be combined to satisfy threshold signature schemes, where M-of-N signatures are required for authorization.

Key and Output Sizes

For Ed25519-based indexed signatures:

• Private key: 32 bytes (256 bits)
• Public key: 32 bytes (256 bits)
• Raw signature: 64 bytes (512 bits)
• Index encoding: Variable (typically 1-2 characters in text domain)
• Total CESR primitive: ~88-90 characters in Base64 text domain

Data Format & Encoding

CESR Encoding Structure

Indexed signatures follow CESR's self-framing design with a specific encoding pattern:

[derivation_code][index][signature_bytes]

The derivation code is a 1-2 character prefix that encodes:

• The signature algorithm (e.g., Ed25519)
• The index encoding scheme (small vs. large index)
• The pad size for 24-bit boundary alignment

Text Domain Representation

In the text domain, indexed signatures use Base64 URL-safe encoding:

Example structure: 0AABxxx...xxx

• 0A: Derivation code indicating Ed25519 signature with small index
• AB: Index value encoded in Base64 (index 0 in this example)
• xxx...xxx: 64-byte signature encoded as 88 Base64 characters

The complete primitive is exactly 92 characters (4 + 88), maintaining CESR's requirement that all primitives be integer multiples of 4 characters for composability.

Binary Domain Representation

In the binary domain, the same indexed signature is encoded as raw bytes:

• Derivation code: 1-2 bytes
• Index: 1-2 bytes (depending on index size)
• Signature: 64 bytes
• Total: 66-68 bytes (integer multiple of 3 for 24-bit alignment)

Derivation Codes

CESR defines multiple derivation codes for indexed signatures:

Small index codes (index 0-63):

• 0A: Ed25519 signature, index encoded in next character
• 0B: ECDSA secp256k1 signature, small index

Large index codes (index 64+):

• 2A: Ed25519 signature, index encoded in next 2 characters
• 2B: ECDSA secp256k1 signature, large index

The choice of code depends on the maximum index value needed for the multi-signature scheme.

Usage in KERI/ACDC

Multi-Signature AID Control

Indexed signatures are fundamental to multi-sig AIDs where control authority requires threshold-based signatures from multiple key pairs. When a controller creates a multi-sig AID, they specify:

• Current keys (k field): Ordered list of public keys
• Current threshold (kt field): Number of signatures required (e.g., "2" for 2-of-3)
• Next keys (n field): Ordered list of pre-rotated key digests
• Next threshold (nt field): Threshold for next rotation

When signing a key event, each participating key holder creates an indexed signature where the index corresponds to their position in the current key list.

Establishment Event Signing

Inception events and rotation events require indexed signatures from threshold-satisfying subsets of current keys:

{
  "v": "KERI10JSON000160_",
  "t": "icp",
  "d": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "i": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "s": "0",
  "kt": "2",
  "k": [
    "DKxy2sgzfplyr-tgwIxS19f2OchFHtLwPWD3v4oYimBx",
    "D8KY1sKmgyjAiUDdUBPNPyrSz_ad_Qf9yzhDNZlEKiMc",
    "DEe5T5YEZLccvO_JJpvm2Fz-B4Li1XWJRT_7VWHbTd2s"
  ],
  "nt": "2",
  "n": [
    "ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM",
    "EYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS",
    "EnmwyZdi0d8JZAoTNZYAfSVPzhzaU6JR2H3ULvS6b5CM"
  ]
}

Attached indexed signatures might look like:

-AADAA0ABxxx...xxx0ACByyy...yyy

Where:

• -AAD: Count code indicating 3 indexed signatures follow
• AA: First signature at index 0
• 0AB: Second signature at index 1
• 0AC: Third signature at index 2

Witness Signature Application

Indexed signatures extend beyond controller signatures to witness signatures. When witnesses provide receipts for key events, they attach their own signatures as indexed signatures:

{
  "v": "KERI10JSON000091_",
  "t": "rct",
  "d": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "i": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "s": "0"
}

Attached witness indexed signatures:

-AABAA0ABxxx...xxx0ACByyy...yyy

The controller can determine which specific witness signed by looking up the index in their configured witness list for that event. This enables:

• Efficient witness identification: No need to attempt verification against all witnesses
• Scalable witnessing: Witnesses attach only their individual signature
• Witness accountability: Each witness signature is individually attributable

Interaction Event Anchoring

Interaction events (ixn) also use indexed signatures when anchoring external data:

{
  "v": "KERI10JSON000138_",
  "t": "ixn",
  "d": "E8KY1sKmgyjAiUDdUBPNPyrSz_ad_Qf9yzhDNZlEKiMc",
  "i": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "s": "2",
  "p": "EH7Oq9oxCgYa-nnNLvwhp9sFZpALILlRYyB-6n4WDi7w",
  "a": [
    {
      "i": "EJJR2nmwyZ2i0dzaU6ULvS6b5CM8JZAoTNZH3YAfSVPzh",
      "s": "0",
      "d": "ELccvO_JJpvm2Fz-B4Li1XWJRT_7VWHbTd2sEe5T5YEZ"
    }
  ]
}

The attached indexed signatures prove which subset of the multi-sig group authorized this anchoring operation.

ACDC Credential Signing

In ACDC verifiable credentials, indexed signatures appear in CESR Proof Signatures:

{
  "v": "ACDC10JSON000197_",
  "d": "EBdXt3gIXOf2BBWNHdSXCJnFJL5OuQPyM5K0neuniccM",
  "i": "EAco5dU5WjDrxDBK4b4HrF82_rYb6MX6xsegjq4n0Y7M",
  "s": "EBKValuMGPmwdSm3dpiXAQZHgGqWwaBqWDAKv3VqepLg",
  "a": {
    "d": "ELccvO_JJpvm2Fz-B4Li1XWJRT_7VWHbTd2sEe5T5YEZ",
    "i": "EJJR2nmwyZ2i0dzaU6ULvS6b5CM8JZAoTNZH3YAfSVPzh",
    "LEI": "254900OPPU84GM83MG36"
  }
}

The CESR proof attachment includes indexed signatures proving which keys from the issuer's multi-sig AID authorized the credential issuance.

Verification Procedures

Verifying an indexed signature follows a deterministic algorithm:

Step 1: Parse the Indexed Signature

Extract components from the CESR primitive:

• Derivation code: Determines signature algorithm and index encoding
• Index value: Position in the key list (0-based)
• Raw signature bytes: The actual cryptographic signature

Step 2: Retrieve Current Key State

Query the KEL to obtain the current key state for the signing AID at the event's sequence number:

• Current keys (k field): Ordered list of public keys
• Current threshold (kt field): Required signature count

Step 3: Lookup Public Key

Use the index to retrieve the corresponding public key from the current keys list:

public_key = current_keys[index]

If the index is out of bounds, the signature is invalid.

Step 4: Verify Cryptographic Signature

Perform signature verification using the identified public key:

is_valid = verify_signature(
    public_key=public_key,
    message=event_bytes,
    signature=signature_bytes
)

For Ed25519, this involves:

• Hashing the message with SHA-512
• Verifying the signature equation on Curve25519
• Returning boolean validity result

Step 5: Check Threshold Satisfaction

After verifying all attached indexed signatures, confirm that the count of valid signatures meets or exceeds the threshold:

valid_count = sum(1 for sig in signatures if verify(sig))
is_authorized = valid_count >= threshold

Only if threshold is satisfied is the event considered properly authorized.

Related Primitives

Cigar (Non-Indexed Signature)

A cigar is an un-indexed signature primitive used in single-signature scenarios where no index is needed. The key differences:

• Cigar: No index, used for single-sig AIDs
• Siger: Includes index, required for multi-sig AIDs

Both use the same underlying signature algorithms (Ed25519, ECDSA) but differ in their CESR encoding structure.

Signer (Private Key Primitive)

A signer is the CESR primitive representing a private key. It has the ability to create both:

• Sigers (indexed signatures)
• Cigars (non-indexed signatures)

The signer encapsulates the private key material and provides methods for generating signatures with or without index information.

Verfer (Public Key Primitive)

A verfer represents a public key and has the ability to verify signatures. During indexed signature verification, the verifier:

1. Uses the index to select the appropriate verfer from the key list
2. Calls the verfer's verification method with the signature bytes
3. Returns the verification result

Diger (Digest Primitive)

A diger represents a cryptographic digest. In multi-sig scenarios, digers appear in:

• Next key commitments (n field): Digests of pre-rotated public keys
• Event digests (d field): SAIDs of events
• Prior event references (p field): Backward chaining in KEL

The index in an indexed signature may correspond to the position of a diger in the next keys list during partial rotation.

Implementation Considerations

Index Bounds Checking

Implementations must validate that the index value is within the bounds of the current keys list:

if index < 0 or index >= len(current_keys):
    raise InvalidIndexError(f"Index {index} out of bounds")

Out-of-bounds indices indicate either:

• Malformed signatures
• Incorrect key state retrieval
• Attempted signature substitution attacks

Threshold Validation

Before accepting an event, implementations must verify threshold satisfaction:

valid_signatures = [sig for sig in signatures if verify(sig)]
if len(valid_signatures) < threshold:
    raise InsufficientSignaturesError(
        f"Required {threshold}, got {len(valid_signatures)}"
    )

Duplicate Index Detection

Implementations should detect and reject duplicate indices in the signature set:

indices = [sig.index for sig in signatures]
if len(indices) != len(set(indices)):
    raise DuplicateIndexError("Duplicate signature indices detected")

Duplicate indices may indicate:

• Implementation bugs
• Replay attacks
• Malicious signature manipulation

Fractional Weight Thresholds

For advanced multi-sig schemes with fractional weights, implementations must:

1. Parse the threshold as a rational number (e.g., "1/2", "2/3")
2. Assign weights to each key position
3. Sum the weights of valid signatures
4. Compare the sum to the threshold

weights = [1, 1, 2]  # Key at index 2 has weight 2
total_weight = sum(weights[sig.index] for sig in valid_signatures)
threshold_weight = parse_threshold("2/3") * sum(weights)
if total_weight < threshold_weight:
    raise InsufficientWeightError()

Partial Rotation Support

During partial rotation, only a subset of pre-rotated keys may be exposed. Implementations must:

1. Verify that indices in rotation signatures correspond to exposed next keys
2. Confirm that unexposed keys remain committed via their digests
3. Validate that the rotation threshold is satisfied by exposed keys only

Performance Optimization

For high-throughput scenarios, implementations can optimize indexed signature verification:

Batch verification: Ed25519 supports efficient batch verification of multiple signatures:

verify_batch(
    public_keys=[keys[sig.index] for sig in signatures],
    messages=[event_bytes] * len(signatures),
    signatures=[sig.raw for sig in signatures]
)

Parallel verification: Independent signature verifications can be parallelized:

with ThreadPoolExecutor() as executor:
    results = executor.map(verify_signature, signatures)
    valid_count = sum(results)

Caching: Frequently verified events can have their verification results cached:

cache_key = (event_digest, frozenset(sig.index for sig in signatures))
if cache_key in verification_cache:
    return verification_cache[cache_key]

Security Considerations

Timing attacks: Implementations should use constant-time comparison for signature verification to prevent timing side-channels.

Index substitution: The CESR encoding cryptographically binds the index to the signature through the self-framing structure, but implementations should validate this binding.

Replay protection: Indexed signatures on events include the event's sequence number and prior event digest, preventing replay across different events.

Key compromise: If a key at a specific index is compromised, only signatures from that index are affected. The multi-sig threshold provides defense-in-depth.

Conclusion

Indexed signatures represent a fundamental innovation in KERI's approach to multi-signature authorization. By embedding index information directly in the signature primitive, KERI achieves:

• Deterministic verification: No ambiguity about which key to use
• Efficient processing: Single-pass verification without trial-and-error
• Threshold flexibility: Support for M-of-N and weighted schemes
• Witness scalability: Individual witness attribution in receipts
• Composability: Seamless integration with CESR streaming

The indexed signature primitive demonstrates KERI's design philosophy of creating self-describing, composable cryptographic primitives that enable both human readability (text domain) and machine efficiency (binary domain) while maintaining rigorous security properties.