1  /* This file is part of DarkFi (https://dark.fi)
  2   *
  3   * Copyright (C) 2020-2025 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  
 19  use std::{
 20      sync::{
 21          atomic::{AtomicBool, AtomicU64, Ordering},
 22          Arc,
 23      },
 24      thread,
 25      time::Instant,
 26  };
 27  
 28  use darkfi_sdk::num_traits::{One, Zero};
 29  use num_bigint::BigUint;
 30  use randomx::{RandomXCache, RandomXDataset, RandomXFlags, RandomXVM};
 31  use smol::channel::Receiver;
 32  use tracing::debug;
 33  
 34  use crate::{
 35      blockchain::{
 36          block_store::{BlockDifficulty, BlockInfo},
 37          Blockchain, BlockchainOverlayPtr,
 38      },
 39      util::{ringbuffer::RingBuffer, time::Timestamp},
 40      validator::utils::median,
 41      Error, Result,
 42  };
 43  
 44  // Note: We have combined some constants for better performance.
 45  /// Amount of max items(blocks) to use for next difficulty calculation.
 46  /// Must be >= 2 and == BUF_SIZE - DIFFICULTY_LAG.
 47  const DIFFICULTY_WINDOW: usize = 720;
 48  /// Amount of latest blocks to exlude from the calculation.
 49  /// Our ring buffer has length: DIFFICULTY_WINDOW + DIFFICULTY_LAG,
 50  /// but we only use DIFFICULTY_WINDOW items in calculations.
 51  /// Must be == BUF_SIZE - DIFFICULTY_WINDOW.
 52  const _DIFFICULTY_LAG: usize = 15;
 53  /// Ring buffer length.
 54  /// Must be == DIFFICULTY_WINDOW + DIFFICULTY_LAG
 55  const BUF_SIZE: usize = 735;
 56  /// Used to calculate how many items to retain for next difficulty
 57  /// calculation. We are keeping the middle items, meaning cutting
 58  /// both from frond and back of the ring buffer, ending up with max
 59  /// DIFFICULTY_WINDOW - 2*DIFFICULTY_CUT items.
 60  /// (2*DIFFICULTY_CUT <= DIFFICULTY_WINDOW-2) must be true.
 61  const _DIFFICULTY_CUT: usize = 60;
 62  /// Max items to use for next difficulty calculation.
 63  /// Must be DIFFICULTY_WINDOW - 2 * DIFFICULTY_CUT
 64  const RETAINED: usize = 600;
 65  /// Already known cutoff start index for this config
 66  const CUT_BEGIN: usize = 60;
 67  /// Already known cutoff end index for this config
 68  const CUT_END: usize = 660;
 69  /// How many most recent blocks to use to verify new blocks' timestamp
 70  const BLOCKCHAIN_TIMESTAMP_CHECK_WINDOW: usize = 60;
 71  /// Time limit in the future of what blocks can be
 72  const BLOCK_FUTURE_TIME_LIMIT: Timestamp = Timestamp::from_u64(60 * 60 * 2);
 73  
 74  /// This struct represents the information required by the PoW algorithm
 75  #[derive(Clone)]
 76  pub struct PoWModule {
 77      /// Genesis block timestamp
 78      pub genesis: Timestamp,
 79      /// Target block time, in seconds
 80      pub target: u32,
 81      /// Optional fixed difficulty
 82      pub fixed_difficulty: Option<BigUint>,
 83      /// Latest block timestamps ringbuffer
 84      pub timestamps: RingBuffer<Timestamp, BUF_SIZE>,
 85      /// Latest block cumulative difficulties ringbuffer
 86      pub difficulties: RingBuffer<BigUint, BUF_SIZE>,
 87      /// Total blocks cumulative difficulty
 88      /// Note: we keep this as a struct field for faster
 89      /// access(optimization), since its always same as
 90      /// difficulties buffer last.
 91      pub cumulative_difficulty: BigUint,
 92  }
 93  
 94  impl PoWModule {
 95      // Initialize a new `PowModule` for provided target over provided `Blockchain`.
 96      // Optionally, a fixed difficulty can be set and/or initialize before some height.
 97      pub fn new(
 98          blockchain: Blockchain,
 99          target: u32,
100          fixed_difficulty: Option<BigUint>,
101          height: Option<u32>,
102      ) -> Result<Self> {
103          // Retrieve genesis block timestamp
104          let genesis = blockchain.genesis_block()?.header.timestamp;
105  
106          // Retrieving last BUF_SIZE difficulties from blockchain to build the buffers
107          let mut timestamps = RingBuffer::<Timestamp, BUF_SIZE>::new();
108          let mut difficulties = RingBuffer::<BigUint, BUF_SIZE>::new();
109          let mut cumulative_difficulty = BigUint::zero();
110          let last_n = match height {
111              Some(h) => blockchain.blocks.get_difficulties_before(h, BUF_SIZE)?,
112              None => blockchain.blocks.get_last_n_difficulties(BUF_SIZE)?,
113          };
114          for difficulty in last_n {
115              timestamps.push(difficulty.timestamp);
116              difficulties.push(difficulty.cumulative_difficulty.clone());
117              cumulative_difficulty = difficulty.cumulative_difficulty;
118          }
119  
120          // If a fixed difficulty has been set, assert its greater than zero
121          if let Some(diff) = &fixed_difficulty {
122              assert!(diff > &BigUint::zero());
123          }
124  
125          Ok(Self {
126              genesis,
127              target,
128              fixed_difficulty,
129              timestamps,
130              difficulties,
131              cumulative_difficulty,
132          })
133      }
134  
135      /// Compute the next mining difficulty, based on current ring buffers.
136      /// If ring buffers contain 2 or less items, difficulty 1 is returned.
137      /// If a fixed difficulty has been set, this function will always
138      /// return that after first 2 difficulties.
139      pub fn next_difficulty(&self) -> Result<BigUint> {
140          // Retrieve first DIFFICULTY_WINDOW timestamps from the ring buffer
141          let mut timestamps: Vec<Timestamp> =
142              self.timestamps.iter().take(DIFFICULTY_WINDOW).cloned().collect();
143  
144          // Check we have enough timestamps
145          let length = timestamps.len();
146          if length < 2 {
147              return Ok(BigUint::one())
148          }
149  
150          // If a fixed difficulty has been set, return that
151          if let Some(diff) = &self.fixed_difficulty {
152              return Ok(diff.clone())
153          }
154  
155          // Sort the timestamps vector
156          timestamps.sort_unstable();
157  
158          // Grab cutoff indexes
159          let (cut_begin, cut_end) = self.cutoff(length)?;
160  
161          // Calculate total time span
162          let cut_end = cut_end - 1;
163  
164          let mut time_span = timestamps[cut_end].checked_sub(timestamps[cut_begin])?;
165          if time_span.inner() == 0 {
166              time_span = 1.into();
167          }
168  
169          // Calculate total work done during this time span
170          let total_work = &self.difficulties[cut_end] - &self.difficulties[cut_begin];
171          if total_work <= BigUint::zero() {
172              return Err(Error::PoWTotalWorkIsZero)
173          }
174  
175          // Compute next difficulty
176          let next_difficulty =
177              (total_work * self.target + time_span.inner() - BigUint::one()) / time_span.inner();
178  
179          Ok(next_difficulty)
180      }
181  
182      /// Calculate cutoff indexes.
183      /// If buffers have been filled, we return the
184      /// already known indexes, for performance.
185      fn cutoff(&self, length: usize) -> Result<(usize, usize)> {
186          if length >= DIFFICULTY_WINDOW {
187              return Ok((CUT_BEGIN, CUT_END))
188          }
189  
190          let (cut_begin, cut_end) = if length <= RETAINED {
191              (0, length)
192          } else {
193              let cut_begin = (length - RETAINED).div_ceil(2);
194              (cut_begin, cut_begin + RETAINED)
195          };
196          // Sanity check
197          if
198          /* cut_begin < 0 || */
199          cut_begin + 2 > cut_end || cut_end > length {
200              return Err(Error::PoWCuttofCalculationError)
201          }
202  
203          Ok((cut_begin, cut_end))
204      }
205  
206      /// Compute the next mine target.
207      pub fn next_mine_target(&self) -> Result<BigUint> {
208          Ok(BigUint::from_bytes_be(&[0xFF; 32]) / &self.next_difficulty()?)
209      }
210  
211      /// Compute the next mine target and difficulty.
212      pub fn next_mine_target_and_difficulty(&self) -> Result<(BigUint, BigUint)> {
213          let difficulty = self.next_difficulty()?;
214          let mine_target = BigUint::from_bytes_be(&[0xFF; 32]) / &difficulty;
215          Ok((mine_target, difficulty))
216      }
217  
218      /// Verify provided difficulty corresponds to the next one.
219      pub fn verify_difficulty(&self, difficulty: &BigUint) -> Result<bool> {
220          Ok(difficulty == &self.next_difficulty()?)
221      }
222  
223      /// Verify provided block timestamp is not far in the future and
224      /// check its valid acorrding to current timestamps median.
225      pub fn verify_current_timestamp(&self, timestamp: Timestamp) -> Result<bool> {
226          if timestamp > Timestamp::current_time().checked_add(BLOCK_FUTURE_TIME_LIMIT)? {
227              return Ok(false)
228          }
229  
230          Ok(self.verify_timestamp_by_median(timestamp))
231      }
232  
233      /// Verify provided block timestamp is valid and matches certain criteria.
234      pub fn verify_timestamp_by_median(&self, timestamp: Timestamp) -> bool {
235          // Check timestamp is after genesis one
236          if timestamp <= self.genesis {
237              return false
238          }
239  
240          // If not enough blocks, no proper median yet, return true
241          if self.timestamps.len() < BLOCKCHAIN_TIMESTAMP_CHECK_WINDOW {
242              return true
243          }
244  
245          // Make sure the timestamp is higher or equal to the median
246          let timestamps = self
247              .timestamps
248              .iter()
249              .rev()
250              .take(BLOCKCHAIN_TIMESTAMP_CHECK_WINDOW)
251              .map(|x| x.inner())
252              .collect();
253  
254          timestamp >= median(timestamps).into()
255      }
256  
257      /// Verify provided block timestamp and hash.
258      pub fn verify_current_block(&self, block: &BlockInfo) -> Result<()> {
259          // First we verify the block's timestamp
260          if !self.verify_current_timestamp(block.header.timestamp)? {
261              return Err(Error::PoWInvalidTimestamp)
262          }
263  
264          // Then we verify the block's hash
265          self.verify_block_hash(block)
266      }
267  
268      /// Verify provided block corresponds to next mine target.
269      // TODO: Verify depending on block Proof of Work data
270      pub fn verify_block_hash(&self, block: &BlockInfo) -> Result<()> {
271          let verifier_setup = Instant::now();
272  
273          // Grab the next mine target
274          let target = self.next_mine_target()?;
275  
276          // Setup verifier
277          let flags = RandomXFlags::default();
278          let cache = RandomXCache::new(flags, block.header.previous.inner()).unwrap();
279          let vm = RandomXVM::new(flags, &cache).unwrap();
280          debug!(target: "validator::pow::verify_block", "[VERIFIER] Setup time: {:?}", verifier_setup.elapsed());
281  
282          // Compute the output hash
283          let verification_time = Instant::now();
284          let out_hash = vm.hash(block.header.hash().inner());
285          let out_hash = BigUint::from_bytes_be(&out_hash);
286  
287          // Verify hash is less than the expected mine target
288          if out_hash > target {
289              return Err(Error::PoWInvalidOutHash)
290          }
291          debug!(target: "validator::pow::verify_block", "[VERIFIER] Verification time: {:?}", verification_time.elapsed());
292  
293          Ok(())
294      }
295  
296      /// Append provided timestamp and difficulty to the ring buffers.
297      pub fn append(&mut self, timestamp: Timestamp, difficulty: &BigUint) {
298          self.timestamps.push(timestamp);
299          self.cumulative_difficulty += difficulty;
300          self.difficulties.push(self.cumulative_difficulty.clone());
301      }
302  
303      /// Append provided block difficulty to the ring buffers and insert
304      /// it to provided overlay.
305      pub fn append_difficulty(
306          &mut self,
307          overlay: &BlockchainOverlayPtr,
308          difficulty: BlockDifficulty,
309      ) -> Result<()> {
310          self.append(difficulty.timestamp, &difficulty.difficulty);
311          overlay.lock().unwrap().blocks.insert_difficulty(&[difficulty])
312      }
313  
314      /// Mine provided block, based on next mine target.
315      pub fn mine_block(
316          &self,
317          miner_block: &mut BlockInfo,
318          threads: usize,
319          stop_signal: &Receiver<()>,
320      ) -> Result<()> {
321          // Grab the next mine target
322          let target = self.next_mine_target()?;
323  
324          mine_block(&target, miner_block, threads, stop_signal)
325      }
326  }
327  
328  impl std::fmt::Display for PoWModule {
329      fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
330          write!(f, "PoWModule:")?;
331          write!(f, "\ttarget: {}", self.target)?;
332          write!(f, "\ttimestamps: {:?}", self.timestamps)?;
333          write!(f, "\tdifficulties: {:?}", self.difficulties)?;
334          write!(f, "\tcumulative_difficulty: {}", self.cumulative_difficulty)
335      }
336  }
337  
338  /// Mine provided block, based on provided PoW module next mine target.
339  pub fn mine_block(
340      target: &BigUint,
341      miner_block: &mut BlockInfo,
342      threads: usize,
343      stop_signal: &Receiver<()>,
344  ) -> Result<()> {
345      let miner_setup = Instant::now();
346  
347      debug!(target: "validator::pow::mine_block", "[MINER] Mine target: 0x{target:064x}");
348      // Get the PoW input. The key changes with every mined block.
349      let input = miner_block.header.previous;
350      debug!(target: "validator::pow::mine_block", "[MINER] PoW input: {input}");
351      let flags = RandomXFlags::default() | RandomXFlags::FULLMEM;
352      debug!(target: "validator::pow::mine_block", "[MINER] Initializing RandomX dataset...");
353      let dataset = Arc::new(RandomXDataset::new(flags, input.inner(), threads).unwrap());
354      debug!(target: "validator::pow::mine_block", "[MINER] Setup time: {:?}", miner_setup.elapsed());
355  
356      // Multithreaded mining setup
357      let mining_time = Instant::now();
358      let mut handles = vec![];
359      let found_block = Arc::new(AtomicBool::new(false));
360      let found_nonce = Arc::new(AtomicU64::new(0));
361      let threads = threads as u64;
362      for t in 0..threads {
363          let target = target.clone();
364          let mut block = miner_block.clone();
365          let found_block = Arc::clone(&found_block);
366          let found_nonce = Arc::clone(&found_nonce);
367          let dataset = Arc::clone(&dataset);
368          let stop_signal = stop_signal.clone();
369  
370          handles.push(thread::spawn(move || {
371              debug!(target: "validator::pow::mine_block", "[MINER] Initializing RandomX VM #{t}...");
372              let mut miner_nonce = t;
373              let vm = RandomXVM::new_fast(flags, &dataset).unwrap();
374              loop {
375                  // Check if stop signal was received
376                  if stop_signal.is_full() {
377                      debug!(target: "validator::pow::mine_block", "[MINER] Stop signal received, thread #{t} exiting");
378                      break
379                  }
380  
381                  block.header.nonce = miner_nonce;
382                  if found_block.load(Ordering::SeqCst) {
383                      debug!(target: "validator::pow::mine_block", "[MINER] Block found, thread #{t} exiting");
384                      break
385                  }
386  
387                  let out_hash = vm.hash(block.hash().inner());
388                  let out_hash = BigUint::from_bytes_be(&out_hash);
389                  if out_hash <= target {
390                      found_block.store(true, Ordering::SeqCst);
391                      found_nonce.store(miner_nonce, Ordering::SeqCst);
392                      debug!(target: "validator::pow::mine_block", "[MINER] Thread #{t} found block using nonce {miner_nonce}");
393                      debug!(target: "validator::pow::mine_block", "[MINER] Block hash {}", block.hash());
394                      debug!(target: "validator::pow::mine_block", "[MINER] RandomX output: 0x{out_hash:064x}");
395                      break
396                  }
397  
398                  // This means thread 0 will use nonces, 0, 4, 8, ...
399                  // and thread 1 will use nonces, 1, 5, 9, ...
400                  miner_nonce += threads;
401              }
402          }));
403      }
404  
405      for handle in handles {
406          let _ = handle.join();
407      }
408      // Check if stop signal was received
409      if stop_signal.is_full() {
410          return Err(Error::MinerTaskStopped)
411      }
412  
413      debug!(target: "validator::pow::mine_block", "[MINER] Mining time: {:?}", mining_time.elapsed());
414  
415      // Set the valid mined nonce in the block
416      miner_block.header.nonce = found_nonce.load(Ordering::SeqCst);
417  
418      Ok(())
419  }
420  
421  #[cfg(test)]
422  mod tests {
423      use std::{
424          io::{BufRead, Cursor},
425          process::Command,
426      };
427  
428      use darkfi_sdk::num_traits::Num;
429      use num_bigint::BigUint;
430      use sled_overlay::sled;
431  
432      use crate::{
433          blockchain::{BlockInfo, Blockchain},
434          Result,
435      };
436  
437      use super::PoWModule;
438  
439      const DEFAULT_TEST_THREADS: usize = 2;
440      const DEFAULT_TEST_DIFFICULTY_TARGET: u32 = 120;
441  
442      #[test]
443      fn test_wide_difficulty() -> Result<()> {
444          let sled_db = sled::Config::new().temporary(true).open()?;
445          let blockchain = Blockchain::new(&sled_db)?;
446          let genesis_block = BlockInfo::default();
447          blockchain.add_block(&genesis_block)?;
448          let mut module = PoWModule::new(blockchain, DEFAULT_TEST_DIFFICULTY_TARGET, None, None)?;
449  
450          let output = Command::new("./script/research/pow/gen_wide_data.py").output().unwrap();
451          let reader = Cursor::new(output.stdout);
452  
453          for (n, line) in reader.lines().enumerate() {
454              let line = line.unwrap();
455              let parts: Vec<String> = line.split(' ').map(|x| x.to_string()).collect();
456              assert!(parts.len() == 2);
457  
458              let timestamp = parts[0].parse::<u64>().unwrap().into();
459              let difficulty = BigUint::from_str_radix(&parts[1], 10).unwrap();
460  
461              let res = module.next_difficulty()?;
462  
463              if res != difficulty {
464                  eprintln!("Wrong wide difficulty for block {n}");
465                  eprintln!("Expected: {difficulty}");
466                  eprintln!("Found: {res}");
467                  assert!(res == difficulty);
468              }
469  
470              module.append(timestamp, &difficulty);
471          }
472  
473          Ok(())
474      }
475  
476      #[test]
477      fn test_miner_correctness() -> Result<()> {
478          // Default setup
479          let sled_db = sled::Config::new().temporary(true).open()?;
480          let blockchain = Blockchain::new(&sled_db)?;
481          let mut genesis_block = BlockInfo::default();
482          genesis_block.header.timestamp = 0.into();
483          blockchain.add_block(&genesis_block)?;
484          let module = PoWModule::new(blockchain, DEFAULT_TEST_DIFFICULTY_TARGET, None, None)?;
485          let (_, recvr) = smol::channel::bounded(1);
486  
487          // Mine next block
488          let mut next_block = BlockInfo::default();
489          next_block.header.previous = genesis_block.hash();
490          module.mine_block(&mut next_block, DEFAULT_TEST_THREADS, &recvr)?;
491  
492          // Verify it
493          module.verify_current_block(&next_block)?;
494  
495          Ok(())
496      }
497  }