Botan 3.5.0
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/exceptn.h>
14#include <botan/strong_type.h>
15#include <botan/internal/stl_util.h>
16
17#include <cstdint>
18#include <functional>
19#include <optional>
20#include <vector>
21
22namespace Botan {
23
24namespace concepts {
25
26template <typename T>
28
29/**
30 * @brief An index of a node in a layer.
31 *
32 * This is a separate index for each layer.
33 * The left most node of a layer has the index 0.
34 */
35template <typename T>
37
38/**
39 * @brief A layer in a Tree.
40 *
41 * The bottom layer is the layer 0.
42 */
43template <typename T>
45
46template <typename T>
48
49/**
50 * @brief An adress in a Tree.
51 */
52template <typename T, typename TreeLayerIndex, typename TreeNodeIndex>
53concept tree_address = requires(T a, TreeLayerIndex tree_layer, TreeNodeIndex tree_index) {
56 { a.set_address(tree_layer, tree_index) };
57};
58
59template <typename T, typename NodeIdx, typename LayerIdx, typename Address, typename NodeSS>
62 requires(T func, NodeSS out, const Address& address, NodeSS a, NodeSS b) {
63 { func(out, address, a, b) };
64 };
65
66template <typename T, typename NodeIdx, typename LayerIdx, typename Address, typename NodeSS>
69 requires(T func, NodeSS out, const Address& address) {
70 { func(out, address) };
71 };
72
73} // namespace concepts
74
75/**
76 * @brief Treehash logic to build up a merkle hash tree.
77 *
78 * Computes the root of the merkle tree.
79 * Can also output an authentication path necessary for a hash based signature.
80 *
81 * Given the following tree:
82 * Layer:
83 * 2 7R
84 * / \
85 * 1 3X 6A
86 * / \ / \
87 * 0 1X 2A 4 5
88 *
89 * The treehash logic traverses the tree (Post-order traversal), i.e., the nodes are
90 * discovered in order 1,2,3,...,7. If we want to create a signature using leaf node 1,
91 * the authentication path is (Node 2, Node 6), since we need those to compute the
92 * root.
93 *
94 * @param out_root An output buffer to store the root node in (size: node_size ).
95 * @param out_auth_path Optional buffer to store the authentication path in (size: node_size * total_tree_height).
96 * @param leaf_idx The optional index of the leaf used to sign in the bottom tree layer beginning with index 0.
97 * nullopt if no node is signed, so we need no auth path.
98 * @param node_size The size of each node in the tree.
99 * @param total_tree_height The hight of the merkle tree to construct.
100 * @param idx_offset If we compute a subtree this marks the index of the leftmost leaf node in the bottom layer
101 * @param node_pair_hash The function to process two child nodes to compute their parent node.
102 * @param gen_leaf The logic to create a leaf node given the address in the tree. Probably this function
103 * creates a one-time/few-time-signature's public key which is hashed to be the leaf node.
104 * @param tree_address The address that is passed to gen_leaf or node_pair hash. This function will update the
105 * address accordings to the currently processed node. This object may contain further
106 * algorithm specific information, like the position of this merkle tree in a hypertree.
107 */
108template <concepts::contiguous_strong_type TreeNode,
109 concepts::strong_span AuthPathSS,
112 typename Address>
114inline void treehash(
115 StrongSpan<TreeNode> out_root,
116 std::optional<AuthPathSS> out_auth_path,
117 std::optional<TreeNodeIndex> leaf_idx,
118 size_t node_size,
119 TreeLayerIndex total_tree_height,
120 uint32_t idx_offset,
123 Address& tree_address) {
124 BOTAN_ASSERT_NOMSG(out_root.size() == node_size);
125 BOTAN_ASSERT(out_auth_path.has_value() == leaf_idx.has_value(),
126 "Both leaf index and auth path buffer is given or neither.");
127 const bool is_signing = leaf_idx.has_value();
128 BOTAN_ASSERT_NOMSG(!is_signing || out_auth_path.value().size() == node_size * total_tree_height.get());
129
130 const TreeNodeIndex max_idx(uint32_t((1 << total_tree_height.get()) - 1));
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 // Traverse the tree from the left-most leaf, matching siblings and up until
137 // the root (Post-order traversal). Collect the adjacent nodes to build
138 // the authentication path along the way.
139 for(TreeNodeIndex idx(0); true; ++idx) {
140 tree_address.set_address(TreeLayerIndex(0), idx + idx_offset);
141 gen_leaf(StrongSpan<TreeNode>(current_node), tree_address);
142
143 // Now combine the freshly generated right node with previously generated
144 // left ones
145 uint32_t internal_idx_offset = idx_offset;
146 TreeNodeIndex internal_idx = idx;
147 auto internal_leaf = leaf_idx;
148
149 for(TreeLayerIndex h(0); true; ++h) {
150 // Check if we hit the top of the tree
151 if(h == total_tree_height) {
152 copy_mem(out_root, current_node);
153 return;
154 }
155
156 // Check if the node we have is a part of the authentication path; if
157 // it is, write it out. The XOR sum of both nodes (at internal_idx and internal_leaf)
158 // is 1 iff they have the same parent node in the FORS tree
159 if(is_signing && (internal_idx ^ internal_leaf.value()) == 0x01U) {
160 auto auth_path_location = out_auth_path.value().get().subspan(h.get() * node_size, node_size);
161 copy_mem(auth_path_location, current_node);
162 }
163
164 // Check if we're at a left child; if so, stop going up the tree
165 // Exception: if we've reached the end of the tree, keep on going (so
166 // we combine the last 4 nodes into the one root node in two more
167 // iterations)
168 if((internal_idx & 1) == 0U && idx < max_idx) {
169 // We've hit a left child; save the current for when we get the
170 // corresponding right child.
171 copy_mem(last_visited_left_child_at_layer.at(h.get()), current_node);
172 break;
173 }
174
175 // Ok, we're at a right node. Now combine the left and right logical
176 // nodes together.
177
178 // Set the address of the node we're creating.
179 internal_idx_offset /= 2;
180 tree_address.set_address(h + 1, internal_idx / 2 + internal_idx_offset);
181
182 node_pair_hash(current_node, tree_address, last_visited_left_child_at_layer.at(h.get()), current_node);
183
184 internal_idx /= 2;
185 if(internal_leaf.has_value()) {
186 internal_leaf.value() /= 2;
187 }
188 }
189 }
190}
191
192/**
193 * @brief Uses an authentication path and a leaf node to reconstruct the root node
194 * of a merkle tree.
195 *
196 * @param out_root A output buffer for the root node of the merkle tree.
197 * @param authentication_path The authentication path in one buffer (concatenated nodes).
198 * @param leaf_idx The index of the leaf used to sig in the bottom layer beginning with 0.
199 * @param leaf The leaf node used to sig.
200 * @param node_size The size of each node in the tree.
201 * @param total_tree_height The hight of the merkle tree to construct.
202 * @param idx_offset If we compute a subtree this marks the index of the leftmost leaf node in the bottom layer.
203 * @param node_pair_hash The function to process two child nodes to compute their parent node.
204 * @param tree_address The address that is passed to node_pair hash. This function will update the
205 * address accordings to the currently processed node. This object may contain further
206 * algorithm specific information, like the position of this merkle tree in a hypertree.
207 */
208template <concepts::contiguous_strong_type TreeNode,
209 concepts::strong_span AuthPathSS,
210 concepts::tree_node_index TreeNodeIndex,
211 concepts::tree_layer_index TreeLayerIndex,
212 typename Address>
213 requires concepts::tree_address<Address, TreeLayerIndex, TreeNodeIndex>
214inline void compute_root(
215 StrongSpan<TreeNode> out_root,
216 AuthPathSS authentication_path,
217 TreeNodeIndex leaf_idx,
219 size_t node_size,
220 TreeLayerIndex total_tree_height,
221 uint32_t idx_offset,
223 Address& tree_address) {
224 BOTAN_ASSERT_NOMSG(out_root.size() == node_size);
225 BOTAN_ASSERT_NOMSG(authentication_path.size() == node_size * static_cast<size_t>(total_tree_height.get()));
226 BOTAN_ASSERT_NOMSG(leaf.size() == node_size);
227
228 // Use the `out` parameter as intermediate buffer for left/right nodes
229 // while traversing the tree.
230 copy_mem(out_root, leaf);
231
232 // Views into either `auth_path` or `out` depending on the tree location.
235
236 BufferSlicer auth_path(authentication_path);
237
238 // The leaf is put in the left or right buffer, depending on its indexes parity.
239 // Same for the first node of the authentication path
240
241 for(TreeLayerIndex i(0); i < total_tree_height; i++) {
242 // The input of the hash function takes the current node and the node
243 // given in the authentication path. If the current node is a right node
244 // in the tree (i.e. its leaf index is uneven) the hash function inputs
245 // must be swapped.
246 left = out_root;
247 right = auth_path.take<TreeNode>(node_size);
248
249 if((leaf_idx & 1) == 1U) {
250 std::swap(left, right);
251 }
252
253 leaf_idx /= 2;
254 idx_offset /= 2;
255 tree_address.set_address(i + 1, leaf_idx + idx_offset);
256
257 node_pair_hash(out_root, tree_address, left, right);
258 }
259
260 BOTAN_ASSERT_NOMSG(auth_path.empty());
261}
262} // namespace Botan
263
264#endif // BOTAN_TREE_HASH_H_
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50
bool empty() const
Definition stl_util.h:129
std::span< const uint8_t > take(const size_t count)
Definition stl_util.h:98
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
An adress in a Tree.
Definition tree_hash.h:53
An index of a node in a layer.
Definition tree_hash.h:36
FE_25519 T
Definition ge.cpp:34
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:78
Strong< uint32_t, struct TreeLayerIndex_, EnableArithmeticWithPlainNumber > TreeLayerIndex
Index of the layer within a FORS/XMSS tree.
Definition sp_types.h:69
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146
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 GenerateLeafFunction &gen_leaf, Sphincs_Address &tree_address)
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)