[cap-talk] Petnames versus E-order with ocaps

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
> Bill Frantz wrote:
>> It sounds to me like this algorithm gives Bob a way to deny Carol's service
>> to Alice by just throwing the redirected communication on the floor.

Mark Miller replied:
| No because VatA will still continue trying to send this traffic to VatC on
| its own, without relying on VatB's now-redundant attempts to do the same.
| For symbolic traffic, it's well worth a bit of duplicated bandwidth use to
| minimize latency and vulnerability.

I should have waited for this answer before posting; it does address the DoS
vulnerability. Still, I'm interested in whether the solution below would
work, and whether my model of E-order is correct (as far as it goes).

> I think there is a fifth plausible solution to the conflict described on
> the WormholeOp page. It is a variation on solution 2, which I'll quote here
> for context:
> 
> # 2. Wait for drainage. Block all further communications from VatB to VatC
> #    until all communications from VatA to VatC prior to the introduction
> #    have drained out, or until the VatA/VatC timeout period expires,
> #    killing the connection. This could repeatedly impose a huge cost on
> #    VatB for the sake of only a few objects in VatB. While E avoids making
> #    any claims about resistance to denial of service attack, this would be
> #    too egregious a vulnerability to such an attack.
> 
> As Bill Frantz points out, WormholeOp creates a different DoS vulnerability.
> It is possible to avoid both of these vulnerabilities (and maximize
> pipelining subject to the E-order constraint) by only delaying the
> reception by Carol of messages sent on Bob's reference to Carol, rather
> than all messages sent between VatB and VatC.
> 
> I'd better make sure that I have a correct idea of precisely what the
> E-order constraint is, though, since I've got it wrong before. I think
> that E-order can be modelled as follows (ignoring some additional
> complexities of E such as broken promises):
> 
>  - each sent message has a unique MessageID.
> 
>  - a vat has a collection of mutable objects. Each object is associated
>    with a unique ObjectID, and a set of MessageIDs of messages that it
>    has already acted on. A vat also has a collection of received
>    (promise, message) pairs.
> 
>  - a promise, in a given vat, is a mutable data structure that includes
>    the fields
>      referentCell:
>          a pointer to a mutable cell that, when the promise is
>          settled, will contain the ObjectID of the referenced object.
>      lastMessage:
>          the MessageID of the last message that *must* have been acted
>          on by the referenced object before it can receive any messages
>          sent on this promise.
> 
>    (If a promise is shallow-copied, the referentCell will be aliased
>    between the copy and the original.)
> 
>  - when a message M is sent to a promise P,
>     - P and each promise contained in M are shallow-copied, giving
>       (P', M').
>     - P.lastMessage is then updated to be the MessageID of M.
>     - if and when P (or equivalently, P') is settled, (P', M') is
>       forwarded to the vat of the promise's referent.
> 
>  - for each turn in a given vat V, the vat implementation
>     - selects an arbitrary received (P'', M''), where P'' is a
>       settled reference to object O in V, and P''.lastMessage
>       indicates a message that has already been acted on by O.
>     - causes O to act on M''.
> 
>    (The constraint on P''.lastMessage is sufficient by itself to
>    enforce E-order; there are no explicit FIFO queues in the model.)
> 
> Pipelining can be maximized by implementing this model fairly literally.
> Messages are held by the receiving vat until they can be acted on in an
> order that is consistent with E-order. (To avoid resource exhaustion, a
> vat could have a memory quota for held messages received from each other
> vat.) An implementation does not actually need to record *all* of the
> MessageIDs of messages already acted on by a given object, only those
> that might still be in some promise's lastMessage field (which is a
> distributed garbage collection problem with some potential optimizations
> specific to this context).
> 
> The consequence of this approach for the petname system is similar to
> the WormholeOp approach: if Alice sends a settled promise to Bob, it will
> arrive settled, so it can immediately be assigned a petname on arrival.

-- 
David-Sarah Hopwood ⚥