Sui Unveils Truncator for Gas-Friendly Post-Quantum Signatures

Every transaction and data storage in a blockchain incurs costs, including fees for payments, gas for smart contract operations, and resources for data storage. Reducing the size of variables involved in these transactions, without compromising functionality or security, can significantly save on communication, storage, and transaction fees.

Introducing Truncator

Truncator, a mining-based technique designed by Sui, reduces the size of cryptographic outputs in blockchain systems without sacrificing security, according to The Sui Blog.

How Truncator Works

Truncator adds extra steps during transaction composition, resulting in significant benefits by reducing transaction size and associated gas costs. Although this process takes a few seconds, it is beneficial for transactions where reduced variable size outweighs the need for speed. This approach helps reduce transaction fees and benefits the entire ecosystem by lowering storage and communication costs.

The Technique Behind Truncator

Truncator involves an iterative search in cryptographic primitives' inputs or randomness to find a more efficient encrypted output. This method crafts each primitive’s output to meet modified system parameters, such as having specific bits of the output constant. This is similar to proof-of-work mechanisms requiring miners to continually digest the same data with different random values until meeting a specific system need, aiming to simplify the output.

For example, in the key generation algorithm for discrete logarithm-based keys, an iterative search for a secret key can ensure the derived public key has a predetermined ℓ-bit prefix, making public keys smaller and reducing communication and storage costs.

Ensuring Security

Security remains paramount, and the bit-security framework shows that Truncator does not reduce key security. This framework states that a primitive has κ-bit security if it takes an adversary 2^κ operations to break it, implying higher attack costs offset the reduced key space, maintaining security levels.

Real-World Applications

The iterative search method to reduce the size of keys and addresses has appeared before in blockchain, notably in Ethereum proposals for “gas golfing.” Truncator formalizes and expands this idea to multiple cryptographic primitives, such as hash digests, elliptic curve cryptography (ECC) public keys, and signature outputs. For instance, about 7% compression has been achieved in less than a second for ed25519 signatures and under 10 milliseconds for compressed Blake3 digests. Truncator has also been explored for ElGamal encryption and Diffie-Hellman-based encryption, commonly used for blockchain stealth addresses.

A New Approach for Hash-Based Post-Quantum Signatures

Truncator's techniques offer an opportunity to construct new cryptographic schemes, particularly for post-quantum security. Hash-based signature schemes, such as Lamport signatures, are inherently quantum-resistant. Future schemes could incorporate mining feasibility, adjusting key generation to enhance resistance to quantum computing attacks. Optimizing key derivation in hash-based signature schemes can improve performance and efficiency, crucial for maintaining security and usability in a post-quantum world.

Optimizing Lamport Signatures

Optimizing hash-based signatures at the key derivation level could result in high-performance mining with better results than brute forcing. For example, traditional Lamport signatures involve a private key comprising 256 pairs of 256-bit random values, totaling 16 KiB. Each sub-private key corresponds to a public key, resulting in 512 elements. By compressing Lamport signatures through techniques like the Winternitz hash-chain variant, the number of keys required for submission can be reduced, optimizing Lamport verification and shortening proofs.

Conclusion

Truncator offers an innovative approach to reducing the output size of cryptographic primitives, providing a computational trade-off that opens new exploration avenues. Its application to basic cryptographic primitives and potential for optimizing hash-based signatures at the key derivation level has been highlighted. Future extensions of Truncator could enhance efficiency and reduce storage costs in the blockchain ecosystem. Sui is particularly excited about incorporating such optimizations into its roadmap for post-quantum security, maintaining robust security standards while fostering innovation.