dubp_wot/
lib.rs

1//  Copyright (C) 2017-2020  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::unwrap_used,
31    missing_docs,
32    missing_debug_implementations,
33    missing_copy_implementations,
34    trivial_casts,
35    trivial_numeric_casts,
36    unsafe_code,
37    unstable_features,
38    unused_import_braces,
39    unused_qualifications
40)]
41
42pub mod data;
43pub mod operations;
44
45pub use crate::data::{WebOfTrust, WotId};
46
47use once_cell::sync::OnceCell;
48
49/// Main wot instance
50pub static MAIN_WOT: OnceCell<parking_lot::RwLock<data::rusty::RustyWebOfTrust>> = OnceCell::new();
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55    use crate::data::*;
56    use crate::operations::centrality::*;
57    use crate::operations::distance::*;
58    use crate::operations::path::*;
59    use std::{io::Read, io::Write, path::Path};
60
61    fn read_bin_file(file_path: &Path) -> Result<Vec<u8>, std::io::Error> {
62        let mut file = std::fs::File::open(file_path)?;
63        if file.metadata()?.len() == 0 {
64            Ok(vec![])
65        } else {
66            let mut bin_datas = Vec::new();
67            file.read_to_end(&mut bin_datas)?;
68
69            Ok(bin_datas)
70        }
71    }
72
73    fn write_bin_file(file_path: &Path, datas: &[u8]) -> Result<(), std::io::Error> {
74        let mut file = std::fs::File::create(file_path)?;
75        file.write_all(datas)?;
76
77        Ok(())
78    }
79
80    /// Test translated from https://github.com/duniter/wot/blob/master/tests/test.js
81    ///
82    /// Clone and file tests are not included in this generic test and should be done in
83    /// the implementation test.
84    #[allow(clippy::cognitive_complexity)]
85    pub fn generic_wot_test<W>()
86    where
87        W: WebOfTrust + Sync,
88    {
89        let centralities_calculator = UlrikBrandesCentralityCalculator {};
90        let distance_calculator = RustyDistanceCalculator {};
91        let path_finder = RustyPathFinder {};
92        let mut wot = W::new(3);
93
94        // should have an initial size of 0
95        assert_eq!(wot.size(), 0);
96
97        // should return `None()` if testing `is_enabled()` with out-of-bounds node
98        assert_eq!(wot.is_enabled(WotId(0)), None);
99        assert_eq!(wot.is_enabled(WotId(23)), None);
100
101        // should give nomber 0 if we add a node
102        // - add a node
103        assert_eq!(wot.add_node(), WotId(0));
104        assert_eq!(wot.size(), 1);
105        assert_eq!(wot.get_disabled().len(), 0);
106
107        // delete top node (return new top node id)
108        assert_eq!(wot.rem_node(), Some(WotId(0)));
109        assert_eq!(wot.size(), 0);
110
111        // readd node
112        assert_eq!(wot.add_node(), WotId(0));
113
114        // - add another
115        assert_eq!(wot.add_node(), WotId(1));
116        assert_eq!(wot.size(), 2);
117        assert_eq!(wot.get_disabled().len(), 0);
118
119        // - add 10 nodes
120        for i in 0..10 {
121            assert_eq!(wot.add_node(), WotId(i + 2));
122        }
123
124        assert_eq!(wot.size(), 12);
125
126        // shouldn't be able to self cert
127        assert_eq!(
128            wot.add_link(WotId(0), WotId(0)),
129            NewLinkResult::SelfLinkingForbidden()
130        );
131
132        // should add certs only in the boundaries of max_cert
133        assert_eq!(wot.add_link(WotId(0), WotId(1)), NewLinkResult::Ok(1));
134        assert_eq!(wot.add_link(WotId(0), WotId(2)), NewLinkResult::Ok(1));
135        assert_eq!(wot.add_link(WotId(0), WotId(3)), NewLinkResult::Ok(1));
136        assert_eq!(
137            wot.add_link(WotId(0), WotId(4)),
138            NewLinkResult::AllCertificationsUsed(0)
139        );
140
141        assert_eq!(wot.get_max_link(), 3);
142        assert_eq!(wot.has_link(WotId(0), WotId(1)), HasLinkResult::Link(true));
143        assert_eq!(wot.has_link(WotId(0), WotId(2)), HasLinkResult::Link(true));
144        assert_eq!(wot.has_link(WotId(0), WotId(3)), HasLinkResult::Link(true));
145        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(false));
146
147        wot.set_max_link(4);
148        assert_eq!(wot.get_max_link(), 4);
149        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(false));
150        wot.add_link(WotId(0), WotId(4));
151        assert_eq!(wot.has_link(WotId(0), WotId(4)), HasLinkResult::Link(true));
152        wot.rem_link(WotId(0), WotId(1));
153        wot.rem_link(WotId(0), WotId(2));
154        wot.rem_link(WotId(0), WotId(3));
155        wot.rem_link(WotId(0), WotId(4));
156
157        // false when not linked + test out of bounds
158        assert_eq!(wot.has_link(WotId(0), WotId(6)), HasLinkResult::Link(false));
159        assert_eq!(
160            wot.has_link(WotId(23), WotId(0)),
161            HasLinkResult::UnknownSource()
162        );
163        assert_eq!(
164            wot.has_link(WotId(2), WotId(53)),
165            HasLinkResult::UnknownTarget()
166        );
167
168        // created nodes should be enabled
169        assert_eq!(wot.is_enabled(WotId(0)), Some(true));
170        assert_eq!(wot.is_enabled(WotId(1)), Some(true));
171        assert_eq!(wot.is_enabled(WotId(2)), Some(true));
172        assert_eq!(wot.is_enabled(WotId(3)), Some(true));
173        assert_eq!(wot.is_enabled(WotId(11)), Some(true));
174
175        // should be able to disable some nodes
176        assert_eq!(wot.set_enabled(WotId(0), false), Some(false));
177        assert_eq!(wot.set_enabled(WotId(1), false), Some(false));
178        assert_eq!(wot.set_enabled(WotId(2), false), Some(false));
179        assert_eq!(wot.get_disabled().len(), 3);
180        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
181
182        // node 0 and 2 should be disabled
183        assert_eq!(wot.is_enabled(WotId(0)), Some(false));
184        assert_eq!(wot.is_enabled(WotId(1)), Some(true));
185        assert_eq!(wot.is_enabled(WotId(2)), Some(false));
186        assert_eq!(wot.is_enabled(WotId(3)), Some(true));
187        // - set enabled again
188        assert_eq!(wot.set_enabled(WotId(0), true), Some(true));
189        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
190        assert_eq!(wot.set_enabled(WotId(2), true), Some(true));
191        assert_eq!(wot.set_enabled(WotId(1), true), Some(true));
192        assert_eq!(wot.get_disabled().len(), 0);
193
194        // should not exist a link from 2 to 0
195        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(false));
196
197        // should be able to add some links, cert count is returned
198        assert_eq!(wot.add_link(WotId(2), WotId(0)), NewLinkResult::Ok(1));
199        assert_eq!(wot.add_link(WotId(4), WotId(0)), NewLinkResult::Ok(2));
200        // Check that certification replay is handled
201        assert_eq!(
202            wot.add_link(WotId(4), WotId(0)),
203            NewLinkResult::AlreadyExistingCertification(2)
204        );
205        // Check that certification re-replay is handled
206        assert_eq!(
207            wot.add_link(WotId(4), WotId(0)),
208            NewLinkResult::AlreadyExistingCertification(2)
209        );
210        assert_eq!(wot.add_link(WotId(5), WotId(0)), NewLinkResult::Ok(3));
211
212        // should exist new links
213        /* WoT is:
214         *
215         * 2 --> 0
216         * 4 --> 0
217         * 5 --> 0
218         */
219
220        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(true));
221        assert_eq!(wot.has_link(WotId(4), WotId(0)), HasLinkResult::Link(true));
222        assert_eq!(wot.has_link(WotId(5), WotId(0)), HasLinkResult::Link(true));
223        assert_eq!(wot.has_link(WotId(2), WotId(1)), HasLinkResult::Link(false));
224
225        // should be able to remove some links
226        assert_eq!(wot.rem_link(WotId(4), WotId(0)), RemLinkResult::Removed(2));
227        /*
228         * WoT is now:
229         *
230         * 2 --> 0
231         * 5 --> 0
232         */
233
234        // should exist less links
235        assert_eq!(wot.has_link(WotId(2), WotId(0)), HasLinkResult::Link(true));
236        assert_eq!(wot.has_link(WotId(4), WotId(0)), HasLinkResult::Link(false));
237        assert_eq!(wot.has_link(WotId(5), WotId(0)), HasLinkResult::Link(true));
238        assert_eq!(wot.has_link(WotId(2), WotId(1)), HasLinkResult::Link(false));
239
240        // should successfully use distance rule
241        assert_eq!(
242            distance_calculator.is_outdistanced(
243                &wot,
244                WotDistanceParameters {
245                    node: WotId(0),
246                    sentry_requirement: 1,
247                    step_max: 1,
248                    x_percent: 1.0,
249                },
250            ),
251            Ok(false)
252        );
253        // => no because 2,4,5 have certified him
254        assert_eq!(
255            distance_calculator.is_outdistanced(
256                &wot,
257                WotDistanceParameters {
258                    node: WotId(0),
259                    sentry_requirement: 2,
260                    step_max: 1,
261                    x_percent: 1.0,
262                },
263            ),
264            Ok(false)
265        );
266        // => no because only member 2 has 2 certs, and has certified him
267        assert_eq!(
268            distance_calculator.is_outdistanced(
269                &wot,
270                WotDistanceParameters {
271                    node: WotId(0),
272                    sentry_requirement: 3,
273                    step_max: 1,
274                    x_percent: 1.0,
275                },
276            ),
277            Ok(false)
278        );
279        // => no because no member has issued 3 certifications
280
281        // - we add links from member 3
282        assert_eq!(wot.add_link(WotId(3), WotId(1)), NewLinkResult::Ok(1));
283        assert_eq!(wot.add_link(WotId(3), WotId(2)), NewLinkResult::Ok(1));
284        /*
285         * WoT is now:
286         *
287         * 2 --> 0
288         * 5 --> 0
289         * 3 --> 1
290         * 3 --> 2
291         */
292        assert_eq!(wot.size(), 12);
293        assert_eq!(wot.get_sentries(1).len(), 1);
294        assert_eq!(wot.get_sentries(1)[0], WotId(2));
295        assert_eq!(wot.get_sentries(2).len(), 0);
296        assert_eq!(wot.get_sentries(3).len(), 0);
297        assert_eq!(wot.get_non_sentries(1).len(), 11); // 12 - 1
298        assert_eq!(wot.get_non_sentries(2).len(), 12); // 12 - 0
299        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
300        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 1).len(), 0); // KO
301        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
302        assert!(path_finder
303            .find_paths(&wot, WotId(3), WotId(0), 2)
304            .contains(&vec![WotId(3), WotId(2), WotId(0)]));
305
306        assert_eq!(
307            distance_calculator.is_outdistanced(
308                &wot,
309                WotDistanceParameters {
310                    node: WotId(0),
311                    sentry_requirement: 1,
312                    step_max: 1,
313                    x_percent: 1.0,
314                },
315            ),
316            Ok(false)
317        ); // OK : 2 -> 0
318        assert_eq!(
319            distance_calculator.is_outdistanced(
320                &wot,
321                WotDistanceParameters {
322                    node: WotId(0),
323                    sentry_requirement: 2,
324                    step_max: 1,
325                    x_percent: 1.0,
326                },
327            ),
328            Ok(false)
329        ); // OK : 2 -> 0
330        assert_eq!(
331            distance_calculator.is_outdistanced(
332                &wot,
333                WotDistanceParameters {
334                    node: WotId(0),
335                    sentry_requirement: 3,
336                    step_max: 1,
337                    x_percent: 1.0,
338                },
339            ),
340            Ok(false)
341        ); // OK : no stry \w 3 lnk
342        assert_eq!(
343            distance_calculator.is_outdistanced(
344                &wot,
345                WotDistanceParameters {
346                    node: WotId(0),
347                    sentry_requirement: 2,
348                    step_max: 2,
349                    x_percent: 1.0,
350                },
351            ),
352            Ok(false)
353        ); // OK : 2 -> 0
354
355        wot.add_link(WotId(1), WotId(3));
356        wot.add_link(WotId(2), WotId(3));
357
358        assert_eq!(wot.size(), 12);
359        assert_eq!(wot.get_sentries(1).len(), 3);
360        assert_eq!(wot.get_sentries(1)[0], WotId(1));
361        assert_eq!(wot.get_sentries(1)[1], WotId(2));
362        assert_eq!(wot.get_sentries(1)[2], WotId(3));
363
364        assert_eq!(wot.get_sentries(2).len(), 1);
365        assert_eq!(wot.get_sentries(2)[0], WotId(3));
366        assert_eq!(wot.get_sentries(3).len(), 0);
367        assert_eq!(wot.get_non_sentries(1).len(), 9); // 12 - 3
368        assert_eq!(wot.get_non_sentries(2).len(), 11); // 12 - 1
369        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
370        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 1).len(), 0); // KO
371        assert_eq!(path_finder.find_paths(&wot, WotId(3), WotId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
372        assert!(path_finder
373            .find_paths(&wot, WotId(3), WotId(0), 2)
374            .contains(&vec![WotId(3), WotId(2), WotId(0)]));
375
376        assert_eq!(
377            distance_calculator.is_outdistanced(
378                &wot,
379                WotDistanceParameters {
380                    node: WotId(0),
381                    sentry_requirement: 1,
382                    step_max: 1,
383                    x_percent: 1.0,
384                },
385            ),
386            Ok(true)
387        ); // KO : No path 3 -> 0
388           /*assert_eq!(
389               distance_calculator.is_outdistanced(
390                   &wot,
391                   WotDistanceParameters {
392                       node: WotId(0),
393                       sentry_requirement: 2,
394                       step_max: 1,
395                       x_percent: 1.0,
396                   },
397               ),
398               Some(true)
399           );*/ // KO : No path 3 -> 0
400        assert_eq!(
401            distance_calculator.is_outdistanced(
402                &wot,
403                WotDistanceParameters {
404                    node: WotId(0),
405                    sentry_requirement: 3,
406                    step_max: 1,
407                    x_percent: 1.0,
408                },
409            ),
410            Ok(false)
411        ); // OK : no stry \w 3 lnk
412        assert_eq!(
413            distance_calculator.is_outdistanced(
414                &wot,
415                WotDistanceParameters {
416                    node: WotId(0),
417                    sentry_requirement: 2,
418                    step_max: 2,
419                    x_percent: 1.0,
420                },
421            ),
422            Ok(false)
423        ); // OK : 3 -> 2 -> 0
424
425        // should have 12 nodes
426        assert_eq!(wot.size(), 12);
427
428        // delete top node (return new top node id)
429        assert_eq!(wot.rem_node(), Some(WotId(11)));
430
431        // should have 11 nodes
432        assert_eq!(wot.size(), 11);
433
434        // should work with member 3 disabled
435        // - with member 3 disabled (non-member)
436        assert_eq!(wot.set_enabled(WotId(3), false), Some(false));
437        assert_eq!(wot.get_disabled().len(), 1);
438        assert_eq!(
439            distance_calculator.is_outdistanced(
440                &wot,
441                WotDistanceParameters {
442                    node: WotId(0),
443                    sentry_requirement: 2,
444                    step_max: 1,
445                    x_percent: 1.0,
446                },
447            ),
448            Ok(false)
449        ); // OK : Disabled
450
451        // Write wot in file
452        write_bin_file(
453            Path::new("test.wot"),
454            &bincode::serialize(&wot).expect("fail to serialize wot"),
455        )
456        .expect("fail to write wot file");
457
458        let wot2_bin = read_bin_file(Path::new("test.wot")).expect("fail to read wot file");
459        let wot2: W = bincode::deserialize(&wot2_bin).expect("fail to deserialize wot");
460
461        // Read wot from file
462        {
463            assert_eq!(wot.size(), wot2.size());
464            assert_eq!(
465                wot.get_non_sentries(1).len(),
466                wot2.get_non_sentries(1).len()
467            );
468            assert_eq!(wot.get_disabled().len(), wot2.get_disabled().len());
469            assert_eq!(wot2.get_disabled().len(), 1);
470            assert_eq!(wot2.is_enabled(WotId(3)), Some(false));
471            assert_eq!(
472                distance_calculator.is_outdistanced(
473                    &wot2,
474                    WotDistanceParameters {
475                        node: WotId(0),
476                        sentry_requirement: 2,
477                        step_max: 1,
478                        x_percent: 1.0,
479                    },
480                ),
481                Ok(false)
482            );
483        }
484
485        // Dump wot
486        let mut dump_wot2_chars = Vec::new();
487        wot2.dump(&mut dump_wot2_chars).expect("fail to dump wot2");
488        let dump_wot2_str = String::from_utf8(dump_wot2_chars).expect("invalid utf8 chars");
489        assert_eq!(
490            dump_wot2_str,
491            "max_links=4
492nodes_count=11
493000: [2, 5]
494001: [3]
495002: [3]
496003: disabled [1, 2]
497004: []
498005: []
499006: []
500007: []
501008: []
502009: []
503010: []
504"
505        );
506
507        // Read g1_genesis wot
508        let wot3_bin = read_bin_file(Path::new("tests/g1_genesis.bin"))
509            .expect("fail to read g1_genesis wot file");
510        let wot3: W = bincode::deserialize(&wot3_bin).expect("fail to deserialize g1_genesis wot");
511
512        // Check g1_genesis wot members_count
513        let members_count = wot3.get_enabled().len() as u64;
514        assert_eq!(members_count, 59);
515
516        // Test compute_distance in g1_genesis wot
517        assert_eq!(
518            distance_calculator.compute_distance(
519                &wot3,
520                WotDistanceParameters {
521                    node: WotId(37),
522                    sentry_requirement: 3,
523                    step_max: 5,
524                    x_percent: 0.8,
525                },
526            ),
527            Ok(WotDistance {
528                sentries: 48,
529                success: 48,
530                success_at_border: 3,
531                reached: 51,
532                reached_at_border: 3,
533                outdistanced: false,
534            },)
535        );
536
537        // Test betweenness centralities computation in g1_genesis wot
538        let centralities = centralities_calculator.betweenness_centralities(&wot3);
539        assert_eq!(centralities.len(), 59);
540        assert_eq!(
541            centralities,
542            vec![
543                148, 30, 184, 11, 60, 51, 40, 115, 24, 140, 47, 69, 16, 34, 94, 126, 151, 0, 34,
544                133, 20, 103, 38, 144, 73, 523, 124, 23, 47, 17, 9, 64, 77, 281, 6, 105, 54, 0,
545                111, 21, 6, 2, 0, 1, 47, 59, 28, 236, 0, 0, 0, 0, 60, 6, 0, 1, 8, 33, 169,
546            ]
547        );
548
549        // Test stress centralities computation in g1_genesis wot
550        let stress_centralities = centralities_calculator.stress_centralities(&wot3);
551        assert_eq!(stress_centralities.len(), 59);
552        assert_eq!(
553            stress_centralities,
554            vec![
555                848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984,
556                0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276,
557                41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31,
558                0, 9, 55, 216, 865,
559            ]
560        );
561
562        // Test distance stress centralities computation in g1_genesis wot
563        let distance_stress_centralities =
564            centralities_calculator.distance_stress_centralities(&wot3, 5);
565        assert_eq!(distance_stress_centralities.len(), 59);
566        assert_eq!(
567            distance_stress_centralities,
568            vec![
569                848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984,
570                0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276,
571                41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31,
572                0, 9, 55, 216, 865,
573            ]
574        );
575    }
576}
dubp_wot/lib.rs

dubp_wot/
lib.rs
