Must-read capabilities paper (fwd)

[Mark S. Miller]

(Note, this thread is of interest both on the cypherpunks and e-lang 
lists.  Unless messages are marked otherwise, I will forward message in 
this thread on either list to other as I feel is appropriate.)

At Mon, 1 Nov 1999 20:29:07 +0100 Anonymous wrote:
>The E work may be significant and important, but it always seems difficult
>to pin down specific advantages that it offers.

This short message by Anonymous is quite meaty.  It raises many very 
important issues well.  In order to give it the response it deserves, I 
will respond with several email messages, of which this is the first.

>Consider their cash example, from the paper above.  ...[There follows an 
>accurate and nice summary of our banking example, analyzed as if it were a 
>serious proposal for a payment protocol]...   This is a rather mundane 
>approach ...

Yes, as a proposal for a serious cryptographic payment protocol, our cash 
example is indeed mundane.  However, we preface the example 
http://www.erights.org/elib/capability/ode/ode-capabilities.html#simple-mone 
y , in red boldface italics, with "We are not proposing to actually do 
money this way!".  After listing several desirable properties a money 
system should have, we say "The following money provides none of 
these."  We intend the money example, not as a proposed money protocol, but 
as an example of an important principle.

What principle?  Anonymous asks the right question:

>Capabilities thus put some constraints on the design of the system,
>but with sufficient ingenuity one can make systems do what is needed.
>The question is whether this approach brings significant advantages over
>the conventional way of doing things.  Is the promised synergy real?
>How does the capability model help the crypto protocol designer, to
>compensate for the limitations it imposes?

How does the capability model help the protocol designer?  Well, it depends 
on the protocol designer's goal.

"We actually have all the protocols we need."  --Bruce Schneier (from
http://crit.org/http://slashdot.org/interviews/99/10/29/0832246.shtml%ff:wor 
ds:(Sajma-asks)#M1-target )  Schneier goes on to say:

>What is useful are the few simple primitives -- signatures, encryption,
>authentication -- and the different ways to mirror real-life trust models
>using them. [...] The real problem with protocols, and the thing that is the
>hardest to deal with, is all the non-cryptographic dressing around the core
>protocols. [...] many systems end up with a design that is as complex as the
>designers and implementers can reasonably handle. [...] In actual systems,
>the situation is not quite so bad; there are often options that are
>'orthogonal' in that they have no relation or interaction with each other.
>[...]  Good modularization can dramatically reduce the effective complexity
>of a system without the need to eliminate important features

For us, the timing of Schneier's interview is quite fortunate, as these are 
exactly the points we need to start with to answer Anonymous.  And no, we 
don't fully subscribe to "We actually have all the protocols we need", but 
probably for a different reason from most cryptographers.  But first, we 
have to distinguish between two levels of protocol.

Since we agree that our money example, as a cryptographic payment protocol, 
is mundane, what point are we making?  That this "money" is a cryptographic 
protocol only in the sense that an ALU or a register is an analog 
circuit.  Imagine the hell that digital component designers would have if 
they always had to design in terms of analog building blocks.  Of course, 
they are ultimately building on analog building blocks, but they don't 
normally think of it that way.  If 1) their logic design is correct, and 2) 
the design rules correctly wrestle the analog mess into a faithful 
implementation of the digital logic gate abstraction, then their component 
is correct.  (Of course, it's good to test an analog simulation of the 
circuit as a sanity check, but if this fails when the first two don't, 
something is seriously wrong.)

Cryptographic protocol design is *hard* 
http://www.counterpane.com/whycrypto.html , but, given the assumption that 
we have a faithful cryptographic implementation of the capability security 
model, the design of this money was easy.  However, this money is 
admittedly mundane, as befits a first example in a short 
paper.  Interestingly, the Smart Contract implementing the Covered Call 
Option (a kind of stock option) was also 
easy. 
http://www.erights.org/elib/capability/ode/ode-bearer.html#options-contract 
.  It was easy because the designer of the contract could think about the 
security & trust relationships among the five (!) participants in the 
contract *without thinking about cryptography*.

