Gas Friendly Post-Quantum Signatures With Truncator

Every transaction and piece of stored data incurs a cost on a blockchain. Whether it's the fees to make payments, gas costs to execute smart contract operations, or the resources required to store data, the size of the variables involved plays a crucial role in determining these costs. Reducing the size of these variables without compromising their functionality or security can lead to significant savings in communication, storage, and transaction fees.

Introducing Truncator

Truncator is a mining-based technique designed to reduce the size of various cryptographic outputs frequently encountered in blockchain systems. Truncator's key innovation involves achieving this reduction without sacrificing security.

How Truncator works

Truncator adds a few extra steps during transaction composition in return for significant benefits in reducing transaction size and associated gas costs. While this addition time is typically on the order of seconds rather than milliseconds, it is particularly beneficial for transactions where reduced variable size outweighs the need for speed. By adopting this approach, the transaction sender realizes advantages, such as reduced transaction fees, and the entire ecosystem benefits through reduced storage and communication costs.

The technique behind Truncator

This approach involves an iterative search (or mining) in the cryptographic primitives inputs or randomness to find a more efficient encrypted output. This method crafts each primitive’s output in a specific way that satisfies the modified system’s public parameters, such as requiring some specific bits of the output to be constant. This is similar to how proof-of-work mechanisms require miners to continually digest the same data with different random values until meeting a specific system need. In the case of Truncator, the system goal is to simplify the output to a certain degree.

For example, consider applying Truncator in the key generation algorithm for discrete logarithm (dlog)-based keys. Assuming all acceptable public keys have a pre-determined ℓ-bit prefix, we can perform an iterative search for a secret key \( sk \) such that the format of its derived public key \( pk = g^{sk} \) satisfies the predetermined ℓ-bit prefix. The resulting public keys would be ℓ bits smaller, thus offering reduced communication and storage costs.

Ensuring security

Security is paramount, of course, and the bit-security framework shows that Truncator does not reduce the security of the keys. The bit-security framework states that a primitive \( P \) has κ-bit security if it takes an adversary \( 2^{κ} \) operations to break it. This implies that for any attack with computational cost \( T \) and success probability \( ϵ \), it must hold that \( T /ϵ > 2^{κ} \). The intuition here is that the mining approach for truncation incurs higher attack costs, which overall offsets the reduced key space, maintaining the same level of security.

Real-world applications

The idea of an iterative search to reduce the size of keys and addresses has appeared before in the blockchain space, most notably in Ethereum proposals for addresses with a prefix of many zeroes to reduce gas fees (known as “gas golfing”). In this Truncator work, we formalize and expand this idea to multiple cryptographic primitives such as hash digests, elliptic curve cryptography (ECC) public keys, and signature outputs. For example, about 7 percent compression (2 bytes less) has been achieved in less than a second for ed25519 signatures and less than 10 milliseconds for compressed Blake3 digests. We have also explored truncation in ElGamal encryption and Diffie-Hellman-based encryption, commonly used for blockchain stealth addresses.

A new approach for hash-based post-quantum signatures

There is an exciting opportunity to construct new cryptographic schemes that leverage Truncator’s techniques during the protocol design phase, particularly in the context of post-quantum security. Hash-based signature schemes, such as Lamport signatures and their variants, are inherently quantum-resistant because their security relies on the properties of hash functions rather than on the hardness of problems like factoring large integers or computing discrete logarithms, which quantum computers can efficiently solve.

Future schemes could consider mining feasibility and securely adjust key generation or other cryptographic operations to accommodate it, thus enhancing resistance to quantum computing attacks. By optimizing the key derivation process in hash-based signature schemes, it is possible to achieve better performance and efficiency. This involves reducing the computational load and storage requirements, which is crucial for maintaining the security and usability of cryptographic systems in a post-quantum world. High-performance mining techniques can lead to more efficient generation and verification of signatures, ensuring that cryptographic systems remain robust and scalable in the face of emerging quantum threats.

Optimizing Lamport signatures

One intriguing direction involves optimizing hash-based signatures at the key derivation level, aiming for high-performance mining with significantly better results than brute forcing. For example, in traditional Lamport signatures, the private key comprises 256 independent pairs of 256-bit random values (seeds), totaling 512 elements and 16 KiB. Each sub-private key corresponds to a public key, its hash, resulting in a total of 512 elements. Typically, we sign hashed messages, where each bit in the hash corresponds to a sub-private value.

While compressing Lamport signatures typically requires techniques such as the Winternitz hash-chain variant, it can also be achieved by deriving private parts in a tree fashion structure rather than selecting them independently.

Consider signing a message consisting of all zeros. Using the top key, verifiers can derive all sub-keys via Merkle tree operations. For adjacent similar bits, we can use the corresponding tree path to reduce the number of keys required for submission. This principle also applies to adjacent set bits. By maximizing the number of adjacent bits through hash retries, we can reduce the signature payload, resulting in more optimized Lamport verification and shorter proofs.

Conclusion

Truncator presents an innovative approach to truncating the output size of cryptographic primitives, offering a computational trade-off that opens new avenues for exploration. We've highlighted its application to basic cryptographic primitives and introduced an exciting direction for optimizing hash-based signatures at the key derivation level.

Looking ahead, we see potential in extending Truncator to more advanced cryptographic primitives and crafting novel protocols that leverage mining techniques across various cryptographic protocols. These efforts hold the promise of enhancing efficiency and reducing storage costs in the blockchain ecosystem and beyond.

At Sui, we’re particularly excited about incorporating such optimizations into our roadmap for post-quantum security, ensuring that our platform remains at the forefront of innovation while maintaining robust security standards. Truncator can potentially help in more gas-friendly post-quantum signatures, contributing to a more efficient and secure blockchain environment.

To explore Truncator more deeply, check out our GitHub.