Sigma Protocols for the Working Programmer

Introduction

In this article, we explore the fascinating world of sigma protocols, a class of zero-knowledge proofs that facilitate secure and private authentication within cryptographic systems.

As you immerse yourself in reading, you’ll uncover how they enable provers to demonstrate possession of secret information without actually revealing any of it.

You will learn how crucial these protocols are in various applications, including digital signature schemes and blockchain technology. I will discuss both the theoretical foundations and practical implementations that make sigma protocols a cornerstone in blockchain security.

What Are Sigma Protocols?

Sigma protocols are a powerful cryptographic tool used to prove statement validity without revealing additional information. Their primary applications lie in blockchain technology and secure transaction signing [1].

These protocols are named "sigma" due to their step structure, which resembles the Greek letter Σ. The process involves an exchange of messages between a prover and verifier.

The prover shares a commitment, responds to a challenge, and provides a response [2], while the verifier checks the proof, as shown in the diagram below.

One common example of sigma protocols is solving discrete logarithm problems[3]. There are two types of sigma protocols: interactive and non-interactive. Non-interactive protocols present a particular practical interest as they can be used in blockchains.

In blockchain technology, non-interactive sigma protocols allow users to prove knowledge of private keys without revealing them. This enables the use of public keys for identification and signature verification[3].

The Fiat-Shamir heuristic is an example of a non-interactive sigma protocol that allows provers to generate proofs in a single message by replacing random verifier challenges with a cryptographic hash function [4]. Provers can create independent proofs by simulating the verifier's role [4].

In transaction signing, non-interactive sigma protocols protect private keys while confirming transaction authenticity[3].

Overall, Blockchain technology benefits greatly from non-interactive sigma protocols, enabling efficient and secure communication without the need for back-and-forth interactions or revealing users' secret information [1].

Sigma Protocols in a Blockchain

To better understand sigma protocols, imagine this scenario: a blockchain user, Alice, wants to prove to the blockchain, represented by Bob, that she knows the private key associated with a specific public key, without actually revealing the private key.

In this case, public keys serve the dual purpose of identifying users (their network addresses or accounts) and verifying signatures.

In a non-interactive setting, Alice generates a proof in a single message using the Fiat-Shamir heuristic. This heuristic replaces the need for a random challenge from the verifier (the blockchain) with a cryptographic hash function based on the prover's (Alice's) initial message.

By simulating the verifier's role, Alice can create a proof independently of the verifier (Bob) and without interacting with him.

Suppose Alice wants to sign a transaction with her private key. A discrete logarithm problem is a common example of a sigma protocol used for this purpose.

Instead of directly revealing the private key, she computes the proof using the non-interactive sigma protocol based on the discrete logarithm problem. She then signs the transaction and sends the signed transaction along with the proof to the blockchain.

The blockchain, represented by Bob, verifies the proof to confirm that Alice knows the private key without ever learning the key itself. Once the transaction's authenticity is confirmed, the transaction is included in the next block.

Here's the pseudocode for generating a proof using the Fiat-Shamir heuristic:

function generate_proof(txBytes, public_key, private_key):
    random_value = generate_random_value()
    commitment = compute_commitment(random_value)

    // this is how Alice simulates the verifier and generates a challenge
    challenge = hash(txBytes ++ commitment) 
    response = compute_response(challenge, random_value, private_key)
    proof = (commitment, response)
    return proof

This way the interactive sigma protocol can be turned into a non-interactive proof, allowing Alice to prove her knowledge of the private key without revealing it.

Here's the pseudocode that outlines the steps for Bob (the blockchain) to verify the proof using the Fiat-Shamir heuristic:

function verify_proof(txBytes, public_key, proof):
    (commitment, response) = proof

    // Bob uses the same data and hash() to generate the same challenge 
    challenge = hash(txBytes ++ commitment)
    expected_commitment = compute_expected_commitment(response, challenge, public_key)
    if commitment == expected_commitment:
        return True  // Proof is valid
    else:
        return False // Proof is invalid

