Crossed hellos

[Christopher Lemmer Webber]

heHELLOllo,

Today I'm thinking about the "crossed hellos" problem, I guess also
called the "crossed wires" problem in the original VatTP literature, but
MarkM and Dean Tribble on a recent call suggested a preference for
"crossed hellos" and that makes sense to me in a way that "crossed
wires" did not quite as clearly.

Let's see if I can lay out the problem appropriately:

A combination CapTP/VatTP type system prefers to reuse bidirectional
connections between two vats/machines for two reasons: (1) to reduce
superfluous connections and (2) to provide shortening (which is extra
important for eq?-like identity checks).

However, if Machine A and Machine B would both like to start
connections to each other, and begin reaching out at the same time, we
have a race condition: should we choose the session that Machine A
initiates, or the session that Machine B initiates?

In a sense then, we really are looking at a case of the Two Generals
Problem, which shows we're already in a tough spot. Yikes!

My understanding of what VatTP did is something like the following: both
sides share the potential sessions to choose amongst they currently
*believe* they have open from their side. Both sides select a viable
subset between what both sides have shared... and then some arbitrary
choice is made, probably by some comparison with lowest ordered by
byte-comparison. This was based on identity of the vats in original
VatTP I think, and I was thinking maybe comparison of session ids in the
same way. There may be an advantage by comparing by session ids as they
currently exist in OCapN vs the vat-identity in Pluribus, which is that
an extra step where the lower-identity-vat "explicitly chose" made sense
since we were selecting based on identity of some operator... so the
operator must "say and select". But if we can compare based on identity
of session, both sides should be able to deterministically select the
same choice anyway from the subset.

Something feels unsettling about this solution but I can't fully model
in my mind whether there's a further problem or not. But maybe it's
good enough.

Thoughts? Is this a good summary of the problem? Did I capture the
solution as VatTP did it right as well?

- Chris

[Bill Frantz]

Let me see if I can still comment on the original VatTP design.
The design document is available at:
<http://www.erights.org/elib/distrib/vattp/DataComm_startup.html>.
Note that in this document, "Crossed Hellos" are called "Crossed Connections".

The most important reason for only allowing 1 connection between
vats is ensuring that messages between two objects, one on each
vat, arrive in the order they were sent.

Note that the E comm system did not allow vat C to relay
messages between vats A and B. This avoids the traffic analysis
attack that C could perform.

On 2/10/21 at 10:54 AM, cwe...@dustycloud.org (Christopher

Lemmer Webber) wrote:

>heHELLOllo,
>
>Today I'm thinking about the "crossed hellos" problem, I guess also
>called the "crossed wires" problem in the original VatTP literature, but
>MarkM and Dean Tribble on a recent call suggested a preference for
>"crossed hellos" and that makes sense to me in a way that "crossed
>wires" did not quite as clearly.
>
>Let's see if I can lay out the problem appropriately:
>
>A combination CapTP/VatTP type system prefers to reuse bidirectional
>connections between two vats/machines for two reasons: (1) to reduce
>superfluous connections and (2) to provide shortening (which is extra
>important for eq?-like identity checks).
>
>However, if Machine A and Machine B would both like to start
>connections to each other, and begin reaching out at the same time, we
>have a race condition: should we choose the session that Machine A
>initiates, or the session that Machine B initiates?

This is the Crossed Connection/Crossed Hellos situation.

>In a sense then, we really are looking at a case of the Two Generals
>Problem, which shows we're already in a tough spot. Yikes!

I don't think the two generals problem applies here. The
protocol discovers that the situation is about to occur and
takes steps to avoid it.

>My understanding of what VatTP did is something like the following: both
>sides share the potential sessions to choose amongst they currently
>*believe* they have open from their side. Both sides select a viable
>subset between what both sides have shared... and then some arbitrary
>choice is made, probably by some comparison with lowest ordered by
>byte-comparison. This was based on identity of the vats in original
>VatTP I think, and I was thinking maybe comparison of session ids in the
>same way. There may be an advantage by comparing by session ids as they
>currently exist in OCapN vs the vat-identity in Pluribus, which is that
>an extra step where the lower-identity-vat "explicitly chose" made sense
>since we were selecting based on identity of some operator... so the
>operator must "say and select". But if we can compare based on identity
>of session, both sides should be able to deterministically select the
>same choice anyway from the subset.

I don't really understand what this paragraph is saying.

Both sides of the negotiation use their respective VatIDs to
decide which vat will make the decision. Since the VatIDs, being
the hashes of the respective public keys, can be interpreted as
bit strings, a simple comparison decides which is greater, both
sides will get the same answer, and the larger VatID gets to
make the decision.

>Something feels unsettling about this solution but I can't fully model
>in my mind whether there's a further problem or not. But maybe it's
>good enough.
>
>Thoughts? Is this a good summary of the problem? Did I capture the
>solution as VatTP did it right as well?
>
>- Chris
>

-------------------------------------------------------------------------
Bill Frantz | When it comes to the world | Periwinkle
(408)348-7900 | around us, is there any choice | 150
Rivermead Rd #235
www.pwpconsult.com | but to explore? - Lisa Randall |
Peterborough, NH 03458

[Christopher Lemmer Webber]

Hey Bill! Thanks for the help. :)

Bill Frantz writes:

