What is SHPLONK? - Sin7Y Tech Review (11)

1. SHPLONK vs PLONK: What is the difference?

SHPLONK is a more effective commitment scheme than KZG10 commitment. On the premise of Multi-poly and Multi-openings, SHPLONK can make the workload of Prover not increase with Openings. As a result, developers tend to use Permutation or Multi-shifts techniques to increase the number of polynomials when designing constraint systems. (As for the current PLONK algorithm, there are two Openings, i.e., z and zw. When there are more Openings, this algorithm will have more advantages.)

2. General Introduction to Polynomial Commitment Schemes (PCS)

2.1 One open point

If f(x) - a can be divided by x  -  z, then f(z) = a

2.2 Multi open points For set S, there is polynomial Zs(X) = ПzϵS(X-z). If f(X) - r(X) can be divided by the polynomial Zs(X), it means that for any element z in set S, satisfying f(z) = r(z)

2.3 PCS protocol A polynomial commitment scheme should consist of three parts, ϴ = (gen, com, open), satisfying:

a. The inputs of Prover are as follows:

b. The inputs of Verifier are as follows:

c. At the end of the protocol, Verifier should output either true or false and meet the following requirements:

3. First Improved PCS

3.1 Protocol

a. Verifier selects a number γ ϵ F at random b. Prover computes polynomials:

and computes c. Verifier computes:

d. Verifier computes:

e. Verifier output is correct if and only if:

Proof:

3.2 Complexity

4. Final Improved PCS

4.1 Protocol

a. Verifier randomly selects random number γ

b. Prover computes polynomials:

c. Verifier randomly selects z and sends it to Prover

d. Prover computes:

Of which:

It can be found: So (X-z)|L. Prover computes: e. Verifier computes:

f. Verifier output is correct if and only if:

4.2 Complexity

Reference

SHPLONK: https://eprint.iacr.org/2020/081.pdf

Plonk: https://eprint.iacr.org/2019/953.pdf

KZG10: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

Slonk: https://ethresear.ch/t/slonk-a-simple-universal-snark/6420