Espra PQCrypto: Preparing for the Post-Quantum World

Why Post-Quantum Cryptography?

Ever since the 90s, we’ve known that quantum algorithms like Shor’s algorithm [Sho94] and Grover’s algorithm [Gro96] would eventually threaten the security of existing cryptographic systems.

Despite this, most systems still rely on classical algorithms, as quantum computers were seen as a distant threat that may never come. This has changed in recent years.

We are seeing consistent advances in quantum computing on two critical axes: increasing number of qubits and reduced error rates — as seen recently with Google’s Willow quantum processor [GQAI24].

We’re also seeing breakthroughs in quantum algorithms such as improvements to Shor’s algorithm that reduces the size needed of quantum circuits from O(n2) to just O(n1.5) [Reg23].

At the current rate of progress, it seems reasonably likely that today’s public-key cryptosystems, as used in systems like Bitcoin and TLS, will be broken by quantum computers by around 2040.

In light of this, we will be using a range of post-quantum cryptographic primitives throughout Espra, and will keep updating them based on developments in post-quantum cryptography.

What is Post-Quantum Secure?

It’s important to note that, within the cryptographic community, with the exception of one-time pads [Mil82] we don’t really know if anything is truly secure.

For all we know, it could be that P = NP [Coo71] and that all of today’s cryptography can be broken by a classical computer. So, instead we depend on:

• Ongoing cryptanalysis of cryptosystems to surface previously unknown weaknesses. It can sometimes take decades to find these vulnerabilities.

• A strong intuition built up over a lifetime. This is so rare that most of today’s major protocols all use crypto designed by just one man and his collaborators — Daniel J. Bernstein [Gut16].

So it’s important to be cautious. What we believe to be post-quantum secure may not be. Especially since we don’t yet have viable quantum computers to test against.

For example, of the 69 algorithms that made it into the NIST Post-Quantum Cryptography competition in 2017, the majority are now broken — many using just classical computers.

With regards to NIST, one should apply reasonable caution to their standards as they have a proven history of being used by the NSA to backdoor cryptographic primitives, e.g. Dual EC-DRBG.

It’s also important to note that cryptography is about trade-offs. Certain algorithms might offer stronger security than others, but be millions of times slower. There is no single right choice.

Hash Functions

Hash functions take arbitrary-sized data as input and yield a fixed-sized output. Since these functions are deterministic, they always yield the same output for a given input, e.g.

hash("Alice") = "3bc510"
hash("Bob")   = "cd9fb1"
hash("Alice") = "3bc510"

Modern hash functions like SHA-256 [FIPS180-2] and SHA-3 [FIPS202] are thought to be:

1. Collision-resistant, i.e. given a hash function H, it is infeasible to find two distinct inputs a and b such that H(a) = H(b).

   The standard method for finding collisions on classical computers, the “parallel rho” method [OW95], is still cheaper than any proposed quantum method for collision search [Ber09].

2. Preimage-resistant, i.e. given a hash function H and the hash output x, it is infeasible to find an input a such that H(a) = x.

   As long as nothing is known about the input that will help to reduce the search space, attackers would need to brute-force all possible inputs to find a preimage.

   For an n-bit hash function, the complexity is on the order of 2n on a classical computer, i.e. for a 256-bit hash function, that’s well beyond the number of atoms in our galaxy.

   On quantum computers, Grover’s algorithm can bring this complexity down to 2n/2, i.e. a 256-bit hash function only has 128 bits of post-quantum security.

   Thankfully, Grover’s algorithm is considered non-parallelizable, so 2128 is a massive number of permutations for a single quantum computer to churn through.

Of course, there might be structural elements of specific hash algorithms that we don’t know about that might allow for faster quantum cryptanalysis.

In order to hedge against this, we’ll be using a “combo hash” as the initial hash function in Espra:

BLAKE3_TURBOSHAKE256_512

