This is a cross-posted article across ethresearch and zkresearch for better moderation of zk researches
Thanks for your reviews! @levs57, curryrasul, @AtHeartEngineer!
TL;DR
- Uses KZG polynomial commitment per epoch
- Uses KZG opening per message
- Should be less than 1 ms to generate a proof per message, which is almost 1000x improvment
- Finally, we can use RLN, the spam protection layer, for Tor network and the Ethereum validator network!
Intro
The PSE team is delivering a project RLN - Rate-Limiting Nullifier which is originated from Barry’s post. Briefly, RLN is a spam protection layer which can be used in the anonymous network where we have the network level privacy. More technically, transmitter chooses a polynomial where its f(0) is its private key and share a point on that polynomial when they send a message. Therefore, if f is a n-degree polynomial, te message limit becomes n since the transmitter cannot share more than n points not to get exploited the private key.
To make everything work well, we’re using zkSNARK to prove the membership proof to encure that the transmitter commited a proof of stake and also the message proof is containinng a point on the polynomial. But the problem is that it takes about 1 second to generate a proof per message and is not affordable for many cases, for example Tor, Validator network, and mobile environment etc.
By the way, we also can utilize the polynomial commitment schemes and KZG opening fits pretty perfect for RLN scheme. Here’s the detail technical setup about how to use KZG opening to achieve a 1ms proving time instead of 1 sec.
Preparation
- For a given epoch e and a message limit n, a user creates a polynomial f(x) of degree n, which satisfies the condition that f(0) equals the user’s private key pk.
- Trusted setup:
- We need a shared common reference: g, g^\alpha, g^{\alpha^2}, ..., g^{\alpha^n} for message limit n
- In the non-anonymous version, we should execute a trusted setup for each message limit,
- In the anonymous version, we can use an existing reference.
- We need a shared common reference: g, g^\alpha, g^{\alpha^2}, ..., g^{\alpha^n} for message limit n
Commitment
- User selects a n-degree polynomial f for an epoch to send maximum n messages which f(0) is the private key.
- User computes the KZG polynomial commitment C = g^{f(\alpha)} using the reference string.
- User shares the polynomial commitment C for the given epoch
- To send a message, user shares (f(m), g^{\psi_m(\alpha)}) where m is the hash of the messgae value and g^{\psi_m(\alpha)}, \psi_m(x) = {f(x) - f(m) \over x-m} is the opening proof.
Evaluation of a message
- Calculate the hash of the message: m
- RLN message: m, f(m),g^{\psi_{m}(\alpha)}
- Verifier has the polynomial commitment of the given epoch g^{f(\alpha)}
- Verifier evaluates the message:
Various Commitment Schemes(for each epoch)
Version A: the simplest approach with a non-anonymous setting
- User’s public key: g^{f(0)}
- User submits the commitment of the polynomial, its public key, and the opening proof. g^{f(\alpha)}, g^{\psi_{0}(\alpha)}, g^{f(0)}
- Verifier checks if the user’s public key is on the committed polynomial by verifying the opening of the kzg commitment.
How KZG opening works?
To prove the opening of (\beta, f(\beta)) on f
The quotient \psi_\beta(x) is
And then we can simply prove that opening by checking the pairings like below
because the left side of the equation should be
Version B: Using zkp for the anonymous setting
- User creates a zkp to prove that
- public: g^{f(\alpha)}, n
- private: f(x), pk
- constraints
- f(0) = pk
- Membership proof of g^{f(0)}
- c_i = 0 when i>n and f(x) = \Sigma_{i=0}^{k} c_i x^i
- And submits the proof \pi and the polynomial commitment g^{f(\alpha)}
- Verifier checks the proof:
Version C: Using multiple polynomial commitments for multi-epoch commitment
Commitment
- User creates m polynomials of degree n for m epochs, then the user commit whole polynomials at once.
- For a given epoch e, let’s say f_e(x) is a polynomial of degree n for that epoch.
- Then we can rewrite f_e(x) = \Sigma_{i=0}^{n} c_i(e) \cdot x^i
- For example,f_1(x) = c_0(1) + c_1(1) x + c_2(1) x^2 + ... + c_n(1) x^n\\ f_2(x) = c_0(2) + c_1(2) x + c_2(2) x^2 + ... + c_n(2) x^n\\ f_3(x) = c_0(3) + c_1(3) x + c_2(3) x^2 + ... + c_n(3) x^n\\ ...\\ f_m(x) = c_0(m) + c_1(m) x + c_2(m) x^2 + ... + c_n(m) x^n
- Then the user creates polynomial commitments g^{c_i(\alpha)} for each c_i(e)
- And creates a zkp to prove that
- public: g^{c_i(\alpha)}, n, m
- private: c_i(e), pk
- constraints
- c_0(e) = pk for every e \leq m
- c_i(e) = 0 when i>n and f(x) = \Sigma_{i=0}^{k} c_i(e) x^i
- Membership proof of g^{f(0)}
- The polynomial commitment g^{c_i(\alpha)} is correct.
Verification
- For the registration,
- Verifier checks the proof:
- For each epoch e,
- User submits
- \{(g^{c_0(e)}, g^{\phi_{0, e}(\alpha)}), (g^{c_1(e)}, g^{\phi_{1, e}(\alpha)}), ..., (g^{c_n(e)}), g^{\phi_{n, e}(\alpha)})\} where \phi_{(i, e)}(x) = {c_i(x) - c_i(e)\over x-e }
- g^{f_e(\alpha)}
- Then the verifier checks
- User submits
by
- For i = 0...n, the verifier checks the submitted homomorphically hidden coefficients is in the polynomial commitments by
where
- After then,
- Calculate the hash of the message: m
- RLN message: m, f(m),g^{\psi_{m}(\alpha)}
- Verifier evaluates the message:
Conclusion
| Version A | Version B | Version C | |
|---|---|---|---|
| Description | Pairing check using the public key | Use zkp for each epoch to prove the membership proof and polynomial commitment for each epoch’s secret sharing polynomial | Use zkp only once to prove the membership proof and the polynomial commitments of the coefficients of the secret sharing polynomials for multiple epochs |
| preparation | trusted setup for each message limit number | can use a universal trusted setup | can use a universal trusted setup |
| zkp | N/A | 1 zkp per epoch | 1 zkp per m epochs |
| anonymity | no | yes | yes |
| proof size per epoch | 1 group element | depends on zkp scheme | 2n + 1 group elements |
| verification for each epoch | 3 pairings | 1 zkp | 4n + 1 pairing (n: message limit) |
| proof size per message | 1 group element | 1 group element | 1 group element |
| verification for each message | 2 pairings | 2 pairings | 2 pairings |
Update:
curryrasul pointed out that we can cache e(g^{f(\alpha)}, g) at the beginning of the epoch and then use it for its future message verifications. So it’ll cost 2 pairings per message verification.
