penumbra_sdk_shielded_pool/
fmd.rs

1use anyhow::{anyhow, Result};
2use decaf377_fmd::Precision;
3use penumbra_sdk_proto::{
4    core::component::shielded_pool::v1::{self as pb},
5    DomainType,
6};
7use serde::{Deserialize, Serialize};
8
9pub mod state_key;
10
11/// How long users have to switch to updated parameters.
12pub const FMD_GRACE_PERIOD_BLOCKS_DEFAULT: u64 = 1 << 4;
13
14pub fn should_update_fmd_params(fmd_grace_period_blocks: u64, height: u64) -> bool {
15    height % fmd_grace_period_blocks == 0
16}
17
18#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
19#[serde(try_from = "pb::FmdParameters", into = "pb::FmdParameters")]
20pub struct Parameters {
21    /// FMD Precision.
22    pub precision: Precision,
23    /// The block height at which these parameters became effective.
24    pub as_of_block_height: u64,
25}
26
27impl DomainType for Parameters {
28    type Proto = pb::FmdParameters;
29}
30
31impl TryFrom<pb::FmdParameters> for Parameters {
32    type Error = anyhow::Error;
33
34    fn try_from(msg: pb::FmdParameters) -> Result<Self> {
35        Ok(Parameters {
36            precision: msg.precision_bits.try_into()?,
37            as_of_block_height: msg.as_of_block_height,
38        })
39    }
40}
41
42impl From<Parameters> for pb::FmdParameters {
43    fn from(params: Parameters) -> Self {
44        pb::FmdParameters {
45            precision_bits: params.precision.bits() as u32,
46            as_of_block_height: params.as_of_block_height,
47        }
48    }
49}
50
51impl Default for Parameters {
52    fn default() -> Self {
53        Self {
54            precision: Precision::default(),
55            as_of_block_height: 1,
56        }
57    }
58}
59
60/// A struct holding params for the sliding window algorithm
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub struct SlidingWindow {
63    window: u32,
64    targeted_detections_per_window: u32,
65}
66
67impl SlidingWindow {
68    pub fn updated_fmd_params(
69        &self,
70        old: &Parameters,
71        state: MetaParametersAlgorithmState,
72        height: u64,
73        clue_count_delta: (u64, u64),
74    ) -> (Parameters, MetaParametersAlgorithmState) {
75        // An edge case, which should act as a constant.
76        if self.window == 0 {
77            return (
78                old.clone(),
79                MetaParametersAlgorithmState::SlidingWindow {
80                    approximate_clue_count: 0,
81                },
82            );
83        }
84
85        let new_clues_in_period = clue_count_delta.1.saturating_sub(clue_count_delta.0);
86
87        let projected_clue_count = u64::from(self.window) * new_clues_in_period;
88        let old_approximate_clue_count = match state {
89            MetaParametersAlgorithmState::SlidingWindow {
90                approximate_clue_count,
91            } => approximate_clue_count,
92            _ => 0,
93        };
94        // ((w - 1) * old + new) / w, but using u64 for more precision, and saturating
95        let approximate_clue_count: u32 = u32::try_from(
96            (u64::from(old_approximate_clue_count)
97                .saturating_mul((self.window - 1).into())
98                .saturating_add(projected_clue_count))
99                / u64::from(self.window),
100        )
101        .unwrap_or(u32::MAX);
102
103        // 1 / this_number of transactions should be detected as false positives
104        let inverse_detection_ratio = approximate_clue_count
105            .checked_div(self.targeted_detections_per_window)
106            .unwrap_or(0);
107        // To receive the power of two *above* the targeted number of clues,
108        // take the base 2 logarithm, round down, and use 1 for 0 clues
109        let required_precision = if inverse_detection_ratio == 0 {
110            Precision::new(1u8).expect("1 is a valid precision")
111        } else {
112            let lg_inverse_ratio = 63 - inverse_detection_ratio.leading_zeros();
113            if lg_inverse_ratio > Precision::MAX.bits().into() {
114                Precision::MAX
115            } else {
116                Precision::new(lg_inverse_ratio as u8)
117                    .expect("unexpected precision overflow after check")
118            }
119        };
120        (
121            Parameters {
122                precision: required_precision,
123                as_of_block_height: height,
124            },
125            MetaParametersAlgorithmState::SlidingWindow {
126                approximate_clue_count,
127            },
128        )
129    }
130}
131
132#[derive(Clone, Copy, Debug, PartialEq, Eq)]
133pub enum MetaParametersAlgorithm {
134    /// Use a fixed precision forever.
135    Fixed(Precision),
136    /// Use a sliding window
137    SlidingWindow(SlidingWindow),
138}
139
140/// Meta parameters governing how FMD parameters change.
141#[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq, Eq)]
142#[serde(try_from = "pb::FmdMetaParameters", into = "pb::FmdMetaParameters")]
143pub struct MetaParameters {
144    pub fmd_grace_period_blocks: u64,
145    pub algorithm: MetaParametersAlgorithm,
146}
147
148impl TryFrom<pb::FmdMetaParameters> for MetaParameters {
149    type Error = anyhow::Error;
150
151    fn try_from(value: pb::FmdMetaParameters) -> Result<Self> {
152        let fmd_grace_period_blocks = value.fmd_grace_period_blocks;
153        let algorithm = match value
154            .algorithm
155            .ok_or(anyhow!("FmdMetaParameters missing algorithm"))?
156        {
157            pb::fmd_meta_parameters::Algorithm::FixedPrecisionBits(p) => {
158                MetaParametersAlgorithm::Fixed(Precision::new(p as u8)?)
159            }
160            pb::fmd_meta_parameters::Algorithm::SlidingWindow(x) => {
161                MetaParametersAlgorithm::SlidingWindow(SlidingWindow {
162                    window: x.window_update_periods,
163                    targeted_detections_per_window: x.targeted_detections_per_window,
164                })
165            }
166        };
167        Ok(MetaParameters {
168            fmd_grace_period_blocks,
169            algorithm,
170        })
171    }
172}
173
174impl From<MetaParameters> for pb::FmdMetaParameters {
175    fn from(value: MetaParameters) -> Self {
176        let algorithm = match value.algorithm {
177            MetaParametersAlgorithm::Fixed(p) => {
178                pb::fmd_meta_parameters::Algorithm::FixedPrecisionBits(p.bits().into())
179            }
180            MetaParametersAlgorithm::SlidingWindow(SlidingWindow {
181                window,
182                targeted_detections_per_window,
183            }) => pb::fmd_meta_parameters::Algorithm::SlidingWindow(
184                pb::fmd_meta_parameters::AlgorithmSlidingWindow {
185                    window_update_periods: window,
186                    targeted_detections_per_window,
187                },
188            ),
189        };
190        pb::FmdMetaParameters {
191            fmd_grace_period_blocks: value.fmd_grace_period_blocks,
192            algorithm: Some(algorithm),
193        }
194    }
195}
196
197impl DomainType for MetaParameters {
198    type Proto = pb::FmdMetaParameters;
199}
200
201impl Default for MetaParameters {
202    fn default() -> Self {
203        Self {
204            fmd_grace_period_blocks: FMD_GRACE_PERIOD_BLOCKS_DEFAULT,
205            algorithm: MetaParametersAlgorithm::Fixed(Precision::default()),
206        }
207    }
208}
209
210/// If any, the current state for the algorithm we're using.
211///
212/// This allows algorithms to hold arbitrary state. The algorithms need to be able
213/// to start from having no state and function appropriately, which allows for good
214/// backwards-compatability.
215#[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq, Eq)]
216#[serde(
217    try_from = "pb::FmdMetaParametersAlgorithmState",
218    into = "pb::FmdMetaParametersAlgorithmState"
219)]
220pub enum MetaParametersAlgorithmState {
221    /// A catch-all case to allow us to explicitly handle not having state
222    Nothing,
223    /// The state for the fixed algorithm
224    Fixed,
225    /// The state for the sliding window algorithm.
226    SlidingWindow {
227        /// The approximate number of clues in the previous window.
228        approximate_clue_count: u32,
229    },
230}
231
232impl TryFrom<pb::FmdMetaParametersAlgorithmState> for MetaParametersAlgorithmState {
233    type Error = anyhow::Error;
234
235    fn try_from(value: pb::FmdMetaParametersAlgorithmState) -> Result<Self> {
236        Ok(match value.state {
237            Some(pb::fmd_meta_parameters_algorithm_state::State::Fixed(_)) => Self::Fixed,
238            Some(pb::fmd_meta_parameters_algorithm_state::State::SlidingWindow(x)) => {
239                Self::SlidingWindow {
240                    approximate_clue_count: x.approximate_clue_count,
241                }
242            }
243            None => Self::Nothing,
244        })
245    }
246}
247
248impl From<MetaParametersAlgorithmState> for pb::FmdMetaParametersAlgorithmState {
249    fn from(value: MetaParametersAlgorithmState) -> Self {
250        let state = match value {
251            MetaParametersAlgorithmState::Nothing => None,
252            MetaParametersAlgorithmState::Fixed => {
253                Some(pb::fmd_meta_parameters_algorithm_state::State::Fixed(
254                    pb::fmd_meta_parameters_algorithm_state::FixedState {},
255                ))
256            }
257            MetaParametersAlgorithmState::SlidingWindow {
258                approximate_clue_count,
259            } => Some(
260                pb::fmd_meta_parameters_algorithm_state::State::SlidingWindow(
261                    pb::fmd_meta_parameters_algorithm_state::SlidingWindowState {
262                        approximate_clue_count,
263                    },
264                ),
265            ),
266        };
267        pb::FmdMetaParametersAlgorithmState { state }
268    }
269}
270
271impl DomainType for MetaParametersAlgorithmState {
272    type Proto = pb::FmdMetaParametersAlgorithmState;
273}
274
275impl Default for MetaParametersAlgorithmState {
276    fn default() -> Self {
277        Self::Nothing
278    }
279}
280
281impl MetaParameters {
282    pub fn updated_fmd_params(
283        &self,
284        old: &Parameters,
285        state: MetaParametersAlgorithmState,
286        height: u64,
287        clue_count_delta: (u64, u64),
288    ) -> (Parameters, MetaParametersAlgorithmState) {
289        if clue_count_delta.1 < clue_count_delta.0 {
290            tracing::warn!(
291                "decreasing clue count at height {}: {} then {}",
292                height,
293                clue_count_delta.0,
294                clue_count_delta.1
295            );
296        }
297        match self.algorithm {
298            MetaParametersAlgorithm::Fixed(precision) => (
299                Parameters {
300                    precision,
301                    as_of_block_height: height,
302                },
303                MetaParametersAlgorithmState::Fixed,
304            ),
305            MetaParametersAlgorithm::SlidingWindow(w) => {
306                w.updated_fmd_params(old, state, height, clue_count_delta)
307            }
308        }
309    }
310}
penumbra_sdk_shielded_pool/fmd.rs

penumbra_sdk_shielded_pool/
fmd.rs
