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