Consider two lists of committed values x1,…,xn and y1,…,yn. The goal is to prove that the second list is a permutation of the fi rst. This problem is called a veri able shuffle. It has many applications in voting [FS01, Nef01], mix-nets [Cha82], and solvency proofs [DBB+15]. Neff [Nef01] gave a practical implementation of a veri able shuffle and later work improved on it [Gro03, GI08a]. Currently the most efficient shuffle [BG12] has size sqrt(n).
Bulletproofs can be used to create a verifi able shuffle of size O(log n). The two lists of commitments are given as inputs to the circuit protocol from Section 5. The circuit can implement a shuffle by sorting the two lists and then checking that they are equal. A sorting circuit can be implemented using O(n* log(n)) multiplications which means that the proof size will be only O(log(n)). This is much smaller than previously proposed protocols. Given the concrete efficiency of Bulletproofs, a veri fiable shuffle using Bulletproofs would be very efficient in practice.
参考资料： [1] 论文《Bulletproofs-Short Proofs for Confidential Transactions》