This will produce a 512-bit output by concatenating 256 bits of output from each of the underlying hash functions: BLAKE3 [OAN+19] and TurboSHAKE256 [BDH+23].

• BLAKE3, based on the ChaCha20 stream cipher, is a highly versatile cryptographically-secure hash function that also works as an XOF, KDF, PRF, MAC, etc.

  Derived from BLAKE, one of the SHA-3 finalists, BLAKE3 is designed to be super fast, e.g. by sacrificing what is considered to be unnecessary rounds of hashing [Aum19].

  It uses a Merkle tree structure that gives it great performance while allowing clients to efficiently verify the integrity of small portions of data without having to download everything.

• TurboSHAKE256 is based on the exact same Keccak sponge construction [BDP+08] that became SHA-3, and is even by the same team.

  Like BLAKE3, it combines fewer rounds of hashing with a tree structure to be a lot faster than SHA-3, and is a generalization of what was previously defined as KangarooTwelve [BDP+16].

Based on the current state of cryptographic research, this should provide at least 128 bits of security against collision, preimage, and 2^nd preimage attacks on quantum computers.

While a combo hash function might seem like overkill, by using two distinct hash families, we will buy ourselves some breathing room if either of them turn out to be broken.

The additional storage cost, compared to say SHA-256, should be reasonably offset by the two underlying hash functions being a lot faster and significantly more versatile.

For example, as both of our hash functions are XOFs (eXtensible Output Functions), it means we can use the same construct for other purposes, i.e. not need separate key derivation functions, etc.

Digital Signatures

Digital signatures are used to verify that a message was created by a specific entity. This is often done using public/private key pairs, where the private key is kept secret and used to sign messages.

Unfortunately, most of today’s popular digital signature schemes are based on mathematical structures that we know quantum computers can break once they’re powerful enough.

For example, ECDSA [ANSIX9.62] is not quantum-secure, which means that it’s only a matter of time before someone with a quantum computer cracks all of Satoshi’s private keys and takes all his Bitcoins.

To protect against similar attacks, Espra requires users to create separate signing keys for each security level of our MultiSec framework — with each level using a different signature scheme.

• High-Security Keys — these are used for sensitive operations like account recovery, updating signing keys, moving large sums of money as defined by a user within any 24-hour window, etc.

  We will initially use the SPHINCS+ signature scheme [BHK+19] for these keys. This is hash-based in the lineage of Lamport signatures [Lam79], the very first digital signature scheme.

  As such, its security properties have been extensively studied and is thought to be quantum-secure as long as the underlying hash function is secure.

  Unlike other hash-based signature schemes like XMSS [BDH11] and LMS [RFC8554], which require careful tracking of what’s been signed to avoid leaking the private key, SPHINCS+ is stateless.

  But on the flip side, SPHINCS+ produces really large signatures, e.g. compare the classical scheme used by Ethereum with a SPHINCS+ parameter set that provides ~256 bits of security:

  Scheme/Parameters	Public Key Size	Signature Size
  ECDSA-secp256k1	64 bytes	65 bytes
  SPHINCS+-256f	64 bytes	49,856 bytes

  When NIST standardized SPHINCS+ as SLH-DHA [FIPS205], it set the requirement that each key should be able to sign up to 264 messages — that’s 18,446,744,073,709,551,615 messages.

  This is unncessarily wasteful. As such, we will look into finding an alternative parameter set for SPHINCS+ that produces smaller signatures:

  • Since high-security keys are meant to be used relatively infrequently, it would be fine for those keys to take slightly longer for key generation and signing.

  • Experimentation by others already shows improvements, e.g. just 14,208 byte signatures [KP22] if each key can only sign up to 230 messages, i.e. over a billion messages.

  This will also result in faster verification times — which can be sped up even more by instantiating SPHINCS+ with TurboSHAKE instead of the SHAKE hash function specified in SLH-DHA.

