PROTOCOL: Encrypted open books

[tcmay@got.net (Timothy C. May)]

>Date: Thu, 26 Aug 93 11:28:14 -0700
>From: Eric Hughes <hughes@soda.berkeley.edu>
>To: cypherpunks@toad.com
>Subject: PROTOCOL: Encrypted open books
>Status: OR
>
>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