Re: Ecash without a mint, or - making anonymous payments practical

[Bill Stewart]

>On Mon, 27 Sep 1999 [EMAIL PROTECTED] wrote:
>> One small final comment:  physical cash is not really anonymous (bills have
>> serial numbers, and certainly coins may contain secret marks. Why?

At 02:47 PM 09/27/1999 -0700, bram wrote:
>I believe at least part of the reason is to make heists difficult 

It also makes basic counterfeiting more difficult - 
the counterfeiter not only needs to make good-looking banknotes,
but needs to put unique serial numbers, rather than taking
a single banknote and copying it many times.

One effect of changing technology is that serial numbers on cash
did not provide much traceability in the past, but they do in the future.
There have been various proposals to put bar-coded numbers on cash
to make scanning faster and easier, but that's becoming less necessary.
OCR technology for reading numbers has become much more affordable,
and (either now or in the near future) it would not be difficult to 
make ATMs which record serial numbers of cash when dispensing it.

Recording serial numbers used to be a slow manual process used
mainly for kidnap ransom and similar transactions - now it's
almost practical for drug payments and soon for everyday transactions.
Thanks! 
Bill
Bill Stewart, [EMAIL PROTECTED]
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639

Re: Ecash without a mint, or - making anonymous payments practical

[bram]

On Mon, 27 Sep 1999 [EMAIL PROTECTED] wrote:

> One small final comment:  physical cash is not really anonymous (bills have
> serial numbers, and certainly coins may contain secret marks. Why?

I believe at least part of the reason is to make heists difficult - Places
which have loads of nice new bills almost always have them with sequential
serial numbers. There have been many cases of a huge heist getting pulled
off successfully and then the robbers were unable to dispose of the cash
they got because it was too easy to trace.

-Bram

Re: Ecash without a mint, or - making anonymous paymentspractical

[Lynn . Wheeler]

One of the things provided by X9.59 is that it is privacy/anonymous neutral at
point-of-sale &/or merchant webserver ... and in fact, with AADS accounts for
hardgood shipments ... an X9.59-like protocol for address-authorization
transaction... similar to X9.59 for payment-authorization ... not only
eliminates name/address from the payment transactions at a webserver ... but can
also eliminate the name/address at merchant webservers.

merchant webservers get accounts ... for payments by financial institutions ...
and accounts for name/address by shippers (i.e. policing name/address privacy at
a couple dozen shippers is much simpler than policing name/address privacy at 20
million merchant webservers).

Re: Ecash without a mint, or - making anonymous payments practical

[amir . herzberg]

Steve takes an issue with me for my belief that anonymous payments will involve
overhead that may make them less popular than non-anonymous payments. He says,

> There is no reason to expect anonymous system will be more expensive than
> the current book-entry variety, in fact quite the contrary.

Of course, it doesn't make any sense that adding any requirement, esp. a
non-trivial one such as anonymity, will result in a less expensive system. In
particular anonymity does not remove the technical requirements of book-keeping
to prevent duplication.

But, I don't see the point in arguing about this. Let us implement the best
systems - with and without anonymity - and then compare.

Again: I'm _not_ against anonymity, on the contrary (even done a bit of research
in this area). However my main goal is to facilitate commerce in digital goods
and services. I think this is a difficult goal as it is without adding the
anonymity requirement. I feel better knowing that this will not prevent
anonymity solutions, since the hybrid approach allows them to be an extension of
the basic payment scheme.

One small final comment:  physical cash is not really anonymous (bills have
serial numbers, and certainly coins may contain secret marks. Why?

Best Regards,
Amir Herzberg
Manager, E-Business and Security Technologies
IBM Research - Haifa Lab (Tel Aviv Office)
http://www.hrl.il.ibm.com
New e-mail: [EMAIL PROTECTED]
New Lotus notes mail: amir herzberg/haifa/ibm@IBMIL

Re: Ecash without a mint, or - making anonymous payments practical

[Anonymous]

Amir Herzberg writes:
> (btw, I really wonder what's the point of having a technical discussion
> incognito... I hope this is not for a really good/bad reason such as
> you are living in some dark country)

Yes, regrettably many of us do live in a dark country.  Public discussions
of cryptographic technology in a forum which is transmitted overseas
are outlawed, at least if the discussions might lead to the development
of cryptographic software (which would be the case for any but the most
abstract topics).  Such discussions entail the provision of technical
assistance to foreigners and are forbidden by section 744.9 of the United
States Code of Federal Regulations.

Regarding the benefits of combining anonymous and non-anonymous payment
systems:
> Second, and more essential, there are some important advantages e.g. in
> efficiency to non-anonymous payment mechanisms.

Some people have been loudly arguing the opposite, that anonymous payment
systems are inherently more efficient than non anonymous ones.  For one
thing, anonymous systems would tend to have lower record keeping costs
because there are fewer records to keep.  Also, transactions close and
clear immediately because there can be no way to reverse them due to
their untraceability.

Of course these general considerations don't necessarily dominate the
specific details of any particular payment system, and indeed proposed
anonymous systems like DigiCash had a spent coin list and other overhead
which could make them more costly.

Re: Ecash without a mint, or - making anonymous payments practical

[Steve Schear]

At 01:36 PM 9/26/99 +0300, [EMAIL PROTECTED] wrote:
>There are two reasons. First, as you say below, there is simply the reality of
>there being multiple systems. Second, and more essential, there are some
>important advantages e.g. in efficiency to non-anonymous payment mechanisms.
>BTW, non-anonymous here does not necessarily mean `identity-based`, but
rather,
>payment mechanism which do not offer complete, secure anonymity. The
problem is
>of course that if such non-anonymous payment mechanisms are common, it may

I wonder, if anonymous systems should get the lion's share of attention so
that the shoe is on the other foot, how will you see this situation?

>become difficult to convince merchants to support also an anonymous payment
>mechanism (with relatively few customers - assuming most customers will not be
>willing to `pay` for the anonymity). 

There is no reason to expect anonymous system will be more expensive than
the current book-entry variety, in fact quite the contrary.

Furthermore customers choosing the
>anonymous mechanism may attract attention to themselves (I guess the use of
>`anonymous` for e-mail is a good example!). 

No more than cash.

--Steve

Re: Ecash without a mint, or - making anonymous payments practical

[Ben Laurie]

[EMAIL PROTECTED] wrote:
> 
> Anonymous says, (btw, I really wonder what's the point of having a technical
> discussion incognito... I hope this is not for a really good/bad reason such as
> you are living in some dark country),

Frankly, I'm somewhat surprised. There are several really obvious
reasons for having technical discussions anonymously:

a) You don't have to live with any embarassing mistakes you may make
b) If you are discouraged from having the discussion (e.g. by NDA,
contract, disapproving boss), you still can
c) You don't necessarily give away what your company is up to
d) Men in black 'copters find it harder to know who to spirit away :-)

