1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
|
\documentclass{llncs}
%\usepackage[margin=1in,a4paper]{geometry}
\usepackage[T1]{fontenc}
\usepackage{palatino}
\usepackage{xspace}
\usepackage{microtype}
\usepackage{tikz}
\usepackage{amsmath,amssymb}
\usepackage{enumitem}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
% Terminology:
% - SEPA-transfer -- avoid 'SEPA transaction' as we use
% 'transaction' already when we talk about taxable
% transfers of Taler coins and database 'transactions'.
% - wallet = coins at customer
% - reserve = currency entrusted to mint waiting for withdrawl
% - deposit = SEPA to mint
% - withdrawl = mint to customer
% - spending = customer to merchant
% - redeeming = merchant to mint (and then mint SEPA to merchant)
% - refreshing = customer-mint-customer
% - dirty coin = coin with exposed public key
% - fresh coin = coin that was refreshed or is new
% - coin signing key = mint's online key used to (blindly) sign coin
% - message signing key = mint's online key to sign mint messages
% - mint master key = mint's key used to sign other mint keys
% - owner = entity that knows coin private key
% - transaction = coin ownership transfer that should be taxed
% - sharing = coin copying that should not be taxed
\title{Taler: Taxable Anonymous Libre Electronic Reserves}
\begin{document}
\mainmatter
%\author{Florian Dold \and Sree Harsha Totakura \and Benedikt M\"uller \and Christian Grothoff}
%\institute{The GNUnet Project}
\maketitle
\begin{abstract}
This paper introduces Taler, a Chaum-style digital currency using
blind signatures that enables anonymous payments while ensuring that
entities that receive payments are auditable and thus taxable. Taler
differs from Chaum's original proposal in that customers can never defraud anyone,
merchants can only fail to deliver the merchandise to the customer,
and mints can be fully audited. Consequently, enforcement of honest
behavior is better and more timely than with Chaum, and is at least as
strict as with legacy credit card payment systems that do not provide
for privacy. Furthermore, Taler allows fractional and incremental
payments, and even in this case is still able to guarantee
unlinkability of transactions via a new coin refreshing protocol.
Finally, Taler also supports microdonations using probabilistic
transactions. We argue that Taler provides a secure digital currency
for modern liberal societies as it is a flexible, libre and efficient
protocol and adequately balances the state's need for monetary control
with the citizen's needs for private economic activity.
\end{abstract}
\section{Introduction}
The design of payment systems shapes economies and societies. Strong,
developed nation states are evolving towards fully transparent payment
systems, such as the MasterCard and VisaCard credit card schemes and
computerized bank transactions such as SWIFT. Such systems enable
mass surveillance and thus extensive government control over the
economy, from taxation to intrusion into private lives. Bribery and
corruption are limited to elites that can afford to escape the
dragnet. The other extreme are economies of developing, weak nation
states where economic activity is based largely on coins, paper money
or even barter. Here, the state is often unable to effectively
monitor or tax economic activity, and this limits the ability of the
state to shape the society. As bribery is virtually impossible to
detect, it is widespread and not limited to social elites.
ZeroCoin~\cite{miers2013zerocoin} is an example for translating such
an economy into the digital realm.
Taler is supposed to offer a middleground between an authoritarian
state in total control of the population and weak states with almost
anarchistic economies. Specifically, we believe that a liberal
democracy needs a payment system with the following properties:
\begin{description}
\item[Customer Anonymity] It must be impossible for mints, merchants
and even a global active adversary, to trace the spending behavior
of a customer.
\item[Unlinkability] Merchants must not be able to tell if two
transactions were performed by the same customer. It must be
infeasible to link a set of transactions to the same (anonymous)
customer. %, even when taking aborted transactions into account.
\item[Taxability] In many current legal systems, it is the
responsibility of the merchant to deduct (sales) taxes from
purchases made by customers, or to pay (income) taxes for payments
received for work.
%Taxation is neccessary for the state to
%provide legitimate social functions, such as education. Thus, a payment
%system must facilitate sales, income and transaction taxes.
This specifically means that it must be able to audit merchants (or
generally anybody receiving money), and thus the receiver of
electronic cash must be easily identifiable.
%non-anonymous, as this would enable tax fraud.
\item[Verifiability] The payment system should try to minimize the
trust necessary between the participants. In particular, digital
signatures should be used extensively in order to be able to
resolve disputes between the involved parties. Nevertheless,
customers must never be able to defraud anyone, and merchants must
at best be able to defraud their customers by not delivering the
on the agreed contract. Neither merchants nor customers must ever
be able to commit fraud against the mint. Both customers and
merchants must receive cryptographic proofs of bad behavior in
case of protocol violations by the mint. Thus, only the mint will
have to be tightly audited and regulated. The design must make it
easy to audit the finances of the mint.
\item[Ease of Deployment] %The system should be easy to deploy for
% real-world applications. In order to lower the entry barrier and
% acceptance of the system, a gateway to the existing financial
% system should be provided, i.e. by integrating internet-banking
% protocols such as HBCI/FinTAN.
The digital currency should be
tied 1:1 to existing currencies (such as EUR or USD) to avoid
exposing users to unnecessary risks from currency fluctuations.
Moreover, the system must have a free software reference
implementation and an open protocol standard.
% The protocol should
% be able to run easily over HTTP(S).
\item[Low resource consumption] In order to minimize the operating
costs and environmental impact of the payment system, it must
avoid the reliance on expensive and ``wasteful'' computations
such as proof-of-work.
\item[Large Payments and Microdonations] The payment system needs to
handle large payments in a reliable manner. Furthermore, for
microdonations the system should allow sacrificing reliability to
achieve economic viability.
\end{description}
Taler builds on ideas from Chaum~\cite{chaum1983blind}, who proposed a
digital currency system that would provide (some) customer anonymity
while disclosing the identity of the merchants. Chaum's digital cash
system had some limitations and ultimately failed to be widely
adopted. In our assessment, key reasons include:
\begin{itemize}
\item The use of patents to protect the technology; a payment system
must be libre --- free software --- to have a chance for widespread
adoption.
\item The use of off-line payments and thus deferred detection of
double-spending, which could require the mint to attempt to recover
funds from customers via the legal system. This creates a
significant business risk for the mint, as the system is not
self-enforcing from the perspective of the mint. In 1983 off-line
payments might have been a necessary feature. However, today
requiring network connectivity is feasible and avoids the business
risks associated with deferred fraud detection.
\item % In addition to the risk of legal disputes with fradulent
% merchants and customers,
Chaum's published design does not clearly
limit the financial damage a mint might suffer from the
disclosure of its private online signing key.
% \item Chaum did not support fractional payments, and Brand's
% extensions for fractional payments broke unlinkability and thus
% limited anonymity. Chaum also did not support microdonations,
% leaving an opportunity for expanding payments into additional areas
% unexplored.
% \item Chaum's system was implemented at a time where the US market
% was still dominated by paper checks and the European market was
% fragmented into dozens of currencies. Today, SEPA provides a
% unified currency and currency transfer method for most of Europe,
% significantly lowering the barrier to entry into this domain for
% a larger market.
\end{itemize}
This paper describes Taler, a simple and practical payment with the
above goals in mind. The basic idea is to use Chaum's model of
customer, merchant and mint (Figure~\ref{fig:cmm}) where the customer
withdraws digital currency from the mint with unlinkability provided
via blind signatures. In contrast to Chaum, Taler uses online
detection of double-spending, thus ensuring the merchant instantly
that a transaction is valid. Instead of using cryptographic methods
to enable fractional payments, the customer can simply include
the fraction of a coin's value that is to be paid to the merchant in
his message to the merchant.
\begin{figure}[h]
\centering
\begin{tikzpicture}
\tikzstyle{def} = [node distance= 7em and 10em, inner sep=1em, outer sep=.3em];
\node (origin) at (0,0) {};
\node (mint) [def,above=of origin,draw]{Mint};
\node (customer) [def, draw, below left=of origin] {Customer};
\node (merchant) [def, draw, below right=of origin] {Merchant};
\tikzstyle{C} = [color=black, line width=1pt]
\draw [<-, C] (customer) -- (mint) node [midway, above, sloped] (TextNode) {withdraw coins};
\draw [<-, C] (mint) -- (merchant) node [midway, above, sloped] (TextNode) {deposit coins};
\draw [<-, C] (merchant) -- (customer) node [midway, above, sloped] (TextNode) {spend coins};
\end{tikzpicture}
\caption{Taler's system model for the payment system is based on Chaum~\cite{chaum1983blind}.}
\label{fig:cmm}
\end{figure}
Online fraud detection can create problems if the network fails during
the initial steps of a transaction. For example, a law enforcement
agency might try to entrap a customer by offering illicit goods and
then aborting the transaction after learning the public key of the
coin. If the customer were to then later spend that coin on a
purchase with shipping, the law enforcement agency could link the two
transactions and might be able to use the shipping to deanonymize the
customer. Similarly, fractional payments also lead to the
possibility of customers wanting to legitimately use the same coin
twice. Taler addresses this problem by allowing customers to {\em
refresh} coins. Refreshing means that a customer is able to
exchange one coin for a fresh coin, with the old and the new coin
being unlinkable (except for the customer himself). Taler ensures
that the {\em entity} of the user owning the new coin is the same as the
entity of the user owning the old coin, thus making sure that the
refreshing protocol cannot be abused for money laundering or other
illicit transactions.
\section{Related Work}
\subsection{Blockchain-based currencies}
In recent years, a class of decentralized electronic payment systems,
based on collectively recorded and verified append-only public
ledgers, have gained immense popularity. The most well-known protocol
in this class is Bitcoin~\cite{nakamoto2008bitcoin}. An initial
concern with Bitcoin was the lack of anonymity, as all Bitcoin
transactions are recorded for eternity, which can enable
identification of users. In theory, this concern has been addressed
with the Zerocoin extension to the protocol~\cite{miers2013zerocoin}.
While these protocols dispense with the need for a central, trusted
authority and provide anonymity, we argue there are some major,
irredeemable problems inherent in these systems:
\begin{itemize}
\item Bitcoins are not (easily) taxable. The legality and legitimacy of
this aspect is questionable. The Zerocoin extension would only make
this worse.
\item Bitcoins can not be bound to any fiat currency, and are subject to
significant value fluctuations. While such fluctuations may be
acceptable for high-risk investments, they make Bitcoin unsuitable as
a medium of exchange.
\item The computational puzzles solved by Bitcoin nodes with the purpose
of securing the block chain
consume a considerable amount of computational resources and thus
energy. Thus, Bitcoin does not represent an environmentally responsible
design.
\item Anyone can easily start an alternative Bitcoin transaction chain
(a so-called AltCoin) and, if successful, reap the benefits of the low
cost to initially create coins via computation. As a result, dozens of
AltCoins have been created, often without any significant changes to the
technology. A large number of AltCoins creates additional overheads for
currency exchange and exascerbates the problems with currency fluctuations.
\end{itemize}
\subsection{Chaum-style electronic cash}
Chaum's original digital cash system~\cite{chaum1983blind} was
extended by Brands~\cite{brands1993efficient} with the ability to
perform fractional payments; however, the transactions performed with
the same coin then become linkable.
%
%Some argue that the focus on technically perfect but overwhelmingly
%complex protocols, as well as the the lack of usable, practical
%solutions lead to an abandonment of these ideas by
%practitioners~\cite{selby2004analyzing}.
%
To our knowledge, the only publicly available effort to implement
Chaum's idea is
Opencoin~\cite{dent2008extensions}. However,
Opencoin seems to be neither actively developed nor used, and it is
not clear to what degree the implementation is even complete. Only a
partial description of the Opencoin protocol is available to date.
\subsection{Peppercoin}
Peppercoin~\cite{rivest2004peppercoin} is a microdonation protocol.
The main idea of the protocol is to reduce transaction costs by
minimizing the number of transactions that are processed directly by
the mint. Instead of always paying, the customer ``gambles'' with the
merchant for each microdonation. Only if the merchant wins, the
microdonation is upgraded to a macropayment to be deposited at the
mint. Peppercoin does not provide customer-anonymity. The proposed
statistical method for mints detecting fraudulent cooperation between
customers and merchants at the expense of the mint not only creates
legal risks for the mint (who has to make a statistical argument), but
also would require the mint to learn about microdonations where the
merchant did not get upgraded to a macropayment. Thus, it is unclear
how much Peppercoin would actually do to reduce the computational
burden on the mint.
\section{Design}
The payment system we propose is built on the blind signature
primitive proposed by Chaum, but extended with additional
constructions to provide unlinkability, online fraud detection and
taxability.
As with Chaum, the Taler system comprises three principal types of
actors: The \emph{customer} is interested in receiving goods or
services from the \emph{merchant} in exchange for payment. When
making a transaction, both the customer and the merchant must agree on
the same \emph{mint}, which serves as an intermediary for the
financial transaction between the two. The mint is responsible for
allowing the customer to obtain the anonymous digital currency and for
enabling the merchant to convert the anonymous digital currency back
to some traditional currency.
\subsection{Security model}
Taler's security model assumes that cryptographic primitives are
secure and that each participant is under full control of his system.
The contact information of the mint is known to both customer and
merchant from the start. Furthermore, the merchant is known to the
customer and we assume that an anonymous, reliable bi-directional
communication channel can be established by the customer to both the
mint and the merchant.
The mint is trusted to hold funds of its customers and to forward them
when receiving the respective deposit instructions from the merchants.
Customer and merchant can have some assurances about the mint's
liquidity and operation, as the mint has proven reserves, is subject
to the law, and can have its business is regularly audited (for
example, by the government or a trusted third party auditor).
Audits of the mint's accounts must reveal any possible fraud.
%
The merchant is trusted to deliver the service or goods to the
customer upon receiving payment. The customer can seek legal relief
to achieve this, as he must get cryptographic proofs of the contract
and that he paid his obligations.
%
Neither the merchant nor the customer may have any ability to {\em
effectively} defraud the mint or the state collecting taxes. Here,
``effectively'' means that the expected return for fraud is negative.
%
Note that customers do not need to be trusted in any way, and that in
particular it is never necessary for anyone to try to recover funds
from customers using legal means.
\subsection{Taxability and Entities}
Electronic coins are trivially copied between machines. Thus, we must
clarify what kinds of operations can even be expected to be taxed.
After all, without instrusive measures to take away control of the
computing platform from its users, copying an electronic wallet from
one computer to another can hardly be prevented by a payment system.
Furthermore, it would also hardly be appropriate to tax the moving of
funds between two computers owned by the same individual. We thus
need to clarify which kinds of transfers we expect to tax.
Taler is supposed to ensure that the state can tax {\em transactions}.
We define a transaction as the transfer of funds between {\em mutually
distrustful} entities. Two entities are assumed to be mutually
distrustful if they are unwilling to share control over assets. If a
private key is shared between two entities, then both entities have
equal access to the credentials represented by the private key. In a
payment system this means that either entity could spent the
associated funds. Assuming the payment system has effective
double-spending detection, this means that either entity has to
constantly fear that the funds might no longer be available to it.
Thus, ``transferring'' funds by sharing a private key implies that
receiving party must trust the sender. In Taler, making funds
available by sharing a private key and thus sharing control is {\bf
not} considered a {\em transaction} and thus {\bf not} recorded for
taxation.
A {\em transaction} is a transfer where it is assured that one entity
gains control over funds while at the same time another entity looses
control over those funds. Taler ensures taxability only when some
entity acquires exclusive control over digital coins. For
transactions, the state can obtain information from the mint (or the
bank) that identifies the entity that received the digital coins as
well as the exact value of those coins. Taler also allows the mint
(and thus the state) to learn the value of digital coins withdrawn by
a customer --- but not how, where or when they were spent. Finally,
to enable audits, the current balance and profits of the mint are also
easily determined.
\subsection{Anonymity}
An anonymous communication channel (e.g. via Tor~\cite{tor-design}) is
used for all communication between the customer and the merchant.
Thus, the customer can remain anonymous; however, the system does reveal
that the customer is one of the patrons of the mint. Naturally, the
customer-merchant operation might leak other information about the
customer, such as a shipping address. Such purchase-specific
information leakage is outside of the scope of this work.
The customer may use an anonymous communication channel for the
communication with the mint to avoid leaking IP address information;
however, the mint will anyway be able to determine the customer's
identity from the (SEPA) transfer that the customer initiates to
obtain anonymous digital cash. The scheme is anonymous
because the mint will be unable to link the known identity of the
customer that withdrew anonymous digital currency to the {\em
purchase} performed later at the merchant.
% All the mint will be
%able to confirm is that the customer is {\em one} of its patrons who
%previously obtained the anonymous digital currency --- and of course
%that the coin was not spent before.
While the customer thus has anonymity for his purchase, the mint will
always learn the merchant's identity (which is necessary for
taxation), and thus the merchant has no reason to anonymize his
communication with the mint.
% Technically, the merchant could still
%use an anonymous communication channel to communicate with the mint.
%However, in order to receive the traditional currency the mint will
%require (SEPA) account details for the deposit.
%As both the initial transaction between the customer and the mint as
%well as the transactions between the merchant and the mint do not have
%to be done anonymously, there might be a formal business contract
%between the customer and the mint and the merchant and the mint. Such
%a contract may provide customers and merchants some assurance that
%they will actually receive the traditional currency from the mint
%given cryptographic proof about the validity of the transaction(s).
%However, given the business overheads for establishing such contracts
%and the natural goal for the mint to establish a reputation and to
%minimize cost, it is more likely that the mint will advertise its
%external auditors and proven reserves and thereby try to convince
%customers and merchants to trust it without a formal contract.
\subsection{Coins}
A \emph{coin} is a digital token which derives its financial value
from a signature on the coin's identifier by a mint. The mint is
expected to have multiple {\em coin signing key} pairs available for
signing, each representing a different coin denomination.
The coin signing keys have an expiration date (typically measured in
years), and coins signed with a coin signing key must be spent (or
exchanged for new coins) before that expiration date. This allows the
mint to limit the amount of state it needs to keep to detect
double spending attempts. Furthermore, the mint is expected to use each coin
signing key only for a limited number of coins, for example by
limiting its use to sign coins to a week or a month. That way, if the
private coin signing key were to be compromised, the mint can detect
this once more coins are redeemed than the total that was signed into
existence using the respective coin signing key. In this case, the
mint can allow the original set of customers to exchange the coins
that were signed with the compromised private key, while refusing
further transactions from merchants if they involve those coins. As a
result, the financial damage of loosing a private signing key can be
limited to at most twice the amount originally signed with that key.
To ensure that the mint does not enable deanonymization of users by
signing each coin with a fresh coin signing key, the mint must
publicly announce the coin signing keys in advance. Those
announcements are expected to be signed with an off-line long-term
private {\em master signing key} of the mint and possibly the auditor.
Before a customer can withdraw a coin from the mint, he has to pay the
mint the value of the coin, as well as processing fees. This is done
using other means of payments, such as SEPA transfers~\cite{sepa}.
The subject line of the transfer must contain {\em withdrawal
authorization key}, a public key for digital signatures generated by
the customer. When the mint receives a transfer with a public key in
the subject, it adds the funds to a {\em reserve} identified by the
withdrawl authorization key. By signing the withdrawl messages using
the withdrawl authorization key, the customer can prove to the mint
that he is authorized to withdraw anonymous digital coins from the
reserve. The mint will record the withdrawl messages with the reserve
record as proof that the anonymous digital coin was created for the
correct customer.
After a coin is minted, the customer is the only entity that knows the
private key of the coin, making him the \emph{owner} of the coin. The
coin can be identified by the mint by its public key; however, due to
the use of blind signatures, the mint does not learn the public key
during the minting process. Knowledge of the private key of the coin
enables the owner to spent the coin. If the private key is shared
with others, they also become owners of the coin.
\subsection{Coin spending}
To spend a coin, the coin's owner needs to sign a {\em deposit
request} specifying the amount, the merchant's account information
and a {\em business transaction-specific hash} using the coin's
private key. A merchant can then transfer this permission of the
coin's owner to the mint to obtain the amount in traditional currency.
If the customer is cheating and the coin was already spent, the mint
provides cryptographic proof of the fraud to the merchant, who will
then refuse the transaction.
% The mint is typically expected
%to transfer the funds to the merchant using a SEPA transfer or similar
%methods appropriate to the domain of the traditional currency.
%The mint needs to ensure that a coin can only be spent once. This is
%done by storing the public keys of all deposited coins (together with
%the deposit request and the owner's signature confirming the
%transaction). The mint's state can be limited as coins signed with
%expired coin sigining keys do not have to be retained.
\paragraph{Partial spending.}
To allow exact payments without requiring the customer to keep a large
amount of ``change'' in stock, the payment systems allows partial
spending of coins. Consequently, the mint the must not only store the
identifiers of spent coins, but also the fraction of the coin that has
been spent.
%\paragraph{Online checks.}
%
%For secure transactions (non-microdonations), the merchant is expected
%to perform an online check to detect double-spending. In the simplest
%case, the merchant simply directly confirms the validity of the
%deposit permission signed by the coin's owner with the mint, and then
%proceeds with the contract.
\subsection{Refreshing Coins}
In the payment scenarios there are several cases where a customer will
reveal the public key of a coin to a merchant, but not ultimately sign
over the full value of the coin. If the customer then continues to
use the remainder of the value of the coin in other transactions,
merchants and the mint could link the various transactions as they all
share the same public key for the coin.
Thus, the owner might want to exchange such a {\em dirty} coin for a
{\em fresh} coin to ensure unlinkability of future transactions with
the previous operation. Even if a coin is not dirty, the owner of a
coin may want to exchange a coin if the respective coin signing key is
about to expire. All of these operations are supported with the {\em
coin refreshing protocol}, which allows the owner of a coin to
exchange existing coins (or their remaining value) for fresh coins
with a new public-private key pairs. Refreshing does not use the
ordinary spending operation as the owner of a coin should not have to
pay taxes on this operation. Because of this, the refreshing protocol
must assure that owner stays the same. After all, the coin refreshing
protocol must not be usable for transactions, as transactions in Taler
must be taxable.
Thus, one main goal of the refreshing protocol is that the mint must
not be able to link the fresh coin's public key to the public key of
the dirty coin. The second main goal is to enable the mint to ensure
that the owner of the dirty coin can determine the private key of the
fresh coin. This way, refreshing cannot be used to construct a
transaction --- the owner of the dirty coin remains in control of the
fresh coin.
As with other operations, the refreshing protocol must also protect
the mint from double-spending; similarly, the customer has to have
cryptographic evidence if there is any misbehaviour by the mint.
Finally, the mint may choose to charge a transaction fee for
refreshing by reducing the value of the generated fresh coins
in relation to the value of the melted coins.
%Naturally, all such transaction fees should be clearly stated as part
%of the business contract offered by the mint to customers and
%merchants.
\section{Taler's Cryptographic Protocols}
% In this section, we describe the protocols for Taler in detail.
For the sake of brevity, we do not specifically state that the
recipient of a signed message always first checks that the signature
is valid. Also, whenever a signed message is transmitted, it is
assumed that the receiver is told the public key (or knows it from the
context) and that the signature contains additional identification as
to the purpose of the signature (such that it is not possible to
use a signature from one protocol step in a different context).
When the mint signs messages (not coins), an {\em online message
signing key} of the mint is used. The mint's long-term offline key
is used to certify both the coin signing keys as well as the online
message signing key of the mint. The mint's long-term offline key is
assumed to be well-known to both customers and merchants, for example
because it is certified by the auditors.
As we are dealing with financial transactions, we explicitly state
whenever entities need to safely commit data to persistent storage.
As long as those commitments persist, the protocol can be safely
resumed at any step. Commitments to disk are cummulative, that is an
additional commitment does not erase the previously committed
information. Keys and thus coins always have a well-known expiration
date; information committed to disk can be discarded after the
expiration date of the respective public key. Customers can also
discard information once the respective coins have been fully spent,
and merchants may discard information once payments from the mint have
been received (assuming records are also no longer needed for tax
authorities). The mint's bank transfers dealing in traditional
currency are expected to be recorded for tax authorities to ensure
taxability.
\subsection{Withdrawal}
To withdraw anonymous digital coins, the customer performs the
following interaction with the mint:
\begin{enumerate}
\item The customer identifies a mint with an auditor-approved
coin signing public-private key pair $K := (K_s, K_p)$
and randomly generates:
\begin{itemize}
\item withdrawal key $W := (W_s,W_p)$ with private key $W_s$ and public key $W_p$,
\item coin key $C := (C_s,C_p)$ with private key $C_s$ and public key $C_p$,
\item blinding factor $b$,
\end{itemize}
and commits $\langle W, C, b \rangle$ to disk.
\item The customer transfers an amount of money corresponding to (at least) $K_p$ to the mint, with $W_p$ in the subject line of the transaction.
\item The mint receives the transaction and credits the $W_p$ reserve with the respective amount in its database.
\item The customer sends $S_W(E_b(C_p))$ to the mint to request withdrawal of $C$; here, $E_b$ denotes Chaum-style blinding with blinding factor $b$.
\item The mint checks if the same withdrawal request was issued before; in this case, it sends $S_{K}(E_b(C_p))$ to the customer.\footnote{Here $S_K$
denotes a Chaum-style blind signature with private key $K_s$.}
If this is a fresh withdrawal request, the mint performs the following transaction:
\begin{enumerate}
\item checks if the reserve $W_p$ has sufficient funds for a coin of value corresponding to $K_p$
\item stores the withdrawal request $\langle S_W(E_b(C_p)), S_K(E_b(C_p)) \rangle$ in its database for future reference,
\item deducts the amount corresponding to $K_p$ from the reserve,
\item and sends $S_{K}(E_b(C_p))$ to the customer.
\end{enumerate}
If the guards for the transaction fail, the mint sends a descriptive error back to the customer,
with proof that it operated correctly (i.e. by showing the transaction history for the reserve).
\item The customer computes (and verifies) the unblind signature $S_K(C_p) = D_b(S_K(E_b(C_p)))$.
The customer writes $\langle S_K(C_p), C_s \rangle$ to disk (effectively adding the coin to the
local wallet) for future use.
\end{enumerate}
\subsection{Exact and partial spending}
A customer can spend coins at a merchant, under the condition that the
merchant trusts the mint that minted the coin. Merchants are
identified by their public key $M := (M_s, M_p)$, which must be known
to the customer apriori.
The following steps describe the protocol between customer, merchant and mint
for a transaction involving a coin $C := (C_s, C_p)$ which is previously signed
by a mint's denomination key $K$, i.e. the customer posses
$\widetilde{C} := S_K(C_p)$:
\begin{enumerate}
\item\label{contract} Let $\vec{D} := D_1, \ldots, D_n$ be the list of
mints accepted by the merchant where each $D_i$ is a mint's public
key. The merchant creates a digitally signed contract $\mathcal{A}
:= S_M(m, f, a, H(p, r), \vec{D})$ where $a$ is data relevant to the
contract indicating which services or goods the merchant will
deliver to the customer, $f$ is the price of the offer, and $p$ is
the merchant's payment information (e.g. his IBAN number) and $r$ is
an random nounce. The merchant commits $\langle \mathcal{A}
\rangle$ to disk and sends $\mathcal{A}$ it to the customer.
\item\label{deposit} The customer must possess or acquire a coin minted by a mint that is
accepted by the merchant, i.e. $K$ should be publicly signed by some $D_i
\in \{D_1, D_2, \ldots, D_n\}$, and has a value $\geq f$. (The customer
can of course also use multiple coins where the total value adds up to
the cost of the transaction and run the following steps for each of
the coins. However, for simplicity of the description here we will
assume that one coin is sufficient.)
The customer then generates a \emph{deposit-permission} $\mathcal{D} :=
S_c(\widetilde{C}, m, f, H(a), H(p,r), M_p)$
and sends $\langle \mathcal{D}, D_i\rangle$ to the merchant,
where $D_i$ is the mint which signed $K$.
\item The merchant gives $(\mathcal{D}, p, r)$ to the mint, revealing his
payment information.
\item The mint validates $\mathcal{D}$ and detects double spending.
If the coin has been involved in previous transactions, it sends an error
with the records from the previous transactions back to the merchant.
If double spending is not found, the mint commits $\langle \mathcal{D} \rangle$ to disk
and notifies the merchant that deposit operation was successful.
\item The merchant commits and forwards the notification from the mint to the
customer, confirming the success or failure of the operation.
\end{enumerate}
Similarly, if a transaction is aborted after Step~\ref{deposit},
subsequent transactions with the same coin can be linked to the coin,
but not directly to the coin's owner. The same applies to partially
spent coins (where $f$ is smaller than the actual value of the coin).
To unlink subsequent transactions from a coin, the customer has to
execute the coin refreshing protocol with the mint.
%\begin{figure}[h]
%\centering
%\begin{tikzpicture}
%
%\tikzstyle{def} = [node distance= 1em, inner sep=.5em, outer sep=.3em];
%\node (origin) at (0,0) {};
%\node (offer) [def,below=of origin]{make offer (merchant $\rightarrow$ customer)};
%\node (A) [def,below=of offer]{permit lock (customer $\rightarrow$ merchant)};
%\node (B) [def,below=of A]{apply lock (merchant $\rightarrow$ mint)};
%\node (C) [def,below=of B]{confirm (or refuse) lock (mint $\rightarrow$ merchant)};
%\node (D) [def,below=of C]{sign contract (merchant $\rightarrow$ customer)};
%\node (E) [def,below=of D]{permit deposit (customer $\rightarrow$ merchant)};
%\node (F) [def,below=of E]{make deposit (merchant $\rightarrow$ mint)};
%\node (G) [def,below=of F]{transfer confirmation (mint $\rightarrow$ merchant)};
%
%\tikzstyle{C} = [color=black, line width=1pt]
%\draw [->,C](offer) -- (A);
%\draw [->,C](A) -- (B);
%\draw [->,C](B) -- (C);
%\draw [->,C](C) -- (D);
%\draw [->,C](D) -- (E);
%\draw [->,C](E) -- (F);
%\draw [->,C](F) -- (G);
%
%\draw [->,C, bend right, shorten <=2mm] (E.east)
% to[out=-135,in=-45,distance=3.8cm] node[left] {aggregate} (D.east);
%\end{tikzpicture}
%\caption{Interactions between a customer, merchant and mint in the coin spending
% protocol}
%\label{fig:spending_protocol_interactions}
%\end{figure}
\subsection{Refreshing}
The following protocol is executed in order to refresh a coin $C'$ of
denomination $K$ to a fresh coin $\widetilde{C}$ with the same
denomination. In the protocol, $\kappa \ge 3$ is a security parameter
and $G$ is the generator of the elliptic curve.
\begin{enumerate}
\item For each $i = 1,\ldots,\kappa$, the customer
\begin{itemize}
\item randomly generates transfer key $T^{(i)} := \left(t^{(i)}_s,T^{(i)}_p\right)$ where $T^{(i)}_p := t^{(i)}_s G$,
\item randomly generates coin key pair $C^{(i)} := \left(c_s^{(i)}, C_p^{(i)}\right)$ where $C^{(i)}_p := c^{(i)}_s G$,
\item randomly generates blinding factors $b_i$,
\item computes $E_i := E_{K_i}\left(c_s^{(i)}, b_i\right)$ where $K_i := H(c'_s T_p^{(i)})$. (The encryption key $K_i$ is
computed by multiplying the private key $c'_s$ of the original coin with the point on the curve
that represents the public key $T^{(i)}_p$ of the transfer key $T^{(i)}$.),
\end{itemize}
and commits $\langle C', \vec{T}, \vec{C}, \vec{b} \rangle$ to disk.
\item The customer computes $B_i := E_{b_i}(C^{(i)}_p)$ for $i=1,\ldots,\kappa$ and sends a commitment
$S_{C'}(\vec{E}, \vec{B}, \vec{T_p}))$ to the mint;
here $E_{b_i}$ denotes Chaum-style blinding with blinding factor $b_i$.
\item The mint generates a random $\gamma$ with $1 \le \gamma \le \kappa$ and
marks $C'_p$ as spent by committing
$\langle C', \gamma, S_{C'}(\vec{E}, \vec{B}, \vec{T}) \rangle$ to disk.
\item The mint sends $S_K(C'_p, \gamma)$ to the customer.\footnote{Instead of $K$, it is also
possible to use any equivalent mint signing key known to the customer here, as $K$ merely
serves as proof to the customer that the mint selected this particular $\gamma$.}
\item The customer commits $\langle C', S_K(C'_p, \gamma) \rangle$ to disk.
\item The customer computes $\mathfrak{R} := \left(t_s^{(i)}, C_p^{(i)}, b_i\right)_{i \ne \gamma}$
and sends $S_{C'}(\mathfrak{R})$ to the mint.
\item \label{step:refresh-ccheck} The mint checks whether $\mathfrak{R}$ is consistent with the commitments;
specifically, it computes for $i \not= \gamma$:
\begin{itemize}
\item $\overline{K}_i := H(t_s^{(i)} C_p')$,
\item $(\overline{c}_s^{(i)}, \overline{b}_i) := D_{\overline{K}_i}(E_i)$,
\item $\overline{C}^{(i)}_p := \overline{c}_s^{(i)} G$,
\item $\overline{B}_i := E_{b_i}(C_p^{(i)})$,
\item $\overline{T}_i := t_s^{(i)} G$,
\end{itemize}
and checks if $\overline{C}^{(i)}_p = C^{(i)}_p$ and $H(E_i, \overline{B}_i, \overline{T}^{(i)}_p) = H(E_i, B_i, T^{(i)}_p)$
and $\overline{T}_i = T_i$.
\item \label{step:refresh-done} If the commitments were consistent,
the mint sends the blind signature $\widetilde{C} :=
S_{K}(B_\gamma)$ to the customer. Otherwise, the mint responds
with an error the value of $C'$.
\end{enumerate}
%\subsection{N-to-M Refreshing}
%
%TODO: Explain, especially subtleties regarding session key / the spoofing attack that requires signature.
\subsection{Linking}
% FIXME: explain better...
For a coin that was successfully refreshed, the mint responds to
a request $S_{C'}(\mathtt{link})$ with $(T^{(\gamma)}_p$, $E_{\gamma}, \widetilde{C})$.
This allows the owner of the old coin to also obtain the private key
of the new coin, even if the refreshing protocol was illicitly
executed by another party who learned $C'_s$ from the old owner.
\section{Discussion}
\subsection{Offline Payments}
Chaum's original proposals for anonymous digital cash avoided the
locking and online spending steps detailed in this proposal by
providing a means to deanonymize customers involved in
double-spending. We believe that this is problematic as the mint or
the merchant will then still need out-of-band means to recover funds
from the customer, which may be impossible in practice. In contrast,
in our design only the mint may try to defraud the other participants
and disappear. While this is still a risk, this is likely manageable,
especially compared to recovering funds via the court system from
customers.
\subsection{Bona-fide microdonations}
Evidently the customer can ``cheat'' by aborting the transaction in
Step 3 of the microdonation protocol if the outcome is unfavourable ---
and repeat until he wins. This is why Taler is suitable for
microdonations --- where the customer voluntarily contributes ---
and not for micropayments.
Naturally, if the donations requested are small, the incentive to
cheat for minimal gain should be quite low. Payment software could
embrace this fact by providing an appeal to conscience in form of an
option labeled ``I am unethical and want to cheat'', which executes
the dishonest version of the payment protocol.
If an organization detects that it cannot support itself with
microdonations, it can always choose to switch to the macropayment
system with slightly higher transaction costs to remain in business.
\subsection{Merchant Tax Audits}
For a tax audit on the merchant, the mint includes the business
transaction-specific hash in the transfer of the traditional
currency. A tax auditor can then request the merchant to reveal
(meaningful) details about the business transaction ($\mathcal{D}$,
$a$, $p$, $r$), including proof that applicable taxes were paid.
If a merchant is not able to provide theses values, he can be punished
in relation to the amount transferred by the traditional currency
transfer.
\section{Future Work}
%The legal status of the system needs to be investigated in the various
%legal systems of the world. However, given that the system enables
%taxation and is able to impose withdrawal limits and thus is not
%suitable for money laundering, we are optimistic that states will find
%the design desirable.
We did not yet perform performance measurements for the various
operations. However, we are pretty sure that the computational and
bandwidth cost for transactions described in this paper is likely
small compared to other business costs for the mint. We expect costs
within the system to be dominated by the (replicated, transactional)
database. However, these expenses are again likely small in relation
to the business cost of currency transfers using traditional banking.
Here, mint operators should be able to reduce their expenses by
aggregating multiple transfers to the same merchant.
\section{Conclusion}
We have presented an efficient electronic payment system that
simultaneously addresses the conflicting objectives created by the
citizen's need for privacy and the state's need for taxation. The
coin refreshing protocol makes the design flexible and enables a
variety of payment methods. The libre implementation and open
protocol may finally enable modern society to upgrade to proper
electronic wallets with efficient, secure and privacy-preserving
transactions.
\bibliographystyle{alpha}
\bibliography{taler}
\appendix
\section{Optional features}
In this appendix we detail various optional features that can
be added to the basic protocol.
\subsection{Refunds}
\subsection{Incremental spending}
For services that include pay-as-you-go billing, customers can over
time sign deposit permissions for an increasing fraction of the value
of a coin to be paid to a particular merchant. As checking with the
mint for each increment might be expensive, the coin's owner can
instead sign a {\em lock permission}, which allows the merchant to get
an exclusive right to redeem deposit permissions for the coin for a
limited duration. The merchant uses the lock permission to determine
if the coin has already been spent and to ensure that it cannot be
spent by another merchant for the {\em duration} of the lock as
specified in the lock permission. If the coin has been spent or is
already locked, the mint provides the owner's deposit or locking
request and signature to prove the attempted fraud by the customer.
Otherwise, the mint locks the coin for the expected duration of the
transaction (and remembers the lock permission). The merchant and the
customer can then finalize the business transaction, possibly
exchanging a series of incremental payment permissions for services.
Finally, the merchant then redeems the coin at the mint before the
lock permission expires to ensure that no other merchant spends the
coin first.
\begin{enumerate}
\item\label{offer2} The merchant sends an \emph{offer:} $\langle S_M(m, f),
\vec{D} \rangle$ containing the price of the offer $f$, a transaction
ID $m$ and the list of mints $D_1, \ldots, D_n$ accepted by the merchant
where each $D_i$ is a mint's public key.
\item\label{lock2} The customer must possess or acquire a coin minted by a mint that is
accepted by the merchant, i.e. $K$ should be publicly signed by some $D_i
\in \{D_1, D_2, \ldots, D_n\}$, and has a value $\geq f$.
Customer then generates a \emph{lock-permission} $\mathcal{L} :=
S_c(\widetilde{C}, t, m, f, M_p)$ where $t$ specifies the time until which the
lock is valid and sends $\langle \mathcal{L}, D_i\rangle$ to the merchant,
where $D_i$ is the mint which signed $K$.
\item The merchant asks the mint to apply the lock by sending $\langle
\mathcal{L} \rangle$ to the mint.
\item The mint validates $\widetilde{C}$ and detects double spending if there is
a lock-permission record $S_c(\widetilde{C}, t', m', f', M_p')$ where $(t',
m', f', M_p') \neq (t, m, f, M_p)$ or a \emph{deposit-permission} record for
$C$ and sends it to the merchant, who can then use it prove to the customer
and subsequently ask the customer to issue a new lock-permission.
If double spending is not found, the mint commits $\langle \mathcal{L} \rangle$ to disk
and notifies the merchant that locking was successful.
\item\label{contract2} The merchant creates a digitally signed contract
$\mathcal{A} := S_M(m, f, a, H(p, r))$ where $a$ is data relevant to the contract
indicating which services or goods the merchant will deliver to the customer, and $p$ is the
merchant's payment information (e.g. his IBAN number) and $r$ is an random nounce.
The merchant commits $\langle \mathcal{A} \rangle$ to disk and sends it to the customer.
\item The customer creates a
\emph{deposit-permission} $\mathcal{D} := S_c(\widetilde{C}, f, m, M_p, H(a), H(p, r))$, commits
$\langle \mathcal{A}, \mathcal{D} \rangle$ to disk and sends $\mathcal{D}$ to the merchant.
\item\label{invoice_paid2} The merchant commits the received $\langle \mathcal{D} \rangle$ to disk.
\item The merchant gives $(\mathcal{D}, p, r)$ to the mint, revealing his
payment information.
\item The mint verifies $(\mathcal{D}, p, r)$ for its validity. A
\emph{deposit-permission} for a coin $C$ is valid if:
\begin{itemize}
\item $C$ is not refreshed already
\item there exists no other \emph{deposit-permission} on disk for \\
$\mathcal{D'} := S_c(\widetilde{C}, f', m', M_p', H(a'), H(p', r'))$ for $C$
such that \\ $(f', m',M_p', H(a')) \neq (f, m, M_p, H(a))$
\item $H(p, r) := H(p', r')$
\end{itemize}
If $C$ is valid and no other \emph{deposit-permission} for $C$ exists on disk, the
mint does the following:
\begin{enumerate}
\item if a \emph{lock-permission} exists for $C$, it is deleted from disk.
\item\label{transfer2} transfers an amount of $f$ to the merchant's bank account
given in $p$. The subject line of the transaction to $p$ must contain
$H(\mathcal{D})$.
\item $\langle \mathcal{D}, p, r \rangle$ is commited to disk.
\end{enumerate}
If the deposit record $\langle \mathcal{D}, p, r \rangle$ already exists,
the mint sends it to the merchant, but does not transfer money to $p$ again.
\end{enumerate}
To facilitate incremental spending of a coin $C$ in a single transaction, the
merchant makes an offer in Step~\ref{offer2} with a maximum amount $f_{max}$ he
is willing to charge in this transaction from the coin $C$. After obtaining the
lock on $C$ for $f_{max}$, the merchant makes a contract in Step~\ref{contract2}
with an amount $f \leq f_{max}$. The protocol follows with the following steps
repeated after Step~\ref{invoice_paid2} whenever the merchant wants to charge an
incremental amount up to $f_{max}$:
\begin{enumerate}
\setcounter{enumi}{4}
\item The merchant generates a new contract $ \mathcal{A}' := S_M(m, f', a', H(p,
r)) $ after obtaining the deposit-permission for a previous contract. Here
$f'$ is the accumulated sum the merchant is charging the customer, of which
the merchant has received a deposit-permission for $f$ from the previous
contract \textit{i.e.}~$f <f' \leq f_{max}$. Similarly $a'$ is the new
contract data appended to older contract data $a$.
The merchant commits $\langle \mathcal{A}' \rangle$ to disk and sends it to the customer.
\item Customer commits $\langle \mathcal{A}' \rangle$ to disk, creates
$\mathcal{D}' := S_c(\widetilde{C}, f', m, M_p, H(a'), H(p, r))$, commits
$\langle \mathcal{D'} \rangle$ and sends it to the merchant.
\item The merchant commits the received $\langle \mathcal{D'} \rangle$ and
deletes the older $\mathcal{D}$
\end{enumerate}
%Figure~\ref{fig:spending_protocol_interactions} summarizes the interactions of the
%coin spending protocol.
For transactions with multiple coins, the steps of the protocol are executed in
parallel for each coin.
During the time a coin is locked, it may not be spent at a
different merchant. To make the storage costs of the mint more predictable,
only one lock per coin can be active at any time, even if the lock only covers a
fraction of the coin's denomination. The mint will delete the locks when they
expire. Thus the coins can be reused once their locks expire. However, doing
so may link the new transaction to older transaction.
Similarly, if a transaction is aborted after Step 2, subsequent transactions
with the same coin can be linked to the coin, but not directly to the coin's
owner. The same applies to partially spent coins. To unlink subsequent
transactions from a coin, the customer has to execute the coin refreshing
protocol with the mint.
%\begin{figure}[h]
%\centering
%\begin{tikzpicture}
%
%\tikzstyle{def} = [node distance= 1em, inner sep=.5em, outer sep=.3em];
%\node (origin) at (0,0) {};
%\node (offer) [def,below=of origin]{make offer (merchant $\rightarrow$ customer)};
%\node (A) [def,below=of offer]{permit lock (customer $\rightarrow$ merchant)};
%\node (B) [def,below=of A]{apply lock (merchant $\rightarrow$ mint)};
%\node (C) [def,below=of B]{confirm (or refuse) lock (mint $\rightarrow$ merchant)};
%\node (D) [def,below=of C]{sign contract (merchant $\rightarrow$ customer)};
%\node (E) [def,below=of D]{permit deposit (customer $\rightarrow$ merchant)};
%\node (F) [def,below=of E]{make deposit (merchant $\rightarrow$ mint)};
%\node (G) [def,below=of F]{transfer confirmation (mint $\rightarrow$ merchant)};
%
%\tikzstyle{C} = [color=black, line width=1pt]
%\draw [->,C](offer) -- (A);
%\draw [->,C](A) -- (B);
%\draw [->,C](B) -- (C);
%\draw [->,C](C) -- (D);
%\draw [->,C](D) -- (E);
%\draw [->,C](E) -- (F);
%\draw [->,C](F) -- (G);
%
%\draw [->,C, bend right, shorten <=2mm] (E.east)
% to[out=-135,in=-45,distance=3.8cm] node[left] {aggregate} (D.east);
%\end{tikzpicture}
%\caption{Interactions between a customer, merchant and mint in the coin spending
% protocol}
%\label{fig:spending_protocol_interactions}
%\end{figure}
\subsection{Probabilistic spending}
Similar to Peppercoin, Taler supports probabilistic spending of coins to
support cost-effective transactions for small amounts. Here, an
ordinary transaction is performed based on the result of a biased coin
flip with a probability related to the desired transaction amount in
relation to the value of the coin. Unlike Peppercoin, in Taler either
the merchant wins and the customer looses the coin, or the merchant
looses and the customer keeps the coin. Thus, there is no opportunity
for the merchant and the customer to conspire against the mint. To
determine if the coin is to be transferred, merchant and customer
execute a secure coin flipping protocol~\cite{blum1981}. The commit
values are included in the business contract and are revealed after
the contract has been signed using the private key of the coin. If
the coin flip is decided in favor of the merchant, the merchant can
redeem the coin at the mint.
One issue in this protocol is that the customer may use a worthless
coin by offering a coin that has already been spent. This kind of
fraud would only be detected if the customer actually lost the coin
flip, and at this point the merchant might not be able to recover from
the loss. A fradulent anonymous customer may run the protocol using
already spent coins until the coin flip is in his favor. As with
incremental spending, lock permissions could be used to ensure that
the customer cannot defraud the merchant by offering a coin that has
already been spent. However, as this means involving the mint even if
the merchant looses the coin flip, such a scheme is unsuitable for
microdonations as the transaction costs from involving the mint might
be disproportionate to the value of the transaction, and thus with
locking the probabilistic scheme has no advantage over simply using
fractional payments.
Hence, Taler uses probabilistic transactions {\em without} the online
double-spending detection. This enables the customer to defraud the
merchant by paying with a coin that was already spent. However, as,
by definition, such microdonations are for tiny amounts, the incentive
for customers to pursue this kind of fraud is limited.
The following steps are executed for microdonations with upgrade probability $p$:
\begin{enumerate}
\item The merchant sends an offer to the customer.
\item The customer sends a commitment $H(r_c)$ to a random
value $r_c \in [0,2^R)$, where $R$ is a system parameter.
\item The merchant sends random $r_m \in [0,2^R)$ to the customer.
\item The customer computes $p' := (|r_c - r_m|) / (2^R)$.
If $p' < p$, the customer sends a coin with deposit-permission to the merchant.
Otherwise, the customer sends $r_c$ to the merchant.
\item The merchant deposits the coin, or checks if $r_c$ is consistent
with $H(r_c)$.
\end{enumerate}
\end{document}
|