[e-lang] Pre-Announcing 0.8.28d: Donut-Lab in 72 hours. 3-vat CapTP. An E IOU; always Y...

[Mark S. Miller]

At http://www.erights.org/download/0-8-28/index.html

Until further testing, this is currently just a release candidate. Due to 
various disasters, I currently have no working Linux or Mac OS X systems, 
and so will not be able to build binary releases for these platforms yet. If 
you have any problems building from sources on these or any platforms, 
please let me know. (After this week, I'll be gone for two weeks, and so 
won't be able to repair the situation until the end of June.)

Note that the last official E release is 0.8.26h. The 0.8.27 series is 
skipped, but remains as a milestone of what we were able to accomplish using 
E in only 72 hours, all of which is included in 0.8.28d: 


                      Donut-Lab: A PlanetLab with no center


PlanetLab http://planet-lab.org was created to serve as a testbed for 
experimenting with large scale distributed systems of various kinds. Among 
the systems now running on PlanetLab are various DHTs, content distribution 
networks (like CoDeeN), proposed DNS replacements, and other highly 
decentralized, massively distributed systems. However, PlanetLab itself is 
an administratively centralized system. "PlanetLab Central" remains a 
central point of failure for all the systems built on top of PlanetLab, 
which is unfortunate, as these systems themselves are often impressive 
exemplars of systems designed not to have such centralized vulnerabilities.

When I raised this issue with Timothy ("Mothy") Roscoe, one of the PlanetLab 
architects (and, btw, an old capabilities guy), he said "PlanetLab is a good 
enough testbed to prototype its successor." Indeed. Rick McGeer, an E fan on 
the PlanetLab steering committee, has gotten E working in a PlanetLab sliver 
(a Linux VServer, which is how PlanetLab nodes currently offer compute 
services to PlanetLab apps).

In thinking about the needs of a secure persistent fully decentralized 
PlanetLab-like system, MarcS realized that such a system could be created 
quickly in E, and that E was almost ready. Over the memorial day weekend, in 
72 hours, MarcS, Terry, and I created Donut-Lab. The results of this effort 
are posted as the 0.8.27h draft release of E at 
http://www.erights.org/download/0-8-27/index.html . It works. It's 
persistent. It would be secure as far as we know -- once the outstanding 
severe security hole identified by Kevin Reid is fixed. It's agoric -- it 
uses "money" to put various kinds of resource use on a pay-as-you-go basis 
(within the limits of what we're currently able to meter). We built a first 
distributed app: the DoughBot, an attempt at a DDOS attacker. Of course, 
given the agoric resource controls, the DoughBot's attack stops once it's 
spent all its money.

(Unless you're interested in the history, we recommend looking at the 
Donut-Lab code in the latest release instead.)

{We even have a logo: See 
http://www.erights.org/smart-contracts/donut-lab/index.html .)

(Donut-Lab currently only runs distributed apps written in E, as E's 
protections are the basis for limiting the authority provided to a sliver. 
For Donut-Lab to become real, it should also provide the option of loading 
untrusted machine code into a virtual machine sliver at some point, reusing 
mechanisms from the existing or planned PlanetLabs (VServers, Xen, ...). At 
that point, Donut-Lab would become a decentralized control layer for 
otherwise conventional sliver machinery. In any case, the main point of 
Donut-Lab isn't Donut-Lab per se. It is to demonstrate the power of E's high 
quality linguistic support for rapidly developing secure decentralized 
persistent apps.)


                       3-vat Introduction-by-Shortening in CapTP again


The main missing element from E was the lack of 3-vat Introduction-by-
Shortening in CapTP. We lost this when we added pipelining, as the 
combination of the two creates a huge case analysis that's still in front of 
us. However, Alan Karp raised my confidence that the current protocol design 
is correct by asking me "What's the hardest case you're worried about?", and 
then having me step through that case in explicit detail. (A three vat 
"simultaneous" promise loop that need to resolve, at each vat, to a 
reference broken by a VisciousCycleException.) It worked, and it seemed to 
work for all the right reasons.

For purposes of this experiment, I turned the remaining mechanism on, fixed 
the one bug I encountered, and started using it. We now have, for the first 
time, the full co-existence, in one protocol, of 

* 3-vat introduction-by-shortening
* message pipelining
* distributed capability security
* partial order preservation
* distributed acyclic garbage collection
* partition cleanup with support for recovery

Given this list, it's not surprising that we still have that enormous case 
analysis in front of us. However, the kinds of bugs that such a case 
analysis would catch, and that we should be worried about in its absence, 
are most likely not bugs which could provide inappropriate authority to 
anyone. Rather, they would more likely create inappropriate failures or lack 
of progress. Once I realized this, I decided to leave this feature turned on 
in 0.8.28d.

Donut-Lab makes heavy use of this new feature. We have no known bugs in 
CapTP's 3-vat introduction at this time. CapTP therefore now support the "Y" 
property http://www.waterken.com/dev/YURL/Definition/ , needed by the 
Waterken IOU design.


                    An E IOU. Always Y


The hardest part to figure out how to decentralize is money. With the 
exception of DSR (Digital Silk Road) http://www.agorics.com/Library/dsr.html 
, all electronic money proposals of which we're aware rely on a centralized 
issuer. By contrast, DSR works the way the real world does: multiple 
currencies, and floating market exchange rates between them. In DSR, any 
pairwise financial relationship has a "soft credit window" (as recently 
analyzed by http://www-db.stanford.edu/~byang/pubs/ppay.pdf ), and a 
clearing arrangement mutually acceptable to that pair of entities. There 
need be no global agreement on how to clear imbalances, just compositions of 
pairwise local agreements.

During the 72 hour period, we only instantiated one currency with one issuer 
used for initial payments and clearing. We did not create any money 
changers, and we created only the barest approximation of a soft credit 
window. But everything we built is consistent with growing in these 
directions. For our initial issuer, we used the Waterken IOU protocol. 

Starting with the KeyKOS Space Bank protocol, and evolving though the 
Fractal Reserve Bank 
http://www.eros-os.org/pipermail/cap-talk/2003-July/001255.html , WebMart, 
and ERTP, it took us 20 years to arrive at the wonderful combination of 
flexibility and simplicity of the IOU design. MarcS was able to implement 
this design in E in about three hours. 
http://www.waterken.com/dev/IOU/Design/ documents well the extraordinary set 
of simultaneous goals satisfied by the IOU protocol. We also found it very 
easy to use well. We're very happy with it. Congratulations to Tyler for 
this gem.


                      Painless Upgrade


When MarcS first suggested the Donut-Lab exercise, I expected we could fix 
CapTP quickly, as we in fact did, but I initially thought "E's persistence 
isn't ready yet". Then I remembered that Kevin Reid's been using it 
successfully in Den, so it must be ready enough! It was.

Based on the Electric Communities experience, we remembered that the hard 
persistence problem isn't recovering from crashes; it's recovering from 
version upgrade of the code. We strictly followed the Arturo persistence 
philosophy -- only save what you really need and reconstruct the rest on 
revival. As a result, we were able to go through our development cycle quickly: 

    while (true) {
        Run until we spot a bug. 
        Shut down
        Fix the bug
        Revive old state into the new version and continue
    }

Once we got checkpoints working at all, we were then able to go around this 
loop without once being surprised by being unable to upgrade into a new 
version. We experienced the fantasy of persistence with rapid development 
rarely experienced outside of Smalltalk.


                        Multi-vat Updoc and Causeway


In addition to the virtues of the E language, CapTP, and the DSR and IOU 
designs, other crucial elements to our quick success were the high level 
tools created mostly by Terry Stanley: Multi-vat Updoc and Causeway. 

For example, when the Updoc script in the release at
e/src/jsrc/net/captp/jcomm/bad-resolve.updoc, is run, updoc, running in one 
vat, controls three other vats, stepping them through a sequence of actions 
in order to create some three-vat interaction test cases in an easily 
reproducible fashion. The one 3-vat CapTP bug we encountered, a race with 
the local garbage collector, we were able to find by replaying this script 
repeatedly from within the IntelliJ IDEA debugger (with lots of breakpoints 
set).

We also encountered a discouraging new race condition bug that happened 
rarely, and seemed completely inexplicable. However, it happened once while 
we had causality tracing on ("TraceLog_causality=debug" in eprops.txt, or 
"-DTraceLog_causality=debug" on the command line), so we were able to do a 
post-mortem analysis of this using Causeway. (The screenshot at the end of 
http://www.erights.org/smart-contracts/donut-lab/index.html is from this 
session.) The bug itself was in the boot-comm system -- one of the few parts 
of the E implementation which deals directly with the Java threading model. 
Even though this is below the level of abstraction Causeway was built to 
deal with, Causeway provided me enough information to figure out what to 
think about. I doubt I would have found this bug during this same weekend 
without such a tool.


-- 
Text by me above is hereby placed in the public domain

        Cheers,
        --MarkM