runiter_wot/
lib.rs

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

runiter_wot/
lib.rs