But what most surprises me is that you think identity matters _at all_
in a technical discussion. Surely the discussion stands or falls on its
merit, and nothing else?

Now, if only I'd thought of a) before!

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html

"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
 - Indira Gandhi

Re: Ecash without a mint, or - making anonymous payments practical

[amir . herzberg]

Anonymous says, (btw, I really wonder what's the point of having a technical
discussion incognito... I hope this is not for a really good/bad reason such as
you are living in some dark country),

   > Hmmm... sounds like you are saying that if you had an anonymous payment
   > system you could use it to buy "checks" in your non-anonymous system.
   > But if you already had the ability to make anonymous payments, why bother
   > with your system?  I can go to the bank and buy a cashier's check for
   > cash, then make a payment with it, but I could just as easily have paid
   > with cash directly.

There are two reasons. First, as you say below, there is simply the reality of
there being multiple systems. Second, and more essential, there are some
important advantages e.g. in efficiency to non-anonymous payment mechanisms.
BTW, non-anonymous here does not necessarily mean `identity-based`, but rather,
payment mechanism which do not offer complete, secure anonymity. The problem is
of course that if such non-anonymous payment mechanisms are common, it may
become difficult to convince merchants to support also an anonymous payment
mechanism (with relatively few customers - assuming most customers will not be
willing to `pay` for the anonymity). Furthermore customers choosing the
anonymous mechanism may attract attention to themselves (I guess the use of
`anonymous` for e-mail is a good example!). So I think my simple hybrid proposal
makes sense.

   > Of course in practice it is helpful to have money changers who can
   > convert between different payment systems, since there are so many
   > competing proposals in the world.

