🚀 go-pugleaf

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.  For instance, a secure newsgroup
would be an excellent way to distribute public keys.  You just post to
the newsgroup, and when you see it appear, you're guaranteed that
everybody sees it the same way you do.

Later in the article, I sketch out how to implement a secure newsgroup
on top of a few insecure usenet newsgroups.  I'm serious -- this could
be a useful and interesting hack!

-----

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.

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.

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.  Any non-participating machine
can still read the group; it just can't participate in the security process.

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

I should point out that there is no centralized server in this scheme.
Individuals post articles, post signatures, and post "proofs" that a given
article has been accepted or rejected by more than half the participating
hosts.

-----

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
				   most of 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.
				   One proof is enough, but anyone can post
				   one.

   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.

-----

What do you think?  See any gaping holes?  Want to flesh it out and 
give it a try?


    --Marc Ringuette, mnr@cs.cmu.edu