Sumcheck protocol for Pedersen Commitment

In the previous blog, we introduced the definitions of Sumcheck protocol. Now we’ll describe Sumcheck argument based on Sumcheck protocol and Pedersen commitment.

Firstly, here we give a definition of Sumcheck-friendly commitments. A commitment scheme CM is Sumcheck friendly if

Comm(ck, m) = \sum_{w_1,…, w_l \in H} f(p_m (w_1, …, w_l), p_{ck}(w_1, …, w_l))

Of which the Comm(ck, m)’s commitment space C is an R-module[1], H is a subset of ring R, and message polynomial p_m(w) and key polynomial are both in M[X], M is R-module. The combination function is

Obviously that Pedersen Commitment `C = vG + rH` is Sumcheck-friendly. And the instance can be formally defined below in Sumcheck protocol (recall the definition in the previous post):

where the prover P use polynomial

. After the end of the Sumcheck protocol execution, the P learns r, and V learns (r, v). The P computes and sends p_a(r) to V, and the V calculates p_G(r), and checks that:

Now we need to prove that the above Sumcheck protocol for Pedersen Commitment is well-defined.

For instance, let

which satisfies:

and the products can be rewritten as:

which is a natural extension of the scalar multiplication operation of aG, mapping F X G -> G.

And in this construction, easy to find that the completeness is satisfied. For every `a` in F, C = <a, G>, Pr[ <P(G, C, a), V(G, C)> = 1] = 1, which means the commitment C binding to a generated by P in G, can be verified by V with high probabilities within same G. For the knowledge soundness, if the verifier accepts the commitments, one can efficiently extract an opening key a, such that C = <a, G>.

More proof explanations can be found in the paper[2].

1. https://eprint.iacr.org/2021/333.pdf, https://youtu.be/tazkY_CaLK0
2. https://math.stackexchange.com/questions/144518/what-exactly-is-an-r-module