From Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU Fri Aug 7 17:06:11 1992
Received: from DAISY.LEARNING.CS.CMU.EDU by scss3.cl.msu.edu (4.1/4.7) id AA14432; Fri, 7 Aug 92 17:06:10 EDT
Date: Fri, 7 Aug 1992 16:56-EDT
From: Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU
To: Mark Riordan <mrr@scss3.cl.msu.edu>
Subject: Electronic cash, secure netnews
Status: ORS

Here's an article I updated recently about implementing electronic cash
using a "secure newsgroup" which is guaranteed to look the same to
everybody in the world.

A secure newsgroup would also be a good place to put public keys.
It might be a neat idea to establish a secure newsgroup on top of
a conventional newsgroup, and use it as the public key server. The
group could be archived in various places to provide easy access to
old messages. Any interest in talking about this or actually doing it?

M.



Electronic Cash = Ownership of a Secret
---------------------------------------
My goal is to implement electronic cash without having a central
trusted authority such as a bank or the government. I would rather
accomplish security through distributed means, where everyone can
see the system in operation.

Given this philosophy, I don't want to represent money like a checking
account, where money is a contract with a bank. Instead, I'll define money
as a secret key which corresponds to a publicly published public key.

So, I can prove that I own the dollar bill that was published by the
Federal Reserve last week by proving I have the corresponding secret key.

I can give you money by giving you the secret key. But giving money
should have two results: you have it, and I don't. You, as the
recipient, accomplish this by publishing the secret key along with a
new public key, in an anonymous posting to the world. Your posting
declares, "I own this dollar bill and hereby mutate it into this new
dollar bill." Now you have the secret corresponding to this new key,
and the world knows that my old secret is no longer valid.

The usual problem with "money as data" is that you can easily make copies.
This is solved by the fact that the money transfer really isn't complete
until the anonymous posting, and when that happens, the first posting to
reveal the secret key gets possession of the cash.

I don't have any interesting solution to the money-creation problem.
A bank will have to publicly set aside real cash which corresponds to
the electronic cash it signs "creation messages" for.

There is a problem that cash transactions can be traced. One solution
is the use of money-laundering servers.

I really like the concept of "money as a secret". All it requires is a
global consensus on what dollar bills are in existence at any one time. This
could be achieved by a global secure posting system with guarantees that
everyone sees posts in the same sequence.

I'll admit, I've replaced a not-so-hard problem (electronic checking
accounts) with a harder problem (a newsgroup that's guaranteed to look
the same to everybody in the world, where the guarantee is made without
a central authority). But I think secure netnews is a useful goal in
its own right, as well as providing the basis for an interesting
electronic cash scheme.


Secure Netnews
--------------
It seems like a useful critter: a newsgroup which can guarantee that
every reader receives the identical articles in the identical order.
Anonymous posting is also a useful (and easy-to-implement) feature,
which is valuable in the electronic-cash case.

One of the main challenges to deal with is a "network partition" where
some fraction of the distribution network is cut off from the rest.
In order to guarantee consistency, the procedure must determine
which partition contains a majority of machines, or it must "stall"
until contact can be regained with the rest of the network.

The basic technique I propose to achieve this is a two-stage news
distribution process, where first the news is distributed to the entire set
of receiving machines, then signatures are collected from all receivers and
distributed in the same way as a regular news article. Only when signatures
from at least half the newsreading machines have been received, will a
receiver be assured that the article is authentic.

Since this involves a large amount of signature traffic, the method can be
modified to get signatures only from a random sample of receiving machines;
only when it is shown with high probability that more than half of the
network has received the correct article will it be accepted by each
individual machine as correct. Until this happens, no further articles will
be processed; instead, if there is some question as to whether at least half
the network has seen the article, more and more machines will be polled until
certainty is attained. The philosophy is that it's better to stall than it
is to allow two inconsistent versions of the world to exist. It's slightly
tricky to determine which machines must participate in the random sample
while preventing cheating: a reasonable choice would be to tell receiving
machines to "respond if the first 7 bits of the MD5 digest of your signature
of this article are 1111111". Each recipient computes this function and
responds or not; no one else can do the computation.

It is necessary to know exactly what machines are receiving news, in order to
poll them about what news they have received and are willing to sign. New
machines must register themselves by posting to the newsgroup, and must agree
to respond to signature requests within a reasonable window, or they will be
removed from the set of participating hosts. One would probably want to
create a second class of hosts, "read-only", which do not register as part of
the network; such a host does not get a chance to take part in the security
process, but it avoids having to sign messages on demand.

It is also important that confidence be maintained that no half of the
machines on the network are going to get into a cheating coalition together.
Actually, the fraction 1/2 is not graven in stone; it could be made 95% if
desired, but then the whole system would stall if any 5% of participating
machines went off line. In any case, there must be a mechanism to prevent
"flooding" the network with bogus machines for the purposes of cheating.
This is probably best solved using practical real-world constraints.

