The main problem CT faces is to make its transaction very large and slow to verify, because it requires every transaction output to contain a rangeproof, which is a proof of zero knowledge, and the amount of proof is too small to overflow. Ordinary digital signatures are less than 100 bytes, which can be verified in less than 100 microseconds, while rangeproofs are thousands of bytes, which takes several milliseconds to verify. In fact, rangeproofs is the vast majority of transaction data in any transaction that uses them.
Although our rangeproofs based on Borromean ring signature are the fastest and smallest in the literature, they are still very large for the range we need and the untrustworthy environment.
Since 20 15, we have been working hard to improve the efficiency of rangeproofs. At the beginning of 20 17, Adam Back found that rangeproofs decreased by 24%, but the verification speed did not increase. In the meantime, we have mentioned this problem to our friends and colleagues, cryptographers Dan Boneh and BenediktBünz of Stanford University, and they are quite confident about the room for improvement.
They finally shocked us.
According to Bootle et al.' s improvement on the spatial efficiency of zero-knowledge proof based on discrete logarithm in 20 16, Bulletproofs are a form of zero-knowledge proof with higher spatial efficiency. Importantly, for our purposes, these proofs also have local support for submitted values, such as Pedersen promises and public keys. This enables us to realize the functions such as rangeproofs under the general zero-knowledge framework, instead of realizing the complex elliptic curve algorithm under the zero-knowledge framework.
Stronger. In order to limit the transaction size, our old version rangeproofs limited the output range size to 2 32. This limits the output to about 43 BTC, but the output can be increased by reducing the proofing granularity from 1 cluster to1cluster or 100 cluster, or increasing the minimum value from scratch. These adjustments are possible, but the number of displays is used, which limits the privacy provided by the system.
The size of these 32-bit range proofs is about 2.5 KiB. After Adam's optimization, their size will be 2 KiB. With Bulletproofs, they should be 6 10 bytes. With such a small size, we can double the range to 64 bits without any non-privacy adjustment. In this case, it will increase 6 10 bytes to 1220 bytes, right? No, actually, the 64-bit bulletproof shooting range only has 674 bytes.
Smaller. We doubled the size of the range, but the size of the proof only increased by 64 bytes because they grew exponentially. This is done by using the change of internal product parameters in Bootle et al.' s paper 20 16. Jonathan bootle also helped benedikt and Dan develop bulletproof devices. Specifically, the logarithmic inner product parameter described in this paper is further reduced in Bulletproofs, from 6log(N) curve point to 2log(N).
The same technology can integrate multiple rangeproofs in a transaction into one, which will only increase the number of bytes. The sum of two rangeproofs is 738 bytes, four are 802 bytes and eight are 866 bytes. Eight 64-bit classic rangeproofs will exceed 40,000 bytes.
Faster. This can save a lot of space, but our preliminary analysis of this technology shows that the verification speed will be slower than the old version of rangeproofs. It seems that verifying a 64-bit certificate requires more than 200 scalar point multiplications, each of which is a heavy 50-microsecond transaction, while the old rangeproofs only needs 128 scalar point multiplications.
But after further analysis, we can combine many multiplications to reduce the total to 147. More importantly, we realized that, unlike the old rangeproofs, these multiplications are independent of each other, so we can complete them in one batch. As part of our summary of signature work, we know how to multiply in batches quickly. Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman and I spent several months on this problem, and finally reduced the multiplication speed of 147 to 15.5 microseconds respectively, which reduced the total verification time of bulletproof to 2.3 ms, while the proof of the old version took 5.8 ms
The speed is not only doubled, but also because the more points you provide, the faster our batch multiplication speed and the more impressive comprehensive performance figures are. It can be verified by integrating eight 64-bit Bulletproofs, 1 1.5 ms, while the old proof takes 46.8 ms, which is more than four times faster.
But it can be better. Bulletproofs supports a very effective form of batch verification. In the 147 multiplication that we need to complete, 130 uses the same point in each bullet-proof, that is to say, in batch verification, this 130 multiplication can be merged, leaving only the 17 multiplication as a new one. In fact, this small cost only increases in logarithmic order: for the integration of two intervals, each additional proof needs 19 additional points, while for the integration of four intervals, each proof needs 2 1 points.
Note that we have introduced two similar but independent concepts: aggregation means that the prover combines multiple rangeproofs into1; Batch processing means that the validator detects multiple separate certificates at the same time.
This means that two 64-bit rangeproofs can be verified within 2.7 ms, that is, each range1.4 ms. In 130 ms, 500 rangeproofs can be verified, that is, each range 0.26 ms, which is 23 times higher than the old version. However, due to integration, it can become more impressive. 500 8-in 1 integrated range proofs (one * * * is 4000 range proofs) can be verified within 305 ms, or each range is 76 microseconds, which is 75 times higher than the old version.
With the more and more efficient scalar point multiplication is no longer the dominant role, this influence will eventually be maximized around the integration of 64 proofs. At this point, we can carry out batch verification in the range of 46 microseconds each, and the speed is increased by 125 times. For reference, the signature of elliptic curve digital signature algorithm (ECDSA) takes about 55 microseconds, so at this integration level, rangeproofs is not even the main part of transaction verification. Of course, we are unlikely to see 64 output transactions on the blockchain, but this speed is in a non-blockchain environment (such as provisioning)
) is possible.
This verification also saves memory. Verifying a single rangeproof requires 100 KiB, which increases or decreases with the size.
Bullet proof is more general than range proof. They can be used to prove arbitrary statements with zero knowledge. They are equivalent to SNARKs or STARKs, but they natively support elliptic curve (EC) public key and Pedersen promise (so there is usually no need to implement EC algorithm in the program). In addition, unlike SNARK, Bulletproofs has complete 128-bit security under the standard conjecture of untrusted environment. Unlike Stark, they are enough to quickly prove and verify the problem of reasonable size on typical computer hardware.
As a concrete example, consider the operation of SHA2 compression function. Our proof program needs less than 30 MiB of memory and about 2 1 sec to prove the knowledge of SHA2 original image. Verification requires about 23 MiB of memory and 75 ms, but we can verify additional certificates in batches, each of which is about 5 ms, 13.4 KiB.
Our proof program saves more memory than SNARK: in the same system, a SNARK proof of SHA2 only takes 4 seconds, but it needs 75 MiB memory. When verifying, each circuit needs a lot of one-time pre-calculation (statements that need to be proved), and then it only needs 3-5 ms and little memory to verify. These numbers will not increase with the increase of circuits, so for circuits with more than several thousand gates, SNARK is obviously the winner even compared with our batch verification. Unfortunately, this is at the expense of trusted environment and new encryption conjecture.
Bulletproofs still has a lot of room for optimization in the process of proof and verification.
The ability to verify arbitrary statements-whether Bulletproofs, snakes or snakes-has many applications. It can be used to implement common digital signatures, including (traceable) ring signatures and threshold signatures. For large rings, it is more effective than the traditional scheme in verification time and scale. Its use is not limited to this, but also can be used to solve the problem of selling Sudoku reliably, and can be used for multi-party calculation. Even if there are secret data, it can prove that all parties are honest. (Especially in multi-signature schemes like MuSig, this allows deterministic random number generation without the signer maintaining state or being vulnerable to random reuse attacks. It can also be used to prove the hash image.
The latter application, hash image, is particularly interesting because it can be used to create zero-knowledge Merkle proofs, including efficient proofs in large-scale collections (with millions or even billions of elements). We will discuss this in a future article.
We are very grateful for the internal product parameters developed by Bootle and others, which have guided us. Thanks also to our co-authors Benedikt Bünz and Dan Boneh, who have done a lot of creative work. Thanks to Sean Bowe and Daira Hopwood for their research on optimizing arithmetic circuits.
Translator: Xu Li
Original address: bullet proof, fast range proof and more