Skip to main

Zero-Knowledge Proof - Cryptographic Primitives and Sigma Protocol

This blog covers the use of mathematics and cryptography in zero-knowledge protocols, specifically discussing elliptic curves, Pedersen commitments, and the Sigma protocol. It provides an overview of these concepts and their relevance in blockchain.

ByVitali Bestolkau Explainers

15 min read

Zero-Knowledge Proof - Cryptographic Primitives and Sigma Protocol

Introduction

This article is an overview of mathematics and cryptography as they relate to zero-knowledge protocols. Our goal is to provide a simplified introduction to these concepts, focusing on the math and cryptography principles used in the Sigma protocol. It's important to note that the Sigma protocol is just one example of a zero-knowledge protocol. It is not necessarily representative of other protocols such as ZK-SNARKS, ZK-STARKS, or Bulletproofs. However, the Sigma protocol implements many cryptographic primitives widely used in the field and has also found applications in the blockchain industry. This article aims to provide a general understanding of these concepts and their significance in Zero-Knowledge protocols.

1 Elliptic Curve

1.1 What is it

Elliptic Curves (ECs) are cryptographic primitives that are widely used in modern cryptography. They are defined by the equation y2=x3+ax+by^2 = x^3 + ax + b and have a specific shape. ECs are used in public-key encryption and the Elliptic Curve Digital Signature Algorithm (ECDSA), which was previously used for creating signatures in the Bitcoin blockchain for transaction verification. ECs are powerful tools that allow for the performance of various mathematical operations in cryptography.

In general, an Elliptic Curve looks like this:

Elliptic Curve.png

💡

Note: Not all Elliptic Curves look this way. The way they look depends on the constants aa and bb. In the example, a=1a = -1 and b=3b = 3, which makes the final equation looks like this: y2=x3x+3y^2 = x^3 - x + 3

To make the set of points on an elliptic curve finite, the values of xx and yy are capped at a large prime number pp, so that x,y[0;p1]x, y \in [0; p-1]. This can also be expressed as (y2x3axb)0  (mod  p)(y^2 - x^3 - ax - b) \equiv 0 ~~(mod ~~p).

1.2 How does it help to encrypt and decrypt data securely?

Elliptic curves can be used to securely encrypt and decrypt data through the use of public and private keys. Both sides (sender and receiver) must first "agree" on the specific EC to be used, including its constants aa and bb and the maximum value of the prime number pp. They also choose a random point GG on this EC, which they will use.

The sender and receiver then use their private keys, cc and dd, respectively, to calculate their respective public keys. Public key generation is done through the following equations: cG=CcG = C and dG=DdG = D, where CC and DD are new points on the EC and the public keys.

💡

Note: the Elliptic Curve Math differs from common Math. Check the source if you want to learn more about how multiplication and other operations work. Or you can check this video for the explanation of point addition.

To send the information, the sender:

  1. Encrypts the data using the receiver's public key DD.
  2. Sends the encrypted data to the receiver.
  3. The receiver decrypts the data using their private key dd.

If the receiver wants to reply to the received information, they can follow the same process but use the sender's public key CC instead of DD. When the sender receives the data, they can decrypt it using their private key cc.

The EC public key encryption scheme is considered secure because the private key computation involves the "elliptic curve discrete logarithm function," which is infeasible to compute for modern (non-quantum) computers (check the source for more). Thanks to the discrete logarithm problem, both public keys, CC and DD, can be made public along with the initial EC point GG. If an individual knows both CC and GG from the equation cG=CcG = C, it is almost impossible for them to compute the private key cc due to the difficulty of the discrete logarithm problem.

2 Pedersen Commitment

2.1 What is a commitment for

Commitments (or commitment schemes) are cryptographic primitives that securely send data that can only be verified when the sender (prover) reveals the data. Once the data is disclosed, the verifier calculates a new commitment using the revealed values and compares it to the original commitment sent by the prover.

2.2 Commitment properties

Commitments have two crucial properties: binding and hiding.

  • Binding: means that the value included in the commitment is fixed (defined) and cannot be altered after the commitment is created.
  • Hiding: means that the value included in the commitment is hidden and cannot be viewed by anyone until it is "officially" revealed.

2.3 Reasons for Pedersen Commitment

