Proposal: GetExclusive operator

[danfinlay]

I’ve been entertaining an ongoing debate recently about whether distributed, async programming can be more easily safe and secure than traditional synchronous environments.

This has implications for blockchains like Ethereum, which are popularizing the idea of avoiding async operations, and also for secure distributed JavaScript in general, which through promises, eventual-sends, and promise pipelining makes it easier than ever to integrate complex asynchronous logic into some code.

I’d like to suggest that there may be a single pattern that is the most dangerous for async programming, and it the notion of un-locked memory access. You can see this in things like Mark Miller’s dislike of async/await, and the general aversion to distributed programming.

I was trying to imagine how to make it as easy as possible to integrate these ideas at the language level, and even with promise pipelining it seems like a system would still be vulnerable to this kind of problem, so I don’t think it’s exclusively a problem with await, it instead has to do with how hard it is to reason about exclusive rights to memory access.

For this reason, I think there may be room for a new operator, one equivalent to ~. (eventual send), but one that represents getting an exclusive right to that object. The object would also need some mechanism for releasing this exclusive right, and so it would be like building mutexes into the language.

Let’s say we choose a new operator that is similar to ~., I’ll just use $. for example here, I have no idea if this is taken or not. In this case, code like this would be safe:

const trainTicketRight = trainStation$.getTicket()
const hotelTicketRight = hotel$.getRoom()

if (trainTicketRight.price + hotelTicketRight.price < myBudget) {
    trainTicketRight.purchase()
    hotelTicketRight.purchase()
} else {
  trainTicketRight.release()
  hotelTicketRight.release()
}

I’m not certain there’s a benefit to this being at the language level: It’s possible having ~.getExclusive() methods would be sufficient, since the host of the methods would be responsible for enforcing the exclusivity anyways, this may merely be syntactic sugar, but by integrating the notion of a mutex directly into the language, I was exploring whether it might be easier for a developer to reason about writing secure code, and so wanted to capture the idea somewhere, and this seemed like a good place.

[kate_sills]

Just want to say that the Kialo link is amazing! Thanks for organizing that!

[kate_sills]

I’d like to suggest that there may be a single pattern that is the most dangerous for async programming, and it the notion of un-locked memory access. You can see this in things like Mark Miller’s dislike of async/await , and the general aversion to distributed programming.

If you have a single thread, and the event loop is pulling messages off the queue, then that code is guaranteed to have the only live access to the heap, right? So it seems like there’s already an amount of locking. As I understand it, Mark’s aversion to async/await is that it can hide what should be a very clear indication of a turn boundary. It should signal that “this is the place where other code might be executed” but to the eye, it looks like normal code, so that’s an error-prone design.

I was trying to imagine how to make it as easy as possible to integrate these ideas at the language level, and even with promise pipelining it seems like a system would still be vulnerable to this kind of problem, so I don’t think it’s exclusively a problem with await , it instead has to do with how hard it is to reason about exclusive rights to memory access.

Is it memory access you want? Or is it exclusive access to digital assets? If it’s the latter, then ERTP does that well! If you call const newPayment = assay.claimAll(payment) and it succeeds, you have exclusive access because you have the only reference to the new payment that exists outside of the mint.

