1 // ethash: C/C++ implementation of Ethash, the Ethereum Proof of Work algorithm.
2 // Copyright 2018 Pawel Bylica.
3 // Licensed under the Apache License, Version 2.0. See the LICENSE file.
4
5 #include "ethash-internal.hpp"
6
7 #include "bit_manipulation.h"
8 #include "endianness.hpp"
9 #include "primes.h"
10 #include "support/attributes.h"
11 #include <ethash/keccak.hpp>
12 #include <ethash/progpow.hpp>
13
14 #include <cassert>
15 #include <cstdlib>
16 #include <cstring>
17 #include <limits>
18
19 namespace ethash
20 {
21 // Internal constants:
22 constexpr static int light_cache_init_size = 1 << 24;
23 constexpr static int light_cache_growth = 1 << 17;
24 constexpr static int light_cache_rounds = 3;
25 constexpr static int full_dataset_init_size = 1 << 30;
26 constexpr static int full_dataset_growth = 1 << 23;
27 constexpr static int full_dataset_item_parents = 256;
28
29 // Verify constants:
30 static_assert(sizeof(hash512) == ETHASH_LIGHT_CACHE_ITEM_SIZE, "");
31 static_assert(sizeof(hash1024) == ETHASH_FULL_DATASET_ITEM_SIZE, "");
32 static_assert(light_cache_item_size == ETHASH_LIGHT_CACHE_ITEM_SIZE, "");
33 static_assert(full_dataset_item_size == ETHASH_FULL_DATASET_ITEM_SIZE, "");
34
35
36 namespace
37 {
38 using ::fnv1;
39
fnv1(const hash512 & u,const hash512 & v)40 inline hash512 fnv1(const hash512& u, const hash512& v) noexcept
41 {
42 hash512 r;
43 for (size_t i = 0; i < sizeof(r) / sizeof(r.word32s[0]); ++i)
44 r.word32s[i] = fnv1(u.word32s[i], v.word32s[i]);
45 return r;
46 }
47
bitwise_xor(const hash512 & x,const hash512 & y)48 inline hash512 bitwise_xor(const hash512& x, const hash512& y) noexcept
49 {
50 hash512 z;
51 for (size_t i = 0; i < sizeof(z) / sizeof(z.word64s[0]); ++i)
52 z.word64s[i] = x.word64s[i] ^ y.word64s[i];
53 return z;
54 }
55 } // namespace
56
find_epoch_number(const hash256 & seed)57 int find_epoch_number(const hash256& seed) noexcept
58 {
59 static constexpr int num_tries = 30000; // Divisible by 16.
60
61 // Thread-local cache of the last search.
62 static thread_local int cached_epoch_number = 0;
63 static thread_local hash256 cached_seed = {};
64
65 // Load from memory once (memory will be clobbered by keccak256()).
66 const uint32_t seed_part = seed.word32s[0];
67 const int e = cached_epoch_number;
68 hash256 s = cached_seed;
69
70 if (s.word32s[0] == seed_part)
71 return e;
72
73 // Try the next seed, will match for sequential epoch access.
74 s = keccak256(s);
75 if (s.word32s[0] == seed_part)
76 {
77 cached_seed = s;
78 cached_epoch_number = e + 1;
79 return e + 1;
80 }
81
82 // Search for matching seed starting from epoch 0.
83 s = {};
84 for (int i = 0; i < num_tries; ++i)
85 {
86 if (s.word32s[0] == seed_part)
87 {
88 cached_seed = s;
89 cached_epoch_number = i;
90 return i;
91 }
92
93 s = keccak256(s);
94 }
95
96 return -1;
97 }
98
99 namespace generic
100 {
build_light_cache(hash_fn_512 hash_fn,hash512 cache[],int num_items,const hash256 & seed)101 void build_light_cache(
102 hash_fn_512 hash_fn, hash512 cache[], int num_items, const hash256& seed) noexcept
103 {
104 hash512 item = hash_fn(seed.bytes, sizeof(seed));
105 cache[0] = item;
106 for (int i = 1; i < num_items; ++i)
107 {
108 item = hash_fn(item.bytes, sizeof(item));
109 cache[i] = item;
110 }
111
112 for (int q = 0; q < light_cache_rounds; ++q)
113 {
114 for (int i = 0; i < num_items; ++i)
115 {
116 const uint32_t index_limit = static_cast<uint32_t>(num_items);
117
118 // Fist index: 4 first bytes of the item as little-endian integer.
119 const uint32_t t = le::uint32(cache[i].word32s[0]);
120 const uint32_t v = t % index_limit;
121
122 // Second index.
123 const uint32_t w = static_cast<uint32_t>(num_items + (i - 1)) % index_limit;
124
125 const hash512 x = bitwise_xor(cache[v], cache[w]);
126 cache[i] = hash_fn(x.bytes, sizeof(x));
127 }
128 }
129 }
130
create_epoch_context(build_light_cache_fn build_fn,int epoch_number,bool full)131 epoch_context_full* create_epoch_context(
132 build_light_cache_fn build_fn, int epoch_number, bool full) noexcept
133 {
134 static_assert(sizeof(epoch_context_full) < sizeof(hash512), "epoch_context too big");
135 static constexpr size_t context_alloc_size = sizeof(hash512);
136
137 const int light_cache_num_items = calculate_light_cache_num_items(epoch_number);
138 const int full_dataset_num_items = calculate_full_dataset_num_items(epoch_number);
139 const size_t light_cache_size = get_light_cache_size(light_cache_num_items);
140 const size_t full_dataset_size =
141 full ? static_cast<size_t>(full_dataset_num_items) * sizeof(hash1024) :
142 progpow::l1_cache_size;
143
144 const size_t alloc_size = context_alloc_size + light_cache_size + full_dataset_size;
145
146 char* const alloc_data = static_cast<char*>(std::calloc(1, alloc_size));
147 if (!alloc_data)
148 return nullptr; // Signal out-of-memory by returning null pointer.
149
150 hash512* const light_cache = reinterpret_cast<hash512*>(alloc_data + context_alloc_size);
151 const hash256 epoch_seed = calculate_epoch_seed(epoch_number);
152 build_fn(light_cache, light_cache_num_items, epoch_seed);
153
154 uint32_t* const l1_cache =
155 reinterpret_cast<uint32_t*>(alloc_data + context_alloc_size + light_cache_size);
156
157 hash1024* full_dataset = full ? reinterpret_cast<hash1024*>(l1_cache) : nullptr;
158
159 epoch_context_full* const context = new (alloc_data) epoch_context_full{
160 epoch_number,
161 light_cache_num_items,
162 light_cache,
163 l1_cache,
164 full_dataset_num_items,
165 full_dataset,
166 };
167
168 auto* full_dataset_2048 = reinterpret_cast<hash2048*>(l1_cache);
169 for (uint32_t i = 0; i < progpow::l1_cache_size / sizeof(full_dataset_2048[0]); ++i)
170 full_dataset_2048[i] = calculate_dataset_item_2048(*context, i);
171 return context;
172 }
173 } // namespace generic
174
build_light_cache(hash512 cache[],int num_items,const hash256 & seed)175 void build_light_cache(hash512 cache[], int num_items, const hash256& seed) noexcept
176 {
177 return generic::build_light_cache(keccak512, cache, num_items, seed);
178 }
179
180 struct item_state
181 {
182 const hash512* const cache;
183 const int64_t num_cache_items;
184 const uint32_t seed;
185
186 hash512 mix;
187
item_stateethash::item_state188 ALWAYS_INLINE item_state(const epoch_context& context, int64_t index) noexcept
189 : cache{context.light_cache},
190 num_cache_items{context.light_cache_num_items},
191 seed{static_cast<uint32_t>(index)}
192 {
193 mix = cache[index % num_cache_items];
194 mix.word32s[0] ^= le::uint32(seed);
195 mix = le::uint32s(keccak512(mix));
196 }
197
updateethash::item_state198 ALWAYS_INLINE void update(uint32_t round) noexcept
199 {
200 static constexpr size_t num_words = sizeof(mix) / sizeof(uint32_t);
201 const uint32_t t = fnv1(seed ^ round, mix.word32s[round % num_words]);
202 const int64_t parent_index = t % num_cache_items;
203 mix = fnv1(mix, le::uint32s(cache[parent_index]));
204 }
205
finalethash::item_state206 ALWAYS_INLINE hash512 final() noexcept { return keccak512(le::uint32s(mix)); }
207 };
208
calculate_dataset_item_512(const epoch_context & context,int64_t index)209 hash512 calculate_dataset_item_512(const epoch_context& context, int64_t index) noexcept
210 {
211 item_state item0{context, index};
212 for (uint32_t j = 0; j < full_dataset_item_parents; ++j)
213 item0.update(j);
214 return item0.final();
215 }
216
217 /// Calculates a full dataset item
218 ///
219 /// This consist of two 512-bit items produced by calculate_dataset_item_partial().
220 /// Here the computation is done interleaved for better performance.
calculate_dataset_item_1024(const epoch_context & context,uint32_t index)221 hash1024 calculate_dataset_item_1024(const epoch_context& context, uint32_t index) noexcept
222 {
223 item_state item0{context, int64_t(index) * 2};
224 item_state item1{context, int64_t(index) * 2 + 1};
225
226 for (uint32_t j = 0; j < full_dataset_item_parents; ++j)
227 {
228 item0.update(j);
229 item1.update(j);
230 }
231
232 return hash1024{{item0.final(), item1.final()}};
233 }
234
calculate_dataset_item_2048(const epoch_context & context,uint32_t index)235 hash2048 calculate_dataset_item_2048(const epoch_context& context, uint32_t index) noexcept
236 {
237 item_state item0{context, int64_t(index) * 4};
238 item_state item1{context, int64_t(index) * 4 + 1};
239 item_state item2{context, int64_t(index) * 4 + 2};
240 item_state item3{context, int64_t(index) * 4 + 3};
241
242 for (uint32_t j = 0; j < full_dataset_item_parents; ++j)
243 {
244 item0.update(j);
245 item1.update(j);
246 item2.update(j);
247 item3.update(j);
248 }
249
250 return hash2048{{item0.final(), item1.final(), item2.final(), item3.final()}};
251 }
252
253 namespace
254 {
255 using lookup_fn = hash1024 (*)(const epoch_context&, uint32_t);
256
hash_seed(const hash256 & header_hash,uint64_t nonce)257 inline hash512 hash_seed(const hash256& header_hash, uint64_t nonce) noexcept
258 {
259 nonce = le::uint64(nonce);
260 uint8_t init_data[sizeof(header_hash) + sizeof(nonce)];
261 std::memcpy(&init_data[0], &header_hash, sizeof(header_hash));
262 std::memcpy(&init_data[sizeof(header_hash)], &nonce, sizeof(nonce));
263
264 return keccak512(init_data, sizeof(init_data));
265 }
266
hash_final(const hash512 & seed,const hash256 & mix_hash)267 inline hash256 hash_final(const hash512& seed, const hash256& mix_hash)
268 {
269 uint8_t final_data[sizeof(seed) + sizeof(mix_hash)];
270 std::memcpy(&final_data[0], seed.bytes, sizeof(seed));
271 std::memcpy(&final_data[sizeof(seed)], mix_hash.bytes, sizeof(mix_hash));
272 return keccak256(final_data, sizeof(final_data));
273 }
274
hash_kernel(const epoch_context & context,const hash512 & seed,lookup_fn lookup)275 inline hash256 hash_kernel(
276 const epoch_context& context, const hash512& seed, lookup_fn lookup) noexcept
277 {
278 static constexpr size_t num_words = sizeof(hash1024) / sizeof(uint32_t);
279 const uint32_t index_limit = static_cast<uint32_t>(context.full_dataset_num_items);
280 const uint32_t seed_init = le::uint32(seed.word32s[0]);
281
282 hash1024 mix{{le::uint32s(seed), le::uint32s(seed)}};
283
284 for (uint32_t i = 0; i < num_dataset_accesses; ++i)
285 {
286 const uint32_t p = fnv1(i ^ seed_init, mix.word32s[i % num_words]) % index_limit;
287 const hash1024 newdata = le::uint32s(lookup(context, p));
288
289 for (size_t j = 0; j < num_words; ++j)
290 mix.word32s[j] = fnv1(mix.word32s[j], newdata.word32s[j]);
291 }
292
293 hash256 mix_hash;
294 for (size_t i = 0; i < num_words; i += 4)
295 {
296 const uint32_t h1 = fnv1(mix.word32s[i], mix.word32s[i + 1]);
297 const uint32_t h2 = fnv1(h1, mix.word32s[i + 2]);
298 const uint32_t h3 = fnv1(h2, mix.word32s[i + 3]);
299 mix_hash.word32s[i / 4] = h3;
300 }
301
302 return le::uint32s(mix_hash);
303 }
304 } // namespace
305
hash(const epoch_context & context,const hash256 & header_hash,uint64_t nonce)306 result hash(const epoch_context& context, const hash256& header_hash, uint64_t nonce) noexcept
307 {
308 const hash512 seed = hash_seed(header_hash, nonce);
309 const hash256 mix_hash = hash_kernel(context, seed, calculate_dataset_item_1024);
310 return {hash_final(seed, mix_hash), mix_hash};
311 }
312
hash(const epoch_context_full & context,const hash256 & header_hash,uint64_t nonce)313 result hash(const epoch_context_full& context, const hash256& header_hash, uint64_t nonce) noexcept
314 {
315 static const auto lazy_lookup = [](const epoch_context& context, uint32_t index) noexcept
316 {
317 auto full_dataset = static_cast<const epoch_context_full&>(context).full_dataset;
318 hash1024& item = full_dataset[index];
319 if (item.word64s[0] == 0)
320 {
321 // TODO: Copy elision here makes it thread-safe?
322 item = calculate_dataset_item_1024(context, index);
323 }
324
325 return item;
326 };
327
328 const hash512 seed = hash_seed(header_hash, nonce);
329 const hash256 mix_hash = hash_kernel(context, seed, lazy_lookup);
330 return {hash_final(seed, mix_hash), mix_hash};
331 }
332
verify_final_hash(const hash256 & header_hash,const hash256 & mix_hash,uint64_t nonce,const hash256 & boundary)333 bool verify_final_hash(const hash256& header_hash, const hash256& mix_hash, uint64_t nonce,
334 const hash256& boundary) noexcept
335 {
336 const hash512 seed = hash_seed(header_hash, nonce);
337 return is_less_or_equal(hash_final(seed, mix_hash), boundary);
338 }
339
verify(const epoch_context & context,const hash256 & header_hash,const hash256 & mix_hash,uint64_t nonce,const hash256 & boundary)340 bool verify(const epoch_context& context, const hash256& header_hash, const hash256& mix_hash,
341 uint64_t nonce, const hash256& boundary) noexcept
342 {
343 const hash512 seed = hash_seed(header_hash, nonce);
344 if (!is_less_or_equal(hash_final(seed, mix_hash), boundary))
345 return false;
346
347 const hash256 expected_mix_hash = hash_kernel(context, seed, calculate_dataset_item_1024);
348 return is_equal(expected_mix_hash, mix_hash);
349 }
350
search_light(const epoch_context & context,const hash256 & header_hash,const hash256 & boundary,uint64_t start_nonce,size_t iterations)351 search_result search_light(const epoch_context& context, const hash256& header_hash,
352 const hash256& boundary, uint64_t start_nonce, size_t iterations) noexcept
353 {
354 const uint64_t end_nonce = start_nonce + iterations;
355 for (uint64_t nonce = start_nonce; nonce < end_nonce; ++nonce)
356 {
357 result r = hash(context, header_hash, nonce);
358 if (is_less_or_equal(r.final_hash, boundary))
359 return {r, nonce};
360 }
361 return {};
362 }
363
search(const epoch_context_full & context,const hash256 & header_hash,const hash256 & boundary,uint64_t start_nonce,size_t iterations)364 search_result search(const epoch_context_full& context, const hash256& header_hash,
365 const hash256& boundary, uint64_t start_nonce, size_t iterations) noexcept
366 {
367 const uint64_t end_nonce = start_nonce + iterations;
368 for (uint64_t nonce = start_nonce; nonce < end_nonce; ++nonce)
369 {
370 result r = hash(context, header_hash, nonce);
371 if (is_less_or_equal(r.final_hash, boundary))
372 return {r, nonce};
373 }
374 return {};
375 }
376 } // namespace ethash
377
378 using namespace ethash;
379
380 extern "C" {
381
ethash_calculate_epoch_seed(int epoch_number)382 ethash_hash256 ethash_calculate_epoch_seed(int epoch_number) noexcept
383 {
384 ethash_hash256 epoch_seed = {};
385 for (int i = 0; i < epoch_number; ++i)
386 epoch_seed = ethash_keccak256_32(epoch_seed.bytes);
387 return epoch_seed;
388 }
389
ethash_calculate_light_cache_num_items(int epoch_number)390 int ethash_calculate_light_cache_num_items(int epoch_number) noexcept
391 {
392 static constexpr int item_size = sizeof(hash512);
393 static constexpr int num_items_init = light_cache_init_size / item_size;
394 static constexpr int num_items_growth = light_cache_growth / item_size;
395 static_assert(
396 light_cache_init_size % item_size == 0, "light_cache_init_size not multiple of item size");
397 static_assert(
398 light_cache_growth % item_size == 0, "light_cache_growth not multiple of item size");
399
400 int num_items_upper_bound = num_items_init + epoch_number * num_items_growth;
401 int num_items = ethash_find_largest_prime(num_items_upper_bound);
402 return num_items;
403 }
404
ethash_calculate_full_dataset_num_items(int epoch_number)405 int ethash_calculate_full_dataset_num_items(int epoch_number) noexcept
406 {
407 static constexpr int item_size = sizeof(hash1024);
408 static constexpr int num_items_init = full_dataset_init_size / item_size;
409 static constexpr int num_items_growth = full_dataset_growth / item_size;
410 static_assert(full_dataset_init_size % item_size == 0,
411 "full_dataset_init_size not multiple of item size");
412 static_assert(
413 full_dataset_growth % item_size == 0, "full_dataset_growth not multiple of item size");
414
415 int num_items_upper_bound = num_items_init + epoch_number * num_items_growth;
416 int num_items = ethash_find_largest_prime(num_items_upper_bound);
417 return num_items;
418 }
419
ethash_create_epoch_context(int epoch_number)420 epoch_context* ethash_create_epoch_context(int epoch_number) noexcept
421 {
422 return generic::create_epoch_context(build_light_cache, epoch_number, false);
423 }
424
ethash_create_epoch_context_full(int epoch_number)425 epoch_context_full* ethash_create_epoch_context_full(int epoch_number) noexcept
426 {
427 return generic::create_epoch_context(build_light_cache, epoch_number, true);
428 }
429
ethash_destroy_epoch_context_full(epoch_context_full * context)430 void ethash_destroy_epoch_context_full(epoch_context_full* context) noexcept
431 {
432 ethash_destroy_epoch_context(context);
433 }
434
ethash_destroy_epoch_context(epoch_context * context)435 void ethash_destroy_epoch_context(epoch_context* context) noexcept
436 {
437 context->~epoch_context();
438 std::free(context);
439 }
440
441 } // extern "C"
442