zksigma

package module
v0.0.0-...-a6a19e8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 13, 2019 License: MIT Imports: 12 Imported by: 2

README

zkSigma

WARNING: zkSigma is research code and should not be used with sensitive data. It definitely has bugs!

zkSigma is a library for generating non-interactive zero-knowledge proofs, also known as NIZKs. The proofs in zkSigma are based on Generalized Schnorr Proofs; they can be publicly verified and do not require any trusted setup.

Features:

  • Generating non-interactive zero-knowledge proofs for various logical statements
  • Simplified elliptic curve operations
  • Plug and Play API
  • Built in serialization and deserialization of proofs

Statements that can be proved:

  • I can open a Pedersen Commitment A(=aG+uH) (Open)
  • I know the discrete log of a commitment A(=aG) (GSPFS Proof)
  • I know the discrete log of commitments A(=xG) and B(=xH) and they are equal (Equivalence Proof)
  • I know the discrete log of either commitment A or B (Disjunctive Proof)
  • I know that the blinding factor of commitments A and B is equal (Consistency Proof)
  • I know a, b, and c in commitments A, B and C and a * b = c (ABC Proof)
  • I know a and b in commitments A and B and a != b (InequalityProof is a special case of ABC Proof)

Running the tests:

  • Will show debugging messages, good for debugging a proof that is not generating or verifying
go test -debug1
  • Run rangeproof tests (default: off)
go test -range

Notation:

  • lower case letters are scalars (a, b, c, x,...)
  • lower case letters starting with u are randomly generated scalars (ua, ub, u1, u2, ...)
  • upper case letters are always elliptic curve points (type ECPoint) (G, H, A, B,...)
    • G = Base Point of ZKCurve.C
    • H = Secondary Base Point whose relation to G should not be known
    • A, B, CM, CMTok, etc, are usually of the form vG+uH unless otherwise stated
  • sk and PK are always secret key and public key. sk is a randomly chosen scalar. PK = sk * H
  • CM = Commitment of the form aG + uH
  • CMTok = Commitment Token of the form ua * PK

Sigma Protocols : A three step protocol where a prover and verifier can exchange a commitment and a challenge in order to verify proof of knowledge behind the commitment. Simple explanation here.

Unifying Zero-Knowledge Proofs of Knowledge : This paper explains zero-knowledge proof of knowledge and provides the foundation on which all our proofs are built upon.

zkLedger : A privacy preserving distributed ledger that allows for verifiable auditing. The original motivation for creating zksigma.

Bulletproofs : A faster form of rangeproofs that only requires log(n) steps to verify that a commitment is within a given range. This might be integrated into this library in the future.

Comparison to zkSNARKS

You cannot use zkSigma to prove general statements.

Documentation

Overview

**WARNING: zkSigma is research code and should not be used with sensitive data. It definitely has bugs!**

zkSigma is a library for generating non-interactive zero-knowledge proofs, also known as NIZKs. The proofs in zkSigma are based on Generalized Schnorr Proofs; they can be publicly verified and do not require any trusted setup.

Features:

* Generating non-interactive zero-knowledge proofs for various logical statements

* Simplified elliptic curve operations

* Plug and Play API

More info on Github

Index

Constants

This section is empty.

Variables

View Source 
var BigZero *big.Int

BigZero contains a cached instance of big.Int with value 0

View Source 
var DEBUG = flag.Bool("debug1", false, "Debug output")

DEBUG Indicates whether we output debug information while running the tests. Default off.

Functions

func GenerateChallenge 

func GenerateChallenge(zkpcp ZKPCurveParams, arr ...[]byte) *big.Int

GenerateChallenge hashes the passed byte arrays using SHA-256, and then returns the resulting hash as a big.Int modulo the order of the curve base point

func Open 

func Open(zkpcp ZKPCurveParams, value, randomValue *big.Int, pcomm ECPoint) bool

Open checks if the values given result in the given Pedersen commitment

func ReadBigInt 

func ReadBigInt(r io.Reader) (*big.Int, error)

ReadBigInt reads a big.Int from io.Reader r

func VerifyR 

func VerifyR(zkpcp ZKPCurveParams, rt ECPoint, pk ECPoint, r *big.Int) bool

VerifyR checks if the point in question is a valid commitment of r by generating a new point and comparing the two

func WriteBigInt 

func WriteBigInt(w io.Writer, b *big.Int) error