While elliptic curves (ECs) can be used for secure data transfer by encrypting a hidden value, typically, this value is within a small range (e.g., from 1 to 10), which makes it vulnerable to brute force attacks. That's where Pedersen commitments come in.

2.4 Pedersen Commitment Details

Pedersen Commitments address this issue by introducing a "blinding factor," a randomly generated number rr from a large range [0;2256)[0; 2^{256}), which is used to "blind" the committed value. This blinding factor helps to obscure the committed value, making it more difficult for an attacker to guess the value through brute force methods.

But rr can not be added to the committed value vv and have (r+v)G(r + v)G, where GG is a point on an elliptic curve. That would violate the binding property. After making a commitment, the committer may reveal not values vv and rr, but instead values vv' and rr', where v=v1v' = v - 1 and r=r+1r' = r + 1, and they would still provide the right outcome.

In Pedersen Commitments, in addition to GG, we have another point HH on an elliptic curve. Then we get the following commitment formula: rG+vHrG + vH. Although, most commonly, a Pedersen Commitment is represented like:

commitment(v,r)=gvhrcommitment(v, r) = g^v h^r

Where g,hg, h are public generators of a cyclic group QpQ_p of prime order pp. (v,r)(v, r) is also called the opening of the commitment.

💡

commitment(v,r)commitment(v, r) is a function. But why do we provide (only) two variables? Because everything except vv and rr is public. vv and rr are the only unknown variables before the function is executed.

💡

Different articles show different mathematical approaches in the same context.

Some articles use the Elliptic Curve Math to explain Pedersen commitments and the Sigma protocol (which is presented further in the article), which in the case of the commitments, would look like commitment(v,r)=vG+rHcommitment(v, r) = vG + rH, where GG and HH are points on an EC.

Other articles use logarithms to show the math behind these principles. The Pedersen commitment case would look the same as shown earlier in the article: commitment(v,r)=gvhrcommitment(v, r) = g^v h^r.

In the context of this article, these versions can be considered equal because they are both based on the discrete logarithm problem. But this article will stick to the logarithm version from now on.

2.5 How Pedersen Commitments work

In a nutshell, Pedersen Commitments work the following way:

A prover is a person/party trying to prove the validity of the data they provide. A verifier is a person/party that verifies the validity of the received data.

  1. The prover selects a secret value vv.
  2. A random number rr (as a blinding factor) is generated.
  3. The prover creates a commitment cc using the previous two values: c=C(v,r)c = C(v, r) and sends it to the verifier.
  4. The prover reveals values vv and rr.
  5. The verifier calculates cc' with the revealed values: c=C(v,r)c' = C(v, r) and checks if c=cc' = c.

💡

It is worth mentioning that the Pedersen commitments are not Zero Knowledge, as they rely on the private data being revealed in the end.

3 Sigma protocols

This section is mostly based on this article that perfectly explains on a high level how the Sigma protocol works.

Sigma protocols are Proof of Knowledge (or, in this context, an interactive Zero-Knowledge Proof (ZKP), more about that here) protocols that consist of three phases:

  1. Commitment phase. The prover decides on the value they are trying to prove, creates a commitment out of this, and sends the commitment to the verifier.
  2. Challenge phase. The verifier comes up with a challenge and sends it to the prover.
  3. Response phase. The prover generates a response and sends it to the verifier.

The verifier can then determine if the prover knows the value based on the response received.

💡

Even though the Sigma protocol is Zero-Knowledge, it is not connected to the ZK-SNARKs, ZK-STARKs, or Bulletproofs, as those protocols work differently from the Sigma protocol. However, they may share some similarities.

💡

The Sigma protocols are ZKP, but one of their main disadvantages is that they rely on the fact that the verifier is honest. In the case of a dishonest verifier, the protocol will fail. At the same time, zk-SNARKs, Bulletproofs, and zk-STARKs do not have this issue.

Note: there can be a more detailed comparison of advantages and disadvantages between the Sigma protocol and other ZKP protocols, but the scope of this article will limit itself to only this disadvantage.

3.1 Schnorr Protocol

The Schnorr protocol is one of the most used Proofs of Knowledge. It is also a variation of a Sigma protocol, as it follows the three-step structure. It involves a prover attempting to prove to a verifier that they know the value of x=loggyx = \log_g y, where gg is a generator of a cyclic group GqG_q of order qq, yy is public, and xx is private and known only to the prover.

💡

