source file: /home/buildslave/tahoe/edgy/build/src/allmydata/hashtree.py
file stats: 166 lines, 166 executed: 100.0% covered
coverage versus previous test: 0 lines added, 0 lines removed
1. # -*- test-case-name: allmydata.test.test_hashtree -*-
2.
3. from allmydata.util import mathutil # from the pyutil library
4.
5. """
6. Read and write chunks from files.
7.
8. Version 1.0.0.
9.
10. A file is divided into blocks, each of which has size L{BLOCK_SIZE}
11. (except for the last block, which may be smaller). Blocks are encoded
12. into chunks. One publishes the hash of the entire file. Clients
13. who want to download the file first obtain the hash, then the clients
14. can receive chunks in any order. Cryptographic hashing is used to
15. verify each received chunk before writing to disk. Thus it is
16. impossible to download corrupt data if one has the correct file hash.
17.
18. One obtains the hash of a complete file via
19. L{CompleteChunkFile.file_hash}. One can read chunks from a complete
20. file by the sequence operations of C{len()} and subscripting on a
21. L{CompleteChunkFile} object. One can open an empty or partially
22. downloaded file with L{PartialChunkFile}, and read and write chunks
23. to this file. A chunk will fail to write if its contents and index
24. are not consistent with the overall file hash passed to
25. L{PartialChunkFile} when the partial chunk file was first created.
26.
27. The chunks have an overhead of less than 4% for files of size
28. less than C{10**20} bytes.
29.
30. Benchmarks:
31.
32. - On a 3 GHz Pentium 3, it took 3.4 minutes to first make a
33. L{CompleteChunkFile} object for a 4 GB file. Up to 10 MB of
34. memory was used as the constructor ran. A metafile filename
35. was passed to the constructor, and so the hash information was
36. written to the metafile. The object used a negligible amount
37. of memory after the constructor was finished.
38. - Creation of L{CompleteChunkFile} objects in future runs of the
39. program took negligible time, since the hash information was
40. already stored in the metafile.
41.
42. @var BLOCK_SIZE: Size of a block. See L{BlockFile}.
43. @var MAX_CHUNK_SIZE: Upper bound on the size of a chunk.
44. See L{CompleteChunkFile}.
45.
46. free (adj.): unencumbered; not under the control of others
47. Written by Connelly Barnes in 2005 and released into the
48. public domain with no warranty of any kind, either expressed
49. or implied. It probably won't make your computer catch on fire,
50. or eat your children, but it might. Use at your own risk.
51. """
52.
53. from allmydata.util import base32
54. from allmydata.util.hashutil import tagged_hash, tagged_pair_hash
55.
56. __version__ = '1.0.0-allmydata'
57.
58. BLOCK_SIZE = 65536
59. MAX_CHUNK_SIZE = BLOCK_SIZE + 4096
60.
61. def roundup_pow2(x):
62. """
63. Round integer C{x} up to the nearest power of 2.
64. """
65. ans = 1
66. while ans < x:
67. ans *= 2
68. return ans
69.
70.
71. class CompleteBinaryTreeMixin:
72. """
73. Adds convenience methods to a complete binary tree.
74.
75. Assumes the total number of elements in the binary tree may be
76. accessed via C{__len__}, and that each element can be retrieved
77. using list subscripting.
78.
79. Tree is indexed like so::
80.
81.
82. 0
83. / \
84. 1 2
85. / \ / \
86. 3 4 5 6
87. / \ / \ / \ / \
88. 7 8 9 10 11 12 13 14
89.
90. """
91.
92. def parent(self, i):
93. """
94. Index of the parent of C{i}.
95. """
96. if i < 1 or (hasattr(self, '__len__') and i >= len(self)):
97. raise IndexError('index out of range: ' + repr(i))
98. return (i - 1) // 2
99.
100. def lchild(self, i):
101. """
102. Index of the left child of C{i}.
103. """
104. ans = 2 * i + 1
105. if i < 0 or (hasattr(self, '__len__') and ans >= len(self)):
106. raise IndexError('index out of range: ' + repr(i))
107. return ans
108.
109. def rchild(self, i):
110. """
111. Index of right child of C{i}.
112. """
113. ans = 2 * i + 2
114. if i < 0 or (hasattr(self, '__len__') and ans >= len(self)):
115. raise IndexError('index out of range: ' + repr(i))
116. return ans
117.
118. def sibling(self, i):
119. """
120. Index of sibling of C{i}.
121. """
122. parent = self.parent(i)
123. if self.lchild(parent) == i:
124. return self.rchild(parent)
125. else:
126. return self.lchild(parent)
127.
128. def needed_for(self, i):
129. """
130. Return a list of node indices that are necessary for the hash chain.
131. """
132. if i < 0 or i >= len(self):
133. raise IndexError('index out of range: 0 >= %s < %s' % (i, len(self)))
134. needed = []
135. here = i
136. while here != 0:
137. needed.append(self.sibling(here))
138. here = self.parent(here)
139. return needed
140.
141. def depth_first(self, i=0):
142. yield i, 0
143. try:
144. for child,childdepth in self.depth_first(self.lchild(i)):
145. yield child, childdepth+1
146. except IndexError:
147. pass
148. try:
149. for child,childdepth in self.depth_first(self.rchild(i)):
150. yield child, childdepth+1
151. except IndexError:
152. pass
153.
154. def dump(self):
155. lines = []
156. for i,depth in self.depth_first():
157. lines.append("%s%3d: %s" % (" "*depth, i,
158. base32.b2a_or_none(self[i])))
159. return "\n".join(lines) + "\n"
160.
161. def get_leaf_index(self, leafnum):
162. return self.first_leaf_num + leafnum
163.
164. def get_leaf(self, leafnum):
165. return self[self.first_leaf_num + leafnum]
166.
167. def depth_of(i):
168. """Return the depth or level of the given node. Level 0 contains node 0
169. Level 1 contains nodes 1 and 2. Level 2 contains nodes 3,4,5,6."""
170. return mathutil.log_floor(i+1, 2)
171.
172. def empty_leaf_hash(i):
173. return tagged_hash('Merkle tree empty leaf', "%d" % i)
174. def pair_hash(a, b):
175. return tagged_pair_hash('Merkle tree internal node', a, b)
176.
177. class HashTree(CompleteBinaryTreeMixin, list):
178. """
179. Compute Merkle hashes at any node in a complete binary tree.
180.
181. Tree is indexed like so::
182.
183.
184. 0
185. / \
186. 1 2
187. / \ / \
188. 3 4 5 6
189. / \ / \ / \ / \
190. 7 8 9 10 11 12 13 14 <- List passed to constructor.
191.
192. """
193.
194. def __init__(self, L):
195. """
196. Create complete binary tree from list of hash strings.
197.
198. The list is augmented by hashes so its length is a power of 2, and
199. then this is used as the bottom row of the hash tree.
200.
201. The augmenting is done so that if the augmented element is at index
202. C{i}, then its value is C{hash(tagged_hash('Merkle tree empty leaf',
203. '%d'%i))}.
204. """
205.
206. # Augment the list.
207. start = len(L)
208. end = roundup_pow2(len(L))
209. self.first_leaf_num = end - 1
210. L = L + [None] * (end - start)
211. for i in range(start, end):
212. L[i] = empty_leaf_hash(i)
213. # Form each row of the tree.
214. rows = [L]
215. while len(rows[-1]) != 1:
216. last = rows[-1]
217. rows += [[pair_hash(last[2*i], last[2*i+1])
218. for i in xrange(len(last)//2)]]
219. # Flatten the list of rows into a single list.
220. rows.reverse()
221. self[:] = sum(rows, [])
222.
223. def needed_hashes(self, leafnum, include_leaf=False):
224. """Which hashes will someone need to validate a given data block?
225.
226. I am used to answer a question: supposing you have the data block
227. that is used to form leaf hash N, and you want to validate that it,
228. which hashes would you need?
229.
230. I accept a leaf number and return a set of 'hash index' values, which
231. are integers from 0 to len(self). In the 'hash index' number space,
232. hash[0] is the root hash, while hash[len(self)-1] is the last leaf
233. hash.
234.
235. This method can be used to find out which hashes you should request
236. from some untrusted source (usually the same source that provides the
237. data block), so you can minimize storage or transmission overhead. It
238. can also be used to determine which hashes you should send to a
239. remote data store so that it will be able to provide validatable data
240. in the future.
241.
242. I will not include '0' (the root hash) in the result, since the root
243. is generally stored somewhere that is more trusted than the source of
244. the remaining hashes. I will include the leaf hash itself only if you
245. ask me to, by passing include_leaf=True.
246. """
247.
248. needed = set(self.needed_for(self.first_leaf_num + leafnum))
249. if include_leaf:
250. needed.add(self.first_leaf_num + leafnum)
251. return needed
252.
253.
254. class NotEnoughHashesError(Exception):
255. pass
256.
257. class BadHashError(Exception):
258. pass
259.
260. class IncompleteHashTree(CompleteBinaryTreeMixin, list):
261. """I am a hash tree which may or may not be complete. I can be used to
262. validate inbound data from some untrustworthy provider who has a subset
263. of leaves and a sufficient subset of internal nodes.
264.
265. Initially I am completely unpopulated. Over time, I will become filled
266. with hashes, just enough to validate particular leaf nodes.
267.
268. If you desire to validate leaf number N, first find out which hashes I
269. need by calling needed_hashes(N). This will return a list of node numbers
270. (which will nominally be the sibling chain between the given leaf and the
271. root, but if I already have some of those nodes, needed_hashes(N) will
272. only return a subset). Obtain these hashes from the data provider, then
273. tell me about them with set_hash(i, HASH). Once I have enough hashes, you
274. can tell me the hash of the leaf with set_leaf_hash(N, HASH), and I will
275. either return None or raise BadHashError.
276.
277. The first hash to be set will probably be 0 (the root hash), since this
278. is the one that will come from someone more trustworthy than the data
279. provider.
280.
281. """
282.
283. def __init__(self, num_leaves):
284. L = [None] * num_leaves
285. start = len(L)
286. end = roundup_pow2(len(L))
287. self.first_leaf_num = end - 1
288. L = L + [None] * (end - start)
289. rows = [L]
290. while len(rows[-1]) != 1:
291. last = rows[-1]
292. rows += [[None for i in xrange(len(last)//2)]]
293. # Flatten the list of rows into a single list.
294. rows.reverse()
295. self[:] = sum(rows, [])
296.
297.
298. def needed_hashes(self, leafnum, include_leaf=False):
299. """Which new hashes do I need to validate a given data block?
300.
301. I am much like HashTree.needed_hashes(), except that I don't include
302. hashes that I already know about. When needed_hashes() is called on
303. an empty IncompleteHashTree, it will return the same set as a
304. HashTree of the same size. But later, once hashes have been added
305. with set_hashes(), I will ask for fewer hashes, since some of the
306. necessary ones have already been set.
307. """
308.
309. maybe_needed = set(self.needed_for(self.first_leaf_num + leafnum))
310. if include_leaf:
311. maybe_needed.add(self.first_leaf_num + leafnum)
312. return set([i for i in maybe_needed if self[i] is None])
313.
314. def _name_hash(self, i):
315. name = "[%d of %d]" % (i, len(self))
316. if i >= self.first_leaf_num:
317. leafnum = i - self.first_leaf_num
318. numleaves = len(self) - self.first_leaf_num
319. name += " (leaf [%d] of %d)" % (leafnum, numleaves)
320. return name
321.
322. def set_hashes(self, hashes={}, leaves={}):
323. """Add a bunch of hashes to the tree.
324.
325. I will validate these to the best of my ability. If I already have a
326. copy of any of the new hashes, the new values must equal the existing
327. ones, or I will raise BadHashError. If adding a hash allows me to
328. compute a parent hash, those parent hashes must match or I will raise
329. BadHashError. If I raise BadHashError, I will forget about all the
330. hashes that you tried to add, leaving my state exactly the same as
331. before I was called. If I return successfully, I will remember all
332. those hashes.
333.
334. I insist upon being able to validate all of the hashes that were
335. given to me. If I cannot do this because I'm missing some hashes, I
336. will raise NotEnoughHashesError (and forget about all the hashes that
337. you tried to add). Note that this means that the root hash must
338. either be included in 'hashes', or it must have been provided at some
339. point in the past.
340.
341. 'leaves' is a dictionary uses 'leaf index' values, which range from 0
342. (the left-most leaf) to num_leaves-1 (the right-most leaf), and form
343. the base of the tree. 'hashes' uses 'hash_index' values, which range
344. from 0 (the root of the tree) to 2*num_leaves-2 (the right-most
345. leaf). leaf[i] is the same as hash[num_leaves-1+i].
346.
347. The best way to use me is to start by obtaining the root hash from
348. some 'good' channel and populate me with it:
349.
350. iht = IncompleteHashTree(numleaves)
351. roothash = trusted_channel.get_roothash()
352. iht.set_hashes(hashes={0: roothash})
353.
354. Then use the 'bad' channel to obtain data block 0 and the
355. corresponding hash chain (a dict with the same hashes that
356. needed_hashes(0) tells you, e.g. {0:h0, 2:h2, 4:h4, 8:h8} when
357. len(L)=8). Hash the data block to create leaf0, then feed everything
358. into set_hashes() and see if it raises an exception or not::
359.
360. otherhashes = untrusted_channel.get_hashes()
361. # otherhashes.keys() should == iht.needed_hashes(leaves=[0])
362. datablock0 = untrusted_channel.get_data(0)
363. leaf0 = HASH(datablock0)
364. # HASH() is probably hashutil.tagged_hash(tag, datablock0)
365. iht.set_hashes(otherhashes, leaves={0: leaf0})
366.
367. If the set_hashes() call doesn't raise an exception, the data block
368. was valid. If it raises BadHashError, then either the data block was
369. corrupted or one of the received hashes was corrupted. If it raises
370. NotEnoughHashesError, then the otherhashes dictionary was incomplete.
371. """
372.
373. assert isinstance(hashes, dict)
374. for h in hashes.values():
375. assert isinstance(h, str)
376. assert isinstance(leaves, dict)
377. for h in leaves.values():
378. assert isinstance(h, str)
379. new_hashes = hashes.copy()
380. for leafnum,leafhash in leaves.iteritems():
381. hashnum = self.first_leaf_num + leafnum
382. if hashnum in new_hashes:
383. if new_hashes[hashnum] != leafhash:
384. raise BadHashError("got conflicting hashes in my "
385. "arguments: leaves[%d] != hashes[%d]"
386. % (leafnum, hashnum))
387. new_hashes[hashnum] = leafhash
388.
389. remove_upon_failure = set() # we'll remove these if the check fails
390.
391. # visualize this method in the following way:
392. # A: start with the empty or partially-populated tree as shown in
393. # the HashTree docstring
394. # B: add all of our input hashes to the tree, filling in some of the
395. # holes. Don't overwrite anything, but new values must equal the
396. # existing ones. Mark everything that was added with a red dot
397. # (meaning "not yet validated")
398. # C: start with the lowest/deepest level. Pick any red-dotted node,
399. # hash it with its sibling to compute the parent hash. Add the
400. # parent to the tree just like in step B (if the parent already
401. # exists, the values must be equal; if not, add our computed
402. # value with a red dot). If we have no sibling, throw
403. # NotEnoughHashesError, since we won't be able to validate this
404. # node. Remove the red dot. If there was a red dot on our
405. # sibling, remove it too.
406. # D: finish all red-dotted nodes in one level before moving up to
407. # the next.
408. # E: if we hit NotEnoughHashesError or BadHashError before getting
409. # to the root, discard every hash we've added.
410.
411. try:
412. num_levels = depth_of(len(self)-1)
413. # hashes_to_check[level] is set(index). This holds the "red dots"
414. # described above
415. hashes_to_check = [set() for level in range(num_levels+1)]
416.
417. # first we provisionally add all hashes to the tree, comparing
418. # any duplicates
419. for i,h in new_hashes.iteritems():
420. if self[i]:
421. if self[i] != h:
422. raise BadHashError("new hash %s does not match "
423. "existing hash %s at %s"
424. % (base32.b2a(h),
425. base32.b2a(self[i]),
426. self._name_hash(i)))
427. else:
428. level = depth_of(i)
429. hashes_to_check[level].add(i)
430. self[i] = h
431. remove_upon_failure.add(i)
432.
433. for level in reversed(range(len(hashes_to_check))):
434. this_level = hashes_to_check[level]
435. while this_level:
436. i = this_level.pop()
437. if i == 0:
438. # The root has no sibling. How lonely. You can't
439. # really *check* the root; you either accept it
440. # because the caller told you what it is by including
441. # it in hashes, or you accept it because you
442. # calculated it from its two children. You probably
443. # want to set the root (from a trusted source) before
444. # adding any children from an untrusted source.
445. continue
446. siblingnum = self.sibling(i)
447. if self[siblingnum] is None:
448. # without a sibling, we can't compute a parent, and
449. # we can't verify this node
450. raise NotEnoughHashesError("unable to validate [%d]"%i)
451. parentnum = self.parent(i)
452. # make sure we know right from left
453. leftnum, rightnum = sorted([i, siblingnum])
454. new_parent_hash = pair_hash(self[leftnum], self[rightnum])
455. if self[parentnum]:
456. if self[parentnum] != new_parent_hash:
457. raise BadHashError("h([%d]+[%d]) != h[%d]" %
458. (leftnum, rightnum, parentnum))
459. else:
460. self[parentnum] = new_parent_hash
461. remove_upon_failure.add(parentnum)
462. parent_level = depth_of(parentnum)
463. assert parent_level == level-1
464. hashes_to_check[parent_level].add(parentnum)
465.
466. # our sibling is now as valid as this node
467. this_level.discard(siblingnum)
468. # we're done!
469.
470. except (BadHashError, NotEnoughHashesError):
471. for i in remove_upon_failure:
472. self[i] = None
473. raise