go-zkp

README

Schnorr Non-Interactive Zero Knowledge Proof using discrete log over prime number cyclic group

https://datatracker.ietf.org/doc/html/rfc8235

• This has been made non-interactive using Fiat-Shamir Transformation and using a secure cryptographic hash function to issue the challenge
• No interaction is necessary between prover and verifier

Assumptions

• Fp is a finite field of p elements where p is prime
• E(Fp) is an elliptic curve over Fp
• P is a very large prime number over the curve representing our private key value
• G is a generator point over the curve that serves as a generator for the subgroup E(Fp) of prime order n
• Cofactor H is ignored for secp256k1 EC

Algorithm

Prover

• Create Keypair
• Create Random
• Create Challenge (sha256sum of Gx, Random, Pubkey )
• Compute r
• Send r and Pubkey and Random to Verifier

Verifier

• Verify Pubkey of Prover to be on the elliptic Curve
• Verify Proof using sent challenge (sha256 format) with the Random

Some Research

Elliptic Curve Secp256k1

• p = (2^256)-(2^32)–(2^9)–(2^8)–(2^7)–(2^6)–(2^4) -(1)
• a=0, b=7
• GG =(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)
• n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Zero Knowledge Proofs

• Zero knowledge proofs are cryptographic protocols that allow a prover to prove that they have some knowledge of a certain kind, without revealing any additional information about that knowledge
• Digital Signatures are a bit like zkp
• A ZKPOK or Zero Knowledge Proof of Knowledge scheme for a particular language consists of a prover and verifier satisying the following properties:
  • Correctness
  • Zero Knowledge
  • Proof of Knowledge
• Sigma Protocol for knowledge of discrete log
  • ZKPOK{(a): g^a = A}
  • Here g is the geenrator of a group G of prime order p
• Sigma protocol can be modified to a digital signature scheme by using Schnorr Signature scheme
• Cyclic groups are generated by a single element G =