publications

2024

1. Ceno

   Ceno: Non-uniform, Segment and Parallel Zero-knowledge Virtual Machine

   Tianyi Liu, Zhenfei Zhang, Yuncong Zhang, and 2 more authors

   2024

   Bib PDF

   @misc{cryptoeprint:2024/387,
     author = {Liu, Tianyi and Zhang, Zhenfei and Zhang, Yuncong and Hu, Wenqing and Zhang, Ye},
     title = {Ceno: Non-uniform, Segment and Parallel Zero-knowledge Virtual Machine},
     howpublished = {Cryptology ePrint Archive, Paper 2024/387},
     year = {2024},
     note = {\url{https://eprint.iacr.org/2024/387}},
     url = {https://eprint.iacr.org/2024/387},
   }

2. Pianist

   Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs

   T. Liu, T. Xie, J. Zhang, and 2 more authors

   In 2024 IEEE Symposium on Security and Privacy (SP) May 2024

   Abs Bib PDF Code

   In the past decade, blockchains have seen various financial and technological innovations, with cryptocurrencies reaching a market cap of over 1 trillion dollars. However, scalability is one of the key issues hindering the deployment of blockchains in many applications. To improve the throughput of the transactions, zkRollups and zkEVM techniques using the cryptographic primitive of zero-knowledge proofs (ZKPs) have been proposed and many companies are adopting these technologies in the layer-2 solutions. However, in these technologies, the proof generation of the ZKP is the bottleneck and the companies have to deploy powerful machines with TBs of memory to batch a large number of transactions in a ZKP. In this work, we improve the scalability of these techniques by proposing new schemes of fully distributed ZKPs. Our schemes can improve the efficiency and the scalability of ZKPs using multiple machines, while the communication among the machines is minimal. With our schemes, the ZKP generation can be distributed to multiple participants in a model similar to the mining pools. Our protocols are based on Plonk, an efficient zero-knowledge proof system with a universal trusted setup. The first protocol is for data-parallel circuits. For a computation of M sub-circuits of size T each, using M machines, the prover time is O(T\log T + M \log M), while the prover time of the original Plonk on a single machine is O(MT\log (MT)). Our protocol incurs only O(1) communication per machine, and the proof size and verifier time are both O(1), the same as the original Plonk. Moreover, we show that with minor modifications, our second protocol can support general circuits with arbitrary connections while preserving the same proving, verifying, and communication complexity. The technique is general and may be of independent interest for other applications of ZKP. We implement Pianist (Plonk vIA uNlimited dISTribution), a fully distributed ZKP system using our protocols. Pianist can generate the proof for 8192 transactions in 313 seconds on 64 machines. This improves the scalability of the Plonk scheme by 64\times. The communication per machine is only 2.1 KB, regardless of the number of machines and the size of the circuit. The proof size is 2.2 KB and the verifier time is 3.5 ms. We further show that Pianist has similar improvements for general circuits. On a randomly generated circuit with 2^25 gates, it only takes 5s to generate the proof using 32 machines, 24.2\times faster than Plonk on a single machine.

   @inproceedings{pianist,
     author = {Liu, T. and Xie, T. and Zhang, J. and Song, D. and Zhang, Y.},
     booktitle = {2024 IEEE Symposium on Security and Privacy (SP)},
     title = {Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs},
     year = {2024},
     volume = {},
     issn = {2375-1207},
     pages = {35-35},
     keywords = {zero knowledge proofs;snarks;distributed computing},
     doi = {10.1109/SP54263.2024.00035},
     url = {https://doi.ieeecomputersociety.org/10.1109/SP54263.2024.00035},
     publisher = {IEEE Computer Society},
     address = {Los Alamitos, CA, USA},
     month = may,
   }

2021

1. zkCNN

   ZkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy

   Tianyi Liu, Xiang Xie, and Yupeng Zhang

   In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security May 2021

   Abs Bib PDF Code

   Deep learning techniques with neural networks are developing prominently in recent years and have been deployed in numerous applications. Despite their great success, in many scenarios it is important for the users to validate that the inferences are truly computed by legitimate neural networks with high accuracy, which is referred to as the integrity of machine learning predictions. To address this issue, in this paper, we propose zkCNN, a zero knowledge proof scheme for convolutional neural networks (CNN). The scheme allows the owner of the CNN model to prove to others that the prediction of a data sample is indeed calculated by the model, without leaking any information about the model itself. Our scheme can also be generalized to prove the accuracy of a secret CNN model on a public dataset.Underlying zkCNN is a new sumcheck protocol for proving fast Fourier transforms and convolutions with a linear prover time, which is even faster than computing the result asymptotically. We also introduce several improvements and generalizations on the interactive proofs for CNN predictions, including verifying the convolutional layer, the activation function of ReLU and the max pooling. Our scheme is highly efficient in practice. It can support the large CNN of VGG16 with 15 million parameters and 16 layers. It only takes 88.3 seconds to generate the proof, which is 1264\texttimes faster than existing schemes. The proof size is 341 kilobytes, and the verifier time is only 59.3 milliseconds. Our scheme can further scale to prove the accuracy of the same CNN on 20 images.

   @inproceedings{10.1145/3460120.3485379,
     author = {Liu, Tianyi and Xie, Xiang and Zhang, Yupeng},
     title = {ZkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy},
     year = {2021},
     isbn = {9781450384544},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {https://doi.org/10.1145/3460120.3485379},
     doi = {10.1145/3460120.3485379},
     booktitle = {Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security},
     pages = {2968–2985},
     numpages = {18},
     keywords = {convolutional neural networks, zero knowledge proofs, machine learning},
     location = {Virtual Event, Republic of Korea},
     series = {CCS '21},
   }

2. Virgo++

   Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time

   Jiaheng Zhang, Tianyi Liu, Weijie Wang, and 4 more authors

   In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security May 2021

   Abs Bib PDF Code

   We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our key technique is a new sumcheck equation that reduces a claim about the output of one layer to claims about its input only, instead of claims about all the layers above which inevitably incurs an overhead proportional to the depth of the circuit. We developed efficient algorithms for the prover to run this sumcheck protocol and to combine multiple claims back into one in linear time in the size of the circuit. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 208 kilobytes and the verifier time is 66 milliseconds. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.

   @inproceedings{10.1145/3460120.3484767,
     author = {Zhang, Jiaheng and Liu, Tianyi and Wang, Weijie and Zhang, Yinuo and Song, Dawn and Xie, Xiang and Zhang, Yupeng},
     title = {Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time},
     year = {2021},
     isbn = {9781450384544},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {https://doi.org/10.1145/3460120.3484767},
     doi = {10.1145/3460120.3484767},
     booktitle = {Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security},
     pages = {159–177},
     numpages = {19},
     keywords = {interactive proofs, zero knowledge proofs},
     location = {Virtual Event, Republic of Korea},
     series = {CCS '21},
   }