CS 2360 Assignment 3: Due Midnight Feb 6

Digital Cash

This is assignment is a tribute to David Chaum, the cryptologist who invented digital cash in the 1980's. If you would like more information about digital cash, cryptography, and/or David Chaum, please see me and I can provide you with the the appropriate references. All of my discussion of this material comes from the book Applied Cryptography by Bruce Schnier (available at any decent bookstore!).

This assignment is an exercise in abstraction: You should seek to implement as abstract a solution as possible, because you don't know all the details! If you do your work carefully and abstractly, your solution should be easily modifiable, if presented with a more complex scenario later....

Let us assume that at some point in the not-too-distant future all cash as we know it is eliminated by the government by law. They now make it a requirement that all financial transactions occur electronically over the (just built) information superhighway (or as it known at the time by the populace, "the Information Ho Chi Min trail"). The problem is that now the government can track all purchases made by its citizens via credit (or ATM) cards. This is clearly not a good property, so here you come to the rescue!

You've decided that what the country needs is a form of digital cash. This "digicash," as it is often known, will not violate the law requiring all funds transfers to be electronic but yet will preserve the two good properties of the old form of physical cash:

It is anonymous; anyone can buy anything from anyone with it without the transaction being traced.
It is close to impossible to commit fraud (forgery) with it. This is (also) the reason that almost everyone accepts it without question. Further, the penalties for fraud are so severe that it is unlikely anyone would even attempt fraud as the gain is not worth the risk.

Why would you still want cash in the brave new world of the Information H.C.M. Trail?

You want to commit various felonies involving the exchange of (untraceable) monies, such as fraud, bribery of public officials, drug buying/selling, etc.
You want to purchase something that your employer (or for that matter anyone) might consider questionable and you don't want there to be a record of it. Drugs (see above) are a special case of this as they are illegal. But, more close to home, you might have a employer who doesn't approve of certain movies (say, Last Tango In Paris) and you'd rather not have your employer be able to trace your transaction.
(Most generally) You don't think it's the government's or anyone else's business what you do with your money.

