Scalable Distributed Security with Bearer Certificates

[Mark S. Miller]

Since the libtech list has a general "don't store, forward, or cite"
policy, I hereby give permission to do so freely with this message.  I'm
also cc'ing the E list, which is publicly archived
"http://eros.cis.upenn.edu/%7Emajordomo/e-lang/index.html".  If you wish to
keep you responses private, be sure to check your cc list first.

----------------------------------------------------------------------

Thanks for the reminder Nick.  I liked your recent intro to distributed
capabilities as bearer instruments for smart contracting.  Here's recent
news that may interest this group, from the top of the old E Download Page
http://www.erights.org/download.html:


-----------------------------------------------------------------------
                NEW: Internationally Available
                  Cryptographically Secure E

E 0.8.0 is now available for download internationally, with no export
constraints. Unlike daffE (see definitions below), this version has
not been crypto-crippled to appease bureaucrats. Tyler Close, not a
citizen or resident of the US, has independently figured out how to
reverse the damage we did to create daffE. Bill Frantz, who wrote the
US-only, unreleased, original secure version, has verified that
Tyler's version will communicate with the unreleased US version of
E. Note that E and daffE do not communicate with each other.

At this time, we will continue to offer daffE on this page, but little
reason remains to download it, rather than E. To get the real E, go to
Tyler's page.

1998 saw the open sourcing of E, EROS, and now the international
distribution of cryptographically secure E. 1998 is hereby The Year
When Capabilities Were Freed. Happy new year!
-----------------------------------------------------------------------

https://www.cypherpunks.to/~tyler is the new E download page referred to above.

http://www.erights.org/elib/elibmanual.pdf combined with
http://www.caplet.com/security/taxonomy/grant-match/grant-matcher.html is
my current draft attempt to define capability security.  These are not yet
explained well, but I believe the only foundational element of capabilities
they leave out is rights amplification.  E's rights amplification primitive
(or synergy primitive) is modelled on Joule's "Energetic Secrets"
ftp://www.agorics.com/pub1/agorics/postscript/MANUAL.B17.ps.Z

The E language is a distributed pure object language based on the premise
that pure object computation is identical to pure capability computation,
with object references as capabilities.  Those familiar with the C syntax
tradition, should be able to start using E very quickly as a normal
programming language.
http://www.erights.org/elang/concurrency/introducer.html is the first step
from normal programming to using E as a secure distributed language.

-----------------------------------------------------------------------

In talking about potential anonymity problem in doing capability-based
smart contracting, there are four very different anonymity issues.

		Identification of "Principles"

ACL systems are based on the premise of authorizing, not fine-grained parts
of a computation, but some large-grain entity (like a human or a
human-organizational-role) on behalf of whom computation is done.  The
decision to authorize such a large-grain entity is typically made by a
human administrator, so the large grain entities usually have to have
identities meaningful to humans.  This is at odds with anonymity, but
bearer instruments and capabilities do not suffer from this problem.

		Object Identity vs Physical Location

