Back to the lattice

After talking with Tamaghna about splitting the work on trustless logs and transactions indexing — and realizing I wouldn't have much to do until the implementation reaches a certain point — I returned to something I was covering back in week 1 that also got new light recently: the Post-Quantum stealth address protocol, now also my project proposal[1].

The problem to cover, briefly, is not really the spending part but securing the key-exchange protocol with an efficient and future-proof solution. The paper I'm referencing[2] relies on Learning With Errors and its Module-LWE variant — it results in larger keys, but noise separation is considered pq-hard, so it's a good candidate.

Because I already had a reference implementation, I decided to start by trying to reproduce a PoC of the ML-KEM[3] key exchange and spending using Kohaku's pq-account[4]. The coding agent quickly flagged that pq-account is Dilithium level 2 while we assumed level 3 by default — quickly figuring out that the spending part should be a stretch goal.

There's a general trick with zk-proofs and 4337[5]: generate a zk proof of a valid signature recovery, proving possession of the private key. With the traditional key exchange described in 5564[6], the next step after finding the note that belongs to you is deriving the private key that controls that stealth address.

The initial gas-sponsoring issue from the 5564 ERC can be solved quite nicely with account abstraction today and deserves a description, but it sounded like a slightly different problem. I basically came to the realization that it's better to divide the problem into:

• a pq-safe Diffie-Hellman-like key exchange and its alternatives (indexing faster than O(n) is deliberately not covered), plus measuring gas costs;
• pq-safe spending (less of a priority), as it would be covered on the protocol level according to pq.ethereum.org[7].

With the help of a coding agent I quickly ran an anvil Sepolia fork to run the whole flow, not really sure it was going to work "first prompt". Then, after :railgun:, got the PoC validated[8] on a live net with a deployed precompile.

Announcement #0 came in at 67,580 gas[9]. The ephemeralPubKey is noticeably bigger compared with existing announcements — 1088 bytes of ML-KEM ciphertext against a 33-byte compressed secp256k1 point in a classic 5564 one:

announce(uint256 schemeId, address stealthAddress,
         bytes ephemeralPubKey, bytes metadata)

ML-KEM (schemeId 0x5567)              secp256k1 (schemeId 0x1)
[4]: ...0440   // 1088 bytes          [4]: ...0021   // 33 bytes
[5]: beef31c81ab8fd3c361dd6ab...      [5]: 021e7a0e1b19d1dfbc578c...
     + 33 more words of ciphertext

Then on CT I saw something about Lean 4 and it clicked that I might also get formal verification for the algebraic part of the key exchange. I sent it to Claude, it did it, and now I need to spend a ton of time figuring out whether it's right. VCVio[10] was a huge help.

As next steps, I'm going to take a deeper dive into the existing conversations on speeding up the O(n) indexing and try to see if there's something we can improve. And I'd probably better get basic infrastructure running for 4337-sponsored spending with a custom verifier that checks an address-derivation proof instead of the full signature — before frame transactions[11] would land.

The problem there is the proving backend: if we go with Groth16/Plonk we for real get a significant improvement, but neither is itself pq-secure. Other options like STARKs are — however, much more expensive.