TLA Line data Source code
1 : // evmone: Fast Ethereum Virtual Machine implementation
2 : // Copyright 2022 The evmone Authors.
3 : // SPDX-License-Identifier: Apache-2.0
4 :
5 : #include "mpt.hpp"
6 : #include "rlp.hpp"
7 : #include <algorithm>
8 : #include <cassert>
9 :
10 : namespace evmone::state
11 : {
12 : namespace
13 : {
14 : /// The MPT node kind.
15 : enum class Kind : uint8_t
16 : {
17 : leaf,
18 : ext,
19 : branch
20 : };
21 :
22 : /// The collection of nibbles (4-bit values) representing a path in a MPT.
23 : ///
24 : /// TODO(c++26): This is an instance of std::inplace_vector.
25 : class Path
26 : {
27 : static constexpr size_t max_size = 64;
28 :
29 : size_t m_size = 0; // TODO: Can be converted to uint8_t.
30 : uint8_t m_nibbles[max_size]{};
31 :
32 : public:
33 CBC 109 : Path() = default;
34 :
35 : /// Constructs a path from a pair of iterators.
36 771 : Path(const uint8_t* first, const uint8_t* last) noexcept
37 771 : : m_size(static_cast<size_t>(last - first))
38 : {
39 771 : assert(m_size <= std::size(m_nibbles));
40 771 : std::copy(first, last, m_nibbles);
41 771 : }
42 :
43 : /// Constructs a path from bytes - each byte will produce 2 nibbles in the path.
44 544 : explicit Path(bytes_view key) noexcept : m_size{2 * key.size()}
45 : {
46 544 : assert(m_size <= std::size(m_nibbles) && "a keys must not be longer than 32 bytes");
47 544 : size_t i = 0;
48 14666 : for (const auto b : key)
49 : {
50 14122 : m_nibbles[i++] = b >> 4;
51 14122 : m_nibbles[i++] = b & 0x0f;
52 : }
53 544 : }
54 :
55 544 : [[nodiscard]] static constexpr size_t capacity() noexcept { return max_size; }
56 550 : [[nodiscard]] bool empty() const noexcept { return m_size == 0; }
57 993 : [[nodiscard]] const uint8_t* begin() const noexcept { return m_nibbles; }
58 1542 : [[nodiscard]] const uint8_t* end() const noexcept { return m_nibbles + m_size; }
59 :
60 544 : [[nodiscard]] bytes encode(Kind kind) const
61 : {
62 544 : assert(kind == Kind::leaf || kind == Kind::ext);
63 544 : const auto kind_prefix = kind == Kind::leaf ? 0x20 : 0x00;
64 544 : const auto has_odd_size = m_size % 2 != 0;
65 544 : const auto nibble_prefix = has_odd_size ? (0x10 | m_nibbles[0]) : 0x00;
66 :
67 544 : bytes encoded{static_cast<uint8_t>(kind_prefix | nibble_prefix)};
68 14229 : for (auto i = size_t{has_odd_size}; i < m_size; i += 2)
69 13685 : encoded.push_back(static_cast<uint8_t>((m_nibbles[i] << 4) | m_nibbles[i + 1]));
70 544 : return encoded;
71 UBC 0 : }
72 : };
73 : } // namespace
74 :
75 : /// The MPT Node.
76 : ///
77 : /// The implementation is based on StackTrie from go-ethereum.
78 : // TODO(clang-tidy-17): bug https://github.com/llvm/llvm-project/issues/50006
79 : // NOLINTNEXTLINE(bugprone-reserved-identifier)
80 : class MPTNode
81 : {
82 : static constexpr size_t num_children = 16;
83 :
84 : Kind m_kind = Kind::leaf;
85 : Path m_path;
86 : bytes m_value;
87 : std::unique_ptr<MPTNode> m_children[num_children];
88 :
89 CBC 762 : explicit MPTNode(Kind kind, const Path& path = {}, bytes&& value = {}) noexcept
90 762 : : m_kind{kind}, m_path{path}, m_value{std::move(value)}
91 762 : {}
92 :
93 : /// Creates an extended node.
94 GBC 1 : static MPTNode ext(const Path& path, std::unique_ptr<MPTNode> child) noexcept
95 : {
96 1 : assert(child->m_kind == Kind::branch);
97 1 : MPTNode node{Kind::ext, path};
98 1 : node.m_children[0] = std::move(child);
99 1 : return node;
100 : }
101 :
102 : /// Optionally wraps the child node with newly created extended node in case
103 : /// the provided path is not empty.
104 1 : static std::unique_ptr<MPTNode> optional_ext(
105 : const Path& path, std::unique_ptr<MPTNode> child) noexcept
106 : {
107 2 : return (!path.empty()) ? std::make_unique<MPTNode>(ext(path, std::move(child))) :
108 1 : std::move(child);
109 : }
110 :
111 : /// Creates a branch node out of two children and optionally extends it with an extended
112 : /// node in case the path is not empty.
113 CBC 109 : static MPTNode ext_branch(const Path& path, size_t idx1, std::unique_ptr<MPTNode> child1,
114 : size_t idx2, std::unique_ptr<MPTNode> child2) noexcept
115 : {
116 109 : assert(idx1 != idx2);
117 109 : assert(idx1 < num_children);
118 109 : assert(idx2 < num_children);
119 :
120 109 : MPTNode br{Kind::branch};
121 109 : br.m_children[idx1] = std::move(child1);
122 109 : br.m_children[idx2] = std::move(child2);
123 :
124 219 : return (!path.empty()) ? ext(path, std::make_unique<MPTNode>(std::move(br))) :
125 110 : std::move(br);
126 109 : }
127 :
128 : public:
129 : MPTNode() = default;
130 :
131 : /// Creates new leaf node.
132 652 : static std::unique_ptr<MPTNode> leaf(const Path& path, bytes&& value) noexcept
133 : {
134 652 : return std::make_unique<MPTNode>(MPTNode{Kind::leaf, path, std::move(value)});
135 : }
136 :
137 : void insert(const Path& path, bytes&& value);
138 :
139 : [[nodiscard]] bytes encode() const;
140 : };
141 :
142 331 : void MPTNode::insert(const Path& path, bytes&& value) // NOLINT(misc-no-recursion)
143 : {
144 : // The insertion is all about branch nodes. In happy case we will find an empty slot
145 : // in an existing branch node. Otherwise, we need to create new branch node
146 : // (possibly with an adjusted extended node) and transform existing nodes around it.
147 :
148 331 : const auto [this_idx, insert_idx] = std::ranges::mismatch(m_path, path);
149 :
150 : // insert_idx is always valid if requirements are fulfilled:
151 : // - if m_path is not shorter than path they must have mismatched nibbles,
152 : // given the requirement of key uniqueness and not being a prefix if existing key,
153 : // - if m_path is shorter and matches the path prefix
154 : // then insert_idx points at path[m_path.size()].
155 331 : assert(insert_idx != path.end() && "a key must not be a prefix of another key");
156 :
157 331 : const Path common{m_path.begin(), this_idx};
158 331 : const Path insert_tail{insert_idx + 1, path.end()};
159 :
160 331 : switch (m_kind)
161 : {
162 222 : case Kind::branch:
163 : {
164 222 : assert(m_path.empty()); // Branch has no path.
165 222 : if (auto& child = m_children[*insert_idx]; child)
166 1 : child->insert(insert_tail, std::move(value));
167 : else
168 221 : child = leaf(insert_tail, std::move(value));
169 222 : break;
170 : }
171 :
172 GBC 1 : case Kind::ext:
173 : {
174 1 : assert(!m_path.empty()); // Ext must have non-empty path.
175 1 : if (this_idx == m_path.end()) // Paths match: go into the child.
176 UBC 0 : return m_children[0]->insert({insert_idx, path.end()}, std::move(value));
177 :
178 : // The original branch node must be pushed down, possible extended with
179 : // the adjusted extended node if the path split point is not directly at the branch node.
180 : // Clang Analyzer bug: https://github.com/llvm/llvm-project/issues/47814
181 : // NOLINTNEXTLINE(clang-analyzer-cplusplus.NewDeleteLeaks)
182 GBC 1 : auto this_branch = optional_ext({this_idx + 1, m_path.end()}, std::move(m_children[0]));
183 1 : auto new_leaf = leaf(insert_tail, std::move(value));
184 : *this =
185 1 : ext_branch(common, *this_idx, std::move(this_branch), *insert_idx, std::move(new_leaf));
186 1 : break;
187 1 : }
188 :
189 CBC 108 : case Kind::leaf:
190 : {
191 108 : assert(!m_path.empty()); // Leaf must have non-empty path.
192 108 : assert(this_idx != m_path.end() && "a key must be unique");
193 108 : auto this_leaf = leaf({this_idx + 1, m_path.end()}, std::move(m_value));
194 108 : auto new_leaf = leaf(insert_tail, std::move(value));
195 : *this =
196 108 : ext_branch(common, *this_idx, std::move(this_leaf), *insert_idx, std::move(new_leaf));
197 108 : break;
198 108 : }
199 :
200 UBC 0 : default:
201 0 : assert(false);
202 : }
203 : }
204 :
205 : /// Encodes a node and optionally hashes the encoded bytes
206 : /// if their length exceeds the specified threshold.
207 CBC 439 : static bytes encode_child(const MPTNode& child) noexcept // NOLINT(misc-no-recursion)
208 : {
209 439 : if (auto e = child.encode(); e.size() < 32)
210 UBC 0 : return e; // "short" node
211 : else
212 CBC 439 : return rlp::encode(keccak256(e));
213 : }
214 :
215 653 : bytes MPTNode::encode() const // NOLINT(misc-no-recursion)
216 : {
217 653 : bytes encoded;
218 653 : switch (m_kind)
219 : {
220 544 : case Kind::leaf:
221 : {
222 544 : encoded = rlp::encode(m_path.encode(m_kind)) + rlp::encode(m_value);
223 544 : break;
224 : }
225 109 : case Kind::branch:
226 : {
227 109 : assert(m_path.empty());
228 : static constexpr uint8_t empty = 0x80; // encoded empty child
229 :
230 1853 : for (const auto& child : m_children)
231 : {
232 1744 : if (child)
233 439 : encoded += encode_child(*child);
234 : else
235 1305 : encoded += empty;
236 : }
237 109 : encoded += empty; // end indicator
238 109 : break;
239 : }
240 UBC 0 : case Kind::ext:
241 : {
242 0 : encoded = rlp::encode(m_path.encode(m_kind)) + encode_child(*m_children[0]);
243 0 : break;
244 : }
245 : }
246 :
247 CBC 1306 : return rlp::internal::wrap_list(encoded);
248 653 : }
249 :
250 :
251 424 : MPT::MPT() noexcept = default;
252 424 : MPT::~MPT() noexcept = default;
253 :
254 544 : void MPT::insert(bytes_view key, bytes&& value)
255 : {
256 544 : assert(key.size() <= Path::capacity() / 2); // must fit the path impl. length limit
257 544 : const Path path{key};
258 :
259 544 : if (m_root == nullptr)
260 214 : m_root = MPTNode::leaf(path, std::move(value));
261 : else
262 330 : m_root->insert(path, std::move(value));
263 544 : }
264 :
265 424 : [[nodiscard]] hash256 MPT::hash() const
266 : {
267 424 : if (m_root == nullptr)
268 210 : return emptyMPTHash;
269 214 : return keccak256(m_root->encode());
270 : }
271 :
272 : } // namespace evmone::state
|