Agreed.

   > > We actually will have the necessary APIs in merchant and buyer to allow
   > > integration of such an anonymous payment mechanism with the next release
   > > of IBM Micro Payment (1.3, next month). We may later on implement this
   > > ourselves if customers are interested, but frankly I prefer to see others
   > > implementing it; for one reason, as you know, there are multiple patents
   > > regarding anonymous payments, so it will be a pain to do this (in IBM).

   > http://www.ecoin.net/mmdh is a project based on Wagner blinding which
   > is thought to escape patent protection.  Perhaps this would be a good
   > starting point for a blind payment system.  Are your APIs going to
   > be public?

Thanks for the pointer. Of course, as long as the anonymity is provided by
somebody else,  I don't need even to worry about the patents... so much the
better...

And yes, of course we're going to publish our APIs. We actually published also
the APIs for version 1.2 (see the manuals in our site) but then, version 1.3 is
almost a complete re-write of the system and in particular we've dramatically
improved the APIs - so better wait for them. We hope to be able to publish them
in time for the IETF BOF on Micro Payments (BTW I'm still looking for
presentations and interest in this event - let me know if you want to present,
or event just confirm to me that there is interest in the BOF and in at least us
proposing our protocols). Discussions of the BOF are in [EMAIL PROTECTED]

Best Regards,
Amir Herzberg
Manager, E-Business and Security Technologies
IBM Research - Haifa Lab (Tel Aviv Office)
http://www.hrl.il.ibm.com
New e-mail: [EMAIL PROTECTED]
New Lotus notes mail: amir herzberg/haifa/ibm@IBMIL


Anonymous <[EMAIL PROTECTED]> on 24/09/99 00:44:47

Please respond to Anonymous <[EMAIL PROTECTED]>

To:   [EMAIL PROTECTED], micropay@IBMIL
cc:(bcc: Amir Herzberg/Haifa/IBM)
Subject:  Re: Ecash without a mint, or - making anonymous payments practical




Amir Herzberg says,
> Anonymous says,
>
> > It is still worth considering how to create anonymous payment systems
> > which could be more compatible with other elements of present day society.
>
> I think we can do this, indeed, we can achieve an even stronger goal:
> a payment mechanism that will support anonymous payments for people
> so wishing, while allowing other people to use non-anonymous payments
> (which will always have some advantages), without allowing merchants to
> identify the anonymity-seekers.

Yes, of course you could add identification to an anonymous payment
system simply by having people reveal their identities.  Anonymity
infrastructures offer users the option to hide their identities, but
they can't stop people from revealing pseudonyms or true names.

> The method is simple and can use any anonymous payment mechanism. Consider
> for simplicity a buyer, seller and a billing server (payment system
> provider - bank, telco, etc. - `billing system` is the term we use
> for this party in IBM Micro Payments). The payment system supports
> pre-certified payments, which are payments (to the seller) signed
> directly by the bi

Re: Ecash without a mint, or - making anonymous payments practical

[Anonymous]

Amir Herzberg says,
> Anonymous says,
>
> > It is still worth considering how to create anonymous payment systems
> > which could be more compatible with other elements of present day society.
>
> I think we can do this, indeed, we can achieve an even stronger goal:
> a payment mechanism that will support anonymous payments for people
> so wishing, while allowing other people to use non-anonymous payments
> (which will always have some advantages), without allowing merchants to
> identify the anonymity-seekers.

Yes, of course you could add identification to an anonymous payment
system simply by having people reveal their identities.  Anonymity
infrastructures offer users the option to hide their identities, but
they can't stop people from revealing pseudonyms or true names.