If the verification succeeds, it means Alice has proven her knowledge of the private key and Bob (the blockchain) can accept the transaction and add it to the next block.

Here, we need to look into definitions of compute_commitment, compute_response, and compute_expected_commitment, but first, let’s see how a sigma protocol can be implemented using elliptic curves.

Non-Interactive Sigma Protocol Over Elliptic Curves

Non-interactive Sigma protocols can be based on elliptic curves as shown in the following diagram:

In this diagram, Alice (the signer) and Bob (the verifier) are involved in a non-interactive Sigma protocol using discrete logarithm on an elliptic curve (EC) in multiplicative group notation for signing a message M (e.g. transaction bytes).

Let’s break it down:

Alice chooses a random value r in the range [0, q-1], where q is the large prime number representing the cyclic group's order.
Alice calculates R by raising the group generator G (fixed base point on the curve that is used as the starting point for generating other points on the curve) to the power of r (i.e., multiplication * of G with itself r times).
Alice calculates the challenge e as the hash of the message M, R and her public key A concatenated.
Alice calculates the response s as (r + a * e) mod q, where a is her private key, and the operations + and * are executed on big positive integers.
Alice shares the signature (e, s) and the message M with Bob.
Bob verifies the equation G^s * A^(-e) == R, where ^ is exponentiation (i.e., multiplication * of G with itself s times) and * is a group operation that multiplies two group elements. See Appendix A for the proof of this equation and why it implies knowledge of the private key a.
Based on the verification, Bob accepts or rejects the signature provided by Alice.

Note that here, we are using multiplicative notation. In multiplicative notation, the discrete logarithm problem (DLP) involves finding exponent x in G^x=Q, where G is a generator in a finite cyclic group.

In additive notation, the DLP refers to identifying scalar x in x*G=Q, where G is a base point on the curve and Q is a resulting point.

Now, with this notation, we can define the remaining functions.

The compute_commitment function takes a random value as input and calculates the commitment using the generator of the cyclic group (G) and the group order (q):

// Parameters:
// - random_value: a random number in [0, q-1] generated by Alice
function compute_commitment(random_value):
    // Constants:
    // - G: a generator of the cyclic group (prime order)
    // - q: a large prime number (group order)
    commitment = G^random_value
    return commitment

The compute_response function computes the response using the challenge, random value, and private key, taking into account the modulo operation with group order q:

// Parameters:
// - challenge: the hash of txBytes, commitment, and Alice's public_key
// - random_value: a random number generated by Alice
// - private_key: Alice's private key
function compute_response(challenge, random_value, private_key):
    response = (random_value + challenge * private_key) mod q
    return response

The function compute_expected_commitment computes the expected commitment using the response, challenge, and public key provided:

// Parameters:
// - response: the response value computed by Alice
// - challenge: the hash of the transaction bytes and the commitment
// - public_key: Alice's public key (G^private_key mod q)
function compute_expected_commitment(response, challenge, public_key):
    // Constants:
    // - G: a generator of the cyclic group (with prime order q)
    expected_commitment = G^response * public_key^(-challenge)
    return expected_commitment

If the expected commitment matches the commitment received from Alice, the signature is considered valid.

Now that we know how to prove and verify propositions such as "I know the private key for a given public key," we can now construct more complex propositions that can be proven and verified using sigma protocols.

Sigma Propositions

As we have seen above, sigma protocols can be used to sign a transaction. Alice can generate a signature using her private key a and sign a transaction, which proves to Bob that she knows the secret key for her public key A.

In the blockchain, parties are typically identified by their public keys, i.e., Alice is identified by A, Bob by B, etc. Therefore, any signature from Alice corresponds to a verifiable proposition such as “signed by A”.

From this perspective, a simple signature like “signed by A” can be combined with “signed by B” using OR or AND logical operations, where A and B are public keys. We can write A OR B to mean “signed by A or B”

With sigma protocols, such statements can be made provable (and verifiable). For example, it is possible to prove the statement “signed by A or B” with “zero knowledge” of who signed it (Alice or Bob).

