PQ spending for Stealth Address Protocol

1

PQ SAP - PQ Spending

Thanks Hy, @mmjahanara, @Pierre, @winderica, and kassandra for useful discussion and feedback.

TLDR;

This post is the 3rd post of a series of posts on Stealth Address Protocol and its Post-quantum upgrade. See Post Quantum Stealth Address Protocol for the 1st post, and PQ SAP - PQ Anonymity for upgrades in the announcement layer.

We have an accompanied repo for scheme 3 which is the best first step to PQ SAP upgrade

A Stealth Address Protocol allows:

  • a receiver to register a public Stealth Meta Address
  • a sender to derive a one-time Stealth Address for the receiver using the Stealth Meta Address and an ephemeral secret (also a nonce)
  • payments from a sender to a receiver, under different one time Stealth Addresses (meaning different nonces) of the same Stealth Meta Address, are unlinkable
  • sender anonymity is not-guaranteed (as a current property)

The (current) components often coupled with the Stealth Address Protocol are:

  • Stealth Meta Address registry where receivers can register their public keys and Annoucement registry where senders can announce their stealth payments to receivers
  • nonce manager on sender’s side to prevent re-using the same one-time Stealth Address twice or more
  • stealth payment discovery or scanning service for stealth payments, for this purpose, we usually rely on Dual Key Stealth Address Protocol, which separates the spending key from the viewing key
 RECEIVER (Bob)                          SENDER (Alice)
 k_view, k_spend                         nonce mgr: fresh r, never reuse
 M = (P_view, P_spend)                        |
      |                                       |
      | register M                            | lookup M
      v                                       v
 [META ADDRESS REGISTRY] ---------------------+
                                              |  s    = KA(r, P_view)
                                              |  P_st = P_spend + H(s)G
                                              |  R    = pub(r), vtag
                                              |
 [LEDGER]              value -> P_st  <-------+
 [ANNOUNCEMENT REGISTRY]  (R, P_st, vtag) <---+
      |
      | Bob (or view-delegate) scan: s' = KA(k_view, R); vtag? P_spend+H(s')G == P_st?
      v
 Bob spends with k_spend + H(s')

 unlinkable : P_st from same M, different r        [ HOLDS ]
 sender     : Alice's account funds + announces    [ EXPOSED ]
 keys       : k_view = detect (delegatable), k_spend = spend

A quantum attacker, observing the permanently-on-chain ERC6538Registry and ERC5564Announcer, will capture R and (K,V), and all the stealth payments to a stealth address P, and can recover r from R, k from K, and v from V, and be effectively the scanner with v and the receiver with k and have full viewing and spending access to the stealth payments.

We focus on upgrading the two core components of an SAP, namely the (1/2)-ECDH and the ECDSA, resulting in a schemeId = 3, 5, and 6 SAP, and interpret the implications to existing components.

Replacing ECDH with ML-KEM aims to protect payment discovery and recipient unlinkability against quantum attackers. Replacing ECDSA aims to protect spending authorization. Schemes 2-5 retain ECDSA and therefore do not provide both properties.

In this second extension of ERC-5564, we attempt to replace the ECDSA with a PQ ML-DSA and hash-based-spending (HSAP), resulting in SAPs schemeId = 6.

The numbers (gas cost) in this post is likely to be changed in the future given the field is actively moving. Hence, let us focus more on the mechanism rather than the actual cost.

Upgrading ECDSA with a PQ Signature Scheme

Let us first fix the syntax of a PQ secure Digital Signature Scheme:

  • (k,K) \leftarrow SKeyGen(\lambda)
  • (\sigma) \leftarrow Sign(k,m)
  • \{0,1\} \leftarrow Ver(K,\sigma,m)

Intuitively, we can further define 3 non-standard additional PQ algorithms for the PQ secure Digital Signature Scheme above:

  • P \leftarrow PKeyGen(K,r)
  • P' \leftarrow PMatch(dk,c,K)
  • p \leftarrow SKeyDer(k,r)
    where p is the signing key of public key P that is unlinkable to K or ek.

Notice that in the case of EC-based-SAP we have P \leftarrow PKeyGen(K,r) corresponding to set $P = K + hG$ while P' \leftarrow PMatch(dk,c,K) corresponding to decapsulating $r' = Decaps(dk,c)$, and recompute $h' = H(r')$, and the receiving address $P' = K + h'G$ and p \leftarrow SKeyDer(k,r) corresponding to one-time spending key now being $k + h$.

