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

ant_libp2p_kad/kbucket/
key.rs
