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.
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.
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.
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.
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.
|Currency.java||Each currency results from a separate Mint creation event. Money is only primitively transferable within a currency.|
|Purse.java||Money is not represented directly, but rather as counters held in Purses. Purses of the same currency will transfer money between them, while enforcing properties such as local conservation.|
|Mint.java||The power to print more money in a given currency. This is where money comes from. All other operations can only transfer it around.|
|DifferentCurrencyException.java||If an attempt is made to directly transfer between different currencies. Note that the system allows intermediary money changers that trade in multiple currencies.|
|NegativeBalanceException.java||If an action would cause a balance to go negative.|
|Charity.java||Interface to those, like KEQD, that can accept a donation.|
|GrantStatus.java||Interface for callbacks to be provided by Alice and Dana in their GrantMatcher requests so they can find out the status of their request, and receive a refund if needed.|
|GrantMatcher.java||If everything goes well, The Grant Matcher accepts two messages, escrows the money from each, sees that they agree, gives the sum to the common charity, and lets both sides know the transaction completed. Otherwise, it refunds any money escrowed, and lets both sides know the transaction failed. This class is abstract, leaving subclasses to decide how to determine equality.|
|MalletCharity.java||An Charity-in-the-middle that forwards all equality messages to the Charity it is trying to impersonate, while pocketing all donations.|