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

Archive Download this file

Branches

Tags

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