It might be fun to set up such a system on the Internet, as a test, using
conventional newsgroups and digital signatures.

--Marc Ringuette, mnr@cs.cmu.edu, 10/24/90 and 8/1/92

From Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU Tue Aug 18 16:48:19 1992
Received: from DAISY.LEARNING.CS.CMU.EDU by scss3.cl.msu.edu (4.1/4.7) id AA05504; Tue, 18 Aug 92 16:48:18 EDT
Date: Tue, 18 Aug 1992 16:44-EDT
From: Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU
To: Mark Riordan <mrr@scss3.cl.msu.edu>
Subject: Secure netnews
Status: OR

It just occurred to me that this is absolutely bang-on the right way
to distribute ripem keys. Once you have a secure newsgroup that is
guaranteed to look the same to everybody, you just post to the newsgroup!

You might want to note particularly the part about how to create such
a secure newsgroup with a group of participating hosts and five normal
Usenet newsgroups.

-----

It seems like a useful thing: a newsgroup which can guarantee that
every reader receives the identical articles in the identical order.
Such a newsgroup can be used as the "worldwide consensus reality"
for the purposes of arbitrating disputes. The winner of a race could be
the first one to post there; unlike most newsgroups, "first" and "post"
are well-defined.

One of the main challenges to deal with is a "network partition" where
some fraction of the distribution network is cut off from the rest.
In order to guarantee consistency, the procedure must determine
which partition contains a majority of machines, or it must "stall"
until contact can be regained with the rest of the network.

The basic technique I propose in order to achieve this is a two-stage news
distribution process, where first the news is distributed to the entire set
of receiving machines, then signatures are collected from all receivers and
distributed in the same way as a regular news article. Only when signatures
from at least half the newsreading machines have been received, will a
receiver be assured that the article is authentic, and the article is
given the next number in the sequence of accepted articles.

It is necessary to know exactly what machines are receiving news, in order to
poll them about what news they have received and are willing to sign. New
machines must register themselves by posting to the newsgroup, and must agree
to respond to signature requests within a reasonable window, or they will be
removed from the set of participating hosts. One would probably want to
create a second class of hosts, "read-only", which do not register as part of
the network; such a host does not get a chance to take part in the security
process, but it avoids having to sign messages on demand.

It is also important that confidence be maintained that no half of the
machines on the network are going to get into a cheating coalition together.

-----

It might be fun to set up such a system on the Internet, using
conventional newsgroups and digital signatures. I've sketched it
out like this:

alt.secure.submitted -- articles are posted here by anyone

alt.secure.packages -- lists of "alt.secure.submitted articles
posted today" are posted here by
participating hosts; articles seen by
more than half the hosts are included
in a "package" to be signed.

alt.secure.signatures -- signatures of message packages go here.

alt.secure.proofs -- proofs (in the form of lists of signatures)
that package X has been accepted or that
no agreement will be reached in this round.

alt.secure.accepted -- (optional) an archive of the entire
sequence of accepted packages with proofs.

-----

Requiring the agreement of half the machines is a minimum threshold (any less
and two different articles could get accepted at once), but higher thresholds
are reasonable. It may be desirable to require 90% of machines to agree on
an article; if more than 10% are shown to disagree, then the article is
thrown out. You'll note that as the threshold approaches 1, denial of
service is possible by a smaller and smaller clique of machines.

Similarly, as the threshold approaches .5, the "swing vote" becomes
smaller and a small number of cheating machines could (in the presence
of a network partition) cause two inconsistent world views to exist.
A threshold of 75% seems like a good choice.

-----

Since the verification process involves a large amount of signature traffic,
the method can be modified to get signatures only from a random sample of
receiving machines; only when it is shown with high probability that more
than X% of the network has received the correct article will it be accepted
by each individual machine as correct. Until this happens, no further
articles will be processed; instead, if there is some question as to whether
at least X% the network has seen the article, more and more machines will be
polled until the article is accepted or it can be proved that it will never
be accepted. The philosophy is that it's better to stall than it is to allow
two inconsistent versions of the world to exist.

It's slightly tricky to determine which machines must participate in the
random sample while preventing cheating coalitions. If the sampling
algorithm were predictable, small cliques of machines could arrange to be
part of a sample and spoil the results. One solution is to choose the sample
based on a "joint random-number stream" agreed upon in the previous round
which consists of the XOR of all contributions to it; contributions are
encrypted until after the contribution deadline in order to prevent
last-minute fudging of the random number stream.

-----

I'd appreciate references to any interesting relevant papers you've seen,
regarding both the cryptography and the distributed consensus aspects.

--Marc Ringuette, mnr@cs.cmu.edu, 8/1/92