[E-Lang] Promises, equality and trust

Mark Seaborn mrs35@cam.ac.uk
Sat, 28 Jul 2001 23:19:06 +0100


"Mark S. Miller" <markm@caplet.com> writes:

> At 02:54 PM Thursday 7/26/01, Mark Seaborn wrote:

> >(Incidentally, what is the origin of the term `Miranda method'?
> >Presumably it doesn't come from the language Miranda.)
> 
> In the U.S., one's Miranda rights include "If you cannot afford a 
> lawyer, one will be provided for you".  They're named after this case:
> http://www.thecapras.org/mcapra/miranda/rights.html .

Ah!  I wasn't expecting the origin to be an area like that!  (I should
have guessed, after the Granovetter operator.  Incidentally, I did a
search in Researchindex.org for Miranda methods and found nothing.  I
did a search for `rights amplification' there too and didn't get much.
The literature has some progress to make. :-) )


> >Does a holder of a promise always get told about the promise's
> >resolution, or does this information only come through the call to an
> >observer passed to a whenResolved message, with the local proxy for
> >the promise wrapping the observer passed in whenResolved so that it
> >detects the resolution too?  (Giving whenResolved special treatment in
> >this way does not seem very elegant.)
> 
> The latter.  The holder of a promise never gets told simply by virtue of 
> holding. Rather, the holder of a promise can arrange to find out by means of 
> the various "when..." constructs you already know about.  The holder of a 
> promise can also check (ie, poll) by use of "Ref isResolved(expr)".

A minor thing:  I presume you mean the holder never gets told by virtue
of holding in terms of the inter-vat protocol (so polling would not
work unless a `when...' message had also been sent).  (Also, does the
`Ref' object replace the `E' object?)

That means that if Alice receives a promise P from Bob by Bob sending
it in a message to Alice (rather than it being the result of Alice
sending to Bob), Alice has to wait for a round trip to P to complete
(at least) to find out what P is resolved to (assuming that Bob didn't
know what P was resolved to at the time of sending this message,
even though P may resolve soon after).  This may not be a big problem,
but it would be nice to improve on it.

Suppose the protocol is changed:  Rather than just sending P, Bob also
sends an arrowtail connected to P and an arrowhead that Alice will
connect to be an observer for B.  Bob keeps the arrowtail to Alice's
observer for P.  Soon after sending this message, Bob finds out that P
resolved to X.  Bob notifies Alice of this by sending a message to
Alice's observer for P.

This improves latency, but unfortunately, as well as trusting P to
resolve consistently (that is, to give consistent answers when queried
directly about what it resolved to), we are trusting Bob not to lie
about how P resolved.  (It might also result in many redundant
resolution messages being sent; for example, if many different vats
send Alice the same promise.)

A possible solution to this:  Alice can require that messages sent to
Alice's observer for P be signed by P's vat's private key.  Then Bob
cannot lie about how P resolved; Bob can only forward resolution
statements from P (and expect to be believed).  I don't think this can
be implemented in terms of capabilities -- at least I don't think it
can be described with a Granovetter diagram without adding a round
trip.  (I saw a reference on the Web site to `CryptoBrandMakers' --
does E implement crypto sealer/unsealer pairs yet?)

We still end up having to trust P not to generate more than one
resolution statement.  I had the idea that we could motivate against P
doing this by forwarding any pair of inconsistent resolution
statements we encounter (signed by P's vat) to other vats and urging
them to sever connections with P's vat (very political!).  But I don't
think this would be effective since if P's vat's owner wanted to do
this maliciously he could simply arrange for P to be in its own vat,
to be sacrificed.

However, we don't need to trust the value to which P resolves to give
consistent answers from its `whenResolved' method (unless P resolves
to a promise).


> >If the invocation of observers passed in whenResolved messages is the
> >way promises get resolved to values, wouldn't that mean promises can
> >get resolved to different values in different vats?  A promise that
> >started out being equal to itself would end up splitting into
> >inconsistent values.
> 
> Yes, but I believe this issue can't be fixed.  The rationale for the
> current design rests on that unproven belief, so there's definitely
> something to talk about.  More later.

Yes, I agree with you.  The reason seems to be that we can't stop a
promise signing more than one statement of resolution, because the
promise's private key is just a number which cannot get consumed by
signing a statement of resolution.  The promise can send out
conflicting resolution statements in different directions across the
network, to vats that may not even be aware of each other yet, so they
can't check consistency.

I can't think of any specific cases in which this would be a problem,
but in the general case it does mean that Alice can't send an
unresolved promise P to Bob and then expect the answer received to
have anything to do with the X Alice later finds P has resolved to,
since Bob may think P resolved to Y.  Maybe the answer Bob sends to
Alice should be marked as based on the assumption that P resolved to Y
(a hash of Y could be presented to avoid revealing Y itself).


> >Another concern I have:  If Alice passes to Carol her reference to Bob,
> >Carol's vat will have to establish a connection to Bob's vat in order
> >to send messages to Bob (assuming all three live in different vats).
> >Assuming Bob and Bob's vat are in collusion, Bob will be able to
> >distinguish between messages from Alice and messages from Carol.
[snip]
> 
> Fascinating.  What you're proposing is what E-Speak2.2 planned to do: have 
> the default case be not to shorten paths (the case actually implemented), 
> and then have a path shortening Granovetter introduction be something a 
> program can explicitly request (AFAIK, their plan for this was sound, but it 
> never got implemented).  I remember arguing with Alan over this years ago 
> (remember Alan?), but yours is the first rationale for the E-Speak position 
> I understand.
> 
> I still think default shortening is the right engineering decision, because 
> the price of not shortening is too high, and the above price of shortening 
> will IMO usually not be a practical issue.

Isn't there an initial cost of shortening, though?  The vats being
introduced must wait for a few round trips to complete to set up a
connection.  Might it be worth sending messages through a proxy until
a connection is set up?

Shortening as a default is fine, though there will always be people
out there who are hostile to delegation, and it might be worthwhile
making this risk stark by providing capabilities for finding out where
a request comes from (not given out by default, of course).

-- 
         Mark Seaborn
   - mseaborn@bigfoot.com - http://www.srcf.ucam.org/~mrs35/ -

           So foul and fair a tagline I have not seen.