The Math

  • receiver runs (k,K) \leftarrow SKeyGen(\lambda) and (dk,ek) \leftarrow KeyGen(\lambda), and register (K,ek) as Stealth Meta Address
  • for a one time payment, the sender (in some way) obtains (K, ek), runs (r,c) \leftarrow Encaps(ek), and compute h = H(r), set P \leftarrow PKeyGen(K,r), sends some fund to P, and then publish c
  • the receiver, or a scanning service that the receiver entrust with the decapsulation key dk, can match the stealth payment by first decapsulating r' = Decaps(dk,c), and recompute P' \leftarrow PMatch(dk,c,K), and test whether P =? P'
  • however, only the receiver, who has k (not even the scanning service who only has dk), can access the fund, with the one-time spending key now being p \leftarrow SKeyDer(k,r) for the public key P \leftarrow PKeyGen(K,r)

The Candidates

The 1st clean way to do this is via Isogeny however the security of Isogeny has become questionable recently and it is also not NIST standardized.

In what follows, we outline two other schemes that are variants of ML-DSA (NIST FIPS 204), which we can accomodate for PQ-SAP.

ML-DSA FIPS 204

ML-DSA is the standardized descendant of Dilithium. The arithmetic uses polynomials:

R_q=\mathbb{Z}_q[X]/(X^{256}+1), \qquad q=8380417, \qquad A\in R_q^{k\times\ell}.

Generating the keys. The signer samples secret vectors s_1 and s_2 whose polynomial coefficients are small (“short vectors”), and compute t=As_1+s_2, where the public matrix A is generated from a compact public seed \rho: A=\mathsf{ExpandA}(\rho). To reduce the public-key size, each coefficient of t is split into a rounded high part and a low remainder: t=2^{13}t_1+t_0. The public key is (\rho,t_1); the signer keeps t_0 as signing metadata.

The factor 2^{13}=8192 determines the scale of this compression.

Signing a message. Signing proceeds in “attempts” taking \mu as the message digest bound to the public key and signing context. For each signing attempt, the signer generates a secret mask y and computes w=Ay and w_1=\mathsf{HighBits}(w) where w_1 is a coarse representation of w, using the signing algorithm’s rounding rule. The signer computes \widetilde c=H(\mu\parallel\mathsf{Encode}(w_1)), and c=\mathsf{SampleInBall}(\widetilde c) then z=y+cs_1.

Sampling Rejection, i.e. rejecting unsuitable attempts. As in Dilithium design explanation, masking alone is insufficient: some responses would leak information about the secret-dependent shift. This rejection sampling protects the secret and ensures verification works. The signer also creates a small correction hint h. The resulting signature is \sigma=(\widetilde c,z,h).

Verifying the signature. The verifier reconstructs A and c, then computes \overline w=Az-c(2^{13}t_1). Substituting the signing and key-generation equations gives \overline w=A(y+cs_1)-c(t-t_0)=w-cs_2+ct_0.

Thus the verifier obtains w with correction terms. The hint lets it recover the same coarse value w_1 used by the signer: w_1'=\mathsf{UseHint}(h,\overline w). It then checks \widetilde c\stackrel{?}{=}H(\mu\parallel\mathsf{Encode}(w_1')).

Parameters Set. NIST further provided 3 parameter sets for ML-DSA:

Parameter set Public key Signature
ML-DSA-44 1312 bytes 2420 bytes
ML-DSA-65 1952 bytes 3309 bytes
ML-DSA-87 2592 bytes 4627 bytes

SPIRIT

SPIRIT was given in Post Quantum Fuzzy Stealth Signatures and Applications.