• Medium-Security Keys — these are used for actions that involve Transferable resources, e.g. paying for things, moving tokenized assets, voting, etc.

  As these will be used reasonably frequently, they need to have a small public key size, signature size, and be fast to verify. There’s no obvious post-quantum choice here, e.g.

  Scheme/Parameters	Public Key Size	Signature Size	Verification Time
  Dilithium-5 (ML-DSA-87)	2,592 bytes	4,627 bytes	1.74x
  Falcon-1024	1,793 bytes	1,280 bytes	1.00x
  HAWK-1024	2,440 bytes	1,221 bytes	1.89x
  MAYO5	5,008 bytes	838 bytes	7.39x
  QR-UOV-V (31, 1120, 120, 10)	58,564 bytes	807 bytes	2,700x
  SPHINCS+-256f	64 bytes	49,856 bytes	1,200x
  UOV-V-pkc	446,992 bytes	260 bytes	12.66x

  While we can rule out SPHINCS+ for its massive signatures and slow verification speeds, there are lots of trade-offs for all of the other signature schemes:

  • Dilithium [DKL+17] was chosen by NIST and standardized as ML-DSA [FIPS204], is fast, but has large signatures, and lattice-based cryptography is still on shaky grounds.

  • Falcon [FHK+20], another lattice-based scheme, is fast, has smaller signatures, but is hard to implement safely as it uses floating-point maths, and has its security in question [GJK24].

  • HAWK [BBD+23] is somewhat similar to Falcon and avoids the need for floating-point maths, but it’s based on the lattice isomorphism problem that hasn’t been well-studied so far.

  • UOV (Unbalanced Oil and Vinegar) [KPG99] [BCD+23] is an old multivariate scheme that has held up over decades. It has super small signatures but is let down by huge public keys.

  • MAYO [Beu22] [BCC+23] is a UOV variant with much smaller public keys, slightly larger signatures, and faster verification times. Its security is not that well explored though.

  • QR-UOV [FIH+23] is another UOV variant with slightly smaller public keys and slightly larger signatures, but it currently has extremely slow verification times.

  We’ll be using MAYO₅ as the initial signature scheme for our medium-security keys as it offers the smallest signatures without blowing up the public key size or verification time.

  We will revisit this decision as more cryptanalysis is done on MAYO. Even if it gets broken, we’ll still have better security than most chains thanks to our multi-level key design.

• Low-Security Keys — these are used for most day-to-day actions, e.g. posting comments, sending messages, liking something on social media, etc.

  As these are likely to be the most common transaction signatures within Espra blocks, we optimize for:

  1. Small signature size
  2. Fast verification
  3. Small public key size
  4. Fast signing

  We will initially use the Ed25519 signature scheme [BDL+11] for these keys. Based on elliptic curve cryptography, this is a fairly well-established classical signature scheme:

  • Designed to be relatively safe to implement
  • 32-byte public keys
  • 64-byte signatures
  • Fast signing and verification

  The fact that it’s not quantum-secure is not a major issue for us because:

  1. Low-security keys won’t be used to secure any tokenized assets with value. As such, even if such a key gets compromised, the damage will be relatively minimal.

     At most, there could be some damage to a user’s reputation if an attacker with a quantum computer uses it to post fake comments as someone else, create fake alerts, etc.

  2. There will only be a small window of time for attackers to cause any mischief. As soon as there’s any evidence that Ed25519 is broken, we’ll disable it across all of Espra.

     All users will then need to upgrade their low-security keys to whatever quantum-secure scheme we deem to be best-suited at that point in time.

  3. The SPHINCS+ signature scheme that we’re using for high-security keys is considered a fairly conservative choice by the cryptographic community.

     Since all users will have a predefined high-security key, they can upgrade their low-security keys without the risk of anyone stealing their assets in the meantime.

  It’s extremely likely that we would replace Ed25519 with a quantum-secure scheme long before quantum computers are able to break it.

  The broader cryptographic community is also actively interested in finding a quantum-secure scheme that has small public keys, signature sizes, and fast verification/signing.

  In the meantime, thanks to our tiered security design, we can enjoy the size, speed, and security benefits of Ed25519 without worrying about the risk of quantum computing.

