Back to godoc.org

Package proof

v0.0.0 (ffb7191)
Latest Go to latest
Published: Jan 25, 2019 | License: | Module:

Overview ¶

Package proof implements generic support for Sigma-protocols and discrete logarithm proofs in the Camenisch/Stadler framework. For the cryptographic foundations of this framework see "Proof Systems for General Statements about Discrete Logarithms" at ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf.

Example (And1)

This code creates an And predicate indicating that the prover knows two different secrets x and y, such that point X is equal to x*B and point Y is equal to y*B. This predicate might be used to prove knowledge of the private keys corresponding to two public keys X and Y, for example.

Code:

```pred := And(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println(pred.String())
```
```X=x*B && Y=y*B
```
Example (And2)

This code creates an And predicate indicating that the prover knows a single secret value x, such that point X1 is equal to x*B1 and point X2 is equal to x*B2. Thus, the prover not only proves knowledge of the discrete logarithm of X1 with respect to B1 and of X2 with respect to B2, but also proves that those two discrete logarithms are equal.

Code:

```pred := And(Rep("X1", "x", "B1"), Rep("X2", "x", "B2"))
fmt.Println(pred.String())
```
```X1=x*B1 && X2=x*B2
```
Example (HashProve1)

This example shows how to build classic ElGamal-style digital signatures using the Camenisch/Stadler proof framework and HashProver.

Code:

```rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base()

x := suite.Scalar().Pick(suite.RandomStream())
X := suite.Point().Mul(x, nil)

M := "Hello World!"
rep := Rep("X", "x", "B")
sec := map[string]kyber.Scalar{"x": x}
pub := map[string]kyber.Point{"B": B, "X": X}
prover := rep.Prover(suite, sec, pub, nil)
proof, _ := HashProve(suite, M, prover)
fmt.Print("Signature:\n" + hex.Dump(proof))

verifier := rep.Verifier(suite, pub)
err := HashVerify(suite, M, verifier, proof)
if err != nil {
fmt.Println("signature failed to verify: ", err)
return
}
fmt.Println("Signature verified against correct message M.")

verifier = rep.Verifier(suite, pub)
err = HashVerify(suite, BAD, verifier, proof)
fmt.Println("Signature verify against wrong message: " + err.Error())
```
```Signature:
00000000  e9 a2 da f4 9d 7c e2 25  35 be 0a 15 78 9c ea ca  |.....|.%5...x...|
00000010  a7 1e 6e d6 26 c3 40 ed  0d 3d 71 d4 a9 ef 55 3b  |..n.&.@..=q...U;|
00000020  64 76 55 7b 3c 63 20 d8  4b 29 3a 1c 7f 44 59 ad  |dvU{<c .K):..DY.|
00000030  ff 5d c1 ff 06 1d 97 0c  59 06 3c 4b aa 7b 7c 0c  |.]......Y.<K.{|.|
Signature verified against correct message M.
Signature verify against wrong message: invalid proof: commit mismatch
```
Example (HashProve2)

This example implements Linkable Ring Signatures (LRS) generically using the Camenisch/Stadler proof framework and HashProver.

A ring signature proves that the signer owns one of a list of public keys, without revealing anything about which public key the signer actually owns. A linkable ring signature (LRS) is the same but includes a linkage tag, which the signer proves to correspond 1-to-1 with the signer's key, but whose relationship to the private key remains secret from anyone who does not hold the private key. A key-holder who signs multiple messages in the same public "linkage scope" will be forced to use the same linkage tag in each such signature, enabling others to tell whether two signatures in a given scope were produced by the same or different signers.

This scheme is conceptually similar to that of Liu/Wei/Wong in "Linkable and Anonymous Signature for Ad Hoc Groups". This example implementation is less space-efficient, however, because it uses the generic HashProver for Fiat-Shamir noninteractivity instead of Liu/Wei/Wong's customized hash-ring structure.

Code:

```rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base()

X := make([]kyber.Point, 3)
for i := range X {
X[i] = suite.Point().Pick(suite.RandomStream())
}

mine := 2
x := suite.Scalar().Pick(suite.RandomStream())
X[mine] = suite.Point().Mul(x, nil)

sec := map[string]kyber.Scalar{"x": x}
preds := make([]Predicate, len(X))
for i := range X {
name := fmt.Sprintf("X[%d]", i)
pub[name] = X[i]

preds[i] = And(Rep(name, "x", "B"), Rep("T", "x", "BT"))
}
pred := Or(preds...)

choice := make(map[Predicate]int)
choice[pred] = mine

M := "Hello World!"
prover := pred.Prover(suite, sec, pub, choice)
proof, _ := HashProve(suite, M, prover)

verifier := pred.Verifier(suite, pub)
err := HashVerify(suite, M, verifier, proof)
if err != nil {
fmt.Println("signature failed to verify: ", err)
return
}
```
```Linkable Ring Signature Predicate:
(X[0]=x*B && T=x*BT) || (X[1]=x*B && T=x*BT) || (X[2]=x*B && T=x*BT)
00000000  d6 73 58 df 19 52 fc a7  70 2b 42 00 83 03 bd 5f  |.sX..R..p+B...._|
00000010  4d 86 4b 8d db 3d 76 17  00 17 2c b9 a3 6b 54 57  |M.K..=v...,..kTW|
00000020  e1 fd c0 d4 00 9b ea 5d  85 2b f1 83 41 80 ec 83  |.......].+..A...|
00000030  ac b2 f4 0c e4 01 35 61  34 ef 94 34 0b 77 44 3e  |......5a4..4.wD>|
00000040  e3 bd 92 b2 f8 f5 85 97  c4 dd 39 f7 a0 b6 ef b1  |..........9.....|
00000050  65 c6 53 80 e4 78 07 52  62 a5 0b a5 f1 0b 33 2b  |e.S..x.Rb.....3+|
00000060  c8 f5 43 9b 1c bf c2 1a  4a 5b ea b0 e9 18 d1 db  |..C.....J[......|
00000070  a3 57 eb e0 5b d4 99 0e  af f2 10 d4 29 a9 0e 43  |.W..[.......)..C|
00000080  fd 20 a1 42 01 ef 68 a0  43 64 70 f4 f9 09 0f 77  |. .B..h.Cdp....w|
00000090  b3 b0 82 0a 31 8a 66 41  a8 d0 f4 5f 1e da 6e 63  |....1.fA..._..nc|
000000a0  a0 46 74 75 86 6f 3e 85  52 f0 74 6c 74 3b 00 1b  |.Ftu.o>.R.tlt;..|
000000b0  b2 4b 93 95 33 1d 9e 6a  96 43 e5 e2 30 46 6e e5  |.K..3..j.C..0Fn.|
000000c0  2b e0 be 8d 56 55 1a d1  6e 11 21 fc 20 3e 0f 5f  |+...VU..n.!. >._|
000000d0  4d 97 a9 bf 1a 28 27 6d  3b 71 04 e1 c0 86 96 08  |M....('m;q......|
000000e0  8d 0e c0 14 e3 eb 8b e9  16 40 29 60 ab bd e6 1a  |.........@)`....|
000000f0  68 54 5e 29 c8 85 05 bc  4a 27 83 d9 32 cc 74 0f  |hT^)....J'..2.t.|
00000100  5e 16 30 25 e2 d6 35 2a  d4 3e b5 07 1f d4 0a eb  |^.0%..5*.>......|
00000110  5d ef 3b 84 35 39 90 0c  3a 02 bb ee c7 9a e7 09  |].;.59..:.......|
00000120  d1 cc 1e e1 f4 3b 88 52  e5 99 ed 50 d7 66 b5 76  |.....;.R...P.f.v|
00000130  59 6c c1 66 98 07 e5 73  e7 b8 fe 48 43 a0 74 09  |Yl.f...s...HC.t.|
00000140  84 9a 7b ec 21 aa ff c7  fc 79 c6 8f f4 23 82 e7  |..{.!....y...#..|
00000150  d3 71 69 20 d6 94 27 ef  11 0b 4c a5 79 54 1f 09  |.qi ..'...L.yT..|
00000160  6b ec 50 c2 1f 98 38 ea  a7 02 da ca aa 1b 6b 39  |k.P...8.......k9|
00000170  70 b8 35 6c fe 03 1f b0  08 42 e0 5d b2 5e 40 04  |p.5l.....B.].^@.|
```
Example (Or1)

This code creates an Or predicate indicating that the prover either knows a secret x such that X=x*B, or the prover knows a secret y such that Y=y*B. This predicate in essence proves knowledge of the private key for one of two public keys X or Y, without revealing which key the prover owns.

Code:

```pred := Or(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println(pred.String())
```
```X=x*B || Y=y*B
```
Example (Or2)

This code shows how to create and verify Or-predicate proofs, such as the one above. In this case, we know a secret x such that X=x*B, but we don't know a secret y such that Y=y*B, because we simply pick Y as a random point instead of generating it by scalar multiplication. (And if the group is cryptographically secure we won't find be able to find such a y.)

Code:

```pred := Or(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println("Predicate: " + pred.String())

rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base()

x := suite.Scalar().Pick(rand)
X := suite.Point().Mul(x, nil)
Y := suite.Point().Pick(rand)

choice := make(map[Predicate]int)
choice[pred] = 0

sval := map[string]kyber.Scalar{"x": x}
pval := map[string]kyber.Point{"B": B, "X": X, "Y": Y}
prover := pred.Prover(suite, sval, pval, choice)
proof, _ := HashProve(suite, "TEST", prover)
fmt.Print("Proof:\n" + hex.Dump(proof))

verifier := pred.Verifier(suite, pval)
err := HashVerify(suite, "TEST", verifier, proof)
if err != nil {
fmt.Println("Proof failed to verify: " + err.Error())
}
fmt.Println("Proof verified.")
```
```Predicate: X=x*B || Y=y*B
Proof:
00000000  44 bb 0f bb 2b 06 29 a6  73 59 0f c1 5a ca de 36  |D...+.).sY..Z..6|
00000010  4c c8 15 ed b1 eb 50 d3  d9 d2 9b 31 6c d3 0f 6b  |L.....P....1l..k|
00000020  a2 a9 bc d2 8c 6d d0 5e  9a 8e d1 8e 04 fb 88 af  |.....m.^........|
00000030  fb 90 8a 2a 71 ac 34 08  f9 bc 07 78 08 44 40 07  |...*q.4....x.D@.|
00000040  ab 1f 36 7e 7b db 50 7d  49 38 34 75 69 07 67 4b  |..6~{.P}I84ui.gK|
00000050  55 cb 28 f2 50 ad d1 4b  24 d2 d1 44 fe 44 b0 0e  |U.(.P..K\$..D.D..|
00000060  00 e8 d3 8b 37 76 4f 47  d1 4a 93 0c cd df 20 08  |....7vOG.J.... .|
00000070  fc 0f ad f9 01 6c 30 c0  02 d4 fa 1b 1f 1c fa 04  |.....l0.........|
00000080  6d 2a a7 d8 8e 67 72 87  51 0e 16 72 51 87 99 83  |m*...gr.Q..rQ...|
00000090  2e c9 4e a1 ca 20 7d 64  33 04 f5 66 9b d3 74 03  |..N.. }d3..f..t.|
000000a0  2b e0 be 8d 56 55 1a d1  6e 11 21 fc 20 3e 0f 5f  |+...VU..n.!. >._|
000000b0  4d 97 a9 bf 1a 28 27 6d  3b 71 04 e1 c0 86 96 08  |M....('m;q......|
Proof verified.
```
Example (Rep1)

This code creates a simple discrete logarithm knowledge proof. In particular, that the prover knows a secret x that is the elliptic curve discrete logarithm of a point X with respect to some base B: i.e., X=x*B. If we take X as a public key and x as its corresponding private key, then this constitutes a "proof of ownership" of the public key X.

Code:

```pred := Rep("X", "x", "B")
fmt.Println(pred.String())
```
```X=x*B
```
Example (Rep2)

This example shows how to generate and verify noninteractive proofs of the statement in the example above, i.e., a proof of ownership of public key X.

Code:

```pred := Rep("X", "x", "B")
fmt.Println(pred.String())

rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base()

x := suite.Scalar().Pick(rand)
X := suite.Point().Mul(x, nil)

sval := map[string]kyber.Scalar{"x": x}
pval := map[string]kyber.Point{"B": B, "X": X}
prover := pred.Prover(suite, sval, pval, nil)
proof, _ := HashProve(suite, "TEST", prover)
fmt.Print("Proof:\n" + hex.Dump(proof))

verifier := pred.Verifier(suite, pval)
err := HashVerify(suite, "TEST", verifier, proof)
if err != nil {
fmt.Println("Proof failed to verify: ", err)
return
}
fmt.Println("Proof verified.")
```
```X=x*B
Proof:
00000000  e9 a2 da f4 9d 7c e2 25  35 be 0a 15 78 9c ea ca  |.....|.%5...x...|
00000010  a7 1e 6e d6 26 c3 40 ed  0d 3d 71 d4 a9 ef 55 3b  |..n.&.@..=q...U;|
00000020  c1 84 20 a6 b7 79 86 9c  f8 dd 09 82 1e 48 a9 00  |.. ..y.......H..|
00000030  3e f3 68 66 3f a0 58 f9  88 df b4 35 1b 2f 72 0d  |>.hf?.X....5./r.|
Proof verified.
```
Example (Rep3)

This code creates a predicate stating that the prover knows a representation of point X with respect to two different bases B1 and B2. This means the prover knows two secrets x1 and x2 such that X=x1*B1+x2*B2.

Point X might constitute a Pedersen commitment, for example, where x1 is the value being committed to and x2 is a random blinding factor. Assuming the discrete logarithm problem is hard in the relevant group and the logarithmic relationship between bases B1 and B2 is unknown - which we would be true if B1 and B2 are chosen at random, for example - then a prover who has committed to point P will later be unable to "open" the commitment using anything other than secrets x1 and x2. The prover can also prove that one of the secrets (say x1) is equal to a secret used in the representation of some other point, while leaving the other secret (x2) unconstrained.

If the prover does know the relationship between B1 and B2, however, then X does not serve as a useful commitment: the prover can trivially compute the x1 corresponding to an arbitrary x2.

Code:

```pred := Rep("X", "x1", "B1", "x2", "B2")
fmt.Println(pred.String())
```
```X=x1*B1+x2*B2
```

Index ¶

func HashProve¶

`func HashProve(suite Suite, protocolName string, prover Prover) ([]byte, error)`

HashProve runs a given Sigma-protocol prover with a ProverContext that produces a non-interactive proof via the Fiat-Shamir heuristic. Returns a byte-slice containing the noninteractive proof on success, or an error in the case of failure.

The optional protocolName is fed into the hash function used in the proof, so that a proof generated for a particular protocolName will verify successfully only if the verifier uses the same protocolName.

The caller must provide a source of random entropy for the proof; this can be random.New() to use fresh random bits, or a pseudorandom stream based on a secret seed to create deterministically reproducible proofs.

func HashVerify¶

```func HashVerify(suite Suite, protocolName string,
verifier Verifier, proof []byte) error```

HashVerify computes a hash-based noninteractive proof generated with HashProve. The suite and protocolName must be the same as those given to HashProve. Returns nil if the proof checks out, or an error on any failure.

type Context¶

```type Context interface {

// A follower calls Step to provide its message for the next step,
// and wait for the leader to collect and distribute all messages.
// Returns the list of collected messages, one per participant.
// The returned message slice is positionally consistent across steps:
// each index consistently represents the same participant every step.
// One returned message will be the same slice as the one passed in,
// representing the calling participant's own slot.
Step(msg []byte) ([][]byte, error)

// Get a source of private cryptographic randomness.
Random() kyber.XOF
}```

Context represents a kyber.context for running a clique protocol. A clique protocol is initiated by a leader but incorporates a variable number of followers, all of whom operate in lock-step under the leader's direction. At each step, each follower produces one message; the leader aggregates all the followers' messages for that step and returns the vector of collected messages to each follower. Followers can drop out or be absent at any step, in which case they are seen as contributing an empty message in that step.

type Predicate¶

```type Predicate interface {

// Create a Prover proving the statement this Predicate represents.
Prover(suite Suite, secrets map[string]kyber.Scalar,
points map[string]kyber.Point, choice map[Predicate]int) Prover

// Create a Verifier for the statement this Predicate represents.
Verifier(suite Suite, points map[string]kyber.Point) Verifier

// Produce a human-readable string representation of the predicate.
String() string
// contains filtered or unexported methods
}```

A Predicate is a composable logic expression in a knowledge proof system, representing a "knowledge specification set" in Camenisch/Stadler terminology. Atomic predicates in this system are statements of the form P=x1*B1+...+xn+Bn, indicating the prover knows secrets x1,...,xn that make the statement true, where P and B1,...,Bn are public points known to the verifier. These atomic Rep (representation) predicates may be combined with logical And and Or combinators to form composite statements. Predicate objects, once created, are immutable and safe to share or reuse for any number of proofs and verifications.

After constructing a Predicate using the Rep, And, and Or functions below, the caller invokes Prover() to create a Sigma-protocol prover. Prover() requires maps defining the values of both the Scalar variables and the public Point variables that the Predicate refers to. If the statement contains logical Or operators, the caller must also pass a map containing branch choices for each Or predicate in the "proof-obligated path" down through the Or predicates. See the examples provded for the Or function for more details.

Similarly, the caller may invoke Verifier() to create a Sigma-protocol verifier for the predicate. The caller must pass a map defining the values of the public Point variables that the proof refers to. The verifier need not be provided any secrets or branch choices, of course. (If the verifier needed those then they wouldn't be secret, would they?)

Currently we require that all Or operators be above all And operators in the expression - i.e., Or-of-And combinations are allowed, but no And-of-Or predicates. We could rewrite expressions into this form as Camenisch/Stadler suggest, but that could run a risk of unexpected exponential blowup in the worst case. We could avoid this risk by not rewriting the expression tree, but instead generating Pedersen commits for variables that need to "cross" from one OR-domain to another non-mutually-exclusive one. For now we simply require expressions to be in the appropriate form.

func And¶

`func And(sub ...Predicate) Predicate`

And predicate states that all of the constituent sub-predicates are true. And predicates may contain Rep predicates and/or other And predicates.

func Or¶

`func Or(sub ...Predicate) Predicate`

Or predicate states that the prover knows at least one of the sub-predicates to be true, but the proof does not reveal any information about which.

func Rep¶

`func Rep(P string, SB ...string) Predicate`

Rep creates a predicate stating that the prover knows a representation of a point P with respect to one or more secrets and base point pairs.

In its simplest usage, Rep indicates that the prover knows a secret x that is the (elliptic curve) discrete logarithm of a public point P with respect to a well-known base point B:

```Rep(P,x,B)
```

Rep can take any number of (Scalar,Base) variable name pairs, however. A Rep statement of the form Rep(P,x1,B1,...,xn,Bn) indicates that the prover knows secrets x1,...,xn such that point P is the sum x1*B1+...+xn*Bn.

type Protocol¶

`type Protocol func(ctx Context) []error`

Protocol represents the role of a participant in a clique protocol. A participant is represented as a higher-order function taking a StarContext, which invokes the StarContext's methods to send and receive messages, and finally returns once the protocol has concluded for all participants. Returns a slice of success/error indicators, one for each participant.

func DeniableProver¶

```func DeniableProver(suite Suite, self int, prover Prover,
verifiers []Verifier) Protocol```

DeniableProver is a Protocol implementing an interactive Sigma-protocol to prove a particular statement to the other participants. Optionally the Protocol participant can also verify the Sigma-protocol proofs of any or all of the other participants. Different participants may produce different proofs of varying sizes, and may even consist of different numbers of steps.

type Prover¶

`type Prover func(ctx ProverContext) error`

Prover represents the prover role in an arbitrary Sigma-protocol. A prover is simply a higher-order function that takes a ProverContext, runs the protocol while making calls to the ProverContext methods as needed, and returns nil on success or an error once the protocol run concludes. The resulting proof is embodied in the interactions with the ProverContext, but HashProve() may be used to encode the proof into a non-interactive proof using a hash function via the Fiat-Shamir heuristic.

type ProverContext¶

```type ProverContext interface {
Put(message interface{}) error        // Send message to verifier
PubRand(message ...interface{}) error // Get public randomness
PriRand(message ...interface{}) error // Get private randomness
}```

ProverContext represents the kyber.environment required by the prover in a Sigma protocol.

In a basic 3-step Sigma protocol such as a standard digital signature, the prover first calls Put() one or more times to send commitment information to the verifier, then calls PubRand() to obtain a public random challenge from the verifier, and finally makes further calls to Put() to respond to the challenge.

The prover may also call PriRand() at any time to obtain any private randomness needed in the proof. The prover should obtain secret randomness only from this source, so that the prover may be run deterministically if desired.

More sophisticated Sigma protocols requiring more than 3 steps, such as the Neff shuffle, may also use this interface; in this case the prover simply calls PubRand() multiple times.

type Suite¶

```type Suite interface {
kyber.Group
kyber.HashFactory
kyber.Encoding
kyber.XOFFactory
kyber.Random
}```

Suite defines the functionalities needed for this package to operate correctly. It provides a general abstraction to easily change the underlying implementations.

type Verifier¶

`type Verifier func(ctx VerifierContext) error`

Verifier represents the verifier role in an arbitrary Sigma-protocol. A verifier is a higher-order function that takes a VerifierContext, runs the protocol while making calls to VerifierContext methods as needed, and returns nil on success or an error once the protocol run concludes.

type VerifierContext¶

```type VerifierContext interface {
Get(message interface{}) error        // Receive message from prover
PubRand(message ...interface{}) error // Get public randomness
}```

VerifierContext represents the kyber.environment required by the verifier in a Sigma protocol.

The verifier calls Get() to obtain the prover's message data, interspersed with calls to PubRand() to obtain challenge data. Note that the challenge itself comes from the VerifierContext, not from the verifier itself as in the traditional Sigma-protocol model. By separating challenge production from proof verification logic, we obtain the flexibility to use a single Verifier function in both non-interactive proofs (e.g., via HashProve) and in interactive proofs (e.g., via DeniableProver).

Documentation was rendered with GOOS=linux and GOARCH=amd64.