1 {-# LANGUAGE DataKinds #-}
3 {-# LANGUAGE OverloadedStrings #-}
4 module Protocol.Election where
6 import Control.Monad (Monad(..), mapM, zipWithM)
7 import Control.Monad.Morph (MFunctor(..))
8 import Control.Monad.Trans.Class (MonadTrans(..))
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
32 import Protocol.Arithmetic
33 import Protocol.Credential
35 -- * Type 'Encryption'
36 -- | ElGamal-like encryption.
37 -- Its security relies on the /Discrete Logarithm problem/.
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)@
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
55 (encryption_nonce x * encryption_nonce y)
56 (encryption_vault x * encryption_vault y)
58 -- *** Type 'EncryptionNonce'
59 type EncryptionNonce = E
61 -- | @('encrypt' pubKey clear)@ returns an ElGamal-like 'Encryption'.
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'.
70 Monad m => RandomGen r => SubGroup q =>
72 S.StateT r m (EncryptionNonce q, Encryption q)
73 encrypt pubKey clear = do
75 -- NOTE: preserve the 'encNonce' for 'prove'.
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
87 -- | 'Proof' of knowledge of a discrete logarithm:
88 -- @secret == logBase base (base^secret)@.
90 -- NOTE: Since @(pubKey == 'groupGen' '^'secKey)@, then:
91 -- @(logBase 'encryption_nonce' ('encryption_vault' '*' 'encryption_nonce') '==' secKey '+' clear)@.
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'@.
104 -- To be computed efficiently, it requires @sec@:
105 -- either the @secKey@ (in 'signature_proof')
106 -- or the @encNonce@ (in 'prove').
109 -- ** Type 'Challenge'
113 -- An 'Oracle' returns the 'Challenge' of the 'Commitment's
114 -- by hashing them (eventually with other 'Commitment's).
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
126 -- | @('prove' sec commitments oracle)@
127 -- returns a 'Proof' that @sec@ is known.
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').
135 -- NOTE: 'sec' is @secKey@ in 'signature_proof' or @encNonce@ in 'proveEncryption'.
137 -- NOTE: The 'commitments' are @['groupGen']@ in 'signature_proof'
138 -- or @['groupGen', 'pubKey']@ in 'proveEncryption'.
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).
143 -- NOTE: a 'random' @nonce@ is used to ensure each 'prove'
144 -- does not reveal any information regarding the secret 'sec'.
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
150 let proof_challenge = oracle $ (^ nonce) <$> commitments
153 , proof_response = nonce - sec*proof_challenge
156 -- ** Type 'Commitment'
159 -- | @('commit' proof x y)@ returns a 'Commitment'
160 -- from the given 'Proof' with the knowledge of the verifier.
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 #-}
172 -- | Index of a 'Disjunction' within a list of them.
173 -- It is encrypted as an 'E'xponent by 'encrypt'.
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)@,
182 booleanDisjunctions :: SubGroup q => [Disjunction q]
183 booleanDisjunctions = List.take 2 groupGenInverses
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) $
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]
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.
203 -- A /NIZK Disjunctive Chaum Pedersen Logarithm Equality/ is used.
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
220 sum (proof_challenge <$> prevProofs) +
221 sum (proof_challenge <$> nextProofs)
222 correctProof <- prove encNonce [groupGen, pubKey] $
224 \correctCommitments ->
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)
236 fakeProof :: Disjunction q -> S.StateT r (Exn.ExceptT ErrorProove m) (Proof q, [Commitment q])
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))
249 PublicKey q -> ZKP ->
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
260 challengeSum = sum (proof_challenge <$> proofs)
261 commitments = foldMap (encryptionCommitments pubKey enc) (List.zip disjs proofs)
263 encryptionStatement :: SubGroup q => ZKP -> Encryption q -> BS.ByteString
264 encryptionStatement (ZKP zkp) Encryption{..} =
266 fromString (show (natG encryption_nonce))<>","<>
267 fromString (show (natG encryption_vault))<>"|"
269 -- | @('encryptionCommitments' pubKey enc (disj,proof))@
270 -- returns the 'Commitment's with only the knowledge of the verifier.
272 -- The 'Proof' comes from 'prove' of @fakeProof@ in 'proveEncryption'.
273 encryptionCommitments ::
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).
286 -- | Zero-knowledge proof
287 newtype ZKP = ZKP BS.ByteString
289 -- ** Type 'ErrorProove'
290 -- | Error raised by 'proveEncryption'.
292 = ErrorProove_InvalidOpinion Natural Natural
293 -- ^ When the opinion is not within the number of 'Disjunction's.
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.
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)
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 ::
324 -- ** Type 'ErrorAnswer'
325 -- | Error raised by 'encryptAnswer'.
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'.
335 -- | @('encryptAnswer' pubKey zkp quest opinions)@
336 -- returns an 'Answer' validable by 'verifyAnswer',
337 -- unless an 'ErrorAnswer' is returned.
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) =
346 ErrorAnswer_WrongSumOfOpinions
350 | List.length opinions /= List.length question_choices =
352 ErrorAnswer_WrongNumberOfOpinions
353 (fromIntegral $ List.length opinions)
354 (fromIntegral $ List.length question_choices)
356 encryptions <- encrypt pubKey `mapM` opinions
357 hoist (Exn.withExceptT (\case
358 ErrorProove_InvalidOpinion{} -> error "encryptAnswer: impossible happened"
360 individualProofs <- zipWithM
361 (proveEncryption pubKey zkp booleanDisjunctions)
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
370 { answer_opinions = List.zip
371 (snd <$> encryptions) -- NOTE: drop encNonce
373 , answer_sumProof = sumProof
376 opinionsSum = sum opinions
377 opinions = (\o -> if o then one else zero) <$> opinionsBools
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
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)
393 return (and validOpinions && validSum)
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
406 newtype Hash = Hash Text
407 deriving (Eq,Ord,Show)
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
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'.
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 =
428 ErrorBallot_WrongNumberOfAnswers
429 (fromIntegral $ List.length opinionsByQuest)
430 (fromIntegral $ List.length election_questions)
434 Nothing -> (Nothing, ZKP "")
436 ( Just (secKey, pubKey)
437 , ZKP (fromString (show (natG pubKey))) )
438 where pubKey = groupGen ^ secKey
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
447 prove secKey (Identity groupGen) $
448 \(Identity commitment) ->
450 (signatureCommitments zkp commitment)
451 (signatureStatement ballot_answers)
452 return $ Just Signature{..}
455 , ballot_election_hash = election_hash
456 , ballot_election_uuid = election_uuid
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
471 proof_challenge signature_proof == hash
472 (signatureCommitments zkp (commit signature_proof groupGen signature_publicKey))
473 (signatureStatement ballot_answers)
476 List.zipWith (verifyAnswer election_publicKey zkpSign)
477 election_questions ballot_answers
479 -- ** Type 'Signature'
480 -- | Schnorr-like signature.
482 -- Used to avoid 'Ballot' stuffing.
483 data Signature q = Signature
484 { signature_publicKey :: PublicKey q
485 , signature_proof :: Proof q
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]
493 foldMap $ \Answer{..} ->
494 (`foldMap` answer_opinions) $ \(Encryption{..}, _proof) ->
495 [encryption_nonce, encryption_vault]
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))<>"|"
503 -- ** Type 'ErrorBallot'
504 -- | Error raised by 'encryptBallot'.
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'.