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 + Sub + Mul + From + Eq + Serialize + Deserialize Scalar: Zero + One + Div + Add + Sub + From + Eq + 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; 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, . 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, . [SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1: Elliptic Curve Cryptography", . Author's Address Michele Orrù CNRS Email: m@orru.net Orrù Expires 30 August 2025 [Page 13]