/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to doc/hashes.txt

  • Committer: Martin Pool
  • Date: 2005-06-28 03:02:31 UTC
  • Revision ID: mbp@sourcefrog.net-20050628030231-d311e4ebcd467ef4
Merge John's import-speedup branch:

                                                                                         
  777 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:32 -0500
      revision-id: john@arbash-meinel.com-20050627032031-e82a50db3863b18e
      bzr selftest was not using the correct bzr

  776 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:22 -0500
      revision-id: john@arbash-meinel.com-20050627032021-c9f21fde989ddaee
      Add was using an old mutter

  775 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:02:33 -0500
      revision-id: john@arbash-meinel.com-20050627030233-9165cfe98fc63298
      Cleaned up to be less different

  774 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:54:53 -0500
      revision-id: john@arbash-meinel.com-20050627025452-4260d0e744edef43
      Allow BZR_PLUGIN_PATH='' to negate plugin loading.

  773 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:49:34 -0500
      revision-id: john@arbash-meinel.com-20050627024933-b7158f67b7b9eae5
      Finished the previous cleanup (allowing load_plugins to be called twice)

  772 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:45:08 -0500
      revision-id: john@arbash-meinel.com-20050627024508-723b1df510d196fc
      Work on making the tests pass. versioning.py is calling run_cmd directly, but plugins have been loaded.

  771 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:32:29 -0500
      revision-id: john@arbash-meinel.com-20050627023228-79972744d7c53e15
      Got it down a little bit more by removing import of tree and inventory.

  770 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:26:05 -0500
      revision-id: john@arbash-meinel.com-20050627022604-350b9773ef622f95
      Reducing the number of import from bzrlib/__init__.py and bzrlib/branch.py

  769 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:32:25 -0500
      revision-id: john@arbash-meinel.com-20050627013225-32dd044f10d23948
      Updated revision.py and xml.py to include SubElement.

  768 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:56 -0500
      revision-id: john@arbash-meinel.com-20050627010356-ee66919e1c377faf
      Minor typo

  767 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:13 -0500
      revision-id: john@arbash-meinel.com-20050627010312-40d024007eb85051
      Caching the import

  766 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:51:47 -0500
      revision-id: john@arbash-meinel.com-20050627005147-5281c99e48ed1834
      Created wrapper functions for lazy import of ElementTree

  765 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:46:37 -0500
      revision-id: john@arbash-meinel.com-20050627004636-bf432902004a94c5
      Removed all of the test imports of cElementTree

  764 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:43:59 -0500
      revision-id: john@arbash-meinel.com-20050627004358-d137fbe9570dd71b
      Trying to make bzr startup faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/hashes.txt
 
1
Use of hashes in Bazaar-NG
 
2
**************************
 
3
 
 
4
* http://infohost.nmt.edu/~val/review/hash.html
 
5
* http://infohost.nmt.edu/~val/review/hash2.html
 
6
 
 
7
The main attraction of hashes in bazaar-ng is as an easy way to get
 
8
universally-unique IDs, or at least with a low chance of collision:
 
9
 
 
10
The first paper is a bit paranoid; the second has some sensible
 
11
advice:
 
12
 
 
13
1. Will compare-by-hash provide significant benefit -- save time,
 
14
   bandwidth, etc?
 
15
 
 
16
2. Is the system usable if hash collisions can be generated at will?
 
17
 
 
18
3. Can the hashes be regenerated with a different algorithm at any
 
19
   time?
 
20
 
 
21
We should try to abide by these rules.  I think they are possibly too
 
22
paranoid -- a real break of SHA-1 would have much wider security
 
23
implications -- but if a design that respects them is practical, it
 
24
should be preferred.
 
25
 
 
26
The first is probably true; the third is just a matter of making sure
 
27
we allow for the choice of hash to be varied in the format.
 
28
 
 
29
There are actually two variations on the second:
 
30
 
 
31
2a. Is the system safe if an attacker can generate hash collisions?
 
32
 
 
33
2b. Is the system safe if a user's own files contain collisions.
 
34
 
 
35
Regardless of cryptographic weakness, SHA-1 is unlikely to
 
36
"accidentally" collide, but it's possible that someone will
 
37
intentionally generate collisions (in research on SHA) and then want
 
38
to store them.  It would be unfortunate if that did not work.
 
39
 
 
40
An advantage of naming by hash is that it lets us store only a single
 
41
copy of identical files, but we have already decided__ that disk space
 
42
is pretty cheap.  It is perhaps enough to have a single copy of files
 
43
that do not change from one tree revision to the next.
 
44
 
 
45
__ costs.html
 
46
 
 
47
As far as an attacker: we will not automatically trust that ids from
 
48
one branch have the same value in another.  It is possible for a
 
49
branch to contain "lies" about its history or contents, but that
 
50
doesn't corrupt anything else.  It may confuse or mislead someone who
 
51
looks at the branch, but there is no substitute for human review
 
52
anyhow.
 
53
 
 
54
-------
 
55
 
 
56
The safest position may be to never rely on identifying content by
 
57
hash.  Rather, things which need a universally unique ID should get a
 
58
UUID instead.
 
59
 
 
60
This has a slight advantage that the id can be stored directly in the
 
61
object it refers to, when that's useful.
 
62
 
 
63
So a `Revision` holds a UUID for the `Inventory`.  
 
64
 
 
65
An inventory holds `InventoryEntry` objects, each with
 
66
 
 
67
* file-id
 
68
* filename (location in tree)
 
69
* type (file, dir, etc)
 
70
* text-id (uuid identifying the text)
 
71
* text-sha1
 
72
* text-length (for catching bugs)
 
73
* parent-file-id