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