summaryrefslogtreecommitdiff log msg author committer range
path: root/doc/paper/taler.tex
 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 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436  % RMS wrote: %The text does not mention GNU anywhere. This paper is an opportunity %to make people aware of GNU, but the current text fails to use the %opportunity. % %It should say that Taler is a GNU package. % %I suggest using the term "GNU Taler" in the title, once in the %abstract, and the first time the name is mentioned in the body text. %In the body text, it can have a footnote with more information %including a reference to http://gnu.org/gnu/the-gnu-project.html. % %At the top of page 3, where it says "a free software implementation", %it should add "(free as in freedom)", with a reference to %http://gnu.org/philosophy/free-sw.html and %http://gnu.org/philosophy/free-software-even-more-important.html. % %Would you please include these things in every article or posting? % % CG adds: % We SHOULD do this for the FINAL paper, not for the anon submission. \documentclass{llncs} %\usepackage[margin=1in,a4paper]{geometry} \usepackage[T1]{fontenc} \usepackage{palatino} \usepackage{xspace} \usepackage{microtype} \usepackage{tikz,eurosym} \usepackage{amsmath,amssymb} \usepackage{enumitem} \usetikzlibrary{shapes,arrows} \usetikzlibrary{positioning} \usetikzlibrary{calc} % Relate to: % http://fc14.ifca.ai/papers/fc14_submission_124.pdf % 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 exchange waiting for withdrawal % - deposit = SEPA to exchange % - withdrawal = exchange to customer % - spending = customer to merchant % - redeeming = merchant to exchange (and then exchange SEPA to merchant) % - refreshing = customer-exchange-customer % - dirty coin = coin with exposed public key % - fresh coin = coin that was refreshed or is new % - coin signing key = exchange's online key used to (blindly) sign coin % - message signing key = exchange's online key to sign exchange messages % - exchange master key = exchange's key used to sign other exchange 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 exchanges 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 payments, and even in this case is still able to guarantee unlinkability of transactions via a new coin refreshing protocol. 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, corruption is widespread and not limited to social elites. ZeroCoin~\cite{miers2013zerocoin} is an example for translating such an economy into the digital realm. This paper describes Taler, a simple and practical payment system for a modern social-liberal society, which is not being served well by current payment systems which enable either an authoritarian state in total control of the population, or create weak states with almost anarchistic economies. The Taler protocol is heavily based on ideas from Chaum~\cite{chaum1983blind} and also follows Chaum's basic architecture of customer, merchant and exchange (Figure~\ref{fig:cmm}). The two designs share the key first step where the {\em customer} withdraws digital {\em coins} from the {\em exchange} with unlinkability provided via blind signatures. The coins can then be spent at a {\em merchant} who {\em deposits} them at the exchange. Taler uses online detection of double-spending, thus assuring the merchant instantly that a transaction is valid. \begin{figure}[h] \centering \begin{tikzpicture} \tikzstyle{def} = [node distance= 5em and 7em, inner sep=1em, outer sep=.3em]; \node (origin) at (0,0) {}; \node (exchange) [def,above=of origin,draw]{Exchange}; \node (customer) [def, draw, below left=of origin] {Customer}; \node (merchant) [def, draw, below right=of origin] {Merchant}; \node (auditor) [def, draw, above right=of origin]{Auditor}; \tikzstyle{C} = [color=black, line width=1pt] \draw [<-, C] (customer) -- (exchange) node [midway, above, sloped] (TextNode) {withdraw coins}; \draw [<-, C] (exchange) -- (merchant) node [midway, above, sloped] (TextNode) {deposit coins}; \draw [<-, C] (merchant) -- (customer) node [midway, above, sloped] (TextNode) {spend coins}; \draw [<-, C] (exchange) -- (auditor) node [midway, above, sloped] (TextNode) {verify}; \end{tikzpicture} \caption{Taler's system model for the payment system is based on Chaum~\cite{chaum1983blind}.} \label{fig:cmm} \end{figure} Taler was designed for use in a modern social-liberal society, which we believe needs a payment system with the following properties: \begin{description} \item[Customer Anonymity] It must be impossible for exchanges, merchants and even a global active adversary, to trace the spending behavior of a customer. \item[Unlinkability] As a strong form of customer anonymity, 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 necessary for the state to %provide legitimate social functions, such as education. Thus, a payment %system must facilitate sales, income and transaction taxes. This requires that merchants are easily identifiable and that an audit trail is always generated, so that the state can ensure that its taxation regime is obeyed. \item[Verifiability] The payment system should try to minimize the trust necessary between the participants. In particular, digital signatures should be used, and retained, whenever they would play a role in resolving 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 on the agreed contract. Neither merchants nor customers should ever be able to commit fraud against the exchange. Additionally, both customers and merchants must receive cryptographic proofs of bad behavior in case of protocol violations by the exchange. In this way, only the exchange will need to be tightly audited and regulated. The design must make it easy to audit the finances of the exchange. \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 coins should be denominated in existing currencies, such as EUR or USD, to avoid exposing citizens to unnecessary risks from currency fluctuations. Moreover, the system must have an open protocol specification and a free software reference implementation. % 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 should avoid the reliance on expensive or wasteful'' computations, such as proof-of-work. \item[Fractional payments] The payment system needs to handle both small and large payments in an efficient and reliable manner. It is inefficient to simply issue coins in the smallest unit of currency, so instead a mechanism to give {\em change} should be provided to ensure that customers with sufficient total funds can always spend them. \end{description} % We give a concise example of how these properties interact: A customer may want to pay \EUR{49,99} using a \EUR{100,00} coin. the system must thus support giving change in the form of spendable coins, say a \EUR{0,01} coin and a \EUR{50,00} coin. A merchant cannot simply give the customer their coins in another transaction; however, as this reverses the role of merchant and customer, and our taxability requirement would deanonymize the customer. The customer also cannot withdraw exact change from his account from the exchange, as this would allow the exchange to link the identity of the customer that is revealed during withdrawal to the subsequent deposit operation that follows shortly afterwards. Instead, the customer should obtain new freshly anonymized coins that cannot be linked with this transaction, the original \EUR{100,00} coin, or each other. Instead of using cryptographic methods like $k$-show signatures~\cite{brands1993efficient} to achieve divisibility, Taler's fractional payments use a simpler, more powerful mechanism. In Taler, a coin is not simply a signed unique random token, but signature over the hash of a public key where the private key is only known to the owner of the coin. A customer transfers currency from a coin to a merchant by cryptographically signing a deposit message with this private key. This deposit message specifies the fraction of the coin's value to be paid to the merchant. A key contribution of Taler is the {\em refresh} protocol, which enables a customer to exchange the residual value of the exchanged coin for unlinkable freshly anonymized change. Taler exchanges ensure that all transactions involving the same coin do not exceed the total value of the coin simply by requiring that merchants clear transactions immediately with the exchange. This improves dramatically on systems that support offline merchants with cryptographic threats to deanonymizing customers who double-spend, like restrictive blind signatures~\cite{brands1993efficient}. In such schemes, if a transaction is interrupted, then any coins sent to the merchant become tainted, but may never arrive or be spent. It becomes tricky to extract the value of the tainted coins without linking to the aborted transaction and risking deanonymization. As with support for fractional payments, Taler addresses these problems by allowing customers to refresh tainted coins, thereby destroying the link between the refunded or aborted transaction and the new coin. 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}. These protocols do dispense with the need for a central, trusted authority, while providing a useful measure of pseudonymity. Yet, there are several major irredeemable problems inherent in their designs: \begin{itemize} \item The computational puzzles solved by Bitcoin nodes with the purpose of securing the block chain consume a considerable amount of computational resources and energy. So Bitcoin does not an environmentally responsible design. \item Bitcoin transactions are not easily taxable, leading to legal hurdles. % The legality and legitimacy of this aspect is questionable. The Zerocoin extension would only make this worse. \item Bitcoins can not easily be bound to any fiat currency, leading to significant fluctuations in value. These fluctuations may be desirable in a high-risk investment instrument, but they make Bitcoin unsuitable as a medium of exchange. \item Worse, anyone can start an alternative Bitcoin transaction chain, called an AltCoin, and, if successful, reap the benefits of the low cost to initially create coins via computation. As participants are de facto investors, these become a form of ponzi scheme. % 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 exacerbates the problems with currency fluctuations. \end{itemize} GreenCoinX\footnote{\url{https://www.greencoinx.com/}} is a more recent AltCoin where the company promises to identify the owner of each coin via e-mail addresses and phone numbers. While it is unclear from their technical description how this identification would be enforced against a determined adversary, the resulting payment system would also merely impose a totalitarian financial panopticon on a BitCoin-style money supply and transaction model, thus largely combining what we would consider to be the drawbacks of these existing systems. \subsection{Chaum-style electronic cash} Taler builds on ideas from Chaum~\cite{chaum1983blind}, who proposed a digital payment system that would provide some customer anonymity while disclosing the identity of the merchants. Chaum's digital cash system DigiCash had some limitations and ultimately failed to be widely adopted. In our assessment, key reasons for DigiCash's failure that Taler avoids include: \begin{itemize} \item The use of patents to protect the technology; a payment system should be free software (libre) 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 exchange to attempt to recover funds from customers via the legal system. This creates a significant business risk for the exchange, as the system is not self-enforcing from the perspective of the exchange. 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 fraudulent % merchants and customers, Chaum's published design does not clearly limit the financial damage a exchange might suffer from the disclosure of its private online signing key. \item Chaum did not support fractional payments or refunds without breaking customer anonymity. %, and Brand's % extensions for fractional payments broke unlinkability and thus % limited anonymity. % \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} Chaum's original digital cash system~\cite{chaum1983blind} was extended by Brands~\cite{brands1993efficient} with the ability to {\em divide} coins and thus spend certain fractions of a coin using restrictive blind signatures. Compared to Taler, performing fractional payments is cryptographically way more expensive and moreover the transactions performed with divisions'' from the same coin do 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 exchange. 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 exchange. Peppercoin does not provide customer-anonymity. The proposed statistical method by which exchanges detect fraudulent cooperation between customers and merchants at the expense of the exchange not only creates legal risks for the exchange, but would also require that the exchange learns about microdonations where the merchant did not get upgraded to a macropayment. It is therefore unclear how Peppercoin would actually reduce the computational burden on the exchange. \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 (Figure~\ref{fig:cmm}): 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{exchange}, which serves as an intermediary for the financial transaction between the two. The exchange is responsible for allowing the customer to obtain the anonymous digital currency and for enabling the merchant to convert the digital coins back to some traditional currency. The \emph{auditor} assures customers and merchants that the exchange operates correctly. \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 exchange is known to both customer and merchant from the start. Furthermore, the merchant communication's authenticity is assured to the customer, such as by using X.509 certificates~\cite{rfc5280}, and we assume that an anonymous, reliable bi-directional communication channel can be established by the customer to both the exchange and the merchant, such as by using Tor. The exchange 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 exchange's liquidity and operation, as the exchange has proven reserves, is subject to the law, and can have its business regularly audited by a government or third party. Regular audits of the exchange's accounts should reveal any possible fraud before the exchange is allowed to destroy the corresponding accumulated cryptographic proofs and book its fees as profits. % 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 exchange 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} As electronic coins are trivially copied between machines, we should clarify what kinds of operations can even be expected to be taxed. After all, without intrusive 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 entity. 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}. 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. We further restrict transactions to apply only to 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 coins. 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. It follows that sharing coins by copying a private key implies mutual trust between the two parties, in which case Taler will treat them as the same entity. In Taler, making funds available by copying a private key and thus sharing control is {\bf not} considered a {\em transaction} and thus {\bf not} recorded for taxation. Taler ensures taxability only when some entity acquires exclusive control over the value of digital coins, which requires an interaction with the exchange. For such transactions, the state can obtain information from the exchange, or a bank, that identifies the entity that received the digital coins as well as the exact value of those coins. Taler also allows the exchange, and hence the state, to learn the value of digital coins withdrawn by a customer---but not how, where, or when they were spent. \subsection{Anonymity} An anonymous communication channel such as Tor~\cite{tor-design} is used for all communication between the customer and the merchant. Ideally, the customer's anonymity is limited only by this channel; however, the payment system does additionally reveal that the customer is one of the patrons of the exchange. There are naturally risks that the customer-merchant business operation may leak identifying information about the customer. At least, customers have some options to defend their privacy against nosey merchants however, possibly even when dealing with physical goods \cite{apod}. We consider information leakage specific to the business logic to be outside of the scope of the design of Taler. Ideally, customer should use an anonymous communication channel with the exchange to avoid leaking IP address information; however, the exchange would typically learn the customer's identity from the wire transfer that funds the customer's withdraw anonymous digital coins. In fact, this is desirable as there might be rules and regulations designed to limit the amount of anonymous digital cash that an individual customer can withdraw in a given time period, similar to how states today sometimes impose limits on cash withdrawals~\cite{france2015cash,greece2015cash}. Taler is only anonymous with respect to {\em payments}, as the exchange 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. In this respect, Taler provides exactly the same scheme for unconditional anonymous payments as was proposed by Chaum~\cite{chaum1983blind,chaum1990untraceable} over 30 years ago. While the customer thus has anonymity for purchases, the exchange will always learn the merchant's identity in order to credit the merchant's account. This is simply necessary for taxation, as Taler is supposed to make information about funds received by any entity transparent to the state. % Technically, the merchant could still %use an anonymous communication channel to communicate with the exchange. %However, in order to receive the traditional currency the exchange will %require (SEPA) account details for the deposit. %As both the initial transaction between the customer and the exchange as %well as the transactions between the merchant and the exchange do not have %to be done anonymously, there might be a formal business contract %between the customer and the exchange and the merchant and the exchange. Such %a contract may provide customers and merchants some assurance that %they will actually receive the traditional currency from the exchange %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 exchange to establish a reputation and to %minimize cost, it is more likely that the exchange 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} in Taler is a public-private key pair which derives its financial value from a signature over the coin's public key by a exchange. The exchange is expected to have multiple {\em coin signing key} pairs available for signing, each representing a different coin denomination. These coin signing keys have an expiration date, before which any coins signed with it must be spent or refreshed. This allows the exchange to eventually discard records of old transactions, thus limiting the records that the exchange must retain and search to detect double-spending attempts. Furthermore, the exchange 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. In this way, if a private coin signing key were to be compromised, the exchange would detect this once more coins were redeemed than the total that was signed into existence using that coin signing key. In this case, the exchange could allow authentic customers to exchange their unspent coins that were signed with the compromised private key, while refusing further anonymous transactions involving those coins. As a result, the financial damage of losing a private signing key can be limited to at most twice the amount originally signed with that key. To ensure that the exchange does not enable deanonymization of users by signing each coin with a fresh coin signing key, the exchange 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 exchange and the auditor. Before a customer can withdraw a coin from the exchange, he has to pay the exchange the value of the coin, as well as processing fees. This is done using other means of payments, such as wire transfers or by having a personal {\em reserve} at the exchange, which is equivalent to a bank account with a positive balance. Taler assumes that the customer has a {\em withdrawal authorization key} to identify himself as authorized to withdraw funds from the reserve. By signing the withdrawal request messages using this withdrawal authorization key, the customer can prove to the exchange that he is the individual authorized to withdraw anonymous digital coins from his reserve. The exchange will record the withdrawal messages with the reserve record as proof that the anonymous digital coin was created for the correct customer. We note that the specifics of how the customer authenticates to the exchange are orthogonal to the rest of the system, and multiple methods can be supported. %To put it differently, unlike %modern cryptocurrencies like BitCoin, Taler's design simply %acknowledges that primitive accumulation~\cite{engels1844} predates %the system and that a secure method to authenticate owners exists. After a coin is exchanged, 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 exchange by its public key; however, due to the use of blind signatures, the exchange does not learn the public key during the exchange 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 exchange to obtain the amount in traditional currency. If the customer is cheating and the coin was already spent, the exchange provides cryptographic proof of the fraud to the merchant, who will then refuse the transaction. The exchange is typically expected to transfer the funds to the merchant using a wire transfer or by crediting the merchant's individual account, depending on what is appropriate to the domain of the traditional currency. To allow exact payments without requiring the customer to keep a large amount of change'' in stock and possibly perform thousands of signatures for larger transactions, the payment systems allows partial spending where just a fraction of a coin's total value is transferred. Consequently, the exchange the must not only store the identifiers of spent coins, but also the fraction of the coin that has been spent. \subsection{Refreshing Coins} In this and other scenarios it is thus possible that a customer has revealed the public key of a coin to a merchant, but not ultimately signed over the full value of the coin. If the customer then continues to directly use the coin in other transactions, merchants and the exchange could link the various transactions as they all share the same public key for the coin. The owner of such a {\em dirty} coin might therefore want to exchange it for a {\em fresh} coin to ensure unlinkability with future transactions. % with the previous operation. Even if a coin is not dirty, the owner of a coin may want to exchange it 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 {\em melt} it for fresh coins of the same value 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. % Meh, this paragraph sucks : We therefore demand two main properties from the refresh protocol: First, the exchange must not be able to link the fresh coin's public key to the public key of the dirty coin. Second, the exchange can ensure that the owner of the dirty coin can determine the private key of the fresh coin, thereby preventing the refresh protocol from being used to construct a transaction. %As with other operations, the refreshing protocol must also protect %the exchange from double-spending; similarly, the customer has to have %cryptographic evidence if there is any misbehavior by the exchange. %Finally, the exchange 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 exchange to customers and %merchants. \section{Taler's Cryptographic Protocols} % In this section, we describe the protocols for Taler in detail. We shall assume for the sake of brevity that a recipient of a signed message always first checks that the signature is valid, aborting the operation if not. Additionally, we assume that the receiver of a signed message is either told the public key, or knows it from the context, and that the signature contains additional identification as to the purpose of the signature, making it impossible to use a signature in a different context. The exchange has an {\em online message signing key} used for signing messages, as opposed to coins. The exchange's long-term offline key is used to certify both the coin signing keys and the online message signing key of the exchange. The exchange's long-term offline key is assumed to be known to both customers and merchants and is certified by the auditors. As we are dealing with financial transactions, we explicitly describe 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 cumulative, 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 exchange have been received, assuming the records are also no longer needed for tax purposes. The exchange's bank transfers dealing in traditional currency are expected to be recorded for tax authorities to ensure taxability. \subsection{Withdrawal} Let $G$ be the generator of an elliptic curve. To withdraw anonymous digital coins, the customer performs the following interaction with the exchange: \begin{enumerate} \item The customer identifies a exchange 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 := c_s G$, \item blinding factor $b$, and commits $\langle W, C, b \rangle$ to disk. \end{itemize} \item The customer transfers an amount of money corresponding to at least $K_p$ to the exchange, with $W_p$ in the subject line of the transaction. \item The exchange receives the transaction and credits the $W_p$ reserve with the respective amount in its database. \item The customer sends $S_W(B_b(C_p))$ to the exchange to request withdrawal of $C$; here, $B_b$ denotes Chaum-style blinding with blinding factor $b$. \item The exchange checks if the same withdrawal request was issued before; in this case, it sends $S_{K}(B_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 exchange 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 and response $\langle S_W(B_b(C_p)), S_K(B_b(C_p)) \rangle$ in its database for future reference, \item deducts the amount corresponding to $K_p$ from the reserve, \end{enumerate} and then sends $S_{K}(B_b(C_p))$ to the customer. If the guards for the transaction fail, the exchange sends a descriptive error back to the customer, with proof that it operated correctly. Assuming the signature was valid, this would involve showing the transaction history for the reserve. \item The customer computes and verifies the unblinded signature $S_K(C_p) = U_b(S_K(B_b(C_p)))$. The customer saves the coin $\langle S_K(C_p), c_s \rangle$ to local wallet on disk. \end{enumerate} We note that the authorization to create and access a reserve using a withdrawal key $W$ is just one way to establish that the customer is authorized to withdraw funds. If a exchange has other ways to securely authenticate customers and establish that they are authorized to withdraw funds, those can also be used with Taler. \subsection{Exact and partial spending} A customer can spend coins at a merchant, under the condition that the merchant trusts the specific exchange that exchanged the coin. Merchants are identified by their key $M := (m_s, M_p)$ where the public key $M_p$ must be known to the customer a priori. We now describe the protocol between the customer, merchant, and exchange for a transaction in which the customer spends a coin $C := (c_s, C_p)$ with signature $\widetilde{C} := S_K(C_p)$ where $K$ is the exchange's demonination key. \begin{enumerate} \item\label{contract} Let $\vec{D} := D_1, \ldots, D_n$ be the list of exchanges accepted by the merchant where each $D_j$ is a exchange's public key. The merchant creates a digitally signed contract $\mathcal{A} := S_M(m, f, a, H(p, r), \vec{D})$ where $m$ is an identifier for this transaction, $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 a random nonce. The merchant commits $\langle \mathcal{A} \rangle$ to disk and sends $\mathcal{A}$ to the customer. \item\label{deposit} The customer should already possess a coin exchanged by a exchange that is accepted by the merchant, meaning $K$ should be publicly signed by some $D_j \in \{D_1, D_2, \ldots, D_n\}$, and has a value $\geq f$. \item The customer 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_j\rangle$ to the merchant, where $D_j$ is the exchange which signed $K$. \item The merchant gives $(\mathcal{D}, p, r)$ to the exchange, revealing $p$ only to the exchange. \item The exchange validates $\mathcal{D}$ and checks for double spending. If the coin has been involved in previous transactions and the new one would exceed its remaining value, it sends an error with the records from the previous transactions back to the merchant. % If double spending is not found, the exchange commits $\langle \mathcal{D} \rangle$ to disk and notifies the merchant that the deposit operation was successful. \item The merchant commits and forwards the notification from the exchange to the customer, confirming the success or failure of the operation. \end{enumerate} We have simplified the exposition by assuming that one coin suffices, but in practice a customer can use multiple coins from the same exchange where the total value adds up to $f$ by running the following steps for each of the coins. There is a risk of metadata leakage if a customer acquires a coin in responce to the merchant, or if a customer uses coings issued by multiple exchanges together. If a transaction is aborted after Step~\ref{deposit}, subsequent transactions with the same coin could 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 exchange. %\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$ exchange)}; %\node (C) [def,below=of B]{confirm (or refuse) lock (exchange $\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$ exchange)}; %\node (G) [def,below=of F]{transfer confirmation (exchange $\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 exchange in the coin spending % protocol} %\label{fig:spending_protocol_interactions} %\end{figure} \subsection{Refreshing} \label{sec:refreshing} We now describe the refresh protocol whereby a dirty coin $C'$ of denomination $K$ is melted to obtain a fresh coin $\widetilde{C}$ with the same denomination. In practice, Taler uses a natural extension where multiple fresh coins are generated a the same time to enable giving precise change matching any amount. 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 randomly generates \begin{itemize} \item transfer key $T^{(i)} := \left(t^{(i)}_s,T^{(i)}_p\right)$ where $T^{(i)}_p := t^{(i)}_s G$, \item coin key pair $C^{(i)} := \left(c_s^{(i)}, C_p^{(i)}\right)$ where $C^{(i)}_p := c^{(i)}_s G$, and \item blinding factors $b^{(i)}$. \end{itemize} The customer then computes $E^{(i)} := E_{K_i}\left(c_s^{(i)}, b^{(i)}\right)$ where $K_i := H(c'_s T_p^{(i)})$, and commits $\langle C', \vec{T}, \vec{C}, \vec{b} \rangle$ to disk. Our computation of $K_i$ is effectively a Diffie-Hellman operation between the private key $c'_s$ of the original coin with the public transfer key $T_p^{(i)}$. \item The customer computes $B^{(i)} := B_{b^{(i)}}(C^{(i)}_p)$ for $i \in \{1,\ldots,\kappa\}$ and sends a commitment $S_{C'}(\vec{E}, \vec{B}, \vec{T_p})$ to the exchange. \item The exchange 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_p}) \rangle$ to disk. Auditing processes should assure that $\gamma$ is unpredictable until this time to prevent the exchange from assisting tax evasion. \item The exchange sends $S_{K'}(C'_p, \gamma)$ to the customer where $K'$ is the exchange's message signing key. \item The customer commits $\langle C', S_K(C'_p, \gamma) \rangle$ to disk. \item The customer computes $\mathfrak{R} := \left(t_s^{(i)}\right)_{i \ne \gamma}$ and sends $S_{C'}(\mathfrak{R})$ to the exchange. \item \label{step:refresh-ccheck} The exchange checks whether $\mathfrak{R}$ is consistent with the commitments; specifically, it computes for $i \not= \gamma$: \vspace{-2ex} \begin{minipage}{5cm} \begin{align*} \overline{K}_i :&= H(t_s^{(i)} C_p'), \\ (\overline{c}_s^{(i)}, \overline{b_i}) :&= D_{\overline{K}_i}(E^{(i)}), \\ \overline{C^{(i)}_p} :&= \overline{c}_s^{(i)} G, \end{align*} \end{minipage} \begin{minipage}{5cm} \begin{align*} \overline{T_p^{(i)}} :&= t_s^{(i)} G, \\ \\ \overline{B^{(i)}} :&= B_{\overline{b_i}}(\overline{C_p^{(i)}}), \end{align*} \end{minipage} and checks if $\overline{B^{(i)}} = B^{(i)}$ and $\overline{T^{(i)}_p} = T^{(i)}_p$. \item \label{step:refresh-done} If the commitments were consistent, the exchange sends the blind signature $\widetilde{C} := S_{K}(B^{(\gamma)})$ to the customer. Otherwise, the exchange responds with an error indicating the location of the failure. \end{enumerate} %\subsection{N-to-M Refreshing} % %TODO: Explain, especially subtleties regarding session key / the spoofing attack that requires signature. \subsection{Linking} For a coin that was successfully refreshed, the exchange responds to a request $S_{C'}(\mathtt{link})$ with $(T^{(\gamma)}_p$, $E^{(\gamma)}, \widetilde{C})$. % This allows the owner of the melted coin to also obtain the private key of the new coin, even if the refreshing protocol was illicitly executed with the help of another party who generated $\vec{c_s}$ and only provided $\vec{C_p}$ and other required information to the old owner. As a result, linking ensures that access to the new coins exchanged by the refresh protocol is always {\em shared} with the owner of the melted coins. This makes it impossible to abuse the refresh protocol for {\em transactions}. The linking request is not expected to be used at all during ordinary operation of Taler. If the refresh protocol is used by Alice to obtain change as designed, she already knows all of the information and thus has little reason to request it via the linking protocol. The fundamental reason why the exchange must provide the link protocol is simply to provide a threat: if Bob were to use the refresh protocol for a transaction of funds from Alice to him, Alice may use a link request to gain shared access to Bob's coins. Thus, this threat prevents Alice and Bob from abusing the refresh protocol to evade taxation on transactions. If Bob trusts Alice to not execute the link protocol, then they can already conspire to evade taxation by simply exchanging the original private coin keys. This is permitted in our taxation model as with such trust they are assumed to be the same entity. The auditor can anonymously check if the exchange correctly implements the link request, thus preventing the exchange operator from legally disabling this protocol component. Without the link operation, Taler would devolve into a payment system where both sides can be anonymous, and thus no longer provide taxability. \subsection{Error handling} During operation, there are three main types of errors that are expected. First, in the case of faulty clients, the responding server will generate an error message with detailed cryptographic proofs demonstrating that the client was faulty, for example by providing proof of double-spending or providing the previous commit and the location of the missmatch in the case of the reveal step in the refresh protocol. It is also possible that the server may claim that the client has been violating the protocol. In these cases, the clients should verify any proofs provided and if they are acceptable, notify the user that they are somehow faulty. Similar, if the server indicates that the client is violating the protocol, the client should record the interaction and enable the user to file a bug report. The second case is a faulty exchange service provider. Such faults will be detected because of protocol violations, such as providing a faulty proof or no proof. In this case, the client is expected to notify the auditor, providing a transcript of the interaction. The auditor can then anonymously replay the transaction, and either provide the now correct response to the client or take appropriate legal action against the faulty provider. The third case are transient failures, such as network failures or temporary hardware failures at the exchange service provider. Here, the client may receive an explicit protocol indication, such as an HTTP response code 500 internal server error'' or simply no response. The appropriate behavior for the client is to automatically retry after 1s, and twice more at randomized times within 1 minute. If those three attempts fail, the user should be informed about the delay. The client should then retry another three times within the next 24h, and after that time the auditor be informed about the outage. Using this process, short term failures should be effectively obscured from the user, while malicious behavior is reported to the auditor who can then presumably rectify the situation, such as by shutting down the operator and helping customers to regain refunds for coins in their wallets. To ensure that such refunds are possible, the operator is expected to always provide adequate securities for the amount of coins in circulation as part of the certification process. \subsection{Refunds} The refresh protocol offers an easy way to enable refunds to customers, even if they are anonymous. Refunds can be supported by including a public signing key of the merchant in the transaction details, and having the customer keep the private key of the spent coins on file. Given this, the merchant can simply sign a {\em refund confirmation} and share it with the exchange and the customer. Assuming the exchange has a way to recover the funds from the merchant, or has not yet performed the wire transfer, the exchange can simply add the value of the refunded transaction back to the original coin, re-enabling those funds to be spent again by the original customer. This anonymous customer can then use the refresh protocol to melt the refunded coin and create a fresh coin that is unlinkable to the refunded transaction. \section{Discussion} Taler's security is largely equivalent to that of Chaum's original design without online checks or the cut-and-choose revelation of double-spending customers for offline spending. We specifically note that the digital equivalent of the Columbian Black Market Exchange''~\cite{fatf1997} is a theoretical problem for both Chaum and Taler, as individuals with a strong mutual trust foundation can simply copy electronic coins and thereby establish a limited form of black transfers. However, unlike the situation with physical checks with blank recipients in the Columbian black market, the transitivity is limited as each participant can deposit the electronic coins and thereby cheat any other participant, while in the Columbian black market each participant only needs to trust the issuer of the check and not also all previous owners of the physical check. As with any unconditionally anonymous payment system, the Perfect Crime'' attack~\cite{solms1992perfect} where blackmail is used to force the exchange to issue anonymous coins also continues to apply in principle. However, as mentioned Taler does facilitate limits on withdrawals, which we believe is a better trade-off than the problematic escrow systems where the necessary intransparency actually facilitates voluntary cooperation between the exchange and criminals~\cite{sander1999escrow} and where state can selectively deanonymize activists to support the deep state's quest for absolute security. \subsection{Offline Payments} Chaum's original proposals for anonymous digital cash avoided the need for online interactions with the exchange to detect double spending by providing a means to deanonymize customers involved in double-spending. We believe that this is problematic as the exchange 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 exchange may try to defraud the other participants and disappear. While this is still a risk, and regular financial audits are required to protect against it, this is more manageable and significantly cheaper compared to recovering funds via the court system from customers. Chaum's method for offline payments would also be incompatible with the refreshing protocol (Section~\ref{sec:refreshing}) which enables the crucial feature of giving unlinkable change. The reason is that if the owner's identity were embedded in coins, it would be leaked to the exchange as part of the reveal operation in the cut-and-choose operation of the refreshing protocol. %\subsection{Merchant Tax Audits} % %For a tax audit on the merchant, the exchange 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 %subjected to financial penalties by the state in relation to the %amount transferred by the traditional currency transfer. \subsection{Cryptographic proof vs. evidence} In this paper we have use the term proof'' in many places as the protocol provides cryptographic proofs of which parties behave correctly or incorrectly. However, as~\cite{fc2014murdoch} point out, in practice financial systems need to provide evidence that holds up in courts. Taler's implementation is designed to export evidence and upholds the core principles described in~\cite{fc2014murdoch}. In particular, in providing the cryptographic proofs as evidence none of the participants have to disclose their core secrets, the process is covered by standard testing procedures, and the full trusted computing base (TCB) is public and free software. %\subsection{System Performance} % %We performed some initial performance measurements for the various %operations on our exchange implementation. The main conclusion was that %the computational and bandwidth cost for transactions described in %this paper is smaller than $10^{-3}$ cent/transaction, and thus %dwarfed by the other business costs for the exchange. However, this %figure excludes the cost of currency transfers using traditional %banking, which a exchange operator would ultimately have to interact with. %Here, exchange 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 current balance and profits of the %exchange are also easily determined, thus audits can be used to ensure %that the exchange operates correctly. The libre implementation and open %protocol may finally enable modern society to upgrade to proper %electronic wallets with efficient, secure and privacy-preserving %transactions. % commented out for anonymized submission %\subsection*{Acknowledgements} %This work was supported by a grant from the Renewable Freedom Foundation. % FIXME: ARED? %We thank Tanja Lange, Dan Bernstein, Luis Ressel and Fabian Kirsch for feedback on an earlier %version of this paper, Nicolas Fournier for implementing and running %some performance benchmarks, and Richard Stallman, Hellekin Wolf, %Jacob Appelbaum for productive discussions and support. \bibliographystyle{alpha} \bibliography{taler,rfc} \newpage \appendix \section{Optional features} In this appendix we detail various optional features that can be added to the basic protocol to reduce transaction costs for certain interactions. However, we note that Taler's transaction costs are expected to be so low that these features are likely not particularly useful in practice: When we performed some initial performance measurements for the various operations on our exchange implementation, the main conclusion was that the computational and bandwidth cost for transactions described in this paper is smaller than $10^{-3}$ cent/transaction, and thus dwarfed by the other business costs for the exchange. We note that the $10^{-3}$ cent/transaction estimate excludes the cost of wire transfers using traditional banking, which a exchange operator would ultimately have to interact with. Here, exchange operators should be able to reduce their expenses by aggregating multiple transfers to the same merchant. As a result of the low cost of the interaction with the exchange in Taler today, we expect that transactions with amounts below Taler's internal transaction costs to be economically meaningless. Nevertheless, we document various ways how such transactions could be achieved within Taler. \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 exchange 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 insufficient funds because too much has been spent or is already locked, the exchange provides the owner's deposit or locking request and signature to prove the attempted fraud by the customer. Otherwise, the exchange 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 exchange before the lock permission expires to ensure that no other merchant redeems 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 exchanges $D_1, \ldots, D_n$ accepted by the merchant where each $D_j$ is a exchange's public key. \item\label{lock2} The customer must possess or acquire a coin $\widetilde{C}$ signed by a exchange that is accepted by the merchant, i.e. $K$ should be signed by some $D_j \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_j\rangle$ to the merchant, where $D_j$ is the exchange which signed $K$. \item The merchant asks the exchange to apply the lock by sending $\langle \mathcal{L} \rangle$ to the exchange. \item The exchange validates $\widetilde{C}$ and detects double spending in the form of existing \emph{deposit-permission} or lock-permission records for $\widetilde{C}$. If such records exist and indicate that insufficient funds are left, the exchange sends those records to the merchant, who can then use the records to prove the double spending to the customer. If double spending is not found, the exchange 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 nonce. 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}, \widetilde{L}, 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 exchange, revealing his payment information. \item The exchange verifies $(\mathcal{D}, p, r)$ for its validity and checks against double spending, while of course permitting the merchant to withdraw funds from the amount that had been locked for this merchant. \item If $\widetilde{C}$ is valid and no equivalent \emph{deposit-permission} for $\widetilde{C}$ and $\widetilde{L}$ exists on disk, the exchange performs the following transaction: \begin{enumerate} \item $\langle \mathcal{D}, p, r \rangle$ is committed to 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})$. \end{enumerate} Finally, the exchange sends a confirmation to the merchant. \item If the deposit record $\langle \mathcal{D}, p, r \rangle$ already exists, the exchange sends the confirmation 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 ,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 exchange in the coin spending % protocol} %\label{fig:spending_protocol_interactions} %\end{figure} \subsection{Probabilistic donations} Similar to Peppercoin, Taler supports probabilistic {\em micro}donations of coins to support cost-effective transactions for small amounts. We consider amounts to be micro'' if the value of the transaction is close or even below the business cost of an individual transaction to the exchange. To support microdonations, 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. More specifically, a microdonation of value$\epsilon$is upgraded to a macropayment of value$m$with a probability of$\frac{\epsilon}{m}$. Here,$m$is chosen such that the business transaction cost at the exchange is small in relation to$m$. The exchange is only involved in the tiny fraction of transactions that are upgraded. On average both customers and merchants end up paying (or receiving) the expected amount$\epsilon$per microdonation. 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 exchange. 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 exchange. 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 fraudulent 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 exchange even if the merchant looses the coin flip, such a scheme is unsuitable for microdonations as the transaction costs from involving the exchange 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} 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. Still, to clarify that the customer must be honest, we prefer the term micro{\em donations} over micro{\em payments} for this scheme. 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} Evidently the customer can cheat'' by aborting the transaction in Step 3 of the microdonation protocol if the outcome is unfavorable --- 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. \newpage \section{Notation summary} The paper uses the subscript$p$to indicate public keys and$s$to indicate secret (private) keys. For keys, we also use small letters for scalars and capital letters for points on an elliptic curve. The capital letter without the subscript$p$stands for the key pair. The superscript$(i)$is used to indicate one of the elements of a vector during the cut-and-choose protocol. Bold-face is used to indicate a vector over these elements. A line above indicates a value computed by the verifier during the cut-and-choose operation. We use$f()$to indicate the application of a function$f$to one or more arguments. Records of data being committed to disk are represented in between$\langle\rangle$. \begin{description} \item[$K_s$]{Private (RSA) key of the exchange used for coin signing} \item[$K_p$]{Public (RSA) key corresponding to$K_s$} \item[$K$]{Public-priate (RSA) coin signing key pair$K := (K_s, K_p)$} \item[$b$]{RSA blinding factor for RSA-style blind signatures} \item[$B_b()$]{RSA blinding over the argument using blinding factor$b$} \item[$U_b()$]{RSA unblinding of the argument using blinding factor$b$} \item[$S_K()$]{Chaum-style RSA signature,$S_K(C) = U_b(S_K(B_b(C)))$} \item[$w_s$]{Private key from customer for authentication} \item[$W_p$]{Public key corresponding to$w_s$} \item[$W$]{Public-private customer authentication key pair$W := (w_s, W_p)$} \item[$S_W()$]{Signature over the argument(s) involving key$W$} \item[$m_s$]{Private key from merchant for authentication} \item[$M_p$]{Public key corresponding to$m_s$} \item[$M$]{Public-private merchant authentication key pair$M := (m_s, M_p)$} \item[$S_M()$]{Signature over the argument(s) involving key$M$} \item[$G$]{Generator of the elliptic curve} \item[$c_s$]{Secret key corresponding to a coin, scalar on a curve} \item[$C_p$]{Public key corresponding to$c_s$, point on a curve} \item[$C$]{Public-private coin key pair$C := (c_s, C_p)$} \item[$S_{C}()$]{Signature over the argument(s) involving key$C$(using EdDSA)} \item[$c_s'$]{Private key of a dirty'' coin (otherwise like$c_s$)} \item[$C_p'$]{Public key of a dirty'' coin (otherwise like$C_p$)} \item[$C'$]{Dirty coin (otherwise like$C$)} \item[$\widetilde{C}$]{Exchange signature$S_K(C_p)$indicating validity of a fresh coin (with key$C$)} \item[$n$]{Number of exchanges accepted by a merchant} \item[$j$]{Index into a set of accepted exchanges,$i \in \{1,\ldots,n\}$} \item[$D_j$]{Public key of a exchange (not used to sign coins)} \item[$\vec{D}$]{Vector of$D_j$signifying exchanges accepted by a merchant} \item[$a$]{Complete text of a contract between customer and merchant} \item[$f$]{Amount a customer agrees to pay to a merchant for a contract} \item[$m$]{Unique transaction identifier chosen by the merchant} \item[$H()$]{Hash function} \item[$p$]{Payment details of a merchant (i.e. wire transfer details for a bank transfer)} \item[$r$]{Random nonce} \item[${\cal A}$]{Complete contract signed by the merchant} \item[${\cal D}$]{Deposit permission, signing over a certain amount of coin to the merchant as payment and to signify acceptance of a particular contract} \item[$\kappa$]{Security parameter$\ge 3$} \item[$i$]{Index over cut-and-choose set,$i \in \{1,\ldots,\kappa\}$} \item[$\gamma$]{Selected index in cut-and-choose protocol,$\gamma \in \{1,\ldots,\kappa\}$} \item[$t^{(i)}_s$]{private transfer key, a scalar} \item[$T^{(i)}_p$]{public transfer key, point on a curve (same curve must be used for$C_p$)} \item[$T^{(i)}$]{public-private transfer key pair$T^{(i)} := (t^{(i)}_s,T^{(i)}_s)$} \item[$\vec{T}$]{Vector of$T^{(i)}$} \item[$c_s^{(i)}$]{Secret key corresponding to a fresh coin, scalar on a curve} \item[$C_p^{(i)}$]{Public key corresponding to$c_s^{(i)}$, point on a curve} \item[$C^{(i)}$]{Public-private coin key pair$C^{(i)} := (c_s^{(i)}, C_p^{(i)})$} \item[$\vec{C}$]{Vector of$C^{(i)}$(public and private keys)} \item[$b^{(i)}$]{Blinding factor for RSA-style blind signatures} \item[$\vec{b}$]{Vector of$b^{(i)}$} \item[$B^{(i)}$]{Blinding of$C_p^{(i)}$} \item[$\vec{B}$]{Vector of$B^{(i)}$} \item[$K_i$]{Symmetric encryption key derived from ECDH operation via hashing} \item[$E_{K_i}()$]{Symmetric encryption using key$K_i$} \item[$E^{(i)}$]{$i$-th encryption of the private information$(c_s^{(i)}, b_i)$} \item[$\vec{E}$]{Vector of$E^{(i)}$} \item[$\cal{R}$]{Tuple of revealed vectors in cut-and-choose protocol, where the vectors exclude the selected index$\gamma$} \item[$\overline{K_i}$]{Encryption keys derived by the verifier from DH} \item[$\overline{B^{(i)}}$]{Blinded values derived by the verifier} \item[$\overline{T_p^{(i)}}$]{Public transfer keys derived by the verifier from revealed private keys} \item[$\overline{c_s^{(i)}}$]{Private keys obtained from decryption by the verifier} \item[$\overline{b_s^{(i)}}$]{Blinding factors obtained from decryption by the verifier} \item[$\overline{C^{(i)}_p}$]{Public coin keys computed from$\overline{c_s^{(i)}}\$ by the verifier} \end{description} \end{document}