]> Git — Sourcephile - majurity.git/blob - hjugement-protocol/Protocol/Election.hs
protocol: handle list length checks in the library
[majurity.git] / hjugement-protocol / Protocol / Election.hs
1 {-# LANGUAGE DataKinds #-}
2 {-# LANGUAGE GADTs #-}
3 {-# LANGUAGE OverloadedStrings #-}
4 module Protocol.Election where
5
6 import Control.Monad (Monad(..), mapM, zipWithM)
7 import Control.Monad.Morph (MFunctor(..))
8 import Control.Monad.Trans.Class (MonadTrans(..))
9 import Data.Bool
10 import Data.Either (either)
11 import Data.Eq (Eq(..))
12 import Data.Foldable (Foldable, foldMap, and)
13 import Data.Function (($), id, const)
14 import Data.Functor (Functor, (<$>))
15 import Data.Functor.Identity (Identity(..))
16 import Data.Maybe (Maybe(..), fromMaybe)
17 import Data.Ord (Ord(..))
18 import Data.Semigroup (Semigroup(..))
19 import Data.String (IsString(..))
20 import Data.Text (Text)
21 import Data.Traversable (Traversable(..))
22 import Data.Tuple (fst, snd)
23 import GHC.Natural (minusNaturalMaybe)
24 import Numeric.Natural (Natural)
25 import Prelude (error, fromIntegral)
26 import Text.Show (Show(..))
27 import qualified Control.Monad.Trans.Except as Exn
28 import qualified Control.Monad.Trans.State.Strict as S
29 import qualified Data.ByteString as BS
30 import qualified Data.List as List
31
32 import Protocol.Arithmetic
33 import Protocol.Credential
34
35 -- * Type 'Encryption'
36 -- | ElGamal-like encryption.
37 -- Its security relies on the /Discrete Logarithm problem/.
38 --
39 -- Because ('groupGen' '^'encNonce '^'secKey '==' 'groupGen' '^'secKey '^'encNonce),
40 -- knowing @secKey@, one can divide 'encryption_vault' by @('encryption_nonce' '^'secKey)@
41 -- to decipher @('groupGen' '^'clear)@, then @clear@ must be small to be decryptable,
42 -- because it is encrypted as a power of 'groupGen' to enable the additive homomorphism.
43 data Encryption q = Encryption
44 { encryption_nonce :: G q
45 -- ^ Public part of the random 'encNonce': @('groupGen' '^'encNonce)@
46 , encryption_vault :: G q
47 -- ^ Encrypted clear: @('pubKey' '^'r '*' 'groupGen' '^'clear)@
48 } deriving (Eq,Show)
49
50 -- | Additive homomorphism.
51 -- Using the fact that: @'groupGen' '^'x '*' 'groupGen' '^'y '==' 'groupGen' '^'(x'+'y)@.
52 instance SubGroup q => Additive (Encryption q) where
53 zero = Encryption one one
54 x+y = Encryption
55 (encryption_nonce x * encryption_nonce y)
56 (encryption_vault x * encryption_vault y)
57
58 -- *** Type 'EncryptionNonce'
59 type EncryptionNonce = E
60
61 -- | @('encrypt' pubKey clear)@ returns an ElGamal-like 'Encryption'.
62 --
63 -- WARNING: the secret encryption nonce (@encNonce@)
64 -- is returned alongside the 'Encryption'
65 -- in order to prove the validity of the encrypted clear in 'prove',
66 -- but this secret @encNonce@ MUST be forgotten after that,
67 -- as it may be used to decipher the 'Encryption'
68 -- without the secret key associated with 'pubKey'.
69 encrypt ::
70 Monad m => RandomGen r => SubGroup q =>
71 PublicKey q -> E q ->
72 S.StateT r m (EncryptionNonce q, Encryption q)
73 encrypt pubKey clear = do
74 encNonce <- random
75 -- NOTE: preserve the 'encNonce' for 'prove'.
76 return $ (encNonce,)
77 Encryption
78 { encryption_nonce = groupGen^encNonce
79 , encryption_vault = pubKey ^encNonce * groupGen^clear
80 -- NOTE: 'clear' is put as exponent in order
81 -- to make an additive homomorphism
82 -- instead of a multiplicative homomorphism.
83 -- log (a*b) = log a + log b
84 }
85
86 -- * Type 'Proof'
87 -- | 'Proof' of knowledge of a discrete logarithm:
88 -- @secret == logBase base (base^secret)@.
89 --
90 -- NOTE: Since @(pubKey == 'groupGen' '^'secKey)@, then:
91 -- @(logBase 'encryption_nonce' ('encryption_vault' '*' 'encryption_nonce') '==' secKey '+' clear)@.
92 data Proof q = Proof
93 { proof_challenge :: Challenge q
94 -- ^ 'Challenge' sent by the verifier to the prover
95 -- to ensure that the prover really has knowledge
96 -- of the secret and is not replaying.
97 -- Actually, 'proof_challenge' is not sent in a 'prove',
98 -- but derived from the prover's 'Commitment's and statements
99 -- with a collision resistant hash.
100 , proof_response :: E q
101 -- ^ Response sent by the prover to the verifier.
102 -- Usually: @nonce '+' sec '*' 'proof_challenge'@.
103 --
104 -- To be computed efficiently, it requires @sec@:
105 -- either the @secKey@ (in 'signature_proof')
106 -- or the @encNonce@ (in 'prove').
107 } deriving (Eq,Show)
108
109 -- ** Type 'Challenge'
110 type Challenge = E
111
112 -- ** Type 'Oracle'
113 -- An 'Oracle' returns the 'Challenge' of the 'Commitment's
114 -- by hashing them (eventually with other 'Commitment's).
115 --
116 -- Used in 'prove' it enables a Fiat-Shamir transformation
117 -- of an /interactive zero-knowledge/ (IZK) proof
118 -- into a /non-interactive zero-knowledge/ (NIZK) proof.
119 -- That is to say that the verifier does not have
120 -- to send a 'Challenge' to the prover.
121 -- Indeed, the prover now handles the 'Challenge'
122 -- which becomes a (collision resistant) hash
123 -- of the prover's commitments (and statements to be a stronger proof).
124 type Oracle list q = list (Commitment q) -> Challenge q
125
126 -- | @('prove' sec commitments oracle)@
127 -- returns a 'Proof' that @sec@ is known.
128 --
129 -- The 'Oracle' is given the 'commitments'
130 -- raised to the power of the secret nonce of the 'Proof',
131 -- as those are the 'commitments' that the verifier will obtain
132 -- when composing the 'proof_challenge' and 'proof_response' together
133 -- (in 'encryptionCommitments').
134 --
135 -- NOTE: 'sec' is @secKey@ in 'signature_proof' or @encNonce@ in 'proveEncryption'.
136 --
137 -- NOTE: The 'commitments' are @['groupGen']@ in 'signature_proof'
138 -- or @['groupGen', 'pubKey']@ in 'proveEncryption'.
139 --
140 -- WARNING: for 'prove' to be a so-called /strong Fiat-Shamir transformation/ (not a weak):
141 -- the statement must be included in the hash (not only the commitments).
142 --
143 -- NOTE: a 'random' @nonce@ is used to ensure each 'prove'
144 -- does not reveal any information regarding the secret 'sec'.
145 prove ::
146 Monad m => RandomGen r => SubGroup q => Functor list =>
147 E q -> list (Commitment q) -> Oracle list q -> S.StateT r m (Proof q)
148 prove sec commitments oracle = do
149 nonce <- random
150 let proof_challenge = oracle $ (^ nonce) <$> commitments
151 return Proof
152 { proof_challenge
153 , proof_response = nonce - sec*proof_challenge
154 }
155
156 -- ** Type 'Commitment'
157 type Commitment = G
158
159 -- | @('commit' proof x y)@ returns a 'Commitment'
160 -- from the given 'Proof' with the knowledge of the verifier.
161 --
162 -- NOTE: Contrary to Helios-C specifications,
163 -- @('*')@ is used instead of @('/')@
164 -- to avoid the performance cost of a modular exponentiation
165 -- @('^' ('groupOrder' '-' 'one'))@,
166 -- this is compensated by using @('-')@ instead of @('+')@ in 'prove'.
167 commit :: SubGroup q => Proof q -> G q -> G q -> Commitment q
168 commit Proof{..} x y = x^proof_response * y^proof_challenge
169 {-# INLINE commit #-}
170
171 -- ** Type 'Opinion'
172 -- | Index of a 'Disjunction' within a list of them.
173 -- It is encrypted as an 'E'xponent by 'encrypt'.
174 type Opinion = E
175
176 -- ** Type 'Disjunction'
177 -- | A 'Disjunction' is an 'inv'ersed @('groupGen' '^'opinion)@
178 -- it's used in 'proveEncryption' to generate a 'Proof'
179 -- that an 'encryption_vault' contains a given @('groupGen' '^'opinion)@,
180 type Disjunction = G
181
182 booleanDisjunctions :: SubGroup q => [Disjunction q]
183 booleanDisjunctions = List.take 2 groupGenInverses
184
185 intervalDisjunctions :: SubGroup q => Opinion q -> Opinion q -> [Disjunction q]
186 intervalDisjunctions mini maxi =
187 List.genericTake (fromMaybe 0 $ (natE maxi + 1)`minusNaturalMaybe`natE mini) $
188 List.genericDrop (natE mini) $
189 groupGenInverses
190
191 -- ** Type 'DisjProof'
192 -- | A list of 'Proof's to prove that the 'Opinion' within an 'Encryption'
193 -- is indexing a 'Disjunction' within a list of them,
194 -- without knowing which 'Opinion' it is.
195 newtype DisjProof q = DisjProof [Proof q]
196 deriving (Eq,Show)
197
198 -- | @('proveEncryption' pubKey zkp disjs opin (encNonce, enc))@
199 -- returns a 'DisjProof' that 'enc' 'encrypt's
200 -- one of the 'Disjunction's within 'disjs',
201 -- without revealing which one it is.
202 --
203 -- A /NIZK Disjunctive Chaum Pedersen Logarithm Equality/ is used.
204 proveEncryption ::
205 forall m r q.
206 Monad m => RandomGen r => SubGroup q =>
207 PublicKey q -> ZKP ->
208 [Disjunction q] -> Opinion q ->
209 (EncryptionNonce q, Encryption q) ->
210 S.StateT r (Exn.ExceptT ErrorProove m) (DisjProof q)
211 proveEncryption pubKey zkp disjs opinion (encNonce, enc)
212 | (prevDisjs, _indexedDisj:nextDisjs) <-
213 List.genericSplitAt (natE opinion) disjs = do
214 -- Fake proofs for all values except the correct one.
215 prevFakes <- fakeProof `mapM` prevDisjs
216 nextFakes <- fakeProof `mapM` nextDisjs
217 let prevProofs = fst <$> prevFakes
218 let nextProofs = fst <$> nextFakes
219 let challengeSum =
220 sum (proof_challenge <$> prevProofs) +
221 sum (proof_challenge <$> nextProofs)
222 correctProof <- prove encNonce [groupGen, pubKey] $
223 -- 'Oracle'
224 \correctCommitments ->
225 let commitments =
226 foldMap snd prevFakes <>
227 correctCommitments <>
228 foldMap snd nextFakes in
229 hash (encryptionStatement zkp enc) commitments - challengeSum
230 return $ DisjProof $ prevProofs <> (correctProof : nextProofs)
231 | otherwise = lift $ Exn.throwE $
232 ErrorProove_InvalidOpinion
233 (fromIntegral $ List.length disjs)
234 (natE opinion)
235 where
236 fakeProof :: Disjunction q -> S.StateT r (Exn.ExceptT ErrorProove m) (Proof q, [Commitment q])
237 fakeProof disj = do
238 -- Returns 'Commitment's verifiables by the verifier,
239 -- but computed from random 'proof_challenge' and 'proof_response'
240 -- instead of correct ones.
241 proof_challenge <- random
242 proof_response <- random
243 let proof = Proof{..}
244 return (proof, encryptionCommitments pubKey enc (disj, proof))
245
246 verifyEncryption ::
247 Monad m =>
248 SubGroup q =>
249 PublicKey q -> ZKP ->
250 [Disjunction q] ->
251 (Encryption q, DisjProof q) ->
252 Exn.ExceptT ErrorValidateEncryption m Bool
253 verifyEncryption pubKey zkp disjs (enc, DisjProof proofs)
254 | List.length proofs /= List.length disjs =
255 Exn.throwE $ ErrorValidateEncryption_InvalidProofLength
256 (fromIntegral $ List.length proofs)
257 (fromIntegral $ List.length disjs)
258 | otherwise = return $ challengeSum == hash (encryptionStatement zkp enc) commitments
259 where
260 challengeSum = sum (proof_challenge <$> proofs)
261 commitments = foldMap (encryptionCommitments pubKey enc) (List.zip disjs proofs)
262
263 encryptionStatement :: SubGroup q => ZKP -> Encryption q -> BS.ByteString
264 encryptionStatement (ZKP zkp) Encryption{..} =
265 "prove|"<>zkp<>"|"<>
266 fromString (show (natG encryption_nonce))<>","<>
267 fromString (show (natG encryption_vault))<>"|"
268
269 -- | @('encryptionCommitments' pubKey enc (disj,proof))@
270 -- returns the 'Commitment's with only the knowledge of the verifier.
271 --
272 -- The 'Proof' comes from 'prove' of @fakeProof@ in 'proveEncryption'.
273 encryptionCommitments ::
274 SubGroup q =>
275 PublicKey q -> Encryption q ->
276 (Disjunction q, Proof q) -> [G q]
277 encryptionCommitments pubKey Encryption{..} (disj, proof) =
278 [ commit proof groupGen encryption_nonce
279 -- == groupGen ^ nonce if 'Proof' comes from 'prove'
280 , commit proof pubKey (encryption_vault*disj)
281 -- == pubKey ^ nonce if 'Proof' comes from 'prove'
282 -- and 'encryption_vault' encrypts (- logBase groupGen disj).
283 ]
284
285 -- ** Type 'ZKP'
286 -- | Zero-knowledge proof
287 newtype ZKP = ZKP BS.ByteString
288
289 -- ** Type 'ErrorProove'
290 -- | Error raised by 'proveEncryption'.
291 data ErrorProove
292 = ErrorProove_InvalidOpinion Natural Natural
293 -- ^ When the opinion is not within the number of 'Disjunction's.
294 deriving (Eq,Show)
295
296 -- ** Type 'ErrorValidateEncryption'
297 -- | Error raised by 'verifyEncryption'.
298 data ErrorValidateEncryption
299 = ErrorValidateEncryption_InvalidProofLength Natural Natural
300 -- ^ When the number of proofs is different than
301 -- the number of 'Disjunction's.
302 deriving (Eq,Show)
303
304 -- * Type 'Question'
305 data Question q = Question
306 { question_text :: Text
307 , question_choices :: [Text]
308 , question_mini :: Opinion q
309 , question_maxi :: Opinion q
310 -- , question_blank :: Maybe Bool
311 } deriving (Eq, Show)
312
313 -- * Type 'Answer'
314 data Answer q = Answer
315 { answer_opinions :: [(Encryption q, DisjProof q)]
316 -- ^ Encrypted 'Opinion' for each 'question_choices'
317 -- with a 'DisjProof' that they belong to [0,1].
318 , answer_sumProof :: DisjProof q
319 -- ^ Proofs that the sum of the 'Opinon's encrypted in 'answer_opinions'
320 -- is an element of @[mini..maxi]@.
321 -- , answer_blankProof ::
322 } deriving (Eq,Show)
323
324 -- ** Type 'ErrorAnswer'
325 -- | Error raised by 'encryptAnswer'.
326 data ErrorAnswer
327 = ErrorAnswer_WrongNumberOfOpinions Natural Natural
328 -- ^ When the number of opinions is different than
329 -- the number of choices ('question_choices').
330 | ErrorAnswer_WrongSumOfOpinions Natural Natural Natural
331 -- ^ When the sum of opinions is not within the bounds
332 -- of 'question_mini' and 'question_maxi'.
333 deriving (Eq,Show)
334
335 -- | @('encryptAnswer' pubKey zkp quest opinions)@
336 -- returns an 'Answer' validable by 'verifyAnswer',
337 -- unless an 'ErrorAnswer' is returned.
338 encryptAnswer ::
339 Monad m => RandomGen r => SubGroup q =>
340 PublicKey q -> ZKP ->
341 Question q -> [Bool] ->
342 S.StateT r (Exn.ExceptT ErrorAnswer m) (Answer q)
343 encryptAnswer pubKey zkp Question{..} opinionsBools
344 | not (question_mini <= opinionsSum && opinionsSum <= question_maxi) =
345 lift $ Exn.throwE $
346 ErrorAnswer_WrongSumOfOpinions
347 (natE opinionsSum)
348 (natE question_mini)
349 (natE question_maxi)
350 | List.length opinions /= List.length question_choices =
351 lift $ Exn.throwE $
352 ErrorAnswer_WrongNumberOfOpinions
353 (fromIntegral $ List.length opinions)
354 (fromIntegral $ List.length question_choices)
355 | otherwise = do
356 encryptions <- encrypt pubKey `mapM` opinions
357 hoist (Exn.withExceptT (\case
358 ErrorProove_InvalidOpinion{} -> error "encryptAnswer: impossible happened"
359 )) $ do
360 individualProofs <- zipWithM
361 (proveEncryption pubKey zkp booleanDisjunctions)
362 opinions encryptions
363 sumProof <- proveEncryption pubKey zkp
364 (intervalDisjunctions question_mini question_maxi)
365 (opinionsSum - question_mini)
366 ( sum (fst <$> encryptions) -- NOTE: sum the 'encNonce's
367 , sum (snd <$> encryptions) -- NOTE: sum the 'Encryption's
368 )
369 return $ Answer
370 { answer_opinions = List.zip
371 (snd <$> encryptions) -- NOTE: drop encNonce
372 individualProofs
373 , answer_sumProof = sumProof
374 }
375 where
376 opinionsSum = sum opinions
377 opinions = (\o -> if o then one else zero) <$> opinionsBools
378
379 verifyAnswer ::
380 SubGroup q =>
381 PublicKey q -> ZKP ->
382 Question q -> Answer q -> Bool
383 verifyAnswer pubKey zkp Question{..} Answer{..}
384 | List.length question_choices /= List.length answer_opinions = False
385 | otherwise = either (const False) id $ Exn.runExcept $ do
386 validOpinions <-
387 verifyEncryption pubKey zkp booleanDisjunctions
388 `traverse` answer_opinions
389 validSum <- verifyEncryption pubKey zkp
390 (intervalDisjunctions question_mini question_maxi)
391 ( sum (fst <$> answer_opinions)
392 , answer_sumProof )
393 return (and validOpinions && validSum)
394
395 -- * Type 'Election'
396 data Election q = Election
397 { election_name :: Text
398 , election_description :: Text
399 , election_publicKey :: PublicKey q
400 , election_questions :: [Question q]
401 , election_uuid :: UUID
402 , election_hash :: Hash -- TODO: serialize to JSON to calculate this
403 } deriving (Eq,Show)
404
405 -- ** Type 'Hash'
406 newtype Hash = Hash Text
407 deriving (Eq,Ord,Show)
408
409 -- * Type 'Ballot'
410 data Ballot q = Ballot
411 { ballot_answers :: [Answer q]
412 , ballot_signature :: Maybe (Signature q)
413 , ballot_election_uuid :: UUID
414 , ballot_election_hash :: Hash
415 }
416
417 -- | @('encryptBallot' elec ('Just' secKey) opinionsByQuest)@
418 -- returns a 'Ballot' signed by 'secKey' (the voter's secret key)
419 -- where 'opinionsByQuest' is a list of 'Opinion's
420 -- on each 'question_choices' of each 'election_questions'.
421 encryptBallot ::
422 Monad m => RandomGen r => SubGroup q =>
423 Election q -> Maybe (SecretKey q) -> [[Bool]] ->
424 S.StateT r (Exn.ExceptT ErrorBallot m) (Ballot q)
425 encryptBallot Election{..} secKeyMay opinionsByQuest
426 | List.length election_questions /= List.length opinionsByQuest =
427 lift $ Exn.throwE $
428 ErrorBallot_WrongNumberOfAnswers
429 (fromIntegral $ List.length opinionsByQuest)
430 (fromIntegral $ List.length election_questions)
431 | otherwise = do
432 let (keysMay, zkp) =
433 case secKeyMay of
434 Nothing -> (Nothing, ZKP "")
435 Just secKey ->
436 ( Just (secKey, pubKey)
437 , ZKP (fromString (show (natG pubKey))) )
438 where pubKey = groupGen ^ secKey
439 ballot_answers <-
440 hoist (Exn.withExceptT ErrorBallot_Answer) $
441 zipWithM (encryptAnswer election_publicKey zkp)
442 election_questions opinionsByQuest
443 ballot_signature <- case keysMay of
444 Nothing -> return Nothing
445 Just (secKey, signature_publicKey) -> do
446 signature_proof <-
447 prove secKey (Identity groupGen) $
448 \(Identity commitment) ->
449 hash
450 (signatureCommitments zkp commitment)
451 (signatureStatement ballot_answers)
452 return $ Just Signature{..}
453 return Ballot
454 { ballot_answers
455 , ballot_election_hash = election_hash
456 , ballot_election_uuid = election_uuid
457 , ballot_signature
458 }
459
460 verifyBallot :: SubGroup q => Election q -> Ballot q -> Bool
461 verifyBallot Election{..} Ballot{..} =
462 ballot_election_uuid == election_uuid &&
463 ballot_election_hash == election_hash &&
464 List.length election_questions == List.length ballot_answers &&
465 let (isValidSign, zkpSign) =
466 case ballot_signature of
467 Nothing -> (True, ZKP "")
468 Just Signature{..} ->
469 let zkp = ZKP (fromString (show (natG signature_publicKey))) in
470 (, zkp) $
471 proof_challenge signature_proof == hash
472 (signatureCommitments zkp (commit signature_proof groupGen signature_publicKey))
473 (signatureStatement ballot_answers)
474 in
475 and $ isValidSign :
476 List.zipWith (verifyAnswer election_publicKey zkpSign)
477 election_questions ballot_answers
478
479 -- ** Type 'Signature'
480 -- | Schnorr-like signature.
481 --
482 -- Used to avoid 'Ballot' stuffing.
483 data Signature q = Signature
484 { signature_publicKey :: PublicKey q
485 , signature_proof :: Proof q
486 }
487
488 -- | @('signatureStatement' answers)@
489 -- returns all the 'encryption_nonce's and 'encryption_vault's
490 -- of the given @answers@.
491 signatureStatement :: Foldable f => SubGroup q => f (Answer q) -> [G q]
492 signatureStatement =
493 foldMap $ \Answer{..} ->
494 (`foldMap` answer_opinions) $ \(Encryption{..}, _proof) ->
495 [encryption_nonce, encryption_vault]
496
497 -- | @('signatureCommitments' zkp commitment)@
498 -- returns the hashable content from the knowledge of the verifier.
499 signatureCommitments :: SubGroup q => ZKP -> Commitment q -> BS.ByteString
500 signatureCommitments (ZKP zkp) commitment =
501 "sig|"<>zkp<>"|"<>fromString (show (natG commitment))<>"|"
502
503 -- ** Type 'ErrorBallot'
504 -- | Error raised by 'encryptBallot'.
505 data ErrorBallot
506 = ErrorBallot_WrongNumberOfAnswers Natural Natural
507 -- ^ When the number of answers
508 -- is different than the number of questions.
509 | ErrorBallot_Answer ErrorAnswer
510 -- ^ When 'encryptAnswer' raised an 'ErrorAnswer'.
511 deriving (Eq,Show)