elastic_elgamal/app/
quadratic_voting.rs

1//! Quadratic voting application.
2
3use core::fmt;
4
5use elliptic_curve::rand_core::{CryptoRng, RngCore};
6use merlin::Transcript;
7#[cfg(feature = "serde")]
8use serde::{Deserialize, Serialize};
9
10use crate::{
11    Ciphertext, PreparedRange, PublicKey, RangeDecomposition, RangeProof, SumOfSquaresProof,
12    VerificationError, alloc::Vec, group::Group,
13};
14
15/// [Quadratic voting] parameters prepared for a certain [`Group`].
16///
17/// The parameters are:
18///
19/// - [Receiver key](Self::receiver()) using which votes in [`QuadraticVotingBallot`]s
20///   are encrypted
21/// - [Number of options](Self::options_count()) in the ballot
22/// - [Number of credits](Self::credits()) per ballot
23/// - [Maximum number of votes](Self::max_votes()) per option
24///
25/// See [`QuadraticVotingBallot`] for a detailed description of parameters.
26///
27/// [Quadratic voting]: https://en.wikipedia.org/wiki/Quadratic_voting
28///
29/// # Examples
30///
31/// ```
32/// # use elastic_elgamal::{app::QuadraticVotingParams, group::Ristretto, Keypair};
33/// let (receiver, _) = Keypair::<Ristretto>::generate(&mut rand::rng())
34///     .into_tuple();
35/// let mut params = QuadraticVotingParams::new(receiver, 5, 20);
36/// // 5 options, 20 credits.
37/// assert_eq!(params.options_count(), 5);
38/// assert_eq!(params.credits(), 20);
39/// // By default, max votes per option are determined based on credits
40/// assert_eq!(params.max_votes(), 4); // 4 < sqrt(20) < 5
41///
42/// // It is possible to reduce max votes per ballot.
43/// params.set_max_votes(3);
44/// assert_eq!(params.max_votes(), 3);
45/// ```
46#[derive(Debug, Clone)]
47pub struct QuadraticVotingParams<G: Group> {
48    vote_count_range: PreparedRange<G>,
49    credit_range: PreparedRange<G>,
50    options_count: usize,
51    receiver: PublicKey<G>,
52}
53
54impl<G: Group> QuadraticVotingParams<G> {
55    /// Creates new parameters for the specified number of `credits` allocated per voter.
56    ///
57    /// The maximum number of votes per option is automatically set as `floor(sqrt(credits))`;
58    /// it can be changed via [`Self::set_max_votes()`].
59    ///
60    /// # Panics
61    ///
62    /// Panics if the number of options or credits is zero.
63    pub fn new(receiver: PublicKey<G>, options: usize, credits: u64) -> Self {
64        assert!(options > 0, "Number of options must be positive");
65        assert!(credits > 0, "Number of credits must be positive");
66
67        let max_votes = isqrt(credits);
68        let vote_count_range = RangeDecomposition::optimal(max_votes + 1);
69        let credit_range = RangeDecomposition::optimal(credits + 1);
70        Self {
71            vote_count_range: vote_count_range.into(),
72            credit_range: credit_range.into(),
73            options_count: options,
74            receiver,
75        }
76    }
77
78    /// Returns the public key for which the [`QuadraticVotingBallot`]s are encrypted.
79    pub fn receiver(&self) -> &PublicKey<G> {
80        &self.receiver
81    }
82
83    /// Returns the number of options.
84    pub fn options_count(&self) -> usize {
85        self.options_count
86    }
87
88    /// Returns the number of credits per ballot.
89    pub fn credits(&self) -> u64 {
90        self.credit_range.decomposition().upper_bound() - 1
91    }
92
93    /// Returns the maximum number of votes per option.
94    pub fn max_votes(&self) -> u64 {
95        self.vote_count_range.decomposition().upper_bound() - 1
96    }
97
98    /// Sets the maximum number of votes per option.
99    ///
100    /// # Panics
101    ///
102    /// Panics if `max_votes * max_votes` exceeds `credits`; in this case, this number of votes
103    /// cannot be cast for a single option.
104    pub fn set_max_votes(&mut self, max_votes: u64) {
105        assert!(
106            max_votes * max_votes <= self.credits(),
107            "Vote bound {max_votes} is too large; its square is greater than credit bound {}",
108            self.credits()
109        );
110        self.vote_count_range = RangeDecomposition::optimal(max_votes + 1).into();
111    }
112
113    fn check_options_count(&self, actual_count: usize) -> Result<(), QuadraticVotingError> {
114        if self.options_count == actual_count {
115            Ok(())
116        } else {
117            Err(QuadraticVotingError::OptionsLenMismatch {
118                expected: self.options_count,
119                actual: actual_count,
120            })
121        }
122    }
123}
124
125/// Integer square root of a `u64` number. Uses the digit-by-digit calculation method in base 2;
126/// see https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2)
127fn isqrt(mut x: u64) -> u64 {
128    let mut root = 0_u64;
129    let mut power_of_4 = 1_u64 << 62;
130    while power_of_4 > x {
131        power_of_4 /= 4;
132    }
133    while power_of_4 > 0 {
134        if x >= root + power_of_4 {
135            x -= root + power_of_4;
136            root = root / 2 + power_of_4;
137        } else {
138            root /= 2;
139        }
140        power_of_4 /= 4;
141    }
142    root
143}
144
145/// Encrypted ballot for [quadratic voting] together with zero-knowledge proofs of correctness.
146///
147/// # Overview
148///
149/// Quadratic voting assumes a non-exclusive selection among `n >= 1` predefined options.
150/// Unlike with [`MultiChoice`](crate::app::MultiChoice) polling, a voter can cast more than
151/// one vote for a single option. The additional votes come at a quadratic expense for the voter,
152/// however. For example, to cast 4 votes for a certain option, a voter needs 16 credits,
153/// while single votes for 4 different options are worth 4 credits.
154///
155/// The `QuadraticVotingBallot` construction assumes that there is a known number of credits
156/// for each ballot (e.g., it is uniform across all eligible voters), and that votes are tallied
157/// by a tallier or a federation of talliers that jointly control a [`SecretKey`](crate::SecretKey).
158/// As such, the ballot is represented as follows:
159///
160/// - ElGamal [`Ciphertext`] for each of `n` options (can be summed across all valid ballots
161///   to get vote totals that will be decrypted by the talliers)
162/// - [`RangeProof`] for each of these ciphertexts proving that the encrypted value
163///   is in range `0..=V`
164/// - [`Ciphertext`] for the number of credits used by the ballot, and a [`RangeProof`]
165///   that it is in range `0..=C`
166/// - Zero-knowledge [`SumOfSquaresProof`] proving that the encrypted number of credits is computed
167///   correctly, i.e., as a sum of squares of the values encrypted in the vote ciphertexts.
168///
169/// Here, `C` (the number of credits) and `V` (max votes per option) are the protocol parameters
170/// encapsulated in [`QuadraticVotingParams`].
171///
172/// [quadratic voting]: https://en.wikipedia.org/wiki/Quadratic_voting
173///
174/// # Examples
175///
176/// ```
177/// # use elastic_elgamal::{
178/// #     app::{QuadraticVotingParams, QuadraticVotingBallot}, group::Ristretto, Keypair,
179/// #     DiscreteLogTable,
180/// # };
181/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
182/// let mut rng = rand::rng();
183/// let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
184/// let params = QuadraticVotingParams::new(pk, 5, 20);
185/// // 5 options, 20 credits (= 4 max votes per option)
186/// assert_eq!(params.max_votes(), 4);
187///
188/// let votes = [4, 0, 0, 1, 1];
189/// let ballot = QuadraticVotingBallot::new(&params, &votes, &mut rng);
190/// let encrypted: Vec<_> = ballot.verify(&params)?.collect();
191///
192/// assert_eq!(encrypted.len(), 5);
193/// let lookup = DiscreteLogTable::new(0..=params.max_votes());
194/// let decrypted: Vec<_> = encrypted
195///     .into_iter()
196///     .map(|vote| sk.decrypt(vote, &lookup).unwrap())
197///     .collect();
198/// assert_eq!(decrypted, votes);
199/// # Ok(())
200/// # }
201/// ```
202#[derive(Debug, Clone)]
203#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
204#[cfg_attr(feature = "serde", serde(bound = ""))]
205pub struct QuadraticVotingBallot<G: Group> {
206    votes: Vec<CiphertextWithRangeProof<G>>,
207    credit: CiphertextWithRangeProof<G>,
208    credit_equivalence_proof: SumOfSquaresProof<G>,
209}
210
211#[derive(Debug, Clone)]
212#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
213#[cfg_attr(feature = "serde", serde(bound = ""))]
214struct CiphertextWithRangeProof<G: Group> {
215    ciphertext: Ciphertext<G>,
216    range_proof: RangeProof<G>,
217}
218
219impl<G: Group> CiphertextWithRangeProof<G> {
220    fn new(ciphertext: Ciphertext<G>, range_proof: RangeProof<G>) -> Self {
221        Self {
222            ciphertext,
223            range_proof,
224        }
225    }
226}
227
228impl<G: Group> QuadraticVotingBallot<G> {
229    /// Creates a ballot based on the provided parameters and voter's `votes`.
230    ///
231    /// # Panics
232    ///
233    /// Panics if the length of `votes` differs from the number of options in `params`.
234    pub fn new<R: CryptoRng + RngCore>(
235        params: &QuadraticVotingParams<G>,
236        votes: &[u64],
237        rng: &mut R,
238    ) -> Self {
239        assert_eq!(
240            votes.len(),
241            params.options_count,
242            "Mismatch between expected and actual number of choices"
243        );
244        let credit = votes.iter().map(|&x| x * x).sum::<u64>();
245
246        let votes: Vec<_> = votes
247            .iter()
248            .map(|&vote_count| {
249                let (ciphertext, proof) = RangeProof::new(
250                    &params.receiver,
251                    &params.vote_count_range,
252                    vote_count,
253                    &mut Transcript::new(b"quadratic_voting_variant"),
254                    rng,
255                );
256                (ciphertext.generalize(), proof)
257            })
258            .collect();
259        let (credit, credit_range_proof) = RangeProof::new(
260            &params.receiver,
261            &params.credit_range,
262            credit,
263            &mut Transcript::new(b"quadratic_voting_credit_range"),
264            rng,
265        );
266        let credit = credit.generalize();
267
268        let credit_equivalence_proof = SumOfSquaresProof::new(
269            votes.iter().map(|(ciphertext, _)| ciphertext),
270            &credit,
271            &params.receiver,
272            &mut Transcript::new(b"quadratic_voting_credit_equiv"),
273            rng,
274        );
275
276        Self {
277            votes: votes
278                .into_iter()
279                .map(|(ciphertext, proof)| CiphertextWithRangeProof::new(ciphertext.into(), proof))
280                .collect(),
281            credit: CiphertextWithRangeProof::new(credit.into(), credit_range_proof),
282            credit_equivalence_proof,
283        }
284    }
285
286    /// Verifies this ballot against the provided parameters.
287    ///
288    /// # Errors
289    ///
290    /// - Returns an error if verification fails.
291    pub fn verify(
292        &self,
293        params: &QuadraticVotingParams<G>,
294    ) -> Result<impl Iterator<Item = Ciphertext<G>> + '_, QuadraticVotingError> {
295        params.check_options_count(self.votes.len())?;
296
297        for (i, vote_count) in self.votes.iter().enumerate() {
298            vote_count
299                .range_proof
300                .verify(
301                    &params.receiver,
302                    &params.vote_count_range,
303                    vote_count.ciphertext,
304                    &mut Transcript::new(b"quadratic_voting_variant"),
305                )
306                .map_err(|error| QuadraticVotingError::Variant { index: i, error })?;
307        }
308
309        self.credit
310            .range_proof
311            .verify(
312                &params.receiver,
313                &params.credit_range,
314                self.credit.ciphertext,
315                &mut Transcript::new(b"quadratic_voting_credit_range"),
316            )
317            .map_err(QuadraticVotingError::CreditRange)?;
318
319        self.credit_equivalence_proof
320            .verify(
321                self.votes.iter().map(|c| &c.ciphertext),
322                &self.credit.ciphertext,
323                &params.receiver,
324                &mut Transcript::new(b"quadratic_voting_credit_equiv"),
325            )
326            .map_err(QuadraticVotingError::CreditEquivalence)?;
327
328        Ok(self.votes.iter().map(|c| c.ciphertext))
329    }
330}
331
332/// Errors that can occur when verifying [`QuadraticVotingBallot`]s.
333#[derive(Debug)]
334#[non_exhaustive]
335pub enum QuadraticVotingError {
336    /// Error verifying a [`RangeProof`] for a vote for a particular option.
337    Variant {
338        /// Zero-based option index.
339        index: usize,
340        /// Error that occurred during range proof verification.
341        error: VerificationError,
342    },
343    /// Error verifying a [`RangeProof`] for credits.
344    CreditRange(VerificationError),
345    /// Error verifying the [proof of equivalence](SumOfSquaresProof) for credits.
346    CreditEquivalence(VerificationError),
347    /// Mismatch between expected and actual number of options in the ballot.
348    OptionsLenMismatch {
349        /// Expected number of options.
350        expected: usize,
351        /// Actual number of options.
352        actual: usize,
353    },
354}
355
356impl fmt::Display for QuadraticVotingError {
357    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
358        match self {
359            Self::Variant { index, error } => write!(
360                formatter,
361                "error verifying range proof for option #{}: {error}",
362                *index + 1
363            ),
364            Self::CreditRange(err) => {
365                write!(formatter, "error verifying range proof for credits: {err}")
366            }
367            Self::CreditEquivalence(err) => {
368                write!(formatter, "error verifying credit equivalence proof: {err}")
369            }
370            Self::OptionsLenMismatch { expected, actual } => write!(
371                formatter,
372                "number of options in the ballot ({actual}) differs from expected ({expected})"
373            ),
374        }
375    }
376}
377
378#[cfg(feature = "std")]
379impl std::error::Error for QuadraticVotingError {
380    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
381        match self {
382            Self::Variant { error, .. }
383            | Self::CreditRange(error)
384            | Self::CreditEquivalence(error) => Some(error),
385            _ => None,
386        }
387    }
388}
389
390#[cfg(test)]
391mod tests {
392    use super::*;
393    use crate::{
394        DiscreteLogTable, Keypair,
395        group::{ElementOps, Ristretto},
396    };
397
398    #[test]
399    fn isqrt_is_correct() {
400        let samples = (0..1_000).chain((0..1_000).map(|x| x * 1_000)).chain([
401            u64::MAX,
402            u64::MAX - 1,
403            1 << 63,
404            1 << 62,
405            (1 << 62) - 1,
406        ]);
407        for sample in samples {
408            let sqrt = isqrt(sample);
409            assert!(sqrt * sqrt <= sample, "sqrt({sample}) ?= {sqrt}");
410
411            let next_square = (sqrt + 1).checked_mul(sqrt + 1);
412            assert!(
413                next_square.is_none_or(|sq| sq > sample),
414                "sqrt({sample}) ?= {sqrt}"
415            );
416        }
417    }
418
419    #[test]
420    fn quadratic_voting() {
421        let mut rng = rand::rng();
422        let (pk, sk) = Keypair::generate(&mut rng).into_tuple();
423        let params = QuadraticVotingParams::<Ristretto>::new(pk, 5, 25);
424        let ballot = QuadraticVotingBallot::new(&params, &[1, 3, 0, 3, 2], &mut rng);
425
426        let choices = ballot.verify(&params).unwrap();
427        let lookup_table = DiscreteLogTable::new(0..=5);
428        let choices: Vec<_> = choices
429            .map(|c| sk.decrypt(c, &lookup_table).unwrap())
430            .collect();
431        assert_eq!(choices, [1, 3, 0, 3, 2]);
432
433        {
434            let mut bogus_ballot = ballot.clone();
435            bogus_ballot.votes[0].ciphertext.blinded_element += Ristretto::generator();
436            let err = bogus_ballot.verify(&params).map(drop).unwrap_err();
437            assert!(matches!(
438                err,
439                QuadraticVotingError::Variant {
440                    index: 0,
441                    error: VerificationError::ChallengeMismatch
442                }
443            ));
444        }
445
446        {
447            let mut bogus_ballot = ballot.clone();
448            bogus_ballot.credit.ciphertext.blinded_element -= Ristretto::generator();
449            let err = bogus_ballot.verify(&params).map(drop).unwrap_err();
450            assert!(matches!(err, QuadraticVotingError::CreditRange(_)));
451        }
452
453        let mut bogus_ballot = ballot.clone();
454        let (ciphertext, proof) = RangeProof::new(
455            &params.receiver,
456            &params.vote_count_range,
457            3, // << overly large
458            &mut Transcript::new(b"quadratic_voting_variant"),
459            &mut rng,
460        );
461        bogus_ballot.votes[0] = CiphertextWithRangeProof::new(ciphertext.into(), proof);
462
463        let err = bogus_ballot.verify(&params).map(drop).unwrap_err();
464        assert!(matches!(err, QuadraticVotingError::CreditEquivalence(_)));
465    }
466}
elastic_elgamal/app/quadratic_voting.rs

elastic_elgamal/app/
quadratic_voting.rs
