Re: [Taler] optimal coin spending

[Jeff Burdges]

On Sun, 2015-12-20 at 10:16 +0100, Christian Grothoff wrote:
> On 12/20/2015 12:00 AM, Jeff Burdges wrote:
> > As I mention in my first mail, if we use a greedy algorithm, then
> > we
> > should run it separately for each mint's denomination set.  It's
> > easy
> > to lose the property of being well suited for the greedy algorithm
> > by
> > taking the union of two mint's denomination sets. 
> 
> Sure, I was expecting us to run the algo for each withdraw operation
> anyway.

We're talking about purchase algorithms, not withdrawal algorithms, but
I suppose you just miss typed.  Yes, we'd need to run for each purchase
operation regardless, but..

If we've multiple mints that support the same auditor and currency,
then we should run the purchase algorithm separately for each mint that
can perform a purchase operation, assuming the algorithm is greedy.  If
I take the union of the denominations issued by two mints, then I'll
frequently create a denomination set that's bad for the greedy
algorithm.

Worse, our deposit fee divided by value heuristic comes from
considering the case where one uses only a single denomination,
dividing the objective function by an approximate price, and ignoring
the term refresh fee divided by price.  It's unwise to ignore this last
term for micropayments.  Imagine: Alice has a mint not meant for
micropayments with only big denominations with deposit and refresh fees
that're small as a fraction.  Bob has a mint specializing in
micropayments with deposit fees that're relatively high as a fraction
of the value, but he offers many denominations and no refresh fees.  A
greedy wallet using this heuristic with both currencies will always
choose Alice's mint over Bob's mint.  Again, we solve this by
considering the denominations for different mints separately. 

Anonymity suffers when spending from multiple mints simultaneously too.

Jeff

signature.asc
Description: This is a digitally signed message part