Let A be a globally shared matrix.

  • The receiver samples short (s_1,s_2), computes the full-precision t=As_1+s_2, generates a KEM key pair (ek,dk), and publishes the meta-address (t,ek).
  • The sender runs (\kappa,ct)\leftarrow\mathsf{Encaps}(ek), derives short (s_1',s_2')=\mathsf{ExpandS} (\kappa), and computes t'=t+As_1'+s_2'. It rounds t' to obtain the one-time public key (\rho_A,t_1') and publishes ct alongside the payment.
  • The receiver, or a scanner holding (dk,t), decapsulates ct and recomputes the derived public key to recognize the payment.
  • The receiver derives the signing secret (s_1+s_1',s_2+s_2'), together with the low bits and auxiliary signing values. Spending uses the corresponding Dilithium-style signature verifier.

Correctness simply follows t'=A(s_1+s_1')+(s_2+s_2').

However, we need a global matrix for SAP unlinkability (a pre-defined seed throughout the ERC). And the master t must remain uncompressed. And the coefficient bound is increased from \eta to 2\eta, requiring \beta'=2\tau\eta. Original SPIRIT also doubles \gamma_1 and \gamma_2 to control signing retries. In order to keep the standard mask widths we will need tighter signer rejection and a separate compatibility/security analysis.

Cost of ML-DSA Verification

For SAP, only ML-DSA signature verification and account execution run on chain. The main verifier bottleneck includes SHAKE expansion/hashing, NTT arithmetic, matrix-vector products, decoding, and bounds checks. According to ETHDILITHIUM benchmarks:

Verification path Reported gas Assumption
ZKNox SHAKE-based main implementation about 8.1M Expanded/precomputed public key
ZKNox experimental packed SHAKE verifier 1,196,707 Expanded/precomputed key and external Keccak-f helper
ZKNox experimental packed ETHDilithium 847,709 Modified hash construction; not FIPS 204

Draft EIP-8051 proposes a 4500-gas ML-DSA-44 verification precompile with an expanded-key interface.

Non-ML-DSA PQ-SAP

Abstracting the SAP following Vitalik’s idea, we can consider the minimal model below:

  • the receiver publish K and keeps its associated k secret
  • the sender needs to make a stealth payment to an address P, which is associated with some nonce r (to be delivered to the receiver via ML-KEM), and P is associated in some way but unlinkable to K,
  • the spending condition has to be that receiver is the only one who can spend the fund in P, given the knowledge of k and r.

This makes a typical application of PQ zk-SNARK/STARK (in fact, a DSA is a specific instance of ZKP) which can be as minimal as:

  • let K = H(k)
  • let P = H(K,r)
  • spending condition be proving in zk knowledge of k,r s.t. P = H(H(k),r))

This sounds like a zkWormhole which is known to be insecure if P/K is an Ethereum address; BUT this is ONLY TRUE in the case that we want to disconnect the sender from the smart contract account, which IS NOT OUR CASE, i.e. the sender indeed sends some fund to the smart contract account that can be spent with a PQ-zk-SNARK/STARK later (with the cost of one PQ-zk-SNARK/STARK verification per-spend), which, as of now, cost around 7M gas at 300.000 R1CS constraints if we extrapolate a WHIR-EVM-Verifier benchmark. However, this may not be the case in a not so far future, as EIP-8288 on Frame Type for PQ Sig and STARK Aggregation proposes to add recursive STARK-based aggregation for quantum-resistant signatures and STARKs via an EIP-8141 frame mode, which can amortize the verification cost (IF we use leanStark) with only an additional validation fee of 30K gas.

This gives us HSAP: a PQ-SAP with ML-KEM delivery and hash-preimage spending.

The Math

