monotone

monotone Mtn Source Tree

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