darkfi/event_graph/
event.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use std::{collections::HashSet, time::UNIX_EPOCH};
20
21use darkfi_serial::{async_trait, deserialize_async, Encodable, SerialDecodable, SerialEncodable};
22use sled_overlay::{sled, SledTreeOverlay};
23
24use crate::{event_graph::util::generate_genesis, Result};
25
26use super::{
27    util::next_rotation_timestamp, EventGraph, EVENT_TIME_DRIFT, INITIAL_GENESIS, NULL_ID,
28    N_EVENT_PARENTS,
29};
30
31#[derive(Debug, Clone, PartialEq, SerialEncodable, SerialDecodable)]
32pub struct Header {
33    /// Event version
34    // pub version: u8,
35    /// Timestamp of the event in milliseconds
36    pub timestamp: u64,
37    /// Parent nodes in the event DAG
38    pub parents: [blake3::Hash; N_EVENT_PARENTS],
39    /// DAG layer index of the event
40    pub layer: u64,
41}
42
43impl Header {
44    // Create a new Header given EventGraph to retrieve the correct layout
45    pub async fn new(event_graph: &EventGraph) -> Self {
46        let current_dag_name = event_graph.current_genesis.read().await.header.timestamp;
47        let (layer, parents) = event_graph.get_next_layer_with_parents(&current_dag_name).await;
48        Self { timestamp: UNIX_EPOCH.elapsed().unwrap().as_millis() as u64, parents, layer }
49    }
50
51    pub async fn new_static(event_graph: &EventGraph) -> Self {
52        let (layer, parents) = event_graph.get_next_layer_with_parents_static().await;
53        Self { timestamp: UNIX_EPOCH.elapsed().unwrap().as_millis() as u64, parents, layer }
54    }
55
56    pub async fn with_timestamp(timestamp: u64, event_graph: &EventGraph) -> Self {
57        let current_dag_name = event_graph.current_genesis.read().await.header.timestamp;
58        let (layer, parents) = event_graph.get_next_layer_with_parents(&current_dag_name).await;
59        Self { timestamp, parents, layer }
60    }
61
62    /// Hash the [`Header`] to retrieve its ID
63    pub fn id(&self) -> blake3::Hash {
64        let mut hasher = blake3::Hasher::new();
65        self.timestamp.encode(&mut hasher).unwrap();
66        self.parents.encode(&mut hasher).unwrap();
67        self.layer.encode(&mut hasher).unwrap();
68        hasher.finalize()
69    }
70
71    /// Fully validate a header for the correct layout against provided
72    /// DAG [`sled::Tree`] reference and enforce relevant age, assuming
73    /// some possibility for a time drift. Optionally, provide an overlay
74    /// to use that instead of actual referenced DAG.
75    pub async fn validate(
76        &self,
77        header_dag: &sled::Tree,
78        hours_rotation: u64,
79        overlay: Option<&SledTreeOverlay>,
80    ) -> Result<bool> {
81        // Check if the event is not older than the oldest genesis
82        let genesis_timestamp = generate_genesis(1).header.timestamp;
83        // A day ago genesis same hour
84        let oldest_genesis_ts = genesis_timestamp - 86_400_000u64;
85        if self.timestamp < oldest_genesis_ts - EVENT_TIME_DRIFT {
86            return Ok(false)
87        }
88
89        // If a rotation has been set, check if the event timestamp
90        // is after the next genesis timestamp
91        if hours_rotation > 0 {
92            let next_genesis_timestamp = next_rotation_timestamp(INITIAL_GENESIS, hours_rotation);
93            if self.timestamp > next_genesis_timestamp + EVENT_TIME_DRIFT {
94                return Ok(false)
95            }
96        }
97
98        // Validate the parents. We have to check that at least one parent
99        // is not NULL, that the parents exist, that no two parents are the
100        // same, and that the parent exists in previous layers, to prevent
101        // recursive references(circles).
102        let mut seen = HashSet::new();
103        let self_id = self.id();
104
105        for parent_id in self.parents.iter() {
106            if parent_id == &NULL_ID {
107                continue
108            }
109
110            if parent_id == &self_id {
111                return Ok(false)
112            }
113
114            if seen.contains(parent_id) {
115                return Ok(false)
116            }
117
118            let parent_bytes = if let Some(overlay) = overlay {
119                overlay.get(parent_id.as_bytes())?
120            } else {
121                header_dag.get(parent_id.as_bytes())?
122            };
123            if parent_bytes.is_none() {
124                return Ok(false)
125            }
126
127            let parent: Header = deserialize_async(&parent_bytes.unwrap()).await?;
128            if self.layer <= parent.layer {
129                return Ok(false)
130            }
131
132            seen.insert(parent_id);
133        }
134
135        Ok(!seen.is_empty())
136    }
137}
138
139/// Representation of an event in the Event Graph
140#[derive(Debug, Clone, PartialEq, SerialEncodable, SerialDecodable)]
141pub struct Event {
142    pub header: Header,
143    /// Content of the event
144    pub content: Vec<u8>,
145}
146
147impl Event {
148    /// Create a new event with the given data and an [`EventGraph`] reference.
149    /// The timestamp of the event will be the current time, and the parents
150    /// will be `N_EVENT_PARENTS` from the current event graph unreferenced tips.
151    /// The parents can also include NULL, but this should be handled by the rest
152    /// of the codebase.
153    pub async fn new(data: Vec<u8>, event_graph: &EventGraph) -> Self {
154        let header = Header::new(event_graph).await;
155        Self { header, content: data }
156    }
157
158    pub async fn new_static(data: Vec<u8>, event_graph: &EventGraph) -> Self {
159        let header = Header::new_static(event_graph).await;
160        Self { header, content: data }
161    }
162
163    pub fn id(&self) -> blake3::Hash {
164        self.header.id()
165    }
166
167    /// Same as `Event::new()` but allows specifying the timestamp explicitly.
168    pub async fn with_timestamp(timestamp: u64, data: Vec<u8>, event_graph: &EventGraph) -> Self {
169        let header = Header::with_timestamp(timestamp, event_graph).await;
170        Self { header, content: data }
171    }
172
173    /// Return a reference to the event's content
174    pub fn content(&self) -> &[u8] {
175        &self.content
176    }
177
178    /// Fully validate an event for the correct layout against provided
179    /// [`EventGraph`] reference and enforce relevant age, assuming some
180    /// possibility for a time drift.
181    pub async fn dag_validate(&self, header_dag: &sled::Tree) -> Result<bool> {
182        if self.content.is_empty() {
183            return Ok(false)
184        }
185        // Perform validation
186        self.header.validate(header_dag, 1, None).await
187    }
188
189    /// Validate a new event for the correct layout and enforce relevant age,
190    /// assuming some possibility for a time drift.
191    /// Note: This validation does *NOT* check for recursive references(circles),
192    /// and should be used as a first quick check.
193    pub fn validate_new(&self) -> bool {
194        // Let's not bother with empty events
195        if self.content.is_empty() {
196            return false
197        }
198
199        // Check if the event is too old or too new
200        let now = UNIX_EPOCH.elapsed().unwrap().as_millis() as u64;
201        let too_old = self.header.timestamp < now - EVENT_TIME_DRIFT;
202        let too_new = self.header.timestamp > now + EVENT_TIME_DRIFT;
203        if too_old || too_new {
204            return false
205        }
206
207        // Validate the parents. We have to check that at least one parent
208        // is not NULL and that no two parents are the same.
209        let mut seen = HashSet::new();
210        let self_id = self.header.id();
211
212        for parent_id in self.header.parents.iter() {
213            if parent_id == &NULL_ID {
214                continue
215            }
216
217            if parent_id == &self_id {
218                return false
219            }
220
221            if seen.contains(parent_id) {
222                return false
223            }
224
225            seen.insert(parent_id);
226        }
227
228        !seen.is_empty()
229    }
230}
231
232#[cfg(test)]
233mod tests {
234    use std::sync::Arc;
235
236    use smol::Executor;
237
238    use crate::{
239        event_graph::{EventGraph, EventGraphPtr},
240        net::{P2p, Settings},
241    };
242
243    use super::*;
244
245    async fn make_event_graph() -> Result<EventGraphPtr> {
246        let ex = Arc::new(Executor::new());
247        let p2p = P2p::new(Settings::default(), ex.clone()).await?;
248        let sled_db = sled::Config::new().temporary(true).open().unwrap();
249        EventGraph::new(p2p, sled_db, "/tmp".into(), false, false, 1, ex).await
250    }
251
252    #[test]
253    fn event_is_valid() -> Result<()> {
254        smol::block_on(async {
255            // Generate a dummy event graph
256            let event_graph = make_event_graph().await?;
257
258            let dag_name = event_graph.current_genesis.read().await.header.timestamp.to_string();
259            let hdr_tree_name = format!("headers_{dag_name}");
260            let header_dag = event_graph.dag_store.read().await.get_dag(&hdr_tree_name);
261
262            // Create a new valid event
263            let valid_event = Event::new(vec![1u8], &event_graph).await;
264
265            // Validate our test Event struct
266            assert!(valid_event.dag_validate(&header_dag).await?);
267
268            // Thanks for reading
269            Ok(())
270        })
271    }
272
273    #[test]
274    fn invalid_events() -> Result<()> {
275        smol::block_on(async {
276            // Generate a dummy event graph
277            let event_graph = make_event_graph().await?;
278
279            let dag_name = event_graph.current_genesis.read().await.header.timestamp.to_string();
280            let hdr_tree_name = format!("headers_{dag_name}");
281            let header_dag = event_graph.dag_store.read().await.get_dag(&hdr_tree_name);
282
283            // Create a new valid event
284            let valid_event = Event::new(vec![1u8], &event_graph).await;
285
286            let mut event_empty_content = valid_event.clone();
287            event_empty_content.content = vec![];
288            assert!(!event_empty_content.dag_validate(&header_dag).await?);
289
290            let mut event_timestamp_too_old = valid_event.clone();
291            event_timestamp_too_old.header.timestamp = 1000;
292            assert!(!event_timestamp_too_old.dag_validate(&header_dag).await?);
293
294            let mut event_timestamp_too_new = valid_event.clone();
295            event_timestamp_too_new.header.timestamp = u64::MAX;
296            assert!(!event_timestamp_too_new.dag_validate(&header_dag).await?);
297
298            let mut event_duplicated_parents = valid_event.clone();
299            event_duplicated_parents.header.parents[1] = valid_event.header.parents[0];
300            assert!(!event_duplicated_parents.dag_validate(&header_dag).await?);
301
302            let mut event_null_parents = valid_event.clone();
303            let all_null_parents = [NULL_ID, NULL_ID, NULL_ID, NULL_ID, NULL_ID];
304            event_null_parents.header.parents = all_null_parents;
305            assert!(!event_null_parents.dag_validate(&header_dag).await?);
306
307            let mut event_same_layer_as_parents = valid_event.clone();
308            event_same_layer_as_parents.header.layer = 0;
309            assert!(!event_same_layer_as_parents.dag_validate(&header_dag).await?);
310
311            // Thanks for reading
312            Ok(())
313        })
314    }
315}
darkfi/event_graph/event.rs

darkfi/event_graph/
event.rs
