reth_dns_discovery/
tree.rs

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 of the entry used for signing:
126    ///
127    /// ```text
128    /// enrtree-root:v1 e=<enr-root> l=<link-root> seq=<sequence-number>
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/// Returns whether the value starts with a recognized EIP-1459 entry prefix.
345pub(crate) fn has_entry_prefix(value: &str) -> bool {
346    [ROOT_V1_PREFIX, BRANCH_PREFIX, LINK_PREFIX, ENR_PREFIX]
347        .iter()
348        .any(|prefix| value.starts_with(prefix))
349}
350
351/// Parses the value of the key value pair
352fn parse_value<F, V>(input: &mut &str, key: &str, err: &'static str, f: F) -> ParseEntryResult<V>
353where
354    F: Fn(&str) -> ParseEntryResult<V>,
355{
356    ensure_strip_key(input, key, err)?;
357    let val = input.split_whitespace().next().ok_or(FieldNotFound(err))?;
358    *input = &input[val.len()..];
359
360    f(val)
361}
362
363/// Strips the `key` from the `input`
364///
365/// Returns an err if the `input` does not start with the `key`
366fn ensure_strip_key(input: &mut &str, key: &str, err: &'static str) -> ParseEntryResult<()> {
367    *input = input.trim_start().strip_prefix(key).ok_or(FieldNotFound(err))?;
368    Ok(())
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374
375    #[test]
376    fn parse_root_entry() {
377        let s = "enrtree-root:v1 e=QFT4PBCRX4XQCV3VUYJ6BTCEPU l=JGUFMSAGI7KZYB3P7IZW4S5Y3A seq=3 sig=3FmXuVwpa8Y7OstZTx9PIb1mt8FrW7VpDOFv4AaGCsZ2EIHmhraWhe4NxYhQDlw5MjeFXYMbJjsPeKlHzmJREQE";
378        let root: TreeRootEntry = s.parse().unwrap();
379        assert_eq!(root.to_string(), s);
380
381        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
382            DnsEntry::Root(root) => {
383                assert_eq!(root.to_string(), s);
384            }
385            _ => unreachable!(),
386        }
387    }
388
389    #[test]
390    fn parse_branch_entry() {
391        let s = "enrtree-branch:CCCCCCCCCCCCCCCCCCCC,BBBBBBBBBBBBBBBBBBBB";
392        let entry: BranchEntry = s.parse().unwrap();
393        assert_eq!(entry.to_string(), s);
394
395        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
396            DnsEntry::Branch(entry) => {
397                assert_eq!(entry.to_string(), s);
398            }
399            _ => unreachable!(),
400        }
401    }
402    #[test]
403    fn parse_branch_entry_base32() {
404        let s = "enrtree-branch:YNEGZIWHOM7TOOSUATAPTM";
405        let entry: BranchEntry = s.parse().unwrap();
406        assert_eq!(entry.to_string(), s);
407
408        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
409            DnsEntry::Branch(entry) => {
410                assert_eq!(entry.to_string(), s);
411            }
412            _ => unreachable!(),
413        }
414    }
415
416    #[test]
417    fn parse_invalid_branch_entry() {
418        let s = "enrtree-branch:1,2";
419        let res = s.parse::<BranchEntry>();
420        assert!(res.is_err());
421        let s = "enrtree-branch:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
422        let res = s.parse::<BranchEntry>();
423        assert!(res.is_err());
424
425        let s = "enrtree-branch:,BBBBBBBBBBBBBBBBBBBB";
426        let res = s.parse::<BranchEntry>();
427        assert!(res.is_err());
428
429        let s = "enrtree-branch:CCCCCCCCCCCCCCCCCCCC\n,BBBBBBBBBBBBBBBBBBBB";
430        let res = s.parse::<BranchEntry>();
431        assert!(res.is_err());
432    }
433
434    #[test]
435    fn parse_link_entry() {
436        let s = "enrtree://AM5FCQLWIZX2QFPNJAP7VUERCCRNGRHWZG3YYHIUV7BVDQ5FDPRT2@nodes.example.org";
437        let entry: LinkEntry<SecretKey> = s.parse().unwrap();
438        assert_eq!(entry.to_string(), s);
439
440        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
441            DnsEntry::Link(entry) => {
442                assert_eq!(entry.to_string(), s);
443            }
444            _ => unreachable!(),
445        }
446    }
447
448    #[test]
449    fn parse_enr_entry() {
450        let s = "enr:-HW4QES8QIeXTYlDzbfr1WEzE-XKY4f8gJFJzjJL-9D7TC9lJb4Z3JPRRz1lP4pL_N_QpT6rGQjAU9Apnc-C1iMP36OAgmlkgnY0iXNlY3AyNTZrMaED5IdwfMxdmR8W37HqSFdQLjDkIwBd4Q_MjxgZifgKSdM";
451        let entry: NodeEntry<SecretKey> = s.parse().unwrap();
452        assert_eq!(entry.to_string(), s);
453
454        match s.parse::<DnsEntry<SecretKey>>().unwrap() {
455            DnsEntry::Node(entry) => {
456                assert_eq!(entry.to_string(), s);
457            }
458            _ => unreachable!(),
459        }
460    }
461}
reth_dns_discovery/tree.rs

reth_dns_discovery/
tree.rs
