discv5/kbucket/
key.rs

1// Copyright 2018 Parity Technologies (UK) Ltd.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a
4// copy of this software and associated documentation files (the "Software"),
5// to deal in the Software without restriction, including without limitation
6// the rights to use, copy, modify, merge, publish, distribute, sublicense,
7// and/or sell copies of the Software, and to permit persons to whom the
8// Software is furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in
11// all copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
14// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
19// DEALINGS IN THE SOFTWARE.
20
21// This basis of this file has been taken from the rust-libp2p codebase:
22// https://github.com/libp2p/rust-libp2p
23
24#![allow(clippy::all)]
25
26use enr::{
27    k256::sha2::digest::generic_array::{typenum::U32, GenericArray},
28    NodeId,
29};
30use uint::construct_uint;
31
32construct_uint! {
33    /// 256-bit unsigned integer.
34    pub(super) struct U256(4);
35}
36
37/// A `Key` is a cryptographic hash, identifying both the nodes participating in
38/// the Kademlia DHT, as well as records stored in the DHT.
39///
40/// The set of all `Key`s defines the Kademlia keyspace.
41///
42/// `Key`s have an XOR metric as defined in the Kademlia paper, i.e. the bitwise XOR of
43/// the hash digests, interpreted as an integer. See [`Key::distance`].
44///
45/// A `Key` preserves the preimage of type `T` of the hash function. See [`Key::preimage`].
46#[derive(Clone, Debug)]
47pub struct Key<T> {
48    preimage: T,
49    hash: GenericArray<u8, U32>,
50}
51
52impl<T> PartialEq for Key<T> {
53    fn eq(&self, other: &Key<T>) -> bool {
54        self.hash == other.hash
55    }
56}
57
58impl<T> Eq for Key<T> {}
59
60impl<TPeerId> AsRef<Key<TPeerId>> for Key<TPeerId> {
61    fn as_ref(&self) -> &Key<TPeerId> {
62        self
63    }
64}
65
66impl<T> Key<T> {
67    /// Construct a new `Key` by providing the raw 32 byte hash.
68    pub fn new_raw(preimage: T, hash: GenericArray<u8, U32>) -> Key<T> {
69        Key { preimage, hash }
70    }
71
72    /// Borrows the preimage of the key.
73    pub fn preimage(&self) -> &T {
74        &self.preimage
75    }
76
77    /// Converts the key into its preimage.
78    pub fn into_preimage(self) -> T {
79        self.preimage
80    }
81
82    /// Computes the distance of the keys according to the XOR metric.
83    pub fn distance<U>(&self, other: &Key<U>) -> Distance {
84        let a = U256::from_big_endian(self.hash.as_slice());
85        let b = U256::from_big_endian(other.hash.as_slice());
86        Distance(a ^ b)
87    }
88
89    // Used in the FINDNODE query outside of the k-bucket implementation.
90    /// Computes the integer log-2 distance between two keys, assuming a 256-bit
91    /// key. The output returns None if the key's are identical. The range is 1-256.
92    pub fn log2_distance<U>(&self, other: &Key<U>) -> Option<u64> {
93        let xor_dist = self.distance(other);
94        let log_dist = u64::from(256 - xor_dist.0.leading_zeros());
95        if log_dist == 0 {
96            None
97        } else {
98            Some(log_dist)
99        }
100    }
101}
102
103impl From<NodeId> for Key<NodeId> {
104    fn from(node_id: NodeId) -> Self {
105        Key {
106            preimage: node_id,
107            hash: *GenericArray::from_slice(&node_id.raw()),
108        }
109    }
110}
111
112/// A distance between two `Key`s.
113#[derive(Copy, Clone, PartialEq, Eq, Default, PartialOrd, Ord, Debug)]
114pub struct Distance(pub(super) U256);
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119    use crate::kbucket::bucket::tests::arbitrary_node_id;
120    use quickcheck::*;
121
122    impl Arbitrary for Key<NodeId> {
123        fn arbitrary<G: Gen>(g: &mut G) -> Key<NodeId> {
124            Key::from(arbitrary_node_id(g))
125        }
126    }
127
128    #[test]
129    fn identity() {
130        fn prop(a: Key<NodeId>) -> bool {
131            a.distance(&a) == Distance::default()
132        }
133        quickcheck(prop as fn(_) -> _)
134    }
135
136    #[test]
137    fn symmetry() {
138        fn prop(a: Key<NodeId>, b: Key<NodeId>) -> bool {
139            a.distance(&b) == b.distance(&a)
140        }
141        quickcheck(prop as fn(_, _) -> _)
142    }
143
144    #[test]
145    fn triangle_inequality() {
146        fn prop(a: Key<NodeId>, b: Key<NodeId>, c: Key<NodeId>) -> TestResult {
147            let ab = a.distance(&b);
148            let bc = b.distance(&c);
149            let (ab_plus_bc, overflow) = ab.0.overflowing_add(bc.0);
150            if overflow {
151                TestResult::discard()
152            } else {
153                TestResult::from_bool(a.distance(&c) <= Distance(ab_plus_bc))
154            }
155        }
156        quickcheck(prop as fn(_, _, _) -> _)
157    }
158
159    #[test]
160    fn unidirectionality() {
161        fn prop(a: Key<NodeId>, b: Key<NodeId>) -> bool {
162            let d = a.distance(&b);
163            (0..100).all(|_| {
164                let c = Key::from(NodeId::random());
165                a.distance(&c) != d || b == c
166            })
167        }
168        quickcheck(prop as fn(_, _) -> _)
169    }
170}
discv5/kbucket/key.rs

discv5/kbucket/
key.rs