> The method is simple and can use any anonymous payment mechanism. Consider
> for simplicity a buyer, seller and a billing server (payment system
> provider - bank, telco, etc. - `billing system` is the term we use
> for this party in IBM Micro Payments). The payment system supports
> pre-certified payments, which are payments (to the seller) signed
> directly by the billing server. In this case, the buyer's identity
> obviously does not need to appear in the pre-certified payment (it
> is simply a payment - like a check - from billing server to seller).
> So all the buyer really does is `buy` this pre-certified payment. Now,
> obviously, if the billing system allows, the buyer may use anonymous
> payment protocol to buy the pre-certified payment, in which case (and
> assuming all communication is anonymized) we have complete anonymity
> (from billing system and from seller).

Hmmm... sounds like you are saying that if you had an anonymous payment
system you could use it to buy "checks" in your non-anonymous system.
But if you already had the ability to make anonymous payments, why bother
with your system?  I can go to the bank and buy a cashier's check for
cash, then make a payment with it, but I could just as easily have paid
with cash directly.

Of course in practice it is helpful to have money changers who can
convert between different payment systems, since there are so many
competing proposals in the world.  So it would be useful if you could in
fact accept some kind of anonymous payment system and translate it into
your own currency.  This is more of a financial problem than a technical
one, though.

> We actually will have the necessary APIs in merchant and buyer to allow
> integration of such an anonymous payment mechanism with the next release
> of IBM Micro Payment (1.3, next month). We may later on implement this
> ourselves if customers are interested, but frankly I prefer to see others
> implementing it; for one reason, as you know, there are multiple patents
> regarding anonymous payments, so it will be a pain to do this (in IBM).

http://www.ecoin.net/mmdh is a project based on Wagner blinding which
is thought to escape patent protection.  Perhaps this would be a good
starting point for a blind payment system.  Are your APIs going to
be public?

Re: Ecash without a mint, or - making anonymous payments practical

[amir . herzberg]

Anonymous says,

> It is still worth considering how to create anonymous payment systems
> which could be more compatible with other elements of present day society.

I think we can do this, indeed, we can achieve an even stronger goal: a payment
mechanism that will support anonymous payments for people so wishing, while
allowing other people to use non-anonymous payments (which will always have some
advantages), without allowing merchants to identify the anonymity-seekers.

The method is simple and can use any anonymous payment mechanism. Consider for
simplicity a buyer, seller and a billing server (payment system provider - bank,
telco, etc. - `billing system` is the term we use for this party in IBM Micro
Payments). The payment system supports pre-certified payments, which are
payments (to the seller) signed directly by the billing server. In this case,
the buyer's identity obviously does not need to appear in the pre-certified
payment (it is simply a payment - like a check - from billing server to seller).
So all the buyer really does is `buy` this pre-certified payment. Now,
obviously, if the billing system allows, the buyer may use anonymous payment
protocol to buy the pre-certified payment, in which case (and assuming all
communication is anonymized) we have complete anonymity (from billing system and
from seller).

We actually will have the necessary APIs in merchant and buyer to allow
integration of such an anonymous payment mechanism with the next release of IBM
Micro Payment (1.3, next month). We may later on implement this ourselves if
customers are interested, but frankly I prefer to see others implementing it;
for one reason, as you know, there are multiple patents regarding anonymous
payments, so it will be a pain to do this (in IBM).


Best Regards,
Amir Herzberg
Manager, E-Business and Security Technologies
IBM Research - Haifa Lab (Tel Aviv Office)
http://www.hrl.il.ibm.com
New e-mail: [EMAIL PROTECTED]
New Lotus notes mail: amir herzberg/haifa/ibm@IBMIL

Re: Ecash without a mint

[Anonymous]

