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 <map>
11#include <string>
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::get_hex_slot(size_t slot, hexenc<id> & val) const
138{
139 id i;
140 get_raw_slot(slot, i);
141 encode_hexenc(i, val);
142}
143
144void
145merkle_node::set_raw_slot(size_t slot, id const & val)
146{
147 check_invariants();
148 idx(this->slots, slot) = val;
149}
150
151void
152merkle_node::set_hex_slot(size_t slot, hexenc<id> const & val)
153{
154 id i;
155 decode_hexenc(val, i);
156 set_raw_slot(slot, i);
157}
158
159void
160merkle_node::extended_prefix(size_t slot,
161 dynamic_bitset<unsigned char> & extended) const
162{
163 // remember, in a dynamic_bitset, bit size()-1 is most significant
164 check_invariants();
165 I(slot < constants::merkle_num_slots);
166 extended = this->pref;
167 for (size_t i = 0; i < constants::merkle_fanout_bits; ++i)
168 extended.push_back(static_cast<bool>((slot >> i) & 1));
169}
170
171void
172merkle_node::extended_raw_prefix(size_t slot,
173 prefix & extended) const
174{
175 dynamic_bitset<unsigned char> ext;
176 extended_prefix(slot, ext);
177 bitset_to_prefix(ext, extended);
178}
179
180void
181merkle_node::extended_hex_prefix(size_t slot,
182 hexenc<prefix> & extended) const
183{
184 prefix pref;
185 extended_raw_prefix(slot, pref);
186 encode_hexenc(pref, extended);
187}
188
189slot_state
190merkle_node::get_slot_state(size_t n) const
191{
192 check_invariants();
193 I(n < constants::merkle_num_slots);
194 I(2*n + 1 < bitmap.size());
195 if (bitmap[2*n])
196 {
197 if (bitmap[2*n+1])
198 return subtree_state;
199 else
200 return leaf_state;
201 }
202 else
203 {
204 return empty_state;
205 }
206}
207
208void
209merkle_node::set_slot_state(size_t n, slot_state st)
210{
211 check_invariants();
212 I(n < constants::merkle_num_slots);
213 I(2*n + 1 < bitmap.size());
214 bitmap.reset(2*n);
215 bitmap.reset(2*n+1);
216 if (st == subtree_state || st == leaf_state)
217 bitmap.set(2*n);
218 if (st == subtree_state)
219 bitmap.set(2*n+1);
220}
221
222
223size_t
224prefix_length_in_bits(size_t level)
225{
226 return level * constants::merkle_fanout_bits;
227}
228
229size_t
230prefix_length_in_bytes(size_t level)
231{
232 // level is the number of levels in tree this prefix has.
233 // the prefix's binary *length* is the number of bytes used
234 // to represent it, rounded up to a byte.
235 size_t num_bits = prefix_length_in_bits(level);
236 if (num_bits % 8 == 0)
237 return num_bits / 8;
238 else
239 return (num_bits / 8) + 1;
240}
241
242void
243write_node(merkle_node const & in, string & outbuf)
244{
245 ostringstream oss;
246 oss.put(static_cast<u8>(in.type));
247 I(in.pref.size() == in.level * constants::merkle_fanout_bits);
248
249 string tmp;
250 insert_datum_uleb128<size_t>(in.level, tmp);
251 oss.write(tmp.data(), tmp.size());
252 tmp.clear();
253
254 to_block_range(in.pref, ostream_iterator<char>(oss));
255
256 insert_datum_uleb128<size_t>(in.total_num_leaves, tmp);
257 oss.write(tmp.data(), tmp.size());
258 tmp.clear();
259
260 to_block_range(in.bitmap, ostream_iterator<char>(oss));
261
262 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
263 {
264 if (in.get_slot_state(slot) != empty_state)
265 {
266 I(slot < in.slots.size());
267 id slot_val;
268 in.get_raw_slot(slot, slot_val);
269 oss.write(slot_val().data(), slot_val().size());
270 }
271 }
272 string hash = raw_sha1(oss.str());
273 I(hash.size() == constants::merkle_hash_length_in_bytes);
274 outbuf.append(hash);
275 outbuf.append(oss.str());
276}
277
278void
279read_node(string const & inbuf, size_t & pos, merkle_node & out)
280{
281 string hash = extract_substring(inbuf, pos,
282 constants::merkle_hash_length_in_bytes,
283 "node hash");
284 size_t begin_pos = pos;
285 out.type = static_cast<netcmd_item_type>(extract_datum_lsb<u8>(inbuf, pos, "node type"));
286 out.level = extract_datum_uleb128<size_t>(inbuf, pos, "node level");
287
288 if (out.level >= constants::merkle_num_tree_levels)
289 throw bad_decode(F("node level is %d, exceeds maximum %d")
290 % widen<u32,u8>(out.level)
291 % widen<u32,u8>(constants::merkle_num_tree_levels));
292
293 size_t prefixsz = prefix_length_in_bytes(out.level);
294 require_bytes(inbuf, pos, prefixsz, "node prefix");
295 out.pref.resize(prefix_length_in_bits(out.level));
296 from_block_range(inbuf.begin() + pos,
297 inbuf.begin() + pos + prefixsz,
298 out.pref);
299 pos += prefixsz;
300
301 out.total_num_leaves = extract_datum_uleb128<size_t>(inbuf, pos, "number of leaves");
302
303 require_bytes(inbuf, pos, constants::merkle_bitmap_length_in_bytes, "bitmap");
304 out.bitmap.resize(constants::merkle_bitmap_length_in_bits);
305 from_block_range(inbuf.begin() + pos,
306 inbuf.begin() + pos + constants::merkle_bitmap_length_in_bytes,
307 out.bitmap);
308 pos += constants::merkle_bitmap_length_in_bytes;
309
310 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
311 {
312 if (out.get_slot_state(slot) != empty_state)
313 {
314 string slot_val = extract_substring(inbuf, pos,
315 constants::merkle_hash_length_in_bytes,
316 "slot value");
317 out.set_raw_slot(slot, id(slot_val));
318 }
319 }
320
321 string checkhash = raw_sha1(inbuf.substr(begin_pos, pos - begin_pos));
322 out.check_invariants();
323 if (hash != checkhash)
324 throw bad_decode(F("mismatched node hash value %s, expected %s")
325 % xform<Botan::Hex_Encoder>(checkhash) % xform<Botan::Hex_Encoder>(hash));
326}
327
328
329// returns the first hashsz bytes of the serialized node, which is
330// the hash of its contents.
331
332static id
333hash_merkle_node(merkle_node const & node)
334{
335 string out;
336 write_node(node, out);
337 I(out.size() >= constants::merkle_hash_length_in_bytes);
338 return id(out.substr(0, constants::merkle_hash_length_in_bytes));
339}
340
341void
342pick_slot_and_prefix_for_value(id const & val,
343 size_t level,
344 size_t & slotnum,
345 dynamic_bitset<unsigned char> & pref)
346{
347 pref.resize(val().size() * 8);
348 from_block_range(val().begin(), val().end(), pref);
349
350 // remember, in a dynamic_bitset, bit size()-1 is most significant
351
352 slotnum = 0;
353 for (size_t i = constants::merkle_fanout_bits; i > 0; --i)
354 {
355 slotnum <<= 1;
356 if (pref[level * constants::merkle_fanout_bits + (i-1)])
357 slotnum |= static_cast<size_t>(1);
358 else
359 slotnum &= static_cast<size_t>(~1);
360 }
361 pref.resize(level * constants::merkle_fanout_bits);
362}
363
364id
365recalculate_merkle_codes(merkle_table & tab,
366 prefix const & pref,
367 size_t level)
368{
369 merkle_table::const_iterator i = tab.find(make_pair(pref, level));
370 I(i != tab.end());
371 merkle_ptr node = i->second;
372
373 for (size_t slotnum = 0; slotnum < constants::merkle_num_slots; ++slotnum)
374 {
375 slot_state st = node->get_slot_state(slotnum);
376 if (st == subtree_state)
377 {
378 id slotval;
379 node->get_raw_slot(slotnum, slotval);
380 if (slotval().empty())
381 {
382 prefix extended;
383 node->extended_raw_prefix(slotnum, extended);
384 slotval = recalculate_merkle_codes(tab, extended, level+1);
385 node->set_raw_slot(slotnum, slotval);
386 }
387 }
388 }
389
390 return hash_merkle_node(*node);
391}
392
393void
394collect_items_in_subtree(merkle_table & tab,
395 prefix const & pref,
396 size_t level,
397 set<id> & items)
398{
399 merkle_table::const_iterator i = tab.find(make_pair(pref, level));
400 merkle_ptr node;
401 prefix ext;
402 id item;
403 if (i != tab.end())
404 {
405 node = i->second;
406 for (size_t slot = 0; slot < constants::merkle_num_slots; ++slot)
407 {
408 switch (node->get_slot_state(slot))
409 {
410 case empty_state:
411 break;
412
413 case leaf_state:
414 node->get_raw_slot(slot, item);
415 items.insert(item);
416 break;
417
418 case subtree_state:
419 node->extended_raw_prefix(slot, ext);
420 collect_items_in_subtree(tab, ext, level+1, items);
421 break;
422 }
423 }
424 }
425}
426
427bool
428locate_item(merkle_table & table,
429 id const & val,
430 size_t & slotnum,
431 merkle_ptr & mp)
432{
433 mp.reset();
434 boost::dynamic_bitset<unsigned char> pref;
435 for (size_t l = 0; l < constants::merkle_num_tree_levels; ++l)
436 {
437 pick_slot_and_prefix_for_value(val, l, slotnum, pref);
438
439 prefix rawpref;
440 bitset_to_prefix(pref, rawpref);
441
442 merkle_table::const_iterator i = table.find(make_pair(rawpref, l));
443 if (i == table.end() ||
444 i->second->get_slot_state(slotnum) == empty_state)
445 return false;
446
447 if (i->second->get_slot_state(slotnum) == leaf_state)
448 {
449 id slotval;
450 i->second->get_raw_slot(slotnum, slotval);
451 if (slotval == val)
452 {
453 mp = i->second;
454 return true;
455 }
456 else
457 return false;
458 }
459 }
460 return false;
461}
462
463void
464insert_into_merkle_tree(merkle_table & tab,
465 netcmd_item_type type,
466 id const & leaf,
467 size_t level)
468{
469 I(constants::merkle_hash_length_in_bytes == leaf().size());
470 I(constants::merkle_fanout_bits * (level + 1)
471 <= constants::merkle_hash_length_in_bits);
472
473 size_t slotnum;
474 dynamic_bitset<unsigned char> pref;
475 pick_slot_and_prefix_for_value(leaf, level, slotnum, pref);
476
477 prefix rawpref;
478 bitset_to_prefix(pref, rawpref);
479
480 merkle_table::const_iterator i = tab.find(make_pair(rawpref, level));
481 merkle_ptr node;
482
483 if (i != tab.end())
484 {
485 node = i->second;
486 slot_state st = node->get_slot_state(slotnum);
487 switch (st)
488 {
489 case leaf_state:
490 {
491 id slotval;
492 node->get_raw_slot(slotnum, slotval);
493 if (slotval == leaf)
494 {
495 // Do nothing, it's already present
496 }
497 else
498 {
499 insert_into_merkle_tree(tab, type, slotval, level+1);
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 }
506 break;
507
508 case empty_state:
509 node->total_num_leaves++;
510 node->set_slot_state(slotnum, leaf_state);
511 node->set_raw_slot(slotnum, leaf);
512 break;
513
514 case subtree_state:
515 {
516 insert_into_merkle_tree(tab, type, leaf, level+1);
517 id empty_subtree_hash;
518 node->set_raw_slot(slotnum, empty_subtree_hash);
519 node->set_slot_state(slotnum, subtree_state);
520 }
521 break;
522 }
523 }
524 else
525 {
526 node = merkle_ptr(new merkle_node());
527 node->type = type;
528 node->level = level;
529 node->pref = pref;
530 node->total_num_leaves = 1;
531 node->set_slot_state(slotnum, leaf_state);
532 node->set_raw_slot(slotnum, leaf);
533 tab.insert(make_pair(make_pair(rawpref, level), node));
534 }
535}
536
537// Local Variables:
538// mode: C++
539// fill-column: 76
540// c-file-style: "gnu"
541// indent-tabs-mode: nil
542// End:
543// 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