带截断器的 Gas 友好型后量子签名

区块链上的每笔交易和存储的数据都会产生成本。无论是支付费用、执行智能合约操作的 gas 成本，还是存储数据所需的资源，所涉及变量的大小在确定这些成本方面起着至关重要的作用。在不影响其功能或安全性的情况下减小这些变量的大小可以大大节省通信、存储和交易费用。

介绍截断器

Truncator 是一种基于挖矿的技术，旨在减少区块链系统中经常遇到的各种加密输出的大小。Truncator 的关键创新在于在不牺牲安全性的情况下实现这种减少。

Truncator 的工作原理

Truncator 在交易组合过程中增加了几个额外步骤，从而显著降低了交易大小和相关的 gas 成本。虽然这个额外的时间通常以秒为单位而不是以毫秒为单位，但对于减少变量大小比提高速度更重要的交易来说，它尤其有益。通过采用这种方法，交易发送者可以获得诸如降低交易费用等优势，而整个生态系统则通过降低存储和通信成本而受益。

Truncator 背后的技术

这种方法涉及在密码原语输入或随机性中进行迭代搜索（或挖掘），以找到更高效的加密输出。此方法以特定方式制作每个原语的输出，以满足修改后的系统的公共参数，例如要求输出的某些特定位保持不变。这类似于工作量证明机制要求矿工不断用不同的随机值消化相同的数据，直到满足特定的系统需求。在 Truncator 的情况下，系统目标是在一定程度上简化输出。

例如，考虑在基于离散对数 (dlog) 的密钥生成算法中应用 Truncator。假设所有可接受的公钥都有预定的 ℓ 位前缀，我们可以对密钥 \(sk\) 进行迭代搜索，使得其派生公钥 \(pk = g^{sk}\) 的格式满足预定的 ℓ 位前缀。生成的公钥将小 ℓ 位，从而降低通信和存储成本。

确保安全

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

一个有趣的方向是在密钥派生级别优化基于哈希的签名，旨在实现高性能挖掘，其结果明显优于暴力破解。例如，在传统的 Lamport 签名中，私钥包含 256 个独立的 256 位随机值对（种子），总共 512 个元素和 16 KiB。每个子私钥对应一个公钥，即其哈希，总共有 512 个元素。通常，我们会对哈希消息进行签名，其中哈希中的每个位都对应一个子私钥值。

虽然压缩 Lamport 签名通常需要诸如 Winternitz 哈希链变体之类的技术，但它也可以通过以树形结构派生私有部分而不是独立选择它们来实现。

考虑对一条全零组成的消息进行签名。使用顶部密钥，验证者可以通过 Merkle 树操作导出所有子密钥。对于相邻的相似位，我们可以使用相应的树路径来减少提交所需的密钥数量。此原则也适用于相邻的集合位。通过哈希重试最大化相邻位的数量，我们可以减少签名有效负载，从而实现更优化的 Lamport 验证和更短的证明。

通过哈希重试最大化相邻位数，我们可以减少签名负载，从而实现更优化的 Lamport 验证和更短的证明。结论

Truncator 提供了一种创新方法来截断加密基元的输出大小，提供了一种计算权衡，为探索开辟了新的途径。我们重点介绍了它在基本加密基元中的应用，并介绍了在密钥派生级别优化基于哈希的签名的令人兴奋的方向。

展望未来，我们看到将 Truncator 扩展到更高级的加密基元以及制定利用各种加密协议中的挖掘技术的新协议的潜力。这些努力有望提高区块链生态系统及其他领域的效率并降低存储成本。

在 Sui，我们特别高兴能将此类优化纳入我们的后量子安全路线图，确保我们的平台始终处于创新前沿，同时保持强大的安全标准。Truncator 可能有助于实现更节省 gas 的后量子签名，从而有助于打造更高效、更安全的区块链环境。

要更深入地探索 Truncator，请查看我们的 GitHub。

热点：GAS