cs_mwc_libp2p_kad/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
21use uint::*;
22use mwc_libp2p_core::{PeerId, multihash::Multihash};
23use sha2::{Digest, Sha256};
24use sha2::digest::generic_array::{GenericArray, typenum::U32};
25use std::borrow::Borrow;
26use std::hash::{Hash, Hasher};
27use crate::record;
28
29construct_uint! {
30    /// 256-bit unsigned integer.
31    pub(super) struct U256(4);
32}
33
34/// A `Key` in the DHT keyspace with preserved preimage.
35///
36/// Keys in the DHT keyspace identify both the participating nodes, as well as
37/// the records stored in the DHT.
38///
39/// `Key`s have an XOR metric as defined in the Kademlia paper, i.e. the bitwise XOR of
40/// the hash digests, interpreted as an integer. See [`Key::distance`].
41#[derive(Clone, Debug)]
42pub struct Key<T> {
43    preimage: T,
44    bytes: KeyBytes,
45}
46
47impl<T> Key<T> {
48    /// Constructs a new `Key` by running the given value through a random
49    /// oracle.
50    ///
51    /// The preimage of type `T` is preserved. See [`Key::preimage`] and
52    /// [`Key::into_preimage`].
53    pub fn new(preimage: T) -> Key<T>
54    where
55        T: Borrow<[u8]>
56    {
57        let bytes = KeyBytes::new(preimage.borrow());
58        Key { preimage, bytes }
59    }
60
61    /// Borrows the preimage of the key.
62    pub fn preimage(&self) -> &T {
63        &self.preimage
64    }
65
66    /// Converts the key into its preimage.
67    pub fn into_preimage(self) -> T {
68        self.preimage
69    }
70
71    /// Computes the distance of the keys according to the XOR metric.
72    pub fn distance<U>(&self, other: &U) -> Distance
73    where
74        U: AsRef<KeyBytes>
75    {
76        self.bytes.distance(other)
77    }
78
79    /// Returns the uniquely determined key with the given distance to `self`.
80    ///
81    /// This implements the following equivalence:
82    ///
83    /// `self xor other = distance <==> other = self xor distance`
84    pub fn for_distance(&self, d: Distance) -> KeyBytes {
85        self.bytes.for_distance(d)
86    }
87}
88
89impl<T> Into<KeyBytes> for Key<T> {
90    fn into(self) -> KeyBytes {
91        self.bytes
92    }
93}
94
95impl From<Multihash> for Key<Multihash> {
96   fn from(m: Multihash) -> Self {
97       let bytes = KeyBytes(Sha256::digest(&m.to_bytes()));
98       Key {
99           preimage: m,
100           bytes
101       }
102   }
103}
104
105impl From<PeerId> for Key<PeerId> {
106    fn from(p: PeerId) -> Self {
107       let bytes = KeyBytes(Sha256::digest(&p.to_bytes()));
108       Key {
109           preimage: p,
110           bytes
111       }
112    }
113}
114
115impl From<Vec<u8>> for Key<Vec<u8>> {
116    fn from(b: Vec<u8>) -> Self {
117        Key::new(b)
118    }
119}
120
121impl From<record::Key> for Key<record::Key> {
122    fn from(k: record::Key) -> Self {
123        Key::new(k)
124    }
125}
126
127impl<T> AsRef<KeyBytes> for Key<T> {
128    fn as_ref(&self) -> &KeyBytes {
129        &self.bytes
130    }
131}
132
133impl<T, U> PartialEq<Key<U>> for Key<T> {
134    fn eq(&self, other: &Key<U>) -> bool {
135        self.bytes == other.bytes
136    }
137}
138
139impl<T> Eq for Key<T> {}
140
141impl<T> Hash for Key<T> {
142    fn hash<H: Hasher>(&self, state: &mut H) {
143        self.bytes.0.hash(state);
144    }
145}
146
147/// The raw bytes of a key in the DHT keyspace.
148#[derive(PartialEq, Eq, Clone, Debug)]
149pub struct KeyBytes(GenericArray<u8, U32>);
150
151impl KeyBytes {
152    /// Creates a new key in the DHT keyspace by running the given
153    /// value through a random oracle.
154    pub fn new<T>(value: T) -> Self
155    where
156        T: Borrow<[u8]>
157    {
158        KeyBytes(Sha256::digest(value.borrow()))
159    }
160
161    /// Computes the distance of the keys according to the XOR metric.
162    pub fn distance<U>(&self, other: &U) -> Distance
163    where
164        U: AsRef<KeyBytes>
165    {
166        let a = U256::from(self.0.as_slice());
167        let b = U256::from(other.as_ref().0.as_slice());
168        Distance(a ^ b)
169    }
170
171    /// Returns the uniquely determined key with the given distance to `self`.
172    ///
173    /// This implements the following equivalence:
174    ///
175    /// `self xor other = distance <==> other = self xor distance`
176    pub fn for_distance(&self, d: Distance) -> KeyBytes {
177        let key_int = U256::from(self.0.as_slice()) ^ d.0;
178        KeyBytes(GenericArray::from(<[u8; 32]>::from(key_int)))
179    }
180}
181
182impl AsRef<KeyBytes> for KeyBytes {
183    fn as_ref(&self) -> &KeyBytes {
184        self
185    }
186}
187
188/// A distance between two keys in the DHT keyspace.
189#[derive(Copy, Clone, PartialEq, Eq, Default, PartialOrd, Ord, Debug)]
190pub struct Distance(pub(super) U256);
191
192impl Distance {
193    /// Returns the integer part of the base 2 logarithm of the [`Distance`].
194    ///
195    /// Returns `None` if the distance is zero.
196    pub fn ilog2(&self) -> Option<u32> {
197        (256 - self.0.leading_zeros()).checked_sub(1)
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204    use quickcheck::*;
205    use mwc_libp2p_core::multihash::Code;
206    use rand::Rng;
207
208    impl Arbitrary for Key<PeerId> {
209        fn arbitrary<G: Gen>(_: &mut G) -> Key<PeerId> {
210            Key::from(PeerId::random())
211        }
212    }
213
214    impl Arbitrary for Key<Multihash> {
215        fn arbitrary<G: Gen>(_: &mut G) -> Key<Multihash> {
216            let hash = rand::thread_rng().gen::<[u8; 32]>();
217            Key::from(Multihash::wrap(Code::Sha2_256.into(), &hash).unwrap())
218        }
219    }
220
221    #[test]
222    fn identity() {
223        fn prop(a: Key<PeerId>) -> bool {
224            a.distance(&a) == Distance::default()
225        }
226        quickcheck(prop as fn(_) -> _)
227    }
228
229    #[test]
230    fn symmetry() {
231        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
232            a.distance(&b) == b.distance(&a)
233        }
234        quickcheck(prop as fn(_,_) -> _)
235    }
236
237    #[test]
238    fn triangle_inequality() {
239        fn prop(a: Key<PeerId>, b: Key<PeerId>, c: Key<PeerId>) -> TestResult {
240            let ab = a.distance(&b);
241            let bc = b.distance(&c);
242            let (ab_plus_bc, overflow) = ab.0.overflowing_add(bc.0);
243            if overflow {
244                TestResult::discard()
245            } else {
246                TestResult::from_bool(a.distance(&c) <= Distance(ab_plus_bc))
247            }
248        }
249        quickcheck(prop as fn(_,_,_) -> _)
250    }
251
252    #[test]
253    fn unidirectionality() {
254        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
255            let d = a.distance(&b);
256            (0 .. 100).all(|_| {
257                let c = Key::from(PeerId::random());
258                a.distance(&c) != d || b == c
259            })
260        }
261        quickcheck(prop as fn(_,_) -> _)
262    }
263}
cs_mwc_libp2p_kad/kbucket/key.rs

cs_mwc_libp2p_kad/kbucket/
key.rs
