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  //! Proof-of-Work using Equi-X
 20  //!
 21  //! <https://spec.torproject.org/hspow-spec/v1-equix.html>
 22  //! <https://github.com/tevador/equix/blob/master/devlog.md>
 23  //! <https://github.com/tevador/equix>
 24  
 25  use std::convert::AsRef;
 26  
 27  use blake2::{digest::consts::U4, Blake2b, Digest};
 28  pub use equix::{EquiXBuilder, HashError, RuntimeOption, Solution, SolverMemory};
 29  
 30  use darkfi::{Error, Result};
 31  
 32  /// Algorithm personalization string
 33  const P_STRING: &[u8] = b"DarkFi Equi-X\0";
 34  
 35  /// Length of the personalization string, in bytes
 36  const P_STRING_LEN: usize = 14;
 37  
 38  /// Length of the nonce value generated by clients and included in the solution
 39  pub const NONCE_LEN: usize = 16;
 40  
 41  /// A challenge string
 42  #[derive(Debug, Clone, Eq, PartialEq)]
 43  pub struct Challenge(Vec<u8>);
 44  
 45  impl Challenge {
 46      /// Build a new [`Challenge`].
 47      ///
 48      /// Copies `input` and `nonce` values into
 49      /// a new byte vector.
 50      pub fn new(input: &[u8], nonce: &[u8; NONCE_LEN]) -> Self {
 51          let mut result = Vec::<u8>::new();
 52          result.extend_from_slice(P_STRING);
 53          result.extend_from_slice(input.as_ref());
 54          result.extend_from_slice(nonce.as_ref());
 55  
 56          Self(result)
 57      }
 58  
 59      pub fn to_bytes(&self) -> Vec<u8> {
 60          self.0.clone()
 61      }
 62  
 63      /// Clone the input portion of this challenge.
 64      pub fn input(&self) -> Vec<u8> {
 65          self.0[P_STRING_LEN..(self.0.len() - NONCE_LEN)].into()
 66      }
 67  
 68      /// Clone the nonce portion of this challenge.
 69      pub fn nonce(&self) -> [u8; NONCE_LEN] {
 70          self.0[(self.0.len() - NONCE_LEN)..].try_into().expect("slice length correct")
 71      }
 72  
 73      /// Increment the nonce value inside this challenge.
 74      pub fn increment_nonce(&mut self) {
 75          fn inc_le_bytes(slice: &mut [u8]) {
 76              for byte in slice {
 77                  let (value, overflow) = (*byte).overflowing_add(1);
 78                  *byte = value;
 79                  if !overflow {
 80                      break;
 81                  }
 82              }
 83          }
 84          let len = self.0.len();
 85          inc_le_bytes(&mut self.0[(len - NONCE_LEN)..]);
 86      }
 87  
 88      /// Verify that a solution proof passes the effort test.
 89      pub fn check_effort(&self, proof: &equix::SolutionByteArray, effort: u32) -> bool {
 90          let mut hasher = Blake2b::<U4>::new();
 91          hasher.update(self.as_ref());
 92          hasher.update(proof.as_ref());
 93          let value = u32::from_be_bytes(hasher.finalize().into());
 94          value.checked_mul(effort).is_some()
 95      }
 96  }
 97  
 98  impl AsRef<[u8]> for Challenge {
 99      fn as_ref(&self) -> &[u8] {
100          self.0.as_ref()
101      }
102  }
103  
104  pub struct EquiXPow {
105      /// Target effort
106      pub effort: u32,
107      /// The next [`Challenge`] to try
108      pub challenge: Challenge,
109      /// Configuration settings for Equi-X
110      pub equix: EquiXBuilder,
111      /// Temporary memory for Equi-X to use
112      pub mem: SolverMemory,
113  }
114  
115  impl EquiXPow {
116      pub fn run(&mut self) -> Result<Solution> {
117          loop {
118              if let Some(solution) = self.run_step()? {
119                  return Ok(solution);
120              }
121          }
122      }
123  
124      pub fn run_step(&mut self) -> Result<Option<Solution>> {
125          match self.equix.build(self.challenge.as_ref()) {
126              Ok(equix) => {
127                  for candidate in equix.solve_with_memory(&mut self.mem) {
128                      if self.challenge.check_effort(&candidate.to_bytes(), self.effort) {
129                          return Ok(Some(candidate))
130                      }
131                  }
132              }
133              Err(equix::Error::Hash(HashError::ProgramConstraints)) => (),
134              Err(e) => {
135                  return Err(Error::Custom(e.to_string()));
136              }
137          };
138          self.challenge.increment_nonce();
139          Ok(None)
140      }
141  
142      pub fn verify(&self, challenge: &Challenge, solution: &Solution) -> Result<()> {
143          if challenge.check_effort(&solution.to_bytes(), self.effort) {
144              return self
145                  .equix
146                  .verify(challenge.as_ref(), solution)
147                  .map_err(|e| Error::Custom(e.to_string()))
148          }
149          Err(Error::Custom("Equi-X solution has insufficient effort".into()))
150      }
151  }