duniter_wotb/
lib.rs

1//  Copyright (C) 2017-2018  The Duniter 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 [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/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(missing_docs, missing_debug_implementations, missing_copy_implementations, trivial_casts,
31        trivial_numeric_casts, unsafe_code, unstable_features, unused_import_braces,
32        unused_qualifications)]
33
34extern crate bincode;
35extern crate byteorder;
36extern crate rayon;
37extern crate serde;
38#[macro_use]
39extern crate serde_derive;
40
41pub mod legacy;
42pub mod rusty;
43
44pub use legacy::LegacyWebOfTrust;
45
46use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
47
48use std::io::prelude::*;
49use std::fs;
50use std::fs::File;
51
52/// Wrapper for a node id.
53#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
54pub struct NodeId(pub usize);
55
56/// Results of a certification, with the current certification count
57/// of the destination as parameter.
58#[derive(Debug, Copy, Clone, PartialEq, Eq)]
59pub enum NewLinkResult {
60    /// Certification worked.
61    Ok(usize),
62    /// This certification already exist.
63    AlreadyCertified(usize),
64    /// All available certifications has been used.
65    AllCertificationsUsed(usize),
66    /// Unknown source.
67    UnknownSource(),
68    /// Unknown target.
69    UnknownTarget(),
70    /// Self linking is forbidden.
71    SelfLinkingForbidden(),
72}
73
74/// Results of a certification removal, with the current certification count
75/// of the destination as parameter.
76#[derive(Debug, Copy, Clone, PartialEq, Eq)]
77pub enum RemLinkResult {
78    /// Certification has been removed.
79    Removed(usize),
80    /// Requested certification doesn't exist.
81    UnknownCert(usize),
82    /// Unknown source.
83    UnknownSource(),
84    /// Unknown target.
85    UnknownTarget(),
86}
87
88/// Results of `WebOfTrust` parsing from binary file.
89#[derive(Debug)]
90pub enum WotParseError {
91    /// FailToOpenFile
92    FailToOpenFile(std::io::Error),
93
94    /// IOError
95    IOError(std::io::Error),
96}
97
98impl From<std::io::Error> for WotParseError {
99    fn from(e: std::io::Error) -> WotParseError {
100        WotParseError::IOError(e)
101    }
102}
103
104/// Results of `WebOfTrust` writing to binary file.
105#[derive(Debug)]
106pub enum WotWriteError {
107    /// WrongWotSize
108    WrongWotSize(),
109
110    /// FailToCreateFile
111    FailToCreateFile(std::io::Error),
112
113    /// FailToWriteInFile
114    FailToWriteInFile(std::io::Error),
115}
116
117impl From<std::io::Error> for WotWriteError {
118    fn from(e: std::io::Error) -> WotWriteError {
119        WotWriteError::FailToWriteInFile(e)
120    }
121}
122
123/// Results of a certification test.
124#[derive(Debug, Copy, Clone, PartialEq, Eq)]
125pub enum HasLinkResult {
126    /// Both nodes are known, here is the result.
127    Link(bool),
128    /// Unknown source.
129    UnknownSource(),
130    /// Unknown target.
131    UnknownTarget(),
132}
133
134/// Paramters for `WoT` distance calculations
135#[derive(Debug, Copy, Clone, PartialEq)]
136pub struct WotDistanceParameters {
137    /// Node from where distances are calculated.
138    pub node: NodeId,
139    /// Links count received AND issued to be a sentry.
140    pub sentry_requirement: u32,
141    /// Currency parameter.
142    pub step_max: u32,
143    /// Currency parameter.
144    pub x_percent: f64,
145}
146
147/// Results of `WebOfTrust::compute_distance`.
148#[derive(Debug, Copy, Clone, PartialEq, Eq)]
149pub struct WotDistance {
150    /// Sentries count
151    pub sentries: u32,
152    /// Success count
153    pub success: u32,
154    /// Succes at border count
155    pub success_at_border: u32,
156    /// Reached count
157    pub reached: u32,
158    /// Reached at border count
159    pub reached_at_border: u32,
160    /// Is the node outdistanced ?
161    pub outdistanced: bool,
162}
163
164/// Trait for a Web Of Trust.
165/// Allow to provide other implementations of the `WoT` logic instead of the legacy C++
166/// translated one.
167pub trait WebOfTrust {
168    /// Get the maximum number of links per user.
169    fn get_max_link(&self) -> usize;
170
171    /// Set the maximum number of links per user.
172    fn set_max_link(&mut self, max_link: usize);
173
174    /// Add a new node.
175    fn add_node(&mut self) -> NodeId;
176
177    /// Remove the last node.
178    /// Returns `None` if the WoT was empty, otherwise new top node id.
179    fn rem_node(&mut self) -> Option<NodeId>;
180
181    /// Get the size of the WoT.
182    fn size(&self) -> usize;
183
184    /// Check if given node is enabled.
185    /// Returns `None` if this node doesn't exist.
186    fn is_enabled(&self, id: NodeId) -> Option<bool>;
187
188    /// Set the enabled state of given node.
189    /// Returns `Null` if this node doesn't exist, `enabled` otherwise.
190    fn set_enabled(&mut self, id: NodeId, enabled: bool) -> Option<bool>;
191
192    /// Get enabled node array.
193    fn get_enabled(&self) -> Vec<NodeId>;
194
195    /// Get disabled node array.
196    fn get_disabled(&self) -> Vec<NodeId>;
197
198    /// Try to add a link from the source to the target.
199    fn add_link(&mut self, source: NodeId, target: NodeId) -> NewLinkResult;
200
201    /// Try to remove a link from the source to the target.
202    fn rem_link(&mut self, source: NodeId, target: NodeId) -> RemLinkResult;
203
204    /// Test if there is a link from the source to the target.
205    fn has_link(&self, source: NodeId, target: NodeId) -> HasLinkResult;
206
207    /// Get the list of links source for this target.
208    /// Returns `None` if this node doesn't exist.
209    fn get_links_source(&self, target: NodeId) -> Option<Vec<NodeId>>;
210
211    /// Get the number of issued links by a node.
212    /// Returns `None` if this node doesn't exist.
213    fn issued_count(&self, id: NodeId) -> Option<usize>;
214
215    /// Get sentries array.
216    fn get_sentries(&self, sentry_requirement: usize) -> Vec<NodeId>;
217
218    /// Get non sentries array.
219    fn get_non_sentries(&self, sentry_requirement: usize) -> Vec<NodeId>;
220
221    /// Get paths from one node to the other.
222    fn get_paths(&self, from: NodeId, to: NodeId, k_max: u32) -> Vec<Vec<NodeId>>;
223
224    /// Compute distance between a node and the network.
225    /// Returns `None` if this node doesn't exist.
226    fn compute_distance(&self, params: WotDistanceParameters) -> Option<WotDistance>;
227
228    /// Test if a node is outdistanced in the network.
229    /// Returns `Node` if this node doesn't exist.
230    fn is_outdistanced(&self, params: WotDistanceParameters) -> Option<bool>;
231
232    /// Load WebOfTrust from binary file
233    fn from_file(&mut self, path: &str) -> Result<Vec<u8>, WotParseError> {
234        let file_size = fs::metadata(path).expect("fail to read wotb file !").len();
235        let mut file_pointing_to_blockstamp_size: Vec<u8> = vec![0; file_size as usize];
236        match File::open(path) {
237            Ok(mut file) => {
238                file.read_exact(&mut file_pointing_to_blockstamp_size.as_mut_slice())?;
239            }
240            Err(e) => return Err(WotParseError::FailToOpenFile(e)),
241        };
242        // Read up to 4 bytes (blockstamp_size)
243        let mut file_pointing_to_blockstamp = file_pointing_to_blockstamp_size.split_off(4);
244        // Get blockstamp size
245        let mut buf = &file_pointing_to_blockstamp_size[..];
246        let blockstamp_size = buf.read_u32::<BigEndian>().unwrap();
247        // Read up to blockstamp_size bytes (blockstamp)
248        let mut file_pointing_to_nodes_count =
249            file_pointing_to_blockstamp.split_off(blockstamp_size as usize);
250        // Read up to 4 bytes (nodes_count)
251        let mut file_pointing_to_nodes_states = file_pointing_to_nodes_count.split_off(4);
252        // Read nodes_count
253        let mut buf = &file_pointing_to_nodes_count[..];
254        let nodes_count = buf.read_u32::<BigEndian>().unwrap();
255        // Calcule nodes_state size
256        let nodes_states_size = match nodes_count % 8 {
257            0 => nodes_count / 8,
258            _ => (nodes_count / 8) + 1,
259        };
260        // Read up to nodes_states_size bytes (nodes_states)
261        let file_pointing_to_links =
262            file_pointing_to_nodes_states.split_off(nodes_states_size as usize);
263        // Apply nodes state
264        let mut count_remaining_nodes = nodes_count;
265        for byte in file_pointing_to_nodes_states {
266            let mut byte_integer = u8::from_be(byte);
267            let mut factor: u8 = 128;
268            for _i in 0..8 {
269                if count_remaining_nodes > 0 {
270                    self.add_node();
271                    if byte_integer >= factor {
272                        byte_integer -= factor;
273                    } else {
274                        let _test = self.set_enabled(
275                            NodeId((nodes_count - count_remaining_nodes) as usize),
276                            false,
277                        );
278                    }
279                    count_remaining_nodes -= 1;
280                }
281                factor /= 2;
282            }
283        }
284        // Apply links
285        let mut buffer_3b: Vec<u8> = Vec::with_capacity(3);
286        let mut count_bytes = 0;
287        let mut remaining_links: u8 = 0;
288        let mut target: u32 = 0;
289        for byte in file_pointing_to_links {
290            if remaining_links == 0 {
291                target += 1;
292                remaining_links = u8::from_be(byte);
293                count_bytes = 0;
294            } else {
295                buffer_3b.push(byte);
296                if count_bytes % 3 == 2 {
297                    let mut buf = &buffer_3b.clone()[..];
298                    let source = buf.read_u24::<BigEndian>().expect("fail to parse source");
299                    self.add_link(NodeId(source as usize), NodeId((target - 1) as usize));
300                    remaining_links -= 1;
301                    buffer_3b.clear();
302                }
303                count_bytes += 1;
304            }
305        }
306        Ok(file_pointing_to_blockstamp)
307    }
308
309    /// Write WebOfTrust to binary file
310    fn to_file(&self, path: &str, blockstamp: &[u8]) -> Result<(), WotWriteError> {
311        let mut buffer: Vec<u8> = Vec::new();
312        // Write blockstamp size
313        let blockstamp_size = blockstamp.len() as u32;
314        let mut bytes: Vec<u8> = Vec::with_capacity(4);
315        bytes.write_u32::<BigEndian>(blockstamp_size).unwrap();
316        buffer.append(&mut bytes);
317        // Write blockstamp
318        buffer.append(&mut blockstamp.to_vec());
319        // Write nodes_count
320        let nodes_count = self.size() as u32;
321        let mut bytes: Vec<u8> = Vec::with_capacity(4);
322        bytes.write_u32::<BigEndian>(nodes_count).unwrap();
323        buffer.append(&mut bytes);
324        // Write enable state by groups of 8 (count links at the same time)
325        let mut enable_states: u8 = 0;
326        let mut factor: u8 = 128;
327        for n in 0..nodes_count {
328            match self.is_enabled(NodeId(n as usize)) {
329                Some(enable) => {
330                    if enable {
331                        enable_states += factor;
332                    }
333                }
334                None => {
335                    return Err(WotWriteError::WrongWotSize());
336                }
337            }
338            if n % 8 == 7 {
339                factor = 128;
340                let mut tmp_buf = Vec::with_capacity(1);
341                tmp_buf.write_u8(enable_states).unwrap();
342                buffer.append(&mut tmp_buf);
343                enable_states = 0;
344            } else {
345                factor /= 2;
346            }
347        }
348        // nodes_states padding
349        if nodes_count % 8 != 7 {
350            let mut tmp_buf = Vec::with_capacity(1);
351            tmp_buf.write_u8(enable_states).unwrap();
352            buffer.append(&mut tmp_buf);
353        }
354        // Write links
355        for n in 0..nodes_count {
356            if let Some(sources) = self.get_links_source(NodeId(n as usize)) {
357                // Write sources_counts
358                let mut bytes = Vec::with_capacity(1);
359                bytes.write_u8(sources.len() as u8).unwrap();
360                buffer.append(&mut bytes);
361                for source in &sources {
362                    // Write source
363                    let mut bytes: Vec<u8> = Vec::with_capacity(3);
364                    bytes.write_u24::<BigEndian>(source.0 as u32).unwrap();
365                    buffer.append(&mut bytes);
366                }
367            };
368        }
369        // Create or open file
370        let mut file = match File::create(path) {
371            Ok(file) => file,
372            Err(e) => return Err(WotWriteError::FailToCreateFile(e)),
373        };
374        // Write buffer in file
375        file.write_all(&buffer)?;
376
377        Ok(())
378    }
379}
380
381#[cfg(test)]
382mod tests {
383    use super::*;
384
385    /// Test translated from https://github.com/duniter/wotb/blob/master/tests/test.js
386    ///
387    /// Clone and file tests are not included in this generic test and should be done in
388    /// the implementation test.
389    pub fn generic_wot_test<T: WebOfTrust, F>(generator: F)
390    where
391        F: Fn(usize) -> T,
392    {
393        let mut wot = generator(3);
394
395        // should have an initial size of 0
396        assert_eq!(wot.size(), 0);
397
398        // should return `None()` if testing `is_enabled()` with out-of-bounds node
399        assert_eq!(wot.is_enabled(NodeId(0)), None);
400        assert_eq!(wot.is_enabled(NodeId(23)), None);
401
402        // should give nomber 0 if we add a node
403        // - add a node
404        assert_eq!(wot.add_node(), NodeId(0));
405        assert_eq!(wot.size(), 1);
406        assert_eq!(wot.get_disabled().len(), 0);
407
408        // - add another
409        assert_eq!(wot.add_node(), NodeId(1));
410        assert_eq!(wot.size(), 2);
411        assert_eq!(wot.get_disabled().len(), 0);
412
413        // - add 10 nodes
414        for i in 0..10 {
415            assert_eq!(wot.add_node(), NodeId(i + 2));
416        }
417
418        assert_eq!(wot.size(), 12);
419
420        // shouldn't be able to self cert
421        assert_eq!(
422            wot.add_link(NodeId(0), NodeId(0)),
423            NewLinkResult::SelfLinkingForbidden()
424        );
425
426        // should add certs only in the boundaries of max_cert
427        assert_eq!(wot.add_link(NodeId(0), NodeId(1)), NewLinkResult::Ok(1));
428        assert_eq!(wot.add_link(NodeId(0), NodeId(2)), NewLinkResult::Ok(1));
429        assert_eq!(wot.add_link(NodeId(0), NodeId(3)), NewLinkResult::Ok(1));
430        assert_eq!(
431            wot.add_link(NodeId(0), NodeId(4)),
432            NewLinkResult::AllCertificationsUsed(0)
433        );
434
435        assert_eq!(wot.get_max_link(), 3);
436        assert_eq!(
437            wot.has_link(NodeId(0), NodeId(1)),
438            HasLinkResult::Link(true)
439        );
440        assert_eq!(
441            wot.has_link(NodeId(0), NodeId(2)),
442            HasLinkResult::Link(true)
443        );
444        assert_eq!(
445            wot.has_link(NodeId(0), NodeId(3)),
446            HasLinkResult::Link(true)
447        );
448        assert_eq!(
449            wot.has_link(NodeId(0), NodeId(4)),
450            HasLinkResult::Link(false)
451        );
452
453        wot.set_max_link(4);
454        assert_eq!(wot.get_max_link(), 4);
455        assert_eq!(
456            wot.has_link(NodeId(0), NodeId(4)),
457            HasLinkResult::Link(false)
458        );
459        wot.add_link(NodeId(0), NodeId(4));
460        assert_eq!(
461            wot.has_link(NodeId(0), NodeId(4)),
462            HasLinkResult::Link(true)
463        );
464        wot.rem_link(NodeId(0), NodeId(1));
465        wot.rem_link(NodeId(0), NodeId(2));
466        wot.rem_link(NodeId(0), NodeId(3));
467        wot.rem_link(NodeId(0), NodeId(4));
468
469        // false when not linked + test out of bounds
470        assert_eq!(
471            wot.has_link(NodeId(0), NodeId(6)),
472            HasLinkResult::Link(false)
473        );
474        assert_eq!(
475            wot.has_link(NodeId(23), NodeId(0)),
476            HasLinkResult::UnknownSource()
477        );
478        assert_eq!(
479            wot.has_link(NodeId(2), NodeId(53)),
480            HasLinkResult::UnknownTarget()
481        );
482
483        // created nodes should be enabled
484        assert_eq!(wot.is_enabled(NodeId(0)), Some(true));
485        assert_eq!(wot.is_enabled(NodeId(1)), Some(true));
486        assert_eq!(wot.is_enabled(NodeId(2)), Some(true));
487        assert_eq!(wot.is_enabled(NodeId(3)), Some(true));
488        assert_eq!(wot.is_enabled(NodeId(11)), Some(true));
489
490        // should be able to disable some nodes
491        assert_eq!(wot.set_enabled(NodeId(0), false), Some(false));
492        assert_eq!(wot.set_enabled(NodeId(1), false), Some(false));
493        assert_eq!(wot.set_enabled(NodeId(2), false), Some(false));
494        assert_eq!(wot.get_disabled().len(), 3);
495        assert_eq!(wot.set_enabled(NodeId(1), true), Some(true));
496
497        // node 0 and 2 should be disabled
498        assert_eq!(wot.is_enabled(NodeId(0)), Some(false));
499        assert_eq!(wot.is_enabled(NodeId(1)), Some(true));
500        assert_eq!(wot.is_enabled(NodeId(2)), Some(false));
501        assert_eq!(wot.is_enabled(NodeId(3)), Some(true));
502        // - set enabled again
503        assert_eq!(wot.set_enabled(NodeId(0), true), Some(true));
504        assert_eq!(wot.set_enabled(NodeId(1), true), Some(true));
505        assert_eq!(wot.set_enabled(NodeId(2), true), Some(true));
506        assert_eq!(wot.set_enabled(NodeId(1), true), Some(true));
507        assert_eq!(wot.get_disabled().len(), 0);
508
509        // should not exist a link from 2 to 0
510        assert_eq!(
511            wot.has_link(NodeId(2), NodeId(0)),
512            HasLinkResult::Link(false)
513        );
514
515        // should be able to add some links, cert count is returned
516        assert_eq!(wot.add_link(NodeId(2), NodeId(0)), NewLinkResult::Ok(1));
517        assert_eq!(wot.add_link(NodeId(4), NodeId(0)), NewLinkResult::Ok(2));
518        assert_eq!(
519            wot.add_link(NodeId(4), NodeId(0)),
520            NewLinkResult::AlreadyCertified(2)
521        );
522        assert_eq!(
523            wot.add_link(NodeId(4), NodeId(0)),
524            NewLinkResult::AlreadyCertified(2)
525        );
526        assert_eq!(wot.add_link(NodeId(5), NodeId(0)), NewLinkResult::Ok(3));
527
528        // should exist new links
529        /* WoT is:
530         *
531         * 2 --> 0
532         * 4 --> 0
533         * 5 --> 0
534         */
535
536        assert_eq!(
537            wot.has_link(NodeId(2), NodeId(0)),
538            HasLinkResult::Link(true)
539        );
540        assert_eq!(
541            wot.has_link(NodeId(4), NodeId(0)),
542            HasLinkResult::Link(true)
543        );
544        assert_eq!(
545            wot.has_link(NodeId(5), NodeId(0)),
546            HasLinkResult::Link(true)
547        );
548        assert_eq!(
549            wot.has_link(NodeId(2), NodeId(1)),
550            HasLinkResult::Link(false)
551        );
552
553        // should be able to remove some links
554        assert_eq!(
555            wot.rem_link(NodeId(4), NodeId(0)),
556            RemLinkResult::Removed(2)
557        );
558        /*
559         * WoT is now:
560         *
561         * 2 --> 0
562         * 5 --> 0
563         */
564
565        // should exist less links
566        assert_eq!(
567            wot.has_link(NodeId(2), NodeId(0)),
568            HasLinkResult::Link(true)
569        );
570        assert_eq!(
571            wot.has_link(NodeId(4), NodeId(0)),
572            HasLinkResult::Link(false)
573        );
574        assert_eq!(
575            wot.has_link(NodeId(5), NodeId(0)),
576            HasLinkResult::Link(true)
577        );
578        assert_eq!(
579            wot.has_link(NodeId(2), NodeId(1)),
580            HasLinkResult::Link(false)
581        );
582
583        // should successfully use distance rule
584        assert_eq!(
585            wot.is_outdistanced(WotDistanceParameters {
586                node: NodeId(0),
587                sentry_requirement: 1,
588                step_max: 1,
589                x_percent: 1.0,
590            },),
591            Some(false)
592        );
593        // => no because 2,4,5 have certified him
594        assert_eq!(
595            wot.is_outdistanced(WotDistanceParameters {
596                node: NodeId(0),
597                sentry_requirement: 2,
598                step_max: 1,
599                x_percent: 1.0,
600            },),
601            Some(false)
602        );
603        // => no because only member 2 has 2 certs, and has certified him
604        assert_eq!(
605            wot.is_outdistanced(WotDistanceParameters {
606                node: NodeId(0),
607                sentry_requirement: 3,
608                step_max: 1,
609                x_percent: 1.0,
610            },),
611            Some(false)
612        );
613        // => no because no member has issued 3 certifications
614
615        // - we add links from member 3
616        assert_eq!(wot.add_link(NodeId(3), NodeId(1)), NewLinkResult::Ok(1));
617        assert_eq!(wot.add_link(NodeId(3), NodeId(2)), NewLinkResult::Ok(1));
618        /*
619         * WoT is now:
620         *
621         * 2 --> 0
622         * 5 --> 0
623         * 3 --> 1
624         * 3 --> 2
625         */
626        assert_eq!(wot.size(), 12);
627        assert_eq!(wot.get_sentries(1).len(), 1);
628        assert_eq!(wot.get_sentries(1)[0], NodeId(2));
629        assert_eq!(wot.get_sentries(2).len(), 0);
630        assert_eq!(wot.get_sentries(3).len(), 0);
631        assert_eq!(wot.get_non_sentries(1).len(), 11); // 12 - 1
632        assert_eq!(wot.get_non_sentries(2).len(), 12); // 12 - 0
633        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
634        assert_eq!(wot.get_paths(NodeId(3), NodeId(0), 1).len(), 0); // KO
635        assert_eq!(wot.get_paths(NodeId(3), NodeId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
636        assert!(wot.get_paths(NodeId(3), NodeId(0), 2).contains(&vec![
637            NodeId(3),
638            NodeId(2),
639            NodeId(0),
640        ]));
641
642        assert_eq!(
643            wot.is_outdistanced(WotDistanceParameters {
644                node: NodeId(0),
645                sentry_requirement: 1,
646                step_max: 1,
647                x_percent: 1.0,
648            },),
649            Some(false)
650        ); // OK : 2 -> 0
651        assert_eq!(
652            wot.is_outdistanced(WotDistanceParameters {
653                node: NodeId(0),
654                sentry_requirement: 2,
655                step_max: 1,
656                x_percent: 1.0,
657            },),
658            Some(false)
659        ); // OK : 2 -> 0
660        assert_eq!(
661            wot.is_outdistanced(WotDistanceParameters {
662                node: NodeId(0),
663                sentry_requirement: 3,
664                step_max: 1,
665                x_percent: 1.0,
666            },),
667            Some(false)
668        ); // OK : no stry \w 3 lnk
669        assert_eq!(
670            wot.is_outdistanced(WotDistanceParameters {
671                node: NodeId(0),
672                sentry_requirement: 2,
673                step_max: 2,
674                x_percent: 1.0,
675            },),
676            Some(false)
677        ); // OK : 2 -> 0
678
679        wot.add_link(NodeId(1), NodeId(3));
680        wot.add_link(NodeId(2), NodeId(3));
681
682        assert_eq!(wot.size(), 12);
683        assert_eq!(wot.get_sentries(1).len(), 3);
684        assert_eq!(wot.get_sentries(1)[0], NodeId(1));
685        assert_eq!(wot.get_sentries(1)[1], NodeId(2));
686        assert_eq!(wot.get_sentries(1)[2], NodeId(3));
687
688        assert_eq!(wot.get_sentries(2).len(), 1);
689        assert_eq!(wot.get_sentries(2)[0], NodeId(3));
690        assert_eq!(wot.get_sentries(3).len(), 0);
691        assert_eq!(wot.get_non_sentries(1).len(), 9); // 12 - 3
692        assert_eq!(wot.get_non_sentries(2).len(), 11); // 12 - 1
693        assert_eq!(wot.get_non_sentries(3).len(), 12); // 12 - 0
694        assert_eq!(wot.get_paths(NodeId(3), NodeId(0), 1).len(), 0); // KO
695        assert_eq!(wot.get_paths(NodeId(3), NodeId(0), 2).len(), 1); // It exists 3 -> 2 -> 0
696        assert!(wot.get_paths(NodeId(3), NodeId(0), 2).contains(&vec![
697            NodeId(3),
698            NodeId(2),
699            NodeId(0),
700        ]));
701
702        assert_eq!(
703            wot.is_outdistanced(WotDistanceParameters {
704                node: NodeId(0),
705                sentry_requirement: 1,
706                step_max: 1,
707                x_percent: 1.0,
708            },),
709            Some(true)
710        ); // KO : No path 3 -> 0
711        assert_eq!(
712            wot.is_outdistanced(WotDistanceParameters {
713                node: NodeId(0),
714                sentry_requirement: 2,
715                step_max: 1,
716                x_percent: 1.0,
717            },),
718            Some(true)
719        ); // KO : No path 3 -> 0
720        assert_eq!(
721            wot.is_outdistanced(WotDistanceParameters {
722                node: NodeId(0),
723                sentry_requirement: 3,
724                step_max: 1,
725                x_percent: 1.0,
726            },),
727            Some(false)
728        ); // OK : no stry \w 3 lnk
729        assert_eq!(
730            wot.is_outdistanced(WotDistanceParameters {
731                node: NodeId(0),
732                sentry_requirement: 2,
733                step_max: 2,
734                x_percent: 1.0,
735            },),
736            Some(false)
737        ); // OK : 3 -> 2 -> 0
738
739        // should have 12 nodes
740        assert_eq!(wot.size(), 12);
741
742        // delete top node (return new top node id)
743        assert_eq!(wot.rem_node(), Some(NodeId(10)));
744
745        // should have 11 nodes
746        assert_eq!(wot.size(), 11);
747
748        // should work with member 3 disabled
749        // - with member 3 disabled (non-member)
750        assert_eq!(wot.set_enabled(NodeId(3), false), Some(false));
751        assert_eq!(wot.get_disabled().len(), 1);
752        assert_eq!(
753            wot.is_outdistanced(WotDistanceParameters {
754                node: NodeId(0),
755                sentry_requirement: 2,
756                step_max: 1,
757                x_percent: 1.0,
758            },),
759            Some(false)
760        ); // OK : Disabled
761
762        // Write wot in file
763        assert_eq!(
764            wot.to_file(
765                "test.wot",
766                &[0b0000_0000, 0b0000_0001, 0b0000_0001, 0b0000_0000]
767            ).unwrap(),
768            ()
769        );
770
771        let mut wot2 = generator(3);
772
773        // Read wot from file
774        {
775            assert_eq!(
776                wot2.from_file("test.wot").unwrap(),
777                vec![0b0000_0000, 0b0000_0001, 0b0000_0001, 0b0000_0000]
778            );
779            assert_eq!(wot.size(), wot2.size());
780            assert_eq!(
781                wot.get_non_sentries(1).len(),
782                wot2.get_non_sentries(1).len()
783            );
784            assert_eq!(wot.get_disabled().len(), wot2.get_disabled().len());
785            assert_eq!(wot2.get_disabled().len(), 1);
786            assert_eq!(wot2.is_enabled(NodeId(3)), Some(false));
787            assert_eq!(
788                wot2.is_outdistanced(WotDistanceParameters {
789                    node: NodeId(0),
790                    sentry_requirement: 2,
791                    step_max: 1,
792                    x_percent: 1.0,
793                },),
794                Some(false)
795            );
796        }
797
798        // Read g1_genesis wot
799        let mut wot3 = generator(100);
800        assert_eq!(
801            wot3.from_file("tests/g1_genesis.bin").unwrap(),
802            vec![
803                57, 57, 45, 48, 48, 48, 48, 49, 50, 65, 68, 52, 57, 54, 69, 67, 65, 53, 54, 68, 69,
804                48, 66, 56, 69, 53, 68, 54, 70, 55, 52, 57, 66, 55, 67, 66, 69, 55, 56, 53, 53, 51,
805                69, 54, 51, 56, 53, 51, 51, 51, 65, 52, 52, 69, 48, 52, 51, 55, 55, 69, 70, 70, 67,
806                67, 65, 53, 51,
807            ]
808        );
809
810        // Check g1_genesis wot members_count
811        let members_count = wot3.get_enabled().len() as u64;
812        assert_eq!(members_count, 59);
813
814        // Test compute_distance in g1_genesis wot
815        assert_eq!(
816            wot3.compute_distance(WotDistanceParameters {
817                node: NodeId(37),
818                sentry_requirement: 3,
819                step_max: 5,
820                x_percent: 0.8,
821            },),
822            Some(WotDistance {
823                sentries: 48,
824                success: 48,
825                success_at_border: 3,
826                reached: 52,
827                reached_at_border: 3,
828                outdistanced: false,
829            },)
830        );
831
832        // Test centralities computation in g1_genesis wot
833        let wot_size = wot3.size();
834        let members_count = wot3.get_enabled().len() as u64;
835        assert_eq!(members_count, 59);
836        let oriented_couples_count: u64 = members_count * (members_count - 1);
837        let mut centralities = vec![0; wot_size];
838        for i in 0..wot_size {
839            for j in 0..wot_size {
840                let paths = wot3.get_paths(NodeId(i), NodeId(j), 5);
841                let mut intermediate_members: Vec<NodeId> = Vec::new();
842                for path in paths {
843                    if path.len() > 2 {
844                        for node_id in &path[1..path.len() - 1] {
845                            if !intermediate_members.contains(node_id) {
846                                intermediate_members.push(*node_id);
847                            }
848                        }
849                    }
850                }
851                let centralities_copy = centralities.clone();
852                for node_id in intermediate_members {
853                    let centrality = &centralities_copy[node_id.0];
854                    if let Some(tmp) = centralities.get_mut(node_id.0) {
855                        *tmp = *centrality + 1;
856                    }
857                }
858            }
859        }
860        let mut relative_centralities = Vec::with_capacity(wot_size);
861        for centrality in centralities {
862            relative_centralities.push((centrality * 100_000 / oriented_couples_count) as usize);
863        }
864        assert_eq!(relative_centralities.len(), 59);
865    }
866}
duniter_wotb/lib.rs

duniter_wotb/
lib.rs
