monotone

monotone Mtn Source Tree

Root/merkle_tree.cc

1// Copyright (C) 2004 Graydon Hoare <graydon@pobox.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include "base.hh"
11#include <map>
12#include <sstream>
13
14#include <boost/dynamic_bitset.hpp>
15
16#include "botan/botan.h"
17#include "botan/sha160.h"
18
19#include "constants.hh"
20#include "merkle_tree.hh"
21#include "netio.hh"
22#include "numeric_vocab.hh"
23#include "sanity.hh"
24#include "transforms.hh"
25
26using std::make_pair;
27using std::ostream_iterator;
28using std::ostringstream;
29using std::set;
30using std::string;
31
32using boost::dynamic_bitset;
33
34static void
35bitset_to_prefix(dynamic_bitset<unsigned char> const & pref,
36 prefix & rawpref)
37{
38 string s(pref.num_blocks(), 0x00);
39 to_block_range(pref, s.begin());
40 rawpref = prefix(s);
41}
42
43void
44netcmd_item_type_to_string(netcmd_item_type t, string & typestr)
45{
46 typestr.clear();
47 switch (t)
48 {
49 case revision_item:
50 typestr = "revision";
51 break;
52 case file_item:
53 typestr = "file";
54 break;
55 case cert_item:
56 typestr = "cert";
57 break;
58 case key_item:
59 typestr = "key";
60 break;
61 case epoch_item:
62 typestr = "epoch";
63 break;
64 }
65 I(!typestr.empty());
66}
67
68// this is a *raw* SHA1, not the nice friendly hex-encoded type. it is half
69// as many bytes. since merkle nodes are mostly nothing but SHA1 values,
70// and we have to send them over the wire, we use a raw variant here
71// for compactness.
72
73string
74raw_sha1(string const & in)
75{
76 Botan::SHA_160 hash;
77 hash.update(reinterpret_cast<Botan::byte const *>(in.data()),
78 static_cast<unsigned int>(in.size()));
79 char digest[constants::sha1_digest_length];
80 hash.final(reinterpret_cast<Botan::byte *>(digest));
81 string out(digest, constants::sha1_digest_length);
82 return out;
83}
84
85
86merkle_node::merkle_node() : level(0), pref(0),
87 total_num_leaves(0),
88 bitmap(constants::merkle_bitmap_length_in_bits),
89 slots(constants::merkle_num_slots),
90 type(revision_item)
91{}
92
93bool
94merkle_node::operator==(merkle_node const & other) const
95{
96 return (level == other.level
97 && pref == other.pref
98 && total_num_leaves == other.total_num_leaves
99 && bitmap == other.bitmap
100 && slots == other.slots
101 && type == other.type);
102}
103
104void
105merkle_node::check_invariants() const
106{
107 I(this->pref.size() == prefix_length_in_bits(this->level));
108 I(this->level <= constants::merkle_num_tree_levels);
109 I(this->slots.size() == constants::merkle_num_slots);
110 I(this->bitmap.size() == constants::merkle_bitmap_length_in_bits);
111}
112
113void
114merkle_node::get_raw_prefix(prefix & pref) const
115{
116 check_invariants();
117 bitset_to_prefix(this->pref, pref);
118}
119
120void
121merkle_node::get_hex_prefix(hexenc<prefix> & hpref) const
122{
123 prefix pref;
124 get_raw_prefix(pref);
125 encode_hexenc(pref, hpref);
126}
127
128void
129merkle_node::get_raw_slot(size_t slot, id & i) const
130{
131 I(get_slot_state(slot) != empty_state);
132 check_invariants();
133 i = idx(this->slots, slot);
134}
135
136void
137merkle_node::set_raw_slot(size_t slot, id const & val)
138{
139 check_invariants();
140 idx(this->slots, slot) = val;
141}
142
143void
144merkle_node::extended_prefix(size_t slot,
145 dynamic_bitset<unsigned char> & extended) const
146{
147 // remember, in a dynamic_bitset, bit size()-1 is most significant
148 check_invariants();
149 I(slot < constants::merkle_num_slots);
150 extended = this->pref;
151 for (size_t i = 0; i < constants::merkle_fanout_bits; ++i)
152 extended.push_back(static_cast<bool>((slot >> i) & 1));
153}
154
155void
156merkle_node::extended_raw_prefix(size_t slot,
157 prefix & extended) const
158{
159 dynamic_bitset<unsigned char> ext;
160 extended_prefix(slot, ext);
161 bitset_to_prefix(ext, extended);
162}
163
164void
165merkle_node::extended_hex_prefix(size_t slot,
166 hexenc<prefix> & extended) const
167{
168 prefix pref;
169 extended_raw_prefix(slot, pref);
170 encode_hexenc(pref, extended);
171}
172
173slot_state
174merkle_node::get_slot_state(size_t n) const
175{
176 check_invariants();
177 I(n < constants::merkle_num_slots);
178 I(2*n + 1 < bitmap.size());
179 if (bitmap[2*n])
180 {
181 if (bitmap[2*n+1])
182 return subtree_state;
183 else
184 return leaf_state;
185 }
186 else
187 {
188 return empty_state;
189 }
190}
191
192void
193merkle_node::set_slot_state(size_t n, slot_state st)
194{
195 check_invariants();
196 I(n < constants::merkle_num_slots);
197 I(2*n + 1 < bitmap.size());
198 bitmap.reset(2*n);
199 bitmap.reset(2*n+1);
200 if (st == subtree_state || st == leaf_state)
201 bitmap.set(2*n);
202 if (st == subtree_state)
203 bitmap.set(2*n+1);
204}
205
206
207size_t
208prefix_length_in_bits(size_t level)
209{
210 return level * constants::merkle_fanout_bits;
211}
212
213size_t
214prefix_length_in_bytes(size_t level)
215{
216 // level is the number of levels in tree this prefix has.
217 // the prefix's binary *length* is the number of bytes used
218 // to represent it, rounded up to a byte.
219 size_t num_bits = prefix_length_in_bits(level);
220 if (num_bits % 8 == 0)
221 return num_bits / 8;
222 else
223 return (num_bits / 8) + 1;
224}
225
226void
227write_node(merkle_node const & in, string & outbuf)
228{
229 ostringstream oss;
230 oss.put(static_cast<u8>(in.type));
231 I(in.pref.size() == in.level * constants::merkle_fanout_bits);
232
233 string tmp;
234 insert_datum_uleb128<size_t>(in.level, tmp);
235 oss.write(tmp.data(), tmp.size());
236 tmp.clear();
237
238 to_block_range(in.pref, ostream_iterator<char>(oss));
239
240 insert_datum_uleb128<size_t>(in.total_num_leaves, tmp);
241 oss.write(tmp.data(), tmp.size());
242 tmp.clear();
243
244 to_block_range(in.bitmap, ostream_iterator<char>(oss));
245
246 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
247 {
248 if (in.get_slot_state(slot) != empty_state)
249 {
250 I(slot < in.slots.size());
251 id slot_val;
252 in.get_raw_slot(slot, slot_val);
253 oss.write(slot_val().data(), slot_val().size());
254 }
255 }
256 string hash = raw_sha1(oss.str());
257 I(hash.size() == constants::merkle_hash_length_in_bytes);
258 outbuf.append(hash);
259 outbuf.append(oss.str());
260}
261
262void
263read_node(string const & inbuf, size_t & pos, merkle_node & out)
264{
265 string hash = extract_substring(inbuf, pos,
266 constants::merkle_hash_length_in_bytes,
267 "node hash");
268 size_t begin_pos = pos;
269 out.type = static_cast<netcmd_item_type>(extract_datum_lsb<u8>(inbuf, pos, "node type"));
270 out.level = extract_datum_uleb128<size_t>(inbuf, pos, "node level");
271
272 if (out.level >= constants::merkle_num_tree_levels)
273 throw bad_decode(F("node level is %d, exceeds maximum %d")
274 % widen<u32,u8>(out.level)
275 % widen<u32,u8>(constants::merkle_num_tree_levels));
276
277 size_t prefixsz = prefix_length_in_bytes(out.level);
278 require_bytes(inbuf, pos, prefixsz, "node prefix");
279 out.pref.resize(prefix_length_in_bits(out.level));
280 from_block_range(inbuf.begin() + pos,
281 inbuf.begin() + pos + prefixsz,
282 out.pref);
283 pos += prefixsz;
284
285 out.total_num_leaves = extract_datum_uleb128<size_t>(inbuf, pos, "number of leaves");
286
287 require_bytes(inbuf, pos, constants::merkle_bitmap_length_in_bytes, "bitmap");
288 out.bitmap.resize(constants::merkle_bitmap_length_in_bits);
289 from_block_range(inbuf.begin() + pos,
290 inbuf.begin() + pos + constants::merkle_bitmap_length_in_bytes,
291 out.bitmap);
292 pos += constants::merkle_bitmap_length_in_bytes;
293
294 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
295 {
296 if (out.get_slot_state(slot) != empty_state)
297 {
298 string slot_val = extract_substring(inbuf, pos,
299 constants::merkle_hash_length_in_bytes,
300 "slot value");
301 out.set_raw_slot(slot, id(slot_val));
302 }
303 }
304
305 string checkhash = raw_sha1(inbuf.substr(begin_pos, pos - begin_pos));
306 out.check_invariants();
307 if (hash != checkhash)
308 throw bad_decode(F("mismatched node hash value %s, expected %s")
309 % xform<Botan::Hex_Encoder>(checkhash) % xform<Botan::Hex_Encoder>(hash));
310}
311
312
313// returns the first hashsz bytes of the serialized node, which is
314// the hash of its contents.
315
316static id
317hash_merkle_node(merkle_node const & node)
318{
319 string out;
320 write_node(node, out);
321 I(out.size() >= constants::merkle_hash_length_in_bytes);
322 return id(out.substr(0, constants::merkle_hash_length_in_bytes));
323}
324
325void
326pick_slot_and_prefix_for_value(id const & val,
327 size_t level,
328 size_t & slotnum,
329 dynamic_bitset<unsigned char> & pref)
330{
331 pref.resize(val().size() * 8);
332 from_block_range(val().begin(), val().end(), pref);
333
334 // remember, in a dynamic_bitset, bit size()-1 is most significant
335
336 slotnum = 0;
337 for (size_t i = constants::merkle_fanout_bits; i > 0; --i)
338 {
339 slotnum <<= 1;
340 if (pref[level * constants::merkle_fanout_bits + (i-1)])
341 slotnum |= static_cast<size_t>(1);
342 else
343 slotnum &= static_cast<size_t>(~1);
344 }
345 pref.resize(level * constants::merkle_fanout_bits);
346}
347
348id
349recalculate_merkle_codes(merkle_table & tab,
350 prefix const & pref,
351 size_t level)
352{
353 merkle_table::const_iterator i = tab.find(make_pair(pref, level));
354 I(i != tab.end());
355 merkle_ptr node = i->second;
356
357 for (size_t slotnum = 0; slotnum < constants::merkle_num_slots; ++slotnum)
358 {
359 slot_state st = node->get_slot_state(slotnum);
360 if (st == subtree_state)
361 {
362 id slotval;
363 node->get_raw_slot(slotnum, slotval);
364 if (slotval().empty())
365 {
366 prefix extended;
367 node->extended_raw_prefix(slotnum, extended);
368 slotval = recalculate_merkle_codes(tab, extended, level+1);
369 node->set_raw_slot(slotnum, slotval);
370 }
371 }
372 }
373
374 return hash_merkle_node(*node);
375}
376
377void
378collect_items_in_subtree(merkle_table & tab,
379 prefix const & pref,
380 size_t level,
381 set<id> & items)
382{
383 merkle_table::const_iterator i = tab.find(make_pair(pref, level));
384 merkle_ptr node;
385 prefix ext;
386 id item;
387 if (i != tab.end())
388 {
389 node = i->second;
390 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
391 {
392 switch (node->get_slot_state(slot))
393 {
394 case empty_state:
395 break;
396
397 case leaf_state:
398 node->get_raw_slot(slot, item);
399 items.insert(item);
400 break;
401
402 case subtree_state:
403 node->extended_raw_prefix(slot, ext);
404 collect_items_in_subtree(tab, ext, level+1, items);
405 break;
406 }
407 }
408 }
409}
410
411bool
412locate_item(merkle_table & table,
413 id const & val,
414 size_t & slotnum,
415 merkle_ptr & mp)
416{
417 mp.reset();
418 boost::dynamic_bitset<unsigned char> pref;
419 for (size_t l = 0; l < constants::merkle_num_tree_levels; ++l)
420 {
421 pick_slot_and_prefix_for_value(val, l, slotnum, pref);
422
423 prefix rawpref;
424 bitset_to_prefix(pref, rawpref);
425
426 merkle_table::const_iterator i = table.find(make_pair(rawpref, l));
427 if (i == table.end() ||
428 i->second->get_slot_state(slotnum) == empty_state)
429 return false;
430
431 if (i->second->get_slot_state(slotnum) == leaf_state)
432 {
433 id slotval;
434 i->second->get_raw_slot(slotnum, slotval);
435 if (slotval == val)
436 {
437 mp = i->second;
438 return true;
439 }
440 else
441 return false;
442 }
443 }
444 return false;
445}
446
447void
448insert_into_merkle_tree(merkle_table & tab,
449 netcmd_item_type type,
450 id const & leaf,
451 size_t level)
452{
453 I(constants::merkle_hash_length_in_bytes == leaf().size());
454 I(constants::merkle_fanout_bits * (level + 1)
455 <= constants::merkle_hash_length_in_bits);
456
457 size_t slotnum;
458 dynamic_bitset<unsigned char> pref;
459 pick_slot_and_prefix_for_value(leaf, level, slotnum, pref);
460
461 prefix rawpref;
462 bitset_to_prefix(pref, rawpref);
463
464 merkle_table::const_iterator i = tab.find(make_pair(rawpref, level));
465 merkle_ptr node;
466
467 if (i != tab.end())
468 {
469 node = i->second;
470 slot_state st = node->get_slot_state(slotnum);
471 switch (st)
472 {
473 case leaf_state:
474 {
475 id slotval;
476 node->get_raw_slot(slotnum, slotval);
477 if (slotval == leaf)
478 {
479 // Do nothing, it's already present
480 }
481 else
482 {
483 insert_into_merkle_tree(tab, type, slotval, level+1);
484 insert_into_merkle_tree(tab, type, leaf, level+1);
485 id empty_subtree_hash;
486 node->set_raw_slot(slotnum, empty_subtree_hash);
487 node->set_slot_state(slotnum, subtree_state);
488 }
489 }
490 break;
491
492 case empty_state:
493 node->total_num_leaves++;
494 node->set_slot_state(slotnum, leaf_state);
495 node->set_raw_slot(slotnum, leaf);
496 break;
497
498 case subtree_state:
499 {
500 insert_into_merkle_tree(tab, type, leaf, level+1);
501 id empty_subtree_hash;
502 node->set_raw_slot(slotnum, empty_subtree_hash);
503 node->set_slot_state(slotnum, subtree_state);
504 }
505 break;
506 }
507 }
508 else
509 {
510 node = merkle_ptr(new merkle_node());
511 node->type = type;
512 node->level = level;
513 node->pref = pref;
514 node->total_num_leaves = 1;
515 node->set_slot_state(slotnum, leaf_state);
516 node->set_raw_slot(slotnum, leaf);
517 tab.insert(make_pair(make_pair(rawpref, level), node));
518 }
519}
520
521// Local Variables:
522// mode: C++
523// fill-column: 76
524// c-file-style: "gnu"
525// indent-tabs-mode: nil
526// End:
527// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status