Thanks for the train/hotel example! You could use an option (the exclusive right to buy something by an expiration date) for both the train ticket and the hotel room. In Zoe, making an option for a train ticket looks like :

    const coveredCallInvite = await zoe.makeInstance(
      coveredCallInstallationHandle,
      terms: { assays: [trainTicketAssay, dollarAssay]
    );
    const offerRules = harden({
      payoutRules: [
        {
          kind: 'offerAtMost',
          units: trainTicket('B123GE'), // whatever the identifier is
        },
        {
          kind: 'wantAtLeast',
          units: dollars(25),
        },
      ],
      exitRule: {
        kind: 'afterDeadline',
        deadline: 100, 
        timer,
      },
    });
    const payments = [trainTicketPayment, undefined];
    const { seat, payout } = await zoe.redeem(
      coveredCallInvite,
      offerRules,
      payments,
    );
    const option = await seat.makeCallOption();
    return option;

Then once you have the options, you can exercise them knowing that they will remain valid until the expiration date. No chances of exercising one of the options and having the other fail!

I haven’t thought much about a language primitive for this, though. How do you think it would work?

[michaelfig]

I’m intrigued by what you’re proposing, but I think we need to stick with a different primitive than a mutex. Mainly because mutexes are hard to reason about, and make it easy to cause deadlocks. Especially across networks.

Using the “vat” model (islands of synchronous operation connected by asynchronous messaging), the natural ocap way to solve these kinds of problems is to encode all the things we need to do synchronously in a single method call (or with something like @markm’s Promise.prototype.there which could allow for the remote evaluation of a simple Javascript expression).

Once we buy in that synchronous processing is done in the context of a vat (i.e. it’s as if there’s a global mutex that is held when the vat is executing), it makes it possible to encapsulate coordinated interactions without the need for further locking.

As @kate_sills described, there is still a need on the ERTP layer to be able to explicitly transfer erights, rather than just share references between them, but this is a different concern than locking (getting exclusive rights under ERTP is a nonblocking async operation that creates a fresh reference to an eright and severs any other references to that eright).

So, would you be able to maybe use a different example than a transfer of erights to illustrate why a mutex is useful? If not, maybe you are wanting to explore ERTP further?

[danfinlay]

the natural ocap way to solve these kinds of problems is to encode all the things we need to do synchronously in a single method call (or with something like @markm’s Promise.prototype.there which could allow for the remote evaluation of a simple Javascript expression).

I’m not sure this solves multi-vat (>=3) synchronity problems: Even with .there() or doThisAndThat() methods, if you need to coordinate two remote functions based on two remote pieces of data, I’m pretty sure only a type of a lock can achieve safety.

I agree that ERTP solves this problem by way of a JS framework, and I’m just saying that exclusive right to memory is even more fundamental than anyone framework: Many situations may involve this. I’m not sure I can separate the reason from the definition of “e-right”, because that definition is probably fairly encompassing, but here is an instance of a mutex that I think would benefit from the same language, where it simplifies the usage of a mutex:

In MetaMask, multiple websites may want to send an Ethereum transaction at once, and all transactions receive a unique incremented nonce to enforce replay protection. Getting the next valid nonce depends on a transaction queue which can be incremented by other instances of the wallet, and so checking the nonce is an async operation.

This means reading the current nonce needs a notion of a lock, where one wallet can get a copy of its current value with the guarantee that it is not being changed.

const nonce = await wallet$.latestNonce
const next = nonce + 1
sendTransaction({ ...opts, nonce })
nonce.release()

This nonce doesn’t feel like a “right” maybe, since it isn’t a ticket you use, and a user may never think about it, but to a programmer, it’s an order-critical piece of information, and like an e-right, it is sometimes important to have a unique access to.

So I guess my point is just that ERTP is great, and solves this for the blockchain use case, but the notion of exclusive memory rights is so fundamental to strong async programming that it maybe deserves even deeper language integration.

Again, I’m not sure this is the case, because I don’t know how the language can ever enforce what a remote agent is doing, but in terms of ergonomics, I like how it makes the exclusivity explicit at a very basic level, and easy to reason about without having specialized methods for every piece of data.

I totally agree this can also just be solved at the library level though, like ERTP does.

[kate_sills]

The nonce example is a great concise example. Thanks for sharing that!

Just so I understand - you’re talking about the account nonce in Ethereum?
And you want the transactions to 1) never use the same nonce, and 2) be ordered by nonce?

I’m probably just not understanding something, but it seems weird to me that latestNonce and sentTransaction are two steps. If your transactions must get a nonce and they must be sent in a certain order, wouldn’t you want to make sendTransaction asynchronous and get the nonce as needed inside sendTransaction?

To put things another way, it seems like you need a single queue for transactions rather than multiple queues, and the process of sending transactions should get the latest nonce. I must be missing something important, though.

[danfinlay]

To put things another way, it seems like you need a single queue for transactions rather than multiple queues, and the process of sending transactions should get the latest nonce. I must be missing something important, though.

Yeah, you’re right, but if we did this inside sendTransaction the same problem would exist (for multiple-wallet examples, where either wallet can add to the queue, but they want to coordinate over who will add next).

There are other examples, too, I think any mutex-requiring example could work:

Let’s say we both have files representing calendars on our computers. We want to automatically coordinate a time to meet, but we’re both very busy, so we want a program to arrange our meeting time. A script would want to get a list of available times from each of us, and then reserve a time on each of our calendars, but it wants to know that the available times it is looking at is not going to be updated for one of us while writing to the other’s calendar.

I feel like I’m arguing for mutexes, which should be of obvious benefit. I guess the real question I have is “would a language-level expression of a mutex make it easier for developers to reason about asynchronous side-effects?”

