reth_dns_discovery/
tree.rs

Help
1//! Support for the [EIP-1459 DNS Record Structure](https://eips.ethereum.org/EIPS/eip-1459#dns-record-structure)
2//!
3//! The nodes in a list are encoded as a merkle tree for distribution via the DNS protocol. Entries
4//! of the merkle tree are contained in DNS TXT records. The root of the tree is a TXT record with
5//! the following content:
6//!
7//! ```text
8//! enrtree-root:v1 e=<enr-root> l=<link-root> seq=<sequence-number> sig=<signature>
9//! ```
10//!
11//! where
12//!
13//!    enr-root and link-root refer to the root hashes of subtrees containing nodes and links to
14//! subtrees.
15//!   `sequence-number` is the tree’s update sequence number, a decimal integer.
16//!    `signature` is a 65-byte secp256k1 EC signature over the keccak256 hash of the record
17//! content, excluding the sig= part, encoded as URL-safe base64 (RFC-4648).
18
19use crate::error::{
20    ParseDnsEntryError,
21    ParseDnsEntryError::{FieldNotFound, UnknownEntry},
22    ParseEntryResult,
23};
24use alloy_primitives::{hex, Bytes};
25use data_encoding::{BASE32_NOPAD, BASE64URL_NOPAD};
26use enr::{Enr, EnrKey, EnrKeyUnambiguous, EnrPublicKey, Error as EnrError};
27use secp256k1::SecretKey;
28#[cfg(feature = "serde")]
29use serde_with::{DeserializeFromStr, SerializeDisplay};
30use std::{
31    fmt,
32    hash::{Hash, Hasher},
33    str::FromStr,
34};
35
36/// Prefix used for root entries in the ENR tree.
37const ROOT_V1_PREFIX: &str = "enrtree-root:v1";
38/// Prefix used for link entries in the ENR tree.
39const LINK_PREFIX: &str = "enrtree://";
40/// Prefix used for branch entries in the ENR tree.
41const BRANCH_PREFIX: &str = "enrtree-branch:";
42/// Prefix used for ENR entries in the ENR tree.
43const ENR_PREFIX: &str = "enr:";
44
45/// Represents all variants of DNS entries for Ethereum node lists.
46#[derive(Debug, Clone)]
47pub enum DnsEntry<K: EnrKeyUnambiguous> {
48    /// Represents a root entry in the DNS tree containing node records.
49    Root(TreeRootEntry),
50    /// Represents a link entry in the DNS tree pointing to another node list.
51    Link(LinkEntry<K>),
52    /// Represents a branch entry in the DNS tree containing hashes of subtree entries.
53    Branch(BranchEntry),
54    /// Represents a leaf entry in the DNS tree containing a node record.
55    Node(NodeEntry<K>),
56}
57
58impl<K: EnrKeyUnambiguous> fmt::Display for DnsEntry<K> {
59    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60        match self {
61            Self::Root(entry) => entry.fmt(f),
62            Self::Link(entry) => entry.fmt(f),
63            Self::Branch(entry) => entry.fmt(f),
64            Self::Node(entry) => entry.fmt(f),
65        }
66    }
67}
68
69impl<K: EnrKeyUnambiguous> FromStr for DnsEntry<K> {
70    type Err = ParseDnsEntryError;
71
72    fn from_str(s: &str) -> Result<Self, Self::Err> {
73        if let Some(s) = s.strip_prefix(ROOT_V1_PREFIX) {
74            TreeRootEntry::parse_value(s).map(DnsEntry::Root)
75        } else if let Some(s) = s.strip_prefix(BRANCH_PREFIX) {
76            BranchEntry::parse_value(s).map(DnsEntry::Branch)
77        } else if let Some(s) = s.strip_prefix(LINK_PREFIX) {
78            LinkEntry::parse_value(s).map(DnsEntry::Link)
79        } else if let Some(s) = s.strip_prefix(ENR_PREFIX) {
80            NodeEntry::parse_value(s).map(DnsEntry::Node)
81        } else {
82            Err(UnknownEntry(s.to_string()))
83        }
84    }
85}
86
87/// Represents an `enr-root` hash of subtrees containing nodes and links.
88#[derive(Clone, Eq, PartialEq)]
89pub struct TreeRootEntry {
90    /// The `enr-root` hash.
91    pub enr_root: String,
92    /// The root hash of the links.
93    pub link_root: String,
94    /// The sequence number associated with the entry.
95    pub sequence_number: u64,
96    /// The signature of the entry.
97    pub signature: Bytes,
98}
99
100// === impl TreeRootEntry ===
101
102impl TreeRootEntry {
103    /// Parses the entry from text.
104    ///
105    /// Caution: This assumes the prefix is already removed.
106    fn parse_value(mut input: &str) -> ParseEntryResult<Self> {
107        let input = &mut input;
108        let enr_root = parse_value(input, "e=", "ENR Root", |s| Ok(s.to_string()))?;
109        let link_root = parse_value(input, "l=", "Link Root", |s| Ok(s.to_string()))?;
110        let sequence_number = parse_value(input, "seq=", "Sequence number", |s| {
111            s.parse::<u64>().map_err(|_| {
112                ParseDnsEntryError::Other(format!("Failed to parse sequence number {s}"))
113            })
114        })?;
115        let signature = parse_value(input, "sig=", "Signature", |s| {
116            BASE64URL_NOPAD.decode(s.as_bytes()).map_err(|err| {
117                ParseDnsEntryError::Base64DecodeError(format!("signature error: {err}"))
118            })
119        })?
120        .into();
121
122        Ok(Self { enr_root, link_root, sequence_number, signature })
123    }
124
125    /// Returns the _unsigned_ content pairs of the entry:
126    ///
127    /// ```text
128    /// e=<enr-root> l=<link-root> seq=<sequence-number> sig=<signature>
129    /// ```
130    fn content(&self) -> String {
131        format!(
132            "{} e={} l={} seq={}",
133            ROOT_V1_PREFIX, self.enr_root, self.link_root, self.sequence_number
134        )
135    }
136
137    /// Signs the content with the given key
138    pub fn sign<K: EnrKey>(&mut self, key: &K) -> Result<(), EnrError> {
139        let sig = key.sign_v4(self.content().as_bytes()).map_err(|_| EnrError::SigningError)?;
140        self.signature = sig.into();
141        Ok(())
142    }
143
144    /// Verify the signature of the record.
145    #[must_use]
146    pub fn verify<K: EnrKey>(&self, pubkey: &K::PublicKey) -> bool {
147        let mut sig = self.signature.clone();
148        sig.truncate(64);
149        pubkey.verify_v4(self.content().as_bytes(), &sig)
150    }
151}
152
153impl FromStr for TreeRootEntry {
154    type Err = ParseDnsEntryError;
155
156    fn from_str(s: &str) -> Result<Self, Self::Err> {
157        if let Some(s) = s.strip_prefix(ROOT_V1_PREFIX) {
158            Self::parse_value(s)
159        } else {
160            Err(UnknownEntry(s.to_string()))
161        }
162    }
163}
164
165impl fmt::Debug for TreeRootEntry {
166    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167        f.debug_struct("TreeRootEntry")
168            .field("enr_root", &self.enr_root)
169            .field("link_root", &self.link_root)
170            .field("sequence_number", &self.sequence_number)
171            .field("signature", &hex::encode(self.signature.as_ref()))
172            .finish()
173    }
174}
175
176impl fmt::Display for TreeRootEntry {
177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178        write!(f, "{} sig={}", self.content(), BASE64URL_NOPAD.encode(self.signature.as_ref()))
179    }
180}
181
182/// Represents a branch entry in the DNS tree, containing base32 hashes of subtree entries.
183#[derive(Debug, Clone)]
184pub struct BranchEntry {
185    /// The list of base32-encoded hashes of subtree entries in the branch.
186    pub children: Vec<String>,
187}
188
189// === impl BranchEntry ===
190
191impl BranchEntry {
192    /// Parses the entry from text.
193    ///
194    /// Caution: This assumes the prefix is already removed.
195    fn parse_value(input: &str) -> ParseEntryResult<Self> {
196        #[inline]
197        fn ensure_valid_hash(hash: &str) -> ParseEntryResult<String> {
198            /// Returns the maximum length in bytes of the no-padding decoded data corresponding to
199            /// `n` bytes of base32-encoded data.
200            /// See also <https://cs.opensource.google/go/go/+/refs/tags/go1.19.5:src/encoding/base32/base32.go;l=526-531;drc=8a5845e4e34c046758af3729acf9221b8b6c01ae>
201            #[inline(always)]
202            const fn base32_no_padding_decoded_len(n: usize) -> usize {
203                n * 5 / 8
204            }
205
206            let decoded_len = base32_no_padding_decoded_len(hash.len());
207            if !(12..=32).contains(&decoded_len) || hash.chars().any(|c| c.is_whitespace()) {
208                return Err(ParseDnsEntryError::InvalidChildHash(hash.to_string()))
209            }
210            Ok(hash.to_string())
211        }
212
213        let children =
214            input.trim().split(',').map(ensure_valid_hash).collect::<ParseEntryResult<Vec<_>>>()?;
215        Ok(Self { children })
216    }
217}
218
219impl FromStr for BranchEntry {
220    type Err = ParseDnsEntryError;
221
222    fn from_str(s: &str) -> Result<Self, Self::Err> {
223        s.strip_prefix(BRANCH_PREFIX)
224            .map_or_else(|| Err(UnknownEntry(s.to_string())), Self::parse_value)
225    }
226}
227
228impl fmt::Display for BranchEntry {
229    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
230        write!(f, "{}{}", BRANCH_PREFIX, self.children.join(","))
231    }
232}
233
234/// Represents a link entry in the DNS tree, facilitating federation and web-of-trust functionality.
235#[derive(Debug, Clone)]
236#[cfg_attr(feature = "serde", derive(SerializeDisplay, DeserializeFromStr))]
237pub struct LinkEntry<K: EnrKeyUnambiguous = SecretKey> {
238    /// The domain associated with the link entry.
239    pub domain: String,
240    /// The public key corresponding to the Ethereum Node Record (ENR) used for the link entry.
241    pub pubkey: K::PublicKey,
242}
243
244// === impl LinkEntry ===
245
246impl<K: EnrKeyUnambiguous> LinkEntry<K> {
247    /// Parses the entry from text.
248    ///
249    /// Caution: This assumes the prefix is already removed.
250    fn parse_value(input: &str) -> ParseEntryResult<Self> {
251        let (pubkey, domain) = input.split_once('@').ok_or_else(|| {
252            ParseDnsEntryError::Other(format!("Missing @ delimiter in Link entry: {input}"))
253        })?;
254        let pubkey = K::decode_public(&BASE32_NOPAD.decode(pubkey.as_bytes()).map_err(|err| {
255            ParseDnsEntryError::Base32DecodeError(format!("pubkey error: {err}"))
256        })?)
257        .map_err(|err| ParseDnsEntryError::RlpDecodeError(err.to_string()))?;
258
259        Ok(Self { domain: domain.to_string(), pubkey })
260    }
261}
262
263impl<K> PartialEq for LinkEntry<K>
264where
265    K: EnrKeyUnambiguous,
266    K::PublicKey: PartialEq,
267{
268    fn eq(&self, other: &Self) -> bool {
269        self.domain == other.domain && self.pubkey == other.pubkey
270    }
271}
272
273impl<K> Eq for LinkEntry<K>
274where
275    K: EnrKeyUnambiguous,
276    K::PublicKey: Eq + PartialEq,
277{
278}
279impl<K> Hash for LinkEntry<K>
280where
281    K: EnrKeyUnambiguous,
282    K::PublicKey: Hash,
283{
284    fn hash<H: Hasher>(&self, state: &mut H) {
285        self.domain.hash(state);
286        self.pubkey.hash(state);
287    }
288}
289
290impl<K: EnrKeyUnambiguous> FromStr for LinkEntry<K> {
291    type Err = ParseDnsEntryError;
292
293    fn from_str(s: &str) -> Result<Self, Self::Err> {
294        s.strip_prefix(LINK_PREFIX)
295            .map_or_else(|| Err(UnknownEntry(s.to_string())), Self::parse_value)
296    }
297}
298
299impl<K: EnrKeyUnambiguous> fmt::Display for LinkEntry<K> {
300    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
301        write!(
302            f,
303            "{}{}@{}",
304            LINK_PREFIX,
305            BASE32_NOPAD.encode(self.pubkey.encode().as_ref()),
306            self.domain
307        )
308    }
309}
310
311/// Represents the actual Ethereum Node Record (ENR) entry in the DNS tree.
312#[derive(Debug, Clone)]
313pub struct NodeEntry<K: EnrKeyUnambiguous> {
314    /// The Ethereum Node Record (ENR) associated with the node entry.
315    pub enr: Enr<K>,
316}
317
318// === impl NodeEntry ===
319
320impl<K: EnrKeyUnambiguous> NodeEntry<K> {
321    /// Parses the entry from text.
322    ///
323    /// Caution: This assumes the prefix is already removed.
324    fn parse_value(s: &str) -> ParseEntryResult<Self> {
325        Ok(Self { enr: s.parse().map_err(ParseDnsEntryError::Other)? })
326    }
327}
328
329impl<K: EnrKeyUnambiguous> FromStr for NodeEntry<K> {
330    type Err = ParseDnsEntryError;
331
332    fn from_str(s: &str) -> Result<Self, Self::Err> {
333        s.strip_prefix(ENR_PREFIX)
334            .map_or_else(|| Err(UnknownEntry(s.to_string())), Self::parse_value)
335    }
336}
337
338impl<K: EnrKeyUnambiguous> fmt::Display for NodeEntry<K> {
339    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
340        self.enr.to_base64().fmt(f)
341    }
342}
343
344/// Parses the value of the key value pair
345fn parse_value<F, V>(input: &mut &str, key: &str, err: &'static str, f: F) -> ParseEntryResult<V>
346where
347    F: Fn(&str) -> ParseEntryResult<V>,
348{
349    ensure_strip_key(input, key, err)?;
350    let val = input.split_whitespace().next().ok_or(FieldNotFound(err))?;
351    *input = &input[val.len()..];
352
353    f(val)
354}
355
356/// Strips the `key` from the `input`
357///
358/// Returns an err if the `input` does not start with the `key`
359fn ensure_strip_key(input: &mut &str, key: &str, err: &'static str) -> ParseEntryResult<()> {
360    *input = input.trim_start().strip_prefix(key).ok_or(FieldNotFound(err))?;
361    Ok(())
362}
363
364#[cfg(test)]
365mod tests {
366    use super::*;
367
368    #[test]
369    fn parse_root_entry() {
370        let s = "enrtree-root:v1 e=QFT4PBCRX4XQCV3VUYJ6BTCEPU l=JGUFMSAGI7KZYB3P7IZW4S5Y3A seq=3 sig=3FmXuVwpa8Y7OstZTx9PIb1mt8FrW7VpDOFv4AaGCsZ2EIHmhraWhe4NxYhQDlw5MjeFXYMbJjsPeKlHzmJREQE";
371        let root: TreeRootEntry = s.parse().unwrap();
372        assert_eq!(root.to_string(), s);
373
374        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
375            DnsEntry::Root(root) => {
376                assert_eq!(root.to_string(), s);
377            }
378            _ => unreachable!(),
379        }
380    }
381
382    #[test]
383    fn parse_branch_entry() {
384        let s = "enrtree-branch:CCCCCCCCCCCCCCCCCCCC,BBBBBBBBBBBBBBBBBBBB";
385        let entry: BranchEntry = s.parse().unwrap();
386        assert_eq!(entry.to_string(), s);
387
388        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
389            DnsEntry::Branch(entry) => {
390                assert_eq!(entry.to_string(), s);
391            }
392            _ => unreachable!(),
393        }
394    }
395    #[test]
396    fn parse_branch_entry_base32() {
397        let s = "enrtree-branch:YNEGZIWHOM7TOOSUATAPTM";
398        let entry: BranchEntry = s.parse().unwrap();
399        assert_eq!(entry.to_string(), s);
400
401        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
402            DnsEntry::Branch(entry) => {
403                assert_eq!(entry.to_string(), s);
404            }
405            _ => unreachable!(),
406        }
407    }
408
409    #[test]
410    fn parse_invalid_branch_entry() {
411        let s = "enrtree-branch:1,2";
412        let res = s.parse::<BranchEntry>();
413        assert!(res.is_err());
414        let s = "enrtree-branch:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
415        let res = s.parse::<BranchEntry>();
416        assert!(res.is_err());
417
418        let s = "enrtree-branch:,BBBBBBBBBBBBBBBBBBBB";
419        let res = s.parse::<BranchEntry>();
420        assert!(res.is_err());
421
422        let s = "enrtree-branch:CCCCCCCCCCCCCCCCCCCC\n,BBBBBBBBBBBBBBBBBBBB";
423        let res = s.parse::<BranchEntry>();
424        assert!(res.is_err());
425    }
426
427    #[test]
428    fn parse_link_entry() {
429        let s = "enrtree://AM5FCQLWIZX2QFPNJAP7VUERCCRNGRHWZG3YYHIUV7BVDQ5FDPRT2@nodes.example.org";
430        let entry: LinkEntry<SecretKey> = s.parse().unwrap();
431        assert_eq!(entry.to_string(), s);
432
433        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
434            DnsEntry::Link(entry) => {
435                assert_eq!(entry.to_string(), s);
436            }
437            _ => unreachable!(),
438        }
439    }
440
441    #[test]
442    fn parse_enr_entry() {
443        let s = "enr:-HW4QES8QIeXTYlDzbfr1WEzE-XKY4f8gJFJzjJL-9D7TC9lJb4Z3JPRRz1lP4pL_N_QpT6rGQjAU9Apnc-C1iMP36OAgmlkgnY0iXNlY3AyNTZrMaED5IdwfMxdmR8W37HqSFdQLjDkIwBd4Q_MjxgZifgKSdM";
444        let entry: NodeEntry<SecretKey> = s.parse().unwrap();
445        assert_eq!(entry.to_string(), s);
446
447        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
448            DnsEntry::Node(entry) => {
449                assert_eq!(entry.to_string(), s);
450            }
451            _ => unreachable!(),
452        }
453    }
454}
reth_dns_discovery/tree.rs

reth_dns_discovery/
tree.rs
