一种高效的范围证明方案

An Efficient Scheme of Range Proofs

在区块链系统中,由于交易金额是敏感数据,对金额的隐私保护是一个热点话题,它不仅要求将金额隐藏,而且需要提供该金额在某个公开范围的一个证据,许多研究学者采用承诺方案来隐藏交易金额以及绑定该金额与对应的承诺值,同时该承诺需要一个范围证明用来证明该金额在一个合法的区间内,比如[0, 2^64).迄今为止验证速度最快的范围证明方案是2017年BüNZ B等人提出的Bulletproof方案,该方案已广泛应用于区块链系统中.本文在该方案的基础上通过构造新的多项式承诺方案并结合向量内积承诺方案,提出一种高效的范围证明方案.本文方案无需可信第三方的参与,并且证据生成的时间复杂度约为(1.25n+6.5 log n+4)ct,证据验证的时间复杂度约为(0.5n+4.5 log n+5)ct,而证据的长度为(19+2 log n)cs,这里ct表示椭圆曲线标量乘运算所需的时间, cs表示椭圆曲线点的长度, n为交易金额的比特长度.与目前已知应用在区块链系统的范围证明方案相比,本文方案在证据生成耗时、证据产生长度都相当的情况下,将证据的验证速度达到最优,因而是更加实用的区块链范围证明方案.

In Blockchain system, it is a hot topic for the privacy protection of the transaction amount as the sensitive data. The transaction amount should not only be hidden, but also needs a proof which implies that the amount is in some public range. Many researchers use the commitment scheme to hide the transaction amount and bind it with the corresponding commitment. Meanwhile,the commitment scheme needs a proof to show that the amount is in a legitimate range, e.g. [0, 2^64).So far the most efficient range proof scheme with fast verification speed is the Bulletproofs scheme,which was proposed by BüNZ B et al in 2017 and is now widely used in Blockchain systems. Based on the Bulletproofs scheme, this paper presents an efficient scheme of range proofs by combining the new construction of polynomial commitments with the vector inner-product commitments. The scheme does not need a trusted third party, and the time complexity of proof generation and proof verification are about(1.25 n + 6.5 log n + 4)ct and(0.5 n + 4.5 log n + 5)ct respectively, and the size of the proof is(19 + 2 log n)cs, where ct represents the time complexity of the scalar multiplication of the Elliptic Curve, cs represents the size of the elements of the Elliptic Curve, and n is the binary length of the transaction amount. The time complexity of proof generation and the proof size of the proposed scheme match the current schemes of range proofs used in Blockchain systems, and the time complexity of proof verification is optimal. As a result, the scheme proposed in this paper is more suitable to provide the privacy protection in Blockchain systems.