From: Matt Carpenter <mcarpent@Dusk.obscure.net>
Date: Wed, 24 Jul 1996 21:43:32 +0800
To: cypherpunks@toad.com
Subject: Re: E-Cash promotion idea
Message-ID: <199607241015.FAA06111@Dusk.obscure.net>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----


Lucky Green wrote:
>At 23:19 7/22/96, Anonymous wrote:
>
>>How about getting the CyberCafes to accept ecash?  Just pull out your
>>Newton/HP48/PDA and point the IR beam at the cash register.  Now that's
>>an ecash application I'd like to see!!
>
>So would I. And one day we will. Though not not on the HP48.

Actually I've been doing some more thinking about this recently, and it may
be possible even on an HP48, if you're willing to limit your spending 
flexibility a little in order to gain the advantages provided by ecash.

A couple months ago there was a similar thread on using ecash with Newtons,
PDA's, palmtops, and so on.  I mentioned an idea of having an "ecash ATM" on
an online machine, which would allow you to download ecash coins to your
portable device.  You could then carry the ecash around with you.  This way
you wouldn't need a full blown ecash client on the portable, just a simple
program that would ask you for the payment amount and send off the
appropriate coins.  The main problem with the idea seemed to be that I
suggested getting change from the merchant.  Ian Goldberg pointed out that
with the current ecash protocol, accepting change not only eliminates your
anonymity, but that you also have to go online to make sure you aren't being
cheated.

Anonymous's post got me to thinking about this again.  Since I know
many of you are more knowledgeable about ecash than I, let me know if you
can add more detailed information or see any problems with the approach below 
(other than a certain lack of convenience, which may be the major issue 
with this approach). 

What if we just forget about change?  One of the neat things about ecash is
that it allows for coins of (fairly) arbitrary values.  We can use this to
our advantage, since we can guarantee that we can make a single payment of 
any value with a small number of coins.  (People familiar with ecash
know all this already I'm sure, but I'll describe it in some detail for 
others who may not have thought about it as much).

Here's the basic formula:

     Number of required coins = ceiling( log2( P/L ) )

where P is the maximum payment amount available to spend on a single 
transaction, and L is the "loss limit", or the upper limit of money we are 
willing to lose on a single transaction.  For example, if we want to be 
able to make a $50 payment to the nearest cent ($.01), we need:

     ceiling(log2( 50/.01)) = 13 coins

So with only 13 coins, we are guaranteed to be able to make any single
payment from $.01 - $50 to the nearest cent.  Since we are dealing with base
2 logarithms, if we increase the maximum amount to $100, we only need a
single additional coin.

The algorithm to generate the coin values is simple.  Basically you start at
P and just keep dividing by two until you reach L.  For the above example,
we could use 13 coin values of: $25, $12.50, $6.25, $3.13, $1.57, $0.79,
$0.40, $0.20, $0.10, $0.05, $0.03, $0.02, and $0.01.  This actually gives us
a total of $50.05 due to rounding, but we are guaranteed of being able to
pay to the nearest cent any amount between $0.01 to $50.00, with multiple
possible combinations for certain values. 

Now, I'm not sure what the average size of an ecash coin is (anybody?), but
the few I've seen floating around the net in "ASCII armor" have been around
500-600 bytes (of ASCII text), I think.  So guessing (hopefully
conservatively) that the average coin size is about 1k or less, then we need
about 13k worth of storage space to make any single payment of $50 or under.

We can do a little better if we are willing to lose a little money in the
transaction. For instance, if L=$0.10, then we only need 9 coins (and we
will lose less than $0.10 in the transaction).  For L=$0.40, 7 coins.
Of course this probably isn't cost effective in most cases, but might
potentially be useful, if you are tight on storage space or something. 

So, with a storage space of approximately 64k (close to 5 x 13k), we are 
guaranteed of being able to make any 5 payments of $50 dollars of less, to 
the nearest cent.

Of course, we also need some software, but it should be fairly simple and
small.  Just a little database to keep track of which coins we have, and a
simple user interface to prompt for payment amount, select the appropriate
coins, and beam them off to the payee (probably also a transaction log, and
encryption capabilities).


A few points:

* This should be doable with current technology.  All we need is a fairly
small storage space, say 128K or less (more gives us more flexibility), and
something like IR, wireless, or even a serial port connection via cable to
send the coins to the payee.  This seems to allow things like Newtons, HP
Palmtops (and perhaps higher end calculators), USR Pilots, etc. to be used
as unconnected ecash "wallets".  This assumes the payee is online, since
they will want to clear the coins to make sure they are good. 

* This is less expensive than requiring both parties to be online.  The
payee doesn't need to provide a net connection to the payer; the payer
doesn't need to utilize memory space (and possibly additional hardware) 
for more complicated software to carry out the online transactions and
payment generation.  All the payee needs (besides the standard ecash
software and a net connection) is a method of receiving coins, like IR, and
some fairly simple software.

* Although one may be carrying around $250 with the above example, it is much
safer than carrying cash.  Ecash maintains the advantage of cash-like 
anonymity,  but we can keep a back-up of the money on our home machine, 
and we can encrypt the coins we carry to avoid having them spent by someone 
else, in case our portable device is lost or stolen. (Of course we do lose a 
possibly expensive portable device.)

* With the proper software and connections to the "ecash ATM" we can have
our portable device automatically recharged when we get home (and also
update the records of which coins were spent).  The ATM also gives us
complete control over our spending configurations.  There could even be
several default set-ups for frequently used cases, each assigned to a single
button.  Just connect your portable device, click a button, and you're ready
to go. For example, if you are going to work, you might generally want to
have the capability of several smaller payments for snacks, lunch, and
such.  For grocery shopping you may want a few larger payments, etc.  Also
the software could automatically keep track of your purchases (like a credit
card statement, or checking account log, but you'd be the only one who has
access to it).  Plus you don't need to run off to find an ATM; you can get
cash from "the comfort and privacy of your own home". 

* The main problem seems to be the loss of flexibility.  After you make your
maximum number of guaranteed payments you may have money left over, but it
may not be useful for buying what you want.  You may only have a $25 coin
left to purchase that $1.00 item.  Personally, as a possibly paranoid
technophilic cypherpunk, I don't see this as a major problem.  It means you
have to plan ahead a bit, but it gives you the same anonymity as cash, with
less chance of having you're money lost or stolen.  Those with PDD (Paranoia
Deficit Disorder (cypherpunks, are there drugs to treat this? :-)) may not
have the same view, and be more likely to use less private, more
"convenient" methods of payment.  But with the proper software setup and
user interface, this approach could probably be made acceptable to many.

* I'm not sure how easy this would be with the existing ecash software.
Browsing over the ecash API (http://www.digicash.com/api/Home.html), I see 
there is a EC_pocket_begin_withdrawal() function which looks like it may
automatically do something similar to the guaranteed payment thing I
described above (I've been salivating over the ecash API for a while, but 
haven't actually had to time to play with it yet).  Things may get tricky if
you pick funky values of L, the "loss limit".


In any case, it seems like this would be possible, even on an HP48.  Probably
not all that useful/usable though until you move up to something a little
more powerful (how much memory does the HP48 have? I have an old HP28S with
32k, so I'm guessing the '48 has more than that).

Once I finish up my thesis, find a job, and find some free time (hopefully
all within the next month and a half :-) I plan to play with this idea.
Unless someone else beats me to it, or there is something important I'm
missing.  Comments?

- --Matt

- --
mcarpent@mailhost.tcs.tulane.edu

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMfX32ijtJAMyBnp9AQGD+gf/TOe/ouunmhRz7jL+y65iqU57OaZAK1g0
gLIRDFQDTYMX7387FMBKlQ66RMJx4K80lW59oCAaa3/GyBDZR6Kn9bj2m7aZbYkL
4UDV7HoSJrV8qJv08HXnPibi7kmv+bAztHOAx7M7qo5qUayYCFrMeib65ksrrQYY
nnlnCPfLWAPMHeFYUSA3fv9XwQB9NZVSCgr8Z2vhnfCAERqLLukaXHJq9InSPmWw
XFIdU1x/cPzOUJx7rxth6qBonz5DD9AMof9Qqk8VY/AzohqHylKirog/IJRTefNl
p1xEdI/iBhH3m3azvNhtkEIl0MAzBGU26hBIjB2P9P+08shtMfznow==
=vR9P
-----END PGP SIGNATURE-----