durs_wot/
lib.rs

1//  Copyright (C) 2017-2019  The AXIOM TEAM Association.
2//
3// This program is free software: you can redistribute it and/or modify
4// it under the terms of the GNU Affero General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful,
9// but WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11// GNU Affero General Public License for more details.
12//
13// You should have received a copy of the GNU Affero General Public License
14// along with this program.  If not, see <https://www.gnu.org/licenses/>.
15
16//! `wot` is a crate making "Web of Trust" computations for
17//! the [Duniter] project.
18//!
19//! [Duniter]: https://duniter.org/
20//!
21//! It defines a trait representing a Web of Trust and allow to do calculations on it.
22//!
23//! It also contains an "legacy" implementation translated from the original C++ code.
24//!
25//! Web of Trust tests are translated from [duniter/wot Javascript test][js-tests].
26//!
27//! [js-tests]: https://github.com/duniter/wot/blob/master/wotcpp/webOfTrust.cpp
28
29#![deny(
30    clippy::option_unwrap_used,
31    clippy::result_unwrap_used,
32    missing_docs,
33    missing_debug_implementations,
34    missing_copy_implementations,
35    trivial_casts,
36    trivial_numeric_casts,
37    unsafe_code,
38    unstable_features,
39    unused_import_braces,
40    unused_qualifications
41)]
42
43pub mod data;
44pub mod operations;
45
46pub use crate::data::{WebOfTrust, WotId};
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51    use crate::data::*;
52    use crate::operations::centrality::*;
53    use crate::operations::distance::*;
54    use crate::operations::path::*;
55    use std::path::Path;
56
57    /// Test translated from https://github.com/duniter/wot/blob/master/tests/test.js
58    ///
59    /// Clone and file tests are not included in this generic test and should be done in
60    /// the implementation test.
61    #[allow(clippy::cognitive_complexity)]
62    pub fn generic_wot_test<W>()
63    where
64        W: WebOfTrust + Sync,
65    {
66        let centralities_calculator = UlrikBrandesCentralityCalculator {};
67        let distance_calculator = RustyDistanceCalculator {};
68        let path_finder = RustyPathFinder {};
69        let mut wot = W::new(3);
70
71        // should have an initial size of 0
72        assert_eq!(wot.size(), 0);
73
74        // should return `None()` if testing `is_enabled()` with out-of-bounds node
75        assert_eq!(wot.is_enabled(WotId(0)), None);
76        assert_eq!(wot.is_enabled(WotId(23)), None);
77
78        // should give nomber 0 if we add a node
79        // - add a node
80        assert_eq!(wot.add_node(), WotId(0));
81        assert_eq!(wot.size(), 1);
82        assert_eq!(wot.get_disabled().len(), 0);
83
84        // - add another
85        assert_eq!(wot.add_node(), WotId(1));
86        assert_eq!(wot.size(), 2);
87        assert_eq!(wot.get_disabled().len(), 0);
88
89        // - add 10 nodes
90        for i in 0..10 {
91            assert_eq!(wot.add_node(), WotId(i + 2));
92        }
93
94        assert_eq!(wot.size(), 12);
95
96        // shouldn't be able to self cert
97        assert_eq!(
98            wot.add_link(WotId(0), WotId(0)),
99            NewLinkResult::SelfLinkingForbidden()
100        );
101
102        // should add certs only in the boundaries of max_cert
103        assert_eq!(wot.add_link(WotId(0), WotId(1)), NewLinkResult::Ok(1));
104        assert_eq!(wot.add_link(WotId(0), WotId(2)), NewLinkResult::Ok(1));
105        assert_eq!(wot.add_link(WotId(0), WotId(3)), NewLinkResult::Ok(1));
106        assert_eq!(
107            wot.add_link(WotId(0), WotId(4)),
108            NewLinkResult::AllCertificationsUsed(0)
109        );
110
111        assert_eq!(wot.get_max_link(), 3);
112        assert_eq!(wot.has_link(WotId(0), WotId(1)), HasLinkResult::Link(true));
113        assert_eq!(wot.has_link(WotId(0), WotId(2)), HasLinkResult::Link(true));
114        assert_eq!(wot.has_link(WotId(0), WotId(3)), HasLinkResult::Link(true));
115        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(false));
116
117        wot.set_max_link(4);
118        assert_eq!(wot.get_max_link(), 4);
119        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(false));
120        wot.add_link(WotId(0), WotId(4));
121        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(true));
122        wot.rem_link(WotId(0), WotId(1));
123        wot.rem_link(WotId(0), WotId(2));
124        wot.rem_link(WotId(0), WotId(3));
125        wot.rem_link(WotId(0), WotId(4));
126
127        // false when not linked + test out of bounds
128        assert_eq!(wot.has_link(WotId(0), WotId(6)), HasLinkResult::Link(false));
129        assert_eq!(
130            wot.has_link(WotId(23), WotId(0)),
131            HasLinkResult::UnknownSource()
132        );
133        assert_eq!(
134            wot.has_link(WotId(2), WotId(53)),
135            HasLinkResult::UnknownTarget()
136        );
137
138        // created nodes should be enabled
139        assert_eq!(wot.is_enabled(WotId(0)), Some(true));
140        assert_eq!(wot.is_enabled(WotId(1)), Some(true));
141        assert_eq!(wot.is_enabled(WotId(2)), Some(true));
142        assert_eq!(wot.is_enabled(WotId(3)), Some(true));
143        assert_eq!(wot.is_enabled(WotId(11)), Some(true));
144
145        // should be able to disable some nodes
146        assert_eq!(wot.set_enabled(WotId(0), false), Some(false));
147        assert_eq!(wot.set_enabled(WotId(1), false), Some(false));
148        assert_eq!(wot.set_enabled(WotId(2), false), Some(false));
149        assert_eq!(wot.get_disabled().len(), 3);
150        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
151
152        // node 0 and 2 should be disabled
153        assert_eq!(wot.is_enabled(WotId(0)), Some(false));
154        assert_eq!(wot.is_enabled(WotId(1)), Some(true));
155        assert_eq!(wot.is_enabled(WotId(2)), Some(false));
156        assert_eq!(wot.is_enabled(WotId(3)), Some(true));
157        // - set enabled again
158        assert_eq!(wot.set_enabled(WotId(0), true), Some(true));
159        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
160        assert_eq!(wot.set_enabled(WotId(2), true), Some(true));
161        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
162        assert_eq!(wot.get_disabled().len(), 0);
163
164        // should not exist a link from 2 to 0
165        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(false));
166
167        // should be able to add some links, cert count is returned
168        assert_eq!(wot.add_link(WotId(2), WotId(0)), NewLinkResult::Ok(1));
169        assert_eq!(wot.add_link(WotId(4), WotId(0)), NewLinkResult::Ok(2));
170        assert_eq!(wot.add_link(WotId(5), WotId(0)), NewLinkResult::Ok(3));
171
172        // should exist new links
173        /* WoT is:
174         *
175         * 2 --> 0
176         * 4 --> 0
177         * 5 --> 0
178         */
179
180        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(true));
181        assert_eq!(wot.has_link(WotId(4), WotId(0)), HasLinkResult::Link(true));
182        assert_eq!(wot.has_link(WotId(5), WotId(0)), HasLinkResult::Link(true));
183        assert_eq!(wot.has_link(WotId(2), WotId(1)), HasLinkResult::Link(false));
184
185        // should be able to remove some links
186        assert_eq!(wot.rem_link(WotId(4), WotId(0)), RemLinkResult::Removed(2));
187        /*
188         * WoT is now:
189         *
190         * 2 --> 0
191         * 5 --> 0
192         */
193
194        // should exist less links
195        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(true));
196        assert_eq!(wot.has_link(WotId(4), WotId(0)), HasLinkResult::Link(false));
197        assert_eq!(wot.has_link(WotId(5), WotId(0)), HasLinkResult::Link(true));
198        assert_eq!(wot.has_link(WotId(2), WotId(1)), HasLinkResult::Link(false));
199
200        // should successfully use distance rule
201        assert_eq!(
202            distance_calculator.is_outdistanced(
203                &wot,
204                WotDistanceParameters {
205                    node: WotId(0),
206                    sentry_requirement: 1,
207                    step_max: 1,
208                    x_percent: 1.0,
209                },
210            ),
211            Some(false)
212        );
213        // => no because 2,4,5 have certified him
214        assert_eq!(
215            distance_calculator.is_outdistanced(
216                &wot,
217                WotDistanceParameters {
218                    node: WotId(0),
219                    sentry_requirement: 2,
220                    step_max: 1,
221                    x_percent: 1.0,
222                },
223            ),
224            Some(false)
225        );
226        // => no because only member 2 has 2 certs, and has certified him
227        assert_eq!(
228            distance_calculator.is_outdistanced(
229                &wot,
230                WotDistanceParameters {
231                    node: WotId(0),
232                    sentry_requirement: 3,
233                    step_max: 1,
234                    x_percent: 1.0,
235                },
236            ),
237            Some(false)
238        );
239        // => no because no member has issued 3 certifications
240
241        // - we add links from member 3
242        assert_eq!(wot.add_link(WotId(3), WotId(1)), NewLinkResult::Ok(1));
243        assert_eq!(wot.add_link(WotId(3), WotId(2)), NewLinkResult::Ok(1));
244        /*
245         * WoT is now:
246         *
247         * 2 --> 0
248         * 5 --> 0
249         * 3 --> 1
250         * 3 --> 2
251         */
252        assert_eq!(wot.size(), 12);
253        assert_eq!(wot.get_sentries(1).len(), 1);
254        assert_eq!(wot.get_sentries(1)[0], WotId(2));
255        assert_eq!(wot.get_sentries(2).len(), 0);
256        assert_eq!(wot.get_sentries(3).len(), 0);
257        assert_eq!(wot.get_non_sentries(1).len(), 11); // 12 - 1
258        assert_eq!(wot.get_non_sentries(2).len(), 12); // 12 - 0
259        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
260        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 1).len(), 0); // KO
261        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
262        assert!(path_finder
263            .find_paths(&wot, WotId(3), WotId(0), 2)
264            .contains(&vec![WotId(3), WotId(2), WotId(0)]));
265
266        assert_eq!(
267            distance_calculator.is_outdistanced(
268                &wot,
269                WotDistanceParameters {
270                    node: WotId(0),
271                    sentry_requirement: 1,
272                    step_max: 1,
273                    x_percent: 1.0,
274                },
275            ),
276            Some(false)
277        ); // OK : 2 -> 0
278        assert_eq!(
279            distance_calculator.is_outdistanced(
280                &wot,
281                WotDistanceParameters {
282                    node: WotId(0),
283                    sentry_requirement: 2,
284                    step_max: 1,
285                    x_percent: 1.0,
286                },
287            ),
288            Some(false)
289        ); // OK : 2 -> 0
290        assert_eq!(
291            distance_calculator.is_outdistanced(
292                &wot,
293                WotDistanceParameters {
294                    node: WotId(0),
295                    sentry_requirement: 3,
296                    step_max: 1,
297                    x_percent: 1.0,
298                },
299            ),
300            Some(false)
301        ); // OK : no stry \w 3 lnk
302        assert_eq!(
303            distance_calculator.is_outdistanced(
304                &wot,
305                WotDistanceParameters {
306                    node: WotId(0),
307                    sentry_requirement: 2,
308                    step_max: 2,
309                    x_percent: 1.0,
310                },
311            ),
312            Some(false)
313        ); // OK : 2 -> 0
314
315        wot.add_link(WotId(1), WotId(3));
316        wot.add_link(WotId(2), WotId(3));
317
318        assert_eq!(wot.size(), 12);
319        assert_eq!(wot.get_sentries(1).len(), 3);
320        assert_eq!(wot.get_sentries(1)[0], WotId(1));
321        assert_eq!(wot.get_sentries(1)[1], WotId(2));
322        assert_eq!(wot.get_sentries(1)[2], WotId(3));
323
324        assert_eq!(wot.get_sentries(2).len(), 1);
325        assert_eq!(wot.get_sentries(2)[0], WotId(3));
326        assert_eq!(wot.get_sentries(3).len(), 0);
327        assert_eq!(wot.get_non_sentries(1).len(), 9); // 12 - 3
328        assert_eq!(wot.get_non_sentries(2).len(), 11); // 12 - 1
329        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
330        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 1).len(), 0); // KO
331        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
332        assert!(path_finder
333            .find_paths(&wot, WotId(3), WotId(0), 2)
334            .contains(&vec![WotId(3), WotId(2), WotId(0)]));
335
336        assert_eq!(
337            distance_calculator.is_outdistanced(
338                &wot,
339                WotDistanceParameters {
340                    node: WotId(0),
341                    sentry_requirement: 1,
342                    step_max: 1,
343                    x_percent: 1.0,
344                },
345            ),
346            Some(true)
347        ); // KO : No path 3 -> 0
348        assert_eq!(
349            distance_calculator.is_outdistanced(
350                &wot,
351                WotDistanceParameters {
352                    node: WotId(0),
353                    sentry_requirement: 2,
354                    step_max: 1,
355                    x_percent: 1.0,
356                },
357            ),
358            Some(true)
359        ); // KO : No path 3 -> 0
360        assert_eq!(
361            distance_calculator.is_outdistanced(
362                &wot,
363                WotDistanceParameters {
364                    node: WotId(0),
365                    sentry_requirement: 3,
366                    step_max: 1,
367                    x_percent: 1.0,
368                },
369            ),
370            Some(false)
371        ); // OK : no stry \w 3 lnk
372        assert_eq!(
373            distance_calculator.is_outdistanced(
374                &wot,
375                WotDistanceParameters {
376                    node: WotId(0),
377                    sentry_requirement: 2,
378                    step_max: 2,
379                    x_percent: 1.0,
380                },
381            ),
382            Some(false)
383        ); // OK : 3 -> 2 -> 0
384
385        // should have 12 nodes
386        assert_eq!(wot.size(), 12);
387
388        // delete top node (return new top node id)
389        assert_eq!(wot.rem_node(), Some(WotId(10)));
390
391        // should have 11 nodes
392        assert_eq!(wot.size(), 11);
393
394        // should work with member 3 disabled
395        // - with member 3 disabled (non-member)
396        assert_eq!(wot.set_enabled(WotId(3), false), Some(false));
397        assert_eq!(wot.get_disabled().len(), 1);
398        assert_eq!(
399            distance_calculator.is_outdistanced(
400                &wot,
401                WotDistanceParameters {
402                    node: WotId(0),
403                    sentry_requirement: 2,
404                    step_max: 1,
405                    x_percent: 1.0,
406                },
407            ),
408            Some(false)
409        ); // OK : Disabled
410
411        // Write wot in file
412        durs_common_tools::fns::bin_file::write_bin_file(
413            Path::new("test.wot"),
414            &bincode::serialize(&wot).expect("fail to serialize wot"),
415        )
416        .expect("fail to write wot file");
417
418        let wot2_bin = durs_common_tools::fns::bin_file::read_bin_file(Path::new("test.wot"))
419            .expect("fail to read wot file");
420        let wot2: W = bincode::deserialize(&wot2_bin).expect("fail to deserialize wot");
421
422        // Read wot from file
423        {
424            assert_eq!(wot.size(), wot2.size());
425            assert_eq!(
426                wot.get_non_sentries(1).len(),
427                wot2.get_non_sentries(1).len()
428            );
429            assert_eq!(wot.get_disabled().len(), wot2.get_disabled().len());
430            assert_eq!(wot2.get_disabled().len(), 1);
431            assert_eq!(wot2.is_enabled(WotId(3)), Some(false));
432            assert_eq!(
433                distance_calculator.is_outdistanced(
434                    &wot2,
435                    WotDistanceParameters {
436                        node: WotId(0),
437                        sentry_requirement: 2,
438                        step_max: 1,
439                        x_percent: 1.0,
440                    },
441                ),
442                Some(false)
443            );
444        }
445
446        // Read g1_genesis wot
447        let wot3_bin =
448            durs_common_tools::fns::bin_file::read_bin_file(Path::new("tests/g1_genesis.bin"))
449                .expect("fail to read g1_genesis wot file");
450        let wot3: W = bincode::deserialize(&wot3_bin).expect("fail to deserialize g1_genesis wot");
451
452        // Check g1_genesis wot members_count
453        let members_count = wot3.get_enabled().len() as u64;
454        assert_eq!(members_count, 59);
455
456        // Test compute_distance in g1_genesis wot
457        assert_eq!(
458            distance_calculator.compute_distance(
459                &wot3,
460                WotDistanceParameters {
461                    node: WotId(37),
462                    sentry_requirement: 3,
463                    step_max: 5,
464                    x_percent: 0.8,
465                },
466            ),
467            Some(WotDistance {
468                sentries: 48,
469                success: 48,
470                success_at_border: 3,
471                reached: 51,
472                reached_at_border: 3,
473                outdistanced: false,
474            },)
475        );
476
477        // Test betweenness centralities computation in g1_genesis wot
478        let centralities = centralities_calculator.betweenness_centralities(&wot3);
479        assert_eq!(centralities.len(), 59);
480        assert_eq!(
481            centralities,
482            vec![
483                148, 30, 184, 11, 60, 51, 40, 115, 24, 140, 47, 69, 16, 34, 94, 126, 151, 0, 34,
484                133, 20, 103, 38, 144, 73, 523, 124, 23, 47, 17, 9, 64, 77, 281, 6, 105, 54, 0,
485                111, 21, 6, 2, 0, 1, 47, 59, 28, 236, 0, 0, 0, 0, 60, 6, 0, 1, 8, 33, 169,
486            ]
487        );
488
489        // Test stress centralities computation in g1_genesis wot
490        let stress_centralities = centralities_calculator.stress_centralities(&wot3);
491        assert_eq!(stress_centralities.len(), 59);
492        assert_eq!(
493            stress_centralities,
494            vec![
495                848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984,
496                0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276,
497                41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31,
498                0, 9, 55, 216, 865,
499            ]
500        );
501
502        // Test distance stress centralities computation in g1_genesis wot
503        let distance_stress_centralities =
504            centralities_calculator.distance_stress_centralities(&wot3, 5);
505        assert_eq!(distance_stress_centralities.len(), 59);
506        assert_eq!(
507            distance_stress_centralities,
508            vec![
509                848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984,
510                0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276,
511                41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31,
512                0, 9, 55, 216, 865,
513            ]
514        );
515    }
516}
durs_wot/lib.rs

durs_wot/
lib.rs