On Mon, 20 Sep 1999 at 01:52:43PM -0700, Wei Dai wrote:
> On Mon, Sep 20, 1999 at 09:02:17PM +0200, Anonymous wrote:
> > Yeah, neat idea!  With b-money, newly minted value goes directly into
> > someone's account, but if it was used instead to create an anonymous
> > coin you would have an accountless system.  In that case you don't even
> > need the mint for the initial phase.
>
> The account-based aspect is what enables the contract enforcement in
> b-money. You would lose that by going to an accountless system. What is the
> advantage of not having accounts (other than payer-payee unlinkability,
> which can be obtained by using Sanders-Ta-Shma as the payment subprotocol 
> of b-money)?

It is good that b-money is able to include contract enforcement in the
protocol.  However that means that it is a more ambitious and inclusive
system and so more of society would have to change in order to use it.
It is still worth considering how to create anonymous payment systems
which could be more compatible with other elements of present day society.

If all you want is an anonymous payment system, it seems that avoiding
accounts can increase privacy.  There will be ideally no linkage between
any set of transactions with a pure anonymous cash system.  With accounts
there might be some cumulative knowledge about spending patterns.

In the proposal to use the Sanders-Ta-Shma exchange with b-money, is
there a problem that payer and payee can be linked because they transfer
exactly the same amounts of money, if rounds have small granularity?

> > One problem though.  For b-money, you have to expend resources equal
> > in value to the money you generate.  That means that if you wanted to
> > re-create the U.S. money supply of a trillion dollars, you would have
> > to waste a trillion dollars worth of computing cycles.  Not exactly an
> > attractive proposition.
>
> Unfortunately it seems unavoidable unless you have a trusted party control
> the money supply. You'd have the same problem if you used gold as the money
> supply, for example.

There could be a transition period during which some parties were trusted
(bankers, perhaps).  Maybe there could be a special bank account that
people can make conventional payments to and get b-money in return.
Everyone would need to be able to monitor payments into that account.

> > What you might want to do, then, is to let people convert other forms
> > of money into these ecoins to get things going initially.  Then use
> > b-money to create more if they are needed over the long term.  This way
> > you avoid the huge startup costs with b-money.
>
> How do you propose letting people do this without having a trusted party?
> The only thing I can think of is broadcasting video clips of people burning
> their paper money, but it would be hard to verify the authenticity of the
> money being burnt.

Today's payment system does depend on trusted financial intermediaries
and it works OK most of the time.  We could continue to rely on similar
trusted parties through the transition period.  Some level of fraud
may be unavoidable, but with care it should be possible to minimize it.
After the transition then there is no longer a need for trust.

Re: Ecash without a mint

[David Jablon]

A slight correction is noted, which isn't very relevant to the
ZK proofs in the proposed payment system.

At 11:41 AM 9/20/99 -0700, bram wrote:
> Interactive ZK proofs can be made non-interactive by generating an
> encoding of the information offered by the prover, and using the bits of
> the secure hash of that as the challenges by the provee.

Not all interactive ZK proofs can be converted into non-interactive
ZK proofs.  For example, in ZK proofs of low-entropy knowledge,
non-interactive proofs are not possible.

---
David P. Jablon
[EMAIL PROTECTED]
www.IntegritySciences.com

Re: Ecash without a mint

[Robert Hettinga]

At 1:52 PM -0700 on 9/20/99, Wei Dai wrote:


> Unfortunately it seems unavoidable unless you have a trusted party control
> the money supply.

Yes. In business, they call this quaint phenomenon "financial 
intermediation". ;-).

Seriously, if you have *lots* of intermediaries in competition, the 
situation is *quite* stable and very robust, which is the whole point 
of free banking.

Cheers,
RAH
-
Robert A. Hettinga 
The Internet Bearer Underwriting Corporation 
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

Re: Ecash without a mint

[Wei Dai]

On Mon, Sep 20, 1999 at 09:02:17PM +0200, Anonymous wrote:
> Yeah, neat idea!  With b-money, newly minted value goes directly into
> someone's account, but if it was used instead to create an anonymous
> coin you would have an accountless system.  In that case you don't even
> need the mint for the initial phase.

The account-based aspect is what enables the contract enforcement in
b-money. You would lose that by going to an accountless system. What is the
advantage of not having accounts (other than payer-payee unlinkability,
which can be obtained by using Sanders-Ta-Shma as the payment subprotocol 
of b-money)?

