delay.cpp raw
1 // Copyright (c) 2026 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <consensus/delay.h>
6
7 #include <sync.h>
8
9 #include <cstring>
10 #include <map>
11 #include <utility>
12
13 namespace {
14
15 /** Cache of computed delay remainders keyed by (prev_hash, steps).
16 * ComputeDelay is a pure function, so caching is consensus-safe. It
17 * stops DoS amplification: an attacker cannot re-stall validation with
18 * repeated invalid blocks on the same parent - each new parent costs
19 * them a valid fork block (~617s of hashing). */
20 Mutex g_delay_cache_mutex;
21 std::map<std::pair<uint256, uint64_t>, uint64_t> g_delay_cache GUARDED_BY(g_delay_cache_mutex);
22 constexpr size_t DELAY_CACHE_MAX{4096};
23
24 } // namespace
25
26 uint64_t DelayDivisor(const uint256& prev_hash)
27 {
28 uint64_t d;
29 memcpy(&d, prev_hash.begin(), sizeof(d));
30 return d | 1; // odd
31 }
32
33 // high 128 bits of (u1:u0) * (v1:v0) - the 128x128 product high half,
34 // computed explicitly because the compiler truncates u128*u128.
35 static inline uint64_t MulHi128(uint64_t u1, uint64_t u0, uint64_t v1, uint64_t v0)
36 {
37 uint64_t hi0 = (uint64_t)((unsigned __int128)u0 * v0 >> 64);
38 unsigned __int128 t1 = (unsigned __int128)u0 * v1 + hi0;
39 uint64_t lo1 = (uint64_t)t1, hi1 = (uint64_t)(t1 >> 64);
40 unsigned __int128 t2 = (unsigned __int128)u1 * v0 + lo1;
41 uint64_t lo2 = (uint64_t)t2, hi2 = (uint64_t)(t2 >> 64);
42 (void)lo2;
43 return (uint64_t)((unsigned __int128)u1 * v1 + hi1 + hi2);
44 }
45
46 uint64_t DelayStep(uint64_t r, uint64_t w, uint64_t d, unsigned __int128 v)
47 {
48 // qhat = ((r<<64 | w) * v) >> 128 with v = floor((2^128-1)/d):
49 // exact or 1 too small; one conditional correction.
50 uint64_t q = MulHi128(r, w, (uint64_t)(v >> 64), (uint64_t)v);
51 unsigned __int128 u = ((unsigned __int128)r << 64) | w;
52 unsigned __int128 rem = u - (unsigned __int128)q * d;
53 if (rem >= d) {
54 rem -= d;
55 q++;
56 }
57 (void)q;
58 return (uint64_t)rem;
59 }
60
61 uint64_t ComputeDelay(const uint256& prev_hash, uint64_t steps)
62 {
63 const auto cache_key = std::make_pair(prev_hash, steps);
64 {
65 LOCK(g_delay_cache_mutex);
66 const auto it = g_delay_cache.find(cache_key);
67 if (it != g_delay_cache.end()) return it->second;
68 }
69
70 const uint64_t d = DelayDivisor(prev_hash);
71 // Barrett reciprocal, precomputed once per block
72 const unsigned __int128 v = (((unsigned __int128)0 - 1) << 64 | (unsigned __int128)0xffffffffffffffffULL) / d;
73
74 // xorshift64* stream seeded from the previous block hash
75 uint64_t state;
76 memcpy(&state, prev_hash.begin() + 8, sizeof(state));
77 state = (state == 0) ? 0x9e3779b97f4a7c15ULL : state;
78
79 uint64_t r = 0;
80 for (uint64_t i = 0; i < steps; i++) {
81 // xorshift64*
82 uint64_t x = state;
83 x ^= x >> 12;
84 x ^= x << 25;
85 x ^= x >> 27;
86 state = x;
87 const uint64_t w = x * 0x2545F4914F6CDD1DULL;
88 r = DelayStep(r, w, d, v);
89 }
90
91 LOCK(g_delay_cache_mutex);
92 if (g_delay_cache.size() >= DELAY_CACHE_MAX) g_delay_cache.clear();
93 g_delay_cache.emplace(cache_key, r);
94 return r;
95 }
96
97 int GetDelayOutputIndex(const CTransaction& coinbase)
98 {
99 int pos = NO_DELAY_OUTPUT;
100 for (size_t o = 0; o < coinbase.vout.size(); ++o) {
101 const CScript& spk = coinbase.vout[o].scriptPubKey;
102 CScript::const_iterator pc = spk.begin();
103 opcodetype opcode;
104 std::vector<unsigned char> data;
105 if (!spk.GetOp(pc, opcode, data) || opcode != OP_RETURN) continue;
106 if (!spk.GetOp(pc, opcode, data)) continue;
107 if (data.size() == 2 && data[0] == DELAY_MAGIC_BYTE0 && data[1] == DELAY_MAGIC_BYTE1) {
108 pos = static_cast<int>(o);
109 }
110 }
111 return pos;
112 }
113
114 std::optional<uint64_t> GetDelayOutputValue(const CTxOut& out)
115 {
116 const CScript& spk = out.scriptPubKey;
117 CScript::const_iterator pc = spk.begin();
118 opcodetype opcode;
119 std::vector<unsigned char> data;
120 if (!spk.GetOp(pc, opcode, data) || opcode != OP_RETURN) return std::nullopt;
121 if (!spk.GetOp(pc, opcode, data)) return std::nullopt;
122 if (data.size() != 2 || data[0] != DELAY_MAGIC_BYTE0 || data[1] != DELAY_MAGIC_BYTE1) return std::nullopt;
123 if (!spk.GetOp(pc, opcode, data)) return std::nullopt;
124 if (data.size() != 8) return std::nullopt;
125 uint64_t v = 0;
126 for (int i = 0; i < 8; i++) v |= (uint64_t)data[i] << (8 * i);
127 return v;
128 }
129