Just like users, nodes will also have separate signing keys for each security level. These will be used to authenticate peers as well as produce blocks, etc.

All signatures by higher-level keys will also be accompanied by signatures by lower-level keys, e.g. a medium-security signature will also include a signature by a low-security key.

This gives us additional security, e.g.

• If a device gets compromised, a high-level key might be sitting in the clear in RAM while a low-level key might ironically be better protected on something like a Secure Enclave.

  Note: this is due to the fact that secure co-processors tend to be very slow in adding support for new cryptographic primitives.

• If a higher-level signature scheme turns out to be broken, users would still be protected by the security of their lower-level security keys.

As this space is fast-moving, we will be keeping an eye on the NIST Post-Quantum Cryptography Additional Digital Signature Schemes competition [link] for any relevant developments.

Symmetric Encryption

Symmetric encryption helps keep your data safe from prying eyes. It differs from public-key encryption in that it uses the same key to both encrypt and decrypt the data.

Similar to hash functions, the battle-tested symmetric-key ciphers of today like AES-256 [FIPS197] and ChaCha20 [Ber08] are thought to be quantum-resistant.

As with hash functions, Grover’s algorithm will let quantum computers reduce the security of an n-bit cipher to n/2 bits, i.e. a 256-bit cipher will only have 128 bits of security.

But the current consensus within the cryptographic community is that this should still be safe for the foreseeable future — especially since Grover is considered non-parallelizable on quantum computers.

We will be using the ChaCha20 stream cipher combined with the Poly1305 message authentication code [Ber05] as the initial symmetric encryption mechanism in Espra:

AEAD_XCHACHA20_POLY1305

We combine the ChaCha20 and Poly1305 primitives into an AEAD (Authenticated Encryption with Associated Data) in a manner similar to RFC 8439 [RFC8439].

The only difference is that we’ll be using a 192-bit nonce [Arc20] like XSalsa20 [Ber11] rather than a 96-bit nonce. This will allow for the use of random nonces without worrying about nonce reuse.

We chose ChaCha20-Poly1305 over AES-GCM as the latter is hard to implement safely. Further, blocks are just 128 bits even in AES-256, so post-quantum security may be compromised.

ChaCha20-Poly1305 has held up against cryptanalysis so far, and is used in modern protocols like TLS 1.3. Its 256-bit keys is expected to provide at least 128 bits of post-quantum security.

We will use the AEAD construction for all of Espra’s symmetric encryption needs, i.e. encrypting asynchronous messages, securing the transport layer, encrypting data at rest, etc.

Key Encapsulation

KEM (Key Encapsulation Mechanisms) allows senders to share secret keys with recipients without exposing the keys to any eavesdroppers. The secret keys can then be used to create encrypted channels.

Traditional methods of doing this, e.g. Diffie-Hellman key exchange, are not quantum-secure. So attackers are recording encrypted traffic today so they can decrypt it later with quantum computers [Gre13].

We don’t yet know which, if any, of today’s potential post-quantum KEMs will stand the test of time, and thus will use a 3-way hybrid KEM within Espra:

• Classic McEliece [Mce78] has the strongest security track record of all post-quantum KEM proposals. It is based on an NP-hard problem of decoding a general linear code.

  We’ll use the following variant as it offers a decent balance between performance and output sizes:

  mceliece6688128
  

• Kyber [BDK+18] is a lattice-based KEM based on the module learning with errors (M-LWE) problem that won the NIST post-quantum competition.

  Standardized as ML-KEM [FIPS203], we’ll be using the following variant:

  ML-KEM-1024
  

• X25519 [RFC7748] is an elliptic-curve Diffie-Hellman key agreement protocol that is widely used in modern protocols like TLS 1.3 and SSH.

  While it is not quantum-secure, it’s a good fallback just in case the other options turn out to be easily breakable like previous post-quantum candidates, e.g. like SIDH [Rob23].