> One problem though.  For b-money, you have to expend resources equal
> in value to the money you generate.  That means that if you wanted to
> re-create the U.S. money supply of a trillion dollars, you would have
> to waste a trillion dollars worth of computing cycles.  Not exactly an
> attractive proposition.

Unfortunately it seems unavoidable unless you have a trusted party control
the money supply. You'd have the same problem if you used gold as the money
supply, for example.

> What you might want to do, then, is to let people convert other forms
> of money into these ecoins to get things going initially.  Then use
> b-money to create more if they are needed over the long term.  This way
> you avoid the huge startup costs with b-money.

How do you propose letting people do this without having a trusted party?
The only thing I can think of is broadcasting video clips of people burning
their paper money, but it would be hard to verify the authenticity of the
money being burnt.

Re: Ecash without a mint

[Wei Dai]

On Mon, Sep 20, 1999 at 03:46:39PM +0100, Adam Back wrote:
> [1] Wei Dei's b-money protocol: http://www.eskimo.com/~weidei/bmoney.txt

BTW, the correct URL is http://www.eskimo.com/~weidai/bmoney.txt.

Re: Ecash without a mint

[bram]

On Mon, 20 Sep 1999, Adam Back wrote:

> - is the ZK proof interactive?  If so this would place communication
>   restrictions on spending -- payer and payee would need to be
>   simultaneously online.

Interactive ZK proofs can be made non-interactive by generating an
encoding of the information offered by the prover, and using the bits of
the secure hash of that as the challenges by the provee.

-Bram

Re: Ecash without a mint

[Anonymous]

> How communication and computationally intensive is the ZK proof as a
> function of the coin list length?  Could the proof be used in a
> practical system?

According to the Crypto 99 paper, the ZK proof takes resources O(log^2(N)),
where N is the number of coins issued.  However they are vague about the
details of the proof itself.  They also mention an alternative way of
proving list membership due to Benaloh and de Mare, which would be of
order log(N), very efficient.

> (I am thinking that the coin list will grow indefinately as more coins
> are used as the server nodes can't by design tell which coins are
> spent).

You can deal with this by starting up a new issued coin list periodically.
Then the spender has to indicate which list his coin is in, which leaks
info about the age of the coin, or everyone needs to exchange old coins
for new ones when the lists change over.  A similar idea can be used
for the spent coin list.

> Couldn't one have a mintless method of injecting new coins into the
> system by using hashcash in a similar way to that proposed by Wei Dei
> in b-money [1]?
>
> ie. the protocol you describe includes the step that upon submitting a
> ZK proof of knowledge of blinding factor for one of the coins in the
> coin list your can at the same time submit a replacement fresh coin.
>
> A deposit step could be that upon submitting an n-bit hashcash token
> (a n-bit partial hash collision on a chosen string) you can also
> submit a new coin of the corresponding denomination.  Appropriate
> values for n could be chosen using the mechanisms Wei suggests in
> b-money.

Yeah, neat idea!  With b-money, newly minted value goes directly into
someone's account, but if it was used instead to create an anonymous
coin you would have an accountless system.  In that case you don't even
need the mint for the initial phase.

One problem though.  For b-money, you have to expend resources equal
in value to the money you generate.  That means that if you wanted to
re-create the U.S. money supply of a trillion dollars, you would have
to waste a trillion dollars worth of computing cycles.  Not exactly an
attractive proposition.

What you might want to do, then, is to let people convert other forms
of money into these ecoins to get things going initially.  Then use
b-money to create more if they are needed over the long term.  This way
you avoid the huge startup costs with b-money.

> - is the ZK proof interactive?  If so this would place communication
>   restrictions on spending -- payer and payee would need to be
>   simultaneously online.

In the paper it is interactive, but they are presenting a Chaum style
offline system which has the user's identity encoded in each coin
such that it is revealed if you double spend.  With an online system
this is not necessary and then it looks like the ZK proof could be
non interactive.

