monotone

monotone Mtn Source Tree

Root/merkle_tree.cc

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

Archive Download this file

Branches

Tags

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