While it is still early days in terms of knowing which post-quantum KEM will stand the test of time, our 3-way hybrid should give our users better protection than most protocols.

Commitment Schemes

Commitment schemes let people commit to values without revealing them. This is useful as part of protocols where players need to prove that they’ve played a certain way.

For example, when playing “head or tails” over the internet, the coin tosser could change the outcome to their advantage once they know everyone else’s choices.

alice = "heads"
bob = "tails"

To avoid this, each player could hash their choice with a random string of their choice, and share the resulting hash-based commitment instead:

alice_commitment = "9edeed041fec8ada5c05286ef5e96d5c1556cb36a55217435fd41e2991365320"
bob_commitment = "62b7d082777fb1b037a37a5d27ee9562e8c042604801924e9c902d8372f81ff7"

Assuming the commitments were made properly, i.e. with a secure hash function and a long enough random string, no-one would be able to guess at anyone’s choice.

Then, once the coin toss has been made, winners can reveal their choice and random string, e.g.

alice_choice = "heads"
alice_random_string = "KORuIBdrBHOrKzPGt4GDcQPmdM3lrXQ87BcAup5IXlRKhABK"

Others can then hash these together and verify that it matches the original commitment — thus verifying that Alice originally chose “heads”:

hash(alice_choice + alice_random_string)
"9edeed041fec8ada5c05286ef5e96d5c1556cb36a55217435fd41e2991365320"

Similarly, Merkle trees are a way to commit to multiple values in a way that allows for efficient verification of any subset of the data. They are constructed by:

• Splitting the data into n chunks, e.g. Chunk1 .. Chunkn.

• Hashing each of the chunks to produce the leafs of a tree, e.g. H1 .. Hn.

• Hashing the hashes together in a tree-like manner to produce a root hash.

This “Merkle root” then serves as a commitment that can be used to verify any subset of the data by providing just the relevant subset of raw data and sibling hashes:

                HMerkleRoot
               /          \
             HX            HY
            /  \          /  \
          HA    HB       HC    HD
         /  \  /  \     /  \  /  \
        H1  H2 H3  H4   H5  H6 H7  H8

Merkle trees are one of the oldest data structures in cryptography and are secure against quantum computers as long as they use a secure hash function.

Unfortunately, Merkle proofs can become extremely large as they need to include not just the relevant raw data, but also all of the sibling hashes all the way up to the root.

As a result, projects have been looking to polynomial commitments, a highly-compressed algebraic alternative to hash-based structures for committing to large amounts of data.

For example, Ethereum is now using KZG polynomial commitments [KZG10] within:

• Verkle Trees [Kus18] [Fei21], a more efficient way to commit to the state of the chain.

• Proto-Danksharding [EIP4844], a mechanism for rollups to add cheaper data to blocks that are secured using DAS (Data Availability Sampling) [ASB18].

But since KZG requires a trusted setup and is not quantum-secure, we will not be using it despite its efficiency. We’ll instead:

• Stick to hash-based commitments for most use cases.

• Use zero-knowledge proofs to prove that Merkle roots of encoded data are correct [But19].

This will allow us to support use cases like statelessness and data availability sampling without compromising on security.

Computational Integrity

Computational integrity is the ability to prove that a certain computation has been performed correctly, e.g. the execution of smart contracts within a transaction.

The typical way most chains do this is by using “naive replay”, i.e. by executing all of the transactions themselves. This is unnecessarily redundant and wasteful.

In Espra, nodes only execute transactions when:

• Generating checkpoints that allow for the pruning of old transaction data and internal state.

• There’s a conflict between nodes about the resulting state, e.g. due to implementation bugs in the execution layer.

In circumstances like these, we use STARKs [BBH+18] to resolve these conflicts and prove that the resulting state is correct. Compared to other systems like SNARKs [Gro16]:

• STARKs do not require a trusted setup of any kind, and thus have transparent security.

• STARKs are built on top of hash functions, and thus are thought to inherit their quantum-security.

While STARKs are fantastic, and can even be used to generate zero-knowledge proofs, i.e. proofs that maintain the privacy of the input data, the proofs are large and take a lot of time to generate.

Typical optimizations used by real-world STARK systems often compromise their post-quantum security, e.g.

• The Groth16 SNARK is often run on top of a STARK proof to create much shorter proofs, but ends up needing a trusted setup and is not quantum-secure.

We’ll instead look to more foundational optimizations to make the proofs more palatable, e.g. using binary finite fields [DP23] [But24], using multivariate polynomials [Set20], as well as dedicated circuits for:

• Hashing and processing Merkle trees — optimizing for common usecases like data availability and statelessness.

• Recursive STARK proofs — by combining multiple STARK proofs into a single proof, we can dramatically reduce the overhead of proofs.

Privacy-Preserving Computation

Privacy-preserving computation is the ability to perform operations on data without knowing anything about the inputs or outputs. Unfortunately, there is no current mechanism that:

• Maintains privacy in the face of quantum computers.

• Is efficient enough to be used for real-world applications.

Since we’d want to have information-theoretic security for private data, i.e. for it to be secure against adversaries with unlimited resources, we’ll initially keep all private data off chain in Espra.

By default, private data will only be stored locally on trusted machines, i.e. on a user’s device, and privacy-preserving computation will take place locally with side-channel protection to avoid leakage.

For use cases where users want to do privacy-preserving computation on remote machines, we don’t currently trust any approach that would allow for this.

We’ll instead provide a privacy toolkit of various techniques for app developers, and apps using it will need to be explicitly approved by users:

• Differential Privacy — allowing for privacy-preserving statistical analysis of aggregated data by adding noise to the data.

• Fully Homomorphic Encryption — allowing for arbitrary computations on top of encrypted data.

• Linear Secret Sharing — allowing for secrets to be distributed across multiple parties so that a quorum of them is needed to reconstruct the secret.

• Secure Multi-Party Computation — allowing for multiple entities to jointly perform calculations without revealing anything about the inputs.

• Trusted Execution Environments — allowing for secure execution of code in a secure area of a processor.

• Zero-Knowledge Proofs — allowing parties to prove that they know a secret without revealing anything about the secret itself.

We’ll keep adding to this toolkit as secure techniques develop, e.g. blind quantum computing [BKB+12] might eventually allow for true privacy-preserving remote computation.

Verifiable Delay Functions

VDFs (Verifiable Delay Functions) [BBB+18] let provers show that they’ve spent a certain amount of time doing work, while producing results that can be verified quickly.

This asymmetry, in terms of the time spent by provers and verifiers, is useful for creating a proof of work [JJ99] that is very useful, e.g. to protect nodes from resource exhaustion attacks.

Most existing VDFs [Wes18] [Pie18] are based on structured problems in mathematics which can be broken by quantum computers, thanks to the likes of Shor’s algorithm.

To protect against this, we’ll be using ZKBdf [TSL+23] as our initial VDF:

• It’s a challenge-response-based VDF that is built on top of a ZKBoo [GMO16] zero-knowledge proof of knowledge of a secret key, and offers provable quantum-security.

• ZKBdf goes beyond standard VDFs through its use of a “prover secret”. This may prove useful to us in some other contexts, e.g. post-quantum authentication.

In the future, we may switch to a different VDF. This will most likely just be for shorter proofs, as the underlying principles behind ZKBdf is reasonably sound.

Secure Messaging

Secure messaging allows for entities to communicate with each other without anyone being able to eavesdrop. We’ll combine elements from existing protocols for the Espra Messaging Protocol:

• Noise Protocol Framework [Per18] — a framework for creating bespoke cryptographic protocols with a much simpler state machine than TLS.