WriteBigInt write a big.Int to io.Writer w

func WriteECPoint 

func WriteECPoint(w io.Writer, p ECPoint) error

WriteECPoint write an ECPoint to io.Writer w

Types

type ABCProof 

type ABCProof struct {
	B         ECPoint  // commitment for b = 0 OR inv(v)
	C         ECPoint  // commitment for c = 0 OR 1 ONLY
	T1        ECPoint  // T1 = u1G + u2MTok
	T2        ECPoint  // T2 = u1B + u3H
	Challenge *big.Int // chal = HASH(G,H,CM,CMTok,B,C,T1,T2)

	CToken ECPoint
	// contains filtered or unexported fields
}

ABCProof is a proof that generates a proof that the relationship between three 

scalars a, b and c is ab = c

MAPPING[a, b, c] :: [v, inv(v), c]

Public: G, H, CM, B, C, CMTok where
- CM = vG + uaH // we do not know ua, only v
- B = inv(v)G + ubH //inv is multiplicative inverse, in the case of v = 0, inv(v) = 0
- C = (v * inv(v))G + ucH // c = v * inv(v)
- CMTok = uaPK = ua(skH) // ua is r from CM

Prover									Verifier
======                                  ======
generate in order:
- commitment of inv(v), B
- commitment of v * inv(v), C // either 0 or 1 ONLY
- Disjunctive proof of v = 0 or c = 1
select u1, u2, u3 at random
select ub, uc at random // ua was before proof
Compute:
- T1 = u1G + u2CMTok
- T2 = u1B + u3H
- chal = HASH(G,H,CM,CMTok,B,C,T1,T2)
Compute:
- j = u1 + v * chal
- k = u2 + inv(sk) * chal
- l = u3 + (uc - v * ub) * chal

disjuncAC, B, C, T1, T2, c, j, k, l ------->
       									disjuncAC ?= true
       									chal ?= HASH(G,H,CM,CMTok,B,C,T1,T2)
       									chal*CM + T1 ?= jG + kCMTok
       									chal*C + T2 ?= jB + lH˜

func NewABCProof 

func NewABCProof(zkpcp ZKPCurveParams, CM, CMTok ECPoint, value, sk *big.Int, option Side) (*ABCProof, error)

NewABCProof generates a proof that the relationship between three scalars a,b and c is ab = c, in commitments A, B and C respectively. Option Left is proving that A and C commit to zero and simulates that A, B and C commit to v, inv(v) and 1 respectively. Option Right is proving that A, B and C commit to v, inv(v) and 1 respectively and simulating that A and C commit to 0.

func NewABCProofFromBytes 

func NewABCProofFromBytes(b []byte) (*ABCProof, error)

NewABCProofFromBytes returns an ABCProof generated from the deserialization of byte slice b

func (*ABCProof) Bytes 