> - what about propagation delays in updating the spent coin list --
>   can't have people reusing the ZK proof at different servers
>   simultaneously to get more coins than they are due, or having the
>   payer deposit it simultaneously with the payee.  This could make the
>   deposit step quite slow depending on network connectivity of
>   servers.

Yes, clearly the network servers would need to have extreme connectivity
by today's standards.  There must be an atomic update step so that the
coin recipient can know that he has deposited his coin successfully
and got his replacement into the database before he ships the goods.
This would have to happen every time anyone makes a purchase online.
The volume of such transactions is mind boggling.

Re: Ecash without a mint

[Wei Dai]

On Mon, Sep 20, 1999 at 03:46:39PM +0100, Adam Back wrote:
> How communication and computationally intensive is the ZK proof as a
> function of the coin list length?  Could the proof be used in a
> practical system?

The complexity is polylog in the number of coins, but unfortunately it is
not practical yet because the (noninteractive) ZK proofs use generic ZK
constructions rather than known efficient ZK proof systems (though the
authors say they are working on a practical version). 

> Couldn't one have a mintless method of injecting new coins into the
> system by using hashcash in a similar way to that proposed by Wei Dei
> in b-money [1]?

I propose as an alternative to the above that (when it becomes practical) 
we use Sander and Ta-Shma's protocol as a subprotocol in b-money to obtain
payer-payee unlinkability. (Payers and payees in b-money are pseudonyms,
but in the basic protocol the pseudonyms can be linked by payer-payee
relationships.)  Each round the Sander-Ta-Shma protocol is run, and whoever
wants to pay converts b-money into coins and send them to payees. Payees
must convert coins back into b-money during the same round (the coin
database is wiped between rounds).  This way the size of the distributed
database is minimized.

BTW Sander and Ta-Shma's paper is available at
http://www.icsi.berkeley.edu/~sander/publications/audit.ps.

Re: Ecash without a mint

[Adam Back]

Anonymous writes:
> Consider the following system, not yet completely practical, but perhaps
> with some more work it could be made so.  Features:
> 
>  - A "mint" is used only to create the initial allocation of ecash.
>After that it is not needed.
> 
>  - Complete anonymity as with Chaum ecash.
> 
>  - No single point of failure, distributed public databases are used.
> 
>  - No secret keys to be lost or stolen.
> 
> [...]
> 
> The issued coin list is maintained as a hash tree and so the zero
> knowledge proofs of membership are (possibly, barely) feasible.  The need
> for potentially cumbersome ZK proofs is one of the weak points of this
> proposal.

Very interesting proposal.

How communication and computationally intensive is the ZK proof as a
function of the coin list length?  Could the proof be used in a
practical system?

(I am thinking that the coin list will grow indefinately as more coins
are used as the server nodes can't by design tell which coins are
spent).

> This feature, of being able to receive money and immediately create
> new, unrelated coins, is the enhancement that allows us to do away with
> the mint.  The mint is only needed to inject new coins into the system;
> otherwise the money supply stays constant.

Couldn't one have a mintless method of injecting new coins into the
system by using hashcash in a similar way to that proposed by Wei Dei
in b-money [1]?

ie. the protocol you describe includes the step that upon submitting a
ZK proof of knowledge of blinding factor for one of the coins in the
coin list your can at the same time submit a replacement fresh coin.

A deposit step could be that upon submitting an n-bit hashcash token
(a n-bit partial hash collision on a chosen string) you can also
submit a new coin of the corresponding denomination.  Appropriate
values for n could be chosen using the mechanisms Wei suggests in
b-money.

Other questions:

- is the ZK proof interactive?  If so this would place communication
  restrictions on spending -- payer and payee would need to be
  simultaneously online.

- what about propagation delays in updating the spent coin list --
  can't have people reusing the ZK proof at different servers
  simultaneously to get more coins than they are due, or having the
  payer deposit it simultaneously with the payee.  This could make the
  deposit step quite slow depending on network connectivity of
  servers.

Adam

[1] Wei Dei's b-money protocol: http://www.eskimo.com/~weidei/bmoney.txt