cuprate_dandelion_tower/
config.rs

1use std::{
2    ops::{Mul, Neg},
3    time::Duration,
4};
5
6/// When calculating the embargo timeout using the formula: `(-k*(k-1)*hop)/(2*log(1-ep))`
7///
8/// (1 - ep) is the probability that a transaction travels for `k` hops before a nodes embargo timeout fires, this constant is (1 - ep).
9const EMBARGO_FULL_TRAVEL_PROBABILITY: f64 = 0.90;
10
11/// The graph type to use for dandelion routing, the dandelion paper recommends [`Graph::FourRegular`].
12///
13/// The decision between line graphs and 4-regular graphs depend on the priorities of the system, if
14/// linkability of transactions is a first order concern then line graphs may be better, however 4-regular graphs
15/// can give constant-order privacy benefits against adversaries with knowledge of the graph.
16///
17/// See appendix C of the dandelion++ paper.
18#[derive(Default, Debug, Copy, Clone)]
19pub enum Graph {
20    /// Line graph.
21    ///
22    /// When this is selected one peer will be chosen from the outbound peers each epoch to route transactions
23    /// to.
24    ///
25    /// In general this is not recommend over [`Graph::FourRegular`] but may be better for certain systems.
26    Line,
27    /// Quasi-4-Regular.
28    ///
29    /// When this is selected two peers will be chosen from the outbound peers each epoch, each stem transaction
30    /// received will then be sent to one of these two peers. Transactions from the same node will always go to the
31    /// same peer.
32    #[default]
33    FourRegular,
34}
35
36/// The config used to initialize dandelion.
37///
38/// One notable missing item from the config is `Tbase` AKA the timeout parameter to prevent black hole
39/// attacks. This is removed from the config for simplicity, `Tbase` is calculated using the formula provided
40/// in the D++ paper:
41///
42///  `(-k*(k-1)*hop)/(2*log(1-ep))`
43///
44/// Where `k` is calculated from the fluff probability, `hop` is `time_between_hop` and `ep` is fixed at `0.1`.
45#[derive(Debug, Clone, Copy)]
46pub struct DandelionConfig {
47    /// The time it takes for a stem transaction to pass through a node, including network latency.
48    ///
49    /// It's better to be safe and put a slightly higher value than lower.
50    pub time_between_hop: Duration,
51    /// The duration of an epoch.
52    pub epoch_duration: Duration,
53    /// `q` in the dandelion paper, this is the probability that a node will be in the fluff state for
54    /// a certain epoch.
55    ///
56    /// The dandelion paper recommends to make this value small, but the smaller this value, the higher
57    /// the broadcast latency.
58    ///
59    /// It is recommended for this value to be <= `0.2`, this value *MUST* be in range `0.0..=1.0`.
60    pub fluff_probability: f64,
61    /// The graph type.
62    pub graph: Graph,
63}
64
65impl DandelionConfig {
66    /// Returns the number of outbound peers to use to stem transactions.
67    ///
68    /// This value depends on the [`Graph`] chosen.
69    pub const fn number_of_stems(&self) -> usize {
70        match self.graph {
71            Graph::Line => 1,
72            Graph::FourRegular => 2,
73        }
74    }
75
76    /// Returns the average embargo timeout, `Tbase` in the dandelion++ paper.
77    ///
78    /// This is the average embargo timeout _only including this node_ with `k` nodes also putting an embargo timeout
79    /// using the exponential distribution, the average until one of them fluffs is `Tbase / k`.
80    pub fn average_embargo_timeout(&self) -> Duration {
81        // we set k equal to the expected stem length with this fluff probability.
82        let k = self.expected_stem_length();
83        let time_between_hop = self.time_between_hop.as_secs_f64();
84
85        Duration::from_secs_f64(
86            // (-k*(k-1)*hop)/(2*ln(1-ep))
87            ((k.neg() * (k - 1.0) * time_between_hop)
88                / EMBARGO_FULL_TRAVEL_PROBABILITY.ln().mul(2.0))
89            .ceil(),
90        )
91    }
92
93    /// Returns the expected length of a stem.
94    pub const fn expected_stem_length(&self) -> f64 {
95        self.fluff_probability.recip()
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use std::{
102        f64::consts::E,
103        ops::{Mul, Neg},
104        time::Duration,
105    };
106
107    use proptest::{prop_assert, proptest};
108
109    use super::*;
110
111    #[test]
112    fn monerod_average_embargo_timeout() {
113        let cfg = DandelionConfig {
114            time_between_hop: Duration::from_millis(175),
115            epoch_duration: Default::default(),
116            fluff_probability: 0.125,
117            graph: Default::default(),
118        };
119
120        assert_eq!(cfg.average_embargo_timeout(), Duration::from_secs(47));
121    }
122
123    proptest! {
124        #[test]
125        fn embargo_full_travel_probablity_correct(time_between_hop in 1_u64..1_000_000, fluff_probability in 0.000001..1.0) {
126            let cfg = DandelionConfig {
127                time_between_hop: Duration::from_millis(time_between_hop),
128                epoch_duration: Default::default(),
129                fluff_probability,
130                graph: Default::default(),
131            };
132
133            // assert that the `average_embargo_timeout` is high enough that the probability of `k` nodes
134            // not diffusing before expected diffusion is greater than or equal to `EMBARGO_FULL_TRAVEL_PROBABLY`
135            //
136            // using the formula from in appendix B.5
137            let k = cfg.expected_stem_length();
138            let time_between_hop = cfg.time_between_hop.as_secs_f64();
139
140            let average_embargo_timeout = cfg.average_embargo_timeout().as_secs_f64();
141
142            let probability =
143                E.powf((k.neg() * (k - 1.0) * time_between_hop) / average_embargo_timeout.mul(2.0));
144
145            prop_assert!(probability >= EMBARGO_FULL_TRAVEL_PROBABILITY, "probability = {probability}, average_embargo_timeout = {average_embargo_timeout}");
146        }
147    }
148}
cuprate_dandelion_tower/config.rs

cuprate_dandelion_tower/
config.rs