Let’s look at examples. Say we have public keys A, B, C, D. In that case, we can formulate the following propositions:

Formula	What it means
`A`	signed by A
`B`	signed by B
`A OR B`	signed by A or signed by B
`A AND B`	signed by both A and B
`(A OR B) AND (C OR D)`	presented 2 signatures: one by A or B and another by C or D
`(A AND C) OR (A AND D)`	both A and C signed or both A and D signed

It is also remarkable that multiple independent signatures can be combined for a transaction message M, without revealing any secrets. Co-signers can work together to generate a signature for an arbitrary complex proposition, without sharing their private keys.

In practice, there is also THRESHOLD operation (a.k.a. k-out-of-n threshold signature) which generalizes both OR and AND. For example, OR(A,B) can be expressed as THRESHOLD(1, A, B), and AND(A,B) as THRESHOLD(2, A, B).

The first parameter k specifies how many signatures are required from the list of public keys.

Threshold signatures are useful for blind voting, or keeping assets in a foundation wallet, spendable by a committee. When incorporated into smart contracts (like those in the Ergo blockchain) such propositions become the building blocks of complex financial contracts.

A OR B, That Is the Question

Consider the simplest case, A OR B. We want to prove that a message was signed by either party A or party B, without revealing which one exactly. Let’s see how such a signature can be generated and why, by checking it, the verifier cannot identify the signing party.

The key idea here is proof simulation.

Proof Simulation

Remember that a sigma protocol (see the diagram above) involves interaction between the prover and verifier. Any such interaction results in three components:

R — a commitment created by the prover;

e — a challenge created by the verifier;

s — a response created by the prover.

In a non-interactive sigma protocol, all these values can be computed by the prover.

Provided with these three values, the verifier can check them against the public key and the message that was signed.

In the so-called “real” case, such parameters are computed based on the actual private key. However, it is possible to create (or simulate) (R’, e’, s’) for any public key A so that the verifier will accept it as a signature for A.

Now, let's outline the simulation procedure using the same elliptic curve group we used before. Here is the pseudocode:

Simulator(y, e):
    // Step 1: Choose a random response 's' uniformly at random 
    // from the order q of the EC group.
    // Important to use the same secure random generator as used by
    // both the real prover and verifier
    1. Choose random s in [0, q-1]

    // Step 2: Compute the commitment 'R' that would have led to 
    // the response 's' for the challenge 'e'
    2. Calculate R = (G^s * y^(-e)) mod q
    
    // Step 3: Return the simulated conversation (R, e, s) which have
    // the same probability distribution as a real conversation
    // and thus indistinguishable from it
    3. Return (R, e, s)

In the context of the Simulator function, the input parameters G, y, e have the following meanings:

G: This is the generator, which belongs to the multiplicative elliptic curve EC group of prime order q. G generates all other elements in the group through repeated exponentiation. Put simply, any element of the EC group can be written as G raised to some power x, or G^x.
y: This is the public key corresponding to a secret key x, such that y = G^x mod q. The public key y is an element of the EC group and is known to all parties involved in the protocol, including the verifier and any potential eavesdroppers.
e: This is the challenge provided by the verifier in an interactive zero-knowledge proof protocol. In the context of the Simulator function, the challenge e is chosen by the simulator to generate a simulated conversation that appears indistinguishable from a real conversation between a prover and a verifier.

The Simulator function takes these parameters as input and generates a simulated conversation (R, e, s) that is indistinguishable from a real conversation between a prover and verifier in a zero-knowledge proof protocol.

Proving A OR B

Equipped with the simulator, we can now define the steps to prove A OR B as shown in the following pseudocode:

// A: The prover's public key for the first statement
// B: The prover's public key for the second statement
// x: The prover's secret key for A
// message: The message to be signed
Prover(A, B, x, message):
    // Step 0: Choose a random value 'w' from the order q of the EC group    
    0. Choose random w in [0, q-1]

    // Step 1: Compute the first commitment using the secret witness
    1. R0 = G^w mod q

    // Step 2: Choose a random challenge for the second statement B
    2. Choose random e1 // array of 32 bytes

    // Step 3: Simulate a conversation for the second statement
    3. (R1, e1, s1) = Simulator(B, e1)

    // Step 4: Compute cryptographic hash 
    4. s = H(R0, R1, message) // s - typically an array of 32 bytes

    // Step 5: Compute the challenge for the first statement using XOR 
    5. e0 = s ⊕ e1

    // Step 6: Compute the response for the first statement 
    6. s0 = (w + x * e0) mod q  // operations with big integers

    // Step 7: Construct the signature (format parsable by the verifier)
    7. signature = (R0, R1, e0, s0, e1, s1)
    8. Return signature.

The signature generated by the prover can be verified using the following procedure:

// A: The prover's public key for the first statement
// B: The prover's public key for the second statement
// message: The message to be signed
// signature: The signature generated by the prover
Verifier(A, B, message, signature):
    // Step 1: Parse the signature into its components
    1. Parse signature as (R0, R1, e0, s0, e1, s1)

    // Step 2: Compute cryptographic hash 
    2. s = H(R0, R1, message) // same H function used by the prover

    // Step 3: Check challenges using XOR
    3. Check if s = e0 ⊕ e1

    // Step 4: Check if both conversations are valid
    4. ValidConversation(A, R0, e0, s0) and ValidConversation(B, R1, e1, s1)
    5. If all checks pass, accept the signature. Else, reject.

ValidConversation(y, R, e, s):
    R = G^s * y^(-e) mod q

Implementation

The general procedure for proving and verifying arbitrary sigma propositions is quite involved. It is, however, implemented and used by the Ergo blockchain for signing and verifying transactions.

The implementation is outlined in smart contracts interpreter of Ergo (See Interpreter and ProvingInterpreter classes in the source code ). It is also explained in this paper, Appendix A.

In a sense, this article can serve as a starting point to get a grasp of the basics before proceeding to the more elaborate explanation in the above-mentioned sources.

Ergo supports two basic (or atomic) sigma protocols:

proveDlog(x) used for proving knowledge of the discrete logarithm w of x = G^w;
proveDHtuple(g1, g2, u1, u2) used for proving that (g1, g2, u1, u2) form a Diffie-Hellman tuple, i.e. proving knowledge of w such that u1 = g1^w and u2 = g2^w.

Moreover, Ergo’s implementation supports the signing of an arbitrary sigma proposition built using AND, OR, and THRESHOLD logical operations. For further details regarding the implementation, please refer to the aforementioned paper and source code.

Conclusion

Let us recap the key points:

Sigma protocols are cryptographic tools that allow users to prove the validity of a statement without revealing any additional information. They are particularly useful in blockchain technology and secure transaction signing.

The protocols can be interactive or non-interactive, with the latter being more practical for blockchains.

In a blockchain context, a user can prove knowledge of their private key without disclosing it, allowing public keys to be used for identification and signature verification. The Fiat-Shamir heuristic is a non-interactive sigma protocol that enables efficient and secure communication without back-and-forth interactions or revealing secret user information.

Sigma protocols can also be used for proving and verifying more complex propositions, such as combining multiple public keys with logical operations like AND, OR, and THRESHOLD. These propositions can be used as building blocks for complex financial contracts on Ergo blockchain.

Appendix A: Why Is the Verification Formula Correct?

First let's rewrite the equation G^s * A^(-e) == R as G^s == R * A^e.

To demonstrate the correctness of the verification equation G^s == R * A^e when s is defined as s = (r + a * e) mod q, let's consider the following steps:

s = (r + a * e) mod q
G^s = G^(r + a * e) (substitute s with its definition)
G^s = G^(r) * G^(a * e) (using the property a^(m+n) = a^m * a^n)
Recall that A = G^a, which is Alice's public key. We can rewrite G^(a * e) as A^e, thus
G^s = G^r * A^e
Recall that G^r is equal to R, as R = G^r by definition
So we get G^s == R * A^e