The five parties are: the call writer, the call holder (initial buyer), the 
broker, the money issuer, and the stock issuer.  This contract is one page 
of code.  Once distribution and concurrency are added, making this code 
about three times larger, this code *is* the implementation of the 
contract.  It isn't a set of equations describing the abstract logic that 
someone else needs to implement.  We are unaware of any other work in the 
field of cryptography demonstrating this level of expressiveness.  That's 
the core contribution of the capability model.

"Simple things should be simple.  Complex things should be 
possible."  --Alan Kay

Much of modern cryptography has concentrated on pushing the envelope of 
complex things that are found to be possible.  Great, that's valuable.  But 
I suspect that Anonymous's puzzlement with our paper comes from the 
expectation that cryptographic progress is only the invention/discovery of 
new possibilities.  We confess, we have not made any patterns of 
cooperation possible that cryptographers did not already know were 
theoretically possible.  That's not what we were trying to do.  (Actually, 
we may have a few minor such contributions, but these will be the subject 
of other papers & email messages.)

Our work is targeted instead at making the design of simple protocols 
simple.  Protocols that Anonymous finds mundane are beyond what most smart 
professional programmers can successfully design -- if they have to think 
about cryptography.  Other examples in the same spirit: yacc enables people 
to write parsers without knowing any parser theory beyond BNF.  Programming 
languages enable people to program without understanding which register 
does what.  Mosaic created a revolution mostly by simply allowing people to 
avoid learning ftp.  This of capabilities as mundane cryptographic protocol 
design for the rest of us.

Business & Commerce are built from contracts.  Given the theoretical 
possibilities crypto has already created, we have to ask ourselves, why are 
new web businesses, founded after the rise of modern cryptography, hardy 
ever using crypto for anything other than accepting credit card 
payments?  For electronic commerce to happen, vast numbers of people need 
to acquire the skills to write secure electronic contracts -- 
electronically enforceable arrangements by which mutually suspicious 
parties can cooperate, each for their own interests, but with controlled 
and understandable exposure to risk from each other's mischief.  Each such 
arrangement is effectively a new protocol.  However, for the reasons 
Schneier outlines, if each contract requires the design of a new 
cryptographic protocol, we can forget most of our dreams of future 
electronic commerce.

To realize these dreams, we need to do more than make it easy for 
non-cryptographers to write new contracts.  We need secure 
composability.  Consider the likely world of cryptographic commerce in the 
absence of composability. X works on a cryptographic protocol for running 
an auction. Y and Z work on two different systems for cryptographic money. 
W works out a cryptographic escrow exchange agent. Let's say they all do a 
locally perfect job. Should we expect that the money obtained via Y's 
protocol will be accepted by X's auction? Or that electronic rights 
purchased through X's auction will be the kind of rights W's escrow 
exchange protocol knows how to escrow? Capabilities don't make this problem 
trivial, any more than object libraries are trivially reusable! However, in 
the absence of some basis for secure composability, we would have no hope 
of making all the pieces play together securely.

At the end of our paper, we show the construction of a tradable option by 
composing rather generic understandable building blocks.  One providing the 
option itself, and one making an object tradable.  The security of each of 
these is independently reviewable, without reasoning about 
cryptography.  Given a set of such reviewed components, one may then review 
their composition much more cheaply than the cost reviewing a similar 
monolithic composite.  If you wish, think of this as contract construction 
by composition of separately debuggable boilerplate.

We cannot stop building protocols, because we cannot stop writing contracts 
and creating business models.  Schneier also points at the way out -- 
modularity.  But Schneier seems to approach this merely as a recommendation 
of good engineering practice, as if to say "You be good now, and write 
modular systems."  We propose that modularity, to be successful, must be a 
technology supplemented by good engineering practice.  What is the 
technology of modularity?  Abstraction mechanisms --- a technology explored 
almost exclusively by programming language designers.  We are very excited 
that capabilities, properly construed, are simultaneously a powerful 
security primitive and the abstraction mechanisms generally considered most 
successful: lambda abstraction & object programming.



         Cheers,
         --MarkM