> 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.
