[cap-talk] Why is EQ so dang fascinating?

[Dean Tribble]

On 10/27/07, Toby Murray <toby.murray at comlab.ox.ac.uk> wrote:
> Alice introduces Bob to Carol. Dave introduces Bob' to Carol. Carol
> would like to be able to determine whether Bob and Bob' are one and  the
> same. (This is the corroboration.) Let's also presume that Bob and Bob'
> are remote objects, hence they must be some form of caps-as-data.
> Further, that Bob and Bob' are arbitrary references.

But because they are remote references, they are not arbitrary
references from the point of view of Carol, they are remote references
that at least internally designate some remote host.  If they
designate the same remote host, then that host can be authoritative
about whether they are the same.  If they are on different hosts then
if your system support forwarding patterns, then Carol must have a
meta-level conversation with Alice and Bob to shorten the references
or determine that they are indeed the "same" for some value of "same".
If the system does not support any forwarding patterns (e.g., it
allows primitive EQ, which breaks most forwarding patterns), then the
mere fact that the references are to different machines means that the
references are different.  I think anything other than the above
alternatives requires additional discussion of the meta-level
properties of references.

> They're not
> guaranteed to partake in any synergy protocol with a coercer or
> authenticator.

This of course depends on the system.  In E, they are typically
guaranteed to partake in various Miranda protocols. Regardless, the
cap on Bob that the remote reference refers to might not participate
in any synergy protocol, but the remote reference structure does (in
order to support 3-party hand-off).

> But because they're caps-as-data, we might as well
> compare the data bits of Bob with the data bits of Bob' and say that
> corroboration has occurred iff the bits match.

That assumes a specific EQ and reference model. That does not
correspond to E's model, for example (since it cannot cope with
different promises that get resolved to EQ objects).

> I personally see the above scenario as quite possible in any
> person-to-person communications system based on capabilities.

Interesting. I would expect such a system to only share capabilities
that routed through a membrane that supported useful meta-operations
for and on behalf of the provider. For example, revoke all
capabilities I provided to Bob, regardless of whether he delegated
them.

> It appears
> that EQ (or something equivalent to it, as above) is required in order
> to not rule out the possibility of corroboration of arbitrary
> references.

The above scenarios only required an asymmetric operation:
corroborate(X,Y) implies X.isSame(Y) (for some meaning of same).  It
does not require: X.isSame(Y) implies corroborate(X,Y).

> The reason is that corroboration must be independent of the behaviour of
> the references one is trying to corroborate (i.e. independent of the
> behaviour of Bob and Bob'). Suppose that Alice who has first introduced
> Bob to Carol is totally untrusted by Carol. The point of corroboration
> is to enable Carol to alter her trust in Bob, based on her trust in Dave
> (the second introducer). Hence, it's quite possible that Bob (the first
> reference) is totally untrustworthy to Carol (since Alice is) and that
> Carol is unwilling to invoke Bob or even have any other object she
> trusts (like a coercer or authenticator) do so on her behalf.

But since you now have a reference to a Bob' you will work with, why
does Alice care whether Bob is the same trusted entity?

> The behaviour of coercers and authenticators not built with magic, but
> by synergy alone, cannot be independent of the behaviour of the
> references they are trying to authenticate/coerce (because a
> coercer/authenticator must invoke the reference in order to coerce or
> authenticate it, unless it can appeal to magic).

This is a general version of the observation that Shap made in the
context of resume keys. While it has been mostly true of systems so
far, it's not actually a requirement. In E, for example, Ref has many
meta-operations on references that don't need to invoke them. Joule
had provisions for meta-level operations that would "follow" a
reference without invoking it in order to achieve precisely these
kinds of properties without breaking transparent forwardability.  In
particular, the pattern above of transitively figuring out where a
reference comes from a is a meta-level operations that allows
determining who is authoritative about a reference.

> The behaviour (not the
> result, of course) of EQ is independent of the behaviour of the
> references one is trying to compare.

This is too dependent on the notion of "reference" that it's unclear.
In E, multiple promises can be resolved to the same thing, which might
have identity sameness or value sameness.  What do you mean here?

> By Behaviour, I mean things like the time the operation may take to
> complete, or the degree to which the user of the operation makes itself
> vulnerable to the reference it is trying to corroborate.

Two isSame things may have very different characteristics on those dimensions.

> Hence, I'm arguing that EQ seems to be the right fit for corroboration
> because it has this independence property, while anything based on
> synergy alone does not.

This conclusion seems premature: 1) EQ does not have the independence
property above depending on the nature of references 2) references and
EQ are not really defined. are 1.0 and 1.0 EQ? 1 and 1.0? "ab" and "a"
+ "b"? f(a){a} and f(b){b}?  Etc.  The differences in a real system as
a result of even minor differences at this level can be huge.

BTW I'm not arguing the an EQ approach isn't useful sometimes. But,
specific choices about EQ semantics can have huge costs, most uses of
EQ are actually unnecessary, and nonetheless for some scenarios, the
EQ approach might be net simpler.  For PetName introductions, I'm
dubious that it's valuable for "any capability" ("here, John, this is
the partially consumed parser for the third Mime part in message ID
3") as opposed to capabilities for concepts that are meaningful to
users ("here's the authority to store data into directory X"). These
would typically correspond to things that can have a UI projection of
some flavor, and so would have plenty of meta-level support around
them (e.g., I'd want to provide objects that log all the remote
operations, and perhaps supports undoing them).  I'd be interested in
an example that contradicts that model.