1	import Base
2	import ../sha/sha256.bend as SHA
3	import ./limbs.bend as L
4	import ./field.bend as F
5	import ./scalar.bend as S
6	import ./point.bend as P
7	import ./bytes.bend as B
8	
9	# BIP-340 Schnorr signatures over secp256k1: x-only public keys (the point
10	# with even y), tagged SHA-256 hashes, the default signing algorithm (with
11	# its final verification) and verification. Messages may have any length
12	# (BIP-340 as revised in 2022). The contract is
13	# spec/crypto/secp256k1/schnorr.bend.
14	
15	def cat(xs: List<&2, U32>, ys: List<&2, U32>) -> List<&2, U32>:
16	  List.append(&2, U32, xs, ys)
17	
18	# "BIP0340/aux", "BIP0340/nonce", "BIP0340/challenge" in ASCII
19	def tag_prefix(rest: List<&2, U32>) -> List<&2, U32>:
20	  66 <> 73 <> 80 <> 48 <> 51 <> 52 <> 48 <> 47 <> rest
21	
22	def tag_aux() -> List<&2, U32>:
23	  tag_prefix([97, 117, 120])
24	
25	def tag_nonce() -> List<&2, U32>:
26	  tag_prefix([110, 111, 110, 99, 101])
27	
28	def tag_challenge() -> List<&2, U32>:
29	  tag_prefix([99, 104, 97, 108, 108, 101, 110, 103, 101])
30	
31	# hash_tag(x) = SHA256(SHA256(tag) || SHA256(tag) || x)
32	def tagged_h(+th: List<&2, U32>, x: List<&2, U32>) -> List<&2, U32>:
33	  SHA.sha256_bytes(cat(th, cat(th, x)))
34	
35	def tagged(tag: List<&2, U32>, x: List<&2, U32>) -> List<&2, U32>:
36	  tagged_h(SHA.sha256_bytes(tag), x)
37	
38	def xor_bytes(xs: List<&2, U32>, ys: List<&2, U32>) -> List<&2, U32>:
39	  match xs ys:
40	    case x <> xt y <> yt: U32.xor(x, y) <> xor_bytes(xt, yt)
41	    case _ _: Nil{}
42	
43	def is_odd(+y: List<&2, Nat>) -> Nat:
44	  F.parity(y)
45	
46	def verify_aff(+r: List<&2, Nat>, inf: Bool, a: P.Affine) -> Bool:
47	  match a:
48	    case P.Affine{x, +y}: Bool.and(Bool.not(inf), Bool.and(Nat.is_eq(is_odd(y), 0n), F.eq(x, r)))
49	
50	# ---- verification ----
51	
52	# R = [s] G - [e] P must be finite, with even y and x(R) = r
53	def verify_r(+r: List<&2, Nat>, +rr: P.Point) -> Bool:
54	  verify_aff(r, P.is_inf(rr), P.to_affine(rr))
55	
56	def verify_ok(+r: List<&2, Nat>, +s: List<&2, Nat>, +e: List<&2, Nat>, +pp: P.Point, ok: Bool) -> Bool:
57	  match ok:
58	    case True{}: verify_r(r, P.add(P.mul(s, P.g()), P.mul(S.neg(e), pp)))
59	    case False{}: False{}
60	
61	def verify_p(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>, mp: Maybe<&2, P.Point>) -> Bool:
62	  match mp:
63	    case None{}: False{}
64	    case Some{+pp}:
65	      +rb = B.prefix(32n, sig)
66	      +r = B.of_be(rb)
67	      +s = B.of_be(B.suffix(32n, sig))
68	      +e = S.reduce(B.of_be(tagged(tag_challenge(), cat(rb, cat(pk, m)))))
69	      verify_ok(r, s, e, pp, Bool.and(F.lt_p(r), S.lt_n(s)))
70	
71	def lift_if(+x: List<&2, Nat>, ok: Bool) -> Maybe<&2, P.Point>:
72	  match ok:
73	    case True{}: P.decompress(x, 0n)
74	    case False{}: None{}
75	
76	# lift_x: the point with x-coordinate x and even y, if any
77	def lift_x(+x: List<&2, Nat>) -> Maybe<&2, P.Point>:
78	  lift_if(x, F.lt_p(x))
79	
80	def verify_len(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>, ok: Bool) -> Bool:
81	  match ok:
82	    case True{}: verify_p(pk, m, sig, lift_x(B.of_be(pk)))
83	    case False{}: False{}
84	
85	# BIP-340 Verify(pk, m, sig) for a 32-byte x-only key and a 64-byte signature
86	def verify(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>) -> Bool:
87	  verify_len(pk, m, sig, Bool.and(B.has_len(32n, pk), B.has_len(64n, sig)))
88	
89	# ---- signing ----
90	
91	# the secret key d', when 1 <= d' < n
92	def secret_if(+d: List<&2, Nat>, ok: Bool) -> Maybe<&2, List<&2, Nat>>:
93	  match ok:
94	    case True{}: Some{d}
95	    case False{}: None{}
96	
97	def secret(+sk: List<&2, U32>) -> Maybe<&2, List<&2, Nat>>:
98	  +d = B.of_be(sk)
99	  secret_if(d, Bool.and(B.has_len(32n, sk), Bool.and(Bool.not(S.is_zero(d)), S.lt_n(d))))
100	
101	def pubkey_aff(a: P.Affine) -> List<&2, U32>:
102	  match a:
103	    case P.Affine{x, y}: B.to_be(x)
104	
105	def pubkey_d(m: Maybe<&2, List<&2, Nat>>) -> Maybe<&2, List<&2, U32>>:
106	  match m:
107	    case None{}: None{}
108	    case Some{d}: Some{pubkey_aff(P.to_affine(P.mul(d, P.g())))}
109	
110	# PubKey(sk) = bytes(d' G), the 32-byte x-only public key
111	def pubkey(+sk: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
112	  pubkey_d(secret(sk))
113	
114	# sig = bytes(R) || bytes((k + e d) mod n), then Verify(bytes(P), m, sig)
115	def sign_ok(+sig: List<&2, U32>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
116	  match ok:
117	    case True{}: Some{sig}
118	    case False{}: None{}
119	
120	def sign_fin(+pb: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
121	  sign_ok(sig, verify(pb, m, sig))
122	
123	def sign_k(+d: List<&2, Nat>, +pb: List<&2, U32>, +m: List<&2, U32>, +k0: List<&2, Nat>, ra: P.Affine) -> Maybe<&2, List<&2, U32>>:
124	  match ra:
125	    case P.Affine{rx, +ry}:
126	      +k = S.select(is_odd(ry), S.neg(k0), k0)
127	      +rb = B.to_be(rx)
128	      +e = S.reduce(B.of_be(tagged(tag_challenge(), cat(rb, cat(pb, m)))))
129	      sign_fin(pb, m, cat(rb, B.to_be(S.add(k, S.mul(e, d)))))
130	
131	def sign_nz(+d: List<&2, Nat>, +pb: List<&2, U32>, +m: List<&2, U32>, +k0: List<&2, Nat>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
132	  match ok:
133	    case True{}: sign_k(d, pb, m, k0, P.to_affine(P.mul(k0, P.g())))
134	    case False{}: None{}
135	
136	def sign_p(+d0: List<&2, Nat>, +m: List<&2, U32>, +aux: List<&2, U32>, pa: P.Affine) -> Maybe<&2, List<&2, U32>>:
137	  match pa:
138	    case P.Affine{px, +py}:
139	      +d = S.select(is_odd(py), S.neg(d0), d0)
140	      +pb = B.to_be(px)
141	      +t = xor_bytes(B.to_be(d), tagged(tag_aux(), aux))
142	      +k0 = S.reduce(B.of_be(tagged(tag_nonce(), cat(t, cat(pb, m)))))
143	      sign_nz(d, pb, m, k0, Bool.not(S.is_zero(k0)))
144	
145	def sign_d(+m: List<&2, U32>, +aux: List<&2, U32>, md: Maybe<&2, List<&2, Nat>>) -> Maybe<&2, List<&2, U32>>:
146	  match md:
147	    case None{}: None{}
148	    case Some{+d0}: sign_p(d0, m, aux, P.to_affine(P.mul(d0, P.g())))
149	
150	def sign_len(+sk: List<&2, U32>, +m: List<&2, U32>, +aux: List<&2, U32>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
151	  match ok:
152	    case True{}: sign_d(m, aux, secret(sk))
153	    case False{}: None{}
154	
155	# BIP-340 Sign(sk, m, a) for a 32-byte secret key and 32 bytes of auxiliary
156	# randomness; None for an invalid key (or, with negligible probability, a
157	# zero nonce or a failed self-check)
158	def sign(+sk: List<&2, U32>, +m: List<&2, U32>, +aux: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
159	  sign_len(sk, m, aux, B.has_len(32n, aux))