adjoint-io / schnorr-nizk

The purpose of the Schnorr protocol is to allow one to prove the knowledge of a discrete logarithm without revealing its value.

Schnorr Identification Scheme

The Schnorr protocol is an example of a Sigma protocol (-protocol). A Sigma protocol is a three-step protocol in which communication between prover and verifier goes forwards once, then backwards, then forwards again. In general terms:

• : commitment
• : challenge
• : response (proof)

The protocol is defined for a cyclic group of order .

The prover aims to convince the verifier that he knows some private value . Therefore, (see [1]) will be her public key. In order to prove knowledge of it, the prover interacts with the verifier in three passes:

• The prover commits to a random private value , chosen in the range . This is the first message commitment .

• The verifier replies with a challenge chosen at random from .

• After receiving the challenge, the prover sends the third and last message (the response) .

The verifier accepts, if:

• The prover's public key, , is a valid public key. It means that it must be a valid point on the curve and is not a point at infinity, where is the cofactor of the curve.
• The prover's commitment value is equal to

Zero Knowledge Proofs

Zero knowledge proofs are a way by which one party succeeds in convincing another party that she knows a private value without exposing any information apart from the fact that she knows the value .

All proof systems have two requirements:

• Completeness: An honest verifier will be convinced of this fact by an untrusted prover.

• Soundness: No prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small probability.

It is assumed that the verifier is always honest.

Schnorr NIZK proof

The original Schnorr identification scheme is made non-interactive through a Fiat-Shamir transformation, assuming that there exists a secure cryptographic hash function (i.e., the so-called random oracle model).

An oracle is considered to be a black box that outputs unpredictable but deterministic random values in response to a certain input. That means that, given the same input, the oracle will give back the same random output. The input to the random oracle, in the Fiat-Shamir heuristic, is specifically the transcript of the interaction up to that point. The challenge is then redefined as , where is a secure cryptographic hash function like SHA-256. The bit length of the hash output should be at least equal to that of the order of the considered subgroup.

An example of the Schnorr protocol for Non-Interactive Zero-Knowledge Proofs looks as follows.

testSchnorrNIZK :: IO Bool
testSchnorrNIZK = do
  -- Setup
  let curveName = Curve25519
      basePoint = Curve.g curveName
  keyPair@(pk, sk) <- genKeys curveName basePoint

  -- Prover
  proof <- Schnorr.prove curveName basePoint keyPair

  -- Verifier
  pure (Schnorr.verify curveName basePoint pk proof)

Curves

This Schnorr implementation offers support for both SECP256k1 and Curve25519 curves, which are Koblitz and Montgomery curves, respectively.

• SECP256k1
• Curve25519

References:

1. Hao, F. "Schnorr Non-interactive Zero-Knowledge Proof." Newcastle University, UK, 2017
2. Schnorr Non-interactive Zero-Knowledge Proof https://tools.ietf.org/html/rfc8235

Notation:

1. : multiplication of a point with a scalar over an elliptic curve defined over a finite field modulo a prime number

Disclaimer

This is experimental code meant for research-grade projects only. Please do not use this code in production until it has matured significantly.

License

Copyright 2018-2020 Adjoint Inc

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.