> Let me see if I can still comment on the original VatTP design. The
> design document is available at:
> <http://www.erights.org/elib/distrib/vattp/DataComm_startup.html>.
> Note that in this document, "Crossed Hellos" are called "Crossed Connections".
>
> The most important reason for only allowing 1 connection between vats
> is ensuring that messages between two objects, one on each vat, arrive
> in the order they were sent.

That's true, and somehow one I missed (I did list eq?/shortening
concerns, which is what I've mostly been concerned about, and also the
"cost savings" of reusing connections)

> Note that the E comm system did not allow vat C to relay messages
> between vats A and B. This avoids the traffic analysis attack that C
> could perform.
>
> On 2/10/21 at 10:54 AM, cwe...@dustycloud.org (Christopher Lemmer
> Webber) wrote:
>
>>heHELLOllo,
>>
>>Today I'm thinking about the "crossed hellos" problem, I guess also
>>called the "crossed wires" problem in the original VatTP literature, but
>>MarkM and Dean Tribble on a recent call suggested a preference for
>>"crossed hellos" and that makes sense to me in a way that "crossed
>>wires" did not quite as clearly.
>>
>>Let's see if I can lay out the problem appropriately:
>>
>>A combination CapTP/VatTP type system prefers to reuse bidirectional
>>connections between two vats/machines for two reasons: (1) to reduce
>>superfluous connections and (2) to provide shortening (which is extra
>>important for eq?-like identity checks).
>>
>>However, if Machine A and Machine B would both like to start
>>connections to each other, and begin reaching out at the same time, we
>>have a race condition: should we choose the session that Machine A
>>initiates, or the session that Machine B initiates?
>
> This is the Crossed Connection/Crossed Hellos situation.

Ok, good.

>>In a sense then, we really are looking at a case of the Two Generals
>>Problem, which shows we're already in a tough spot. Yikes!
>
> I don't think the two generals problem applies here. The protocol
> discovers that the situation is about to occur and takes steps to
> avoid it.

I've hoped that's true. I'll assume it is for now then. :)

>>My understanding of what VatTP did is something like the following: both
>>sides share the potential sessions to choose amongst they currently
>>*believe* they have open from their side. Both sides select a viable
>>subset between what both sides have shared... and then some arbitrary
>>choice is made, probably by some comparison with lowest ordered by
>>byte-comparison. This was based on identity of the vats in original
>>VatTP I think, and I was thinking maybe comparison of session ids in the
>>same way. There may be an advantage by comparing by session ids as they
>>currently exist in OCapN vs the vat-identity in Pluribus, which is that
>>an extra step where the lower-identity-vat "explicitly chose" made sense
>>since we were selecting based on identity of some operator... so the
>>operator must "say and select". But if we can compare based on identity
>>of session, both sides should be able to deterministically select the
>>same choice anyway from the subset.
>
> I don't really understand what this paragraph is saying.
>
> Both sides of the negotiation use their respective VatIDs to decide
> which vat will make the decision. Since the VatIDs, being the hashes
> of the respective public keys, can be interpreted as bit strings, a
> simple comparison decides which is greater, both sides will get the
> same answer, and the larger VatID gets to make the decision.

Okay, close enough to what I was trying to confirm from the original
VatTP, thanks.

I'll save explaining my modified version of that until I have it
implemented, or until I decide to implement the original approach. ;)
(It's mostly the same, with one tweak.)

[David Nicol]

it seems to me that the requirement for message ordering hides a design failure.

it seems to me that a message that has to be received in ordered parts is not a complete message.

it seems to me that a better system would involve complete (if more complicated) messages only, which could be handled in their entirety at message grain.

By restricting protocols to "complete" messages, the details of the transport layer can then be left out of security analysis.

If a conversation between two actors requires ordering due to actor state changes, the actor-actor message protocol should include that, rather than relying on the host environment maintaining message sequence.

Thank you

David "Tipjar" Nicol

On Wed, Feb 10, 2021 at 2:34 PM Bill Frantz <fra...@pwpconsult.com> wrote:

 

The most important reason for only allowing 1 connection between
vats is ensuring that messages between two objects, one on each
vat, arrive in the order they were sent.

--

"Put it on your toast." -- Flava Flav

[Alan Karp]

David Nicol <david...@gmail.com> wrote:

If a conversation between two actors requires ordering due to actor state changes, the actor-actor message protocol should include that, rather than relying on the host environment maintaining message sequence.

And therein lies madness, or should I say TCP.  The problem with the end-to-end principle, which is what you are proposing, is that only the network has the context to fix problems in the network, and only the application has the context to fix problems in the application.  In-order delivery is something that should be handled in the network; the application, which includes its messaging libraries, should handle things like E-order.

There are numerous examples. A switch will drop packets when it's buffer gets full without any knowledge of which packets the application considers important.  The result is often dropping a short acknowledgement, forcing the resend of a large data message leading to cascade failures.  Another is a network that reorders a sequence of messages from one sender to one receiver.  TCP does an admirable job of hiding that behavior from applications at the cost of considerable complexity and resource use, and it still fails to provide the guarantee when a TCP session is lost.  The result is that applications need thousands of lines of code to deal with corner cases that could be more easily handled in the network.

Sorry for the rant.  The startup I'm working for has a design for a better datacenter network, so these issues are top of mind for me.  You can read about our design at https://ieeexplore.ieee.org/document/9250323.

--------------
Alan Karp