I’d like to provide an introductory overview of the commitment scheme presented by Kate, Zaverucha, and Goldberg (KZG or Kate). Please note that this post is intended as a gentle introduction and does not delve into rigorous mathematical or cryptographic details; it serves as a starting point for understanding the concept.
Kate polynomial commitments are a cryptographic primitive that allow one to commit to a polynomial in a way that is both hiding and binding. This means that the commitment does not reveal any information about the polynomial, and it is impossible to change the polynomial once the commitment has been made.
In simpler terms, Kate polynomial commitments allow one to lock a polynomial into a secret box. The box is locked so that no one can see what polynomial is inside, but the box is also transparent so that anyone can verify that the polynomial inside has not been changed.
How Kate Polynomial Commitments Work
Kate polynomial commitments are based on a mathematical object called a bilinear pairing. A bilinear pairing is a type of mathematical function that takes two elements from one group and produces an element from another group, and have many useful properties, including the ability to be used to create cryptographic commitments.
To commit to a polynomial using a Kate polynomial commitment, you first need to choose a random secret key. Then, you use the bilinear pairing to calculate a commitment to the polynomial. The commitment is a single element of the second group.
Once you have calculated the commitment, you can reveal it to anyone. However, no one will be able to determine the coefficients of the polynomial from the commitment alone.
The prover can then reveal the commitment to the verifier. The verifier can then verify the commitment by evaluating the polynomial at the same point s and raising the result to the power of 1. If the verifier obtains the same commitment as the prover, then the verifier can be confident that the prover has committed to a valid polynomial.
Properties of Kate Polynomial Commitments
Kate polynomial commitments have two important properties:
- Hiding: The commitment does not reveal any information about the polynomial. This means that the verifier cannot learn anything about the polynomial by looking at the commitment.
- Binding: The commitment is binding to a single polynomial. Once the commitment has been made, it is impossible to change the polynomial. This means that the prover cannot cheat by committing to a different polynomial than the one they originally intended to commit to.
Applications of Kate Polynomial Commitments
Kate polynomial commitments have a number of benefits over other types of commitment schemes. First, they are very efficient to compute. Second, they can be used to prove that a polynomial has a certain value at a certain point. This is very useful for a variety of cryptographic applications, such as zero-knowledge proofs.
Kate polynomial commitments are being used in Ethereum to scale the network and to develop privacy-preserving applications. For example, they are used in the proto-Danksharding protocol and in the zkSync rollup.
Here is a concrete example of how Kate polynomial commitments could be used in Ethereum:
- A user wants to deposit ETH into a zkSync rollup.
- The user proves to the rollup that they have the ETH by generating a Kate polynomial commitment to their ETH balance.
- The rollup verifies the commitment and deposits the ETH into the user’s account.
- The user can then withdraw their ETH from the rollup at any time by proving to the rollup that they know the secret key to the polynomial commitment.
Kate polynomial commitments have a number of applications in cryptography, including:
- Zero-knowledge proofs: Kate polynomial commitments can be used to prove that you know a secret without revealing the secret itself. For example, you could use a Kate polynomial commitment to prove that you are over 21 without revealing your date of birth.
- Secure multi-party computation: Kate polynomial commitments can be used to allow multiple parties to compute a function together without revealing their individual inputs to each other. For example, two banks could use Kate polynomial commitments to compute the sum of their account balances without revealing the individual balances to each other.
- Scalable blockchain protocols: Kate polynomial commitments can be used to create scalable blockchain protocols that can support a large number of transactions per second. For example, the Ethereum blockchain is considering using Kate polynomial commitments to implement a new scaling solution called Proto-Danksharding.
Conclusion
Kate polynomial commitments are a powerful cryptographic primitive that has a wide range of applications. Kate polynomial commitments are still under development, but they are already being used in a number of experimental blockchain protocols. As Kate polynomial commitments continue to mature, they are expected to play an increasingly important role in the development of scalable and secure blockchain protocols.
Originally published at https://deeprnd.blogspot.com on June 13, 2023.
