Table of Contents

EXODUS - EXchange Of Digital Uniformed Signatures

Abstract
Verifier prerequisites
Verifier terminology
Verifier inputs
Verifier computes
Reporting issues and feedback

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

EXODUS - EXchange Of Digital Uniformed Signatures

Abstract

We present EXODUS, an algorithm that lets N signers aggregate their public keys and signatures so a verifier needs to check only a single signature. The verifier can also exclude missing signers, enabling EXODUS to operate as a t‑of‑n scheme. EXODUS combines compact signature aggregation with signer‑specific coefficient hashing and explicit transcript binding to provide a practical, secure, and flexible multisignature primitive: it produces signatures indistinguishable in size and verification cost from a single‑party signature while preventing rogue‑key and substitution attacks by deterministically deriving each participant’s weight from a canonical encoding of the signer set and domain data; it preserves full signer autonomy because no aggregated private key or secret‑sharing is ever created.

Note: EXODUS does not use Shamir Secret Sharing or any Distributed Secret‑Sharing scheme during aggregation. Each signer remains fully independent — no aggregated private key is ever constructed or stored. Instead, the aggregate public key is deterministically derived from the validators' session public keys using signer‑specific coefficients computed from a binding encoding of the participant set and session transcript. This preserves simple key management, avoids key‑reconstruction or trusted dealers, and ensures the aggregate key and resulting signature accurately reflect exactly state of the current validator set.

Below is a concise, step‑by‑step verifier procedure and the verification formulas. This section focuses exclusively on the verifier’s responsibilities; the signature aggregation internals are omitted here.

Verifier prerequisites

Stores only the aggregated public key (stateless as much as possible).
Should be as minimal as possible to fit in the EVM limitations.
Because of EVM nature, all numbers are 256 bit.

Verifier terminology

taggedhash - domain-separated SHA-256 hash, bytes concatenated.
G - generator base point of the elliptic curve.
H_{\text{agg}} - aggregated public key.
m - number of missing signers.

Verifier inputs

R - aggregated public nonce.
s - partially aggregated signature or fully aggreagated signature if there's no missing signers.
message - encoded transaction call for EVM.
a_{\text{il}} - first aggregation coefficient of neighbor when signer i is missing.
a_{\text{ir}} - second aggregation coefficient of neighbor when signer i is missing.
X_i - public key of the missing signer i.
R_{\text{i1}} - first public nonce of the missing signer i.
R_{\text{i2}} - second public nonce of the missing signer i.

Verifier computes

 msg = keccak256(message)

 a_i = taggedhash(a_{\text{il}}, a_{\text{ir}}, taggedhash(X_i))

 b = taggedhash(H_{\text{agg}}, (R_x, R_y), msg)

 d = taggedhash(msg, (R_y, R_x), H_{\text{agg}})

 e = taggedhash(H_{\text{agg}}, R_x, msg)

 Verify

 s*G + \sum_i^m (e*(a_i * X_i) + b*R_{\text{i1}} + d*R_{\text{i2}}) = R + e*H_{\text{agg}}

OR

 s*G - e*H_{\text{agg}}= R - \sum_i^m (e*(a_i * X_i) + b*R_{\text{i1}} + d*R_{\text{i2}})

Reporting issues and feedback

We welcome feedback and bug reports from knowledgeable contributors. If you discover any issues or have suggestions, please contact us via email or any of the social links below. If you have an account here, you may also submit a free-form issue.

We are currently investigating the following questions:

Is it feasible to construct arguments in polynomial time that cause the verifier’s equation to hold?

 R', s', message', a_{\text{il}}', a_{\text{ir}}', X_i', R_{\text{i1}}', R_{\text{i2}}'

 s'*G + \sum_i^m (e*(a_i' * X_i') + b*R_{\text{i1}}' + d*R_{\text{i2}})' = R' + e*H_{\text{agg}}

Can information about missing signers be consolidated into a single entry?

 \sum_i^m (e*(a_i * X_i) + b*R_{\text{i1}} + d*R_{\text{i2}}) = e*(a' * X') + b*R_{\text{1}}' + d*R_{\text{2}}'

Are parameters b and d sufficiently robust and indistinguishable from each other?
Are there any other issues you can identify?

Please feel free to use any contact below.

Email: support@ghostchain.io