Zero-Knowledge Proof — Privacy Delegation of Provers
When watching the zkSummit7 videos recently, the first topic caught my attention:
https://www.youtube.com/watch?v=SCIuwh9ya8U
Efficient Privacy Delegation of zkSNARK Provers The presentation Pratyush Mishra made was excellent, clearly explaining the reason for the delegation design and implementation logic. If you are interested in this topic, feel free to watch the video and read this article to understand the Efficient Privacy Delegation of zkSNARK Prover.
Let’s first review the application model of the zkSNARK situation: the Prover build and send the proof to the Verifier for verification. Note that the proof is generated locally at Prover.
With more and more ZKP Applications, here’s the situation: it’s not efficient to generate circuit delegation locally at the Prover side, because it takes too long to execute the circuits, or the computation ability of Prover is limited. Naturally, people thought of outsourcing the work of ZKP.
However, there’s a big problem: information leakage. ZKP was originally designed to protect information privacy. However, a simple outsourcing protocol might leak private information. The goal of this topic is to figure out how to outsource ZKP Delegation while ensuring privacy:
There are two goals: 1/ The proving efficiency. If utilizing a complex protocol, then there is no point in the delegator’s work if it is slower than the Prover. (The delegator’s work should be much less than proving.) 2/ (The delegator’s witness should be hidden from the worker.) All original witness information must be protected.
People may say that the problem could be solved with homomorphism. However, it’s not a great choice due to its greater cost.
It’s able to outsourc the proof work for ZKP with field value based privacy method.
In other words, as long as at least 1 worker is honest, the privacy of the proof is safe. Next, let’s look at the feasibility of the zkSNARK protocol.
The current privacy delegation protocol supports a proving system based on the PIOP, Which has two characteristics: 1/ utilizing the KZG and inner-product-argument polynomial commitment schemes 2/ utilizing the PIOP framework. For the performance, there is more supporting data provided by the end of the presentation.
The whole design is based on the MPC:
Time to consider some details. The complicity of the proving system needs to be considered when utilizing MPC. The whole proving system can be viewed as two parts: 1/ PIOP 2/ Polynomial Commitment.
Before going into details about how each part utilizes MPC to implement delegation, let’s review the Zero-Knowledge Proof protocol structure with the PIOP and polynomial commitment.
After the polynomial commitments are generated, then the random Query points are returned from the Oracle with the inputs of these commitment values. So that these Query points could be used to open polynomials and verify. Before going into detail, there are a few basic knowledge about Additive Secret Shares.
If the Secret Share is separated into multiple parts, and the protocol supports additive homomorphism, then the protocol supports privacy delegation. With the MPC implemntation for the two main parts of Zero-Knowledge Proof, we can implement Zero-Knowledge Proof Delegation.
The whole process is shown below:
Let’s take a close look at the two MPC implementations. Let’s start with the MPC for delegating PIOP provers:
There are 4 main types of computation for PIOP: the first three are all linear (have additive homomorphism), however, Polynomial mults type doesn’t have additive homomorphism. Normally, there are three steps to compute the multiplication of two polynomials:
Use FFT to get polynomial values over 2d domain. After getting the product of the polynomial values, recover the polynomial coefficient of the product via iFFT. Both the first and third step are homomorphism, but the second step isn’t. Imagine this: multiple workers all want to get some secret shares of the polynomial product while not exposing all secret shares. Under this circumstance, these workers can send the partial secret shares back to the Delegator. Since the Delegator is able to access all secret shares, the Delegator can send the redistributed result back to the workers after putting the secret shares through the process of polynomial interpolation and re-multiplication.
With the Delegator in the game, PIOP process can be delegated:
Now, let’s take a look at the Polymer Commitment Scheme. This part is linear, making the process more natural:
By the end of the presentation, some basic testing data are provided:
Via Zero-Knowledge Proof Delegation, it’s possible to obviously increase the performance and the size of circuits.
Summary:
With more and more ZKP applications, Zero-Knowledge Proof Privacy Delegation became more and more important. In some scenes, how to efficiently outsource the proving work while ensuring data privacy is a meaningful topic, when it takes a long time to build a local proof. The zkSummit7 presentation presented a solution: combining with MPC, Privacy Delegation of Provers can be implemented with PIOP + Polynomial Commitment of ZKP.