Now given that we've established that there might interest in digital cash (especially among politicians/drug dealers!), you go to your favorite set of venture capitalists claiming that you know how to make this work and that David Chaum figured out all the mathematics back in the 80's! You say, "All I need is 100 million dollars to build a nationwide system to make it work!" The venture capitalists (read: your TA's) aren't stupid enough however to believe such an idea (not to mention set you up with 100 Megabucks) without a reasonable amount of proof. They want a prototype system; naturally, you should prototype it in Lisp!

They tell you that your prototype should abstract away all the details of the cryptographic system (whew!) that would really be necessary to make all this work, and just implement the basics of the protocols necessary for the digicash systems.

A protocol is sequence of message exchanges between the two parties involved in a transaction (in this specific case, it is always a funds transfer transaction). Here is an example of an existing transaction you are all familiar with:

You give your credit card number to the sales clerk.
The sales clerk gives your number and the amount of the proposed sale to the credit card company.
The credit card company tells the sales clerk "yes" or "no" depending on whether or not the sale is valid.
If the answer is "no", the sales clerk boots you out of the store. The protcol would terminate at this point.
If the answer is "yes", the protocol continues with the sales clerk giving you a receipt with the amount of the sale and a verification number.
You sign the receipt and give a copy to the clerk.

Now, there are some other steps in this protocol that are not shown above, like what does the credit card company do behind the scenes while it is figuring out its answer? What does the credit card company do when it says "yes" or "no"? (Hint: These involves some database work.)

Some more interesting questions come up involving cheating. Some examples are: What happens if you call up the credit card company (or clerk) and claim you didn't really purchase something? What does the company or clerk do to prove you wrong? What do you do if you get a bill at the end of the month that has the wrong amount (or you want to try to falsely claim so)? How does the merchant actually get the money from the credit card company? Most importantly: Who can "cheat" in this protocol and how?

Now, given that we have seen the complexities of this problem for credit cards, how are you going to make all this work for digicash? Luckily, our friend Mr. Chaum has already figured this out a while back. There are several protocols involved in the implementation of digital cash, and I'll spell each of them out individually.

Getting Some Digital Cash

Let's assume you have an account with a major bank, say Citibank. and you want to get some digital cash out. They are willing to give out such cash under exactly one condition: They don't get cheated out of money. (Banks are funny this way.) Given this condition, they really are more than happy to give out digital cash; they don't care what you do with your money, other than cheat them out of theirs.

Here's the physical analogy of the protcol for going to the bank and getting a quick $100 out of your account in digital cash form:

Prepare some number N envelopes beforehand. (N is determined by Citibank in advance.) In each evelope, please a digital cash certificate (D.C.) for $100 and a piece of carbon paper (on top). Write a random, unique string on each D.C. in the appropriate blank; this string is the uniqueness string for that D.C. Seal all the envelopes.
Take your stack of sealed envelopes to the bank, and present them to the cashier.
The cashier opens N-1 of the envelopes, checking to make sure that each certificate is for $100 and that the random, unique strings are different. The opened evelopes and contents are discarded.
If the cashier finds any of the evelopes are not "kosher" he or she calls the cops and you go to jail for ten years! (A stiff price to pay for $100.) This protocol will end if you end up in jail, obviously.
Assuming that all the envelopes check out, the cashier stamps the remaining, unopened envelope on the carbon paper side without opening it. This stamp is the "Citibank Seal Of Approval" and guarantees that this is a valid D.C. The cashier deducts $100 from your account.

At this point, you are have a $100 D.C. with the Citibank seal of approval on it. Any merchant (or congressman!) would be happy to accept your certificant since Citibank guaranteed it.

The astute reader will have noted that there is a problem here: What stops you from just making some photocopies of the D.C.? It would be a license to print money! The very astute reader will have noted that there is also a solution here: the uniqueness string.

Checking Up On Digital Cash

Ok, say you go to your favorite questionable video store, and want to buy Last Tango In Paris. How does the video store place check to make sure that you are using legitimate digital cash when you get up to the counter with your video? Here's the protocol:

Check to make sure the bank's seal of approval is on the D.C. If not, then just don't accept it.
Call up the bank (or their computer) and ask if they have already seen a given uniqueness string and give them the uniqueness string on the D.C.
If they respond that they have not seen the uniqueness string on the D.C. in question, the D.C. is valid.
If they say that have seen the uniqueness string, then the merchant should call the cops and send you to jail for photocopying the D.C!

Note that this is just a check for validity, it doesn't commit the merchant (or you) to spending your D.C. A person who suspicious of the bank looking through his sealed envelope with some sort of spy device when he gets the D.C. can use this information as well! If you call up the bank claiming to be a merchant and check on a given identity string, you know if they are cheating on you or not! (Well, there are some more complex scenarios where you might still be fooled, but this is not a bad approximation...)

Spending Digital Cash

Ok, now the merchant has checked out the D.C. you have presented, how do we actually spend the money?

Assuming the D.C. verifies above, the merchant then asks you to write another random string on the D.C. This string is the identity string which helps everyone involved catch cheaters.
You generate your random identity string and put it on the D.C.
The merchant checks his own database to make sure that he has never seen this identity string before. He needs to do this to protect himself from potential "frame jobs" that would nail him when he got to the bank. If he has ever seen this identity string before, he calls the cops and you would go to jail for a long time. (Probably the merchant would punch you as well, since you are trying to frame him for cheating which could land him the big house!)
If the above step checks out, you leave with your movie, a feeling of security, and (naturally) your change in digital cash!
At some point later the merchant will take the D.C. with him to the bank and tell Citibank to credit his account with $100 and he shows the D.C. as proof.
Naturally, the bank checks (again) to make sure the uniqueness string is still unique and hasn't been used before. If it has, it can consult the identity string to figure out who to send to jail! (See below for details on this).
Assuming that everything is ok above, the bank now puts the uniqueness string in its database along with the matching identity string, and credits the merchant's account with $100.

About how the bank figures out who's cheating: If the uniqueness string has been used but with a different identity string, the purchaser (not the merchant) has been photocopying D.C.'s and should be jailed, but, unfortunately, we will have some trouble finding him, he is using digital cash!. If the same uniqueness string has been used before with the same identity string then its the merchant who is photocopying ("Guards, take him away!") and should be put in the slammer. Keep in mind, that the purchaser shouldn't be able to get away with photocopying if the merchant checks the D.C. for validity before accepting it and take the D.C. to the bank in a timely fashion (like, say, that second!).

Again, the astute reader will note a problem: The success of this system hinges crucially on the inability of any participant to alter D.C.'s after some other participant has made some commitment to it. In a real implementation, cryptography would be used to provide those guarantees, but we are going abstract this issue out of the problem. We are going to implement the higher level solutions and not worry about the details.

Coding This Sucker Up

Overall Directions

All functions are equally weighted.
All functions should take the parameters noted in the order listed.
Everything should be documented and parameter names should be meaningful.
You may need to use the PROGN construct to make some functions work right. We are calling the database functions for effect, so you'll need PROGN to get it work. Further, keep in mind that all DEFUNs have an implicit PROGN.

Before you can get too far, you'll need a general purpose storage facility. I'll give this too you, since it needsd to perform some black magic in its implementation. Keep in mind that you shouldn't be too concerned about how this is implemented, you should be concerned about this code in the abstract. This code is a general purpose storage facility, called "general-database" and it has six functions (plus a helper) that you'll need: (defun general-database-initialize (name-of-database) (set name-of-database nil)) (defun general-database-add (name-of-database key value) (set name-of-database (cons (cons key (cons value nil)) (eval name-of-database)))) (defun general-database-exists-p (name-of-database) (boundp name-of-database)) (defun general-database-contains-p (name-of-database key) (assoc key name-of-database :test #'equal)) (defun general-database-delete (name-of-database key) (set name-of-database (general-database-delete-helper (eval name-of-database) key nil))) (defun general-database-delete-helper (database target result) (cond ((null database) result) ((equal target (caar database)) (general-database-delete-helper (cdr database) target result)) (t (general-database-delete-helper (cdr database) target (cons (car database) result))))) (defun general-database-change (name-of-database target new-value) (if (general-database-contains-p (eval name-of-database) target) (progn (general-database-delete name-of-database target) (general-database-add name-of-database target new-value)))) You can use this to create databases (giving them a name), add things to them, check for the value of things in the database, make sure databases exist, change things in databases, and delete things from a database. You should be sure you understand how to use these functions before going very far on the assignment. Here is an example of their usage: (general-database-initialize 'some-database) NIL > (general-database-add 'some-database 'some-key 'some-value) ((SOME-KEY SOME-VALUE)) > (general-database-add 'some-database 'my-key 'another-value) ((MY-KEY ANOTHER-VALUE) (SOME-KEY SOME-VALUE)) > (general-database-contains-p some-database 'my-key) (MY-KEY ANOTHER-VALUE) > (general-database-contains-p some-database 'bogus-key) NIL > (general-database-contains-p some-database 'some-key) (SOME-KEY SOME-VALUE) > (general-database-add 'some-database "testing 1 2 3" "emergency broadcast") (("testing 1 2 3" "emergency broadcast") (MY-KEY ANOTHER-VALUE) (SOME-KEY SOME-VALUE)) > (general-database-contains-p some-database "testing 1 2 3" ) ("testing 1 2 3" "emergency broadcast") > (general-database-contains-p some-database "TESTING 1 2 3" ) NIL > (general-database-exists-p 'some-database) T > (general-database-exists-p 'bogus-db) NIL >my-db (("some string" "some value") (LYMAN TAYLOR) (IAN SMITH)) > (general-database-delete 'my-db 'lyman) ((IAN SMITH) ("some string" "some value")) > (general-database-delete 'my-db 'ian) (("some string" "some value")) > (general-database-delete 'my-db "some-value") (("some string" "some value")) > (general-database-delete 'my-db "some string") NIL > (general-database-delete 'my-db 'yessir) NIL > (general-database-add 'my-db 'yessir 'ree) ((YESSIR REE)) > (general-database-add 'my-db 'right 'whatever) ((RIGHT WHATEVER) (YESSIR REE)) > (general-database-delete 'my-db 'right) ((YESSIR REE)) > my-db ((YESSIR REE)) > > (general-database-change 'my-db 'lyman 'foobar) NIL > my-db ((YESSIR REE)) > (general-database-change 'my-db 'yessir 'foobar) ((YESSIR FOOBAR)) > my-db ((YESSIR FOOBAR)) > (general-database-add 'my-db 'why 'not) ((WHY NOT) (YESSIR FOOBAR)) > (general-database-change 'my-db 'why 'ask-why) ((WHY ASK-WHY) (YESSIR FOOBAR)) > (general-database-contains-p my-db 'why) (WHY ASK-WHY) Play with these functions for a while to get a feel for them!

Note that the initialize, add, change, and delete functions require that you put a quote (') in front of the name of the database. Further, these functions do not compute a useful value; they are called for their side effects. The contains-p function does not use a quote in front of the name of the database, and further, its result is quite useful! One final caveat, these functions create a global variable which is the name of the database; this may be useful for debugging. The exists-p predicate is there so you can know when to call initialize! You'll need to do this sometimes to get code to work out right.

Note: If you need to remove all the entries in a database, you can just initialize it again.

Part 1

Create some functions that can do the "bookkeeping" necessary for banks to keep track of accounts. Naturally, you should use the general database function above. You only need to implement one bank, so all the accounts can be in the same database. Here are the functions you should write:

bank-account-create: This function should create an new account with a balance of $1000; it should do nothing if there already exists an account with this name. It should take the name of the account as a parameter. This function does not need to compute a useful value.
bank-account-balance: This function should take an account name as a parameter and return the amount in the account by that name. This function should return nil for accounts that don't exist.
bank-account-credit: This function should take the name of an account and an amount as parameters and credit (add) the amount to the account. If the account name is invalid (no such account) this function should do nothing.
bank-account-debit: This is the same as bank-account-debit except it subtracts from the account. You can assume that we will not call credit and debit on an account before we have created it. If they try to withdraw more money than they have, you should use the function ERROR to signal an error. ERROR takes a string as an argument which should explain the error.

Part 2

You should now implement some functions involving the creation of digital cash certificates. You will not be graded on how you implement the digital cash certificate, only if the functions do their jobs or not. This is an abstraction barrier, i.e. you can assume that we will not look beyond the barrier at the implementation of the data structure.

Here are some functions you should write:

digicash-create-certificate: This function should take an argument of the amount of digital cash to put on the certificate (how much is it for). This function should return a D.C. This certificae should contain both the amount and a random uniqueness string. You may find this function useful for generating random uniqueness strings. (defun create-random-string (of-length) (cond ((= of-length 0) (make-sequence 'string 0)) (t (concatenate 'string (make-sequence 'string 1 :initial-element (elt "abcdefghijklmnopqrstuvwxyz0123456789" (random 36))) (create-random-string (- of-length 1)))))) These strings should be at least 10 characters long in your implementation.
digicash-get-amount: This should return the amount of a digital cash certificate given as its input.
digicash-get-uniqueness-string: This should return the uniqueness string of a digital cash certificate.
digicash-create-envelope-set: This function should take a number of envelopes and an amount as its parameters. This function should return a list of digital cash certificates, each one generated by the digicash-create-certificate function with the parameter of the amount.
digicash-same-certificate-p: This function takes two digital cash certificates and returns T or NIL based on whether or not they are equal. Two certificates are equal if they have the same uniqueness string (that's the point!).

Part 3

Now we are starting to really cook! What you need now is a way for various parties in the transactions to have a way to keep track of uniqueness strings they have seen. Use the general database code to construct a set of functions like this:

uniqueness-database-create: This function should create a new (or re-initialize the old) database for a participant to use to keep track of strings they have seen. The parameter should be the name of the database to create.
uniqueness-database-exists-p: This function should take the name of a uniqueness database and return true or false based on whether or not such a database exists.
uniqueness-database-add: This function should take the name of a database and a uniqueness string and add this string to the database of seen strings. Note that since there is not a "value" for these strings to be paired with (in a proper sense) you'll need to make up something.
uniqueness-database-have-seen-p: Normally, I'd make you write this function, but there is a subtle point lurking here about the binding of names to values. I'd like you to just use this function, but have your comments reflect why this code is necessary: (defun uniqueness-database-have-seen-p (db-name target) (if (general-database-contains-p (eval db-name) target) t nil))

Part 4

Given this code, we can start building the protocols discussed above and in class. Let's try the protocol by which a user gets a a D.C. from the bank, and has it stamped. Here are some functions to write.

digicash-stamp: This function should take in an unstamped digicash certificate and return a stamped one. It should do nothing if it finds the D.C. to be already stamped. You can implement this however you want. It will be useful to modify your digicash-create-certificate to indicate that the D.C.'s are unstamped when they are created.
digicash-is-stamped-p: This function should return T or NIL based on whether or not a digicash certificate is stamped. A freshly created digicash certificate should obviously not be stamped!
digicash-remove-envelope: This function should take an envelope set and a D.C. as parameters. This function should use the REMOVE-IF function (with a LAMBDA expression!) and the digicash-same-certificate-p to return another envelope set which does not have the D.C. passed in as a parameter
digicash-check-envelope-set: This function should take a set of envelopes and an amount as parameters. It should examine each one making sure that each one has the amount that it got as a parameter, and that it hasn't seen the uniqueness string before. (Note: This may entail creation of a database for your bank if it doesn't exist yet.) This function should look at ALL envelopes passed to it. Note: each time it looks at an envelope it should note the uniqueness string in its database. If any envelope is bogus, this function should return NIL, otherwise (assuming everything is ok) it should return T.
Note that as you are testing this, the database is filling up with values, so you'll need to watch out for these side-effects.
digicash-get-stamped: This function should take an envelope set, an amount, and a number as parameters. It should return a stamped D.C. of the amount passed in as the amount, which should be the NTH element of the list of envelopes you generate. Use the third parameter with the NTH function to select it. If you find that your envelope set is bogus, you should return NIL.

You will be much happier with your grade, if you write these using any and all functions you have already written as well as functions in this section.

The following piece of code can be used to get digital cash out of the bank:

>(digicash-get-stamped (digicash-create-envelope-set 500 100) 100 6) (100 "in0os4rrpli6lutgex76xrux0wosx6" T) This creates 500 envelopes of denomination 100 with random strings. It claims that they are all 100 denomination, and that the bank should select the sixth one to stamp. Slightly better is: > (digicash-get-stamped (digicash-create-envelope-set 500 100) 100 (random 500)) (100 "1iwr4hwwsnj9cs319o9sm00q8iy77e" T) which picks one of the envelopes of the 500 randomly.

Note that your returned value may be different from mine if you chose to implement your digicash certificates differently from me.

Part 5

Write a driver function called digicash-test which takes an amount and an account name and returns a stamped D.C. of the appropriate denomination, and deducts the amount from the account name mentioned (this will error if this not legal, so you don't have to check this). This function should return the stamped D.C (or NIL if there is cheating) and you may deduct from the account before doing the envelope protocol if you find this easier. You can hard-code the number of envelopes to use and the algorithm for picking the envelope based on your interpretration of paraniod bankers are...

Use the code listed above to guide you on this function! You can assume we won't try to get a certificate with this function unless the person already has an account with the bank via bank-account-create.

Part 6?

If you are adventurous, it is not very hard to hack up the other protocols based on the explanations above... You might try just seeing if you can get it to work... A successful implementation won't get you any more credit, but might get you the admiration of your instructor, TAs, classmates, and David Chaum! You'll need to (naturally) go back and add some more code that handles the signature of the person using the digital cash, and more code to handle the "turning in" of the certificates at the bank... Enjoy!

Back To The CS2360 Home Page

Ian Smith (iansmith@cc.gatech.edu)