• WireGuard [Don17] — a fast, modern, and secure VPN tunnel that supports dynamic mesh topologies where nodes might move from one IP to another, e.g. due to network changes.

• HTTP/3 [RFC9114] — builds on top of the UDP-based QUIC transport protocol for stream multiplexing, per-stream flow control, and low-latency connection establishment.

• PQXDH [KS23] — the post-quantum key agreement protocol created by Signal to support secure messaging between users where parties might be offline.

• PQ3 [ASE24] — the post-quantum messaging protocol created by Apple to support secure messaging with ongoing re-keying for forward secrecy.

We are designing the protocol to best suit our needs, e.g. unlike HTTP which creates lots of ephemeral connections, Espra creates fewer long-lived connections.

• So, instead of sharing the certificates on every connection like HTTPS, we can minimize the cost of the 1MB Classic McEliece public keys by only sharing them on the initial connection.

• These can be signed by the Espra Host’s high-security key, which at just 64 bytes for a SPHINCS+ key will be less than 10MB for pre-bundling the public keys for the top 100,000 Hosts.

• The root certificates for the Espra Hosts will be structured as a verifiable data structure [ELC15] — allowing for easy verifiability as the data gets updated over time.

We will keep revising the Espra Messaging Protocol as things develop on the post-quantum landscape, e.g. our choice of KEM, symmetric encryption, VDF, etc.

Threshold Signature Schemes

TSS (Threshold Signature Schemes) [AHS20] allow for joint ownership of a private key by multiple participants:

• DKG (Distributed Key Generation) lets the participants create a key so that that each of them has a share of it.

• A threshold of t out of n participants are then needed to cooperate to produce valid signatures with that key.

We use TSS for network-owned accounts, i.e. accounts on other chains, like Bitcoin and Ethereum, that are collectively owned by nodes on the Espra network.

As most chains tend to use either ECDSA (often with the secp256k1 curve) or Ed25519 signature schemes, we’ll use:

• CGGMP20 [CGG+20] for the chains using ECDSA.

• FROST [KG20] [Hal23] for the chains using Ed25519.

As neither ECDSA nor Ed25519 are quantum-secure, those keys will inevitably become insecure. Once chains upgrade to more secure signatures, we can look into corresponding threshold schemes.

In the meantime, for chains that support account abstraction, we could deploy a contract that checks a STARK proof instead of signatures for verifying that a transaction has been authorized.

As this is likely to be very expensive on most chains, we may want to hold off until quantum computing becomes more of a threat, or limit usage for accounts with high value assets.

Feature Negotiation

In protocols that support feature negotiation, peers can negotiate the specific cryptographic primitives that they want to use while they’re setting up a connection to each other.

For example, a web server using TLS for HTTPS might support a range of cipher suites, e.g.

TLS_AES_128_GCM_SHA256
TLS_AES_256_GCM_SHA384
TLS_CHACHA20_POLY1305_SHA256
TLS_DH_RSA_WITH_DES_CBC_SHA
TLS_ECDH_ECDSA_WITH_RC4_128_SHA
TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256

This lets the server communicate with outdated clients that might not otherwise support the latest cipher suites. While this backwards compatibility is useful, it:

1. Requires a lot of extra code to maintain all the different primitives. This massively increases the potential attack surface and vulnerabilities can stay hidden for a long time.

2. Can often be exploited by attackers to downgrade security, e.g. by forcing peers to use weaker cryptographic mechanisms like in the FREAK attack [Sch15].

To avoid these issues, Espra will not support feature negotiation at the protocol level. We will:

• Require that everyone use the same set of cryptographic primitives for each version of the Espra protocol.

• Only support, at most, the latest 2 major versions of the protocol.

• Provide a reasonable window of time, e.g. a month, for everyone to upgrade to the latest version of the protocol, after which the previous version will be disabled.

Whilst forcing everyone to upgrade might seem aggressive, it will make the protocol more secure and easier to maintain — especially if quantum computing starts disrupting everything.