func (proof *ABCProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of ABCProof proof

func (*ABCProof) Verify 

func (aProof *ABCProof) Verify(zkpcp ZKPCurveParams, CM, CMTok ECPoint) (bool, error)

Verify checks if ABCProof aProof with appropriate commits CM and CMTok is correct

type ConsistencyProof 

type ConsistencyProof struct {
	T1        ECPoint
	T2        ECPoint
	Challenge *big.Int
	S1        *big.Int // s1 - but capitalized to allow access from outside of zksigma
	S2        *big.Int // s2 - but capitalized to allow access from outside of zksigma
}

ConsistencyProof is similar to EquivalenceProof except that we make some assumptions about the public info. Here we want to prove that the r used in CM and Y are the same. 

	Public:
 - generator points G and H,
 - PK (pubkey) = skH // sk = secret key
 - CM (commitment) = vG + rH
 - CMTok = rPK

 Prover									Verifier
 ======                                  ========
 selects v and r for commitments
 CM = vG + rH; CMTok = rPK				learns CM, CMTok
 selects random u1, u2
 T1 = u1G + u2H
 T2 = u2PK
 c = HASH(G, H, T1, T2, PK, CM, CMTok)
 s1 = u1 + c * v
 s2 = u2 + c * r

 T1, T2, c, s1, s2 ----------------->
                                         c ?= HASH(G, H, T1, T2, PK, CM, CMTok)
                                         s1G + s2H ?= T1 + cCM
                                         s2PK ?= T2 + cCMTok

func NewConsistencyProof 

func NewConsistencyProof(zkpcp ZKPCurveParams,
	CM, CMTok, PubKey ECPoint, value, randomness *big.Int) (*ConsistencyProof, error)

NewConsistencyProof generates a proof that the r used in CM(=xG+rH) and CMTok(=r(sk*H)) are the same.

func NewConsistencyProofFromBytes 

func NewConsistencyProofFromBytes(b []byte) (*ConsistencyProof, error)

NewConsistencyProofFromBytes returns a ConsistencyProof generated from the deserialization of byte slice b

func (*ConsistencyProof) Bytes 

func (proof *ConsistencyProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of ConsistencyProof proof

func (*ConsistencyProof) Verify 

func (conProof *ConsistencyProof) Verify(
	zkpcp ZKPCurveParams, CM, CMTok, PubKey ECPoint) (bool, error)

Verify checks if a ConsistencyProof conProof is valid

type DisjunctiveProof 

type DisjunctiveProof struct {
	T1 ECPoint
	T2 ECPoint
	C  *big.Int
	C1 *big.Int
	C2 *big.Int
	S1 *big.Int
	S2 *big.Int
}

DisjunctiveProof is a proof that you know either x or y but does not reveal which one you know 

 Public: generator points G and H, A, B

 Prover                              Verifier
 ======                              ========
 (proving x)
 knows x AND/OR y
	A = xG; B = yH or yG				learns A, B
 selects random u1, u2, u3
 T1 = u1G
 T2 = u2H + (-u3)yH
 c = HASH(T1, T2, G, A, B)
 deltaC = c - u3
 s = u1 + deltaC * x
 T1, T2, c, deltaC, u3, s, u2 -MAP-> T1, T2, c, c1, c2, s1, s2
                                     c ?= HASH(T1, T2, G, A, B)
                                     c ?= c1 + c2 // mod zkpcp.C.Params().N
                                     s1G ?= T1 + c1A
                                     s2G ?= T2 + c2A
 To prove y instead:

 Prover		 						Verifier
 ======                              ========
 T2, T1, c, u3, deltaC, u2, s -MAP-> T1, T2, c, c1, c2, s1, s2
										Same checks as above

Note: It should be indistinguishable for Verifier with T1, T2, c, c1, c2, s1, s2 to tell if we are proving x or y. The above arrows show how the variables used in the proof translate to T1, T2, etc.

More info: https://drive.google.com/file/d/0B_ndzgLH0bcvMjg3M1ROUWQwWTBCN0loQ055T212eV9JRU1v/view see section 4.2

func NewDisjunctiveProof 

func NewDisjunctiveProof(
	zkpcp ZKPCurveParams, Base1, Result1, Base2, Result2 ECPoint, x *big.Int, option Side) (*DisjunctiveProof, error)

NewDisjunctiveProof generates a disjunctive proof. Base1 and Base2 are our chosen base points. Result1 is Base1 multiplied by x or y, and Result2 is Base2 multiplied by x or y. x is the value to prove, if option is Left, we use Base1 and Result1 - if option is Right we use Base2 and Result2. The verifier will not learn what side is being proved and should not be able to tell.

func NewDisjunctiveProofFromBytes 

func NewDisjunctiveProofFromBytes(b []byte) (*DisjunctiveProof, error)

NewDisjunctiveProofFromBytes returns a DisjunctiveProof generated from the deserialization of byte slice b

func (*DisjunctiveProof) Bytes 

func (djProof *DisjunctiveProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of DisjunctiveProof proof

func (*DisjunctiveProof) Verify 

func (djProof *DisjunctiveProof) Verify(
	zkpcp ZKPCurveParams, Base1, Result1, Base2, Result2 ECPoint) (bool, error)

Verify checks if DisjunctiveProof djProof is valid for the given bases and results

type ECPoint 

type ECPoint struct {
	X, Y *big.Int
}
var Zero ECPoint // initialized in init()

Zero is a cached variable containing ECPoint{big.NewInt(0), big.NewInt(0)}

func CommitR 

func CommitR(zkpcp ZKPCurveParams, pk ECPoint, r *big.Int) ECPoint

CommitR uses the Public Key (pk) and a random number (r) to generate a commitment of r as an ECPoint

func KeyGen 

func KeyGen(curve elliptic.Curve, base ECPoint) (ECPoint, *big.Int)

func PedCommit 

func PedCommit(zkpcp ZKPCurveParams, value *big.Int) (ECPoint, *big.Int, error)

=============== PEDERSEN COMMITMENTS ================ PedCommit generates a pedersen commitment of value using the generators of zkpcp. It returns the randomness generated for the commitment.

func PedCommitR 

func PedCommitR(zkpcp ZKPCurveParams, value, randomValue *big.Int) ECPoint

PedCommitR generates a Pedersen commitment with a given random value

func ReadECPoint 

func ReadECPoint(r io.Reader) (ECPoint, error)

ReadECPoint reads an ECPoint from io.Reader r

func (ECPoint) Bytes 

func (p ECPoint) Bytes() []byte

func (ECPoint) Equal 

func (p ECPoint) Equal(p2 ECPoint) bool

Equal returns true if points p (self) and p2 (arg) are the same.

type EquivalenceProof 

type EquivalenceProof struct {
	UG          ECPoint  // uG is the scalar mult of u (random num) with base G
	UH          ECPoint  // uH is the scalar mult of u (random num) with base H
	Challenge   *big.Int // Challenge is hash sum of challenge commitment
	HiddenValue *big.Int // Hidden Value hides the discrete log x that we want to prove equivalence for
}

EquivalenceProof is an Equivalence Proof. A proof that both A and B both use the same scalar, x. 

 Public: generator points G and H

 Prover                              Verifier
 ======                              ========
 know x
	A = xG ; B = xH						learns A, B
 selects random u
 T1 = uG
 T2 = uH
 c = HASH(G, H, xG, xH, uG, uH)
 s = u + c * x

 T1, T2, s, c ---------------------->
                                     c ?= HASH(G, H, A, B, T1, T2)
                                     sG ?= T1 + cA
                                     sH ?= T2 + cB

func NewEquivalenceProof 

func NewEquivalenceProof(
	zkpcp ZKPCurveParams, Base1, Result1, Base2, Result2 ECPoint, x *big.Int) (*EquivalenceProof, error)

NewEquivalenceProof generates an equivalence proof that Result1 is the scalar multiple of base Base1, and Result2 is the scalar multiple of base Base2 and that both results are using the same x as discrete log.

func NewEquivalenceProofFromBytes 

func NewEquivalenceProofFromBytes(b []byte) (*EquivalenceProof, error)

NewEquivalenceProofFromBytes returns a EquivalenceProof generated from the deserialization of byte slice b

func (*EquivalenceProof) Bytes 

func (proof *EquivalenceProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of EquivalenceProof proof

func (*EquivalenceProof) Verify 

func (eqProof *EquivalenceProof) Verify(
	zkpcp ZKPCurveParams, Base1, Result1, Base2, Result2 ECPoint) (bool, error)

Verify checks if EquivalenceProof eqProof is a valid proof that Result1 is the scalar multiple of base Base1, and Result2 is the scalar multiple of base Base2. Both using the same x as discrete log.

type GSPFSProof 

type GSPFSProof struct {
	Base        ECPoint  // Base point
	RandCommit  ECPoint  // this is H = uG, where u is random value and G is a generator point
	HiddenValue *big.Int // s = x * c + u, here c is the challenge and x is what we want to prove knowledge of
	Challenge   *big.Int // challenge string hash sum, only use for sanity checks
}

GSPFSProof is proof of knowledge of x in commitment A(=xG) GSPFS is Generalized Schnorr Proofs with Fiat-Shamir transform. 

 Public: generator points G and H

 Prover                              Verifier
 ======                              ========
 know x
	A = xG								learns A
 selects random u
 T1 = uG
 c = HASH(G, xG, uG)
 s = u + c * x

 T1, s, c -------------------------->
                                     c ?= HASH(G, A, T1)
                                     sG ?= T1 + cA

func NewGSPFSProof 

func NewGSPFSProof(zkpcp ZKPCurveParams, A ECPoint, x *big.Int) (*GSPFSProof, error)

NewGSPFSProof generates a Schnorr proof for the value x using the first ZKCurve base point. It checks if the passed A is indeed value x multiplied by the generator point.

func NewGSPFSProofBase 

func NewGSPFSProofBase(zkpcp ZKPCurveParams, base, A ECPoint, x *big.Int) (*GSPFSProof, error)

NewGSPFSProofBase is the same as NewGSPFSProof, except it allows you to specify your own base point in parameter base, instead of using the first base point from zkpcp.

func NewGSPFSProofFromBytes 

func NewGSPFSProofFromBytes(b []byte) (*GSPFSProof, error)

NewGSPFSProofFromBytes returns a GSPFSProof generated from the deserialization of byte slice b

func (*GSPFSProof) Bytes 

func (proof *GSPFSProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of GSPFSProof proof

func (*GSPFSProof) Verify 

func (proof *GSPFSProof) Verify(zkpcp ZKPCurveParams, A ECPoint) (bool, error)

Verify (GSPFSVerify) checks if GSPFSProof proof is a valid proof for commitment A

type InequalityProof 

type InequalityProof ABCProof

func NewInequalityProof 

func NewInequalityProof(zkpcp ZKPCurveParams, A, B, CMTokA, CMTokB ECPoint, a, b, sk *big.Int) (*InequalityProof, error)

InequalityProve generates a proof to show that two commitments, A and B, are not equal Given two commitments A and B that we know the values for - a and b respectively - we can prove that a != b without needed any new commitments, just generate a proof There is no Inequality verify since this generates an ABCProof, so just use ABCVerify

func (*InequalityProof) Verify 

func (ieProof *InequalityProof) Verify(zkpcp ZKPCurveParams, CM, CMTok ECPoint) (bool, error)

Verify checks if InequalityProof ieProof with appropriate commits CM and CMTok is correct

type RangeProof 

type RangeProof struct {
	ProofAggregate ECPoint
	ProofE         *big.Int
	ProofTuples    []rangeProofTuple
}

RangeProof Implementation details from: https://blockstream.com/bitcoin17-final41.pdf NOTE: To be consistent with our use of Pedersen commitments, we switch the G and H values from the above description

Takes in a value and randomness used in a commitment, and produces a proof that our value is in range 2^64. Range proofs uses ring signatures from Chameleon hashes and Pedersen Commitments to do commitments on the bitwise decomposition of our value.

func NewRangeProof 

func NewRangeProof(zkpcp ZKPCurveParams, value *big.Int) (*RangeProof, *big.Int, error)

NewRangeProof generates a range proof for the given value

func NewRangeProofFromBytes 

func NewRangeProofFromBytes(b []byte) (*RangeProof, error)

NewRangeProofFromBytes returns a RangeProof generated from the deserialization of byte slice b

func (*RangeProof) Bytes 

func (proof *RangeProof) Bytes() []byte

Bytes returns a byte slice with a serialized representation of RangeProof proof

func (*RangeProof) Verify 

func (proof *RangeProof) Verify(zkpcp ZKPCurveParams, comm ECPoint) (bool, error)

type Side 

type Side int

Side is an enum to pick what side of the proof you want to generate 

const (
	// Left generates the left side of a proof
	Left Side = 0
	// Right generates the right side of a proof
	Right Side = 1
)

type ZKPCurveParams 

type ZKPCurveParams struct {
	C       elliptic.Curve // Curve
	G       ECPoint        // generator 1
	H       ECPoint        // generator 2
	HPoints []ECPoint      // HPoints should be initialized with a pre-populated array of the ZKCurve's generator point H multiplied by 2^x where x = [0...63]
}

ZKPCurveParams is zero knowledge proof curve and params struct, only one instance should be used 

var TestCurve ZKPCurveParams

TestCurve is a global cache for the curve and two generator points used in the test cases. It is equal to ZKLedger's curve - but for abstraction the actual curve parameters are passed into the proof functions. We just test with the same params that ZKLedger uses.

func (ZKPCurveParams) Add 

func (zkpcp ZKPCurveParams) Add(p, p2 ECPoint) ECPoint

Add adds points p and p2 and returns the resulting point

func (ZKPCurveParams) Mult 

func (zkpcp ZKPCurveParams) Mult(p ECPoint, s *big.Int) ECPoint

Mult multiplies point p by scalar s and returns the resulting point

func (ZKPCurveParams) Neg 

func (zkpcp ZKPCurveParams) Neg(p ECPoint) ECPoint

Neg returns the additive inverse of point p

func (ZKPCurveParams) Sub 

func (zkpcp ZKPCurveParams) Sub(p, p2 ECPoint) ECPoint

Source Files

View all Source files

Directories

Path Synopsis
Package btcec implements support for the elliptic curves needed for bitcoin.
 Package btcec implements support for the elliptic curves needed for bitcoin.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.