w3f_plonk_common/
cond_select.rs

1//! Constant-time handling of secret witness bits (the prover's ring
2//! position and the blinding scalar bits). The secret bit is wrapped
3//! into a `subtle::Choice` (an optimization barrier) on entry and
4//! selection is limb-wise on the raw Montgomery representation, so no
5//! field arithmetic -- and none of arkworks' data-dependent conditional
6//! reductions -- ever touches the bits. Defense in depth, not a complete
7//! countermeasure: the unconditional point additions run variable-time
8//! arkworks field arithmetic on secret-derived accumulator values, and
9//! the column FFTs and polynomial commitment MSMs downstream still
10//! process the witness in variable time.
11
12use ark_ec::short_weierstrass::{Projective as SwProjective, SWCurveConfig};
13use ark_ec::twisted_edwards::{Projective as TeProjective, TECurveConfig};
14use ark_ff::{BigInt, Field, Fp, FpConfig};
15use ark_std::marker::PhantomData;
16use subtle::ConditionallySelectable;
17
18pub use subtle::Choice;
19
20/// Conversion into [`Choice`]. The `bool` impl applies subtle's
21/// optimization barrier, preventing the compiler from branching on the
22/// bit later. (`From<bool> for Choice` does not exist upstream, hence
23/// this local trait.)
24pub trait IntoChoice {
25    fn into_choice(self) -> Choice;
26}
27
28impl IntoChoice for Choice {
29    fn into_choice(self) -> Choice {
30        self
31    }
32}
33
34impl IntoChoice for bool {
35    fn into_choice(self) -> Choice {
36        Choice::from(self as u8)
37    }
38}
39
40/// Lifts a bit to a field element without branching on its value.
41pub fn bit_to_field<F: Field + CondSelect>(bit: bool) -> F {
42    F::select(bit, &F::one(), &F::zero())
43}
44
45/// Constant-time two-way select.
46pub trait CondSelect: Sized {
47    fn select(bit: impl IntoChoice, if_true: &Self, if_false: &Self) -> Self;
48}
49
50impl<P: FpConfig<N>, const N: usize> CondSelect for Fp<P, N> {
51    fn select(bit: impl IntoChoice, if_true: &Self, if_false: &Self) -> Self {
52        let limbs =
53            <[u64; N]>::conditional_select(&if_false.0 .0, &if_true.0 .0, bit.into_choice());
54        Fp(BigInt(limbs), PhantomData)
55    }
56}
57
58impl<C: TECurveConfig> CondSelect for TeProjective<C>
59where
60    C::BaseField: CondSelect,
61{
62    fn select(bit: impl IntoChoice, if_true: &Self, if_false: &Self) -> Self {
63        let choice = bit.into_choice();
64        Self::new_unchecked(
65            CondSelect::select(choice, &if_true.x, &if_false.x),
66            CondSelect::select(choice, &if_true.y, &if_false.y),
67            CondSelect::select(choice, &if_true.t, &if_false.t),
68            CondSelect::select(choice, &if_true.z, &if_false.z),
69        )
70    }
71}
72
73impl<C: SWCurveConfig> CondSelect for SwProjective<C>
74where
75    C::BaseField: CondSelect,
76{
77    fn select(bit: impl IntoChoice, if_true: &Self, if_false: &Self) -> Self {
78        let choice = bit.into_choice();
79        Self::new_unchecked(
80            CondSelect::select(choice, &if_true.x, &if_false.x),
81            CondSelect::select(choice, &if_true.y, &if_false.y),
82            CondSelect::select(choice, &if_true.z, &if_false.z),
83        )
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90    use ark_ed_on_bls12_381_bandersnatch::{EdwardsProjective, Fq};
91    use ark_std::{test_rng, UniformRand};
92
93    #[test]
94    fn bit_lift_is_exact() {
95        assert_eq!(bit_to_field::<Fq>(false), Fq::from(0));
96        assert_eq!(bit_to_field::<Fq>(true), Fq::from(1));
97    }
98
99    // The selected values feed committed columns, so they are
100    // consensus-critical: the select must return the operand bit for bit,
101    // not merely an equivalent representation.
102    #[test]
103    fn select_returns_exact_operand() {
104        let rng = &mut test_rng();
105        let a = Fq::rand(rng);
106        let b = Fq::rand(rng);
107        assert_eq!(Fq::select(true, &a, &b), a);
108        assert_eq!(Fq::select(false, &a, &b), b);
109
110        let p = EdwardsProjective::rand(rng);
111        let q = EdwardsProjective::rand(rng);
112        let s = EdwardsProjective::select(true, &p, &q);
113        assert_eq!((s.x, s.y, s.t, s.z), (p.x, p.y, p.t, p.z));
114        let s = EdwardsProjective::select(false, &p, &q);
115        assert_eq!((s.x, s.y, s.t, s.z), (q.x, q.y, q.t, q.z));
116    }
117}
w3f_plonk_common/cond_select.rs

w3f_plonk_common/
cond_select.rs
