We assume a collection of somewhat uniform nodes in each of which there is capability security but no secrecy—as if each program therein had read-access to the entire RAM and disk. Also included are communication links between some pairs of nodes. At this architecture level all capabilities are local. Remote capabilities are natural but would be built upon features described here.
We shall require authenticated communications and this may require a shared secret at the two ends of a link. Message Authentication Codes (MACs) can detect message tampering. Sending a packet with (SHA(secret || message) || message) allows the program at the other end, who shares the secret, to recompute SHA(secret || message) and compare it with the transmitted value. If the message includes a serial number then replay and packet loss are controlled. (See Schneier for niggling problems and fixes to this.) Perhaps NULL PSK-TLS is the right protocol if Internet is used.
Consider a network of nodes connected with links that authenticate messages. Each node runs OBs that can interact within the node via capability discipline. An OB obeys some program within the node. These OBs are dynamically typed as in SmallTalk, Scheme or KeyKOS.
There are a few standard OBs at each node described here that distributed applications rely on. These standard OBs are themselves subject to capability discipline. Their special powers stem entirely from special capabilities they hold.
For each end of each link there is a standard OB that multiplexes that link. There are thus capabilities to channels on these links. A channel is merely a subdivision of the link. These channels only transmit data, not capabilities.
There are travel agents at each node. (They have no monopoly.) These agents are themselves subject to capability discipline. Travel agents have neighbor agents in neighboring nodes with whom they communicate over channel capabilities.
A call to the travel agent establishes a correspondent OB in a neighboring node. The call provides code for the new OB. The agent transmits the code; the neighbor agent creates an OB to obey that code, and endows that OB with a few capabilities to other local standard OBs. Among the standard OBs are the CPU time store, the space store, the travel agent and the introducer (see below). The new OB also gets a capability to the end of a new channel on the connecting link. The caller gets the capability to the other end of the channel. The new OB thus becomes a peer or emissary of the caller. For a market solution DSR can control allocation.
It should now be clear how an object in a node can create its own logical (overlay) network of similar objects connected by channels just as the nodes are connected by links.
Presume that there are cycles in the network. Can two emissaries of the same program that travel to a node by two paths contact each other so as to communicate securely locally? Not without something like the introducer, I think. Recall that the links are not encrypted. This scheme fails if the emissaries think they are at the same node but are not.
First a simple plan for the introducer must be discredited. Naïvely the introducer might just be an array of OB references. One emissary would store a reference to himself in the array and pass the index to his friend who would fetch it from the array. But a rogue may guess the index and fetch the capability. If the rogue taps wires the guessing is especially easy. Even if the array is sparse and the index is difficult to guess, a wire taper may still acquire the index and fetch the reference.
The state of the introducer is an array of pairs some of which are allocated. An allocated pair has an OB reference and an integer. A method first on the introducer passes an OB reference r whereupon a new pair <r, −1> is allocated in the array and the index of that pair is returned. Another method, second, on the introducer passes an OB reference r and two integers m and h. If the pair at index m is unallocated or does not hold <r, −1> or the pair at h is unallocated then the method call is ignored. If the pair at index h holds <s, −1> for some OB reference s then the pair at m is changed to <r, h>. If the pair at index h holds <s, m> for some OB reference s, then both pairs are deallocated and s is returned. The introducer finishes one method before beginning another.
The introducer can now put our two emissaries in contact if they each perform the following:
To convince oneself of the correctness of this we argue from the vantage point of the emissary X who gets the OB reference to the other emissary. X receives index m from his partner. X knows that m is actually from his partner. He knows thus that the object reference in slot m is that of his partner. X has sent his own slot index, n and that slot n is now allocated to himself. He must present the same object reference again, something that only he can do. The introducer must be able to compare capabilities for equality.
| action | slot Xn | slot Yn |
| X and Y each do method “first” | <OBx,−1> | <OBy,−1> |
| X does method “second(OBx,Xn,Yn)” | <OBx,Yn> | <OBy,−1> |
| Y does method “second(OBy,Yn,Xn)” | free | free |
If rogue Z were to learn Xn and Yn and perform “second(OBz, Yn, Xn)” before Y can, or alternatively “second(OBz,Xn,Yn)” posing as X then the introducer would ignore the call due to mismatch between OBz and the table entry.
This protocol can be described metaphorically. Each party orders a telephone from the local phone company. Each party learns the other’s number. This phone system requires that both parties request a call by identifying the other party.
There should be an easier way. Darius Bacon found a serious confusion in a previous version of this scheme. A less symmetric protocol might be easier to understand and implement. The two emissaries would decide between them who was to take the lead. Also the introducer might better directly pass the second invocation thru to the other side.
These patterns might be called “worm heaven” for they promote the worm’s modus operandi as the foundation for robust distributed systems.
To support applications with secrets one presumably needs the sort of local secrecy within the nodes normally provided by capability discipline. If those applications provide their own crypto then the links may remain unsecured. This design may not be efficient but here we are exploring the design space.
I have been vague over whether a travel agent has a local monopoly. If not, different travel agents may in effect define different network overlays. This may be good or bad depending on your goals. A link multiplexor and its peer need a monopoly on a link. These are design parameters that must be explored.
One clarification might be that when an OB is booted in a node by an agent, the new OB is given a list of travel agents vouched for by the booting agent. I think this implies one agent per link and thus a one-to-one map between travel agents and link multiplexors. This architecture level may have no need to separate the travel agent and multiplexor. This seems to lead to monopolies by travel agents and a thus a form of single point failure.