/
clsag.py
144 lines (124 loc) · 3.98 KB
/
clsag.py
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
# CLSAG: Compressed Linkable Spontaneous Anonymous Group signatures
# https://github.com/monero-project/research-lab/issues/52
#
# For a ring with members of the form (P_i,C_i) such that (P_l,C_l) = (p*G,z*G)
# for some index l, generates a linkable ring signature on a message such that
# any public key is equiprobable as corresponding to the signing key.
#
# Two valid signatures containing the same key image were signed with the same
# private key, regardless of the other ring members used in the signature.
#
# By providing a PRNG seed value (which _should_ be unique between uses) during
# signing, a verifier with the same seed value can extract the signing index.
import dumb25519
from dumb25519 import hash_to_scalar, hash_to_point, random_scalar, G
# CLSAG signature
class Signature:
h0 = None
s = None
I = None
D = None
# Generate a CLSAG signature
# INPUTS
# M: message
# p: private key
# P: public key vector
# z: commitment private key
# C: commitment vector
# seed: PRNG seed (optional)
# index: if set, bypass key index check (testing only)
# RETURNS
# sig: Signature
# RAISES
# IndexError if index is not set and private keys are invalid
def sign(M,p,P,z,C,seed=None,index=None):
n = len(P) # ring size
# Recover the private key index
l = None
if index is not None:
l = index
else:
for i in range(n):
if P[i] == G*p and C[i] == G*z:
l = i
break
if l is None:
raise IndexError('Private keys must correspond to public keys!')
# Construct key images
I = hash_to_point(P[l])*p
D = hash_to_point(P[l])*z
# Now generate the signature
mu_P = hash_to_scalar('CLSAG_agg_0',P,I,C,D)
mu_C = hash_to_scalar('CLSAG_agg_1',P,I,C,D)
h = [None]*n
alpha = random_scalar()
# Scalars are either random (seed is None) or hash-constructed
if seed is None:
s = [random_scalar() for _ in range(n)]
else:
s = [hash_to_scalar('CLSAG_scalar',seed,I,i) for i in range(n)]
# Private index
L = G*alpha
R = hash_to_point(P[l])*alpha
h[(l+1) % n] = hash_to_scalar('CLSAG_round',P,C,M,L,R)
# Decoy indices
if n > 1:
for i in range(l+1,l+n):
i = i % n
L = G*s[i] + P[i]*(h[i]*mu_P) + C[i]*(h[i]*mu_C)
R = hash_to_point(P[i])*s[i] + I*(h[i]*mu_P) + D*(h[i]*mu_C)
h[(i+1) % n] = hash_to_scalar('CLSAG_round',P,C,M,L,R)
# Final scalar computation
s[l] = alpha - h[l]*(mu_P*p + mu_C*z)
# Assemble the signature
sig = Signature()
sig.h0 = h[0]
sig.s = s
sig.I = I
sig.D = D
return sig
# Verify a CLSAG signature
# INPUTS
# M: message
# P: public key vector
# C: commitment vector
# sig: Signature
# seed: PRNG seed (optional)
# RETURNS
# signing index (or None) if valid
# RAISES
# ArithmeticError if signature is invalid
def verify(M,P,C,sig,seed=None):
n = len(P) # ring size
h0 = sig.h0
s = sig.s
I = sig.I
D = sig.D
# Reconstruct the aggregation coefficients
h = [None]*n
mu_P = hash_to_scalar('CLSAG_agg_0',P,I,C,D)
mu_C = hash_to_scalar('CLSAG_agg_1',P,I,C,D)
# Recover signing index if possible
signer = None
if seed is not None:
hashes = 0 # number of hash-constructed scalars found
for i in range(n):
if s[i] == hash_to_scalar('CLSAG_scalar',seed,I,i):
hashes += 1
else:
signer = i
# All but one scalar must be hash-constructed
if hashes != n-1:
signer = None
for i in range(0,n):
if i == 0:
temp_h = h0
else:
temp_h = h[i]
L = G*s[i%n] + P[i%n]*(temp_h*mu_P) + C[i%n]*(temp_h*mu_C)
R = hash_to_point(P[i%n])*s[i%n] + I*(temp_h*mu_P) + D*(temp_h*mu_C)
h[(i+1)%n] = hash_to_scalar('CLSAG_round',P,C,M,L,R)
# Final check
if not h[0] == h0:
raise ArithmeticError('Verification failed!')
return signer