Abstractly, in the distributed capability model, a capability designates a
particular object, and conveys messages to that object.  The object must
exists in a physical place or places, and can be no more trusted than is
the hardware on which it runs.  Although someone holding a capability can
communicate with the object it designates, there's nothing in the
capability model that enables them to determine where the object is located
(given that the object doesn't wish to reveal this fact).

The current E implementation visibly aggregates objects into Vats, but this
doesn't violate any fundamentally principles yet.  Other than this
aggregation, there's nothing in E's semantics that necessitates revealing
object location.  Ideally, we would say the Vat is E's unit of full
anonymity.  Unfortunately, there's also nothing in E's implementation that
hides location.  The IP address of the machine hosting a Vat is simply
revealed, and intervat communication is via a direct TCP/IP connection.

http://www.erights.org/to-be-sorted/DataCommThruFirewalls.html describes
our (Bill Frantz's) thoughts on using http tunnelling to get through
firewalls.  It would be great to understand how this, or various
independent mixing schemes, can be extended to hide location.

Btw, something I worry about wrt independent mixing schemes (onion routers,
etc..): What's their model for how connectivity begets connectivity?  As we
all know from crypto protocols, post-handshake security is the easy part.
If you're gonna blow it, you'll probably blow it on the handshake.  I'd
feel much better if their model were shown equivalent to the fundamental
diagram http://www.erights.org/elib/elibmanual.pdf 


		External Traffic Analysis

Traffic Analysis is often lumped together with ascertaining someone's (or
something's) physical location.  I'd like to distinguish hiding an object's
location from one who's been authorized to speak to the object (the
previous section), vs hiding this from external third parties who are
merely spying on the traffic.  Once again, the E semantics don't enable a
third party to gain any information by spying on traffic, but the E
implementation doesn't do anything to prevent statistical analysis of
fluctuating traffic patterns.  I believe the E implementation does hide all
information other than location and fluctuating traffic patterns.

Why am I religiously distinguishing between the security allowed by the E
semantics and that provided by the E implementation?  Capability programs
written today will only have the security provided by the current
implementation's subset of the capability model (ie, pure capabilities
minus the above anonymity weaknesses).  This is still a form of security
adequate for many smart contracts.  As this infrastructure comes into
further use, it will create a demand for the mechanisms needed to plug
these anonymity holes.  Since the semantics does not require the existence
of these holes, no E programs need be fixed when these holes are plugged,
but all E programs get the benefits.

Unfortunately, not all anonymity problems can be fixed later in a
transparent fashion.

		Blinding

Chaum's blinding seems to do something fundamentally different from the
kinds of security that capabilities naturally express.  To make this clear,
here's a simple secure bank in E:


define BrandMaker := import:org.erights.e.elang.sealing.Brand

define MintMakerA(name) {
    define [sealer, unsealer] := BrandMaker pair(name)
    define mint {
	to printOn(oo) {
	    oo print(`<$name's mint>`)
	}
	to makePurse(balance : integer ? (0 <= balance)) {
	    define decr(amount ? (balance >= amount)) {
		balance -= amount
	    }
	    define purse {
		to printOn(oo) {
		    oo print(`<purse holding $balance $name bucks>`)
		}
		to getBalance { balance }
		to getDecr {
		    sealer seal(decr)
		}
		to deposit(amount : integer ? (0 <= amount), src) {
		    unsealer unseal(src getDecr)(amount)
		    balance += amount
		}
		to sprout {
		    mint makePurse(0)
		}
	    }
	}
    }
}

Note that the printOn(oo) methods exist purely to aid debugging, and have
no security significance.  "?" should be read "such that".  Here's a
transcript of a command line interaction with this bank:

	? define MintMaker := import:org.erights.examples.money.MintMakerA
	# value: <MintMakerA>

	? define JoeMint := MintMaker("Joe")
	# value: <Joe's mint>

	? define BettyMint := MintMaker("Betty")
	# value: <Betty's mint>

	? JPurse1 := JoeMint makePurse(100)
	# value: <purse holding 100 Joe bucks>

	? JPurse2 := JPurse1 sprout
	# value: <purse holding 0 Joe bucks> 

	? BPurse1 := BettyMint makePurse(100)
	# value: <purse holding 100 Betty bucks>

	? JPurse2 deposit(20, JPurse1)
	# value: 20

	? JPurse1
	# value: <purse holding 80 Joe bucks>

	? JPurse2
	# value: <purse holding 20 Joe bucks>

	? JPurse2 deposit(20, BPurse1)
	# problem: org.erights.e.elang.sealing.UnsealingException: 
	#          box not sealed by matching sealer

This simple piece of code demonstrably has the following properties:

Anyone can create a new mint.  Each mint represents a separately
exchangeable currency.  Let's call the total of all the "balance" variables
of all purses of a given currency the volume of that currency.  Only
someone with access to the mint can inflate the volume of a currency, ie,
without access to the mint of a currency, it is impossible to violate
conservation of currency.  Only someone with access to a purse can affect
the balance of that purse.

