Goblin semantics, and thinking through / planning for CapTP

414 views
Skip to first unread message

Christopher Lemmer Webber

unread,
May 18, 2020, 5:25:05 PM5/18/20
to cap-...@googlegroups.com
Hello,

I'm implementing CapTP for the first time ever in my life, though I've
been reading about it for a long time. Mark has told me that a nice
phrase they use at Agoric is "don't squander your ignorance". To that
end, I wonder if it might be a good idea for me to work through some of
my thinking live on a thread here. If people find this too noisy,
please tell me and I'll move it off-list.

(In case it's useful and to prevent doubts of copywrongs, I waive all
copyright into the public domain under CC0 1.0. Feel free to use this
if it results in anything resembling useful documentation... though it
probably won't.)

EDIT BEFORE SENDING: this message has gotten huge and I apologize
in advance unless you think it's great in which case you're welcome.


What is CapTP?
==============

(Feel free to skip this, and maybe the next section, if you're familiar
with CapTP already yourself. Or skip everything, I'm not the boss of
you!)

I recently described CapTP and VatTP to a colleague. Here is my attempt
to mirror those definitions, in short.

- VatTP: How you get secure connections between vats (or maybe
machines; that's up to debate). But it's really more about setting
up a way to get messages securely *between* these vats/machines,
rather than what is done with those messages.

- CapTP: This is the "what happens when you get a message" protocol and
is really what allows objects to talk to each other in a fully
distributed environment. It takes care of a bunch of things,
including linking objects across the vats, informing of promise
resolution, cooperative distributed (acyclic) garbage collection, etc
etc.

There have been a bunch of "CapTP"-like things over time. They aren't
all necessarily compatible. In the meanwhile, this makes CapTP more
like an abstract pattern, like "Lisp", rather than a specific standard,
like "R5RS Scheme". Like lisps, you'll likely find many common ideas
between dialects. It may be desirable to find The Great Unification at
one point but that hasn't happened yet. Maybe soon!


How do I learn more?
====================

Here are the main resources I am using to learn about CapTP:

- The Erights CapTP pages:
http://erights.org/elib/distrib/captp/index.html
- MarkM's thesis:
http://www.erights.org/talks/thesis/
- Cap'n Proto's docs:
https://capnproto.org/rpc.html
- More importantly, rpc.capnp, which is a beautiful document:
https://github.com/capnproto/capnproto/blob/master/c++/src/capnp/rpc.capnp
- This extremely wide aspect ratio video by MarkM:
https://www.youtube.com/watch?v=YXUqfgdDbr8
- Agoric's captp.js:
https://github.com/Agoric/agoric-sdk/blob/master/packages/captp/lib/captp.js
- The following Agoric SwingSet docs:
https://github.com/Agoric/agoric-sdk/blob/master/packages/SwingSet/docs/delivery.md
https://github.com/Agoric/agoric-sdk/blob/master/packages/SwingSet/docs/networking.md
(ok that latter one is really for VatTP)

If you are somehow completely new to ocaps (ok, nobody on this list is,
you can tell I'm over-engineering this email for the future), I
personally recommend "A Security Kernel Based on the Lambda Calculus":

http://mumble.net/~jar/pubs/secureos/secureos.html

The core idea is that (object) capabilities are just object references.
There's no need to layer a complex (and more insecure) security
architecture on top of our programming languages because the way
programmers already program, if we take it seriously, already *is* our
programming model: passing references around to functions (or objects)
is basically the full idea. If you don't have it in scope, you can't
use it. More advanced patterns flow from this core idea; we're not
covering them here but the "Ode to the Grannovetter Diagram" writeup
explains many of them in brief:

http://erights.org/elib/capability/ode/index.html


Core structures
===============

I'm going to borrow some slides from a talk I gave on Goblins recently:

https://gitlab.com/dustyweb/talks/-/blob/master/spritely/friam-2020/goblins-talk.org

Jump to "Goblins Architecture", though really *most* of this is common
across other ocap'y systems like E, Agoric's stuff, Cap'n Proto, blah
blah blah.

Here are the abstractions, as used in Goblins, layered. Moving from
inner most part outward:

(machine (vat (actormap {refr: (mactor object)})))

- object: Some sort of encapsulated thing that can be talked to via
call-and-return invocation and asynchronous passing of messages.
Manages its own state, though another way to say that is "decides
after handling one message/invocation how it will respond to the next
message/invocation". In fact, in Goblins this is usually just a
procedure representing the current message handler. Often times
these things may support multiple methods.

In Goblins, objects resemble "classic actors", although that term may
be subject to bikeshedding.

- mactor (Goblins-only?): Stands for "meta-actor"; there are actually
a few core kinds of these and they wrap the object (eg this is where
promises vs non-promises are distinguished in Goblins).

- refr: Also known as "ref" elsewhere in the ocap community; this is
the reference that is used to communicate with the object. If you
have it, you can communicate, if not, you can't.

- actormap: Mapping of refrs to the objects they represent. In
Goblins, if an object specifies it would like to "become" a new
message handler, this is updated (in a transactional way).
Can be used on its own, but only for non-distributed programs.

- vat: An event loop. Wraps the actormap datastructure, handles
passing messages to it. Handles messages one "turn" at a time,
however objects may send asynchronous messages to objects in any vat
that can be established a connection to and even do immediate calls
to other objects that are in the same vat ("near" each other).

- Machine: Some sort of abstract machine or OS process that may have
one or multiple vats in it. (Agoric does fancy things so that they
can even treat blockchains and other such things as abstract
"machines"... we're not doing anything so fancy in Goblins yet.)


Zooming in on the Vat
=====================

Looking just on the vat-and-deeper levels, this looks something like the
following, borrowed and adjusted a bit from MarkM's dissertation:

.-----------------------.
|Internal Vat Schematics|
'======================='

stack heap
($) (actormap)
.-------.----------------------. -.
| | | |
| | .-. | |
| | (obj) .-. | |
| | '-' (obj) | |
| __ | '-' | |
| |__>* | .-. | |- actormap
| __ | (obj) | | territory
| |__>* | '-' | |
| __ | | |
| |__>* | | |
:-------'----------------------: -'
queue | __ __ __ | -.
(<-) | |__>* |__>* |__>* | |- event loop
'------------------------------' -' territory

In the upper-right box is abstractly the actormap datstructure
representing references pointing to objects. If we just do synchronous
programming, we can add in the left-hand column which resembles a call
stack for call-and-return behavior. However these calls can only be
done between objects in this same actormap/vat. Adding in the bottom
row we see messages queued to be handled. Each message is handled,
one "turn" at a time, from this queue, kicking off a call stack (again,
the left hand column) starting with the message invoking some object in
the actormap/heap with some arguments. In general, when a "turn" is
complete, if there is a promise waiting to be fulfilled attached to this
message, it uses the return value from this first call.


Crossing vat and machine boundaries (hello CapTP)
=================================================

Of course, vats aren't just limited to speaking to just themselves.
We want to speak to other vats, including on other machines!

Visually, this looks something like the following (sorry, might render
better in the link to my talk above):

.----------------------------------. .----------------------.
| Machine 1 | | Machine 2 |
| ========= | | ========= |
| | | |
| .--------------. .---------. .-. .-. |
| | Vat A | | Vat B | | \______| \_ .------------. |
| | .---. | | .-. | .-| / | / | | Vat C | |
| | (Alice)----------->(Bob)----' '-' '-' | | .---. | |
| | '---' | | '-' | | | '--->(Carol) | |
| | \ | '----^----' | | | '---' | |
| | V | | | | | | |
| | .----. | | .-. .-. | .------. | |
| | (Alfred) | '-------/ |______/ |____---( Carlos ) | |
| | '----' | \ | \ | | '------' | |
| | | '-' '-' '------------' |
| '--------------' | | |
| | | |
'----------------------------------' '----------------------'

Here we see, with nested bulleted points representing "what contains
what":

- Machine 1, with a connection to Machine 2
- Vat A
- The object Alice (holding references to: Alfred, Bob)
- The object Alfred
- Vat B
- The object Bob (holding a reference to: Carol)
- Machine 2, with a connection to Machine 1
- Vat C
- The object Carol
- The object Carlos (holding a reference to: Bob)

At the boundaries of the vats are triangle-looking things. These, in
theory, represent tables of "live references".

- The top connection between the triangle-looking things represents
references Machine 1 has to objects in Machine 2.
- The top left triangle-looking thing is Machine 1's imports
(from Machine 2)
- The top right triangle-looking thing is Machine 2's expors
(to Machine 1)
- The bottom connection represents the reverse, Machine 2's references
to objects in Machine 1
- Bottom left being Machine 1 exporting to Machine 2
- Bottom right being Machine 2 importing from Machine 1

These tables are numerical indices. For example, Machine1+VatB's
reference to Carol in Machine2+VatC may look like the following:

- Machine1Imports: {<remote-carol-ref>: 3}
- Machine2Exports: {3: <carol-ref>}

(Side note, when I hear "import" and "export" and then look at the
arrows, I get confused, because I think of "import", arrow-wise, "being
shipped to" the side that is importing, such as packages "ship to" an
importer in a trading situation and "ship from" an exporter. The arrows
are being tricky though, because the we're importing a reference "to" an
object that never leaves its location.)

But this either isn't a complete picture, or doesn't represent other
CapTP implementations (remember, Goblins hasn't fully implemented it
yet), so caveats from "really existing" CapTP systems:

- Traditionally, imports/exports have been on the vat level, rather
than on the machine level

- Also usually there are two other tables in addition to
imports/exports: questions/answers. These corresponds to "future
resolutions to promises" (as well as some "promise pipelining" stuff
but we'll talk about that later). A way to think of this is: if Bob
sends a message to Carol using the <- operator in Goblins, Bob should
get back a response that will eventually be resolved with Carol's
response... but when we cross the network divide and Machine2+VatC
gets that message saying "hey, call Carol... and when you're done,
fulfill this thing", we need some way to refer to that.

*SCREECH!* Let's slam the brakes on that last statement for a second.
Because there could be another solution (ignoring promise pipelining for
a second) that gets rid of questions/answers: Machine1+VatB could set up
an export for Machine2+VatC that refers to the promise-resolver that
will fulfill Bob's promise. We could just say in the message to Carol:
"and once you have an answer, fulfill the promise with
<this-resolver-i-just-exported-for-you>"!

Well that seems to solve that just fine and dandy so why bloat our
protocol with these extra two question/answer tables? Shouldn't
import/export be fine?


The desiderata of promise pipelining
====================================

Well, we said we'd get back to "promise pipelining" at some point, so
here we go.

We could send a message to the remote car factory and say "make me a
car!" and hold onto that promise. We could wait for it to resolve to
get a reference to that car, but *only then* would we be able to tell it
to drive.

So this is:

.-- Ask car factory for car
|
| .--- Made the car, sending back the reference
| |
| | .--- Got the reference, tell the car I want to turn it on!
| | |
| | | .--- Turned on the car, telling you it makes a
| | | | "vroom vroom" noise
| | | |
| | | | .--- Finally I have heard my car go "vroom vroom"
| | | | |
V V V V V

B => A => B => A => B

That's a lot of round trips when we knew that we wanted to drive the car
immediately. What if we could instead say, "make me a car, and then
I want to turn it on immediately!" That would instead look like:


.--- Ask car factory for car, and once you have that car, turn it on
|
| .--- Okay I made the car.
| | Okay, now I will turn on that car, telling you it makes a
| | "vroom vroom" noise"
| |
| | .--- Now I get to hear my car go "vroom vroom" already!
| | |
V V V

B => A => B

This is nice for a few reasons: we can start talking about what we'd
like to do immediately instead of waiting for it to be a possibility.
But most importantly, it reduces the round trips of our system, which
are often the most expensive part in a networked environment:

"Machines grow faster and memories grow larger.
But the speed of light is constant and New York is not getting any
closer to Tokyo."
-- MarkM in Robust Composition: Towards a Unified Approach
to Access Control and Concurrency Control


So does that mean we need questions/answers too?
================================================

So now that brings us back to: do we need questions/answers in addition
to these imports/exports? And... actually I'm not so sure.

It strikes me that, when exporting, Machine1+VatB could say "I'm
allocating this object reference for you, and it's a resolver type".
Then when importing, Machine2+VatC could make note of that, and
when it resolves it, immediately make note in its imports table.
Thus when Carol has that answer ready for Bob, Vat C can make note
of that and still use the reference to Carol.

I still don't see the need for separate questions/answers tables.
Maybe I'm missing something. Maybe it's obvious in practice.


Cooperative acyclic garbage collection
======================================

Maybe Bob doesn't need the reference to Carol anymore, or maybe Bob
doesn't even exist anymore. If nobody in Vat B is holding onto a
reference to Carol anymore, then Vat B should let Vat C know so that Vat
C can sever that entry in their database to Carol. That should allow
Vat C to garbage collect Carol if nobody else is holding onto a
reference either.

If Bob and Carol both hold references to each other, neither might ever
GC. Let's hope that doesn't happen!


3-party introductions
=====================

Once you've implemented all that, what happens if Alice wants to spend a
message about Carol to Dave, but Dave is on Machine 3 in Vat D (not
pictured above). Well what the heck do we do now?

There's a whole thing about handoff tables. I feel like this is a
complicated subject, and one I want to write an entirely separate email
about because it still hurts my brain a little. The MarkM talk I linked
to above explains it reasonably though. So ok, we'll just say we can do
that. (There also has been something called "vines" used historically
though I've never been completely clear on what a "vine" is... maybe it
doesn't matter anymore.)


SturdyRefs, or handoff-only, or certificates?
=============================================

So far we've talked about capabilities using double-ended,
network-spanning c-lists (the import/export tables, numerically
ordered). Great... but how do you bootstrap a connection at all? Let's
say Bob in Vat B wants to talk to Carol in Vat C, but they don't have a
connection "yet". Well if Bob was *introduced* to Carol through someone
else (using those handoff tables or whatever) that seems fine. But this
is a weird bootstrapping problem. When Machine1+VatB+Bob has never
connected to *anyone* on *any other* machine, how on earth does Bob get
an entry point into the system at all?

This is one, but only one, justification for SturdyRefs. SturdyRefs are
long-lived network addresses, which we can think of like:

<object-id>@<vat-id>[.<machine-id>]

We could think that vat-id could be a public/(verification+encryption)
key fingerprint, and that immediately gives us a path to thinking about
how to send messages securely to <vat-id>. (<machine-id> is thus more
of a "hint" of how to get there... "oh yeah, I'm on this IP address or
whatevs".) <object-id> is what's called a swissNum, a sufficiently
unguessable random number / blob of randomly generated junk that we
shouldn't be able to brute force.

This is something we could put in a web hyperlink (indeed, "capability
URLs" are technically such a thing) or print on a business card as a QR
code, etc etc. Now we don't have to be born in the network to get
access to it. Once we set up a connection, we can, from there, start
setting up live references using our imports/exports tables between
vats/machines.

Sturdyrefs have some challenges:
- When do you make them expire / need to be renewed?

- They're easy to leak, and it can make re-establishing relationships
difficult if intrusion occurs. Not only do you give away all your
outgoing authority, this resembles a "we were broken into so now all
our users have to reset their passwords" type problem... but arguably
it's much worse because ocap systems may be constructed such that
users don't really know where all the sturdyrefs they rely on exist
in their machine.

- They don't work with systems like blockchains where "which can't hold
secrets" (though necessarily require on secrets being externalized).

So I guess we have a couple of other options:

- Apparently Agoric's stuff is rolling out without them but I'm not
really sure how. I know "bootstrap objects" exist but I think of
those as "system-level objects" and really only there (if they need
to be at all) as a special plumbing object, and aren't sufficient if
everyone has access to them. My best guess is that what you would do
is have Carol in Vat C *anticipate* Bob in Vat B's arrival... "When
Vat B gets here, let's pre-allocate a reference to Carol for them".
Is that how it works?

- Or we could use ocap certificate chains, eg like zcap-ld or CapCert
or the Zebra Copy stuff, etc etc. This adds some structural overhead
but pleasantly removes a large portion of the leaking risks;
recovering from an intrusion may leak some private data, but you
don't need to ask users something resembling "we were broken into so
plese reset your passwords" (but potentially much worse, because
you're now asking your users to debug their running object capability
systems).

Both of those are nice, but neither of them covers the "here's a
blog/social networking post where I mention something interesting" use
case. Particularly, consider if a post is encoded in some document
structure that is stored in something like tahoe-lafs (or datashards or
etc)... how do you encode it as a link in this offline-stored data?

So I'd like to get around the need for sturdyrefs, but I see use cases
for them where they're still desireable. And they're just such a dang
easy way to bootstrap connectivity in a system.


Store imports/exports tables in vats or machines?
=================================================

If multiple vats are on the same machine, who is responsible for the
imports/exports tables? Does each vat provide them? Or should it be on
the machine level?

I think there are a lot of tradeoffs here... admittedly this is one of
the things I'm struggling with most. I'll have more to say in a
forthcoming email maybe.


Store and forward vs break-on-disconnect
========================================

Assuming we have "live references" at all, we are left with some
decisions on what to do about connections. Maybe this is more of a
VatTP thing, I'm unsure, but there seem to be CapTP considerations.

Let's contrast two approaches:

- Live connections which break on disconnect: this was the E approach,
and you use a sturdyref (though maybe we could use a certificate
chain or whatever) to start the connection between vats/machines,
from which you bootstrap your access to live references. On
connection severance (for whatever reason), all live references
break and throw relevant errors.

This is an extremely sensible choice for a distributed video game
like Electric Communities, and seems extremely sensible for my own
use case likewise. If I disconnect from a real-time game, I want my
interface to reflect that.

- Store and forward networks where undelivered messages are always
"waiting in transit". This is really nice for peer to peer systems
where users may go offline a lot, and thus it's an appealing
direction to me for social networks. It could even be very appealing
for turn-based games. This is the direction Agoric is going, but
their motivation appears to be primarily "how do we collaborate with
blockchains" oriented.

I feel like there is a strong desiderata for both of these cases. I
will probably start with the former but I'd like to support the latter.

Is supporting both really feasible?


Procedures vs objects-with-methods as first class?
==================================================

Guy L. Steele nicely broke down how both objects are a poor man's
procedures, and procedures are a poor man's objects.

https://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg03277.html

This is a bit vague, because what "object" means is a bit vague:

http://www.mumble.net/~jar/articles/oo.html

So let's clarify that we're talking about "objects with methods" vs
"procedures", which as many know once you can have one, you can build
the other out of it:

- E chose to make objects-with-methods first-and-foremost: a procedure
is just a special kind of object that merely has a .run() method.
- Goblins goes down the classic Scheme route:
https://dl.acm.org/doi/10.1145/62678.62720
Procedures are first class, and some (but not all) procedures take a
first argument, which is used for method dispatch.

If we want to make Goblins and Agoric's SwingSet inter-compatible, how
do we do it? Which one "wins"?

Looking at the TC39 Eventual Send proposal suggests another path:

https://github.com/tc39/proposal-eventual-send

I personally find EventualGet to be highly disturbing, so let's ignore
it. Use getters, not attributes! :)

So EventualGet being ignored, this proposal gives EventualApply and
EventualSend. These correspond to procedures and method invocation
respectively. (Note that I don't like calling method invocation "send";
for me, "send" is something we support in Goblins and really means
sending an asynchronous message as opposed to call-and-return
invocation. That seems more correct anyway, and "send" thus resembles
dropping something off at the post office. I have never liked "send" as
a way to refer to "invoke a method" for this reason.)

Separating these out into two different ways of *calling things* (as
opposed to two different ways of *constructing things*) is
interesting, and actually seems justifiable to me. An object can itself
provide both "a way to be invoked as a procedure" and "a way to be
invoked with methods". I could support this (and it may even simplify
some "meta methods" headaches I was considering surrounding supporting
the interfaces grant we're working on... more on that later).

It also removes the need to "make a decision" of whether or not to make
procedures and objects-with-methods two separate things or to build it
out of one thing's abstraction. As long as we support both ways of
invoking/sending, we are good.

(But seriously, fire EventualGet into the sun.)


Message ordering
================

I don't understand E-Order and it kind of intimidates me. I'm just
being honest. It would be great to rectify this.

I think as a first step I'm just going to do a roughly-FIFO type thing
that doesn't do too much in terms of message ordering across vat
boundaries. I know there are reasons expressed by MarkM and especially
apparently Dean, but I'm actually unsure: is the complexity worth it?
And how hard is it to do, really?

Maybe in the future I'll Get It (TM) but I'll probably start out without it.


BONUS: Distributed cyclic GC
============================

Obviously I am not going to do this anytime soon but it breaks my brain
that MarkM told me something like "Original E had distributed cyclic GC
support". Apparently it is complicated, involves some hooks into the
local garbage collector, and is rarely needed and tricky enough that
Mark said he doesn't bother to ask for it anymore, but I'm just gonna
say that it both blows my mind and completely befuddles me that some
version of E ever had something like this.

What huh what huh what? And was it ever documented how it works so that
sages in the future can help us sweep out our networks from unneeded
junk? Or is it an idea lost to the sands of time?

I find it personally fairly mystifying.


BONUS: What happens when multiple vats/machines resolve the same resolver?
==========================================================================

This is kind of a side note so I left it for the end.

It strikes me that if promise-resolver pairs are first class, one could
do some really goofy things and hand the same resolver to two different
vats to resolve... first one wins. If Vat C thinks it just successfully
resolved the resolver, it can immediately move forward with pipelined
messages waiting on the result, while Vat D thinks the same, and moves
forward with messages waiting on its own conflicting result. Both of
them may think they can move forward with plans when it actually isn't
safe.

The right answer seems to be, "promise pipelining is something only
set up at the CapTP layer and isn't exposed as something first class
so users shouldn't be able to create messed up situations like this
because we never gave them first-class ability to do it... and there's
only so much you can trust stuff moving across the network layer
in opaque actor type systems anyway."

Which seems true enough for our live-actor'y things. I bet you could
create some sneaky vulnerabilities in a cross-blockchain system what
wasn't anticipating this and took advantage of promise pipelining, and
wasn't engineered to handle this scenario. Dunno.


What's next, assuming I keep sending messages about these
=========================================================

Hi, do you hate this thread yet?

I've left some things I'm uncertain about above. Thoughts welcome.
I'll also share more as I implement, assuming people are open to me
continuing to do so on this list.

I think in an upcoming email I may try to break down some of the common
message types sent in CapTP... that might help me think about what *I*
should implement, too.

But I guess we'll see... what do you think? Is this, and subsequent
similar, message(s) worthwhile/welcome?

- Chris

Christopher Lemmer Webber

unread,
May 18, 2020, 6:21:54 PM5/18/20
to cap-...@googlegroups.com
Christopher Lemmer Webber writes:

> (Side note, when I hear "import" and "export" and then look at the
> arrows, I get confused, because I think of "import", arrow-wise, "being
> shipped to" the side that is importing, such as packages "ship to" an
> importer in a trading situation and "ship from" an exporter. The arrows
> are being tricky though, because the we're importing a reference "to" an
> object that never leaves its location.)

Just clarifying why this is confusing, based on a conversation I just
had on IRC. If I think, "Vat A is giving Vat B a reference to Alice, so
it's exporting it", that makes sense.

But the usual ocap diagrams look like this:

(Alice) ---> (Bob)

And suddenly when we diagram the tables it looks like

(Alice) --[imports]--[exports]--> (Bob)

... and that looks super confusing. The arrow is pointing the wrong
way! (But I know why.)

Rob Markovic

unread,
May 18, 2020, 6:41:34 PM5/18/20
to cap-...@googlegroups.com

I put beer goggles on and ask, what's TP stand for?

++ Rob


--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/875zcs28ao.fsf%40dustycloud.org.

Baldur Jóhannsson

unread,
May 18, 2020, 7:02:34 PM5/18/20
to cap-talk
True Paper! No, seriously, it stands for Transport Protocol.

Suspect it was inspired by the Hyper-Text Transport Protocol.

And it had nothing to do with the other kind of TP that stores ran into shortage of.

-Baldur

Kevin Reid

unread,
May 18, 2020, 7:15:09 PM5/18/20
to cap-...@googlegroups.com
On Mon, May 18, 2020 at 2:25 PM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:
What happens when multiple vats/machines resolve the same resolver?

Within CapTP, a reference to a resolver is, I believe, never handed off to another machine, so this case can't arise, but I don't remember exactly how the 3-party-introduction operates.

However, CapTP in E is built on top of a local promise system that does expose resolvers for general use, and the question does arise there (not specific to multiple machines). In that case, all implementations have been "the first to resolve wins", since it would be Bad if a resolved promise changed targets. However, there is one other question: what does the loser of the race see?

1. E chose to throw an exception in response to the second resolve() message to indicate that there was a probable bug.

2. Waterken chose to silently do nothing, on the grounds that that way a resolver is a purely write-only communication channel — the holder of a resolver cannot learn whether someone else already used it.

Mark S. Miller

unread,
May 18, 2020, 7:26:42 PM5/18/20
to cap-...@googlegroups.com
Nice message -- please keep them coming!

FWIW, resending with the ascii art in, hopefully for each of you reading, a fixed width font. (I'm doing this in gmail)

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

Mark S. Miller

unread,
May 18, 2020, 7:50:59 PM5/18/20
to cap-...@googlegroups.com
OMG, I was writing a long explanation about why we still need a Vine, and found that we do not. We did need a Vine when 3-party introductions were based on swiss numbers. Once we introduced the handoff tables, we no longer do. VatC will retain Carol in VatC's VatA-gifts-for-VatB handoff table until VatB looks it up, placing Carol in VatC's C-to-B exports table.

Somehow, though I introduced the handoff tables over 10 years ago, I never noticed that they make the Vine irrelevant. Thanks!

Mark S. Miller

unread,
May 18, 2020, 8:06:06 PM5/18/20
to cap-...@googlegroups.com
On Mon, May 18, 2020 at 4:26 PM Mark S. Miller <ma...@agoric.com> wrote:

If, before singularity, this gets implemented again for modern distributed ocap protocols (captp, cap'n proto, goblins, ...), I will be pleasantly surprised.
 
Feel free to take that as a challenge. But not first!

William ML Leslie

unread,
May 18, 2020, 8:07:24 PM5/18/20
to cap-talk
On Tue, 19 May 2020 at 07:25, Christopher Lemmer Webber
<cwe...@dustycloud.org> wrote:
> - Also usually there are two other tables in addition to
> imports/exports: questions/answers. These corresponds to "future
> resolutions to promises" (as well as some "promise pipelining" stuff
> but we'll talk about that later). A way to think of this is: if Bob
> sends a message to Carol using the <- operator in Goblins, Bob should
> get back a response that will eventually be resolved with Carol's
> response... but when we cross the network divide and Machine2+VatC
> gets that message saying "hey, call Carol... and when you're done,
> fulfill this thing", we need some way to refer to that.
>
> *SCREECH!* Let's slam the brakes on that last statement for a second.
> Because there could be another solution (ignoring promise pipelining for
> a second) that gets rid of questions/answers: Machine1+VatB could set up
> an export for Machine2+VatC that refers to the promise-resolver that
> will fulfill Bob's promise. We could just say in the message to Carol:
> "and once you have an answer, fulfill the promise with
> <this-resolver-i-just-exported-for-you>"!
>
> Well that seems to solve that just fine and dandy so why bloat our
> protocol with these extra two question/answer tables? Shouldn't
> import/export be fine?
>

You've successfully figured out that "who allocates the index" is one
important distinction between the tables, the other is "which way the
references point". The import table maps far refs to their id, wheras
the export table maps ids to the objects we are exporting.

Keep in mind, too, that the caller may not actually want to receive
the result, they may want to simply pass it elsewhere or discard it.

--
William Leslie

Notice:
Likely much of this email is, by the nature of copyright, covered
under copyright law. You absolutely MAY reproduce any part of it in
accordance with the copyright law of the nation you are reading this
in. Any attempt to DENY YOU THOSE RIGHTS would be illegal without
prior contractual agreement.

Ian Denhardt

unread,
May 18, 2020, 8:10:56 PM5/18/20
to Christopher Lemmer Webber, cap-...@googlegroups.com
Quoting Christopher Lemmer Webber (2020-05-18 17:25:01)
> EDIT BEFORE SENDING: this message has gotten huge and I apologize
> in advance unless you think it's great in which case you're welcome.

Hah, I enjoyed it anyway. I'll try to weigh in on a few things and share
what experience I have to offer from writing an FP implementation of
Cap'n Proto (specifically the Haskell implementation), and from using a
handful of different libraries in different languages for the same
protocol.

> So does that mean we need questions/answers too?
> ================================================
>
> So now that brings us back to: do we need questions/answers in addition
> to these imports/exports? And... actually I'm not so sure.
>
> It strikes me that, when exporting, Machine1+VatB could say "I'm
> allocating this object reference for you, and it's a resolver type".
> Then when importing, Machine2+VatC could make note of that, and
> when it resolves it, immediately make note in its imports table.
> Thus when Carol has that answer ready for Bob, Vat C can make note
> of that and still use the reference to Carol.
>
> I still don't see the need for separate questions/answers tables.
> Maybe I'm missing something. Maybe it's obvious in practice.

I do think it's possible to get rid of Q&A tables in a way that
simplifies things. But first to review: with a call like:

x.foo().bar().baz(),

the caller needs to be able to:

1. Address the message foo() to x.
2. Address the message bar() to the result of (1).
3. Address the message baz() to the result of (2).

This means the sender needs to choose the addresses for the intermediate
results, and this one thing the separate tables get you:

+--------------------------+-----------------+-------------------+
| | Lives in Sender | Lives in Receiver |
+--------------------------+-----------------+-------------------+
| ID is Sender Allocated | Exports | Questions |
| ID is Receiver Allocated | Answers | Imports |
+--------------------------+-----------------+-------------------+

Passing in a resolver doesn't solve the problem on its own because you
have no way of addressing whatever the receiver eventually feeds to the
resolver. If you drop questions & answers, you somehow need to figure
out how to pick addresses for intermediate results.

That said, I *do* think there's an opportunity for a simplification that
gets rid of the Q&A tables and also some message types. I'll use
capnproto terminology to make things concrete:

- Make object IDs a pair of (who allocated, numeric ID), instead of
just a numeric ID.
- Replace the `Call` message's `questionId` field with a fresh object
id N, which will be inserted into the receiver's exports table as
(remote allocated, N), and marked as a promise that will be resolved
later (the protocol already has the latter concept).
- When the call returns, instead of sending a `Return` message, send
a `Resolve` message, which uses the usual promise resolution logic
to provide the result. We can drop the `Return` message type from the
protocol entirely, as it is unused.
- Drop the `Finish` message type too; you can just use a `Release`
message for the same purpose, now that the result is just another
capability.

This also has the neat effect that on top of having simplified the
protocol, it also becomes easy to add fire-and-forget calls; just omit
the promise.

> Store and forward vs break-on-disconnect
> ========================================
>
> [...]
>
> Is supporting both really feasible?

My first instinct here is to do this at a lower level, i.e. use the
disconnect error approach but provide a "persistent transport" that
hides transient disconnects. I haven't though through this deeply
though.

> If we want to make Goblins and Agoric's SwingSet inter-compatible, how
> do we do it? Which one "wins"?

I think this actually doesn't need to resolved at the protocol level;
you can map it to different languages in different ways, as is natural.
At the protocol level there's a `Call` message that has a payload, and
there's a return value that is expected. In capnproto the call message
has an interface id and a method id, but rather than at the language
level using those to work out what method to call, you could just pass
them to the (single) function, and have it switch on those itself. In
the Haskell implementation I ended up mapping things to type classes
because it made diamond dependencies on interfaces easier to deal with,
but another design I considered was to just have actors receive messages
of a single type, which is a discriminated union. i.e. for an interface
like:

interface SomeInterface {
foo @0 A -> B;
bar @1 C -> D;
}

You'd have a message type like:

data SomeInterface_Msg
= Foo A (Fulfiller B)
| Bar C (Fulfiller D)


Even with the protocol in its current state, if I were to do it all
over again I'd be tempted to go that route; in hindsight I think it
would be nicer in some ways, even with the diamond dependency issues.

> Message ordering
> ================
>
> I don't understand E-Order and it kind of intimidates me. I'm just
> being honest. It would be great to rectify this.

E-order is roughly just that the messages sent via a particular
capability should be delivered in FIFO. The disembargo stuff that shows
up at the protocol level is implementation detail to make sure this
abstraction doesn't leak even when cross-vat promises are resolved.

> I think as a first step I'm just going to do a roughly-FIFO type thing
> that doesn't do too much in terms of message ordering across vat
> boundaries. I know there are reasons expressed by MarkM and especially
> apparently Dean, but I'm actually unsure: is the complexity worth it?
> And how hard is it to do, really?

It's not *that* hard to implement, at least in the two-party version,
but it's also possible to design the protocol (and capnproto is designed
this way) such that an implementation can get around this by just
responding "not implemented" to Resolve messages and keep sending calls
to the promise, not the resolved object. This prevents path shortening
from working, but it's a good stepping stone to get the basic
abstraction working without extra effort. The Go implementation does
this, and the first versions of the Haskell implementation did the same
thing. You can absolutely add this later, though it might make sense to
sanity check with folks that the particulars of your design facilitate
doing that.

Hope this is useful,

-Ian

Mark S. Miller

unread,
May 18, 2020, 8:27:46 PM5/18/20
to cap-...@googlegroups.com
On Mon, May 18, 2020 at 4:26 PM Mark S. Miller <ma...@agoric.com> wrote:
The answer doesn't start with promise pipelining. Consider

let resolve;

const bob = harden({
    foo() {
        return new Promise(r => resolve);
    }
}

Alice says:

const p = bobP~.foo();

or without the sugar

const p = E(bobP).foo();

For those more familiar with E, the equivalent might be, depending on my rusty memory:

var resolve;

def bob {
    to foo() {
        const [p, r] = Ref.promise();
        resolve = r;
        return p;
    }
}

Alice says:

def p = bobP <- foo();

Let's start considering the situation where everything is in one vat. Once Alice sends off the foo() message, where is the authority to resolve p?

It is no longer with Alice. Even though Alice created this promise, she immediately gave away her authority to resolve it.

First, it is in the air, traveling with the foo() message.

Then when the foo() message arrives at Bob, Bob gets the authority to resolve it. But not even Bob gets the resolver! Rather, that promise will be resolved by whatever Bob returns. By returning a fresh promise and holding on to the resolver, Bob has obtained that authority. At that point, exclusively! To emphasize this exclusive nature, at Agoric we have taken to saying that Bob is now "the decider". Notice "the".

Now let's revisit with Alice in VatA and Bob in VatB. To Alice, the local proxy for bob is the decider. To VatA, VatB is the decider. To VatB, Bob is the decider.

When Alice then does one of

p~.bar()
E(p).bar()  // no sugar
p <- bar()  // E

where should the message go? After all, we don't know where the object is that p will designate. It might even be on VatA. However, the unambiguously best answer is "send it to the decider". The steps by which it will come to be determined where that object is starts with the decision made by the decider. Therefore, if bar() needs to be routed elsewhere, that will be known at the decider before it is known anywhere else.
 


What's next, assuming I keep sending messages about these
=========================================================

Hi, do you hate this thread yet?

NO!
 

I've left some things I'm uncertain about above.  Thoughts welcome.
I'll also share more as I implement, assuming people are open to me
continuing to do so on this list.

I think in an upcoming email I may try to break down some of the common
message types sent in CapTP... that might help me think about what *I*
should implement, too.

But I guess we'll see... what do you think?  Is this, and subsequent
similar, message(s) worthwhile/welcome?

YES!

Mark S. Miller

unread,
May 18, 2020, 9:32:39 PM5/18/20
to cap-talk
Don't forget ftp. Actually, feel free to forget it ;)


--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.


--
  Cheers,
  --MarkM

Mark S. Miller

unread,
May 18, 2020, 9:37:43 PM5/18/20
to cap-talk
On Mon, May 18, 2020 at 4:15 PM Kevin Reid <kpr...@switchb.org> wrote:
On Mon, May 18, 2020 at 2:25 PM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:
What happens when multiple vats/machines resolve the same resolver?

Within CapTP, a reference to a resolver is, I believe, never handed off to another machine, so this case can't arise, but I don't remember exactly how the 3-party-introduction operates.

However, CapTP in E is built on top of a local promise system that does expose resolvers for general use, and the question does arise there (not specific to multiple machines). In that case, all implementations have been "the first to resolve wins", since it would be Bad if a resolved promise changed targets. However, there is one other question: what does the loser of the race see?

In E, the resolver itself is just a normal pass-by-proxy object. The comm system makes no special case for "sending" a resolving. You just get remote proxies to the stationary resolver. Whatever vat holds the actual resolver is the decider.
 

1. E chose to throw an exception in response to the second resolve() message to indicate that there was a probable bug.

2. Waterken chose to silently do nothing, on the grounds that that way a resolver is a purely write-only communication channel — the holder of a resolver cannot learn whether someone else already used it.

JavaScript chose the Waterken semantics. I don't remember anymore if I was for or against that on tc39 at the time. Agoric of course adopts the JS semantics.

 

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

Ian Denhardt

unread,
May 18, 2020, 10:06:24 PM5/18/20
to Mark S. Miller, cap-talk
Quoting Mark S. Miller (2020-05-18 21:37:31)

> However, CapTP in E is built on top of a local promise system that does
> expose resolvers for general use, and the question does arise there
> (not specific to multiple machines). In that case, all implementations
> have been "the first to resolve wins", since it would be Bad if a
> resolved promise changed targets. However, there is one other question:
> what does the loser of the race see?

It's worth observing that depending on the system there's another option
here: If you're in a language with ownership types, you can just prevent
the aliasing in the first place, statically. Obviously not always
applicable, but interesting.

-Ian

William ML Leslie

unread,
May 18, 2020, 10:19:37 PM5/18/20
to cap-talk
It's more a modality problem - a promise can be resolved at most once,
even if only one scope has access to it.

Ian Denhardt

unread,
May 18, 2020, 11:13:58 PM5/18/20
to William ML Leslie, cap-talk
Quoting William ML Leslie (2020-05-18 22:19:24)

> > It's worth observing that depending on the system there's another option
> > here: If you're in a language with ownership types, you can just prevent
> > the aliasing in the first place, statically. Obviously not always
> > applicable, but interesting.
> >
>
> It's more a modality problem - a promise can be resolved at most once,
> even if only one scope has access to it.

Yes, by ownership types I was thinking of substructural type systems,
like Rust's "affine" types (use at most once). Sorry if the loose
terminology was confusing.

-Ian

Matt Rice

unread,
May 19, 2020, 4:42:16 AM5/19/20
to cap-...@googlegroups.com
On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
<cwe...@dustycloud.org> wrote:

> There's no need to layer a complex (and more insecure) security
> architecture on top of our programming languages because the way
> programmers already program, if we take it seriously, already *is* our
> programming model:

This seems like you wanted to say "already *is* our security model",
otherwise it seems somewhat tautological.
https://xkcd.com/703/
I also think "on top of our programming languages", should really be
"on top of memory safe programming languages".

There seems to also be a distinction that could be made (having only
read this far as of yet),
that (I don't know what to call memory unsafe programming languages,
lassiez faire?),
But taking one of those and *adding* a security model -- to make up
for its insecurity has been so far unworkable,
While taking a memory safe programming language and *keeping it*
secure by *not adding*
insecurity is a workable and realistically achievable approach.

shrug

William ML Leslie

unread,
May 19, 2020, 5:15:26 AM5/19/20
to cap-talk
On Tue, 19 May 2020 at 18:42, Matt Rice <rat...@gmail.com> wrote:
>
> On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
> <cwe...@dustycloud.org> wrote:
>
> > There's no need to layer a complex (and more insecure) security
> > architecture on top of our programming languages because the way
> > programmers already program, if we take it seriously, already *is* our
> > programming model:
>
> This seems like you wanted to say "already *is* our security model",
> otherwise it seems somewhat tautological.
> https://xkcd.com/703/
> I also think "on top of our programming languages", should really be
> "on top of memory safe programming languages".
>

I understood "on top of our programming languages" to be an indictment of this:

https://docs.oracle.com/javase/7/docs/api/java/lang/SecurityManager.html

the Java SecurityManager has been a massive footgun and attempts at
using it rather than paring everything down to capability semantics is
the main reason that having a java client installed (or worse, having
the web plugin installed) is considered a security risk. People like
to quibble about versions, but putting band-aids on a sieve won't
quickly make it waterproof.

Neil Madden

unread,
May 19, 2020, 5:44:19 AM5/19/20
to cap-...@googlegroups.com


On 19 May 2020, at 10:15, William ML Leslie <william.l...@gmail.com> wrote:

On Tue, 19 May 2020 at 18:42, Matt Rice <rat...@gmail.com> wrote:

On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
<cwe...@dustycloud.org> wrote:

There's no need to layer a complex (and more insecure) security
architecture on top of our programming languages because the way
programmers already program, if we take it seriously, already *is* our
programming model:

This seems like you wanted to say "already *is* our security model",
otherwise it seems somewhat tautological.
https://xkcd.com/703/
I also think "on top of our programming languages", should really be
"on top of memory safe programming languages".


I understood "on top of our programming languages" to be an indictment of this:

https://docs.oracle.com/javase/7/docs/api/java/lang/SecurityManager.html

the Java SecurityManager has been a massive footgun and attempts at
using it rather than paring everything down to capability semantics is
the main reason that having a java client installed (or worse, having
the web plugin installed) is considered a security risk.  People like
to quibble about versions, but putting band-aids on a sieve won't
quickly make it waterproof.

On that note, I found this interesting wording in the Java 11 Secure Coding Guidelines (https://www.oracle.com/java/technologies/javase/seccodeguide.html):

Guideline 0-5 / FUNDAMENTALS-5: Minimise the number of permission checks

Java is primarily an object-capability language. SecurityManager checks should be considered a last resort. Perform security checks at a few defined points and return an object (a capability) that client code retains so that no further permission checks are required.

Section 9 elaborates:

Although Java is largely an object-capability language, a stack-based access control mechanism is used to securely provide more conventional APIs.

Well, it made me chuckle anyway…

— Neil

Matt Rice

unread,
May 19, 2020, 5:55:03 AM5/19/20
to cap-...@googlegroups.com
On Tue, May 19, 2020 at 9:15 AM William ML Leslie
<william.l...@gmail.com> wrote:
>
> On Tue, 19 May 2020 at 18:42, Matt Rice <rat...@gmail.com> wrote:
> >
> > On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
> > <cwe...@dustycloud.org> wrote:
> >
> > > There's no need to layer a complex (and more insecure) security
> > > architecture on top of our programming languages because the way
> > > programmers already program, if we take it seriously, already *is* our
> > > programming model:
> >
> > This seems like you wanted to say "already *is* our security model",
> > otherwise it seems somewhat tautological.
> > https://xkcd.com/703/
> > I also think "on top of our programming languages", should really be
> > "on top of memory safe programming languages".
> >
>
> I understood "on top of our programming languages" to be an indictment of this:
>
> https://docs.oracle.com/javase/7/docs/api/java/lang/SecurityManager.html
>
> the Java SecurityManager has been a massive footgun and attempts at
> using it rather than paring everything down to capability semantics is
> the main reason that having a java client installed (or worse, having
> the web plugin installed) is considered a security risk. People like
> to quibble about versions, but putting band-aids on a sieve won't
> quickly make it waterproof.

Trying to understand where I disconnect,
I guess any all languages are sufficient to derive the logic behind a policy,
even those which lack the inherent ability to enforce it. I was
basically nitpicking
that removing the security manager from something like java gets you no closer
to actually enforcing policy derived within the language.
Anyhow the statement is a bit strong for my taste, given the subtlety
of prescribing vs passive enforcement of policy.

William ML Leslie

unread,
May 19, 2020, 6:35:50 AM5/19/20
to cap-talk
On Tue, 19 May 2020 at 19:55, Matt Rice <rat...@gmail.com> wrote:
>
> On Tue, May 19, 2020 at 9:15 AM William ML Leslie
> <william.l...@gmail.com> wrote:
>
> Trying to understand where I disconnect,
> I guess any all languages are sufficient to derive the logic behind a policy,
> even those which lack the inherent ability to enforce it. I was
> basically nitpicking
> that removing the security manager from something like java gets you no closer
> to actually enforcing policy derived within the language.
> Anyhow the statement is a bit strong for my taste, given the subtlety
> of prescribing vs passive enforcement of policy.
>

Would love to know more of what you're thinking - I read the caveat
that static analysis, type systems, and protected memory are still
valuable security tools even in a capability-safe environment, but
I've been known to misread things.

William ML Leslie

unread,
May 19, 2020, 6:42:49 AM5/19/20
to cap-talk
On Tue, 19 May 2020 at 19:44, Neil Madden <neil....@forgerock.com> wrote:
> On that note, I found this interesting wording in the Java 11 Secure Coding Guidelines (https://www.oracle.com/java/technologies/javase/seccodeguide.html):
>
> Guideline 0-5 / FUNDAMENTALS-5: Minimise the number of permission checks
>
> Java is primarily an object-capability language. SecurityManager checks should be considered a last resort. Perform security checks at a few defined points and return an object (a capability) that client code retains so that no further permission checks are required.
>
> Section 9 elaborates:
>
> Although Java is largely an object-capability language, a stack-based access control mechanism is used to securely provide more conventional APIs.
>
> Well, it made me chuckle anyway…
>
> — Neil
>

Wow!

I am still horrified by this:

https://docs.oracle.com/javase/tutorial/networking/urls/connecting.html

I guess it's "primarily an object-capability language with a primarily
ambient standard library" ?

Christopher Lemmer Webber

unread,
May 19, 2020, 6:52:06 AM5/19/20
to cap-...@googlegroups.com
Ahaha, and here I thought maybe I'd send this at the end of the work day
yesterday and nobody would actually read it... woke up to a full inbox.

Kevin Reid writes:

> On Mon, May 18, 2020 at 2:25 PM Christopher Lemmer Webber <
> cwe...@dustycloud.org> wrote:
>
>> What happens when multiple vats/machines resolve the same resolver?
>>
>
> Within CapTP, a reference to a resolver is, I believe, never handed off to
> another machine, so this case can't arise, but I don't remember exactly how
> the 3-party-introduction operates.
>
> However, CapTP in E is built on top of a local promise system that does
> expose resolvers for general use, and the question does arise there (not
> specific to multiple machines). In that case, all implementations have been
> "the first to resolve wins", since it would be Bad if a resolved promise
> changed targets. However, there is one other question: what does the loser
> of the race see?
>
> 1. E chose to throw an exception in response to the second resolve()
> message to indicate that there was a probable bug.
>
> 2. Waterken chose to silently do nothing, on the grounds that that way a
> resolver is a *purely write-only communication channel* — the holder of a
> resolver cannot learn whether someone else already used it.

"What does the loser of the race see" is a good way to put it. Before I
reply to that, let's move forward with, "what does the loser of the race
see when they're confident they already won the promise pipelining race,
and already went off to go eat some winners-victory cake, only to find
out after eating an entire slice that someone else won?"
"The decider" is a good way of putting things, except it gives me
flashbacks to GWB:

https://youtu.be/irMeHmlxE9s?t=44

Of course, "the" decider makes it sound like there can only be one. But
I like Kevin's "what does the loser of the race see", which is a context
that we may have set up multiple potential deciders.

> Now let's revisit with Alice in VatA and Bob in VatB. To Alice, the local
> proxy for bob is the decider. To VatA, VatB is the decider. To VatB, Bob is
> the decider.
>
> When Alice then does one of
>
> p~.bar()
> E(p).bar() // no sugar
> p <- bar() // E
>
> where should the message go? After all, we don't know where the object is
> that p will designate. It might even be on VatA. However, the unambiguously
> best answer is "send it to the decider". The steps by which it will come to
> be determined where that object is starts with the decision made by the
> decider. Therefore, if bar() needs to be routed elsewhere, that will be
> known at the decider before it is known anywhere else.

I'm actually not too concerned from the perspective of Alice at the
moment. Let's say that, in theory, something goofy happened... Vat A
actually sent messages to two different vats. Bob on Vat B and Carol on
Vat C are now both "the decider" and are ready to do something under the
assumption that they're the ones who resolve that promise.

- Bob's promise pipeline has Bob resolve p with cake, and then proceeds
with the next instruction in the pipeline, which is for Bob to eat
the cake.
- Carol's promise pipeline has Carol resolve p with pie, and then
proceeds with the next instruction in the pipeline, which is for
Carol to throw the pie.

We can think of this as a one-phase part of a commit, where Bob and
Carol both immediately assumed that they were the "decider" and could
move forward under the next step of the system.

In an opaque and "live actor'y" mutually suspicious system, I suppose
that Bob and Carol don't know and don't care what promise they're
resolving anyway. The thought is really "I've been given some numerical
index which, once I decide what it is, I'm told to use my decision in
this next step too. What's it resolving? Who cares. I'm just
following these steps... if Alice screwed up the pipeline by declaring
Too Many Cooks*, that's her problem."

But thinking about resolving a promise as a one or two phase commit, and
promise pipelining moving off of the assumption that "I'm the decider"
when maybe there are multiple deciders, sounds like a potential race
condition in the case that you *do* care waht the promise is.

When would that be a problem? And why did I say "blockchains"?

Well I have *no idea* how the Agoric blockchain-machine-mappings work.
My guess is: they probably don't have this problem. But if the mapping
did somehow operate off of the assumption that "I'm the decider" for
sure, Bob eats his cake when actually Carol "won", will this be caught?
Is there a problem with "moving forward under those assumptions"?

And I guess it depends on how the blockchain stuff maps. It probably
isn't a problem. But it's what I was thinking about, out loud. "Too
many cooks/deciders should fail safe".

I'm not sure it ended up being a useful observation, but it lead to some
interesting conversation anyway. :)

- Chris

* Too Many Cooks not failing safe:**
https://www.youtube.com/watch?v=QrGrOK8oZG8

** "This is the worst case of intro-nitis I've ever seen" sounds like
it should fit in somewhere to some ocap conversation

Christopher Lemmer Webber

unread,
May 19, 2020, 6:55:19 AM5/19/20
to cap-...@googlegroups.com
Mark S. Miller writes:

>> BONUS: Distributed cyclic GC
>> ============================
>>
>> Obviously I am not going to do this anytime soon but it breaks my brain
>> that MarkM told me something like "Original E had distributed cyclic GC
>> support". Apparently it is complicated, involves some hooks into the
>> local garbage collector, and is rarely needed and tricky enough that
>> Mark said he doesn't bother to ask for it anymore, but I'm just gonna
>> say that it both blows my mind and completely befuddles me that some
>> version of E ever had something like this.
>>
>> What huh what huh what? And was it ever documented how it works so that
>> sages in the future can help us sweep out our networks from unneeded
>> junk? Or is it an idea lost to the sands of time?
>>
>
> http://erights.org/history/original-e/dgc/
>
> If, before singularity, this gets implemented again for modern distributed
> ocap protocols (captp, cap'n proto, goblins, ...), I will be pleasantly
> surprised.
>
> Feel free to take that as a challenge. But not first!

Horray!

Yeah, it'll be a long time until I have enough space clear (and
understanding of how GCs work), if ever, before I get to tackle
this... but excited that it's there to reference. Thank you!

Christopher Lemmer Webber

unread,
May 19, 2020, 6:57:47 AM5/19/20
to cap-...@googlegroups.com
Mark S. Miller writes:

>> 3-party introductions
>> =====================
>>
>> Once you've implemented all that, what happens if Alice wants to spend a
>> message about Carol to Dave, but Dave is on Machine 3 in Vat D (not
>> pictured above). Well what the heck do we do now?
>>
>> There's a whole thing about handoff tables. I feel like this is a
>> complicated subject, and one I want to write an entirely separate email
>> about because it still hurts my brain a little. The MarkM talk I linked
>> to above explains it reasonably though. So ok, we'll just say we can do
>> that. (There also has been something called "vines" used historically
>> though I've never been completely clear on what a "vine" is... maybe it
>> doesn't matter anymore.)
>>
>
> OMG, I was writing a long explanation about why we still need a Vine, and
> found that we do not. We did need a Vine when 3-party introductions were
> based on swiss numbers. Once we introduced the handoff tables, we no longer
> do. VatC will retain Carol in VatC's VatA-gifts-for-VatB handoff table
> until VatB looks it up, placing Carol in VatC's C-to-B exports table.
>
> Somehow, though I introduced the handoff tables over 10 years ago, I never
> noticed that they make the Vine irrelevant. Thanks!

That's funny. I worked through my understanding of 3 party
introductions in my head without assuming vines were relevant, because
you didn't mention them in the talk I listened to you talking about, so
I assumed you must have worked it out without vines being necessary.
Glad to contribute from that misunderstanding.

Didn't handoff tables also come about from you misunderstanding
something Alan Karp said? :)

Christopher Lemmer Webber

unread,
May 19, 2020, 7:00:32 AM5/19/20
to cap-...@googlegroups.com
Matt Rice writes:

> On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
> <cwe...@dustycloud.org> wrote:
>
>> There's no need to layer a complex (and more insecure) security
>> architecture on top of our programming languages because the way
>> programmers already program, if we take it seriously, already *is* our
>> programming model:
>
> This seems like you wanted to say "already *is* our security model",
> otherwise it seems somewhat tautological.
> https://xkcd.com/703/
> I also think "on top of our programming languages", should really be
> "on top of memory safe programming languages".

Yes this is true... but we can expand that a lot further because there
are many other language features in many languages that make those
languages themselves ocap unsafe (eg dynamic scope support in many
lisps, etc etc). So memory safety is one thing but not the only one if
we go down that path...

I guess what you're saying though is that it's the fact that the runtime
protects you from being able to access anything you weren't handed
access to as an argument is the underlying system providing memory
safety, in which case, true. Though there's something to brevity in
increasing understanding, where we can always follow up after the
initial a-ha. :)

Christopher Lemmer Webber

unread,
May 19, 2020, 7:07:59 AM5/19/20
to cap-...@googlegroups.com
William ML Leslie writes:

> On Tue, 19 May 2020 at 18:42, Matt Rice <rat...@gmail.com> wrote:
>>
>> On Mon, May 18, 2020 at 9:25 PM Christopher Lemmer Webber
>> <cwe...@dustycloud.org> wrote:
>>
>> > There's no need to layer a complex (and more insecure) security
>> > architecture on top of our programming languages because the way
>> > programmers already program, if we take it seriously, already *is* our
>> > programming model:
>>
>> This seems like you wanted to say "already *is* our security model",
>> otherwise it seems somewhat tautological.
>> https://xkcd.com/703/
>> I also think "on top of our programming languages", should really be
>> "on top of memory safe programming languages".
>>
>
> I understood "on top of our programming languages" to be an indictment of this:
>
> https://docs.oracle.com/javase/7/docs/api/java/lang/SecurityManager.html
>
> the Java SecurityManager has been a massive footgun and attempts at
> using it rather than paring everything down to capability semantics is
> the main reason that having a java client installed (or worse, having
> the web plugin installed) is considered a security risk. People like
> to quibble about versions, but putting band-aids on a sieve won't
> quickly make it waterproof.

Yes, that was the intent.

Though the most clear example I've seen of this was this talk:

https://www.youtube.com/watch?v=FNxS1oe3Bzw
https://arxiv.org/abs/1807.09377

The "security mechanisms" added there leads to an explosion of code and
confusion, whereas starting with the assumption that "argument passing
and lexical closures were already enough" means you could have written
all of that and as "normal, straightforward code" and it would have had
the security you wanted in ocap-land.

BTW, I don't mean to hate on this research in that it seems like it was
excellent work assuming that you start with their assumptions, that you
*needed to* layer something on top. I asked the presenter in the Q&A
whether they had compared it something to like Rees' "security kernel
based on the lambda calculus" paper:

https://youtu.be/FNxS1oe3Bzw?t=1184

They hadn't heard of it. To me, the takeaway there is helping people
understand that we already have "Lambda: The Ultimate Security
Abstraction."

Christopher Lemmer Webber

unread,
May 19, 2020, 7:08:23 AM5/19/20
to cap-...@googlegroups.com
This is hilarious.

Christopher Lemmer Webber

unread,
May 19, 2020, 7:10:45 AM5/19/20
to cap-...@googlegroups.com
Note that I'm not asking whether import/export is redundant, but whether
import+answer and export+question is redundant, even if handled
abstractly through negative indices in the same table, as E appears to
do. :)

Matt Rice

unread,
May 19, 2020, 8:18:04 AM5/19/20
to cap-...@googlegroups.com
On Tue, May 19, 2020 at 10:35 AM William ML Leslie
<william.l...@gmail.com> wrote:
>
> On Tue, 19 May 2020 at 19:55, Matt Rice <rat...@gmail.com> wrote:
> >
> > On Tue, May 19, 2020 at 9:15 AM William ML Leslie
> > <william.l...@gmail.com> wrote:
> >
> > Trying to understand where I disconnect,
> > I guess any all languages are sufficient to derive the logic behind a policy,
> > even those which lack the inherent ability to enforce it. I was
> > basically nitpicking
> > that removing the security manager from something like java gets you no closer
> > to actually enforcing policy derived within the language.
> > Anyhow the statement is a bit strong for my taste, given the subtlety
> > of prescribing vs passive enforcement of policy.
> >
>
> Would love to know more of what you're thinking - I read the caveat
> that static analysis, type systems, and protected memory are still
> valuable security tools even in a capability-safe environment, but
> I've been known to misread things.
>

While i'd certainly like to, probably for another thread -- It isn't
really what I was getting at.

I think Chris's "brevity in increasing understanding, where we can
always follow up after the
initial a-ha", covers my intent there well.

Essentially just "memory safe" as a stand in/catch all for a system in
which ambient authority has not yet been added,
Or it isn't enough to just remove the security manager, it is merely
one source of ambient authority, and usually is a symtom of another.

William ML Leslie

unread,
May 19, 2020, 8:53:09 AM5/19/20
to cap-talk
On Tue, 19 May 2020 at 21:10, Christopher Lemmer Webber
Sure, and I think it's worth exploring what CapTP/cc would look like
and how it would function. I'm wondering how promise pipelining still
works.

Let's say we have something like:

def send(connection, target, *args):
answer, question = connection.promise_and_resolver()
export_id = connection.add_export(question)
connection.send(Call(connection.imports[target],
[Export(export_id)] + map(connection.get, args))
return answer

sending messages to the promise wouldn't quite work - there'd need to
be some extra plumbing to get the messages to pass to the other side
rather than enque waiting for the promise to resolve.

Similarly, because the answer is now defined on the sender side, the
receiver will also need extra plumbing to send only resolve messages,
and enqueue anything else.

I suspect you'd need to make answers and questions very strange refs
in order to eliminate the answer/question concept cleanly.

William ML Leslie

unread,
May 19, 2020, 9:06:30 AM5/19/20
to cap-talk
On Tue, 19 May 2020 at 07:25, Christopher Lemmer Webber
<cwe...@dustycloud.org> wrote:
>
> Store and forward vs break-on-disconnect
> ========================================
>
> Assuming we have "live references" at all, we are left with some
> decisions on what to do about connections. Maybe this is more of a
> VatTP thing, I'm unsure, but there seem to be CapTP considerations.
>
> Let's contrast two approaches:
>
> - Live connections which break on disconnect: this was the E approach,
> and you use a sturdyref (though maybe we could use a certificate
> chain or whatever) to start the connection between vats/machines,
> from which you bootstrap your access to live references. On
> connection severance (for whatever reason), all live references
> break and throw relevant errors.
>
> This is an extremely sensible choice for a distributed video game
> like Electric Communities, and seems extremely sensible for my own
> use case likewise. If I disconnect from a real-time game, I want my
> interface to reflect that.
>
> - Store and forward networks where undelivered messages are always
> "waiting in transit". This is really nice for peer to peer systems
> where users may go offline a lot, and thus it's an appealing
> direction to me for social networks. It could even be very appealing
> for turn-based games. This is the direction Agoric is going, but
> their motivation appears to be primarily "how do we collaborate with
> blockchains" oriented.
>
> I feel like there is a strong desiderata for both of these cases. I
> will probably start with the former but I'd like to support the latter.
>
> Is supporting both really feasible?
>

I feel like there is probably good scope for implementing
functional-reactive patterns within a CapTP-like protocol, and that
they could support better behaviour on reconnection. I often imagine
that this might be like a SturdRef that represents a Mozart/Oz-style
logic variable bound to a list - a reference to a list that updates
are consed onto; such that actors can listen for updates or query for
the current state. I've craved this since David Barbour's "Why Not
Events?" but never got around to implementing it. The nice thing is
that unlike pub/sub systems, these lists can really be first-class and
allocated freely.

https://awelonblue.wordpress.com/2012/07/01/why-not-events/

Just one idea.

Christopher Lemmer Webber

unread,
May 19, 2020, 9:29:45 AM5/19/20
to cap-...@googlegroups.com
I am very interested in "FRP meets ocaps"... that's actually what got me
looking at ocap propagators as a generalization of that idea not long
ago.

Christopher Lemmer Webber

unread,
May 19, 2020, 9:33:12 AM5/19/20
to cap-...@googlegroups.com
I think it may be possible to make it work, but... it's hard to
articulate without showing it off. But I guess I will learn by
implementing and report back :)

Christopher Lemmer Webber

unread,
May 19, 2020, 9:40:28 AM5/19/20
to cap-...@googlegroups.com
William ML Leslie writes:

> On Tue, 19 May 2020 at 19:44, Neil Madden <neil....@forgerock.com> wrote:
>> On that note, I found this interesting wording in the Java 11 Secure
>> Coding Guidelines
>> (https://www.oracle.com/java/technologies/javase/seccodeguide.html):
>>
>> Guideline 0-5 / FUNDAMENTALS-5: Minimise the number of permission
>> checks
>>
>> Java is primarily an object-capability language. SecurityManager
>> checks should be considered a last resort. Perform security checks at
>> a few defined points and return an object (a capability) that client
>> code retains so that no further permission checks are required.
>>
>> Section 9 elaborates:
>>
>> Although Java is largely an object-capability language, a stack-based
>> access control mechanism is used to securely provide more
>> conventional APIs.
>>
>> Well, it made me chuckle anyway…
>>
>> — Neil
>>
>
> Wow!
>
> I am still horrified by this:
>
> https://docs.oracle.com/javase/tutorial/networking/urls/connecting.html
>
> I guess it's "primarily an object-capability language with a primarily
> ambient standard library" ?

I had a real scare when I learned that Racket's default http/web
abstraction layer library would automatically handle file:// uris in its
"http GET" abstraction, and since activitypub is all about
references-that-point-to-references-to-retrieve, this lead to a confused
deputy vulnerability against one of my libraries that meant that someone
could talk to the program and use it to request local files.
Even worse than "let me access against localhost"!

Speaking of, the moment where I learned to fear confused deputies also
involved URI requests, these ones against localhost:

https://lists.gnu.org/archive/html/guile-user/2016-10/msg00007.html

This allowed a webpage loaded in a browser to perform arbitrary code
execution against a Guile developer who was doing "live hacking" against
a REPL running "live" on localhost+port.

See also:

https://bou.ke/blog/hacking-developers/

Christopher Lemmer Webber

unread,
May 19, 2020, 10:16:05 AM5/19/20
to cap-...@googlegroups.com
Ian Denhardt writes:

> Quoting Christopher Lemmer Webber (2020-05-18 17:25:01)
>> EDIT BEFORE SENDING: this message has gotten huge and I apologize
>> in advance unless you think it's great in which case you're welcome.
>
> Hah, I enjoyed it anyway. I'll try to weigh in on a few things and share
> what experience I have to offer from writing an FP implementation of
> Cap'n Proto (specifically the Haskell implementation), and from using a
> handful of different libraries in different languages for the same
> protocol.

Cool (and sounds like it was an interesting project to do)!

>> So does that mean we need questions/answers too?
>> ================================================
>>
>> So now that brings us back to: do we need questions/answers in addition
>> to these imports/exports? And... actually I'm not so sure.
>>
>> It strikes me that, when exporting, Machine1+VatB could say "I'm
>> allocating this object reference for you, and it's a resolver type".
>> Then when importing, Machine2+VatC could make note of that, and
>> when it resolves it, immediately make note in its imports table.
>> Thus when Carol has that answer ready for Bob, Vat C can make note
>> of that and still use the reference to Carol.
>>
>> I still don't see the need for separate questions/answers tables.
>> Maybe I'm missing something. Maybe it's obvious in practice.
>
> I do think it's possible to get rid of Q&A tables in a way that
> simplifies things. But first to review: with a call like:
>
> x.foo().bar().baz(),
>
> the caller needs to be able to:
>
> 1. Address the message foo() to x.
> 2. Address the message bar() to the result of (1).
> 3. Address the message baz() to the result of (2).
>
> This means the sender needs to choose the addresses for the intermediate
> results, and this one thing the separate tables get you:
>
> +--------------------------+-----------------+-------------------+
> | | Lives in Sender | Lives in Receiver |
> +--------------------------+-----------------+-------------------+
> | ID is Sender Allocated | Exports | Questions |
> | ID is Receiver Allocated | Answers | Imports |
> +--------------------------+-----------------+-------------------+
>
> Passing in a resolver doesn't solve the problem on its own because you
> have no way of addressing whatever the receiver eventually feeds to the
> resolver. If you drop questions & answers, you somehow need to figure
> out how to pick addresses for intermediate results.

I still don't understand what's wrong with preallocating a bunch of
promises for the questions and answers. But I am more than likely just
not going to understand until I either hit the wall everyone else has or
just find out I stepped clear on the other side unscathed,
question-and-answer-tables-free.

Though the solution I am thinking of does kind of add back something
admittedly similar to the questions and answers tables... it just has
them typed in the same table. I guess we'll see.

> That said, I *do* think there's an opportunity for a simplification that
> gets rid of the Q&A tables and also some message types. I'll use
> capnproto terminology to make things concrete:
>
> - Make object IDs a pair of (who allocated, numeric ID), instead of
> just a numeric ID.
> - Replace the `Call` message's `questionId` field with a fresh object
> id N, which will be inserted into the receiver's exports table as
> (remote allocated, N), and marked as a promise that will be resolved
> later (the protocol already has the latter concept).
> - When the call returns, instead of sending a `Return` message, send
> a `Resolve` message, which uses the usual promise resolution logic
> to provide the result. We can drop the `Return` message type from the
> protocol entirely, as it is unused.
> - Drop the `Finish` message type too; you can just use a `Release`
> message for the same purpose, now that the result is just another
> capability.

That's actually almost entirely what I'm thinking, if I understand you
correctly. The key thing there is pre-allocating promise-resolver pairs
*for* the intermediate anticipated results in the promise pipelining.

Assuming I understand you, maybe that means we came to the same
conclusion, which makes me very optimistic.

> This also has the neat effect that on top of having simplified the
> protocol, it also becomes easy to add fire-and-forget calls; just omit
> the promise.

Yes!

>> Store and forward vs break-on-disconnect
>> ========================================
>>
>> [...]
>>
>> Is supporting both really feasible?
>
> My first instinct here is to do this at a lower level, i.e. use the
> disconnect error approach but provide a "persistent transport" that
> hides transient disconnects. I haven't though through this deeply
> though.

Yes! This is also what I am thinking.

There is one more important detail if we also consider the need of
combining support here with blockchain-like systems and still decide to
keep around sturdyrefs for the live systems: sturdyrefs can never be
allowed to appear on a blockchain, because that could lead to accidental
vulnerability.

The fail-safe solution is simple: when serializing and de-serializing
messages from live-land -> blockchain, simply throw an error and do not
serialize/deserialize the sturdyref type on either end.

>> If we want to make Goblins and Agoric's SwingSet inter-compatible, how
>> do we do it? Which one "wins"?
>
> I think this actually doesn't need to resolved at the protocol level;
> you can map it to different languages in different ways, as is natural.
> At the protocol level there's a `Call` message that has a payload, and
> there's a return value that is expected. In capnproto the call message
> has an interface id and a method id, but rather than at the language
> level using those to work out what method to call, you could just pass
> them to the (single) function, and have it switch on those itself.

The tricky thing is: what about the case where functions don't have a
method at all? Let's say we had a simple "doubler" argument... no
methods, just takes x and returns x * 2.

No methods are relevant to this procedure. Now we could make having a
method type argument mandatory, but I think this is unpleasant.

But I think if we make procedure calls and method calls two distinct
things, as the EventualSend proposal does, this is supportable enough.
I actually have good reasons to desire this right now which is
effectively the motivation for miranda methods. But I feel like I need
to expand on this later.

>> Message ordering
>> ================
>>
>> I don't understand E-Order and it kind of intimidates me. I'm just
>> being honest. It would be great to rectify this.
>
> E-order is roughly just that the messages sent via a particular
> capability should be delivered in FIFO. The disembargo stuff that shows
> up at the protocol level is implementation detail to make sure this
> abstraction doesn't leak even when cross-vat promises are resolved.
>
>> I think as a first step I'm just going to do a roughly-FIFO type thing
>> that doesn't do too much in terms of message ordering across vat
>> boundaries. I know there are reasons expressed by MarkM and especially
>> apparently Dean, but I'm actually unsure: is the complexity worth it?
>> And how hard is it to do, really?
>
> It's not *that* hard to implement, at least in the two-party version,
> but it's also possible to design the protocol (and capnproto is designed
> this way) such that an implementation can get around this by just
> responding "not implemented" to Resolve messages and keep sending calls
> to the promise, not the resolved object. This prevents path shortening
> from working, but it's a good stepping stone to get the basic
> abstraction working without extra effort. The Go implementation does
> this, and the first versions of the Haskell implementation did the same
> thing. You can absolutely add this later, though it might make sense to
> sanity check with folks that the particulars of your design facilitate
> doing that.

Ok, I will suspend disbelief enough to think that it is feasible for me
to understand. I feel like I really need a good presentation on the
subject to get through it.

(MarkM/Dean, you said you might do a presentation at some point about
E-Order eventually... I'm still interested. ;))

Christopher Lemmer Webber

unread,
May 19, 2020, 12:24:23 PM5/19/20
to cap-...@googlegroups.com
So, my confidence is raised a bit about the possibility of me being able
to implement CapTP by the responses here... it sounds like at least I
don't have a fundamentally wrong understanding of things. So it's time
to implement.

Here are the test cases I am thinking I will implement, using the
following notation: Alice(A1) means Alice on Vat A on Machine 2.
Dave(D3) means Dave on Vat D on Machine 3.

- Simple two vats on two-machine cases

- Alice(A1) sends a message to Carol(C2) which has Carol print "hello
Alice" to the screen. Called for side effect only so this is a
"Send Only" type message... promise is not requested / ignored.
- Requires initial bootstrap, probably with sturdyrefs?
- The same as above, but instead of Carol(C2) printing "Hello Alice",
this is the response value resulting in fulfillment of a promise
which Alice(A1) has set up a handler for.
- Requires promise resolution
- Same as above, but Carol(C2) throws an exception, which Alice(A1)
catches.
- Alice(A1) introduces Carol(C2) to Alfred(A1)
- Requires exporting on A1's side, importing on C2's side

- Multiple vats across two machines
- Alice(A1) introduces Carol(C2) to Bob(B1)
- Works across vats on same machine

- Promise pipelining
- Alice(A1) asks Carol(C2) to make her a Car(C2), then turn it on
- Alice(A1) tells Carol(C2) that Bob(B1) is her best friend.
Later Alice(A1) asks Carol(C2) who her best friend is, and then
immediately greets her best friend.

- Three vats across three machines
- Alice(A1) introduces Carol(C2) to Dave(D3).

- Distributed (acyclic) garbage collection

That seems to nicely break the problem into pieces, hopefully allowing
me to build it out incrementally.

The main thing I'm unsure of (which surprisingly nobody commented on!)
is whether or not the imports/exports tables live on the Machine layer
or on the Vat layer. We'll see via implementation, I guess... I see
advantages to both.

- Chris

Kevin Reid

unread,
May 19, 2020, 8:48:12 PM5/19/20
to cap-...@googlegroups.com
On Tue, May 19, 2020 at 9:24 AM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:
The main thing I'm unsure of (which surprisingly nobody commented on!)
is whether or not the imports/exports tables live on the Machine layer
or on the Vat layer.  We'll see via implementation, I guess... I see
advantages to both.

They were per vat, in E. That way, the same-machine-different-vat case is equivalent to the different-machine-different-vat case and does not need any special handling.

In principle, if you have a special case for vats that live in the same address space, you can avoid needing to serialize into a byte stream the data that crosses a vat boundary — but you still have to copy/proxy it according to the serialization rules (in E, Data-E as configured by CapTP) unless it consists of objects known to the implementation to be immutable-and-thread-safe (or whatever similar conditions apply to your environment).

Mark S. Miller

unread,
May 20, 2020, 1:55:03 AM5/20/20
to cap-...@googlegroups.com
That's exactly the opposite of my point. Bob is only the decider when he is the only one that has the power to decide. If multiple parties have the power to decide, then none individually is the decider.

Within a vat, when Alice eventual-sends foo() to Bob, Bob is the decider. Alice does not have the power to decide the resolution of the promise she got back from doing the eventual send.

In some ways it is better to see it in a time reversed manner. The promise/resolver pair Bob makes is the "real" one. The one Alice is holding the the result of sending the promise part backwards in time to Alice, so the promise Alice holds is forwarded to the promise Bob returned. But holds the only non-used-up resolver in the story, and the only one observable from user code.

The questions/answers table is the bookkeeping to do this backwards-in-time passing of the promise from VatB to VatA. VatA on sending the message knows that VatB, on receiving it, will create a promise/resolver pair. What would happen if VatB would send the promise part to VatA? Whatever bookkeeping that is, just set it up ahead of time.

Again, that's why we don't make any special case for passing a resolver as argument. The receiver just received a remote reference to the resolver, with no reason to believe that it holds it exclusively. It may be in a race to resolve the resolver. It is not the decider.


> Now let's revisit with Alice in VatA and Bob in VatB. To Alice, the local
> proxy for bob is the decider. To VatA, VatB is the decider. To VatB, Bob is
> the decider.
>
> When Alice then does one of
>
> p~.bar()
> E(p).bar()  // no sugar
> p <- bar()  // E
>
> where should the message go? After all, we don't know where the object is
> that p will designate. It might even be on VatA. However, the unambiguously
> best answer is "send it to the decider". The steps by which it will come to
> be determined where that object is starts with the decision made by the
> decider. Therefore, if bar() needs to be routed elsewhere, that will be
> known at the decider before it is known anywhere else.

I'm actually not too concerned from the perspective of Alice at the
moment.  Let's say that, in theory, something goofy happened... Vat A
actually sent messages to two different vats.  Bob on Vat B and Carol on
Vat C are now both "the decider" and are ready to do something under the
assumption that they're the ones who resolve that promise.

That situation is not possible under captp with question/answer tables --- for the promises for the results of a send, which are the ones that support pipelining.
 
--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87367w19kb.fsf%40dustycloud.org.

Ian Denhardt

unread,
May 20, 2020, 2:24:57 AM5/20/20
to Christopher Lemmer Webber, cap-...@googlegroups.com
Quoting Christopher Lemmer Webber (2020-05-19 10:16:03)

> That's actually almost entirely what I'm thinking, if I understand you
> correctly. The key thing there is pre-allocating promise-resolver pairs
> *for* the intermediate anticipated results in the promise pipelining.
>
> Assuming I understand you, maybe that means we came to the same
> conclusion, which makes me very optimistic.

If you say that's what you meant I'll take your word for it ;)

What confused me about the way you described is this notion of "passing
in a resolver," which I interpreted as being very different to what I
described above; it sounds like a first-class continuation, which raises
issues discussed elsewhere about what happens if you pass a resolver to
multiple parties?

Whereas the above doesn't do any kind of reification like that, and
doesn't fundamentally change the abstraction, It just removes some
arguably redundant structures in the plumbing of the protocol. I don't
think getting rid of Q & A tables is necessarily that interesting on
its own -- you just have to replace it with another scheme for
allocating IDs -- but it seems like collapsing Return & Resolve and
Finish & Release as well is what makes it a win.

-Ian

Christopher Lemmer Webber

unread,
May 20, 2020, 12:31:22 PM5/20/20
to cap-...@googlegroups.com
Mark S. Miller writes:

> The questions/answers table is the bookkeeping to do this backwards-in-time
> passing of the promise from VatB to VatA. VatA on sending the message knows
> that VatB, on receiving it, will create a promise/resolver pair. What would
> happen if VatB would send the promise part to VatA? Whatever bookkeeping
> that is, just set it up ahead of time.
>
> Again, that's why we don't make any special case for passing a resolver as
> argument. The receiver just received a remote reference to the resolver,
> with no reason to believe that it holds it exclusively. It may be in a race
> to resolve the resolver. It is not the decider.

Let's see if I understand what you're saying here by repeating it back
in my own words, and find out how wrong they are. :)

"In a first class promise-resolver pair, it is possible that multiple
entities may have access to the resolver, and the first one "wins".
But for promise pipelining, we need a stronger understanding: even
though we *could* just point to an arbitrary resolver, when something
is sent over in the questions/answers tables, it's an indication from
the other side that the vat responsible for answering is the one and
only decider. If we instead just pointed at an arbitrary exported
resolver, we aren't making as strong of a commitment... and promise
pipelining really needs that kind of commitment to work."

How far away is this from your thinking?

>> > Now let's revisit with Alice in VatA and Bob in VatB. To Alice, the local
>> > proxy for bob is the decider. To VatA, VatB is the decider. To VatB, Bob is
>> > the decider.
>> >
>> > When Alice then does one of
>> >
>> > p~.bar()
>> > E(p).bar() // no sugar
>> > p <- bar() // E
>> >
>> > where should the message go? After all, we don't know where the object is
>> > that p will designate. It might even be on VatA. However, the
>> unambiguously
>> > best answer is "send it to the decider". The steps by which it will come
>> to
>> > be determined where that object is starts with the decision made by the
>> > decider. Therefore, if bar() needs to be routed elsewhere, that will be
>> > known at the decider before it is known anywhere else.
>>
>> I'm actually not too concerned from the perspective of Alice at the
>> moment. Let's say that, in theory, something goofy happened... Vat A
>> actually sent messages to two different vats. Bob on Vat B and Carol on
>> Vat C are now both "the decider" and are ready to do something under the
>> assumption that they're the ones who resolve that promise.
>>
>
> That situation is not possible under captp with question/answer tables ---
> for the promises for the results of a send, which are the ones that support
> pipelining.

And this is because those promises are only produced in captp-land, not
in a first class object way?

Christopher Lemmer Webber

unread,
May 20, 2020, 12:50:54 PM5/20/20
to cap-...@googlegroups.com
Kevin Reid writes:

> On Tue, May 19, 2020 at 9:24 AM Christopher Lemmer Webber <
> cwe...@dustycloud.org> wrote:
>
>> The main thing I'm unsure of (which surprisingly nobody commented on!)
>> is whether or not the imports/exports tables live on the Machine layer
>> or on the Vat layer. We'll see via implementation, I guess... I see
>> advantages to both.
>
> They were per vat, in E. That way, the same-machine-different-vat case is
> equivalent to the different-machine-different-vat case and does not need
> any special handling.
>
> In principle, if you have a special case for vats that live in the same
> address space, you can avoid needing to *serialize into a byte stream* the
> data that crosses a vat boundary — but you still have to copy/proxy it
> according to the serialization rules (in E, Data-E as configured by CapTP)
> unless it consists of objects known to the implementation to be
> immutable-and-thread-safe (or whatever similar conditions apply to your
> environment).

So, in Goblins *currently*, live-refs contain the information on how to
connect to them.

(struct live-refr refr ; the struct live-refr, which extends refr
(debug-name vat-connector)) ; contains a debug name, and a "vat-connector"

*Currently*, with messages sent between vats on the same machine,
messages are *not* serialized/deserialized. However, between machines,
they will need to be. I do have plans to install an option for a vat to
guard messages sent to/from itself to being only of certain known-safe
types but haven't done it yet.

In general the assumption is the following (and maybe it isn't a good
one, I don't know):

- One might spawn a lot of locally communicating event loops on a local
machine
- Serializing/deserializing is expensive
- live-refrs, using the structure described above, have a "vat
connector" which specifies "how to reach this vat". If they're on
the same machine, we don't even need to do full captp between
machine-local vats.
- A guard could be sufficient for a vat to decide whether or not it
requires a predicate check at its border for a whitelist of types.

So this resembles the "special case" you described above, but is even
looser.

Now between machines, obviously this is not the case. We will
absolutely need to implement captp at the machine boundary.

So the question seems to indeed be open under present architecture about
whether or not import/export (and maybe question/answer) tables should
be at the vat level or at the machine level. There may be other
complications that make it not a good idea, however. Off the top of my
head...

Possible pros to tables at machine level:
- You can handle imports/exports and resolve remote promises once for
all vats on the same machine
- Preserves same-machine vat message sending optimization without
serialization

Possible pros to tables at vat level:
- Easier to serialize "everything you need to know" for this vat to
come back within a snapshot of the vat's single actormap, whereas
on the machine level it requires also snapshotting a segment of
the machine's tables.
- Replay of messages sent to a vat thus may also be easier.
- It's what everyone else appears to have done so far and if all
the ocap cool kids have jumped off this cliff it's probably
because they know it's safe landings so if I have to jump off
a cliff anyway maybe I should jump off this one too

Ian Denhardt

unread,
May 20, 2020, 3:01:17 PM5/20/20
to Christopher Lemmer Webber, cap-...@googlegroups.com
Quoting Christopher Lemmer Webber (2020-05-20 12:50:53)

> So the question seems to indeed be open under present architecture about
> whether or not import/export (and maybe question/answer) tables should
> be at the vat level or at the machine level. There may be other
> complications that make it not a good idea, however. Off the top of my
> head...
>
> Possible pros to tables at machine level:
> - You can handle imports/exports and resolve remote promises once for
> all vats on the same machine
> - Preserves same-machine vat message sending optimization without
> serialization
>
> Possible pros to tables at vat level:
> - Easier to serialize "everything you need to know" for this vat to
> come back within a snapshot of the vat's single actormap, whereas
> on the machine level it requires also snapshotting a segment of
> the machine's tables.
> - Replay of messages sent to a vat thus may also be easier.
> - It's what everyone else appears to have done so far and if all
> the ocap cool kids have jumped off this cliff it's probably
> because they know it's safe landings so if I have to jump off
> a cliff anyway maybe I should jump off this one too

Perhaps this doesn't apply to goblins since you've already picked a
one-event-loop-per-vat architecture, but it's worth noting that this
isn't necessarily a requirement.

Rather, I think the choice of Vat == Event loop is an artifact of an
answer to the question of "how do I do concurrency in this language?"
The languages that I've seen use an event loop per vat are also
languages where you'll see event loops used as the way to write server
software *in general*.

By contrast, in general Go, Haskell, and Erlang all favor a
green-threading approach with message passing (and STM in the case of
Haskell). All three of these also have capnproto rpc implementations
that map a thread to an *actor*, i.e. *each object* is it's own separate
thread, rather than having an event loop per vat.

In this context it's not clear to me that vats and machines are
meaningfully different things -- the tables are fundamentally an
artifact of a *connection*, and in the green thread model as far as I
can see this distinction between vat and machine doesn't really make a
ton of sense.

Food for thought.

-Ian

Christopher Lemmer Webber

unread,
May 20, 2020, 4:04:32 PM5/20/20
to cap-...@googlegroups.com
Very relevant mid-day shower revelations, highly worth the cost of
zoning out and paying extra on relevant wasted hot water utilities.

OK! I'm just going to outline everything here before I forget it. This
may be incoherent nonsense to anyone who isn't me, stepping straight out
of a shower. Hopefully at minimum future me understands.


There's no reason to make a separate event loop for the machine, you doof
=========================================================================

Previously I was writing the machine as a separate event loop.
Well why the heck was I doing that? Just make a special "machine vat".
Hm... sounds a lot like the Agoric "comms vat", yes...


Drivers and a special "comms vat" pave the way for machine-level imports/exports
================================================================================

Earlier I said these foolish things:

> - Easier to serialize "everything you need to know" for this vat to
> come back within a snapshot of the vat's single actormap, whereas
> on the machine level it requires also snapshotting a segment of
> the machine's tables.
> - Replay of messages sent to a vat thus may also be easier.

WRONG! The answer is clearly understood for the same reason that we
don't need to serialize the state of files in order to replay what
information we got historically about their state when we read from
them.

Okay, I'll admit that I don't fully understand Agoric's comms vat and
drivers, but this seems right. Let's say that we replace "comms vat"
with "machine vat"... this is a special vat that both takes care of
inter-machine communication and also driver stuff. If we are worried
about "what's the resolution of this remote promise" but there's one vat
that's in charge of handling all that with a special actor in that vat
that all other vats have access to, this can be in charge of all the
mapping of captp stuff to the local actor addresses. This also nicely
solves my desiderata that on the same machine that we have to do no
serialization/deserialization between vats (see my previous message
about this not excluding guards for security concerns), which I think is
a big performance win and a great simplification of things. It's one of
the things I really like about Goblins right now.


Oh, drivers aren't as hard as I thought
=======================================

I had a hard time wrapping my brain around "how do I implement drivers?"
I mean, I understood why they were a good idea but how to do them?

- When booting the "machine vat", it returns a capability with some
low-level control methods. One of these is the "install driver"
method, which... wait...

- Okay I'm rethinking this as I type it. There's no need to treat
drivers as a special case at all, is there? In fact there's no need
for them to specifically be on the comms/machine vat, it's just a
convenient convention to put them all in one place. Any object in
any vat can technically serve the role of a driver if it uses the
mechanism I'm about to outline?

- Drivers are just conceptually two-faceted objects: half are what
other objects use to talk to the driver, and half are what the driver
uses to talk to the special resource (filesystem, file, audio system,
image system, etc).

- Goblins is an actor model system built *on top of* CSP. This means
it's easy to spawn a separate "thread" to which we have a channel.
So the part that talks to the special resource is just a normal
thread to which:
- The driver actor has access to a channel which talks to that
special-resource-thread and sends instructions such as "read 50
bytes"
- The special-resource-thread then sends messages back to the driver
actor (or a facet of it) using the vat message-bootstrapping
mechanism.

- Probably the comms vat convention is still important in
serializing/deserializing the system in terms of entry/exit points?


Spawn your vats from your machine???
====================================

Very Goblins specific musing?

The procedure to spawn vats could be not exported and be more low-level.
Instead, a procedure to spawn machines is exported which uses that and
spawns the machine vat, from which a capability to spawn further vats is
granted. Both could use the more low-level vat-spawning procedure.

What's the advantage of this? There's at least one, which is that it
gets rid of the current-machine parameter, which isn't exported but
every parameter/fluid I add bothers me.


What the heck is the role of the machine?
=========================================

Goblins managed to implement communication across multiple vats within
the same OS process just fine without a machine abstraction or even
CapTP. The reason for this is that the host environment did a lot for
us:

- It has a garbage collector and weakmaps, and thus unused objects
within the process could be collected.
- It has a CSP mechanism on which implementing a vat is relatively
easy.
- Actor references carried with them a "vat-connector" attribute. If
you were looking at another reference and it had the same (via
scheme's eq?) vat connector as you, why, it must be near! If not,
it must be far, but the underlying Goblins abstractions could use the
vat connector to negotiate contact with it.
- Thus there was no need to create proxies for objects in the same OS
process.
- Promise resolution thus didn't need any special proxies either.
If the other vat is still running and remembers that it has resolved
its promise you can still get that information.

Life was good, society flourished, space shooters were written, and the
primary author looked upon the design and thought that it was good.

But the Distributed Desiderata loomed large, and change needed to come.
The world of a single OS process was no longer satisfactory. When
networks, inter-dimensional communication portals, and even other OS
processes on the same physical computer are introduced, our host
environment is no longer sufficiently simple and safe to solve all our
needs. And in order to facilitate the collapsing of boundaries, we open
a new one, the machine, which needs to solve:

- Routing to those other machines and knowing our messages are getting
there safely
- Other machines having their own garbage collectors
- Other machines having their own objects, and how to map to them and
agree what we're talking about
- How to bootstrap talking to objects on those other machines...
further introductions are only possible starting from initial
connections after all...
- How to serialize and deserialize our messages when sending them
across the wire so we can talk about the same things
- Blah blah promise pipelining blah blah

If VatTP covers the first bullet point, should CapTP live on the machine
layer or the vat layer? Given everything the host system already
provided in the first list with no captp between vats, it seems like the
machine layer could really handle this full second list. And so I
wonder if that indicates that the import/export table really belongs on
the machine, not on the vats.

- Chris

Mark S. Miller

unread,
May 20, 2020, 4:09:36 PM5/20/20
to cap-...@googlegroups.com
On Wed, May 20, 2020 at 9:31 AM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:
Mark S. Miller writes:

> The questions/answers table is the bookkeeping to do this backwards-in-time
> passing of the promise from VatB to VatA. VatA on sending the message knows
> that VatB, on receiving it, will create a promise/resolver pair. What would
> happen if VatB would send the promise part to VatA? Whatever bookkeeping
> that is, just set it up ahead of time.
>
> Again, that's why we don't make any special case for passing a resolver as
> argument. The receiver just received a remote reference to the resolver,
> with no reason to believe that it holds it exclusively. It may be in a race
> to resolve the resolver. It is not the decider.

Let's see if I understand what you're saying here by repeating it back
in my own words, and find out how wrong they are. :)

  "In a first class promise-resolver pair, it is possible that multiple
  entities may have access to the resolver, and the first one "wins".
  But for promise pipelining, we need a stronger understanding: even
  though we *could* just point to an arbitrary resolver, when something
  is sent over in the questions/answers tables, it's an indication from
  the other side that the vat responsible for answering is the one and
  only decider.  If we instead just pointed at an arbitrary exported
  resolver, we aren't making as strong of a commitment... and promise
  pipelining really needs that kind of commitment to work."

How far away is this from your thinking?

You got it in one ;)


 
--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

Mark S. Miller

unread,
May 20, 2020, 4:15:15 PM5/20/20
to cap-...@googlegroups.com
Yes. Only captp makes the promises captp recognizes as remote promises. The captp implementation alone holds the resolver for these promises. The VatA's captp implementation gives only VatB the power to resolve that promise. VatA's captp implementation also has sides facing other objects in VatA, like Alice. captp gives none of them that authority.

To code that views captp as just part of the distributed object system, the resolver of that remote promise is indeed held exclusively by Bob.
 

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

Mark S. Miller

unread,
May 20, 2020, 4:30:06 PM5/20/20
to cap-...@googlegroups.com, Christopher Lemmer Webber
As co-coiner of "vat", a vat is a unit of synchrony in a sea of asynchrony. There is no semantic concurrency inside a vat. Vats are only asynchronous coupled to each other.

An example of non-vat, demonstrating that this definition has teeth:

JavaScript used to be objects in separate synchronous event loops (now "agents") sending asynchronous messages to each other (postMessage, HTTP POST, ...). However, with the addition of "Shared Array Buffer" (SAB) to modern JS, there are no vats in modern full JS language. SABs allow event loops within the same "agent cluster" to synchronously couple to each other. Agent clusters, OTOH, are still only asynchronously coupled to each other. Perhaps an agent cluster is a vat? No, because an agent cluster has internal concurrency.

JS/SES as used by Agoric does have vats, of course.

Btw, I ***hate*** the "agent" and "agent cluster" terminology. But in picking my battles, I didn't pick this one. I discourage its use outside tc39. We need better terminology. But they're not vats!




--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

Ian Denhardt

unread,
May 20, 2020, 4:57:16 PM5/20/20
to Mark S. Miller, cap-...@googlegroups.com, Christopher Lemmer Webber
Quoting Mark S. Miller (2020-05-20 16:29:53)
> As co-coiner of "vat", a vat is a unit of synchrony in a sea of
> asynchrony. There is no semantic concurrency inside a vat. Vats are
> only asynchronous� coupled to each other.
> An example of non-vat, demonstrating that this definition has teeth:
> JavaScript used to be objects in separate synchronous� event loops (now
> "agents") sending asynchronous messages to each other (postMessage,
> HTTP POST, ...). However, with the addition of "Shared Array Buffer"
> (SAB) to modern JS, there are no vats in modern full JS language. SABs
> allow event loops within the same "agent cluster" to
> synchronously� couple to each other. Agent clusters, OTOH, are still
> only asynchronously coupled to each other. Perhaps an agent cluster is
> a vat? No, because an agent cluster has internal concurrency.
> JS/SES as used by Agoric does have vats, of course.
> Btw, I ***hate*** the "agent" and "agent cluster" terminology. But in
> picking my battles, I didn't pick this one. I discourage its use
> outside tc39. We need better terminology. But they're not vats!

Would it be fair then to say that the notion of a vat is entirely
orthogonal to CapTP? It seems like the protocol doesn't really care
about vats in this sense, as the concurrency (or lack thereof) within a
network peer is irrelevant to the protocol's operation (as long as
E-order is respected).

-Ian

Alan Karp

unread,
May 20, 2020, 5:25:19 PM5/20/20
to cap-...@googlegroups.com
Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:

 - Drivers are just conceptually two-faceted objects: half are what
   other objects use to talk to the driver, and half are what the driver
   uses to talk to the special resource (filesystem, file, audio system,
   image system, etc).

This statement revived memories of work I did with Terence Kelly on Tyler's waterken protocol. (https://www.hpl.hp.com/techreports/2010/HPL-2010-155.pdf)

You need to consider the failure model.  Are you using the E model for messages or the waterken model?  E sends messages as soon as they are ready; waterken only sends them at the end of a turn after they have been persisted.  The difference is how you recover from a failure that happens in the middle of a turn.  In waterken, the vat restarts from its most recent checkpoint, resending any unacknowledged messages.  Recovery is harder with the E model.

Waterken automatically ignores a message received more than once, but you can't do that with devices unless the operations are idempotent.  While you can turn many non-idempotent messages into idempotent ones, e.g., change "launch rocket" to "launch rocket #4," there are many you cannot, such as printing on paper.  In your case, I think anything the user sees cannot be considered idempotent.

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

Mark S. Miller

unread,
May 20, 2020, 6:12:40 PM5/20/20
to Ian Denhardt, cap-...@googlegroups.com, Christopher Lemmer Webber
I'll accept "largely orthogonal" but not "entirely orthogonal". Nevertheless, I think we are agreeing.

 

-Ian

Christopher Lemmer Webber

unread,
May 20, 2020, 8:00:41 PM5/20/20
to cap-...@googlegroups.com
I see (I think)... thank you for clarifying. :)

Christopher Lemmer Webber

unread,
May 20, 2020, 8:07:30 PM5/20/20
to cap-...@googlegroups.com
Alan Karp writes:

> Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:
>
>>
> - Drivers are just conceptually two-faceted objects: half are what
> other objects use to talk to the driver, and half are what the driver
> uses to talk to the special resource (filesystem, file, audio system,
> image system, etc).
>
>
> This statement revived memories of work I did with Terence Kelly on Tyler's
> waterken protocol. (https://www.hpl.hp.com/techreports/2010/HPL-2010-155.pdf
> )

Thank you... I've somehow never actually read this paper. Printed to
read later.

> You need to consider the failure model. Are you using the E model for
> messages or the waterken model? E sends messages as soon as they are
> ready; waterken only sends them at the end of a turn after they have been
> persisted. The difference is how you recover from a failure that happens
> in the middle of a turn. In waterken, the vat restarts from its most
> recent checkpoint, resending any unacknowledged messages. Recovery is
> harder with the E model.

I did not realize that E sends them ASAP. Goblins also only sends
messages at the end of a turn... actually, it does now, though in the
first iteration it did not; the purpose of this change was to improve
transactionality and replayability. I feel like I was thinking in the
right direction then.

I would have figured E would have also done them end-of-turn, since that
seems like the cleanest way to work out the logistics of promise
pipelining? So this seems surprising to me. Is E only
opportunistically promise pipelined? I must be missing something.

> Waterken automatically ignores a message received more than once, but you
> can't do that with devices unless the operations are idempotent. While you
> can turn many non-idempotent messages into idempotent ones, e.g., change
> "launch rocket" to "launch rocket #4," there are many you cannot, such as
> printing on paper. In your case, I think anything the user sees cannot be
> considered idempotent.

I think that's right but is something I haven't thought about
sufficiently... I will try to lend it more braincells. Thanks for your
useful comments.

Mark S. Miller

unread,
May 20, 2020, 8:13:11 PM5/20/20
to cap-...@googlegroups.com