Post-quantum keys

2.1What a quantum computer breaks#

Almost every blockchain account is an elliptic-curve key: ECDSA over secp256k1 on Ethereum and every EVM chain, Robinhood Chain included, and Ed25519 on Solana and many others. Both rest on one problem, the elliptic-curve discrete logarithm. Shor's algorithm solves that problem in polynomial time on a large, fault-tolerant quantum computer. With it, a public key gives up its private key, and whoever holds the private key can sign anything.

The public keys are already out:

• On an EVM chain an address is a hash of the public key, but the public key can be recovered from any signature the account has made. Every account that has sent one transaction has published it.
• On Solana the address is the Ed25519 public key, published from the first moment.

So an attacker does not need to watch anyone. The chain's history is the list of targets, and a key that is safe today is only safe until such a machine exists. Hash functions are different: the best known quantum attack on a hash preimage is Grover's search, which only takes the square root of the work, and no shortcut of Shor's kind is known for it. Signatures built only from a hash function keep about half their bits of security, which is why their sizes are chosen with that in mind.

2.2Checking a quantum claim#

A product can add post-quantum cryptography somewhere and still leave its funds behind an elliptic-curve key: post-quantum encryption of messages, a post-quantum seed that derives Ed25519 keys, a quantum-safe login in front of an ECDSA wallet. None of that changes who can move the money. Four questions decide it:

1. Which signature does the contract or the chain check before funds move? If it is ECDSA or Ed25519, the funds are not quantum-resistant.
2. Can any other key move the funds or replace the code? An admin, an owner, an upgrade key. If that key is ECDSA, it is the weak point, whatever the users' keys are.
3. Is the one-time rule enforced on chain? A one-time scheme that the contract lets sign twice is forgeable.
4. Can the claim be checked in deployed code? Verified source on chain, and the lines that do the check.

The rest of this page answers the four questions for Ostra, with the lines.

2.3How an Ostra key works#

Ostra uses the Winternitz one-time signature (WOTS), the oldest and simplest hash-based signature, with Keccak-256 as its only primitive. The contract library is src/Wots.sol; the TypeScript signer that agents run is byte-compatible with it wots.ts:25-33, and the Solidity tests check signatures made by the SDK Wots.t.sol:32-40.

The parameters are constants of the library Wots.sol:20-27.

Making a key#

Every key comes from the agent's 32-byte master seed, its keychain and its index. The seed of key i iskeccak256("OSTRA/WOTS/DERIVE/v1" ‖ master ‖ keychain ‖ i); from it come the salt and the 67 chain secrets, and each secret is hashed 15 times to its chain end wots.ts:122-124. No secret ever leaves the agent's machine: only key roots and, once made, signatures.

Signing and verifying#

The message is hashed with the key's salt into a 32-byte digest, which is read as 64 digits from 0 to 15. Three more digits hold a checksum, the sum of 15 − digit over the 64. For each of the 67 digits d, the signature carries the chain secret hashed d times.

The verifier hashes each revealed value the remaining 15 − d times, rebuilds the key root from the 67 ends it reaches and compares it with the root stored on chain Wots.sol:33-79. Every hash step is keccak256(salt ‖ chain ‖ position ‖ value), so a search for a preimage at one point cannot be reused for another key, chain or position Wots.sol:9-10.

Forging a signature for a message nobody signed would mean producing, for some chain, a value from before the revealed one: a preimage of Keccak-256. Raising one message digit lowers the checksum, so every other message needs at least one chain to go back. The security of the scheme rests only on properties of the hash function, preimage and second-preimage resistance, with no number-theoretic assumption for Shor's algorithm to break. A 224-bit chain value keeps about 112 bits against Grover's search.

2.4Why a key signs once#

One signature reveals one point on every chain. A second signature with the same key, for another message, reveals a second point; on every chain the lower of the two is now public, and anyone can sign any message whose digits all sit at or above those points. The library states it plainly: two signatures from one key let anyone forge a third Wots.sol:17-18. So every Ostra key signs exactly one message, and two layers make sure of it: the contracts, and the signer.

2.5Rotation, enforced on chain#

A vault stores one key root and a nonce. A spend carries the signature and the root of the next key. The signed message is

"OSTRA/VAULT/EVM/v1" ‖ chainid ‖ vault ‖ nonce ‖ nextKeyRoot ‖ action ‖ params

OstraVault.sol:276-283. The vault recovers the root from the signature, and before it calls anything else it replaces its key root with nextKeyRoot and increments the nonce OstraVault.sol:285-351. The signature is bound to this chain, this vault, this nonce and every parameter that moves value, and after it lands the key it was made with no longer opens the vault. A replay fails, a changed recipient fails, and the old key is worthless even if its secret were later found.

The same pattern is used wherever Ostra checks a WOTS signature:

• a shielded deposit's approval key rotates on every batch approval OstraPool.sol:382-399;
• a shielded leaf has its own key and moves once, whole, to the destination it signed OstraPool.sol:491-507;
• the owner of Ostra's upgradeable code rotates its key on every call it authorizes OstraUpgradeOwner.sol:129-142.

2.6Never signing twice#

The contracts make an old key useless once a signature lands. The danger left is a key that signs two messages before either lands, for instance an agent that crashes after signing and signs something else on restart. On one machine the signer makes that impossiblewots.ts:5-18:

• There is no raw sign function. Every signature goes through a keychain that writes it to disk before returning it, so a transaction that did not land is sent again with the identical bytes.
• The keychain refuses to sign a different message with an index that already signed wots.ts:306-331.
• A machine restored from the seed has no local records, so with the relayer it first asks the relayer's signature escrow whether that key already signed, and resends what it finds. If the escrow cannot be read, it signs nothing. The relayer itself refuses a second message for a key root it has seen gate.ts:83-87.
• An operation that would fail is never signed, because a spend that reverts does not rotate the key. Every vault operation is simulated first, from the relayer's account, with a throwaway key put in place of the vault's own quote.ts:5-10.
• A swap is the one operation whose outcome depends on the market between signing and landing. A vault swap that fails inside Uniswap still uses up its key and moves nothing, so a signed swap never leaves the key stuck OstraVault.sol:67-81.
• A zero next key root is refused before signing, since no key could ever sign for it messages.ts:19-24.

2.7What it costs#

A WOTS signature is 1,892 bytes against 65 for ECDSA, and its check hashes up to 990 times. Before signing, Ostra budgets 400,000 gas for a vault spend: the heaviest non-swap spend measured on the mainnet fork, 275,668 gas, plus about 50,000 that WOTS verification adds over an ordinary signature, rounded up relay.ts:86-91. What the agent actually pays is the gas its transaction is simulated to use, at Robinhood Chain's L2 prices, in USDG through the relayer.

2.8What is quantum-resistant today#

This is the complete list of keys that authorize anything in Ostra. The security page gives each one's exact powers.

Protected by WOTS#

Still secp256k1, and the most each could cost#

Every transaction on Robinhood Chain, as on any EVM chain today, is signed with secp256k1 by the account that sends it; no application can change that. What Ostra changes is what a sender decides. The relayer, the aggregator and the keeper carry calls that WOTS keys, or a vault's own crank, authorized, so a broken sender key can delay a call or refuse to send it, but never alter or forge one. The worst case is the most each key could cost if a quantum computer broke it.

A trader who buys from an ordinary wallet rather than from a vault is protected by that wallet's own key, as anywhere else.