Botan 3.14.1
Crypto and TLS for C&
tree_hash.h
Go to the documentation of this file.
1/**
2 * Treehash logic used for hash-based signatures
3 * (C) 2023 Jack Lloyd
4 * 2023 Fabian Albert, René Meusel, Amos Treiber, Philippe Lieser - Rohde & Schwarz Cybersecurity GmbH
5 *
6 * Parts of this file have been adapted from https://github.com/sphincs/sphincsplus
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10#ifndef BOTAN_TREE_HASH_H_
11#define BOTAN_TREE_HASH_H_
12
13#include <botan/strong_type.h>
14#include <botan/internal/buffer_slicer.h>
15#include <optional>
16#include <vector>
17
18namespace Botan {
19
20namespace concepts {
21
22template <typename T>
24
25/**
26 * @brief An index of a node in a layer.
27 *
28 * This is a separate index for each layer.
29 * The left most node of a layer has the index 0.
30 */
31template <typename T>
33
34/**
35 * @brief A layer in a Tree.
36 *
37 * The bottom layer is the layer 0.
38 */
39template <typename T>
41
42template <typename T>
44
45/**
46 * @brief An address in a Tree.
47 */
48template <typename T, typename TreeLayerIndex, typename TreeNodeIndex>
49concept tree_address = requires(T a, TreeLayerIndex tree_layer, TreeNodeIndex tree_index) {
52 { a.set_address(tree_layer, tree_index) };
53};
54
55template <typename T, typename NodeIdx, typename LayerIdx, typename Address, typename NodeSS>
58 requires(T func, NodeSS out, const Address& address, NodeSS a, NodeSS b) {
59 { func(out, address, a, b) };
60 };
61
62template <typename T, typename NodeIdx>
64 concepts::tree_node_index<NodeIdx> && requires(T func, std::span<uint8_t> out, NodeIdx first_idx, size_t count) {
65 { func(out, first_idx, count) };
66 };
67
68} // namespace concepts
69
70/**
71 * @brief Treehash logic to build up a merkle hash tree.
72 *
73 * Computes the root of the merkle tree.
74 * Can also output an authentication path necessary for a hash based signature.
75 *
76 * Given the following tree:
77 * Layer:
78 * 2 7R
79 * / \
80 * 1 3X 6A
81 * / \ / \
82 * 0 1X 2A 4 5
83 *
84 * The treehash logic traverses the tree (Post-order traversal), i.e., the nodes are
85 * discovered in order 1,2,3,...,7. If we want to create a signature using leaf node 1,
86 * the authentication path is (Node 2, Node 6), since we need those to compute the
87 * root.
88 *
89 * @param out_root An output buffer to store the root node in (size: node_size ).
90 * @param out_auth_path Optional buffer to store the authentication path in (size: node_size * total_tree_height).
91 * @param leaf_idx The optional index of the leaf used to sign in the bottom tree layer beginning with index 0.
92 * nullopt if no node is signed, so we need no auth path.
93 * @param node_size The size of each node in the tree.
94 * @param total_tree_height The height of the merkle tree to construct.
95 * @param idx_offset If we compute a subtree this marks the index of the leftmost leaf node in the bottom layer
96 * @param node_pair_hash The function to process two child nodes to compute their parent node.
97 * @param gen_leaves The logic to create a batch of consecutive leaf nodes, given the index of the
98 * first leaf (including the tree's index offset) and the leaf count. Probably this
99 * function creates one-time/few-time-signatures' public keys which are hashed to
100 * be the leaf nodes.
101 * @param tree_address The address that is passed to node_pair hash. This function will update the
102 * address accordings to the currently processed node. This object may contain further
103 * algorithm specific information, like the position of this merkle tree in a hypertree.
104 */
105template <concepts::contiguous_strong_type TreeNode,
106 concepts::strong_span AuthPathSS,
109 typename Address>
111inline void treehash(
112 StrongSpan<TreeNode> out_root,
113 std::optional<AuthPathSS> out_auth_path,
114 std::optional<TreeNodeIndex> leaf_idx,
115 size_t node_size,
116 TreeLayerIndex total_tree_height,
117 uint32_t idx_offset,
120 Address& tree_address) {
121 BOTAN_ASSERT_NOMSG(out_root.size() == node_size);
122 BOTAN_ASSERT(out_auth_path.has_value() == leaf_idx.has_value(),
123 "Both leaf index and auth path buffer is given or neither.");
124 const bool is_signing = leaf_idx.has_value();
125 BOTAN_ASSERT_NOMSG(!is_signing || out_auth_path.value().size() == node_size * total_tree_height.get());
126 BOTAN_ASSERT_NOMSG(total_tree_height.get() < 32);
127
128 const TreeNodeIndex max_idx((uint32_t(1) << total_tree_height.get()) - 1);
129 // Not has_value() || value(), which GCC may compile to test the payload first
130 BOTAN_ASSERT_NOMSG(leaf_idx.value_or(TreeNodeIndex(0)) <= max_idx);
131
132 std::vector<TreeNode> last_visited_left_child_at_layer(total_tree_height.get(), TreeNode(node_size));
133
134 TreeNode current_node(node_size); // Current logical node
135
136 // Leaves are created in batches to enable batched hashing. Both the
137 // batch size and the leaf count are powers of two, so batches are
138 // always full.
139 const uint32_t leaves_per_batch = std::min<uint32_t>(uint32_t(1) << total_tree_height.get(), 32);
140 std::vector<uint8_t> leaves(leaves_per_batch * node_size);
141
142 // Traverse the tree from the left-most leaf, matching siblings and up until
143 // the root (Post-order traversal). Collect the adjacent nodes to build
144 // the authentication path along the way.
145 for(TreeNodeIndex idx(0); true; ++idx) {
146 const uint32_t batch_pos = idx.get() % leaves_per_batch;
147 if(batch_pos == 0) {
148 gen_leaves(std::span(leaves), idx + idx_offset, leaves_per_batch);
149 }
150 copy_mem(current_node, std::span(leaves).subspan(batch_pos * node_size, node_size));
151
152 // Now combine the freshly generated right node with previously generated
153 // left ones
154 uint32_t internal_idx_offset = idx_offset;
155 TreeNodeIndex internal_idx = idx;
156 auto internal_leaf = leaf_idx;
157
158 for(TreeLayerIndex h(0); true; ++h) {
159 // Check if we hit the top of the tree
160 if(h == total_tree_height) {
161 copy_mem(out_root, current_node);
162 return;
163 }
164
165 // Check if the node we have is a part of the authentication path; if
166 // it is, write it out. The XOR sum of both nodes (at internal_idx and internal_leaf)
167 // is 1 iff they have the same parent node in the FORS tree
168 if(is_signing && (internal_idx ^ internal_leaf.value()) == 0x01U) {
169 const auto auth_path_location = out_auth_path.value().get().subspan(h.get() * node_size, node_size);
170 copy_mem(auth_path_location, current_node);
171 }
172
173 // Check if we're at a left child; if so, stop going up the tree
174 // Exception: if we've reached the end of the tree, keep on going (so
175 // we combine the last 4 nodes into the one root node in two more
176 // iterations)
177 if((internal_idx & 1) == 0U && idx < max_idx) {
178 // We've hit a left child; save the current for when we get the
179 // corresponding right child.
180 copy_mem(last_visited_left_child_at_layer.at(h.get()), current_node);
181 break;
182 }
183
184 // Ok, we're at a right node. Now combine the left and right logical
185 // nodes together.
186
187 // Set the address of the node we're creating.
188 internal_idx_offset /= 2;
189 tree_address.set_address(h + 1, internal_idx / 2 + internal_idx_offset);
190
191 node_pair_hash(current_node, tree_address, last_visited_left_child_at_layer.at(h.get()), current_node);
192
193 internal_idx /= 2;
194 if(internal_leaf.has_value()) {
195 internal_leaf.value() /= 2;
196 }
197 }
198 }
199}
200
201/**
202 * @brief Uses an authentication path and a leaf node to reconstruct the root node
203 * of a merkle tree.
204 *
205 * @param out_root A output buffer for the root node of the merkle tree.
206 * @param authentication_path The authentication path in one buffer (concatenated nodes).
207 * @param leaf_idx The index of the leaf used to sig in the bottom layer beginning with 0.
208 * @param leaf The leaf node used to sig.
209 * @param node_size The size of each node in the tree.
210 * @param total_tree_height The height of the merkle tree to construct.
211 * @param idx_offset If we compute a subtree this marks the index of the leftmost leaf node in the bottom layer.
212 * @param node_pair_hash The function to process two child nodes to compute their parent node.
213 * @param tree_address The address that is passed to node_pair hash. This function will update the
214 * address accordings to the currently processed node. This object may contain further
215 * algorithm specific information, like the position of this merkle tree in a hypertree.
216 */
217template <concepts::contiguous_strong_type TreeNode,
218 concepts::strong_span AuthPathSS,
219 concepts::tree_node_index TreeNodeIndex,
220 concepts::tree_layer_index TreeLayerIndex,
221 typename Address>
222 requires concepts::tree_address<Address, TreeLayerIndex, TreeNodeIndex>
223inline void compute_root(
224 StrongSpan<TreeNode> out_root,
225 AuthPathSS authentication_path,
226 TreeNodeIndex leaf_idx,
228 size_t node_size,
229 TreeLayerIndex total_tree_height,
230 uint32_t idx_offset,
232 Address& tree_address) {
233 BOTAN_ASSERT_NOMSG(out_root.size() == node_size);
234 BOTAN_ASSERT_NOMSG(authentication_path.size() == node_size * static_cast<size_t>(total_tree_height.get()));
235 BOTAN_ASSERT_NOMSG(leaf.size() == node_size);
236
237 // Use the `out` parameter as intermediate buffer for left/right nodes
238 // while traversing the tree.
239 copy_mem(out_root, leaf);
240
241 // Views into either `auth_path` or `out` depending on the tree location.
244
245 BufferSlicer auth_path(authentication_path);
246
247 // The leaf is put in the left or right buffer, depending on its indexes parity.
248 // Same for the first node of the authentication path
249
250 for(TreeLayerIndex i(0); i < total_tree_height; i++) {
251 // The input of the hash function takes the current node and the node
252 // given in the authentication path. If the current node is a right node
253 // in the tree (i.e. its leaf index is uneven) the hash function inputs
254 // must be swapped.
255 left = out_root;
256 right = auth_path.take<TreeNode>(node_size);
257
258 if((leaf_idx & 1) == 1U) {
259 std::swap(left, right);
260 }
261
262 leaf_idx /= 2;
263 idx_offset /= 2;
264 tree_address.set_address(i + 1, leaf_idx + idx_offset);
265
266 node_pair_hash(out_root, tree_address, left, right);
267 }
268
269 BOTAN_ASSERT_NOMSG(auth_path.empty());
270}
271} // namespace Botan
272
273#endif // BOTAN_TREE_HASH_H_
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
std::span< const uint8_t > take(const size_t count)
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
constexpr T & get() &
Definition strong_type.h:81
An address in a Tree.
Definition tree_hash.h:49
An index of a node in a layer.
Definition tree_hash.h:32
void treehash(StrongSpan< SphincsTreeNode > out_root, StrongSpan< SphincsAuthenticationPath > out_auth_path, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes, std::optional< TreeNodeIndex > leaf_idx, uint32_t idx_offset, uint32_t total_tree_height, const GenerateLeavesFunction &gen_leaves, Sphincs_Address &tree_address)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr bool is_strong_span_v
Strong< uint32_t, struct TreeNodeIndex_, EnableArithmeticWithPlainNumber > TreeNodeIndex
Index of an individual node inside an XMSS or FORS tree.
Definition sp_types.h:92
Strong< uint32_t, struct TreeLayerIndex_, EnableArithmeticWithPlainNumber > TreeLayerIndex
Index of the layer within a FORS/XMSS tree.
Definition sp_types.h:83
void compute_root(StrongSpan< SphincsTreeNode > out, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes, const SphincsTreeNode &leaf, TreeNodeIndex leaf_idx, uint32_t idx_offset, StrongSpan< const SphincsAuthenticationPath > authentication_path, uint32_t total_tree_height, Sphincs_Address &tree_address)