Note: Usually, in the context of Zero Knowledge, the private value that is being verified is called witness (in this case, xx is the witness). This article uses this word sometimes as well.

Check one of our previous articles to get a better insight into the Zero-Knowledge context

  1. The prover generates a random number rr and calculates a commitment t=grt = g^r. The commitment is then sent to the verifier.
  2. The verifier generates a challenge cc and sends it to the prover.
  3. The prover calculates s=r+xcs = r + xc and sends ss to the verifier.

The verifier checks if the equation gs=yctg^s = y^c t is correct. If it is, then it is considered that the prover knows the witness (secret value) xx.

💡

Why does the verifier check the equation gs=yctg^s = y^c t to prove the prover's knowledge of xx?

Firstly, this equation consists only of public values and does not reveal the private ones: xx or rr.

Secondly, this equation must be equal in the end. That is because: gs=yctgr+xc=yctgr(gx)c=yctg^s = y^c t \longrightarrow g^{r + xc} = y^c t \longrightarrow g^r (g^x)^c = y^c t , but as the initial statement says, gx=yg^x = y, which means that gr(gx)c=yctgryc=yctg^r (g^x)^c = y^c t \longrightarrow g^r y^c = y^c t and from the step 1 in the protocol it is said that t=grt =g^r, so in the end, we will get gryc=ycttyc=yctg^r y^c = y^c t \longrightarrow t y^c = y^c t. Therefore, if the prover takes all the steps correctly, the final equation gs=yctg^s = y^c t should be correct.

Thirdly, the third step kills two birds with one stone.

  1. The prover hides their private value xx, as the verifier can not calculate the xx without knowing rr.

  2. The verifier is assured that the prover does not cheat because it is only possible to calculate the response ss in advance for the final check passed by knowing either the random value rr or the challenge cc.

3.2 Fiat-Shamir Heuristic

The previous example is interactive, making a prover and a verifier communicate and stay online until the end of the process. The Fiat-Shamir Heuristic is a technique that converts interactive Zero-Knowledge Proofs into non-interactive ZKPs, which can also be used as a digital signature.

3.2.1 How it works

The prover needs to prove the knowledge of xx in y=gxy = g^x, which is the same as x=loggyx = \log_gy.

  1. Prover generates a random number rr and calculates the commitment t=grt = g^r.
  2. Instead of receiving a challenge from the verifier, the prover calculates it by hashing g,t,yg, t, y into cc: c=Hash(g,y,t)c = Hash(g, y, t).
  3. The prover calculates the response s=r+cxs = r + cx and sends a tuple (t,s)(t, s) to the verifier.
  4. The verifier calculates c=Hash(g,y,t)c = Hash(g, y, t) and checks if the equation gs=yctg^s = y^c t is correct.

Alternatively, the prover can send the challenge cc to the verifier, who then calculates their own challenge and compares it to the one received from the prover. The process is as follows:

Same as earlier, the prover is trying to prove the knowledge of xx in y=gxy = g^x.

  1. The prover generates a random number rr and calculates the commitment t=grt = g^r.
  2. The prover calculates the challenge c=Hash(g,y,t)c = Hash(g, y, t).
  3. The prover calculates the response s=r+xcs = r + xc and sends a tuple (c,s)(c, s) to the verifier. (instead of (t,s)(t, s), as the prover did in the previous example)

Now the verifier does the following:

  1. Instead of checking equality in the equation gs=yctg^s = y^c t, they get a formula for the commitment tt, which will be t=gsyct = g^s y^{-c} and calculates this tt.
  2. Then the verifier calculates c=Hash(g,y,t)c' = Hash(g, y, t) and checks if the calculated challenge is equal to the previously provided one: c=cc' = c.

3.3 Schnorr signatures

In general terms, a (digital) signature is proof that the owner of a particular public key signed some data. The signature lets everyone confirm that the person with the public key PP signed some data using their private key KK without revealing the signer's private key to others. (Check the source for more)

Schnorr signature is used in validating transactions on the Bitcoin blockchain. To be more specific, it tells everyone that the sender is the one who owns the coins which are being transferred.

