Electroneum
difficulty.cpp
Go to the documentation of this file.
1 // Copyrights(c) 2017-2021, The Electroneum Project
2 // Copyrights(c) 2014-2019, The Monero Project
3 //
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without modification, are
7 // permitted provided that the following conditions are met:
8 //
9 // 1. Redistributions of source code must retain the above copyright notice, this list of
10 // conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 // of conditions and the following disclaimer in the documentation and/or other
14 // materials provided with the distribution.
15 //
16 // 3. Neither the name of the copyright holder nor the names of its contributors may be
17 // used to endorse or promote products derived from this software without specific
18 // prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
22 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
31 
32 #include <algorithm>
33 #include <cassert>
34 #include <cstddef>
35 #include <cstdint>
36 #include <vector>
37 
38 #include "int-util.h"
39 #include "crypto/hash.h"
40 #include "cryptonote_config.h"
41 #include "difficulty.h"
42 
43 #undef ELECTRONEUM_DEFAULT_LOG_CATEGORY
44 #define ELECTRONEUM_DEFAULT_LOG_CATEGORY "difficulty"
45 
46 namespace cryptonote {
47 
48  using std::size_t;
49  using std::uint64_t;
50  using std::vector;
51 
52 #if defined(__x86_64__)
53  static inline void mul(uint64_t a, uint64_t b, uint64_t &low, uint64_t &high) {
54  low = mul128(a, b, &high);
55  }
56 
57 #else
58 
59  static inline void mul(uint64_t a, uint64_t b, uint64_t &low, uint64_t &high) {
60  // __int128 isn't part of the standard, so the previous function wasn't portable. mul128() in Windows is fine,
61  // but this portable function should be used elsewhere. Credit for this function goes to latexi95.
62 
63  uint64_t aLow = a & 0xFFFFFFFF;
64  uint64_t aHigh = a >> 32;
65  uint64_t bLow = b & 0xFFFFFFFF;
66  uint64_t bHigh = b >> 32;
67 
68  uint64_t res = aLow * bLow;
69  uint64_t lowRes1 = res & 0xFFFFFFFF;
70  uint64_t carry = res >> 32;
71 
72  res = aHigh * bLow + carry;
73  uint64_t highResHigh1 = res >> 32;
74  uint64_t highResLow1 = res & 0xFFFFFFFF;
75 
76  res = aLow * bHigh;
77  uint64_t lowRes2 = res & 0xFFFFFFFF;
78  carry = res >> 32;
79 
80  res = aHigh * bHigh + carry;
81  uint64_t highResHigh2 = res >> 32;
82  uint64_t highResLow2 = res & 0xFFFFFFFF;
83 
84  //Addition
85 
86  uint64_t r = highResLow1 + lowRes2;
87  carry = r >> 32;
88  low = (r << 32) | lowRes1;
89  r = highResHigh1 + highResLow2 + carry;
90  uint64_t d3 = r & 0xFFFFFFFF;
91  carry = r >> 32;
92  r = highResHigh2 + carry;
93  high = d3 | (r << 32);
94  }
95 
96 #endif
97 
98  static inline bool cadd(uint64_t a, uint64_t b) {
99  return a + b < a;
100  }
101 
102  static inline bool cadc(uint64_t a, uint64_t b, bool c) {
103  return a + b < a || (c && a + b == (uint64_t) -1);
104  }
105 
106  bool check_hash_64(const crypto::hash &hash, uint64_t difficulty) {
107  uint64_t low, high, top, cur;
108  // First check the highest word, this will most likely fail for a random hash.
109  mul(swap64le(((const uint64_t *) &hash)[3]), difficulty, top, high);
110  if (high != 0) {
111  return false;
112  }
113  mul(swap64le(((const uint64_t *) &hash)[0]), difficulty, low, cur);
114  mul(swap64le(((const uint64_t *) &hash)[1]), difficulty, low, high);
115  bool carry = cadd(cur, low);
116  cur = high;
117  mul(swap64le(((const uint64_t *) &hash)[2]), difficulty, low, high);
118  carry = cadc(cur, low, carry);
119  carry = cadc(high, top, carry);
120  return !carry;
121  }
122 
123  uint64_t next_difficulty_64(std::vector<std::uint64_t> timestamps, std::vector<uint64_t> cumulative_difficulties, size_t target_seconds, uint8_t version) {
124 
125  const size_t difficultyWindow = version == 6 ? DIFFICULTY_WINDOW_V6 : DIFFICULTY_WINDOW;
126 
127  if(timestamps.size() > difficultyWindow)
128  {
129  timestamps.resize(difficultyWindow);
130  cumulative_difficulties.resize(difficultyWindow);
131  }
132 
133  size_t length = timestamps.size();
134  assert(length == cumulative_difficulties.size());
135  if (length <= 1) {
136  return 1;
137  }
138 
139  static_assert(DIFFICULTY_WINDOW >= 2, "Window is too small");
140  static_assert(DIFFICULTY_WINDOW_V6 >= 2, "Window is too small");
141  assert(length <= difficultyWindow);
142  sort(timestamps.begin(), timestamps.end());
143  size_t cut_begin, cut_end;
144 
145  static_assert(2 * DIFFICULTY_CUT <= DIFFICULTY_WINDOW - 2, "Cut length is too large");
146  static_assert(2 * DIFFICULTY_CUT <= DIFFICULTY_WINDOW_V6 - 2, "Cut length is too large");
147 
148  if (length <= difficultyWindow - 2 * DIFFICULTY_CUT) {
149  cut_begin = 0;
150  cut_end = length;
151  } else {
152  cut_begin = (length - (difficultyWindow - 2 * DIFFICULTY_CUT) + 1) / 2;
153  cut_end = cut_begin + (difficultyWindow - 2 * DIFFICULTY_CUT);
154  }
155  assert(/*cut_begin >= 0 &&*/ cut_begin + 2 <= cut_end && cut_end <= length);
156  uint64_t time_span = timestamps[cut_end - 1] - timestamps[cut_begin];
157  if (time_span == 0) {
158  time_span = 1;
159  }
160  uint64_t total_work = cumulative_difficulties[cut_end - 1] - cumulative_difficulties[cut_begin];
161  assert(total_work > 0);
162  uint64_t low, high;
163  mul(total_work, target_seconds, low, high);
164  // blockchain errors "difficulty overhead" if this function returns zero.
165  // TODO: consider throwing an exception instead
166  if (high != 0 || low + time_span - 1 < low) {
167  return 0;
168  }
169  return (low + time_span - 1) / time_span;
170  }
171 
172 #if defined(_MSC_VER)
173 #ifdef max
174 #undef max
175 #endif
176 #endif
177 
178  const difficulty_type max64bit(std::numeric_limits<std::uint64_t>::max());
179  const boost::multiprecision::uint256_t max128bit(std::numeric_limits<boost::multiprecision::uint128_t>::max());
180  const boost::multiprecision::uint512_t max256bit(std::numeric_limits<boost::multiprecision::uint256_t>::max());
181 
182 #define FORCE_FULL_128_BITS
183 
184  bool check_hash_128(const crypto::hash &hash, difficulty_type difficulty) {
185 #ifndef FORCE_FULL_128_BITS
186  // fast check
187  if (difficulty >= max64bit && ((const uint64_t *) &hash)[3] > 0)
188  return false;
189 #endif
190  // usual slow check
191  boost::multiprecision::uint512_t hashVal = 0;
192 #ifdef FORCE_FULL_128_BITS
193  for(int i = 0; i < 4; i++) { // highest word is zero
194 #else
195  for(int i = 1; i < 4; i++) { // highest word is zero
196 #endif
197  hashVal <<= 64;
198  hashVal |= swap64le(((const uint64_t *) &hash)[3 - i]);
199  }
200  return hashVal * difficulty <= max256bit;
201  }
202 
203  bool check_hash(const crypto::hash &hash, difficulty_type difficulty) {
204  if (difficulty <= max64bit) // if can convert to small difficulty - do it
205  return check_hash_64(hash, difficulty.convert_to<std::uint64_t>());
206  else
207  return check_hash_128(hash, difficulty);
208  }
209 
210  difficulty_type next_difficulty(std::vector<uint64_t> timestamps, std::vector<difficulty_type> cumulative_difficulties, size_t target_seconds, uint8_t version) {
211 
212  const size_t difficultyWindow = version == 6 ? DIFFICULTY_WINDOW_V6 : DIFFICULTY_WINDOW;
213 
214  //cutoff DIFFICULTY_LAG
215  if(timestamps.size() > difficultyWindow)
216  {
217  timestamps.resize(difficultyWindow);
218  cumulative_difficulties.resize(difficultyWindow);
219  }
220 
221 
222  size_t length = timestamps.size();
223  assert(length == cumulative_difficulties.size());
224  if (length <= 1) {
225  return 1;
226  }
227  static_assert(DIFFICULTY_WINDOW >= 2, "Window is too small");
228  static_assert(DIFFICULTY_WINDOW_V6 >= 2, "Window is too small");
229  assert(length <= difficultyWindow);
230  sort(timestamps.begin(), timestamps.end());
231  size_t cut_begin, cut_end;
232  static_assert(2 * DIFFICULTY_CUT <= DIFFICULTY_WINDOW - 2, "Cut length is too large");
233  static_assert(2 * DIFFICULTY_CUT <= DIFFICULTY_WINDOW_V6 - 2, "Cut length is too large");
234  if (length <= difficultyWindow - 2 * DIFFICULTY_CUT) {
235  cut_begin = 0;
236  cut_end = length;
237  } else {
238  cut_begin = (length - (difficultyWindow - 2 * DIFFICULTY_CUT) + 1) / 2;
239  cut_end = cut_begin + (difficultyWindow - 2 * DIFFICULTY_CUT);
240  }
241  assert(/*cut_begin >= 0 &&*/ cut_begin + 2 <= cut_end && cut_end <= length);
242  uint64_t time_span = timestamps[cut_end - 1] - timestamps[cut_begin];
243  if (time_span == 0) {
244  time_span = 1;
245  }
246  difficulty_type total_work = cumulative_difficulties[cut_end - 1] - cumulative_difficulties[cut_begin];
247  assert(total_work > 0);
248  boost::multiprecision::uint256_t res = (boost::multiprecision::uint256_t(total_work) * target_seconds + time_span - 1) / time_span;
249  if(res > max128bit)
250  return 0; // to behave like previous implementation, may be better return max128bit?
251  return res.convert_to<difficulty_type>();
252  }
253 
255  {
256  static const char chars[] = "0123456789abcdef";
257  std::string s;
258  while (v > 0)
259  {
260  s.push_back(chars[(v & 0xf).convert_to<unsigned>()]);
261  v >>= 4;
262  }
263  if (s.empty())
264  s += "0";
265  std::reverse(s.begin(), s.end());
266  return "0x" + s;
267  }
268 
269 }
const char * res
Definition: hmac_keccak.cpp:41
const boost::multiprecision::uint256_t max128bit(std::numeric_limits< boost::multiprecision::uint128_t >::max())
difficulty_type next_difficulty(std::vector< uint64_t > timestamps, std::vector< difficulty_type > cumulative_difficulties, size_t target_seconds, uint8_t version)
Definition: difficulty.cpp:210
::std::string string
Definition: gtest-port.h:1097
const difficulty_type max64bit(std::numeric_limits< std::uint64_t >::max())
unsigned char uint8_t
Definition: stdint.h:124
#define DIFFICULTY_WINDOW
#define swap64le
Definition: int-util.h:254
Holds cryptonote related classes and helpers.
Definition: ban.cpp:40
const boost::multiprecision::uint512_t max256bit(std::numeric_limits< boost::multiprecision::uint256_t >::max())
bool check_hash(const crypto::hash &hash, difficulty_type difficulty)
Definition: difficulty.cpp:203
unsigned __int64 uint64_t
Definition: stdint.h:136
#define DIFFICULTY_WINDOW_V6
version
Supported socks variants.
Definition: socks.h:57
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
bool check_hash_64(const crypto::hash &hash, uint64_t difficulty)
checks if a hash fits the given difficulty
Definition: difficulty.cpp:106
boost::multiprecision::uint128_t difficulty_type
Definition: difficulty.h:43
POD_CLASS hash
Definition: hash.h:50
std::string hex(difficulty_type v)
Definition: difficulty.cpp:254
bool check_hash_128(const crypto::hash &hash, difficulty_type difficulty)
Definition: difficulty.cpp:184
uint64_t next_difficulty_64(std::vector< std::uint64_t > timestamps, std::vector< uint64_t > cumulative_difficulties, size_t target_seconds, uint8_t version)
Definition: difficulty.cpp:123
#define DIFFICULTY_CUT