Identity Untangled:

The Grant Matcher Puzzle

by Mark Miller,
with many thanks to Norm Hardy and E. Dean Tribble

Many systems designers have wrestled with the notion of object identity. The issues must be resolved to design foundational equality primitives. Should an object system provide a means to tell whether two object references refer to the same object, without consulting either of the objects involved? Following Lisp, we call any such primitive EQ. Pure capability systems that are otherwise equivalent have come to different answers. The implications of these different answers were not understood until the Grant Matcher Puzzle.


Capability Foundations

Shown here is the fundamental step of capability computation. Alice, Bob, and Carol are three separate objects. In the initial conditions Alice holds an object reference--or capability--to both Bob and Carol, and neither hold a capability to the other two. The subtleties in making this last issue precise are the heart of the Grant Matcher Puzzle. Matching Distributed Grants.explains how to avoid the capability equivalent of a man in the middle attack, otherwise a danger in a distributed cryptographic capability system.

Setting up the Puzzle

In the initial conditions of Grant Matcher Puzzle, the Grant Matcher itself plays the role of Bob, and a charity named KEQD plays the role of Carol. Dana's situation is exactly symmetric with Alice. Alice and Dana are both assumed to trust the Grant Matcher to perform its duties. Money is itself an interesting problem, but should simply be assumed for this puzzle. Here is an implementation of money in Java adequate for this example, secure assuming only that one can prevent further entrants into a package.

Alice and Dana are assumed not to trust each other at all. That is why they are using the Grant Matcher as a mutually trusted third party. No system can enable cooperation in the absence of any trust. The Grant Matcher pattern, however, is supposed to bring about a particular kind of cooperation between Alice and Dana, requiring only that they both trust the Grant Matcher and a common monetary system.

When it Works

The Grant Matcher provides the service of matching grants, to be given to a common destination. Alice wishes to use the Grant Matcher to give $10 to KEQD, but only if $10 also goes to KEQD from Dana. Dana has the symmetric desire involving Alice. The Grant Matcher has no previous knowledge of KEQD, but if both Alice and Dana provide the same amount of money and designate the same destination, the Grant Matcher will take the money from each and give the sum to the destination. Otherwise, the Grant Matcher returns the money to the prospective donors.

The Grant Matcher is assumed to be coded to perform its duties if it is possible for it to do so. The puzzle is: Can the Grant Matcher determine if Alice and Dana are designating the same destination? Having made a determination, can the Grant Matcher reliably transport the money to the destination, in a way mutually acceptable to Alice and Dana? The Grant Matcher must operate so as to ensure that Alice will not lose $10 unless a destination acceptable to her gets $20. Similarly for Dana.

Let us assume there is no EQ primitive--that one can only gain information about a capability by sending messages over it. In that case, the Grant Matcher has to determine equality by sending messages over these capabilities in some equality determining protocol. Having determined--somehow--that both references are equivalent, the Grant Matcher can simply pick one and send the money.
 
 

Alice Gets Greedy

In Actor systems and in Joule, these equality protocols may eventually bottom out in an internal EQ primitive, but this primitive is hooked into the system in such a way as to prevent revealing a transparent forwarder interposed on a messaging path. If the primitive could be used to reveal the forwarder, then full transparency would be lost. In such a system, one could not have a transparent forwarder.

So, in a system in which forwarders can truly be transparent, Alice can send to the Grant Matcher instead a reference to a transparent forwarder to KEQD. This forwarder always transparently sends messages through to KEQD, unless those messages carry $20. In that latter circumstance, the forwarder will deposit the money to Alice's bank account. By assumption, the Grant Matcher cannot distinguish this situation from the earlier one, except at the price of the very $20 that is at stake.

Notice that Alice cannot really be said to have done anything dishonest. The cause that she is designating to the Grant Matcher is simply one that acts just like KEQD, except for where it puts $20 bills. If Dana were to designate this same forwarder object in its request to the Grant Matcher, it would be stating that this object is where it would like to see the money go as well.

Since Alice's object is forwarding messages to KEQD, including the messages that make up the equality protocol, the intermediate object could validly also be seen as part of the plumbing--as a message conduit for delivering messages to KEQD. In this sense, KEQD itself would also be a valid interpretation of what Alice meant by the capability she passed to the Grant Matcher. Were the Grant Matcher to give $20 directly to KEQD instead of her forwarder, Alice would have no grounds for complaint.

However, the Grant Matcher's situation is completely symmetrical, so it might still break the symmetry in Alice's favor, in which case Alice pockets the money. Dana has lost his $10 even though no destination acceptable to Dana got $20. By no stretch of semantics could one interpret Dana's actions so as to say that Alice's bank account was a valid interpretation of the destination Dana meant to designate.


How EQ Makes a Difference

Of all varieties of EQ primitive I am aware of, the simplest is the originally address equality primitive from Lisp, since then appearing in everything from Smalltalk to KeyKOS to Java. Were the Grant Matcher to use this primitive, EQ would say false in the "Alice Gets Greedy" scenario, and both would get their money back instead. This is a perfectly acceptable outcome, though it has some real costs, especially in the distributed case.

Here is an address-equality-based Grant Matcher coded in Java. Ignoring exceptions from outside the puzzle, the following is secure assuming only that one can prevent further entrants into a package.