For their verification, Shnorr signatures use the Shnorr protocol, which implements the second version of the Fiat-Shamir Heuristic. However, while calculating the challenge cc, a new public variable is added. This variable is usually called message mm, which is a transaction itself (meaning the transaction's hash). So, the verification of xx in y=gxy = g^x, knowing the message mm, looks the following way:

  1. The prover generates a random value rr and calculates a commitment t=grt = g^r.
  2. The prover calculates a challenge c=Hash(g,y,t,m)c = Hash(g, y, t, m).
  3. The prover calculates the response s=r+xcs = r + xc and sends a tuple (c,s)(c, s) to the verifier.
  4. The verifier calculates the commitment t=gsyct' = g^s y^{-c}, finds the challenge c=Hash(g,y,t,m)c' = Hash(g, y, t', m), and checks if c=cc' = c. If the challenges are equal, the signature is considered valid.

3.4 Sigma protocol for Pedersen Commitment

Sigma protocol adds a Zero Knowledge layer to the Pedersen Commitments usage, as the private values are initially revealed in the end.

3.4.1 Knowledge of the opening (v,r)(v,r) in Pedersen commitment

The prover wants to verify that they know the value vv and the random number rr from y=gvhry = g^v h^r.

  1. The prover generates random values r1r_1 and r2r_2 and calculates a commitment t=gr1hr2t = g^{r_1} h^{r_2}.
  2. The prover calculates the challenge c=Hash(g,h,y,t)c = Hash(g, h, y, t).
  3. The prover creates two responses s1=r1+vcs_1 = r_1 + vc and s2=r2+rcs_2 = r_2 + rc. And sends (t,s1,s2)(t, s_1, s_2) to the verifier.
  4. The verifier checks if the equation gs1hs2=tycg^{s_1} h^{s_2} = t y^c is correct.

💡

Note: for these examples, the number of random values that should be generated in the first step of every Sigma protocol is equal to the number of private variables. The private variables that should not be revealed to the verifier but still should be proved to be known (in the case of Pedersen commitment, the private variable is a value vv together with a random number rr in y=gvhry = g^v h^r ). As in the third step, the prover creates the same number of responses.

💡

If you want more examples of the Sigma protocol usage, check this source.

4 Recollection

💡

Elliptic Curves (EC) are one of the most well-known cryptographic primitives used in public-key encryption, blockchain, and Zero-Knowledge Proof. ECs are secure for large numbers, as the private key computation, also called the "elliptic curve discrete logarithm function," is infeasible for modern (non-quantum) computers.

💡

Pedersen commitments are used to transfer data that is in a small range securely, and that can be brute-forced. Pedersen commitments use Elliptic Curve Cryptography (ECC) as their basis, but they also add a Blinding factor, making the transferred data infeasible to learn.

💡

Pedersen commitments (like other commitments) have two main properties:

  1. Binding — the submitted values are defined and can not be altered after the commitment is created.
  2. Hiding — the submitted data stays hidden until the prover reveals it.

💡

Sigma protocol is an interactive Zero-Knowledge protocol that has three main steps/phases:

  1. Commitment phase. The prover creates a commitment and sends it to the verifier.
  2. Challenge phase. The verifier creates a challenge and sends it to the prover.
  3. Response phase. The prover calculates a response to the challenge and sends it to the verifier.

In the end verifier checks if the response is correct and tells the prover they are (the verifier) convinced.

💡

Sigma protocol has similarities with more well-known protocols: zk-SNARKs, Bulletproofs, and zk-STARKs, but they are not the same, and the mathematics used in those protocols is more advanced than for the Sigma protocols.

Moreover, compared to others, one of the main disadvantages of the Sigma protocol is that it relies on an honest verifier.

💡

Fiat-Shamir Heuristic helps make a Sigma protocol non-interactive and usable for applications.

💡

Schnorr protocol is one of the most used Sigma protocols.

💡

Shnorr signatures work based on non-interactive Schnorr protocols but add another public value to the equation, usually called message mm. In the context of blockchain, the message mm is a hash of the transaction where the signature is used.

5 Conclusion

This article provided an overview of several cryptographic primitives commonly used in Zero-Knowledge Proofs, including elliptic curve cryptography and Pedersen commitments. The article also described the structure and mechanics of Sigma protocols and demonstrated how they could be used to verify various data types, including Schnorr signatures. The following article will present a basic Proof of Concept for implementing Zero-Knowledge protocols.

More Resources

Elliptic Curve

Pedersen Commitment

Sigma protocol and Shnorr protocol

Shnorr signatures