Skip to main content

Introducing Post-quantum Security to Signatures on Substrate

Elizabeth Binks

Originally posted on Medium

ChainSafe is proud to announce the completion of a collaboration with xx network, one of the world’s first quantum-resistant and privacy-focused blockchain ecosystems.

A few months back, xx network enlisted our help to implement Winternitz One Time Signatures (W-OTS+) for Substrate-based chains and automated Placards generation. The primary goal of this engagement was to introduce post-quantum-security into signatures on Substrate.

Technical highlights
For context, W-OTS+ is a quantum-resistant digital signature scheme that uses relatively small key and signature sizes. And the xx network is a layer one blockchain co-founded by cryptography pioneer David Chaum. XX network is unique in its efforts to guard against cryptography-breaking quantum computing.

This collaboration had two focal points. The first is an implementation of an independent W-OTS+ crypto library that can be used in any context. The second is a Substrate Pallet and Off Chain-Worker Implementation to introduce the W-OTS+ signature scheme and Placards into a Substrate runtime environment.

Both implementations are novel to the Rust-Substrate ecosystem. There’s an existing Golang implementation, but to foster interoperability with Substrate-based chains, the W-OTS+ scheme has been written in Rust.

This package of technologies, therefore, can be regarded as an attractive option for future implementers from various language backgrounds.

Broader implications

W-OTS+ is suitable for post-quantum environments as it’s a hash-based signature scheme. Unlike the current signature schemes generally used in blockchains (e.g., ECDSA, Schnorr, BLS, etc.), which are based on the hardness of the discrete logarithm problem, hash-based schemes are based on the hardness of finding the preimage of a hash.

Unlike the former, there is no efficient quantum algorithm for the latter, making hash-based signature schemes quantum-resistant.

Hash-based cryptography is not the only approach being proposed for a post-quantum world. Isogeny and lattice-based approaches both hope to address the one-time-use limitation of hash-based signature schemes.

However, following the unexpected critical vulnerabilities recently discovered in a NIST finalist SIDH, hash-based cryptography remains a safe approach.

Given that W-OTS+ are one-time signatures, each time a signature is revealed, part of the private key can potentially be recovered. Thus, re-using a private key for multiple signatures eventually leaks the entire private key.

To work around this issue, for the xx network’s use case, a set of keys derived from the same seed and merkleized is published as a validator’s public key. Then, to validate a signature, a merkle proof of inclusion within the tree with the published root is used. The merkle tree of keys is referred to as a “Placard” in the implementation, which can be seen as a simplified version of the XMSS signature scheme.

Summary

As the need for post-quantum cryptography draws closer, the xx network is ensuring its privacy-preserving tech stack is quantum-secure.

This stack includes a private messenger app backed by a mixnet; a novel wallet generation mechanism called Sleeve, which allows embedding a W-OTS+ public key as a backup for any other cryptocurrency wallet — and now, the first step towards integrating quantum secure cryptography into the xx network’s Substrate-based blockchain.

The newly developed W-OTS+ crypto library already empowered the xx network team to implement Sleeve wallet generation in Rust and cross-compile it to WASM for usage in web browsers. Any user can now generate a quantum-ready wallet for any cryptocurrency directly in the xx network web-based wallet and staking app.