Table of Contents
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}}) Optimization ideas
Abuse of ecrecover precompile
Ethereum (majority of EVM-based chains) ecrecover returns an address (hash of public key) given an ECDSA signature. Given message m and ECDSA signature (v, r, s) where v denotes the parity of the y-coordinate for the point where x-coordinate r:
ecrecover(m, v, r, s):
R = point derived from r and v
a = -G*m
b = R*s
Qr = a + b
Q = Qr * (1/r)
Q = (1/r) * (R*s - G*m) //recovered pubkey
Ethereum's ecrecover returns the last 20 bytes of the keccak256 hash of the 64-byte public key, check code here. Given signature (R, s), message m and public key P we can feed values into ecrecover such that the returned address can be used in a comparison to the challenge.
pass:
m = -s*P_x
v = parity of P
r = x-coordinate of P
s = -e*P_x
then:
ecrecover(m=-s*P_x, v=0/1, r=P_x, s=-e*P_x):
P = point derived from r and v (public key)
a = -G*(-s*P_x) = G*s*P_x
b = P*(-m*P_x) = -P*e*P_x
Q = (1/P_x) (a+b)
Q = (1/P_x)(G*s*P_x - P*e*P_x)
Q = G*s - P*e // same as verification above
the returned value is address(Q).
- calculate e'
- check e' == e to verify the signature.
Canoncial ecrecover implementations:
Minimization of multiplications
s*G - e*H_{\text{agg}} = R - \sum_i^m (e*(a_i * X_i) + b*R_{\text{i1}} + d*R_{\text{i2}}) s*G - e*H_{\text{agg}} = b*R_1 + d*R_2 - \sum_i^m (e*(a_i * X_i) + b*R_{\text{i1}} + d*R_{\text{i2}}) s*G - e*H_{\text{agg}} = b*R_1 + d*R_2 - \sum_i^m (e*(a_i * X_i)) - \sum_i^m (b*R_{\text{i1}}) - \sum_i^m (d*R_{\text{i2}}) s*G + e*( \sum_i^m (a_i * X_i) - H_{\text{agg}}) = b*(R_1 - \sum_i^m R_{\text{i1}}) + d*(R_2 - \sum_i^m R_{\text{i2}}) In this variant operations needed:
- number of additions =
3(m + 1) + 2 - number of multiplications =
4 consant
In original version:
- number of additions =
2m + 2 - number of multiplications =
4m + 2
For that reason verifier should reconstruct R from the:
R = b*R_1 + d*R_2 Threshold identification
Because the values a_i, X_i, R_{\text{i1}}, R_{\text{i2}} can be computed locally and only their sums sent to the verifier, a malicious user could try to spoof the threshold. To prevent this, send the full list of original signers to the verifier together with indices for any missing signers; the verifier will then recomput H_{\text{agg}} and compare it to the stored value. The verifier computes each H_i based on the provided indexes of missing signers.
s*G + e*( \sum_i^m (H_i) - H_{\text{agg}}) = b*(R_1 - \sum_i^m R_{\text{i1}}) + d*(R_2 - \sum_i^m R_{\text{i2}}) Usage of GLV (Gallant–Lambert–Vanstone) and GLS (Galbraith–Lin–Scott)
Potentially useful links:
- GLV (Gallant–Lambert–Vanstone)
- GLS (Galbraith–Lin–Scott)
- GLV-Based Scalar Multiplication
- The Realm of the Pairings
- Fast and compact elliptic-curve cryptography
If the final formula is:
s*G + e*( \sum_i^m (H_i) - H_{\text{agg}}) = b*(R_1 - \sum_i^m R_{\text{i1}}) + d*(R_2 - \sum_i^m R_{\text{i2}}) The optimization should be focused on:
b*(R_1 - \sum_i^m R_{\text{i1}}) + d*(R_2 - \sum_i^m R_{\text{i2}}) = k*P + m*Q For a curve with efficient endomorphism ϕ where ϕ(P) = λP in the subgroup of order r:
k ≡ k_1 +k_2 λ (mod r) m ≡ m_1 +m_2 λ (mod r) |k_1|, |k_2|, |m_1|, |m_2| ≈ \sqrt{r} r≈2^{256} k_i, m_i ≈ \sqrt{2^{256}} ≈ 2^{128} Then use multi-scalar multiplication:
kP + mQ = (k_1 + k_2λ)P + (m_1 + m_2λ)Q = k_1P + k_2(λP) + m_1Q + m_2(λQ) P` = λP = ϕ(P) = ϕ((P_x, P_y)) = (βP_x, P_y) Q` = λQ = ϕ(Q) = ϕ((Q_x, Q_y)) = (βQ_x, Q_y) kP + mQ = k_1P + k_1P` + m_2Q + m_2Q` Then use Straus-Shamir trick to do simultaneous multiplication of four elements. In theory that will save:
- 128 doublings, because all scalars are less then 128 bit.
- 120 additions, because probability of four zeros is
1/16.
Based on the current solidity implementation final gas cost for the most intensive part can be estimated around 197,080 gas units.
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
banddsufficiently 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