As I understand it, Mark’s aversion to async/await is that it can hide what should be a very clear indication of a turn boundary. It should signal that “this is the place where other code might be executed” but to the eye, it looks like normal code, so that’s an error-prone design.

Just to zoom in on this point: I think the reason that a event-loop turn is dangerous is exactly because the information you’re operating on can change out from under you, and so I do think this is addressing the same concern, just in a different way. Even eventual-sends with pipelining seems to leave open the question of how to establish a synchronous link between two remote async operations, for which I think only a type of lock can really solve. Even the ERTP solution is an API wrapping a sort of lock, so I’m just suggesting some syntactic sugar to make that kind of flow even more terse and ergonomic.

[kate_sills]

but if we did this inside sendTransaction the same problem would exist (for multiple-wallet examples, where either wallet can add to the queue, but they want to coordinate over who will add next).

Hmm, it seems like whatever code or service has the centralized power to grant a mutex would also have the power to coordinate the transaction order. I could understand the issue if all of the wallets were getting their own version of latestNonce independently, but if they are already going to some central source for that knowledge, couldn’t that central source do the coordination?

Let’s say we both have files representing calendars on our computers. We want to automatically coordinate a time to meet, but we’re both very busy, so we want a program to arrange our meeting time. A script would want to get a list of available times from each of us, and then reserve a time on each of our calendars, but it wants to know that the available times it is looking at is not going to be updated for one of us while writing to the other’s calendar.

I think this example could be (should be?) solved by options. Having the exclusive right to reserve time on someone’s calendar is costly, so it makes sense to me that you’d pay some small amount for that right. Then once the coordinating service has collected options that work together, they could go ahead and actually reserve the time.

I feel like I’m arguing for mutexes, which should be of obvious benefit.

The benefit in these particular examples isn’t obvious to me Is it ok if we explore other options too? I want to try to better understand the pros and cons.

[kate_sills]

@markm is the expert here of course, but if I’m reading his thesis right, I think he recommends communicating event loops as opposed to any kind of shared-state concurrency:

http://www.erights.org/talks/thesis/markm-thesis.pdf

[michaelfig]

@danfinlay regardless of the environment, somebody (such as an agent on the blockchain) has to act as a trusted third party if you want synchronous anything. With a mutex, the agent who claims a lock is acting as the trusted party, but the problem is that there is no guarantee that they are intended to be trusted.

I’ve found that a good way to do locking in an ocap style is to return a Promise that doesn’t resolve until a previous caller has released the lock. This isn’t exactly a mutex, but has a queue for fairness (as semaphores do).

const [nonce, releaseNonce] = await wallet.getLatestNonce()
sendTransaction({ ...opts, nonce })
releaseNonce()

The problem then is (as with mutexes) the caller may delay the release indefinitely. Not sure you’re concerned about that.

The brilliance of ERTP, and the reason it’s useful in these kinds of situations is that it partitions the trust so that for an agent to claim exclusive access, they need to hold ocaps for both the assay as well as the eright itself.

Train-hotel can be done with ERTP not on the blockchain, too.

calendars: Let’s explore this more. I would suggest that a transaction model would be most beneficial. The beauty of transactions is that they can atomically swap/update things without deadlock. The reason I mentioned .there() was to suggest that the script could send some code to each of the participants to block a date during a distributed transaction protocol. If you want to make an abstraction over the specific protocol to coordinate the script’s effects, that would take some work, but would not need to expose such a low-level thing as a mutex.

I could imagine some ocap service that would be useful in coordinating kinds of agreed-upon transactions between mutually-untrusting parties other than erights transfers. This would be like manually electing a coordinator and choosing an ocap to serve as a cohort for a distributed transaction protocol.

@kate_sills I’m curious about your thoughts on this, and if/how ERTP and Zoe could be applied to the task.

[kate_sills]

I’m thinking that reserving space on a calendar is really an economic exchange (could be for free, still). Let’s say your calendar is divided into 15 min segments. The segments can have 3 (?) states: claimed, open, and reserved. To schedule a new appointment with someone, you would see which of their open segments would work for you, try to reserve them (i.e. buy an option for each segment, potentially for free), and then of the successfully reserved ones, see which you like best and actually claim them. It’s easy to represent segments of a calendar as ERTP digital assets, and the options are easily created with boilerplate contracts too, so I think this is all pretty easy to do. It should solve all of the problems of trying to grab a spot on someone’s calendar to find that they have already given it someone else.