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