Sigma Protocols

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:¶

• 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.¶

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.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.2. Witness representation

A witness is simply a list of num_scalars elements.¶

struct Witness {
    scalars: [Scalar; num_scalars] // The set of secret scalars
}

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
}

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)])

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.    }

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

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

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

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)

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

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

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)

def verify_batchable(statement, proof):
  sp = SigmaProtocol.new(statement)
  commitment = read_group_elements(proof)

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.¶

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()

bin_challenge = SHAKE128(iv).update(commitment).digest(scalar_bytes)
challenge = int(bin_challenge) % p

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)]

3.1. P-384

This ciphersuite uses P-384 [NISTCurves] for the Group.¶

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>.