Commitment Scheme in ZKP

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or determined statement) while keeping it hidden to others, with the ability to reveal the committed value later, that is commitment is hiding.

Commitment schemes are designed so that a party cannot change the value or statement after committing to it: commitment schemes are binding. Commitment Binding is the main difference compared to the general one-way hash function.

The classic application of the commitment scheme is Coin Flipping for 2 mistrustful parties, Alice and Bob, to remotely generate a random bit, and no one can bias the outcome beyond a specific probability, without a trusted witness. So differentiating from simple Flip and Open, a commitment scheme is necessary to ensure the outcome’s fair. And the procedure might be:

  1. Alice “calls” the coin, and generates a commitment of the result to Bob;
  2. Bob flips the coin and reports the result;
  3. Alice opens the commitment, and reveals the result to Bob;
  4. Bob verifies the result which is bound to the commitment;
  5. if Alice’s revelation matches the result from Bob, Alice wins.

Formal Definition

From the definition from reference^[1], there are 2 base operation for a commitment scheme, Commit and Open, the Commit operation consume a message, and output a digest c and a decommitment string d. The Open operation is the inversion operation to Commit, which consume the c and d to output the original message.

Formal Definition of Commitment Scheme

Commitment schemes have important applications in a number of cryptographic protocols including secure the signature scheme( Lamport signature scheme), zero-knowledge proofs, and secure computation. This post we focus on how it’s applied in ZKP.

Commitments are used in zero-knowledge proofs for two main purposes: first, to allow the prover to participate in “cut and choose” proofs where the verifier will be presented with a choice of what to learn, and the prover will reveal only what corresponds to the verifier’s choice. Second, commitments are also used in zero-knowledge proofs by the verifier, who will often specify their choices ahead of time in a commitment. This allows zero-knowledge proofs to be composed in parallel without revealing additional information to the prover. here we dive into 2 wide-used schemes, Pedersen Commitment and Polynomial Commitment.

Pedersen Commitment

Pedersen Commitment provides information hiding, computational binding, and additive homomorphism. The generalized Elliptic Curve Pedersen Commitment definition follows^[2]:

A commitment scheme is computational homomorphic if exists an efficient coordinate-wise addition operation defined over C and D, s.t.

Obviously, Pedersen Commitment is additive homomorphic. This capability enables us to hide the ERC20 token balance, combining Zero-Knowledge Range Proof to ensure the balance would be greater or equal to 0.

Pedersen Commitment is widely used by privacy-preserving blockchain protocols, such as Monero, Eigen Network, and MimbleWimble.

Polynomial Commitment

Polynomial Commitment Scheme allows a prover commits to a polynomial P to verifier, and the verifier can verify the commitment is bound to the particular polynomial. Easy to know a polynomial is determined by it’s coefficient. Similar to Merkle Proof, the Merkle root is the commitment, and the value(vector) attached to leaf node is the value to be committed to. If we consider each value a_i in leaf node as the coefficient p_i of the polynomial P, so proving an evaluation means that the prover wants to show to the verifier that P(z) = y for some z. And the prover can do this by sending all the p_i to verifier, and the verifier computing the P(z) is indeed y.

Polynomial commitment and evaluation schemes are fundamental components of many novel succinct zero-knowledge protocols, e.g. Sonic, PLONK.

References

  1. https://kodu.ut.ee/~swen/courses/crypto-ii/2008/05-commitments.pdf
  2. https://tlu.tarilabs.com/cryptography/the-bulletproof-protocols#pedersen-commitments-and-elliptic-curve-pedersen-commitments
  3. https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
  4. https://hackmd.io/@tompocock/Hk2A7BD6U
  5. FRI: https://eprint.iacr.org/2019/1020.pdf
  6. IPA: https://eprint.iacr.org/2017/1066.pdf
  7. https://hackernoon.com/kzg10-ipa-fri-and-darks-analysis-of-polynomial-commitment-schemes

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store