Let H_{\mathsf{key}}, H_{\mathsf{pay}}, and H_{\mathsf{auth}} be SHA-256 with distinct one-byte domain tags and canonical encodings. Let \mathsf{KDF} be HKDF-SHA256 with 32-byte output and deployment domain D, binding the scheme, chain, and factory.

  • The receiver randomly samples a 256-bit spending key k, runs (dk,ek)\leftarrow\mathsf{KeyGen}(\lambda), and registers (K,ek) as the Stealth Meta Address, where K=H_{\mathsf{key}}(k).
  • For a one-time payment, the sender obtains (K,ek), runs (s,c)\leftarrow\mathsf{Encaps}(ek), derives r=\mathsf{KDF}(s,D), and computes C=H_{\mathsf{pay}}(K,r). A fixed factory atomically deploys and funds a smart account at P=\mathsf{CREATE2Addr}(F,C,I(C)), then announces c. The account stores the full 256-bit C, a spend nonce, and a fixed verifier. Deployment failure reverts the payment.
  • The receiver, or a scanner entrusted with dk, recovers s'=\mathsf{Decaps}(dk,c), derives r'=\mathsf{KDF}(s',D), recomputes C'=H_{\mathsf{pay}}(K,r') and P', and tests P=P'. It also checks the deployed account and funded balance.
  • Only the receiver has k. The sender and scanner know r but cannot independently authorize spending. The receiver authorizes a spend with a ZK proof using witness (k,r).

For destination Q, amount a, relayer L, fee f, current nonce n, and expiry t, define

m=H_{\mathsf{msg}}(D,P,C,n,Q,a,L,f,t), \qquad T=H_{\mathsf{auth}}(k,r,m).

The spending proof is

\pi=\mathsf{ZKPoK}\left[ \begin{array}{l} \text{public: } C,m,T;\quad \text{private: } k,r\\ C=H_{\mathsf{pay}}(H_{\mathsf{key}}(k),r)\\ T=H_{\mathsf{auth}}(k,r,m) \end{array} \right].

The account recomputes m, checks the nonce, expiry, balance, and proof, increments the nonce, then transfers a to Q and f to L, with atomic execution to protect against reentrancy. K remains hidden inside the circuit, while the proof transcript binds the whole statement.

Summing on Spending All Up To schemeId = 6

Let us attempt to now abstract how PQ-spending now look like for SAP:

Scheme Master public key K Derived verification key P Derived signing key p
EC reference kG K+H(r)G k+H(r)
Basic SPIRIT t=As_1+s_2 (\rho_A,\mathsf{Hi}(t+Au_1+u_2)) (s_1+u_1,s_2+u_2) plus signing metadata
HSAP H_{\mathsf{key}}(k) H_{\mathsf{pay}}(K,r) (k,r)

For SPIRIT, (u_1,u_2) is derived from r. Signing metadata includes the derived low bits, public-key hash, and required auxiliary signing material.

For HSAP, \mathsf{Sign}(p,m) returns \sigma=(T,\pi), where T=H_{\mathsf{auth}}(k,r,m) and \pi proves $P=H_{\mathsf{pay}}(H_{\mathsf{key}}(k),r) \land
T=H_{\mathsf{auth}}(k,r,m), while \mathsf{Ver}(P,\sigma,m)$ verifies this statement without exposing K, k, or r.

The PQ-spend ERC schemeId = 6

We can extend ERC-5564 with schemeId = 6 for PQ spending, while keeping the actual spending construction abstract.

All the constructions above follow the same flow:

P=\mathsf{PKeyGen}(K,r), \qquad p=\mathsf{SKeyDer}(k,r),

and spending requires

\sigma=\mathsf{Sign}(p,m), \qquad \mathsf{Ver}(P,\sigma,m)=1.

The difference is how each construction defines P, p, and \sigma: for SPIRIT, these are the derived lattice public key, its signing secret, and a signature; while for HSAP, these are the payment commitment, the witness (k,r), and a message-bound ZK authorization

The extended ERC-5564

Notice that P is now the public verification data. We use A for the actual Ethereum smart account address holding the funds. The Stealth Meta Address contains (K,ek) together with an identifier of the selected spending construction. This identifier tells the sender and receiver which derivation algorithms, parameters, and verifier to use.

  • the sender encapsulates to ek, derives r, and computes P=\mathsf{PKeyGen}(K,r)
  • the sender derives the smart account address A through an agreed factory, deploys or validates the account, sends the funds to A, and publishes the KEM ciphertext c
  • the receiver or scanner decapsulates c, recomputes P and A, and checks whether the announcement matches
  • only the receiver has k to derive p=\mathsf{SKeyDer}(k,r) and authorize spending

The existing ERC5564Announcer can keep its event interface:

schemeId        = 6
stealthAddress  = A
ephemeralPubKey = c
metadata        = viewTag || scheme-specific metadata

Similarly, ERC6538Registry can keep its current mapping. Its bytes value carries the keys and the information needed to select the spending construction and account deployment.

The spending path

The smart account is initialized with P, or a full-width commitment to P, and the corresponding verifier.

To spend, the receiver prepares a message m containing the account, chain, nonce, and complete spending instruction, including destination, amount, call data, and any fee. The receiver then produces \sigma=\mathsf{Sign}(p,m).

The account recomputes m, checks the nonce and \mathsf{Ver}(P,\sigma,m)=1, then consumes the nonce and executes the authorized instruction. The spending transaction however cannot replace the account’s verification key or verifier.

Also notice that the verifier only checks authorization. Transfers, batching, gas sponsorship, and account abstraction remain the responsibility of the smart account. Thus, the same account flow can accommodate both SPIRIT-style signatures and HSAP proofs.

Retrospective to previous schemes

  • the announcement and scanning flow remains KEM-based
  • spending replaces ECDSA with the selected PQ authorization mechanism
  • each spend pays for authorization verification and account execution; a fresh account also incurs deployment cost
  • the sender and scanner know r, so the selected construction must prevent spending with that knowledge alone
  • a future precompile can reduce verification cost when it supports the exact construction
  • sender-to-account and subsequent spending links remain public
3 Likes