Between two parties, each unprivileged beyond having a purse of a common
currency, how does one pay another?  The payor "sprout"s a new empty purse
off of his main purse, and "deposit"s the payment amount into it from his
main purse.  The payor then includes the sprouted purse as an argument in a
message requesting service from the payee.  The payee tells her main purse
to "deposit" the expected payment amount into itself from the received
purse, and arranges to find out whether this operation succeeds (returns
normally) or fails (throws an exception).  When the payee finds out that
"deposit" reports success, she knows she's been paid.  The payee cannot
transfer more money to herself from the payor than the payor put in the
sprouted purse.

The above bank is perfectly adequate whether its clients are other E
objects within the same address space (E uses safe language techniques for
intra-address-space security), or across the internet.  This simplicity has
a scaling price: all purses of a given currency are in the same Vat as that
currency's mint, since they are made by the mint in the above simple way.

Non-local clients of the bank need to deal with the bank asynchronously,
which is beyond the scope of the current message.  In any case, this
scheduling difference has no security implications.

The above code should give a taste of E's clarity and simplicity for
expressing many of the properties that smart contracts -- no matter how
they're implemented -- will need to express.  I submit that E is a good
notation for specifying smart contracts.

Except for the traffic analysis and location-hiding concerns already
discussed, the traders are not in any position to know any more about each
other's identity than they do in a Chaumian scheme.  However, the bank is
in a frightening position to notice money flows, as it can observe every
operation on each of its purses.  A modification to the above code that
provides such information to the mint holder would be behaviorally
identical to the purse holders.  I know of no way to do a capability-based
bank with blinded transaction, so Chaumian blinding does seem to be a
fundamental innovation.

The above bank also has a frightening lack of accountability.  If the bank
cheats a customer, the customer can keep enough records to tell he's been
cheated, but he can't prove it to anyone else.  Distributed capabilities do
not naturally express non-repudiatable transactions.

Money in particular needs blinding and accountability, but given such
money, what about the rights one is exchanging such money for?  High
reputation intermediaries and iterated games can often provide incentives
sufficient to prevent much of the cheating you would have wanted
non-repudiation for.  My sense, and the engineering premise of E, is that
there is a vast potential world of smart contracts, accessible now, in
which the security provided straightforwardly by capabilities, even with
all the above qualifiers, are sufficient, given that one also has a
Chaumian scheme specifically for money.  Given the current patent
situation, we have no way to add a Chaumian scheme and maintain our open
source status.

But remember, let's not try to solve all problems simultaneously before we
deploy.  At Xanadu, we anticipated many of the painful problems the web
would experience in the years that followed, and we had elegant
simultaneous solutions for an astonishing number of them.  As a result of
our ambition, we missed the window, and the world instead got stuck with
http/html.  I do learn from my mistakes -- E is clearly not the ideal smart
contracting medium, but 

  * Is it enough to get started?

  * Does it absolutely live up to a set of understandable security claims?

  * Are these claims useful by themselves?

  * How smoothly can it grow into our ideal smart contracting medium?

  * IF there actually will be large-scale demand for our ideal smart 
    contracting medium, how much demand should we expect for such a subset?

  * Would widespread use of this subset lead to demand, and then supply, of   
    the missing features?  This is the incremental way in which the web did 
    solve many of the problems "nobody" anticipated.

I am the open source coordinator of the E project.  I am currently doing
more writing than coding, trying to get things to be presentable to a
larger audience.  Until several more chapters have been written, we've been
mostly laying low (but openly).  It's better to promote once people can
have a rewarding experience by following up.  In any case, if you folks buy
my argument, the open sourced E project could sure use some high quality
help.  Interested?  We pay only in satisfaction.

	Towards jurisdiction-free commerce,
	--MarkM