From: Eric Hughes <hughes@soda.berkeley.edu>
Date: Thu, 26 Aug 93 11:32:31 PDT
To: cypherpunks@toad.com
Subject: PROTOCOL: Encrypted open books
Message-ID: <9308261828.AA12936@soda.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


Note: I started this reply last week; I've decided to post what I
know, since I don't have a solution and I've run out of simple ideas
for now.

Hal' criticism that (real) money could leak out of the system is
correct.  The problem is that while the books would still balance,
i.e. sum to zero, some fake depositor would have a negative balance,
the net result of taking out more money than you put in.  Negative
numbers just aren't allowed in double-entry bookkeeping, but they were
allowed in the first protocol set.

The first part of the solution is to allow no private accounts on the
left hand (asset) side of the ledger, in other words, no anonymous
loans.  A protocol for doing anonymous loans could be invented, but
since the first problem is merely to run a money exchange and not more
complicated financial services, this is acceptable.  Most of the money
that left the S&L's was by corrupt loan practices, so I don't consider
this omission a particularly glaring one right now.

Therefore all the private accounts must be on the right hand side,
that is, they are all liabilities.  In layman's terms, the bank owes
you; should you ask for your money, they have to give it to you.  If
we can verify that each of these accounts never goes negative, then we
can be certain that if the books balance, that the amounts of money in
each account are accurate.

Consider this.  If money was transferred from your account to another
one, that transaction shows up in the public encrypted transaction
record.  If you have due diligence over this record, you can assertain
that no transaction was performed against your will.  This case
corresponds to a debit and credit against two customer accounts,
decreasing one and increasing the other.

Another way that money might end up in a fake account if it were
credited with assets.  A debit to an asset increase its value and the
credit to the account increases that value.  This is the case of a
deposit; the bank gets cash (+asset) and credits someone's account
(+account).  Now if they want to give someone money this way, they
have to do so by increasing the assets somehow; in other words, they
money has to come from somewhere.  It didn't come from any of the
customers because they've already verified that.  It didn't magically
appear from one of the other asset accounts because these are all
publically audited.

In summary, we need to ensure that all accounts have positive balance.
Public accounts can be revealed and seen to be positive.  Private
accounts need a cryptographic assurance.

A private account starts off at zero.  This can be publically
revealed.  Then to the encrypted transaction log and the public cyclic
balances we add publication of the private balances in encrypted form
that allows us to verify to the blinded balance is positive.  This
balance is verifiably linked to previous cyclic balances via the
transaction log.  It is therefore linked all the way back to the
beginning balance which was zero.  

Consider all the transaction triples for which the first element is
equal to the private account in question, since the account was
opened.  Take a product of all of the second elements and a product of
all the third elements.  It is clear that these products can be
calculated inductively from the previous cyclic products and the
activity in this cycle.

The products on second and third elements are equal to

	g^( Sum x_i,j,t + Sum r_i,j,t ), h^( Sum r_i,j,t )

where I've added a time index by cycle which was implicit before.  The
notation for the inductive calculation is different, of course, and
also obscures the underlying invariant.

What we want is a certificate that Sum x_i,j,t is positive.  Here it
gets a bit hairy.  There are likely other solutions to this technical
requirement; here is the one I thought up yesterday and today.

I thought I had an idea with promise on how to create such
certificates using quadratic residuosity, but it doesn't work.  I'm
still thinking about it; this certificate doesn't seem impossible to
create, but the standard ideas that I know about in algebraic protocol
design don't seem to work.

If anybody wants to work on this technical point off-line with me,
send me mail.  The math involved is advanced enough that I'd prefer to
post summaries of work rather than all the detailed discussion.

Another non-technical attack on the problem is to require periodic
bank holidays, where all private balances will be revealed to be zero
(preferably), or whatever is actually in the account.  This doesn't
prevent owner fraud, but does put an upper bound on the time in which
to perpetrate it.

Eric