Root and Branch Naming
Ross
ross.anderson@cl.cam.ac.uk
Mon, 19 Mar 2001 04:09:57 -0500
Ted discusses using hash trees for the higher, more stable levels in
the directory structure and more flexible mechanisms lower down.
This works; we used something like it for a drug database system. The
goal was to provide an electronic equivalent of the drug reference
book that doctors carry around with them. We started off with a simple
hash tree and authenticated everything by a root hash which changed
only when the book was republished every six months. This was far, far
more efficient than signing the book - no-one wants to compute a
digital signature on 8Mb every time they need to check up on the side
effects of aspirin!
Then we found a need for flexibility. For example, hospitals annotate
particular drugs for cost control reasons: `only Dr Edwards can
prescribe this' or `use XXX instead unless authorised by Dr Jones'.
Also, additional drugs are added to local databases which don't appear
in the national, published one: the classic example is an experimental
substance undergoing clinical trials.
The trick was to introduce a `flexible link' - basically, instead of
hashing the content of the stuff lower down, you hash a public key and
sign the stuff lower down with the corresponding private key. This way
you can have a trustworthy static book, but with some active pages.
There's a bit more you need to do to manage meta-content, as you'd
expect. See <http://www.cl.cam.ac.uk/~fapp2/papers/ec98-erl/> for the
paper we wrote on this; related papers are on the P2P part of my web
page, <http://www.cl.cam.ac.uk/users/rja14/#Peer-to-Peer>,
Ross