Secure mobile code presents many interesting problems. Among them is the issue of "distributed linking". How does module "a" import module "b"? How is this import resolved? In what namespace? Can an attacker preload his own "b" into some target vat's namespace, such that "a" imports that version rather than the version he desired? Can we protect "a" against such attacks, but still benefit from distributed replicated caching of code that someone might import?
It turns out that the design of the old Electric Communities (aka Communities.com) "Repository System", created mostly by Monica Anderson (cc'ed on this message) can solve most of these problems, even though it was built to solve a "different" problem. Actually, I just never noticed before that the problem the Repository set out to solve is the general case of the mobile code distributed-linking problem.
Repository Recap
The Repository was built to solve (and, in the beta of EC Habitats, solved) the problem of distributed unspoofable caching of acyclicly-linked large data blobs. Engineering observation: cryptographic hashes don't collide. Therefore, if you store and retrieve data by its hash, you need never worry about collision management. In other words, data blobs and hashes of those blobs are in one-to-one correspondence. (Of course, Shannon would have a fit, but, as Sussman and Abelson might say, this is the difference between engineering and science.) Therefore, a hash can be used as a compact designator of any data blob. The data can be looked up from any source, whether trusted or not, as long as the recipient of the data re-hashes it to ensure that it is indeed the data designated by the hash.
In Original-E, on which EC Habitats was built, capabilities & symbolic traffic were transmitted over the equivalent of today's Pluribus protocol. However, when Alice wanted to send a large bitmap to Bob, she did not transmit the bitmap over Pluribus. Rather, she "published" the bitmap to her Repository, and sent to Bob over Pluribus a designator of the bitmap: the hash of the bitmap + a "location hint" pointing at her Repository as a plausible place to obtain the bitmap.
Bob, on receiving this bitmap designator, asked his own Repository for the corresponding data blob, and got back a promise for the answer. If his Repository already had an entry for this hash, this promise would be fulfilled promptly. Otherwise, his Repository would contact at least Alice's Repository to obtain an alleged answer. On receiving data from Alice's Repository, Bob's Repository would re-hash to ensure it was correct, and if so, both cache it locally and fulfill the promise handed to Bob. Bob's Repository is part of Bob's TCB, but Alice's Repository is not. Therefore Bob's Repository had to rehash the data obtained from Alice's Repository, but Bob doesn't need to re-hash data obtained from his own Repository.
Advantages:
Security Issues:
Acyclic Linking
Of course, besides pure data per se, the data of a blob can include such hash-based designators of other blobs. The Repository required no mechanism to support this -- just as it was up to the client to interpret data as a bitmap, it was up to the client to interpret nested data designators and perform further fetches from the Repository.
Of course, during development the source form of each such data blob would usually need to specify not a particular edition of some other data blob, but (implicitly) the "current version". In building blobs from blob-sources, such development-time inter-blob names (in some development-time namespace) gets turned into namespace-free hash-based inter-blob designators. (Lightbulb) This can be seen as a build-time static linking step. Unfortunately, this solution works only for acyclic blob structures, which was fine for all the data we dealt with then, but doesn't work at all for code. (The EC Habitats beta didn't do mobile code.)
On to Cycles in Part 2.
Cheers,
--MarkM