New paper: "Distributed Electronic Rights in JavaScript"
On Mon, Jan 14, 2013 at 5:46 PM, Mark S. Miller <erights at google.com> wrote:
At code.google.com/p/es-lab/downloads/detail?name=distr-erights-in-js.pdf
Paper for invited talk at ESOP2013 www.etaps.org/2013/esop13 Final already submitted, but comments of course appreciated anyway.
Given that the first word of your abstract is "Contracts", it's surprising to me that you don't reference any of the quite extensive literature on software contracts, starting with Bertrand Meyer in the 80s, and continuing with Findler and Felleisen's work on higher-order contracts over the past 10+ years, which has even been implemented for JS by Tim Disney using proxies [1].
Sam
A fair point. By "contracts" in that first word, we refer to real-world contracts. For software "contracts", we initially had a footnote trying to explain the relationship between the "smart contracts" we're talking about and the type-like "contracts" that this literature refers to. Perhaps unwisely, I removed it because I thought it created more confusion than it cleared up. By introducing "the exchange of rights" in that same first sentence I hope we make it clear that we're talking about a different kind of contract, one closer to the real world notion.
I'll see if I can find the footnote I deleted, at least for the record here on es-discuss ;).
On Mon, Jan 14, 2013 at 6:05 PM, Mark S. Miller <erights at google.com> wrote:
A fair point. By "contracts" in that first word, we refer to real-world contracts. For software "contracts", we initially had a footnote trying to explain the relationship between the "smart contracts" we're talking about and the type-like "contracts" that this literature refers to. Perhaps unwisely, I removed it because I thought it created more confusion than it cleared up. By introducing "the exchange of rights" in that same first sentence I hope we make it clear that we're talking about a different kind of contract, one closer to the real world notion.
I disagree, in two senses. First, behavioral software contracts in the sense of Meyer have a close analogy to real-world contracts, in particular contracts for the exchange of goods. For example, a spot contract is just an agreement to exchange some good meeting some specified description for another (usually one is money). Second, I believe that your escrow contracts are closely related to software contracts, in the sense that we could formulate them as software contracts in a sufficiently-expressive contract system, where the contract/runtime system itself plays the role of trusted host.
On Mon, Jan 14, 2013 at 3:05 PM, Mark S. Miller <erights at google.com> wrote:
A fair point. By "contracts" in that first word, we refer to real-world contracts. For software "contracts", we initially had a footnote trying to explain the relationship between the "smart contracts" we're talking about and the type-like "contracts" that this literature refers to. Perhaps unwisely, I removed it because I thought it created more confusion than it cleared up. By introducing "the exchange of rights" in that same first sentence I hope we make it clear that we're talking about a different kind of contract, one closer to the real world notion.
I'll see if I can find the footnote I deleted, at least for the record here on es-discuss ;).
The footnote I (again, perhaps unwisely) deleted is:
Although types as contracts [2] and higher order contracts [3] can be seen as very special cases of smart contracts, their purpose is typically di erent: locating bugs during development rather than protection from misbehavior in the wild.
- Meyer, B.: Applying Design by Contract". IEEE Computer 25(10) (1992) 40{51
- Findler, R.B., Felleisen, M.: Contracts for higher-order functions. ACM SIGPLAN Notices 37(9) (2002) 48--59
If you find this confusing, or wrong but don't quite know what you'd say instead, without taking up too much space in a paper that's really about something else, perhaps you can sympathize with my edit.
In any case, I will point out that we've been using the term "smart contract" for this flavor of software contract since Nick Szabo coined it, which en.wikipedia.org/wiki/Smart_contract guesses was in
1993 -- only one year after Meyer. I don't remember any of the papers in this other literature clarifying how their use of the term "contract" was distinct from "smart contract". Perhaps because the difference looked clear enough when looking over the gap in that direction?
For the record, in retrospect, yes, I should have left in a footnote and worked to make it clearer. My apologies to my co-authors for making this particular edit without discussion.
On Mon, Jan 14, 2013 at 3:18 PM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:
On Mon, Jan 14, 2013 at 6:05 PM, Mark S. Miller <erights at google.com> wrote:
A fair point. By "contracts" in that first word, we refer to real-world contracts. For software "contracts", we initially had a footnote trying to explain the relationship between the "smart contracts" we're talking about and the type-like "contracts" that this literature refers to. Perhaps unwisely, I removed it because I thought it created more confusion than it cleared up. By introducing "the exchange of rights" in that same first sentence I hope we make it clear that we're talking about a different kind of contract, one closer to the real world notion.
I disagree, in two senses. First, behavioral software contracts in the sense of Meyer have a close analogy to real-world contracts, in particular contracts for the exchange of goods. For example, a spot contract is just an agreement to exchange some good meeting some specified description for another (usually one is money). Second, I believe that your escrow contracts are closely related to software contracts, in the sense that we could formulate them as software contracts in a sufficiently-expressive contract system, where the contract/runtime system itself plays the role of trusted host.
Someone should try this!
On Mon, Jan 14, 2013 at 3:31 PM, Mark S. Miller <erights at google.com> wrote:
On Mon, Jan 14, 2013 at 3:18 PM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:
On Mon, Jan 14, 2013 at 6:05 PM, Mark S. Miller <erights at google.com> wrote:
A fair point. By "contracts" in that first word, we refer to real-world contracts. For software "contracts", we initially had a footnote trying to explain the relationship between the "smart contracts" we're talking about and the type-like "contracts" that this literature refers to. Perhaps unwisely, I removed it because I thought it created more confusion than it cleared up. By introducing "the exchange of rights" in that same first sentence I hope we make it clear that we're talking about a different kind of contract, one closer to the real world notion.
I disagree, in two senses. First, behavioral software contracts in the sense of Meyer have a close analogy to real-world contracts, in particular contracts for the exchange of goods. For example, a spot contract is just an agreement to exchange some good meeting some specified description for another (usually one is money). Second, I believe that your escrow contracts are closely related to software contracts,
I do need to quibble about your terminology here. It would be bizarre to define "software contracts" so they exclude smart contracts implemented as software. I'm fine with "behavioral contract" as the term distinct from "smart contract". But clearly, they are both "software contracts".
On Mon, Jan 14, 2013 at 6:30 PM, Mark S. Miller <erights at google.com> wrote:
The footnote I (again, perhaps unwisely) deleted is:
Although types as contracts [2] and higher order contracts [3] can be seen as very special cases of smart contracts, their purpose is typically different: locating bugs during development rather than protection from misbehavior in the wild.
- Meyer, B.: Applying Design by Contract". IEEE Computer 25(10) (1992) 40{51
- Findler, R.B., Felleisen, M.: Contracts for higher-order functions. ACM SIGPLAN Notices 37(9) (2002) 48--59
I think there are two fundamental mis-understandings of the work on behavioral contracts here. First, that they're mostly about types and type-like properties. On the contrary, contracts are useful precisely because they express far more than conventional types. Matthias Felleisen suggests the following example:
(add-edge ;; adding an edge (from,to) with cost w to this graph (->dm ((from node?) (cost (and/c real? (cost/c (get-field low-cost this) (get-field high-cost this)))) (to node?)) #:pre (triangle-condition-preserved (send this edges) from cost to) any))
which enforces that the triangle inequality is preserved on edge-insertion into a weighted graph.
Second, that they're mostly about development and not production. Behavioral contracts are no more about development-only than array bounds checks are. It's an unfortunate fact of modern software development that both are often omitted in production systems, to the detriment of users as well as developers, but contracts are a fundamental way of finding errors and allocating responsibility for them in both production and development.
I have a couple of comments:
-
On the share-nothing model This comment goes beyond the paper, but I think is relevant for future work. Practice of the event loop model in JavaScript has proven that the share-nothing model has limitations. In my opinion, one of the reasons WebWorkers aren't used is that the share-nothing model imposes to copy data when one wants 2 WebWorkers to communicate. This resulted in the addition of Transferable objects in JavaScript [1]. Rust introduced the notion of unique pointer [2] for equivalent reasons. Adding a notion of (implicit) ownership could be a lead to follow (especially for the event loop work in ES7). It would however create a breach in the uniform vat model which abstracts out whether 2 vats are on the same machine or not. But I think it's a worthwhile addition.
-
Web-key It's probably a nit, but worth mentioning. Web-keys like www.example.com/app/#mhbqcmmva5ja3 only work on the web with a web application taking the fragment and building another url like www.example.com/app/?s=mhbqcmmva5ja3 with it, because the fragment part of a URL is a client-side only thing and is never sent over the network.
Checkpointing a program’s entire state after every event loop turn may be consid- ered costly. Ken takes care to only store those parts of the heap to disk that are updated during a turn. Further, the availability of cheap low-latency non-volatile memory (such as solid-state drives) has driven down the cost of writing state to “disk” to the point that making micro-snapshots after every turn becomes practical.
Out of curiosity, have you measured how much these micro-snapshots take? If so, what are the results/order of magnitude?
David
[1] updates.html5rocks.com/2011/12/Transferable-Objects-Lightning-Fast [2] Relevant article, but I'm not sure it's the best resource on the topic: pcwalton.github.com/blog/2012/10/03/unique-pointers-arent-just-about-memory-management
Le 14/01/2013 23:46, Mark S. Miller a écrit :
Perhaps one useful aspect to add to this discussion is the distinction between
-
contracts as implemented as a DSL (as in Racket)
-
contracts (aka attenuators/...) implemented as code
Both achieve the same functionality of constraining behavior. Contracts-as-code may be more flexible but may have more ability to change (rather than just constrain) behavior, whereas contracts-as-DSL gives simpler contracts, perhaps better blame, and may be easier to reason about.
I am inclined to view them as alternate ways of expressioning the same ideas.
On Tue, Jan 15, 2013 at 2:20 AM, David Bruant <bruant.d at gmail.com> wrote:
Practice of the event loop model in JavaScript has proven that the share-nothing model has limitations. In my opinion, one of the reasons WebWorkers aren't used is that the share-nothing model imposes to copy data when one wants 2 WebWorkers to communicate. This resulted in the addition of Transferable objects in JavaScript [1]. Rust introduced the notion of unique pointer [2] for equivalent reasons.
From a capability viewpoint, there are non-performance reasons to have the
same pattern, even within a given event loop, namely resources which may be transferred with observably exclusive access (ownership); the pattern is to have an operation on the resource which generates a new reference to it (i.e. a new object, from the OO perspective) and makes the old one useless ("revoked").
One could then argue that the share-nothing model + transferables is simply the decision, at the platform level, that similarly excluding access-from-multiple-threads is so valuable that we don't even let individual programs decide not to do it.
Also, I can describe Transferable from an E perspective (not that it is idiomatic to actually do that, but that it is possible to implement) by saying that the serialization of the transferable object has the side effect of performing such an exclusive transfer.
Le 15/01/2013 19:19, Kevin Reid a écrit :
On Tue, Jan 15, 2013 at 2:20 AM, David Bruant <bruant.d at gmail.com <mailto:bruant.d at gmail.com>> wrote:
Practice of the event loop model in JavaScript has proven that the share-nothing model has limitations. In my opinion, one of the reasons WebWorkers aren't used is that the share-nothing model imposes to copy data when one wants 2 WebWorkers to communicate. This resulted in the addition of Transferable objects in JavaScript [1]. Rust introduced the notion of unique pointer [2] for equivalent reasons.From a capability viewpoint, there are non-performance reasons to have the same pattern, even within a given event loop, namely resources which may be transferred with observably exclusive access (ownership); the pattern is to have an operation on the resource which generates a new reference to it (i.e. a new object, from the OO perspective) and makes the old one useless ("revoked").
Interesting. It reminds me that JavaScript does not have a notion of internal and external code with regard to an object. Anyone with access to the object can equivalently modify it (add, delete properties for instance). On object can't at the same time defend its integrity and modify its own shape (I guess it's possible with proxies now).
I don't know why anyone would want to do that, but if you want to model a caterpillar becoming a butterfly, it's a bit complicated in JavaScript without proxies. The caterpillar has a "crawl" method and if we want the same object (same identity) to eventually become a butterfly with a "fly" method (but no crawl method), the object has to remain extensible and the crawl property has to be configurable. The problem is that any outsider can mess around with the properties. The idea of generating a new object out of an old one which becomes useless is interesting, but people holding a reference to the caterpillar may expect to have a reference to a butterfly eventually. The problem with a new identity is that people holding a reference to the caterpillar now have a useless reference and may not hold the reference to the butterfly.
Where have you seen the "create new object from old one" pattern used? It sounds interesting, but I can't think of where I'd use it.
On Tue, Jan 15, 2013 at 12:49 PM, David Bruant <bruant.d at gmail.com> wrote:
Le 15/01/2013 19:19, Kevin Reid a écrit :
From a capability viewpoint, there are non-performance reasons to have the same pattern, even within a given event loop, namely resources which may be transferred with observably exclusive access (ownership); the pattern is to have an operation on the resource which generates a new reference to it (i.e. a new object, from the OO perspective) and makes the old one useless ("revoked").
Interesting. It reminds me that JavaScript does not have a notion of internal and external code with regard to an object. Anyone with access to the object can equivalently modify it (add, delete properties for instance). On object can't at the same time defend its integrity and modify its own shape (I guess it's possible with proxies now).
I don't know why anyone would want to do that, but if you want to model a caterpillar becoming a butterfly, it's a bit complicated in JavaScript without proxies. The caterpillar has a "crawl" method and if we want the same object (same identity) to eventually become a butterfly with a "fly" method (but no crawl method), the object has to remain extensible and the crawl property has to be configurable.
Becoming useless is different from becoming a different interface; all that is necessary is that the operations on the object are disabled. A simple generic answer would be something like 'all getters return undefined, all setters and methods throw'. Note that this is a change in the behavior of functions and is therefore allowed to be entirely internal.
However, it is useful to have an application-specific notion of “useless”. For a made-up-on-the-spot example, suppose the disabled object is some kind of container; if it reports itself as being empty and only throws in response to operations attempting to add new elements, then an application may be able to avoid special-case code by letting the empty container be handled as a trivial case rather than the caller of the transfer operation having to make sure the container is removed from other places. Or consider that objects for e.g. streams and open-files may be closed: anything that designates an external resource often has some kind of well-defined useless state.
Where have you seen the "create new object from old one" pattern used? It
sounds interesting, but I can't think of where I'd use it.
Real examples are hard to find because (1) hardly anyone is writing ocap code with detailed mutually-suspicious interactions, and (2) one generally prefers to avoid having to manage exclusive access by not having a need for exclusion (i.e. everyone has their own independent instance of whatever)!
Our canonical example of exclusive access is virtual money: money held in a 'purse' object may be exclusively transferred away by depositing it into a new purse, leaving the old one with a balance of zero. (In this case, the old object simply has a zero balance and may be reused.) Similarly, a virtual board/card game could handle transfers between players of its virtual 'physical' tokens this way.
If my examples are unconvincing, I leave it to MarkM to provide better ones :)
E uses a different trick. E objects that are marked as transitively immutable and transitively identity-less can be safely passed between vats in one address space by pointer sharing rather than copying. For these objects, this optimization has no semantics. JS has no identity-less objects, but rivertrail does traffic in transitively immutable nested data arrays -- both consuming and producing these.
The reason is the same -- concurrent access is not detectably different access to a separate per-thread copy (identity aside). Perhaps rivertrail and communicating event loops, for parallelism and concurrency respectively, can agree on the same set of transitively immutable data types that can safely be concurrently accessed.
This is not to argue against exclusive ownership transfer -- that may be valuable too. But exclusive ownership transfer is more complicated: To avoid introducing yet another new category of object but still be able to have a revoked behavior in the donating vat, we'd have to define transferables as proxies, as I think you argue on similar grounds. This seems strange for an object whose purpose is high speed access.
Note that neither of these optimizations help or hurt when communicating between address spaces or machines.
---------- Forwarded message ---------- From: Rajesh K Karmani <rajesh.karmani at gmail.com>
Date: Sat, Jan 19, 2013 at 8:26 AM Subject: Re: New paper: "Distributed Electronic Rights in JavaScript" To: "Mark S. Miller" <erights at google.com>
Hello Mark,
Thank you for pointing me to the discussion. I subscribed to the list, but for some reason, I could not find a way to contribute to an existing thread.
I would like to contribute two comments:
-
In terms of performance, ownership transfer (implicit or explicit) of mutable objects could be better than immutable objects (copy-on-write semantics) in cases when both threads or actors modify the object. In such cases, immutable object implementation will result in three total copies, while ownership semantics will result in two copies.
-
Ownership transfer (implicit or explicit) can also help when communicating across machines or address spaces, specifically in improving the efficiency of garbage collection. An object (or its "name") that is transferred out is certainly garbage. Garbage collection for actor-like systems is a challenge due to in-flight messages and reverse knowledge graph. This optimization could help in improving its performance.
Thanks, Rajesh
2013/1/15 David Bruant <bruant.d at gmail.com>:
Hi Mark,
I have a couple of comments:
On the share-nothing model This comment goes beyond the paper, but I think is relevant for future work. Practice of the event loop model in JavaScript has proven that the share-nothing model has limitations. In my opinion, one of the reasons WebWorkers aren't used is that the share-nothing model imposes to copy data when one wants 2 WebWorkers to communicate. This resulted in the addition of Transferable objects in JavaScript [1]. Rust introduced the notion of unique pointer [2] for equivalent reasons. Adding a notion of (implicit) ownership could be a lead to follow (especially for the event loop work in ES7). It would however create a breach in the uniform vat model which abstracts out whether 2 vats are on the same machine or not. But I think it's a worthwhile addition.
Web-key It's probably a nit, but worth mentioning. Web-keys like www.example.com/app/#mhbqcmmva5ja3 only work on the web with a web application taking the fragment and building another url like www.example.com/app/?s=mhbqcmmva5ja3 with it, because the fragment part of a URL is a client-side only thing and is never sent over the network.
Indeed. The spec even says that is specifically to prevent access control based on fragments:
RFC 3986 says in section 3.5
Although this separate handling is often perceived to be a loss of information, particularly for accurate redirection of references as resources move over time, it also serves to prevent information providers from denying reference authors the right to refer to information within a resource selectively.
So a client that has a URI can make authorization decisions based on the fragment, but the server, by design, cannot.
At code.google.com/p/es-lab/downloads/detail?name=distr-erights-in-js.pdf
Paper for invited talk at ESOP2013 www.etaps.org/2013/esop13 Final already submitted, but comments of course appreciated anyway.
Distributed Electronic Rights in JavaScript
Mark S. Miller Tom Van Cutsem Bill Tulloh
Contracts enable mutually suspicious parties to cooperate safely through the exchange of rights. Smart contracts are programs whose behavior enforces the terms of the contract. This paper shows how such contracts can be specified elegantly and executed safely, given an appropriate distributed, secure, persistent, and ubiquitous computational fabric. JavaScript provides the ubiquity but must be significantly extended to deal with the other aspects. The first part of this paper is a progress report on our efforts to turn JavaScript into this fabric. To demonstrate the suitability of this design, we describe an escrow exchange contract implemented in 42 lines of JavaScript code.
At http://code.google.com/p/es-lab/downloads/detail?name=distr-erights-in-js.pdf Paper for invited talk at ESOP2013 http://www.etaps.org/2013/esop13 Final already submitted, but comments of course appreciated anyway. Distributed Electronic Rights in JavaScript Mark S. Miller Tom Van Cutsem Bill Tulloh Contracts enable mutually suspicious parties to cooperate safely through the exchange of rights. Smart contracts are programs whose behavior enforces the terms of the contract. This paper shows how such contracts can be specified elegantly and executed safely, given an appropriate distributed, secure, persistent, and ubiquitous computational fabric. JavaScript provides the ubiquity but must be significantly extended to deal with the other aspects. The first part of this paper is a progress report on our efforts to turn JavaScript into this fabric. To demonstrate the suitability of this design, we describe an escrow exchange contract implemented in 42 lines of JavaScript code. -- Cheers, --MarkM