go-zkp-schnorr

A modular Go library for zero-knowledge proofs focused on Schnorr proofs for authentication.

Sources

https://en.wikipedia.org/wiki/Schnorr_signature
https://crypto.stanford.edu/cs355/19sp/lec5.pdf
https://eprint.iacr.org/2021/1375.pdf
https://asecuritysite.com/golang/ecc_zkp

RFC 8235 - https://datatracker.ietf.org/doc/html/rfc8235

Installation

go get github.com/cedev-1/go-zkp-schnorr

Quick Start

Basic Schnorr Proof

package main

import (
    "fmt"
    "math/big"

    "github.com/cedev-1/go-zkp-schnorr/curves"
    "github.com/cedev-1/go-zkp-schnorr/schnorr"
)

func main() {
    // Use secp256k1 curve (compatible with Bitcoin/Ethereum)
    curve := curves.NewSecp256k1()

    // Create a secret key
    secret := big.NewInt(12345) // In production, use cryptographically secure random

    // Create prover
    prover, _ := schnorr.NewProver(curve, secret)
    fmt.Printf("Public Key: %x\n", prover.PublicKey().Bytes())

    // Generate a non-interactive proof
    message := []byte("authentication challenge")
    proof, _ := prover.ProveNonInteractive(message)

    // Verify the proof
    verifier := schnorr.NewVerifier(curve, prover.PublicKey())
    valid := verifier.VerifyNonInteractive(proof, message)
    fmt.Printf("Proof valid: %v\n", valid)
}

HTTP Authentication

// Server side
server := auth.NewServer(curves.NewSecp256k1())

// Generate challenge for client
sessionID, challenge, _ := server.GenerateChallenge()

// ... client generates proof ...

// Verify authentication
valid, _ := server.VerifyAuthWithSession(sessionID, authRequest)

// Client side
client, _ := auth.NewClientFromBytes(curves.NewSecp256k1(), secretKey)

// Generate proof for challenge
authRequest, _ := client.Authenticate(challenge)

Packages

Package	Description
curves	Elliptic curve abstractions (secp256k1, ed25519)
schnorr	Schnorr identification protocol implementation
auth	High-level authentication helpers

Mathematical Background

Discrete Logarithm Assumption

The security of this library relies on the hardness of the Discrete Logarithm Problem (DLP) in elliptic curve groups.

Given:

• A generator point G of a group of prime order n
• A scalar x (private key)
• A point Y = x \cdot G (public key)

It is computationally infeasible to determine x given G and Y.

Schnorr Identification Protocol

The Schnorr protocol is a Sigma protocol ($\Sigma$-protocol) that proves knowledge of a discrete logarithm without revealing it. It consists of three moves:

1. Commitment: The prover generates a random nonce k \in [1, n-1] and computes the commitment R = k \cdot G.
   • The prover sends R to the verifier.
2. Challenge: The verifier chooses a random challenge e \in [1, n-1].
   • The verifier sends e to the prover.
3. Response: The prover computes s = k + e \cdot x \pmod n.
   • The prover sends s to the verifier.

Verification: The verifier accepts the proof if and only if:

 s \cdot G \stackrel{?}{=} R + e \cdot Y 

Proof of Correctness

 s \cdot G = (k + e \cdot x) \cdot G = k \cdot G + e \cdot (x \cdot G) = R + e \cdot Y 

Non-Interactive Zero-Knowledge (NIZK)

To make the protocol non-interactive (e.g., for use in an HTTP API or blockchain), we apply the Fiat-Shamir heuristic.

Instead of receiving a random challenge from an interactive verifier, the prover computes the challenge as a cryptographic hash of the public parameters and the commitment:

 e = \mathcal{H}(G \parallel R \parallel Y \parallel m) 

Where:

• \mathcal{H} is a cryptographic hash function (e.g., SHA-256)
• G is the generator point
• m is an optional message bound to the proof (context)
• \parallel denotes concatenation

This transforms the interactive identification scheme into a digital signature scheme (Schnorr signature) or a non-interactive zero-knowledge proof (NIZK).

Security Properties

1. Completeness: An honest prover can always convince the verifier.
2. Special Soundness: A cheating prover without knowledge of x cannot convince the verifier (with probability 1/n).
3. Honest Verifier Zero-Knowledge (HVZK): The transcript (R, e, s) reveals no information about the secret x.

Security

This library implements several security best practices:

• Constant-time comparisons: Uses crypto/subtle.ConstantTimeCompare to prevent timing attacks
• Domain separation: Hash includes curve name to prevent cross-curve attacks
• Generator binding: Fiat-Shamir hash includes G to prevent generator substitution attacks
• Replay protection: Session-based challenges with single-use enforcement and TTL expiration
• Cryptographically secure randomness: Uses crypto/rand for all random values

Examples

See the examples directory for complete working examples:

• HTTP Authentication - Full client/server auth flow

Future

• Ring Signatures
• MuSig Aggregation

License

MIT License