Kate Polynomial Commitments

Introduction

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.

Comments

Post a Comment

Popular posts from this blog

CAP Theorem and blockchain

Image
In theoretical computer science, the CAP theorem states that it is impossible for a distributed data store (such as a blockchain network) to simultaneously provide more than two out of the three guarantees: Consistency, Availability & Partition tolerance. CAP Theorem – the parts C: Consistency – At any given time, all nodes in the network have exactly the same (most recent) value. A: Availability – Every request to the network receives a response, though without any guarantee that returned data is the most recent. P: Partition tolerance – The network continues to operate, even if an arbitrary number of nodes are failing. Due to the nature of distributed data stores (such as blockchain), Partition tolerance is a given fact; there will always be failing/unreachable nodes in the network (not least because of the unstable nature of the internet). CAP Theorem states that one has to choose between C (Consistency) or A (Availability) when in the presence of P (Partition): Av...
Read more

Length extension attack

Image
What is length extension? When a Merkle–Damgård based hash is misused as a message authentication code with construction H(secret ‖ message), and message and the length of secret is known, a length extension attack allows anyone to include extra information at the end of the message and produce a valid hash without knowing the secret. Quick sidebar, before you freak out: Since HMAC does not use this construction, HMAC hashes are not prone to length extension attacks. So, a length extension attack is a type of attack where an attacker can use Hash(message1) and the length of message1 to calculate Hash(message1 ‖ message2) for an attacker-controlled message2, without needing to know the content of message1. Algorithms like MD5, SHA-1 and most of SHA-2 that are based on the Merkle–Damgård construction are susceptible to this kind of attack. Truncated versions of SHA-2, including SHA-384 and SHA-512/256 are not susceptible, nor is the SHA-3 algorithm. A bit more details ...
Read more

Contract upgrade anti-patterns

Image
A popular trend in smart contract design is to promote the development of upgradable contracts . To be fair, existing techniques to upgrade contracts have flaws, increase the complexity of the contract significantly, and ultimately introduce bugs - even in the Zeppelin contract upgrade strategy. In this article, we are going to detail our analysis of existing smart contract upgrade strategies, describe the weaknesses we have observed in practice, and provide recommendations for contracts that require upgrades. In a follow-up blog post, we will detail a method, contract migration, that achieves the same benefits with few of the downsides. An overview of upgradable contracts Two ‘families’ of patterns have emerged for upgradable smart contracts: Data separation, where logic and data are kept in separate contracts. The logic contract owns and calls the data contract. Delegatecall-based proxies, where logic and data are kept in separate contracts, also, but the data contr...
Read more