xrpld
Loading...
Searching...
No Matches
DeepChain.h
1#pragma once
2
3#include <xrpl/basics/Blob.h>
4#include <xrpl/basics/SHAMapHash.h>
5#include <xrpl/basics/Slice.h>
6#include <xrpl/basics/base_uint.h>
7#include <xrpl/basics/contract.h>
8#include <xrpl/protocol/Serializer.h>
9#include <xrpl/shamap/SHAMap.h>
10#include <xrpl/shamap/SHAMapAddNode.h>
11#include <xrpl/shamap/SHAMapLeafNode.h>
12#include <xrpl/shamap/SHAMapNodeID.h>
13#include <xrpl/shamap/SHAMapTreeNode.h>
14
15#include <cstddef>
16#include <optional>
17#include <stdexcept>
18#include <utility>
19#include <vector>
20
21namespace xrpl::tests {
22
38{
39 // nodes[d] is the deserialized node for depth d.
42
43 // The key whose path through the tree this chain spells out. Zero for a chain
44 // built without a leaf, which therefore sits on branch 0 at every depth.
46
47 // The depth of the deepest node, the last one nodesBelowRoot() hands out.
49
55
63 explicit DeepChain(unsigned int seed = 1) : DeepChain(std::nullopt, seed, Decoy::No)
64 {
65 }
66
77 [[nodiscard]] static DeepChain
78 withDecoys(unsigned int seed = 1)
79 {
80 return DeepChain{std::nullopt, seed, Decoy::Yes};
81 }
82
94 [[nodiscard]] static DeepChain
95 toLeaf(unsigned int depth, unsigned int seed = 1)
96 {
97 if (depth > SHAMap::kLeafDepth)
98 Throw<std::logic_error>("DeepChain: leaf depth past SHAMap::kLeafDepth");
99 return DeepChain{std::optional{depth}, seed, Decoy::No};
100 }
101
108 [[nodiscard]] SHAMapTreeNodePtr
109 nodeAt(unsigned int depth) const
110 {
111 return nodes[depth];
112 }
113
121 [[nodiscard]] SHAMapNodeID
122 idAt(unsigned int depth) const
123 {
124 return SHAMapNodeID::createID(depth, pathKey);
125 }
126
134 [[nodiscard]] Blob
135 prefixedNodeAt(unsigned int depth) const
136 {
137 Serializer s;
138 nodeAt(depth)->serializeWithPrefix(s);
139 return s.modData();
140 }
141
150 nodesBelowRoot(unsigned int firstDepth = 1) const
151 {
153 for (auto depth = firstDepth; depth <= deepestDepth; ++depth)
154 data.emplace_back(idAt(depth), nodeAt(depth));
155 return data;
156 }
157
169 [[nodiscard]] bool
170 fill(SHAMap& map) const
171 {
172 if (!map.addRootNode(rootHash, nodeAt(0), nullptr).isGood())
173 return false;
174
175 for (auto depth = 1u; depth < deepestDepth; ++depth)
176 {
177 if (!map.addKnownNode(idAt(depth), nodeAt(depth), nullptr).isUseful())
178 return false;
179 }
180
181 return true;
182 }
183
195 [[nodiscard]] SHAMapAddNode
197 {
198 if (deepestDepth == 0)
199 Throw<std::logic_error>("DeepChain: the root is not offered through addKnownNode()");
200 return map.addKnownNode(idAt(deepestDepth), nodeAt(deepestDepth), nullptr);
201 }
202
203private:
204 // Whether each level carries a second child that stays unresolvable.
205 enum class Decoy { No, Yes };
206
215 DeepChain(std::optional<unsigned int> leafDepth, unsigned int seed, Decoy decoy)
216 : nodes(leafDepth.value_or(SHAMap::kLeafDepth) + 1)
217 {
218 if (!leafDepth)
219 {
220 // With no leaf depth given, the deepest inner node points at a child that stays
221 // unresolvable.
223 return;
224 }
225
226 // Exactly kLeafItemBytes of payload, the smallest a leaf item may be. Checked rather than
227 // assumed, since a caller relates that constant to a threshold of its own.
228 Serializer payload;
229 payload.add32(seed);
230 payload.add32(0);
231 payload.add32(0);
232 if (payload.size() != kLeafItemBytes)
233 Throw<std::logic_error>("DeepChain: unexpected leaf payload size");
234
235 Serializer wire;
236 wire.addRaw(payload.peekData());
237 wire.add8(kWireTypeTransaction);
238
239 auto const leaf = SHAMapTreeNode::makeFromWire(makeSlice(wire.peekData()));
240
241 // A transaction leaf's key is the hash of its own contents, so its position follows
242 // this key's nibbles.
243 pathKey = leafKey(*leaf);
244 deepestDepth = *leafDepth;
245 nodes[*leafDepth] = leaf;
246
247 if (*leafDepth == 0)
248 {
249 // The leaf is the root, so the build stops here.
250 rootHash = leaf->getHash();
251 return;
252 }
253
254 buildInnersDownTo(*leafDepth - 1, leaf->getHash(), decoy);
255 }
256
269 void
270 buildInnersDownTo(unsigned int deepest, SHAMapHash childHash, Decoy decoy)
271 {
272 // The decrement is in the body rather than the condition, so the counter never steps
273 // below zero. UndefinedBehaviorSanitizer reports that wraparound, and the project halts
274 // on its first report.
275 for (auto depth = deepest + 1; depth > 0;)
276 {
277 --depth;
278
279 // A key has 64 nibbles, so SHAMap::kLeafDepth is one past the last nibble
280 // selectBranch() reads from a 32-byte key. A fabricated chain's pathKey is zero, so
281 // branch 0 is the position such a node claims.
282 auto const branch =
283 depth == SHAMap::kLeafDepth ? 0u : selectBranch(idAt(depth), pathKey);
284
285 Serializer s;
286 s.addBitString(childHash.asUInt256());
287 s.add8(static_cast<unsigned char>(branch));
288
289 if (decoy == Decoy::Yes)
290 {
291 // The decoy sits at branch 1, which is free while pathKey is zero, so the
292 // compressed-inner-node parser sees two distinct branches.
293 if (branch == 1)
294 Throw<std::logic_error>("DeepChain: decoy branch collides with real child");
295
296 // Derived from the depth, so each level posts its own read. No node stands behind
297 // this hash, so a read for it stays outstanding.
298 UInt256 decoyHash;
299 decoyHash.begin()[0] = 0xDE;
300 decoyHash.begin()[1] = 0xC0;
301 decoyHash.begin()[2] = static_cast<unsigned char>(depth);
302 s.addBitString(decoyHash);
303 s.add8(1);
304 }
305
307
309 childHash = node->getHash();
310 nodes[depth] = std::move(node);
311 }
312
313 rootHash = childHash;
314 }
315};
316
317} // namespace xrpl::tests
iterator begin()
Definition base_uint.h:128
UInt256 const & asUInt256() const
Definition SHAMapHash.h:26
Identifies a node inside a SHAMap.
static SHAMapNodeID createID(unsigned int depth, UInt256 const &key)
Create a SHAMapNodeID of a node with the depth of the node and the key of a leaf.
static SHAMapTreeNodePtr makeFromWire(Slice rawNode)
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
Definition SHAMap.h:172
SHAMapAddNode addRootNode(SHAMapHash const &hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const *filter)
Add a root node to the SHAMap during synchronization.
SHAMapAddNode addKnownNode(SHAMapNodeID const &nodeID, SHAMapTreeNodePtr treeNode, SHAMapSyncFilter const *filter)
Add a known node at a specific position in the SHAMap during synchronization.
Blob const & peekData() const
Definition Serializer.h:273
int addBitString(BaseUInt< Bits, Tag > const &v)
Definition Serializer.h:202
int add8(unsigned char byteValue)
int addRaw(Blob const &vector)
std::size_t size() const noexcept
Definition Serializer.h:147
STL namespace.
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
static constexpr unsigned char const kWireTypeCompressedInner
Slice makeSlice(std::array< T, N > const &a)
Definition Slice.h:228
constexpr std::size_t kMinShaMapItemBytes
BaseUInt< 256 > UInt256
Definition base_uint.h:581
UInt256 const & leafKey(SHAMapTreeNode const &node)
Return the key of the item held by a SHAMap leaf node.
static constexpr unsigned char const kWireTypeTransaction
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
std::vector< unsigned char > Blob
Storage for linear binary data.
Definition Blob.h:11
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)
Definition contract.h:52
DeepChain(unsigned int seed=1)
A chain of inner nodes reaching SHAMap::kLeafDepth, a depth only a leaf may occupy.
Definition DeepChain.h:63
A chain of inner nodes in wire form, from the root down to one deepest node, each with one real child...
Definition DeepChain.h:38
unsigned int deepestDepth
Definition DeepChain.h:48
DeepChain(unsigned int seed=1)
A chain of inner nodes reaching SHAMap::kLeafDepth, a depth only a leaf may occupy.
Definition DeepChain.h:63
Blob prefixedNodeAt(unsigned int depth) const
The same node in the prefixed form used for storage and fetch packs, which is what hashes to the node...
Definition DeepChain.h:135
static constexpr std::size_t kLeafItemBytes
The payload size of the leaf toLeaf() builds, which is the smallest a SHAMap item may be.
Definition DeepChain.h:54
static DeepChain withDecoys(unsigned int seed=1)
The same chain, with an unresolvable second child at every level, so a backed map's descendAsync() po...
Definition DeepChain.h:78
SHAMapAddNode addOffendingNode(SHAMap &map) const
Offer the deepest node, which for a fabricated chain is the inner node at SHAMap::kLeafDepth,...
Definition DeepChain.h:196
bool fill(SHAMap &map) const
Fill a synching map, stopping one level short of the deepest node so the caller offers that one itsel...
Definition DeepChain.h:170
std::vector< std::pair< SHAMapNodeID, SHAMapTreeNodePtr > > nodesBelowRoot(unsigned int firstDepth=1) const
Every node below the root, down to and including the deepest one.
Definition DeepChain.h:150
std::vector< SHAMapTreeNodePtr > nodes
Definition DeepChain.h:40
SHAMapTreeNodePtr nodeAt(unsigned int depth) const
The node the chain holds at the given depth, root first.
Definition DeepChain.h:109
SHAMapNodeID idAt(unsigned int depth) const
Where the node at the given depth claims to belong, which is on the path to pathKey.
Definition DeepChain.h:122
void buildInnersDownTo(unsigned int deepest, SHAMapHash childHash, Decoy decoy)
Fill in inner nodes, each with one real child (and, under Decoy::Yes, an additional unresolvable seco...
Definition DeepChain.h:270
static DeepChain toLeaf(unsigned int depth, unsigned int seed=1)
A chain ending in a real transaction leaf, which completes an acquisition.
Definition DeepChain.h:95
DeepChain(std::optional< unsigned int > leafDepth, unsigned int seed, Decoy decoy)
Build any of the shapes.
Definition DeepChain.h:215