forked from Consensys/gnark
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ecdsa.go
64 lines (56 loc) · 2.05 KB
/
ecdsa.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
Package ecdsa implements ECDSA signature verification over any elliptic curve.
The package depends on the [emulated/sw_emulated] package for elliptic curve group
operations using non-native arithmetic. Thus we can verify ECDSA signatures over
any curve. The cost for a single secp256k1 signature verification is
approximately 4M constraints in R1CS and 10M constraints in PLONKish.
See [ECDSA] for the signature verification algorithm.
[ECDSA]:
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
*/
package ecdsa
import (
"github.com/airchains-network/gnark/frontend"
"github.com/airchains-network/gnark/std/algebra/emulated/sw_emulated"
"github.com/airchains-network/gnark/std/math/emulated"
)
// Signature represents the signature for some message.
type Signature[Scalar emulated.FieldParams] struct {
R, S emulated.Element[Scalar]
}
// PublicKey represents the public key to verify the signature for.
type PublicKey[Base, Scalar emulated.FieldParams] sw_emulated.AffinePoint[Base]
// Verify asserts that the signature sig verifies for the message msg and public
// key pk. The curve parameters params define the elliptic curve.
//
// We assume that the message msg is already hashed to the scalar field.
func (pk PublicKey[T, S]) Verify(api frontend.API, params sw_emulated.CurveParams, msg *emulated.Element[S], sig *Signature[S]) {
cr, err := sw_emulated.New[T, S](api, params)
if err != nil {
// TODO: softer handling.
panic(err)
}
scalarApi, err := emulated.NewField[S](api)
if err != nil {
panic(err)
}
baseApi, err := emulated.NewField[T](api)
if err != nil {
panic(err)
}
pkpt := sw_emulated.AffinePoint[T](pk)
sInv := scalarApi.Inverse(&sig.S)
msInv := scalarApi.MulMod(msg, sInv)
rsInv := scalarApi.MulMod(&sig.R, sInv)
// q = [rsInv]pkpt + [msInv]g
q := cr.JointScalarMulBase(&pkpt, rsInv, msInv)
qx := baseApi.Reduce(&q.X)
qxBits := baseApi.ToBits(qx)
rbits := scalarApi.ToBits(&sig.R)
if len(rbits) != len(qxBits) {
panic("non-equal lengths")
}
for i := range rbits {
api.AssertIsEqual(rbits[i], qxBits[i])
}
}