Network Working Group M. Orrù
Internet-Draft CNRS
Intended status: Informational 26 February 2025
Expires: 30 August 2025
Sigma Protocols
draft-orru-zkproof-sigma-protocols-00
Abstract
This document describes Sigma protocols, a secure, general-purpose
non-interactive zero-knowledge proof of knowledge. Concretely, the
scheme allows proving knowledge of a witness, without revealing any
information about the undisclosed messages or the signature itself,
while at the same time, guarantying soundness of the overall
protocols.
About This Document
This note is to be removed before publishing as an RFC.
The latest revision of this draft can be found at
https://mmaker.github.io/stdsigma/draft-orru-zkproof-sigma-
protocols.html. Status information for this document may be found at
https://datatracker.ietf.org/doc/draft-orru-zkproof-sigma-protocols/.
Source for this draft and an issue tracker can be found at
https://github.com/mmaker/stdsigma.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 30 August 2025.
Orrù Expires 30 August 2025 [Page 1]
Internet-Draft Sigma Protocols February 2025
Copyright Notice
Copyright (c) 2025 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Generic interface . . . . . . . . . . . . . . . . . . . . 3
2. Σ-protocols over prime-order groups . . . . . . . . . . . . . 5
2.1. Group abstraction . . . . . . . . . . . . . . . . . . . . 5
2.1.1. Group . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2. Scalar . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Witness representation . . . . . . . . . . . . . . . . . 6
2.2.1. Constraint representation . . . . . . . . . . . . . . 6
2.3. Core protocol . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1. Verifier procedure . . . . . . . . . . . . . . . . . 10
2.3.2. Prover . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.3. Verifier . . . . . . . . . . . . . . . . . . . . . . 10
2.4. Nonce and challenge derivation . . . . . . . . . . . . . 11
2.4.1. Statement generation . . . . . . . . . . . . . . . . 11
3. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1. P-384 . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.1. Elliptic curve group of P-384 (secp384r1)
NISTCurves . . . . . . . . . . . . . . . . . . . . . 12
3.1.2. Scalar Field of P-384 (secp384r1) . . . . . . . . . . 12
4. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 13
5. References . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1. Normative References . . . . . . . . . . . . . . . . . . 13
5.2. Informative References . . . . . . . . . . . . . . . . . 13
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13
1. Introduction
A Sigma Protocol is a simple zero-knowledge proof of knowledge. Any
sigma protocols must define three objects:
* A commitment, sometimes also called nonce. This message is
computed by the prover.
* A challenge, computed using the Fiat-Shamir transformation using a
hash function.
Orrù Expires 30 August 2025 [Page 2]
Internet-Draft Sigma Protocols February 2025
* A response, computed by the prover, which depends on the
commitment and the challenge.
A sigma protocol allows to convince a *verifier* of the knowledge of
a secret *witness* satisfying a *statement*.
1.1. Generic interface
A sigma protocol is an interface exposing the following functions:
def prove_short(label, statement, witness):
sp = SigmaProtocol.new(statement)
(prover_state, commitment) = sp.prover_commmit(witness)
challenge = SHO
.init(label)
.absorb(commitment)
.squeeze(1)
response = sp.prover_response(commitment, challenge)
return scalar_to_bytes(challenge) + scalar_to_bytes(response)
def prove_batchable(label, statement, witness):
sp = SigmaProtocol.new(statement)
(prover_state, commitment) = sp.prover_commit(witness)
challenge = SHO
.init(label)
.absorb(commitment)
.squeeze(1)
response = sp.prover_response(commitment, challenge)
return point_to_bytes(commitment) + scalar_to_bytes(response)
def verify_batchable(label, statement, proof):
sp = SigmaProtocol.new(statement)
commitment = read_group_elements(proof)
Internally, each sigma protocol implements the following methods.
class SigmaProtocol:
def new(instance: Statement) -> SigmaProtocol
def prover_commit(self, witness: Witness) -> (commitment, prover_state)
def prover_response(self, prover_state, challenge) -> response
def verifier(self, commitment, challenge, response) -> bool
# optional
def simulate_response() -> response
# optional
def simulate_commitment(response, challenge) -> commitment
Where:
Orrù Expires 30 August 2025 [Page 3]
Internet-Draft Sigma Protocols February 2025
* new(il: [u8], cs: ConstraintSystem) -> SigmaProtocol, denoting the
initialization function. This function takes as input a label
identifying local context information (such as: session
identifiers, to avoid replay attacks; protocol metadata, to avoid
hijacking; optionally, a timestamp and some pre-shared randomness,
to guarantee freshness of the proof) and an instance generated via
the ConstraintSystem, the public information shared between prover
and verifier. This function should pre-compute parts of the
statement, or initialize the state of the hash function.
* prover_commit(self, witness: Witness) -> (commitment,
prover_state), denoting the *commitment phase*, that is, the
computation of the first message sent by the prover in a Sigma
protocol. This method outputs a new commitment together with its
associated prover state, depending on the witness known to the
prover and the statement to be proven. This step generally
requires access to a high-quality entropy source. Leakage of even
just of a few bits of the nonce could allow for the complete
recovery of the witness. The commitment meant to be shared, while
prover_state must be kept secret.
* prover_response(self, prover_state, challenge) -> response,
denoting the *response phase*, that is, the computation of the
second message sent by the prover, depending on the witness, the
statement, the challenge received from the verifier, and the
internal state prover_state. The returned value response is meant
to be shared.
* verifier(self, commitment, challenge, response) -> bool, denoting
the *verifier algorithm*. This method checks that the protocol
transcript is valid for the given statement. The verifier
algorithm outputs nothing if verification succeeds, or an error if
verification fails.
The final two algorithms describe the *zero-knowledge simulator* and
are optional. The simulator is primarily an efficient algorithm for
proving zero-knowledge in a theoretical construction, but it is also
needed for verifying short proofs and for or-composition, where a
witness is not known and thus has to be simulated. We have:
* simulate_response() -> response, denoting the first stage of the
simulator. It is an algorithm drawing a random response that
follows the same output distribution of the algorithm
prover_response
* simulate_commitment(response, challenge) -> commitment, returning
a simulated commitment -- the second phase of the zero-knowledge
simulator.
Orrù Expires 30 August 2025 [Page 4]
Internet-Draft Sigma Protocols February 2025
The abstraction SigmaProtocol allows implementing different types of
statements and combiners of those, such as OR statements, validity of
t-out-of-n statements, and more.
2. Σ-protocols over prime-order groups
The following sub-section present concrete instantiations of
Σ-protocols over prime-order groups such as elliptic curves.
Traditionally, Σ-protocols are defined in Camenish-Stadtler notation
as (for example):
VRF(A, B, G, H) = PoK{
(x): // Secret variables
A = x * B, // Statements to prove
G = x * H
}
This section describes how to build and prove statements of this form
programmatically.
2.1. Group abstraction
Because of their dominance, the presentation in the following focuses
on proof goals over elliptic curves, therefore leveraging additive
notation. For prime-order subgroups of residue classes, all notation
needs to be changed to multiplicative, and references to elliptic
curves (e.g., curve) need to be replaced by their respective
counterparts over residue classes. We therefore assume two objects
are available to the programmer:
Group: Zero + Add<Group> + Sub<Group> + Mul<Scalar> + From<int> + Eq<Group> + Serialize + Deserialize
Scalar: Zero + One + Div<Scalar> + Add<Scalar> + Sub<Scalar> + From<int> + Eq<Group> + Serialize + Deserialize
We detail the functions that can be invoked on these objects.
Example choices can be found in Section 3.
2.1.1. Group
* order(): Outputs the order of the group p.
* random(): outputs a random element
* serialize([Group; N]): serializes a list of group elements and
returns a canonical byte array buf of fixed length Ng * N.
Orrù Expires 30 August 2025 [Page 5]
Internet-Draft Sigma Protocols February 2025
* deserialize(buf): Attempts to map a byte array buf of size Ng * N
into [Group; N], and fails if the input is not the valid canonical
byte representation of an element of the group. This function can
raise a DeserializeError if deserialization fails.
2.1.2. Scalar
* random(): outputs a random element
* serialize([Scalar; N]): serializes a list of scalars and returns
their canonical representation of fixed length Ns * N.
2.2. Witness representation
A witness is simply a list of num_scalars elements.
struct Witness {
scalars: [Scalar; num_scalars] // The set of secret scalars
}
2.2.1. Constraint representation
Internally, the constraint can be represented as:
struct Equations {
// the list of statements to be proven
matrix: [LinearCombination<ScalarIndex, &Group>; num_statements]
// An list of references to group elements representing the left-hand side part of the equations
image: [&Group; num_statements]
// the number of secret scalars
num_scalars: usize
// the number of equations to be proven
num_statements: usize
}
The object LinearCombination encodes pairs of indices of the witness
vector with group elements. The initial example of the VRF can
therefore be expressed with the following constraints:
cs = Equations()
[x] = cs.allocate_scalars(1)
[A, B, G, H] = cs.allocate_group_elt(4)
cs.append_equation(lhs=A, rhs=[(x, B)])
cs.append_equation(lhs=G, rhs=[(x, H)])
In the above, Equations.new() creates a new Equations with label
"VRF".
Orrù Expires 30 August 2025 [Page 6]
Internet-Draft Sigma Protocols February 2025
2.2.1.1. Instantiation of the constraints
new(label)
Inputs:
- labels, a byte array
Outputs:
- a ConstraintSystem instance
Procedure:
1. return Equations {
2. label,
3. num_statements: 0,
4. num_scalars: 0,
5. group_elements: [],
6. matrix: [],
7. image: []
8. }
2.2.1.2. Scalar witness allocation
allocate_scalars(self, n)
Inputs:
- self, the current state of the ConstraintSystem
- n, the number of scalars to allocate
Outputs:
- indices, a list of integers each pointing to the new allocated scalars
Procedure:
1. indices = range(self.num_scalars, self.num_scalars + n)
2. self.num_scalars += n
3. return indices
2.2.1.3. Public group element allocation
Orrù Expires 30 August 2025 [Page 7]
Internet-Draft Sigma Protocols February 2025
allocate_group_elt(self, n)
Inputs:
- self, the current state of the constraint system
- n, the number of group elements to allocate
Outputs:
- indices, a list of integers each pointing to the new allocated group elements.
Procedure:
1. indices = range(len(self.group_elts), len(self.group_elements) + n)
2. self.group_elements.extend([None] * n)
3. return indices
2.2.1.4. Group element assignment
assign_point(self, ptr, value)
Inputs:
- self, the current state of the constraint system
- ptr, the pointer to the group element to be assigned
- value, the value to be assigned to the group element
Procedure:
1. self.group_elements[ptr] = value
2.2.1.5. Enforcing an equation
This function adds an equation statement constraint to the instance,
expressed as a left-hand side (the target group element), and a list
of pairs encoding a linear combination of scalars and group elements.
Orrù Expires 30 August 2025 [Page 8]
Internet-Draft Sigma Protocols February 2025
append_equation(self, lhs, rhs)
Inputs:
- self, the current state of the constraint system
- lhs, the left-hand side of the equation
- rhs, the right-hand side of the equation (a list of (ScalarIndex, GroupEltIndex) pairs)
Outputs:
- An Equation instance that enforces the desired relation
Procedure:
1. self.num_statements += 1
2. self.image.append(lhs)
3. self.matrix.append(rhs)
A witness can be mapped to a group element via:
def map(self, witness: [Scalar; num_scalars]):
assert self.num_scalars = self.scalars.len()
image = [0; Group]
for i in range(self.num_statements):
eq_scalars = [self.scalars[idx_pair[0]]
for idx_pair in self.matrix[i]]
eq_group_elt = [self..group_elements[idx_pair[1]] for idx_pair in self.matrix[i]]
image[i] = multi_scalar_multiplication(eq_scalars, eq_group_elt)
return image
2.3. Core protocol
class SigmaProtocol:
def new(statement: Statement):
self.statement = statement
def prover_commit(self, witness: Witness):
nonces = Scalar::random()
prover_state = (witness, nonces)
commitment = self.statement.map(witness)
return (prover_state, commitment)
def prover_response(self, prover_state, challenge):
response = [0; self.cs.num_scalars]
for i in range(self.cs.num_scalars):
response[i] = witness[i] + challenge * nonces[i]
return response
Orrù Expires 30 August 2025 [Page 9]
Internet-Draft Sigma Protocols February 2025
2.3.1. Verifier procedure
verify(self, commitment, challenge, response)
Inputs:
- self, the current state of the SigmaProtocol
- commitment, the commitment generated by the prover
- challenge, the challenge generated by the verifier
- response, the response generated by the prover
Outputs:
- A boolean indicating whether the verification succeeded
Procedure:
1. image = [equation.lhs for equation in self.statement.equations]
2. expected_commitment = challenge * image + self.statement.map(response)
3. return expected_commitment == commitment
2.3.2. Prover
We describe below the prover's wrapping function.
def prove_short(statement, witness):
sp = SigmaProtocol.new(statement)
(prover_state, commitment) = sp.prover_commmit(witness)
challenge = sp.challenge(commitment)
response = sp.prover_response(commitment, challenge)
return scalar_to_bytes(challenge) + scalar_to_bytes(response)
def prove_batchable(statement, witness):
sp = SigmaProtocol.new(statement)
(prover_state, commitment) = sp.prover_commmit(witness)
challenge = sp.challenge(commitment)
response = sp.prover_response(commitment, challange)
return point_to_bytes(commitment) + scalar_to_bytes(response)
2.3.3. Verifier
def verify_batchable(statement, proof):
sp = SigmaProtocol.new(statement)
commitment = read_group_elements(proof)
Orrù Expires 30 August 2025 [Page 10]
Internet-Draft Sigma Protocols February 2025
2.4. Nonce and challenge derivation
Two types of randomness are needed for a sigma protocol:
1. A nonce seeding the randomness used to produce the commitment of
the first round of the protocol
2. A challenge representing the verifier's public random coin.
The challenge of a Schnorr proof is derived with
challenge = sho.init(iv).absorb_group_elt(commitment).squeeze_scalar(1)
This can be generated with:
nonce = sho.init(iv)
.absorb_bytes(random)
.ratchet()
.absorb_scalars(witness)
.squeeze_scalars(cs.num_scalars)
The iv, which must properly separate the application and the
statement being proved, is described below.
2.4.1. Statement generation
Let H be a hash object. The statement is encoded in a stateful hash
object as follows.
hasher = H.new(domain_separator)
hasher.update_usize([cs.num_statements, cs.num_scalars])
for equation in cs.equations:
hasher.update_usize([equation.lhs, equation.rhs[0], equation.rhs[1]])
hasher.update(generators)
iv = hasher.digest()
In simpler terms, without stateful hash objects, this should
correspond to the following:
bin_challenge = SHAKE128(iv).update(commitment).digest(scalar_bytes)
challenge = int(bin_challenge) % p
and the nonce is produced as:
Orrù Expires 30 August 2025 [Page 11]
Internet-Draft Sigma Protocols February 2025
bin_nonce = SHAKE128(iv)
.update(random)
.update(pad)
.update(cs.scalars)
.digest(cs.num_scalars * scalar_bytes)
nonces = [int(bin_nonce[i*scalar_bytes: i*(scalar_bytes+1)]) % p
for i in range(cs.num_scalars-1)]
Where: - pad is a (padding) zero string of length 168 - len(random).
- scalar_bytes is the number of bytes required to produce a uniformly
random group element - random is a random seed obtained from the
operating system memory
3. Ciphersuites
3.1. P-384
This ciphersuite uses P-384 [NISTCurves] for the Group.
3.1.1. Elliptic curve group of P-384 (secp384r1) [NISTCurves]
* order(): Return 0xffffffffffffffffffffffffffffffffffffffffffffffff
c7634d81f4372ddf581a0db248b0a77aecec196accc52973.
* serialize([A]): Implemented using the compressed Elliptic-Curve-
Point-to-Octet-String method according to [SEC1]; Ng = 49.
* deserialize(buf): Implemented by attempting to read buf into
chunks of 49-byte arrays and convert them using the compressed
Octet-String-to-Elliptic-Curve-Point method according to [SEC1],
and then performs partial public-key validation as defined in
section 5.6.2.3.4 of [KEYAGREEMENT]. This includes checking that
the coordinates of the resulting point are in the correct range,
that the point is on the curve, and that the point is not the
point at infinity.
3.1.2. Scalar Field of P-384 (secp384r1)
* serialize(s): Relies on the Field-Element-to-Octet-String
conversion according to [SEC1]; Ns = 48.
* deserialize(buf): Reads the byte array buf in chunks of 48 bytes
using Octet-String-to-Field-Element from [SEC1]. This function
can fail if the input does not represent a Scalar in the range [0,
G.Order() - 1].
Orrù Expires 30 August 2025 [Page 12]
Internet-Draft Sigma Protocols February 2025
4. Acknowledgments
Jan Bobolz, Stephan Krenn, Mary Maller, Ivan Visconti, Yuwen Zhang.
5. References
5.1. Normative References
[KEYAGREEMENT]
Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R.
Davis, "Recommendation for pair-wise key-establishment
schemes using discrete logarithm cryptography", National
Institute of Standards and Technology,
DOI 10.6028/nist.sp.800-56ar3, April 2018,
<https://doi.org/10.6028/nist.sp.800-56ar3>.
5.2. Informative References
[NISTCurves]
"Digital signature standard (DSS)", National Institute of
Standards and Technology (U.S.),
DOI 10.6028/nist.fips.186-4, 2013,
<https://doi.org/10.6028/nist.fips.186-4>.
[SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1:
Elliptic Curve Cryptography",
<https://www.secg.org/sec1-v2.pdf>.
Author's Address
Michele Orrù
CNRS
Email: m@orru.net
Orrù Expires 30 August 2025 [Page 13]