博 士 論 文

Probabilistic Micropayments
in Decentralized Blockchain
Taisei TAKAHASHI
高橋 大成

情報セキュリティ大学院大学
情報セキュリティ研究科
情報セキュリティ専攻
2022 年 9 月

Abstract
Starting with Bitcoin, proposed in 2008, many decentralized blockchain schemes have been
proposed and implemented.

Blockchain has strong potential not only as a cryptocur-

rency, but also with smart contracts, an automated contract enforcement system. However,blockchain has two structural challenges. One is fast payments, and the second is throughput. In this thesis, we assume tamper-proof hardware and solve the three challenges.

Secure Offline Payments in Bitcoin We have achieved fast payments on the blockchain.
Double-spending attacks on fast payments are one of the fatal architectural problems in
Cryptocurrencies. The prior study proposed an offline fast payment scheme that relies ontamper-proof wallets produced by trustworthy manufacturers. With the wallets, the payee
can immediately trust the transactions generated by the wallets without waiting for theirregistration to the blockchain. They proposed a protocol that makes use of a fragmentof the main blockchain to prove to the wallets the legitimacy of preloaded coins. One
drawback is that their protocol requires a trusted online time-stamp server to prove thatthe fragment is from honest miners. Otherwise, it sacrifices usability. To eliminate such an
online trustee, we took the opposite approach that the payee (not the wallets) verifies thelegitimacy of preloaded coins during offline payment. Consequently, our result shows that,with lightweight tamper-proof wallets, completely decentralized offline payment is possible
without any modification to the existing Bitcoin network.
iii
Decentralized Probabilistic Micropayments with Transferability Micropayments
are one of the challenges in cryptocurrencies. The problems in realizing micropaymentsin the blockchain are the low throughput and the high blockchain transaction fee. As asolution, decentralized probabilistic micropayment has been proposed. The winning amountis registered in the blockchain, and the tickets are issued to be won with probability, whichallows us to aggregate approximately 1/p transactions into one. Unfortunately, existing
solutions do not allow for ticket transferability, and the smaller p, the more difficult it is to
use them in the real world. We propose a novel decentralized probabilistic micropayment
Transferable Scheme. It allows tickets to be transferable among users. By allowing tickets
to be transferable, we can make them smaller. We also propose a novel Proportional Fee
Scheme. This is a scheme where each time a ticket is transferred, a portion of the blockchaintransaction fee will be charged. With the proportional fee scheme, users will have theadvantage of sending money with a smaller fee than they would generally send through theblockchain. For example, sending one dollar requires only ten cents.

Anonymous Decentralized Probabilistic Micropayments with Transferability We
propose VeloCash, Decentralized Probabilistic Micropayments with Transferability, which
preserves anonymity. As a tamper-proof hardware assumption, VeloCash uses Attested Execution Secure Processors (AESP), a formal abstraction of secure processors with attested
execution functionality and Direct Anonymous Attestation (DAA) to achieve anonymity forsending and receiving tickets. Even under anonymity, VeloCash can detect double-spending
attacks perfectly and revoke the adversary’s device.

Publication list
This thesis is based on the below publications.

Peer Reviewed Papers[THO22] Taisei Takahashi, Taishi Higuchi and Akira Otsuka. ”VeloCash: Anonymous Decentralized Probabilistic Micropayments with Transferability” in IEEE Access, 2022.

Peer Reviewed Proceedings of International Conferences[TO21] Taisei Takahashi and Akira Otsuka. ”Probabilistic Micropayments with Transferability”. In European Symposium on Research in Computer Security - ESORICS 2021,
Lecture Notes in Computer Science, pages 390–406, Cham, 2021. Springer International Publishing.
[TO20] Taisei Takahashi and Akira Otsuka. ”Short Paper: Secure Offline Payments in
Bitcoin”. In Workshop on Trusted Smart Contracts In Association with Financial
Cryptography and Data Security, Lecture Notes in Computer Science, pages 12–20,
Cham, 2020. Springer International Publishing.

iii

iv

Acknowledgements
Firstly, I appreciate my supervisor, Professor Akira Otsuka. Fortunately, when I started
studying blockchain five years ago, he was willing to accept that he would supervise me.
He led me to the frontier in the blockchain. He has mentored me for these five years.
Without his excellent mentorship, I would not have gone to a Ph.D. program, and I would
not have been able to complete this work. I sincerely appreciate him for everything he hasdone for me. I am incredibly grateful to Professor Seiko Arita, Professor Kouichi Sakurai,
and Associate Professor Kazumasa Omote for their constructive suggestions and valuableadvice. I was able to take the first step into cryptography from Prof. Arita’s lecture on
cryptography. I am thankful to the members of Otsuka Laboratory. They have given me
many cooperations, notices, and support throughout my laboratory life. In particular, theytaught us various aspects of blockchain and cryptography. I want to show my appreciation
to my managers and colleagues for their understanding and cooperation. Mainly, I sincerely
appreciate Mr. Akira Nagata and Ms. Yumiko Baba in Serverworks Co., Ltd. They gave me
the precious opportunity of researching blockchain at the Institute of Information Security.
I could not fulfill this work without their excellent cooperation. Furthermore, I kindly thankmy family. They always encourage and believe me. I sincerely appreciate them for theiraffection while studying and staying at home. Finally, I appreciate anonymous reviewers fortheir valuable comments.

v

vi

List of Figures
3.1

Online Pre-loading protocol . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2

Offline payment protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.3

Coin redemption and double-spending wallet revocation protocol . . . . . . .

17

4.1

Overall Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.2

Payment with Lottery Tickets . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.3

Ticket redemption and double-spending wallet revocation protocol . . . . . .

30

4.4

Proportional Fee Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.5

1
1
Ticket value per generation when β = $100, p = 100
and q = 10
. Figure 4.5ashows the value of a ticket, depending on the number of generations i of theticket. As shown in Figure 4.5b, at roughly 50 generations or more, the valueof the ticket is less than $1, making it micropayment. . . . . . . . . . . . . .
4.6

37

1
Frequency of the ticket values, same as Figure 4.5, when β = $100, p = 100
1
and q = 10
. Roughly more than 50 generations are worth less than $1. . . . .

37

4.7

Double-spending Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.8

Collision detection round . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

5.1

Game for soundness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5.2

Game for unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.3

Game for exculpability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

5.4

Game for coin anonymity

62. . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii

viii

LIST OF FIGURES
5.5

Game for user anonymity. . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.6

Game for Coin transparency . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.7

The algorithms of Gatt [Σ, reg, gpk, AE] . . . . . . . . . . . . . . . . . . . . . .

66

5.8

The algorithms of progw . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.9

Escrow Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

5.10 Anonymous Payment with Lottery Tickets (Payment from X to Y ) . . . . .

82

5.11 Ticket redemption

84. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.1 EPID’s Join protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
B.1 EPID game for Anonymity and Unforgeability . . . . . . . . . . . . . . . . . 111

Contents

List of Figuresvii

1 Introduction3

1.1

Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.1

Secure Offline Payments in Bitcoin . . . . . . . . . . . . . . . . . . .

4

1.2.2

Decentralized Probabilistic Micropayments with Transferability . . .

4

1.2.3

Anonymous Decentralized Probabilistic Micropayments with Transferability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3

Organization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Preliminaries

5
5
7

2.1

Security Notions of Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2

Probabilistic Micropayments . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3

Direct Anonymous Attestation (DAA) . . . . . . . . . . . . . . . . . . . . .

8

2.4

Verifiable Delay Functions (VDF) . . . . . . . . . . . . . . . . . . . . . . . .

93 Secure Offline Payments in Bitcoin
3.1

3.2

11

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.1.1

Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12Security Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

ix

x

CONTENTS
3.3

Secure Offline Payments in Bitcoin . . . . . . . . . . . . . . . . . . . . . . .

14

3.4

Security Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.5

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4 Transferable Probabilistic Micropayments

23

4.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

4.2

Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.3

Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

4.3.1

Payment Channels and Networks . . . . . . . . . . . . . . . . . . . .

26

Ticket Transfer Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.4.1

Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.4.2

Escrow Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4.4.3

Payment with Lottery Ticket . . . . . . . . . . . . . . . . . . . . . .

28

4.4.4

Ticket Winning and Revocation . . . . . . . . . . . . . . . . . . . . .

29

Ticket Winning Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.5.1

Structure of the ticket . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.5.2

Ticket Winning Condition . . . . . . . . . . . . . . . . . . . . . . . .

34

4.6

Proportional Fee Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.7

Security Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.7.1

Detection Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.8.1

43

4.4

4.5

4.8

Open problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 VeloCash

45

5.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

5.2

Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

5.3

Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

5.3.1

48

Direct Anonymous Attestation (DAA) . . . . . . . . . . . . . . . . .

CONTENTS
5.3.2

xi
Specification of EPID . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

Anonymous Ticket Transfer Protocol . . . . . . . . . . . . . . . . . . . . . .

52

5.4.1

Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

5.4.2

Security Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

5.4.3

Anonymity Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

Attested Execution Secure Processors (AESP) . . . . . . . . . . . . . . . . .

64

5.5.1

Extension of AESP . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.6

Key Extractor and Revocation . . . . . . . . . . . . . . . . . . . . . . . . . .

72

5.7

Construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

Ticket Transfer Overview . . . . . . . . . . . . . . . . . . . . . . . . .

80

Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

5.8.1

Economic properties . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

5.8.2

Anonymity properties. . . . . . . . . . . . . . . . . . . . . . . . . .

90

5.8.3

Double-spending attacks Detection Methods . . . . . . . . . . . . . .

96

Efficiency analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

5.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

5.4

5.5

5.7.1
5.8

5.9

6 Conclusions

101

A Construction of EPID

103

A.0.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.0.2 Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.0.3 Sign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
A.0.4 Verify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
A.0.5 Revoke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
B Security Definition of EPID

109

C Proof of Theorem 9

113

CONTENTS

1

Bibliography

115

2

CONTENTS

Chapter 1
Introduction
In this chapter, we describe the introduction consisting of contributions and organization.

1.1

Blockchain

Blockchain technologies, the basis of cryptocurrencies, was born in 2008 with Bitcoin, proposed by an anonymous person or group, Satoshi Nakamoto [Nak09]. Cryptocurrencies andblockchain have attracted significant attention because of their Decentralized properties.
The traditional financial system is a Centralized system based on the trust of specificinstitutions, such as governments, banks, and regulators. Central banks issue paper money,
and electronic payment systems, such as credit cards, are also under the authorities’ control.
In contrast, blockchain has enabled payments that do not require the existence of a specificinstitution. Under the traditional financial system, a great deal of operational cost is required
to maintain the system; thus, the blockchain is expected to simplify and reduce the cost.
Furthermore, blockchain can be used not only as a cryptocurrency but also as a SmartContract that takes advantage of its property of ”sharing the same state globally”, which
was realized by Ethereum [Woo] in 2013. Ethereum allows the execution of smart contract
codes written in Turing-complete programming language that runs on the blockchain.
However, challenges exist for blockchain to have the same performance as the current
3

4

CHAPTER 1. INTRODUCTION

financial system. In this thesis, we address the biggest challenges that blockchain has: 1.
Fast Payments, 2. High Throughput, 3. Anonymity with Transparency.

1.2

Contributions

1.2.1

Secure Offline Payments in Bitcoin

Karame et al. [KAC12] have analyzed double-spending attacks of fast payments in Bitcoin.
This attack scheme allows an adversary to use more coins than he has for fast payment due tothe property of Bitcoin, which takes a certain amount of time to be confirmed. Generally, 6blocks, or roughly one hour before the transaction is registered and confirmed in the Bitcoin
network, are considered secure for the attack. Fast payment, i.e., a scheme that allows thereturn of goods at the same time of payment, is needed in Bitcoin.
Dmitrienko et al. [DNY17] have proposed a secure fast payment scheme in Bitcoin,assuming tamper-proof hardware. However, their proposed method requires either a trusted
online timestamp server or a limit on the duration of time coins can be used.
We propose a secure fast payment scheme in Bitcoin, following Dmitrienko et al. Unlike
Dmitrienko et al., our scheme does not require an online timestamping server or a time limit
on coins.

1.2.2

Decentralized Probabilistic Micropayments with Transferability

Due to the low throughput of the blockchain, micro payments, e.g., less than $1, are challenging to achieve.
Existing studies have proposed Decentralized Probabilistic Micropayments, where winningmoney is registered on the blockchain, lottery tickets are issued, and the tickets are used
as currency. If the winning amount of money β is registered on the blockchain and the1.3. ORGANIZATION

5

probability of winning the ticket is p, the ticket is used as a currency with an expected valueof β · p. Unfortunately, existing research shows that tickets can be sent only once from theticket issuer. Also, the smaller the winning probability p, the higher the throughput of theblockchain, but the less practical it becomes.
We propose that Decentralized Probabilistic Micropayments with Transferability that enables the transferability of ticket sending among payees as well as the issuer. Our proposed
method increases the throughput of the blockchain depending on the number of spending;however, unlike existing research, it does not reduce the utility. In addition, a $1 transfer isfeasible with a 10 cent fee, making it possible to settle payments with a smaller fee than on
the blockchain.

1.2.3

Anonymous Decentralized Probabilistic Micropayments withTransferability

Under our proposed transferable decentralized probabilistic micropayments, payments are
not anonymous. From the user’s perspective, it is desirable that the spending be anonymous
since the fact that the payment is not anonymous means that an individual’s income is
known.
We develop the transferable scheme and propose Decentralized Probabilistic Micropayments with Transferability, which preserves Anonymity, named VeloCash. Furthermore, evenunder anonymity, we ensure ”transparency” that perfectly detects double-spending attacks
and revokes the adversary.

1.3

Organization

In Chapter 2, we describe preliminaries. In Chapter 3, we describe the first work, ”Secure
Offline Payments in Bitcoin”. It realizes secure fast payment on Bitcoin. In Chapter 4,
we state the second work, ”Decentralized Probabilistic Micropayments with Transferabil-

6

CHAPTER 1. INTRODUCTION

ity”. It realizes transferable decentralized probabilistic micropayments that increase theblockchain’s throughput and enable micropayments. In Chapter 5, we mention the third
work, ”VeloCash: Anonymous Decentralized Probabilistic Micropayments with Transferability”. It realized transferable decentralized probabilistic micropayment, which preserves
anonymity with transparency. In Chapter 6, we conclude this thesis.

Chapter 2
Preliminaries
This chapter describes the security notions of blockchain, Direct Anonymous Attestation(DAA), and Attested Execution Secure Processors (AESP). Primarily, DAA and AESP aredescribed in Chapter 5.

2.1

Security Notions of Blockchain

Garay et al. [GKL15] have analyzed Bitcoin’s backbone protocol. They formalize and provethree fundamental properties: common prefix property, chain quality property, and chain
growth property.
Informally, common prefix property means that the probability that k blocks from the endof an honest user’s local chain are not prefixed to another user’s chain decreases exponentiallywith the security parameter. See for the precise statement Theorem 15 of [GKL15].

2.2

Probabilistic Micropayments

The idea of Probabilistic Micropayments has been proposed by Wheeler [Whe97] and Rivest [Riv97].
Since small payments would be costly if settled each time, they proposed a lottery-style protocol where the ticket issuer deposits a large amount of money in the bank, and the winner
7

8

CHAPTER 2. PRELIMINARIES

could receive the money if they won. The lottery tickets can be used as currency, and thevalue per ticket is regarded as the ticket’s expected value. In this scheme, the existence of abank is mandatory, and participants are limited to people who have a relationship with thebank.
MICROPAY [Ps15] and DAM [CGL+ 17] have been proposed as Decentralized Probabilistic Micropayments using blockchain. Since both have a large overhead of supporting
sequential micropayments, Almashaqbeh et al. have proposed MicroCash [ABC20] which isa light-weight protocol for non-interactive and sequential payments.

2.3

Direct Anonymous Attestation (DAA)

Direct Anonymous Attestation (DAA) remote authentication scheme for trusted hardware
modules has been proposed by Brickell et al. [BCC04]. DAA has been adopted by theTrusted Computing Group (TCG).
When a verifier communicates with a user in possession of a trusted hardware module,
DAA allows the verifier to verify that the output from the user is from the hardware module.
In addition, since DAA preserves anonymity, the verifier can only know that the output isfrom the trusted hardware module and can not identify the hardware.
DAA can be seen as group signatures [BMW03] but differs from group signatures inthat DAA does not have an opening algorithm that allows the group manager to obtain theidentity of the signer from the signature. Instead of having opening function, DAA has a
so-called ”revocation function”. Suppose a particular hardware module has been broken andits secret key has been compromised; the secret key is placed on the revocation list. Whena verifier receives the signature, he can verify whether it is signed with the secret key on the
revocation list. The verification can be done by the value K = B f , where f is the secretkey, K and B are the values in the signature, where B is the generator of an algebraic groupand computing the discrete algorithms are hard.

2.4. VERIFIABLE DELAY FUNCTIONS (VDF)

9There are multiple DAA schemes have been proposed [SRC15, GHS11, BCL09, CPS10,
Che10]. In this paper, we adopt Enhanced Privacy ID (EPID) scheme proposed by Brickell
and Li [BL10, BL12]. EPID is a scheme proposed by Intel Corporation and is already inuse in the real world, embedded in chipsets such as Intel SGX. EPID is compliant with
International Standards Organization standard ISO/IEC 20008, 20009 and approved by theTrusted Computing Group (TCG) as the recommended scheme. Intel has made EPID an
open-source to processor manufacturer under the Apache 2 license. In 2015, Microchip andAtmel announced that they had licensed the EPID technology [Cora, Corb].

2.4

Verifiable Delay Functions (VDF)

A Verifiable Delay Function (VDF) [BBBF18] is the function that requires sequential steps
to evaluate yet outputs a unique value that can be efficiently and publicly verifiable.
VDF could be used to build a randomness beacon [Rab83], an ideal function that regularly outputs unpredictable random values, using a permissionless blockchain like Bitcoin
and Ethereum.

10

CHAPTER 2. PRELIMINARIESChapter 3
Secure Offline Payments in Bitcoin

3.1

Introduction

Double-spending attacks on fast payments [KAC12] are one of the fatal architectural problems in Cryptocurrencies. Double spending refers to the payment where the same coin isspent twice in a way that the receiving party cannot notice the invalidity of the payment. We
study an offline immediate payment scheme based on blockchain secure against the doublespending attacks on fast payment assuming the security of tamper-proof wallets. Dmitrienko
et al. [DNY17] pointed out that Bitcoin requires clients to be online to perform transactions
and a certain amount of time to verify them, and also offline payments raise non-trivial
challenges, as the payee has no means to verify transactions. Even online, fast payments
are shown to be vulnerable to double-spending attacks [KAC12]. Offline immediate payments are long demanding in cryptocurrencies. In practice, without changing the ongoing
systems, ”fast payment” is widely used such that the payee could accept the transaction
immediately by checking the signature and the payer’s balance to confirm that the payer
has enough money to spend. However, Karame et al. [KAC12] pointed out that, for sucha fast payment scheme, the double-spending attack is possible if a malicious payer makes
use of the race condition of the double-spending transactions that reach the payees with
11

12

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN

different timing in the peer-to-peer network. Dmitrienko proposed a solution for immediateand offline payments that relies on tamper-proof wallets manufactured by a trustworthy
manufacturer and deploys a time-based transaction confirmation mechanism. They use afragment of the main blockchain to prove the legitimacy of pre-loaded coins to the wallets.
Their scheme solved the double-spending problem, as Karame et al. suggested. The wallet
loses its credibility if a malicious user succeeds to pre-load illegal coins by intention. Thus,
it is enormously important to establish secure coin pre-loading to the wallet. In order toachieve this, Dmitrienko proposes an interesting protocol that proves the fact that a preloading payment to the wallet existed using a subchain, a fragment of the main blockchain.
They considered that a subchain is a part of the mainchain if and only if the total PoW
to mine the blocks in the subchain is greater than some predetermined lower bound andthe average time to produce the subchain is less than some constant time period. Thus, toverify the proof inside the tamper-proof wallet, objectively measuring the total computation
time consumed to generate the subchain is necessary. (A) A trivial solution to this is to
assume a trusted time-stamp server, which supplies a time-stamp to a block every time thecorresponding block is created. (B) Another solution proposed in [DNY17] is to set the
expiration time of the pre-loading coins. This also convinces the wallet that the subchain
is produced within some bounded time period. Apparently, the construction (A) with thetrusted time-stamp server requires an additional trusted third party. The construction (B)is decentralized, but it sacrifices usability to a great extent.

3.1.1

Related work

Other studies of interest include Teechan, an offline payment channel proposed by Lind etal. [LNE+ 19]. It assumes tamper-proof wallets on both sides and achieves offline payments.
However, it has to deposit some funds, which corresponds to our pre-loading, into the 2-of-2
multisig address between the payee and the payer sufficiently before the offline payment
occurs. Thus, the setting differs from ours.

3.2. SECURITY PROPERTIES

13

In the theoretical aspect, Garay et al. [GKL15] formulated the basic properties of theblockchain in Bitcoin [Nak09] such as ”common prefix” and ”chain quality,” assuming thatthe hashing power of an adversary controlling a fraction of the parties is strictly less than
1/2. Further extensions are made for variable difficulty [GKL15], a security analysis in the“semi-synchronous” network model [PSS17].
We propose a novel offline payment scheme alternative to Dmitrienko’s protocol. The
advantage of our scheme is it is fully decentralized; that is, it does not assume any external
trusted time-stamp server. Further, we do not need to set any expiration time for the
pre-loaded coins.

3.2

Security Properties• C: a blockchain.
• Bi : i-th block in C is a triple ⟨H(Bi−1 ), xi , nonce⟩.
• τ : a transaction of a form Sign(skA ; A → B, value).
• xi : a root of Merkle Tree for a set of transactions {τ1 , τ2 , . . .} in Bi .
• U: a set of users.
• H: a set of honest users, H ⊆ U.
• X, Y ∈ U: (typically, X as a payer, Y as a payee).
To analyze the security of our scheme, we follow the notions introduced by Garay etal. [GKL15]. All players are bounded interactive turing machines and are all synchronizedt,nand messages are exchanged in a discrete-time frame called round. {EXECΠ,A,Z(z)}z∈{0,1}∗

denotes the random variable ensemble that determines the output of the environment Zt,non input z for a protocol Π with adversary A. VIEWΠ,A,Z(z) denotes the concatenatedt,nview of all parties after the completion of an execution EXECΠ,A,Z(z). A ”flat” model is

14

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN

assumed where all parties execute exactly q mining trials (hash queries) per round. Then,each mining trial by various players is modeled as a Bernoulli distribution with different
parameters, and the deviation from the expected probability is estimated. We denoted by κ
the length of hash function output, by η parameter determining block to round translation,and by f probability at least one honest party succeeds in finding a POW in a round. Garay
et al. [GKL15] showed that any consecutive rounds S of length |S| > ηκ in the blockchain
protocol is a ”typical execution” with probability 1 − e−Ω(κ) where honest and adversarial
mining trials succeed as expected within a bounded probability fluctuation of at most ϵ.

3.3

Secure Offline Payments in Bitcoin

Our immediate payment protocol construction basically follows the Dmitrienko’s protocol [DNY17] but without the existence of the time-stamp server. The main difference in the
protocol is that the correctness of the coin-preloading to the tamper-proof wallet is verified
by the payee in our construction, not the payer as in Dmitrienko’s protocol. Similarly to theirscheme [DNY17], our construction also assumes the tamper-resistant wallet to incorporate
overspending prevention. The tamper-proof wallet has a secret key skT which was createdby the wallet manufacturer T . The wallet also has a variable balance (≥ 0). It increases
in the coin preloading phase and decreases in the offline payment phase. Our construction
has 3 phases: (i) online coin preloading, (ii) offline payment, and (iii) coin redemption andwallet revocation. The details are as follows.

Online Coin Preloading
The flow diagram is shown in Figure 3.1. In the coin preloading phase, the payer X requests
a new account w from the wallet (Step 1), then create the escrow transaction τl transferring
bl bitcoins from her account x to w, then commit it to the networks (Step 2). As soon asτl is verified and integrated into the Bitcoin network in a block, say Bi , X takes Bi (Step3.3. SECURE OFFLINE PAYMENTS IN BITCOIN

153), and provides τl and the witness of the membership proof τel 1 to W (Step 4). W sets
its balance to bl and stores τl , τel , and replies status (Step 5)2 . For simplicity, we assume

one-time coin preloading for every account w such that once an amount bl is preloaded to w,
the wallet W never accepts preloading transaction to w anymore and only makes payments
while balance ≥ 0. It is not hard to extend it to multiple coin preloading.
Bitcoin Network
B

Payer X
bl , x, pkX , skX

Wallet W
balance, pkW , skW

1. w

2. τl

w ← Hash(pkW )τl ← Sign(skX ; x → w, bl )Confirm τl with Bi
3. Bi

4. τl , τel
5. statusbalance ← bl
Store {τl , τel }Figure 3.1: Online Pre-loading protocol

Offline Payment
The flow diagram is shown in Figure 3.2. In the offline payment phase, the payee Y sends
the public key pkY and the requested amount bo to the payer X, which are immediately
forwarded to W (Step 1). W checks the balance and if balance ≥ bo , it decreases balanceby bo and generates a transaction τo = Sign(skw ; w → y, bo ). Further, W generates a
proof = Sign(skT ; τo , τl , τel ) that shows τo was created within the tamper-proof wallet bysigning with skT . The resulting τo , proof and certT , a trustworthy vendor certificate, aresent to Y (Step 3). Y accepts the transaction if τl is confirmed and τo is valid and issued by1

τel is a set of hash values such that member(B, τ, τe) = 1.
The wallet does not check the validity of coin preloading transaction τl . Payments made from unconfirmed
τl will be rejected by payees.
2

16

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN

a tamper-proof wallet. More formally, Y accepts τo and proof if and only ifcertT is trustworthy







Verify(pk ; proof) = 1
T

(3.1)




τo ∈ (VCY ∩ Sign(skW ; w → ·, bo ))









τl ∈ C⌈kY ∩ Sign(·; · → w, bl )If all checks succeed, Y stores τo , proof and replies to W with status (Step4).
Wallet W
balance, skT , {τl , τel }, pkW , skW

Payee Yy, pkY , skY

Payer Xx, pkX , skX , certT
1. pkY , bo

if (balance ≥ bo )balance ← balance − boτo ← Sign(skW ; w → y, bo )proof ← Sign(skT ; τo , τl , τel )else reject

2. τo , proof, certT
accept τo and proof iff

certT is trustworthyVerify(pk ; proof) = 1
T
τ
∈
(V

o

 CY ∩ Sign(skW ; w → ·,bo ))τ ∈ C⌈k ∩ Sign(·; · → w, b )l

3. Sign(skY ; status)

YlFigure 3.2: Offline payment protocol

Coin Redemption and Wallet Revocation
The flow diagram is shown in Figure 3.3. When Y gets online, Y proceeds to the coinredemption and wallet revocation phase. Y broadcasts τo to the Bitcoin network in orderto redeem the coins received from W (Step 1). Next, the Bitcoin network verifies τo and3.4. SECURITY MODEL

17

integrates it into the blockchain. The payee Y observes the Bitcoin network and periodically
updates its local chain C′Y reflecting the newly mined blocks (Step 2). Y waits until τo is
confirmed or τo becomes invalid, τo ∈/ VC′Y . If τo is invalid, Y initiates revocation by creating
a revocation transaction τr = Sign(skY ; proof, cancel τo ) and send it to Insurer Z (Step 3).
Z investigates τr and, to compensate Y for the damage of bo issues τZ and then commits to
the Bitcoin network (Step 4).
Bitcoin Network
B

Payee Yτo , proof, pkY , skY

Insurer Z
pkZ , skZ

1. τointegrate τo into B

2. C′Yif τo ∈
/ VC′⌈kYτr ← Sign(skY ; proof, cancel τo )3. τr
Z issuesτZ = Sign(skZ ; z → y, bo )after investigation of τr .

4. τZ

Figure 3.3: Coin redemption and double-spending wallet revocation protocol

3.4

Security Model

Definition 1. τ is said to be valid with respect to a blockchain C if and only if τ satisfies3
all the pre-agreed requirements4 with respect to the blockchain C. Further, we denote by VC
3

Dmitrienko [DNY17] have introduced a slightly different term CheckSyntaxT for transaction validation.
CheckSyntaxT refers to the syntactical conformance of transactions to the requirements in the blockchain.
On the other hand, valid refers to all the requirements for integrating into the blockchain. Those are thesyntactical conformance of transactions, the correctness of the payer’s signature and further requirements
such as ”the payer’s account must exist”, and ”balance after the transaction must not be negative.”
4
In Bitcoin, the requirements (e.g., Bitcoin Improvement Proposals) are subject to change. New proposals
will be incorporated into the requirements after agreed upon among the majority of miners through the voting
process in the blockchain.

18

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN

a set of all possible valid transactions with respect to C such that
VC = {τ | τ is valid with respect to C}.

valid transactions are correctly formed and not over-spent more than the balance of thepayer’s account as far as regarding the given blockchain C as the mainchain. Once validtransactions are broadcasted to the Bitcoin network by peers, they may be integrated into
the mainchain if the given chain C is shared by honest miners, and thus the transaction isvalid for those honest miners. Note that this is not guaranteed. Because the given chain
C may contradict the localchains of other honest miners. Furthermore, the set of validtransactions will change as chains evolve.

Definition 2. A transaction τ is said to be confirmed5 if and only if for every honest player
X ∈ H the transaction τ can be found on his localchain CX , that is, τ ∈ CX for all X ∈ H.

Once a transaction τ is confirmed, the transaction must be in the mainchain C where C is
the longest prefix of all localchains held by honest players such that C ⪯ CX for all X ∈ H.
where ⪯ is a prefix relation [GKL15]. We consider confirmed transactions are valid. That is,
τ is confirmed =⇒ τ ∈ VCX for all X ∈ H.

Definition 3. Given a security parameter k, τo is said to be verified by a proof of a form

5

In practice, a transaction is confirmed after the block that contains the transaction has at least six
blocks built on top. This is the situation where our notion of confirmed is satisfied with high probability.

3.4. SECURITY MODEL

19

Sign(skT ; τo , τl ) with respect to a localchain C if and only ifcertT is issued by a trustworthy provider








Verify(pkT ; proof) = 1







τ is a transaction of a form Sign(sk ; w → ·, b )
o

W




τl is a transaction of a form Sign(·; · → w, bl )








τo ∈ VC







τl ∈ C⌈k

o

(3.2)

where certT is a certificate issued to a public key pkT which is generated within a tamperproof wallet W at the production time. (pkW , skW ) is a key pair generated by W, and w isan account related to pkW .

In the offline payment, a payee Y verifies the received transaction τo by a proof Sign(skT ; τo , τl )with his localchain CY . If all of the above conditions are satisfied, Y is convinced that thecoin-preloading transaction to the payer’s wallet τl is confirmed by all honest players withoverwhelming probability in k. As far as the tamper-proof wallet honestly produces thepayment transaction τo , Y can believe that τo is not an overspending transaction and will
be confirmed later on. To see whether τl satisfies the last condition τl ∈ C⌈k , in a naive
construction, the payee must keep the whole set of transactions previously registered in theblockchain C. For efficiency purposes, we assume that all transactions in a block B are
kept in the form of a Merkle Tree, and B only keeps the root hash value of the tree. Let
τel be a witness of the membership proof or a set of all sibling hash values in every branchin the path from the root to the leaf τl . Using the witness τel , the membership proof can be

20

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN

efficiently proved since there exists a function member(·) such thatmember(B, τ, τe) =1 if τ ∈ B
0 otherwise

We replace the proof with Sign(skT ; τo , τl , τel ) where offline payee needs efficiency.
Theorem 1. We assume there exists a tamper-proof wallet W . Given a security parameterk and an offline transaction τo accepted by a payee Y such that τo is verified by a proof =Sign(skw ; τo , τl ) with respect to the payee’s localchain CY , the probability that the transaction⌈kτo , later on, changes its state to invalid is negligible in k. That is, with CY ⪯ C′Y , we havehi⌈kPr τo ∈
/ VC′ | τo is verified by proof with respect to CY < negl(k).

(3.3)

Y

Proof. Given τo is verified by proof with respect to CY , Equation (3.2) holds. Under thetamper-proof assumption, the tamper-proof wallet W never overspend, exceeding the preloaded balance bl . Therefore, if the preloading transaction τl is confirmed, that is,τl ∈ CX for all X ∈ H,

(3.4)

then the offline transaction τo cannot become invalid with respect to C′Y . Since τl is already⌈kin a localchain of Y , that is, τl ∈ CY , for τl not to be confirmed, there must exist an honest
player Z with a localchain CZ such that τl ∈/ CZ . The common prefix property states that
all localchain C held by honest players must satisfyC⌈k ⪯ CZ

(3.5)⌈kwith negligible error probability in k. Substituting C → CY , τl ∈ CY contradicts withτl ∈/ CZ . Thus, τl must be confirmed with arbitrarily high probability 1 − negl(k) with the3.5. CONCLUSION

21

security parameter k. Hence the theorem.
In the case τo ∈/ VC′⌈k where the offline transaction τo is turned out to be invalid later onY⌈kwith respect to the payee’s evolved localchain CY′ (⪰ CY ), this must be the case where thetamper-proof wallet assumption is broken, and τo is found to be an overspent transaction.
Even in this case, the preloading transaction τl must still be confirmed with 1 − negl(k).
Therefore, the proof = Sign(skw ; τo , τl ) still satisfies the following 5 of all 6 conditions in(3.2) for all honest player X ∈ H with 1 − negl(k).
certT is issued by a trustworthy provider








Verify(pkT ; proof) = 1τo is a transaction of a form Sign(skW ; w → ·, bo )







τl is a transaction of a form Sign(·; · → w, bl )






τ ∈ C ⌈k

l
X

(3.6)

This fact convinces all honest players. Given τo is invalid with respect to C′Y , that is,τo ∈/ VC′⌈k , the redeeming transaction τr = Sign(skY ; proof, cancel τo ) becomes valid withY′⌈krespect to CX ⪰ CY for all X ∈ H with arbitrarily high probability 1 − negl(k). The
trustworthy provider of the tamper-proof wallet or an insurance company might compensate
Y for the damage of bo after τr is confirmed.

3.5

Conclusion

In this chapter, we have shown that, with light-weight tamper-proof wallets, completely
decentralized offline payment is possible without any modification to the existing Bitcoin
network. Our protocol requires the coin pre-loading transaction to be confirmed, and its
block is delivered to every possible payee before the first offline payment is made. Thisshould be the best possible for the Bitcoin network.

22

CHAPTER 3. SECURE OFFLINE PAYMENTS IN BITCOIN
Based on the work of Dmitrienko et al. [DNY17], we constructed a scheme on Bitcoin,that is, Proof of Work type blockchain, using the ”common-prefix property” to obtain transactions agreement among all nodes on the blockchain. Since the ”common prefix property”
has also been proposed for Proof of Stake type blockchains [KRDO17, DPS19], our scheme
can also be used in Proof of Stake type blockchains.

Chapter 4
Decentralized Probabilistic
Micropayments with Transferability

4.1

Introduction

Micropayments are minimal payments, e.g., less than $1, and can be used in a wide range
of applications, such as per-page billing in e-books and delivering content billed per minute.
However, it is challenging to realize micropayments in the blockchain.
The problems in realizing micropayments in the blockchain are the low throughput andthe high blockchain transaction fee. Since the capacity of each block is fixed, miners givepriority to transactions that can generate high fees and put off micropayment transactions
with low fees. In addition, the blockchain transaction fees do not depend on the amount ofmoney to be transferred. Thus, the blockchain transaction fees can be relatively small forhigh-value transfers but high for micropayments.
The above problems can be solved by Layer-two [GMSR+ 20]. Instead of registering alltransactions in the blockchain, Layer-two aggregates small transactions into a few larger ones,
increasing transaction throughput and reducing transaction fees. Decentralized probabilistic
micropayments [ABC20, TO21] have been proposed as one of the methods for Layer-two.
23

24

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

It is a lottery-based scheme, the amount of required payments is locked in an escrow, andmicropayments are issued as lottery tickets. Let the winning amount be β, and the winningprobability is p, the expected value per lottery ticket is p·β, and the ticket is used as currency.
Probabilistic micropayments allow us to aggregate the entire transactions by approximately
p. For example, if 10, 000 transactions are to be processed by a probabilistic micropayments
scheme, only 10, 000 · p transactions will be registered in the blockchain.
Almashaqbeh et al. have proposed MicroCash [ABC20] which is a lightweight protocol for
non-interactive and sequential payments. The disadvantage of MicroCash is that the gametheory guarantees safety against double-spending attacks. Thus, the penalty escrow, whichis confiscated after the double-spending attack is discovered, is expensive. As an example,
when m = 5 and Bescrow = 2000, the penalty escrow is Bpenalty = 477.6. In addition, tickets
can only be sent once by the ticket issuer; in other words, the tickets can not be transferable.
As MicroCash, when safety is constructed using only a game-theoretic approach, considering penalty escrow, the number of honest users who can receive the ticket, u, is realisticallyconstrained to about 5. If we make u large, we need to make the penalty escrow large inproportion to u. As an alternative plan, if we assume that the users can not commit malicious activity, such as a tamper-proof assumption, u can be large without penalty escrow.
However, the smaller p is, the higher the gambling potential becomes and the less the payee
can use it for actual economic transactions. If many tickets with a minimal winning probability are sent and do not win, the honest users can not make any income. This is because if
the ticket can not be transferable, the payee will not earn any income unless the ticket theyreceived wins. The smaller p, the more the opportunity to get an income is lost.
If the ticket is transferable, p can be reduced. The payees do not lose anything since theticket can be used to pay others even if the ticket is not won. However, it is challenging toachieve transferability with existing solutions. Since the ticket is transferable, the doublespending attacks can be performed by the issuer and all users. Requiring game-theoreticallyguaranteed penalty escrow for all users is practically undesirable because of high collateral4.2. CONTRIBUTION

25

costs. Suppose the ticket transfer is limited to a tamper-proof device, malicious activities
that deviate from the protocol can be prevented, and transferability can be achieved withouthigh penalty escrow.

4.2

Contribution

We propose a novel decentralized probabilistic micropayments, Transferable Scheme, whichallows tickets to be transferable among users.
The contribution of the chapter is twofold:• Novel probabilistic micropayment techniques:
As far as we know, all of the ever-proposed probabilistic schemes are based on lottery
tickets where only a small fraction of payees will win the lottery and receive multi-foldawards. In contrast, our probabilistic micropayment [TO21] utilizes transferability,
where every payer has to pay a transaction fee proportional to the paid amount,say 10%, and the fees are accumulated inside the transferred ticket. Then, only thewinner of the lottery ticket will take all of the accumulated transaction fees as thelottery award. In addition, non-winners will always gain expected revenue with far
less speculativity. The value of the ticket will diminish exponentially as transferred
until the expected velocity. Most of the payments fall into the range of micropayments.
• Imperfect tamper-proof assumption with game-theoretic upper-bound for the adversary’s utility:
We assume tamper-proof wallets which prevent double-spending before it happens.
Our double-spending detection techniques are shown to detect perfectly when the
double-spent ticket is about to be registered in the blockchain (fork detection) anddetect probabilistically when received at the payee (collision detection). With thesedetection techniques, we can eliminate the need for penalty escrow (required in the

26

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS
previous works [ABC20]) and force adversaries to weigh the cost of breaking a tamperproof wallet against the maximum expected value that the adversary can obtain fromthe attack.

4.3

Background

4.3.1

Payment Channels and Networks

The payment channel establishes a private, peer-to-peer transmission protocol. Based on predefined rules, two parties can agree to update their state and transfer money by exchanging
authenticated state transitions in a so-called ’off-chain’ fashion.
In order to conduct a transaction on Payment Channel, two parties must first register ashared 2-of-2 multi-sig escrow fund in the blockchain and establish the channel. The payment
channel enables the two parties to perform transactions through private communications.
After the sending and receiving are completed in the channel, the final fixed value is registered in the blockchain. Only two transactions are registered in the blockchain per channel,
escrow fund transaction and final fixed value. A payer can send money to a user who has
not established a channel with the payer through the Payment Network between users who
have established a channel. For example, suppose Alice sends 0.1 coins to Charlie, who has
not established a channel with Alice. First, Alice sends 0.1 coins to Bob, with whom Alicehas a channel. Next, Bob sends 0.1 coins to Charlie, whom Bob has a channel.
Unfortunately, the payment channel and the network have the disadvantage of highcollateral cost [MBB+ 19]. Each time a channel is established, escrow is required between
two parties. Also, the longer the payment network path, the more reserves are required
and locked. Since the reserves can not be used during the locktime periods, the reserves
represent a lost opportunity. Furthermore, in a payment network, a fee is charged for eachpass through the nodes. It is impractical to adopt a payment network for micropayments
since it is undesirable to incur the cost for each node.

4.4. TICKET TRANSFER PROTOCOL

27

Blockchain

ϵ

···

ow
scr

e
an
e
t
ea
Cr nt ϵ1u○coac
2 Lottery○ticket τ1···○
3
lot Claiter my t winickn
et ingτ2

Ticket Issuer

···

τv

WinnerFigure 4.1: Overall Design

4.4

Ticket Transfer Protocol

This section presents the design of our transferable scheme. We start with an outline of thelottery ticket transaction, followed by a detailed description of each part.

4.4.1

OutlineThe outline of the system is shown in Figure 4.1.
Step 1, The issuer issues a smart contract escrow account ϵ and registers and confirmsthat ϵ has been registered in the blockchain. Step 2, The issuer issues the ticket τ forprobabilistic micropayments and sends it to a user. The payee verifies that the ticket camefrom a legitimate wallet and that the escrow account is properly registered in the blockchain.
If there is no problem, the user receives the ticket and returns the service or product to thepayer. Then, the payee signs the ticket with his wallet and sends it to another user. Step
3, If the ticket received meets the requirements for winning, the ticket is sent to the escrowaccount ϵ.
The sequence of procedures in this scheme, such as ticket issuance and payment with theticket, is done using a tamper-proof wallet.

28

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

Tamper-proof wallet
The premise is that all users participating in the transferable scheme have tamper-proof
hardware wallets.
The wallet consists of a tamper-proof device manufactured by a trusted manufacturer.
It does not accept any unauthorized operation that deviates from the protocol, such as
double-spent tickets.
There are two keys in the wallet. One is a key for personal use key pairs (skWX , pkWX )for sending and receiving the ticket; we denote the hash value of pkWX be the ”address”
associated with the wallet owner. The other is a secret key skT used to prove that the ticket
was created and sent from a legitimate wallet. Additionally, the wallet owner possesses acertificate certT corresponding to the secret key skT .

4.4.2

Escrow Setup

The flow diagram is shown in Figure 3.1.
The issuer X requests a new account wX from the wallet (Step 1), then create the escrowtransaction τl transferring β coins from the account x to the wallet address wX and commit
it to the networks (Step 2). As soon as τl is verified and integrated into the Blockchain
network in a block, say Bi , X takes Bi (Step 3), and provides τl and Bi to WX (Step 4). W
create the escrow account ϵ. Then, sends it to X with status (Step 5). Finally, X sends τ0and ϵ to the Blockchain network. 1

4.4.3

Payment with Lottery Ticket

The flow diagram is shown in Figure 4.2.

In the payment with lottery ticket phase, thepayee Y sends pkWY (Step 1). The wallet WX creates a ticket τ1 and signs it with the secretkey skWX , and signs the ticket τ1 with the wallet manufacturer’s secret key skT . The wallet
1

The wallet does not check the validity of the escrow transaction τ0 and ϵ. Payees will reject the ticket
which is not transferred from ϵ.

4.4. TICKET TRANSFER PROTOCOL
Payer X’s Wallet WX
skT , pkWX , skWX

29
Payee Y’s Wallet WY
skT ′ , pkWY , skWY

1. pkWYwY ← Hash(pkWY )τ1 ← Sign(skW ; wX → wY , ϵ)proof 1 ← Sign(skT ; τ1 )2. τ1 , proof 1 , certT

3. Sign(skY ; status)

accept and store τ1 and proof 1 iffcertT is trustworthy
Verify(pkT ; proof 1 ) = 1
τ1 is valid

Figure 4.2: Payment with Lottery Tickets
WX sends ticket τ1 , proof 1 , and certT to the payee’ wallet WY (Step 2). If all checks succeed,
Y stores τ1 , proof 1 , and replies to WX with the status (Step 3). If the payee Y wants tosend the received ticket to another user, the same procedure is followed from Step 1.

4.4.4

Ticket Winning and Revocation

The flow diagram is shown in 4.3. If τ ∈ win, Y sends τ and proof to the contract account ϵ(Step 1). If τ is both valid and eligible, the escrow account ϵ signs the escrow transaction τ0
with wY as the destination. The payee Y observes the blockchain network and periodically
updates its local chain and confirms τ0 is valid (Step 2).
If τ is one of the double-spent tickets created by a double-spending attack, the contract
account ϵ shows that τ is double-spend one (Step 3). 2 Y initiates revocation by creating a2

Double-spending attacks can be perfectly detected and the adversary’s address is discovered. See Section 4.7.

30

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

Blockchain Network
B

Payee Y’s Wallet WY
τ, proof, pkY , skY
if τ ∈ win
1. τ, proof

Insurer Z
pkZ , skZ

if τ is eligible and valid
τ0 ← Sign(skWX ; wX → wY , β)else reject
2. τowait until τo ∈ VC′⌈k
Y

3. τ is double-spent ticketτr ← Sign(skY ; proof, cancel τ )4. τrLater T issues
τZ = Sign(skZ ; z → y, (1 − q)j β)
after investigation of τr .
Deactivate the adversary’s wallet.
5. τZ

Figure 4.3: Ticket redemption and double-spending wallet revocation protocol

4.5. TICKET WINNING CONDITION

31

revocation transaction τr = Sign(skY ; proof, cancel τ ) and send it to Insurer Z (Step 4). Z
investigate τr and in order to compensate Y for the damage, issues τZ then committed to
the Bitcoin network (Step 5). 3

4.5

Ticket Winning Condition• C: a blockchain.
• U: a set of users.
• X, Y ∈ U: (typically, X as a payer, Y as a payee).
• l: the number of double-spent (duplicated) tickets by an adversary• ϵ: escrow account which has several fields: (β, h0 , τ0 , p, µ)– β: the lottery winning amount– h0 : the block height containing the escrow account– τ0 : escrow creation transaction– p: the probability for determining of winning a ticket– µ: the fixed number to calculate the winning ticket (∈ N)• τ : a lottery ticket which has several fields : (A, B, τpre , σ)
– A: a sender– B: a receiver– τpre : a reference to a previous ticket or to an escrow account ϵ– σ: signature by a sender• Φ: the cost of breaking a tamper-proof hardware wallet
3

The compensated amount is the same as the return when received the ticket. See Section 4.6 for thevalue of a ticket when it is in transfer.

32

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS• γ: the blockchain transaction fee

4.5.1

Structure of the ticket

This section describes the structure of the lottery ticket and the design of the ticket winning
method. If the ticket is transferable, a blockchain transaction fee is charged when the ticket
is won and registered in the blockchain. We introduce a scheme where users who send andreceive the ticket share the blockchain transaction fee little by little.
Definition 4. A lottery tickets τ consists of a sixfold:(A, B, τpre , σW , σT , certT )(4.1)

where A and B are accounts of a sender and a receiver, respectively. τpre is a reference toa previous ticket or to an escrow account ϵ. A pair of signatures, σW and σT , is a multisignature, where σW is signed with a signing key tied with a sender’s account and σT issigned with a tamper-proof device’s signing key to proving that the signing device is trusted
verifiable with a certificate certT issued by a trusted manufacturer. We denote by σA to denotea signature signed by A. The escrow account ϵ further contains (β, h0 , τ0 , p, µ) to specify theparameters of the transferable transaction, where β is the ticket winning amount, and h0 is
the block height to specify particular VDF values. τ0 is the escrow creation transaction. p is
the probability for determining of winning a ticket. µ is a fixed value used to determine thewinning ticket.
For readability, we write a ticket τ as:

τ = (A → B, τpre )X .

(4.2)

We define |τ | the ”number of generations” of τ , which is the length of the sequence fromϵ to τ . For example, |τ | = n if there exists a sequence τ1 , . . . , τn−1 such that ϵ ≺ τ1 ≺ τ2 ≺

4.5. TICKET WINNING CONDITION

33· · · ≺ τn−1 ≺ τ . We define |τ | = ∞ if no such sequence exists 4 . To write compactly, we
denote by τi the i-th generation of τ .
′Definition 5 (Transferred transaction). Two tickets τi = (A → B, τpre )X and τi+1 = A′ → B ′ , τpreX′

are said to be transferred if and only if following properties satisfies:′
Hash(τi ) = τpre





 A = X, B = A′ = X ′certTX′ is trustworthy





 multi-signature σ ′ and σ ′ are valid
WX
TX

(4.3)

Then, we write τi ≺ τi+1 .

We write τi Î τi+n if there exists a sequence of ordered lottery tickets τ1′ ≺ . . . ≺ τn′ forn ≥ 1 and they satisfy τi ≺ τ1′ and τn′ ≺ τi+n . In the case where τ has no previous lottery
tickets, the ticket is called a ’genesis’ ticket. For the genesis tickets τ1 tied to an escrowaccount ϵ, we specially denote by ϵ ≺ τ1 so that a lottery tickets are simply written as:ϵ ≺ τ1 ≺ τ2 ≺ . . . ≺ τn .

(4.4)

Definition 6. A lottery tickets τ is said to be valid with respect to a blockchain C forsome security parameter k if and only if there exists an escrow account ϵ and a sequence oftransactions τ1 , . . . , τn such thatϵ ∈ C⌈kandϵ ≺ τ1 ≺ . . . ≺ τn ≺ τ.

(4.5)

C⌈k denotes the set of blocks that are k or more blocks before the beginning of theblockchain. This notion is borrowed from Garay et al [GKL15].
4

For practical purposes, we assume that the height of τ can only be measured when all tickets in thesequence from ϵ to τ are given. Even if such a sequence exists, the height of τ is considered to be ∞ unlessthe entire sequence is specifically presented.

34

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

4.5.2

Ticket Winning Condition

This section describes the design of the ticket winnings.

Definition 7. τi,v is said to be win if and only if the following properties satisfies:

win =



τv

VDF (h0 + v · µ) < D, v ∈ N



(4.6)

where v is the number of generations of τ and µ is the fixed number specified in the escrowaccount ϵ.

h0 is registered in ϵ, which specifies the block height at which ϵ would be registered. The
probability p is calculated using a simple Verifiable Delay Function (VDF) [BBBF18]. The
calculation can be done after a certain period of time has elapsed from when the ticket istransferred according to the number of generations. For example, if a ticket with h0 = 100,
µ = 5, and v = 3 is received, the VDF value will be known when the block height of 115 isconfirmed.
As described in the next Section 4.6, even though the ticket meets the requirements win,
the ticket may be used as payment instead of getting the winning amount β. If a ticketτ ∈ win has already been transferred, the user with the most recent ownership can get thewinning amount β.

Definition 8. τv is said to be eligible if and only if the following properties satisfies:eligible = τv∃

τv′ ∈ win ∧ τv′ Î τv



(4.7)

eligible ticket will be considered as the final winning ticket. Thus, the user who has theeligible ticket can get β from the escrow account ϵ.

4.6. PROPORTIONAL FEE SCHEME

4.6

35

Proportional Fee Scheme

In this section, we consider the blockchain transaction fee to transfer the winning amountto the winner’s address and the value of the ticket in the transfer process.
In our transferable scheme, it is not beneficial for the issuer to bear the blockchaintransaction fee. Since when the issuer bears the blockchain transaction fee, the amountavailable for payment is β − γ, which does not provide any advantage for the issuer to use
the transferable scheme.
We propose a novel Proportional Fee Scheme. The process is depicted in Figure 4.4.
This scheme is where each time a payer transfers a ticket; the payer bears the fee based on
the number of generations of the ticket. When a payer sends τj to the payee, in return, thepayee gives goods or services worth (1 − q)j β.
τ1

τ2

τ3

(1 − q)β(1 − q)2 β(1 − q)3 β

Ticket issuer

u1

τi+1

τi
···

(1 − q)i β

u2(1 − q)i+1 β
ui

ui+1

Figure 4.4: Proportional Fee Scheme

Definition 9 (Proportional fee scheme). Let q be the lottery ticket transaction fee rate.
Suppose a payer sends a ticket τi , and in return, the payee gives goods or services worth(1 − q)i β to the sender. The fees borne by the payment is (1 − q)i−1 qβ.
Specifically, the fee for each payment is τi−1 − τi = (1 − q)i−1 qβ, and the profit (income −expenditure) when τi = eligible is β −(τi + γ) = (1 − (1 − q)i ) β −γ where γ is the blockchaintransaction fee.
Suppose the ticket satisfies the win condition before the accumulated fees exceed theblockchain transaction fee γ. In this case, the user may decide whether to send it to theblockchain network and get β or transfer the ticket to another user as payment. Specifically,
the user can profit from the eligible ticket by getting the winning amount β under thefollowing condition:

36

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS
1 − (1 − q)i β > γ.

(4.8)

If the ticket satisfies the win condition is transferred to another user, the ticket is distributed as eligible and can be sent to the blockchain in any subsequent generation. Naturally, the ticket will be sent to the blockchain network in the generation that satisfies theequation 4.8.
This scheme has the advantage that the payment fee can be smaller than the blockchaintransaction fee. The average transaction fee for cryptocurrencies, especially Bitcoin, isapproximate $2 [YCH].
1
1
and q = 10
, the ticket value per
In our transferable scheme, let β = $100, p = 100

generation is depicted in Figure 4.5. As we can see from Figure 4.5b, the value of the ticket
falls below $1 from approximately i = 50. Figure 4.6 shows the frequency of the fee, and we
can see that there are more than 50 transactions whose value is less than $1. Since the fee
1, the fee for a $1 transfer is about 10 cents.
per payment is roughly q = 10

Both the existing Lottery scheme and our Transferable scheme can aggregate blockchaintransactions by the winning probability p. The difference is that our transferable scheme
does not increase the gambling potential, even making the winning probability p smaller. In
the existing scheme, the smaller p is, the lower the probability that the payee will win theticket, which makes the income more unstable for the payees. In our transferable scheme,
even if the ticket is not winning, the payee can use it for payment by paying a smaller fee
than the blockchain transaction fee.
There is a concern that the sizeable winning amount β decreases the velocity of theticket. This is because if there is a large gap between the winning amount β and the valueof the ticket, the profit of winning β − γ will be more significant. Therefore, it is best forrecipients to decide whether to use the ticket for payment after confirming their winnings,
which causes the velocity of the ticket to be slow. The solution is not to make the winning
amount β too high. In addition, if we set the winning amount β to a value almost equal to

37

100

1.0

80

0.8

60

0.6

(1-q)j-1 β(1-q)j-1 β4.6. PROPORTIONAL FEE SCHEME

40

0.4

0.2

20

0

0.0
0

20

40

60

80

100

0

20

40

i

60

80

100

i

(a) < 100(b) < 1

1
1
and q = 10
. Figure 4.5aFigure 4.5: Ticket value per generation when β = $100, p = 100
shows the value of a ticket, depending on the number of generations i of the ticket. As
shown in Figure 4.5b, at roughly 50 generations or more, the value of the ticket is less than
$1, making it micropayment.

50

Frequency

40
30
20
10
0

0

10

20

30

40

(1-q)i-1 β
1Figure 4.6: Frequency of the ticket values, same as Figure 4.5, when β = $100, p = 100
and1
q = 10 . Roughly more than 50 generations are worth less than $1.

38

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

the blockchain transaction fee γ, the profit of winning will be very small; thus, the velocityof the ticket will not be affected.

4.7

Security Properties

As far as the tamper-resistant assumption holds, double-spending attacks can not be performed theoretically. However, in reality, the tamper-proof hardware wallet could be broken,
leading to double-spending attacks. Thus, instead of requiring a penalty escrow, we design
security from the perspective of whether the utility an adversary can gain from the attack
exceeds the cost of breaking the tamper-resistant hardware.
Definition 10 (κ-tamper proof). A device is called κ-tamper proof if it satisfies the following
conditions:
1. tamper-proof hardware is the hardware that prevents an adversary from stealing andchanging stored data.
2. the device is either completely broken/tampered or working perfectly with probability κ
and (1 − κ), respectively 5 .
3. broken/tampered is a state in which all confidential information inside the device,including the secret key, has been leaked to the adversary.
We assume each device is in a state either completely broken/tampered or working
perfectly. They occur with probabilities κ and (1 − κ), respectively. As long as the behavior
is observed from outside, it is not possible to distinguish between a device that is operatingcorrectly and a device that adversary control the correct device who have an access to its
internal key.
5

In reality, the adversaries are biased, but we assume it can not be distinguishable from a legitimate userfrom outside.

4.7. SECURITY PROPERTIES

39

Ticket issuer
···

A

···

l

···
..
.

..
.
···

Figure 4.7: Double-spending Attack
Double-spending Attack
Double-spending attacks are an attack that makes a profit by duplicating and doublespending the received ticket. In our transferable scheme, we assume that the adversary
breaks the κ-tamper proof and receives or issues tickets, then transfers with different addresses (wallets). We call the tickets created by the double-spending attacks ”duplicated.”
In our transferable scheme, we assume an adversary can gain profit up to l · β where l isthe number of duplicated tickets. This is illustrated in Figure 4.7.

4.7.1

Detection Methods

This section describes how to detect the double-spending attacks and find the adversary’s
address. We introduce two methods to detect the attack and find the adversary’s address
perfectly. When the adversary’s address is found, we assume that the address is broadcasted
to all users, and then the adversary’s address is rejected by all users. An adversary can notprofit unless the maximum expected utility he can gain from a single attack exceeds the costof breaking the κ-tamper proof wallet.
Note that the following two detection methods require that the receiver be online at thetime of receipt. Conversely, the payer does not need to be online.

40

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

Definition 11 (Fork of transferred transactions). Given two series of transactions initiatedwith the same escrow account τ = {ϵ ≺ τ1 ≺ · · · ≺ τn }, and τ̃ = {ϵ̃ ≺ τ̃1 ≺ · · · ≺ τ̃n′ }, theseries of transactions are said to be Fork if and only if it satisfies: ∃ k ∈ Z≥0 ,ϵ = ϵ̃τ ⌈k Î τ̃ ∧ τ̃ ⌈k Î τ τ ⌈k−1 ̸Î τ̃ ∨ τ̃ ⌈k−1 ̸Î τ.

(4.9)

Assume the users monitor the blockchain, and after the eligible ticket is registered in theblockchain, the users check the eligible ticket against the ticket they have received.
Theorem 2 (Fork Detection). Given two series of transactions (τ, τ̃ ) ∈ Fork, there exists
an efficient fork detection algorithm that outputs the double-spending transactions.
Proof. Assume there exists two series of transactions τ and τ̃ such that (τ, τ̃ ) ∈ Fork, and τ iseligible and registered in the blockchain, the user who has τ̃ reports a double-spending attack.
Put the two transactions τ , τ̃ as τ = {ϵ ≺ τ1 ≺ · · · ≺ τn }, and τ̃ = {ϵ̃ ≺ τ̃1 ≺ · · · ≺ τ̃n′ }.
From the Definition 11, there exists k ≥ 0 that satisfies the condition (4.9). We assumen ≥ n′ without loss of generality. Then, τ ∗ = {ϵ ≺ τ1 ≺ · · · ≺ τn−k } is the longest common
prefix, and τn−k+1 and τ̃n−k+1 are the double spending transactions.
Definition 12 (Collision of transferred transactions). Assume that each of the u users has
α (≥ 2) addresses. If an adversary sends at least two duplicated tickets to any one of u users,
the ’collision’ occurs.
We adopt a round scheme so that the adversary can not profit when the collision isdetected. We divide the ticket-sending procedure into three rounds. The procedure isillustrated in Figure 4.8. Round 1) The adversary sends the tickets to the honest payees.
The payee checks the received tickets for the collisions. Round 2) If the payee finds thecollision, broadcasts τ and τ̃ to the honest users. Round 3) If the collision is not detected,

4.7. SECURITY PROPERTIES

41

Adversary

Round 1.

Honest users···
1. τ, τ̃

Check for the collisions
if the collision detected,

Round 2.

Round 3.

broadcasts τ and τ̃ to honest users

3. Give something in return or Reject

Figure 4.8: Collision detection roundthe payee gives products or services to the payer in return. If the collision is detected, theadversary’s address is rejected and will never be accepted by all honest users.

Theorem 3 (Collision Detection). Let u be the number of users who participate in transfer
scheme. By collision detection and round scheme, the expected utility of double-spending
attack Ed is upper-bounded by the following inequality:
Ed ≤

r

u
β.
e

(4.10)

Proof. As stated in the Definition 12, we assume a uniform distribution where each user
has α addresses6 . This must be the case where the adversary chooses uniformly l different
addresses from the total of αu addresses. By the round scheme, the adversary can not profit
if a single user address is chosen more than once.
Let p(l; u) be the probability that at least one user address is chosen more than once.
This probability is described as follows:l2

p(l; u) ≈ 1 − e− 2u .
6

(4.11)In reality, the number of addresses each user has is considered more likely to follow an exponential
distribution. It is an unfavourable assumption that all user have the same number of addresses α.

42

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

Assume that the adversary double-spent l tickets with a maximum value of β per ticket.
The adversary’s expected utility value isEd < max lβ · (1 − p(l; u)) .
l

Thus, Ed is at mostpue

β when l =(4.12)√u.

In our transferable scheme, the double-spending attack is perfectly detected, and theaddress used in the attack will be rejected by all users. Therefore, it is not profitable forthe adversary unless the cost of breaking a single tamper-proof wallet exceeds the maximum
expected value gained by the attack. Specifically, the adversary can not profit under thefollowing conditions:

r

u
β<Φ
e

(4.13)

where Φ is the cost of breaking κ-tamper proof wallet.
As an example, consider the maximum expected utility value Ed with u = 1, 000, 000
and β = $100. Applying the equation 4.10 produces Ed ⪅ $60, 700.

4.8

Conclusion

In this chapter, we introduce the first transferable decentralized probabilistic micropayment
scheme and the proportional fee scheme. The feature of our scheme is that the ticket istransferable. Therefore, the ticket winning probability can be much smaller than the existing
methods. Thus we can aggregate a larger number of transactions into one and can increase
the blockchain throughput. Also, the proportional fee scheme can make the transaction fee
smaller via the lottery ticket than on the blockchain.
Our scheme only assumes a tamper-proof device, and the ticket transfer protocol issimple, requiring only a digital signature. The tamper-proof assumptions can be achieved
by SE (Secure Elements) such as SIM cards, which are widely used in Smartphones. Since4.8. CONCLUSION

43

the computational resources of SE are limited, the concern arises that it is not impracticalto perform all operations in the SE. In our scheme, the operations to be performed in the
SE can be limited to the prevention of double-spending. On the other hand, operations thatare not related to double-spending prevention can be executed in the regular application
area. Therefore, since the use of SE’s computational resources can be minimized, it would
be feasible to realize our scheme on mobile devices such as smartphones. Specifically, theoperations to be performed in the SE are checking whether a ticket is valid, creating a
key pair, and signing at the time of money transfer. On the regular application side, theoperations are performed to avoid duplicated tickets (e.g., collision and fork detection) andcheck for winning tickets.
We consider that our transferable scheme is not a singular way of transferable lottery
tickets but a system similar to the circulation of paper and coins issued by central banks.
We will use blockchain to achieve this. We believe that our scheme can be applied not only
to micropayments but also to high-value payment transactions.

4.8.1

Open problem

We proposed a scheme to increase the blockchain’s throughput by a factor of v (100× as an
example). Our scheme increases the throughput by v, but the size of the ticket also increases
by v linearly. The size of the EPID signature is 171 bytes [BL12, BL10], and if the receiving
address is a hash value with the digest length of 512 bits, the aggregation ticket size isroughly 29.9 KB when v = 100. Although v = 100 is negligibly small as a verification costfor the blockchain, it is desirable to avoid increasing the size in proportion to v in practice.
In order to prevent the ticket size from increasing in proportion to the number of times
the ticket is sent, schemes such as aggregate signatures or one-way accumulators may be
used.

44

CHAPTER 4. TRANSFERABLE PROBABILISTIC MICROPAYMENTS

Chapter 5
VeloCash: Anonymous Decentralized
Probabilistic Micropayments withTransferability

5.1

Introduction

In the previous Chapter 4, we have proposed a transferable decentralized probabilistic micropayments scheme. In this chapter, we propose Decentralized Probabilistic Micropaymentswith Transferability which preserves Anonymity, named VeloCash.
Similar to Chapter 4, we realize the lottery scheme and the proportional fee scheme underanonymous conditions. We also realize ”anonymity with transparency” by fully detecting
double-spending attacks and revoking the adversary.

5.2

Contribution

The contribution of the chapter is threefold:
45

46

CHAPTER 5. VELOCASH• Extended anonymity notions for blockhchain-based decentralized transferable payment
schemes:
All of the previous anonymity notions [CG08, BFQ21] assume the existence of the bankas the central authority. Thus, applying those anonymity notions to the blockchainbased decentralized payment schemes is not straightforward. In this chapter, we introduced the generalized anonymity notions of transferred electronic cash schemes tocover both centralized and decentralized payment schemes.
• Revokable anonymity extension for attested execution secure processors:
Attested Execution Secure Processors (AESP) [PST17] is the abstraction of tamperproof secure processors, which enforces every installed program to attach an attested
signature as a proof to show that the output is the result of the execution of the
program. In this chapter, we propose a new mechanism to revoke tampered AESP’s
utilizing the idea of key extractor when double-spending is detected. In order not
to be too abstracted, our key extractor is defined over Enhanced Privacy Identifier(EPID) [BL10], but our technique can be applied to any Direct Anonymous Attestation(DAA) scheme [BCC04] with Fiat-Shamir proof of knowledge for NP relation.
• Secure construction of probabilistic anonymous payments with transferability:
We proposed VeloCash, an anonymous probabilistic micropayment scheme with transferability. The construction satisfies all the security and anonymity notions claimed in
the theorems.

5.3

Preliminary

As in Chapter 4, the transferable payment scheme is realized using tamper-proof devices.
In this study, which realizes the anonymity of the transferable payment scheme, we also assume tamper-proof devices. More specifically, we use Attested Execution Secure Processors

5.3. PRELIMINARY47(AESP), that abstracts ”attested execution” secure processors. In the ”attested execution”
of AESP, the output of the installed program is digitally signed with the secret key in the
AESP. The signature enables verification that the output is indeed from a legitimate AESP.

Direct Anonymous Attestation (DAA) has been used for the attested signature. DAA
can be seen as group signatures [BMW03] but differs from group signatures in that DAA
does not have an opening algorithm that allows the group manager to obtain the identityof the signer from the signature. Instead of having opening function, DAA has a so-called”revocation function”. Suppose a particular hardware module has been broken and its secret
key has been compromised; the secret key is placed on the revocation list. When a verifier
receives the signature, he can verify whether it is signed with the secret key on the revocationlist.

In this study, we use AESP to send and receive tickets, and DAA is used for attested
signatures and for sending tickets. There are three reasons to adopt DAA: 1) For anonymization of attested signature. 2) To extract the adversary’s secret if the double-spending attacks
are performed 3) To revoke the extracted adversary’s secret key. In particular, extracting
and revoking the adversary’s secret key is a strong motivation for adopting DAA. We adopt
Enhanced Privacy ID (EPID), a DAA scheme that uses Fiat-Shamir proof of knowledge for
NP relation. Thus, since the Extractor can be configured, it is possible to extract and revoke
the adversary’s secret key from the double-spending tickets with the same commitment but
different challenges.

A possible alternative to anonymization other than DAA is using ring signatures. Traceable ring signatures [FS07, Fuj11] limit the number of times a secret key can sign transactions, making it possible to detect double-spending attacks. However, ring signatures growproportionally to the size of the anonymity set. There is an inevitable trade-off between
anonymity and signature size while DAA signature size is constant.

48

CHAPTER 5. VELOCASH

5.3.1

Direct Anonymous Attestation (DAA)

Direct Anonymous Attestation (DAA) remote authentication scheme for trusted hardware
module has been proposed by Brickell et al. [BCC04]. DAA has been adopted by the Trusted
Computing Group (TCG).
There are multiple DAA schemes have been proposed [SRC15, GHS11, BCL09, CPS10,
Che10]. In this paper, we adopt Enhanced Privacy ID (EPID) scheme proposed by Brickell
and Li [BL10, BL12]. EPID is a scheme proposed by Intel Corporation and is already inuse in the real world, embedded in chipsets such as Intel SGX. EPID is compliant with
International Standards Organization standard ISO/IEC 20008, 20009 and approved by theTrusted Computing Group (TCG) as the recommended scheme. Intel has made EPID an
open-source to processor manufacturers under the Apache 2 license. In 2015, Microchip andAtmel announced that they had licensed the EPID technology [Cora, Corb].

5.3.2

Specification of EPIDEPID is one of the DAA schemes which preserves anonymity proposed by Brickell andLi [BL10, BL12]. There are two types of revocation in EPID, the secret key based revocation,and the signature based revocation. In the secret key based revocation, put the secret key
into the secret (private) key based revocation list Priv-RL. In the signature based revocation,
put the signature into the revocation list Sig-RL. The verification process will invalidate thesignatures with the keys in the corresponding revocation lists in both revocation schemes.
There are four entities in EPID: an issuer I, a revocation manager R, platforms1 Pi , andverifiers V. The scheme consists of five polynomial-time algorithms:
ΠEPID = (Setup, Join, Sign, Com, Verify, Revoke) .
1

(5.1)

In the original definition by Brickwell and Li [BL10, BL12], platforms are the secure hardware-based
signing entities such as SGX in Intel processors. Pass et al.[PST17] refers to the signing entities to produce
attested signatures as ideal functionality Gatt , and they used the term ’platform’ for the entities who isallowed to invoke functionalities in Gatt .

5.3. PRELIMINARY

49

Setup :
(gpk, isk) ← Setup(1λ )(5.2)

Issuer I takes the security parameter 1λ as input and outputs a group public key gpk
and an issuing private key isk.
Join :⟨⊥, ski ⟩ ← JoinI,Pi ⟨(gpk, isk), gpk⟩

(5.3)

Issuer I is given gpk and isk. Pi is given gpk and outputs a secret key ski .
Sign :σ/⊥ ← Sign(gpk, sk, m, Sig-RL)(5.4)

The above is a probabilistic signature algorithm which on input gpk, sk, a message mand a signature based revocation list Sig-RL outputs a signature σ, or ⊥ if sk has been
revoked in Sig-RL.
Here, we define the deterministic version of the same signature algorithm:σ/⊥ ← Sign(gpk, sk, m, Sig-RL; r)(5.5)

where r is a randomness. Thus, it always outputs the same signature σ if all inputs
are the same.
For simplicity, we sometimes omit public parameters from expressions such that Signsk (m)for probabilistic signature algorithms and Signsk (m; r) for deterministic signature algorithms, respectively.
Com :(x, com) ← Com(gpk, sk; r)(5.6)

The probabilistic commitment generation algorithm on input gpk, sk and r outputs

50

CHAPTER 5. VELOCASH
x and com. This is not defined in Brickwell and Li [BL10, BL12]. We introduce
this function for technical reasons described later in Definition 20. Assuming thesignature scheme uses Fiat-Shamir proof of knowledge for NP relation (x, ω) ∈ Rλ ,there exists a key extractor, as we will see in Definition 20. When used together withthe deterministic signature algorithm Signsk (m; r) with the same randomness r, we canutilize these functions to identify double-spenders. Sometimes we also omit publicparameters and write as comsk (r) for simplicity2 .

Verify :{0, 1} ← Verify(gpk, m, Priv-RL, Sig-RL, σ)
On input gpk, a secret key based revocation list Priv-RL, a signature based revocation
list Sig-RL, a message m and a signature σ, the function outputs either 1 if the signature
is valid and 0 for invalid. Verify outputs 0 (invalid) when either case that σ is not avalid signature on m or that σ has been revoked.

Further, EPID[BL10, BL12] defined the two revocation algorithms: secret key based
revocation and signature based revocation, where original DAA[BCC04] only defines theformer. Our scheme does not utilize the signature based revocation, and hence our construction does not depend on the EPID signature based revocation. The two revocation
algorithms are defined as follows:

Revoke - secret key based revocation

Priv-RL ← Revoke(gpk, Priv-RL, sk)
Given gpk, Priv-RL, and sk, R updates Priv-RL by adding sk into Priv-RL.
2

com satisfies the hiding and biding properties defined in Damgård [Dam99](5.7)

5.3. PRELIMINARY

51

Revoke - Signature based revocation
Sig-RL(5.8)← Revoke(gpk, Priv-RL, Sig-RL, m, σ)Given gpk, Priv-RL, Sig-RL, m, and σ, R updates Sig-RL by adding σ into Sig-RL after
verifying σ.

Security Definition of EPID
An EPID scheme is secure if it satisfies the following three requirements: correctness,anonymity, unforgeability [BCC04, BL10].
The correctness requires that every signature a platform generates is valid except when
the platform is revoked by the secret key based revocation or the signature based revocation.
Theorem 4. (Theorem 4 of [BL09]) The EPID scheme is correct.
The EPID scheme is anonymous if the adversary can not determine from the signature
the secret key used to generate the signature.
Theorem 5. (Theorem 5 of [BL09]) An EPID scheme is anonymous in the random oracle
model under the decisional Diffie-Hellman assumption in G3 .
The EPID scheme is unforgeable if the adversary can not forge a valid signature with all
secret keys known to the adversary that has been revoked.
Theorem 6. (Theorem 6 of [BL09]) The EPID scheme is unforgeable in the random oracle
model under the strong Diffie-Hellman assumption in (G1 , G2 ).
See Appendix A for the construction of EPID and Appendix B for more detailed definitions.

52

CHAPTER 5. VELOCASH

5.4

Anonymous Ticket Transfer Protocol

The results in the preceding section show that the cost of breaking a κ-tamper proof walletmust exceed the expected utility of an adversary. In this section, we follow the formal
abstraction of attested execution secure processors [PST17] with adequate tamper-resistance(whose breaking cost exceeds Φ).
All previously proposed anonymous and transferable electronic cash schemes[OO92, CP93,
CG08, BCFK15, BFQ21] assume that:
1. the existence of central authority (bank), and
2. only the bank can detect double-spending.
Our decentralized blockchain-based transferable payment scheme is described in the previous
section; however, every player is eligible to set up an escrow account and initiate offlinetransferable payments; hence no central authority (bank) exists. Further, our collisiondetection and fork-detection techniques enable every recipient of transferable payments todetect double-spending and publish the evidence on the blockchain. That is, every player can
detect double-spending potentially. Finally, to capture the anonymity in these decentralized
settings, we will define generalized anonymity notions in the following subsections.

Algorithms (CG08)
A conventional transferable e-cash system generally involves two types of players: a bank
B and a user U. Whereas a blockchain-based transferable e-cash system has no banks, a
blockchain C takes the role of a bank B. C can be regarded as B that holds no secret
information and publishes all of its views and the deposited coin list L.
A coin is represented by an identifier id and some values π needed to prove its validity.
• ParamGen(1λ ) is a probabilistic algorithm that outputs the parameters of the systemparam (including the security parameter λ ). We assume all functions take param as
their inputs unless otherwise specified.

5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

53

Note: param may contain the genesis block of the blockchain C. For schemes assuming DAA-based anonymous signature schemes with tamper-proof devices, ParamGen
generates the DAA public key and secret key pair (gpk, gsk) and param contains gpk
for the verification of anonymous signatures.
• BKeyGen(param) (resp. UKeyGen(param)) is a probabilistic algorithm executed byB(resp. U) that outputs the key pair (skB , pkB ) (resp. (skU , pkU )).
Remark. Blockchain-based transferable e-cash systems have the blockchain C in placeof the bank B, and C has no secret information. Thus, BKeyGen(param) outputs nothing such that (skB , pkB ) = (⊥, ⊥).
Remark. For schemes assuming DAA-based anonymous signature schemes with tamperproof device, UKeyGen(param) invokes Join(gpk) protocol with the manufacture whoholds gsk, and stores ski securely in the tamper-proof device within a platform Pi .
Such systems share the group public key gpk and no individual public key pki for theplatform Pi exist. Hence, (skU , pkU ) = (ski , ⊥).
• Withdraw (B (skB , pkB , pkU ) , U (skU , pkU , pkB )) is an interactive protocol where U withdraws from B one coin. At the end, U either gets a coin C = (id, π) and outputs OK,or outputs ⊥. The output of B is either its view VBW of the protocol (including pkU ),or ⊥.
Remark. VBW including pkU is published on the blockchain C in blockchain-based systems. The same amount of the coin C is funded in an address ϵ on the blockchain C,
where ϵ is related to the public key pkU and spendable using the secret key skU .
• Spend Uj (id, π, pkUi ), Ui (skUi , pkB ) is an interactive protocol where Uj gives a coin to

Ui . At the end, either Ui outputs a coin C = (idC , πC ) or ⊥, and either Ui saves that
C is a spent coin and outputs OK, or Ui outputs ⊥.

54

CHAPTER 5. VELOCASH• Deposit (U (id, π, skU , pkU , pkB ) , B (skB , pkB , pkU , L)) is an interactive protocol where U
deposits a coin (id, π) at the bank B. If (id, π) is not consistent/fresh, then B outputs⊥1 . Else, if id already belongs to the list of spent coins L, then there is an entry (id, π ′ )and B outputs (⊥2 , id, π, π ′ ). Else, B adds (id, π) to its list L, credits U ’s account,and returns L. U ′ ’s output is OK or ⊥.
Remark. Blockchain-based transferable e-cash systems have the blockchain C in placeof the bank B. In these systems, Deposit is conducted as a transfer of money fromthe address ϵ to the address of U if the coin (id, π) is consistent and the money in theaddress ϵ has never spent.
Remark. In the blockchain-based transferable e-cash systems, L is a part of the blockchain
C. If id already belongs to the blockchain C, or its list of spent coin L, then there isan entry (id, π ′ ) and every user U ′ who received (id, π) can output (⊥2 , id, π, π ′ ). Else,(id, π) is published on the blockchain C and added to its list of spent coins L. U’s
output is OK or ⊥.
• Identify (id, π, π ′ ) is a deterministic algorithm executed by B that outputs a public key
pkU and a proof ΠG .
Remark. In the blockchain-based transferable e-cash systems, Identify (id, π, π ′ ) is adeterministic algorithm executed by every user U that outputs a double-spender’s secret key ski since DAA-based anonymous signature schemes have no individual publickeys pki . The systems with such anonymous schemes can not output pkU of the double
spender. Therefore, in such systems, Identify (id, π, π ′ ) outputs (⊥, ΠG ). We consider
that ΠG includes the double-spenders secret keys ski and the following VerifyGuilt((id, π), ΠG )determines whether the coin (id, π) is spent by a guilty user of not.
• VerifyGuilt (pkU or (id, π), ΠG ) is a deterministic algorithm that can be executed by any
players. It outputs 1 if ΠG is correct and 0 otherwise.

5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

55

Remark. In the blockchain-based transferable e-cash systems, we assume ΠG is published on the blockchain.

5.4.1

Oracles

Our security games use oracles. We adopt the oracle notions from [BFQ21, CG08].
Global Variables We store all information about users in the user list UL consisting of
Ui = (pki , ski , udsi ) where udsi indicates how many times user Ui has performed the doublespending attacks. The set of supplied coins by the oracles is denoted by SC, and the set of
all coins owned by the oracles is denoted by OC. The set of deposited coins is denoted byDC.
If an error occurs during the execution of the oracles, the oracles output ⊥. Otherwise,
the call of the oracles is assumed to have succeeded.
Registration and Corruption Users The adversary can instruct the creation of honest
users or passively observe registration. It can moreover spy on users, meaning that theadversary can learn the user’s secret key. Note that the spy can not be performed on thechallenge users.
• BRegist() plays the bank side of key generation algorithm BKeyGen and interacts withthe adversary. If successful, it adds (pk, ⊥, uds = 0) to UL.
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank and BKeyGen outputs nothing, oracle BRegist() outputs nothing.
• URegist() plays the user side of the key generation algorithm UKeyGen when theadversary controls the bank. Upon successful execution, it adds (pk, sk, 0) to UL.
Remark. In the blockchain-based transferable e-cash systems, URegist() plays when
the issuer I of DAA-based anonymous signature schemes are controlled by the adversary. Upon successful execution, it adds (⊥, sk, 0) to UL.

56

CHAPTER 5. VELOCASH• Regist() plays both parties in the BKeyGen and UKeyGen algorithm and adds (pk, sk, 0)
to UL.
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank and BKeyGen outputs nothing, the oracle Regist() outputs nothing.
• Spy(i), for i ≤ |UL|, returns the user i’s secret key ski .

Withdrawal Oracles The adversary can withdraw a coin from the bank or passively
observe a withdrawal.
• BWith(i) plays the bank side of Withdraw(B, Ui ) algorithm. This oracle updates SC byadding VBW with bit 1 to flag it as corrupted coin.
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank, oracle BWith(i) outputs nothing.
• UWith(i) plays the user side Withdraw(B, Ui ) when the bank is controlled by the adversary. This oracle updates OC by adding the value (Ui , id, π).
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank, UWith(i) plays with Withdraw(⊥, Ui ) when the adversary controls theissuer. Then, it updates OC by adding the value (Ui , id, π).
• With(i) simulates Withdraw protocol execution of both B and user Ui , and it updates
OC as for Withdraw(B, Ui ) and SC by adding VBW with flag 0.
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank, oracle With(i) outputs nothing.

Spend and deposit oracles.

5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

57• Spd(j) plays the role of user Uj by spending a coin in OC owned by user Uj . It uses
and updates the entry (Uj , id, π) of OC as the Spend protocol.
• Rcv(i) makes honest user i receive a coin from the adversary and updates the set of
OC by adding a new entry (Ui , id, π).
• S&R(j, i) plays the role of both Uj and Ui and it executes the spending of a coin owned
by Uj to user Ui . It updates OC by adding the value (Ui , id, π) and by flagging the coinas spent by Uj .
• BDepo() lets A deposit a coin. It runs Ui in Deposit using the bank’s secret key skB .
If successful, it adds the received coin to DC or runs Identify and returns (pk, ΠG ) ←Identify(id, π, π ′ ).
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank, oracle BDepo() outputs nothing.
• Depo(j), the honest deposit oracle, runs Deposit between the j-th coin owner in OC
and an honest bank. If successful, it adds the received coin to DC or runs Identify andreturns (pk, ΠG ) ← Identify(id, π, π ′ ).
Remark. Since blockchain-based transferable e-cash systems have the blockchain C inplace of the bank, Depo(i) plays the role of the user Ui during a Deposit algorithm.

5.4.2

Security Notions

In this section, we discuss the security properties. To achieve anonymity in Takahashi andOtsuka [TO21], we need to satisfy two major properties.
The first one is Security properties (Economic properties and Security properties). For
achieving anonymity, we borrow the definition of Transferable E-Cash from Bauer et al.
[BFQ21].

58

CHAPTER 5. VELOCASH
The second one is Double-spending attacks Detection methods and Proportional Fee

Scheme. In addition to satisfying anonymity, we outline Double-spending attacks Detection methods, which are the core security design of [TO21], and organize the conditions thatmust be satisfied.
Economic properties ensure that users do not incur economic losses when they participate
in the system. It consists of soundness, unforgeability, and exculpability.

Soundness
Suppose an honest user issues or accepts a ticket during a transfer; he should be guaranteedthat others will accept the ticket. In that case, either honest users when transferring or theblockchain escrow account when claiming.
The game is formalized in Figure 5.1. The adversary issues a ticket or sends the received
ticket τ to the user i0 . If the result of sending ticket the ticket to the user i1 or claiming to
the blockchain is false, the adversary wins.
Experiment: ExptsoundA,Π (λ)param ← ParamGen(1λ ); pkB ← A(param)
2 : (b, i1 , i2 ) ← AURegist,Spy
3 : if b = 0 then run UWith(i1 ) with A
1:

4:

5:
6:
7:
8:
9:

else run Rcv(i1 ) with A

return 0 if this outputs ⊥run S&R(i1 , i2 );if one party outputs ⊥return 1

else return 0

Figure 5.1: Game for soundness

Definition 13. (Soundness) An anonymous transferable scheme is sound if for all PPT
adversaries A, we haveAdvsoundA,Π (λ) =Pr ExptsoundA,Π (λ) = 1 < negl(λ).

(5.9)

5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

59

Unforgeability
Unforgeability ensures that no user can spend more tickets than the number of tickets
they received/issued. Unforgeability also guarantees that the adversary address is accused
whenever a ticket is double-spending. The game is formalized in Figure 5.2.
Experiment: ExptUnforg
A,Π (λ)param ← ParamGen(1λ )2 : (skB , pkB ) ← BKeyGen(param)
1:(id, π, skA , pkA ) ← ABRegist,BWith,BDepo (param, pkB )4 : return 1 if there exists (id, π ′ ) ∈ DC with π ̸= π ′3:and all of the following conditions hold:1) ⊥ ← Identify(id, π, π ′ )∧ 2) (pk, ΠG ) ← Identify(id, π, π ′ )∧ 0 ← VerifyGuilt(pk, ΠG )5:

6:∧ 3) pk ← Identify(id, π, π ′ ) ∧ pk ∈/ ULreturn 1 if id ∈/ SCDeposit U (id, π, skA , pkA , pkB ) , B (skB , pkB , pkA , L) = OKelse return 0

Figure 5.2: Game for unforgeability

Definition 14. (Unforgeability) An anonymous transferable scheme is unforgeable if for all
PPT adversaries A, we have
AdvUnforgA,Π (λ) =hi
Pr ExptUnforg(λ)=
1< negl(λ).
A,Π(5.10)Exculpability
Exculpability ensures that an honest user can not wrongly be accused of double-spending.
Exculpability also guarantees that the adversary’s address is accused whenever a ticket isdouble-spending. Specifically, it guarantees that the adversary can not produce doublespending coins that can output the secret key of a user who has not committed doublespending attacks. The game is formalized in Figure 5.3.

60

CHAPTER 5. VELOCASH
Experiment: ExptexculA,Π (λ)param ← ParamGen(1λ ); skB ← A(param)∗
URegist,Spy,UWith,Rcv,S&R,Depo (param)
2 : (id , π ∗ , Π∗G) ← A3 : return 1 if all of the following conditions hold:
1) VerifyGuilt(id∗ , π ∗ , Π∗G ) = 1
1:

Let i∗ be the owner of (id∗ , π ∗ )∧ 2) there was no call Spy(i∗ )4:∧ 3) udsi∗ = 0

else return 0

Figure 5.3: Game for exculpability
Definition 15. An anonymous transferable scheme is exculpable if for all PPT adversaries
A, we have

5.4.3

AdvexculA,Π (λ) =Pr ExptexculA,Π (λ) = 1 < negl(λ).

(5.11)

Anonymity Notions

Anonymity notion for transferable electronic cash systems is first defined in Okamoto andOhta [OO92]. Canard and Gouget [CG08] defined the four levels of anonymity for transferable electronic cash systems:• Weak anonymity satisfies the property that any PPT adversary can not link the withdrawal and the deposit views. Still, the adversary may link two independent payments
by the same user.
• Strong anonymity satisfies the weak anonymity, and the adversary can not link two
payments by the same user. Still, the adversary may recognize the coin that he has
previously observed.
• Full anonymity satisfies strong anonymity, and the adversary can not recognize any
coin that is transferred between honest users. Still, the adversary may recognize thecoin he has previously owned.

5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

61• Perfect anonymity satisfies full anonymity, and the adversary can not decide whethera coin is the one that he has previously owned or not.
According to the above anonymity notion, the scheme provided by Okamoto and Ohta [OO92]
satisfies weak anonymity. Whereas, transferable electronic cash schemes proposed by Chaum
et al. [CP93] and Canard et al. [CGT08] satisfy strong anonymity. Perfect anonymity isproved to be impossible [CG08]. Intuitively, this proof is conducted as follows: supposethat a PPT adversary received coins c0 and c1 after spending a coin c such that one of thecoins is related to c. Given one of the coins cb for b ∈ {0, 1}, the adversary can always
distinguish whether cb is related to c or not just by depositing c0 together with c. b = 0
if the adversary is accused of double-spending, b = 1 otherwise. Thus, the best achievable
anonymity notions are full anonymity and restricted variants of perfect anonymity. Morerecently, Bauer et al. [BFQ21] introduced new notions of user anonymity, coin anonymity
and coin-transparency. As detailed later, all of these three notions are restricted variants ofperfect anonymity by Canard and Gauget [CG08].

Coin Anonymity (c-an)
Definition 16. (Coin anonymity) For all PPT adversaries A, there exists ∃ λ0 ∈ N such thatfor all security parameter λ ≥ λ0 , the protocol of VeloCash, ΠVC satisfies Coin anonymity
if the following holds:
Advc-anA,Π (λ) =




c-an
Pr Exptc-an< negl(λ).
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1(5.12)

User Anonymity (u-an)
We describe User anonymity game in Figure 5.5. The adversary issues or receives a ticket
and sends it to one of two user groups. Then, the adversary receives the ticket again, which

62

CHAPTER 5. VELOCASH
Experiment: Exptc-an
A,Π,b (λ)
1:
2:
3:
4:
5:

6:
7:

param ← ParamGen(1λ )pkB ← A(param)
(0)

(0)

(1)

(1)

i0 ← AURegist,Spy ; run UWith(i0 ) with A
i0 ← AURegist,Spy ; run UWith(i0 ) with A


(0)
(0)
(1)
(1)
(i1 , · · · , ik0 ), (i1 , · · · , ik1 )← AURegist,Spy
if k0 ̸= k1 then return 0

for j = 1, · · · , k0 :
(0)

(0)

(1)

(1)

8:

run S&R(ij−1 , ij )9:run S&R(ij−1 , ij )10 :run Spd(ij ) with A

11 :run Spd(ij12 :b∗ ← A; return b∗

(b)

(1−b)

) with A

Figure 5.4: Game for coin anonymity
has been passed through between the users, and determines which of two user groups it has
passed through.
Definition 17. (User anonymity) We define User anonymity if the following properties
satisfy: For all PPT adversaries A, there exists ∃ λ0 ∈ N such that for all security parameterλ ≥ λ0 ,Advu-anA,Π (λ) =




u-an
Pr Exptu-an
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1 < negl(λ).

(5.13)

Coin Transparency (c-tr)
c-tr
The experiment is specified in Figure 5.6. We assume ExptA,Π,b(λ) aborts when challengecoins (c0 , c1 ) are double-spent. For more details, see the original definition in [BFQ21]. Thisis a strong anonymity notion, meaning that the user who has transferred a coin will not beable to recognize it if she receives it again. The adversary issues or receives two tickets andsends them to the two user groups, respectively. Then, the adversary receives one of the5.4. ANONYMOUS TICKET TRANSFER PROTOCOL

63

u-an
Experiment: ExptA,Π,b
(λ)
1:
2:
3:
4:
5:

6:
7:

param ← ParamGen(1λ )pkB ← A(param)
(0)

(1)

(i0 , i0 ) ← AURegist,Spy(b)

run Rcv(i0 ) with A


(0)
(0)
(1)
(1)
(i1 , · · · , ik0 ), (i1 , · · · , ik1 )← AURegist,Spy
if k0 ̸= k1 then return 0

for j = 1, · · · , k0 :
(b)

(b)

8:

run S&R(ij−1 , ij )9:run Spd(ij ) with A

10 :

(b)

b∗ ← ABDepo ; return b∗

Figure 5.5: Game for user anonymity
tickets and determines which group the ticket has passed through.
Definition 18. (Coin transparency) We define Coin transparency if the following properties
satisfy: For all PPT adversaries A,
Advc-trA,Π (λ) =




c-tr
Pr Exptc-tr< negl(λ).
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1(5.14)

Definition 19. (Anonymity) For x ∈ {c-an, u-an, c-tr}, an anonymous transferable scheme
satisfies x if it satisfies the following equations: For all PPT adversaries A,
AdvxA,Π (λ) =Pr ExptxA,Π,1 (λ) = 1 − Pr ExptxA,Π,0 (λ) = 1 < negl(λ).

(5.15)

Note that in this chapter, we assume that the winning amount β is equal for all escrowaccounts ϵ, because if the winning amount β is very high, the winning ticket may not satisfy
the anonymity notions. Consider the case where a ticket returns to the same sender again,
and the ticket is won. The user can identify the ticket from the amount spent and the64

CHAPTER 5. VELOCASH
c-tr
Experiment: ExptA,Π,b(λ)

param ← ParamGen(1λ )2 : ((skW , skD , skCK ), pkB ) ← BKeyGen(param)
1:

3:
4:
5:

i(0) ← AURegist,BDepo,Spy (param, pkB , skW , skD )i(1) ← AURegist,BDepo,Spy (param, pkB , skW , skD )Run Rcv(i(0) ) with A

Run Rcv(i(1) ) with A


(0)
(0)
(1)
(1)
7:
(i1 , · · · , ik0 ), (i1 , · · · , ik1 )6:← AURegist,Spy
8 : if k0 ̸= k1 then return 0
9:for j = 1, · · · , k0 :
(b)

(b)

10 :

run S&R(ij−1 , ij )11 :run Spd(ij ) with A

12 :

(b)

b∗ ← A; return b∗

Figure 5.6: Game for Coin transparency
number of times the ticket has been transferred.
This is a trivial assumption and is a setting to simplify the conditions for achieving
anonymity. In Proportional Fee Scheme, there is a concern that the high winning amountcauses the speed of payment to be slowed down since the difference between the value of theticket and the winning amount is large. For example, if the winning amount is $10, 000 andthe ticket value is 1 cent, it is not surprising that people would wait for the winning result
before using it to pay. For Proportional Fee Scheme to work practically, it is ideal if thewinning amount is not very high, i.e., β − γ is negligibly small, where γ is the blockchaintransaction fee.

5.5

Attested Execution Secure Processors (AESP)

Tamper-proof is a property of a secure processor that prevents the leakage of sensitive information such as cryptographic keys and other confidential information against non-invasive
attacks such as side-channel attacks and invasive attacks such as reverse engineering. There5.5. ATTESTED EXECUTION SECURE PROCESSORS (AESP)

65

is no known theoretical implementation method. In many practical cases, the hardware isreferred to as ”tamper-proof” that has passed exhaustive penetration tests such as FIPS 140
and AVA VAN.5 in CC certification (ISO/IEC 15408).
Several methods have been proposed in academic and commercial literature to achieve
tamper-proof secure processors, As a de facto standard, it is often referred to as Trusted
Execution Environment (TEE). TEE allows any program to be executed in secure processors.
Furthermore, TEE also has the ”attested execution” function of verifying that the program’s
output in the device is from a legitimate tamper-proof device by signing the output withthe signing key unique to the tamper-proof device.

66

CHAPTER 5. VELOCASH

On initialize:// Interact with issuer I
1: ⟨⊥, sk⟩ := Σ.JoinI,Gatt ⟨(gpk, isk), gpk⟩, T = ∅2: initialize RT
On receive: getpk() from some P
1: send gpk to P
* * * * * Enclave operations:
On receive: install(idx, prog) from some P ∈ reg :1: if P is honest, assert idx = sid
2: eid ← {0, 1}λ
3: T [eid, P] := (idx, prog, 0)
4: send eid to P
On receive: resume(eid, inp) from some P ∈ reg :1: let (idx, prog, mem) := T [eid, P]
2:
abort if (eid, P) ∈/T
3: (outp, mem) := prog(inp, mem)
4: T [eid, P] := (idx, prog, mem)
5: σ := Σ.Signsk (idx, eid, prog, outp)
6: send (outp, σ) to P
* * * * * Internal operations:
On call: commitment(rid) from some (eid, ·) ∈ T :1: r ← RT[rid]2: (x, com) ← Σ.Comsk (r)3: return (x, com)
On call: sign(m; rid) from some (eid, ·) ∈ T :1: (idx, prog, mem) ← T [eid]2: r ← RT[rid]3: σ := Σ.Signsk (idx, eid, prog, m; r)
4: return (idx, eid, prog, m, σ)Figure 5.7: The algorithms of Gatt [Σ, reg, gpk, AE]5.5. ATTESTED EXECUTION SECURE PROCESSORS (AESP)

On input: initialize() :1: unspentCoin := ∅2: txChain := ∅3: Key := ∅4: A := ∅τb := AE.EncK (sid, eid, progw , (ϵ ≺ τ1 ≺ · · · ≺τn+1 ), σX )dX ∈d X ∈ unspentCoin
17: if addr
/ txChain ∧ addr
dX = ϵ18: // this must be the case addrd
19: ridϵ ← unspentCoin[addrX ]20: (x, com) := Gatt .commitment(ridϵ )21: ϵ := Hash(x, com)
22: τ1 := (ϵ → addrY , Hash(ϵ)) 23:sid, eid, progw , (ϵ ≺ τ1 ), σX:= Gatt .sign((ϵ ≺ τ1 ); ridϵ )d X]
24: delete unspentCoin[addr25:τb := AE.EncK (sid, eid, progw , (τ ≺ τ1 ), σX )26: abort if ϵ ∈/ unspentCoin
27: return τb
16:

On input: set escrow() :1: ridϵ ← Z
2: (x, com) := Gatt .commitment(ridϵ )3: ϵ := Hash(x, com)
4: store unspendCoin[ϵ] := ridϵ
5: return ϵ
On input: init keyex(sid, g) :1: a ← Zp
2: A[sid] := a3: store A
4: return g a67d :On input: receive payment(sid, eid, progw , τb, σb, addr)
1: restore K := Key[sid]2: (sid, eid, progw , τ, σ) := AE.DecK (bτ)//assume
τ
=
{ϵ
≺
·
·
·
τ
}
for
some
n≥1
n
On input: get addr(sid, g a , σ) :3: accept if the outer and inner attested signatures are
1: accept σ if
valid
2:
Verify(gpk, Priv-RL, Sig-RL, g a , σb) = 1// assume up to date Priv-RL, Sig-RL and C are3:// assume up to date Priv-RL, Sig-RL is stored instored in progw
progw
4:
Verify(gpk, Priv-RL, Sig-RL,b
4: b ∈ Zp , K := (g a )5:(sid, eid, progw , τb), σb) = 1
5: store Key[sid] := K
6:// for the attested signature on the encrypted
6: rid ← Zticket7: (x, com) := Gatt .commitment(rid)
7: Verify(gpk, Priv-RL, Sig-RL,
8: addr := Hash(x, com)8:
(sid, eid, progw , τ, σ) = 1
d := AE.EncK (addr)
9: addr9:// for the attested signature on the plaintext
d := rid
10: store unspentCoin[addr]
ticketd (g a , g b )10:
ϵ ∈ C⌈k for some constant k, and not spent
11: return addr,d =τ
11: store txChain[addr]d12:
returnstatus(∈{0, 1})
On input: make payment(addrX , (sid, eid, progw ,abd Y , (g , g ), σY )) :addrd :// Payment from addrX to addrY
On input: check winning(pkZ , addr)
1: accept if
d ∈ txChain
1: if addr
2:
Verify(gpk, Priv-RL, Sig-RL,d2:
rid := unspentCoin[addr]
d Y , (g a , g b )), σY ) = 1(idx, eid, progw , addr
3: (x, com) := Gatt .commitment(rid)
3: restore a4:
addr := Hash(x, com)
4: store K := (g a )bd
5: restore τn := txChain[addr]
dY)
5: addrY := AE.DecK (addr
6: if τn ∈ win
d X ∈ txChain
6: if addr
7: // let τn has the form :d X]
7:ridX := unspentCoin[addr8: // τn = (A → B, Hash(τpre ), σ)8: (x, com) := Gatt .commitment(ridX )9:
τn+1 := (B → pkZ , Hash(τpre ))9:
addrX := Hash(x, com)
10: return τn+1\
11: if ϵ is already spent on C, then Fork is detected
10: restore τ := txChain[addr
X]
d
\
11:
s.t. τ = ϵ ≺ τ1 ≺ · · · ≺ τn
12: if txChain contains addr
Z where τn = (addrZ →12:where τn = (addrZ → addrX , Hash(τn−1 ), σZ ) isdaddrr , Hash(τpre ), σZ ) then Collision is detected
a valid transaction to X from some Z
13: In both cases, there exists τ ′13: τn+1 := (addrX → addrY , Hash(τn ))14: sk := KeyExtractor(τ, τ ′ )14:sid, eid, progw , τn+1 , σX := Gatt .sign(τn+1 ; ridX ) 15:
return sk
d X]
15: delete unspentCoin[addr16: otherwise return ⊥Figure 5.8: The algorithms of progw

68

CHAPTER 5. VELOCASH
Pass et al. have proposed formal abstractions for attested execution secure processors as

Attested Execution Secure Processors (AESP) [PST17].
The structure of AESP is shown in Figure 5.7, 5.8. Pass et al. have proposed an ideal
function Gatt that abstractly captures the essence of the wide range of attested execution
processors. The most naive abstraction of Gatt has a public key and a secret key pair
(gpk, msk) for signing embedded by a manufacturer. By sharing the same secret keys among
all Gatt , no one can distinguish the issuer of the attested signatures.
The signature on message m with the signing key is denoted as Σ.Signsk (idx, eid, prog, m; r).
Gatt has four interfaces as follows:
1. Initialization:
Generates the key pair (mpk, msk) to be used for attested execution and initializes theinternal memory T .
2. Obtaining the public key:
Outputs the public key mpk to be used for signature verification of attested execution.
3. Registration of program:
Register a program prog in Gatt and allocate unique memory space mem for the program. Enclave instance is a pair of (idx , prog, mem) for idx , which is the session ID
when prog is registered. eid is the identifier of the enclave instance and is recorded in
T for each platform P.
4. Execution of program:
Input inp to the prog specified by eid and P, and output outp. Then, sign outp with
msk and output the signature σ for the attestation.
When Gatt is executed, the output outp is always signed with the embedded signing key
msk. Based on the output and the signature, a verifier can verify that the output is sentfrom a secure processor Gatt .
From the above, if Gatt exists, we can achieve the followings:

5.5. ATTESTED EXECUTION SECURE PROCESSORS (AESP)

69

1. Any arbitrary programs can be installed in Gatt .
2. The installed programs are obfuscated; thus, the adversary can not obtain any information more than input and output.
3. Secure channel can be achieved with the installed programs by Diffie–Hellman key
exchange protocol, etc.
4. Outputs from the installed programs are signed by Gatt ; thus, a verifier can verify thatthe output is sent from Gatt .
The signatures on outputs from the internal program by Gatt should be anonymous. Sinceeven though the programs exchange encrypted data through a secure channel, anonymity
is lost if the signer’s identity is known. Anonymous cryptographic technology that can notdetermine from which device the signature came is called ”Anonymous Attestation”.
Realizing anonymous attestation is achieved by using a digital signature scheme called
Direct Anonymous Attestation (DAA), which is similar to group signatures. DAA differsfrom group signatures in that it has strong anonymity, in that even the group manager can
not identify which key was used to create the signature.

5.5.1

Extension of AESPWe propose the following extension to the original AESP to revoke malicious platforms. We
assume that AESP utilizes any direct anonymous attestation (DAA) schemes with FiatShamir proof of knowledge for NP relation. The idea is the following: When a platform
P receives a transaction, we force P to commit to a set of one-time randomness (x, com)as the destination address of the transaction. Then, at the time when P transfers thetransaction to other platforms, P must issue an anonymous attested signature committing
to the randomness (x, com). As a result, the double-spending platform must issue twodifferent signatures using the same randomness (x, com) so that the witness will reveal andregistered in the revocation list.

70

CHAPTER 5. VELOCASHIn the following extension, we introduce Randomness Tape RT inside Gatt and give in-stalled programs to specify randomness index ridi .

Randomness Tape
A randomness tape RT is a list of random numbers with each entry having large enoughentropy.
RT = {rid0 , rid1 , · · · , ridn }(5.16)

When progw calls AESP’s commitment, Gatt returns (x, com). Next, when progw calls signwith the same rid on commitment, Gatt returns the signature σ from the random tape value
corresponding to the eid.

Internal signature
Normally, Gatt ’s EPID signature is applied to the output outp of progw when resume(eid, inp)
is called. When the ticket is sent, the ticket is encrypted with the shared key of Diffie–Hellman
key exchange, and the winning ticket is registered in the blockchain, including the EPID
signature on each transmission. If the signature is performed on the ciphertext, anonymity
can not be satisfied because the winner will post the ciphertext and the signature on theblockchain.
We extend Gatt to provide internal operations that allow progw to request EPID signingon an arbitrary message to Gatt . The progw requests Gatt to sign(m; rid) to obtain an EPID
signature on m.
First, progw creates a plain-text (addrX → addrY ) indicating the transfer from X to Y ,then obtains the signature as follows:

σ := Σ.Signsk

 !
idx, eid, progw , idx, eid, progw , (addrX → addrY , Hash(τpre )) ; r .
(5.17)

Then, progw encrypts the above plain-text and the signature, and Gatt applies an EPID

5.5. ATTESTED EXECUTION SECURE PROCESSORS (AESP)

71

signature on it and sends the following items to the payee’s AESP.
 τb = AE.EncK idx, eid, progw , (addrX → addrY , Hash(τpre )) , σ
P

 σ
b=
.Sign (idx, eid, prog , τb).
sk

(5.18)w

The plain text and the EPID signature on it that will eventually appear on the blockchain
will be encrypted between AESPs so that nobody can track the history of transmission fromoutside the AESP.

Common id values

In the original definition of AESP, at the end of the process of resume, a signature is
performed that makes it verifiable that the output is from AESP. The signature input value
consists of (idx, eid, prog, outp).
In VeloCash, we make the input values idx and eid be specified in a hash of the prog.
When the ticket is sent, idx and eid can be seen in rich environments. In the payment
protocol described later, when a ticket is won, all transaction information, including pasttransactions, is registered in the blockchain, including the signatures. Since the winning
ticket is registered in the blockchain, including idx and eid, it does not satisfy the cointransparency of the anonymity notion. By fixing idx and eid as the hash values of prog, it
makes it impossible to identify from which AESP the ticket was sent.
Fixing eid means single instantiation of prog. For prog to send and receive tickets, it
only needs to be able to store previously received tickets and information associated withthe tickets. Since the memory corresponding to prog can store the states, single instantiation
does not affect sending and receiving.

72

CHAPTER 5. VELOCASH

5.6

Key Extractor and Revocation

In VeloCash, we would like to have a mechanism to revoke an adversary if he performs adouble-spending attack. For revocation, we use the EPID revocation function.
In this paper, we do not use the EPID’s signature based revocation. From the signature
based revocation, the value to be registered in the revocation list is B, K(= B f ) where fis the secret key. In VeloCash, the signer takes a different value for B for each signature.
Therefore, the signature based revocation list can not revoke the adversary.
Instead, we adopt the secret key based revocation. Once the adversary performs a doublespending attack, we make the secret key f extractable and put the f into the secret key
revocation list.
We define Key Extractor, which is an extractor for extracting secret keys in non-interactive
zero-knowledge proof using Fiat-Shamir heuristic [FS87, PS96]. To construct the definition,
we borrow the notion from Fischlin [Fis05].
Definition 20. (Key Extractor) Suppose a Fiat-Shamir proof of knowledge for NP relation Rλ is a pair of probabilistic polynomial-time algorithms (P, V ) with special soundness [Fis05]. Then, there exists a probabilistic polynomial-time algorithm KeyExtractor whichholds (x, ω ′ ) ∈ Rλ , for any security parameter λ satisfies the following:∀
(x, ω) ∈ Rλ and





∀


(x, com, ch, resp), (x, com, ch′ , resp′ )






s.t. V(x, com, ch, resp)= V(x, com, ch′ , resp′ ) = 1





with ch ̸= ch′







ω ′ ← KeyExtractor((x, com, ch, resp),






(x, com, ch′ , resp′ ))where com is a commitment, ch is a challenge, and resp is a response.

(5.19)

5.6. KEY EXTRACTOR AND REVOCATION

73

Lemma 1. EPID signature has the Key Extractor defined in Definition 20.

Proof. EPID signature has a form σ = (B, K, T, c, sx , sf , sa , sb ). Set the corresponding
parameters in the Definition 20 as(x, com, ch, resp)(5.20)= ({B, K, T }, {R1 , R2 }, c, {sx , sf , sa , sb })where
R 1 = B rf
R2 := e (T, g2 )−rx · e (h1 , g2 )rf(5.21)· e (h2 , g2 )rb · e (h2 , ω)raand rx , rf , ra , rb are random parameters. Then, given two valid signatures
σ = (B, K, T, c, sx , sf , sa , sb ),(5.22)σ′′= (B, K, T, c , s′x , s′f , s′a , s′b )on the same x = {B, K, T } and the commitment com = {R1 , R2 } where′

R1 = B rf = B sf K −c = B sf K −c′

R2 = e (T, g2 )−rx · e (h1 , g2 )rf · e (h2 , g2 )rb · e (h2 , ω)ra= e (T, g2 )−sx · e (h1 , g2 )sf · e (h2 , g2 )sb · e (h2 , ω)sa

(5.23)c· (e (g1 , g2 ) /e(T, ω))
′

′

′

′

= e (T, g2 )−sx · e (h1 , g2 )sf · e (h2 , g2 )sb · e (h2 , ω)sa
· (e (g1 , g2 ) /e(T, ω))c′

with c ̸= c′ , which realizes the NIZKP of the witness (x, f, a, b) by the Fiat-Shamir proof of

74

CHAPTER 5. VELOCASH

knowledge for NP relation Rλ as follows:
sx = rx + c · x, s′x = rx + c′ · x





 sf = rf + c · f, s′ = rf + c′ · ffsa = ra + c · a, s′a = ra + c′ · a





 s = r + c · b, s′ = r + c′ · bbbbb(5.24)

By solving the above equations, the witness (x, f, a, b) is extracted as follows:
KeyExtractor(σ, σ ′ ) → (x, f, a, b)sx − s′x sf − s′f sa − s′a sb − s′b
=
,
,
,
.
c − c′ c − c′ c − c′ c − c′

(5.25)

Further, we construct our scheme based on the EPID signature as a representative of
DAA signature schemes. However, the only DAA schemes that have the KeyExtractor are
applicable to our schemes.

5.7

Construction

This section introduces the protocol ΠVC of VeloCash. The general framework of the protocol
is the same as Takahashi and Otsuka [TO21]; however, it includes a mechanism to anonymise
the sending and receiving of tickets.
The protocol ΠVC consists of three phases: 1) Escrow Setup, 2) Payment with Lottery
Ticket, and 3) Ticket Winning and Publication.

Setting The EPID’s secret key based revocation list Priv-RL and signature based revocation list Sig-RL referenced among all user’s AEPS shall be distributed in a blockchain andglobally referenceable.

5.7. CONSTRUCTION75

In the construction section, we have omitted the verification method of blockchain data
performed by AESP. In each phase, AESP must efficiently verify that the escrow is actually registered in the blockchain and that there are no winners already by referring to theblockchain data provided by the wallet owner.
To achieve the verification, we can use the notion of Proof of Publication for PoW
blockchains from [DNY17, CZK+ 19], which allows AESP to verify that a blockchain transaction is valid from the blockchain fragment received from the wallet owner.
In summary, it is an extension of standard transaction confirmation of the Proof-ofWork blockchain. More specifically, an AESP receives n blocks n-T = {Bi , · · · , Bi+n } andevaluates whether the time to produce the blocks is less than the specified security parameter,
as follows:|ti − ti+n | ≤ n · δ(5.26)

where ti and ti+n are time stamps extracted from blocks Bi and Bi+n respectively, and δ isa security parameter.
ParamGen(1λ ) In our construction, we assume EPID as a DAA signature scheme with
Fiat-Shamir proof of knowledge for NP relation. EPID consists of the five algorithms{Setup, Join, Sign, Verify, Revoke} as described in Appendix A. First, Issuer I invokes an
EPID Setup protocol and generates a pair of group public/secret keys (gpk, gsk) as follows:(gpk, gsk) ← Setup(1λ )(5.27)

where gpk = (p, G1 , G2 , G3 , g1 , g2 , g3 , h1 , h2 , w = g2γ ) and gsk = γ. G1 , G2 , G3 are groups oforder p. g1 , h1 , h2 ∈ G1 , g2 ∈ G2 , and g3 ∈ G3 . It outputs param = {gpk}.
BKeyGen(param) As described earlier, blockchain-based transferable e-cash systems havethe blockchain C in place of the bank B, and C has no secret information. Thus, BKeyGen(param)
outputs nothing such that (skB , pkB ) = (⊥, ⊥).

76

CHAPTER 5. VELOCASH

UKeyGen(param) Let Pi be the platform to perform UKeyGen and param = {gpk}. Notethat every Pi is equipped with Attested Execution Secure Processor denoted by Gatti [EPID, reg ={Pi }, gpk, AE] where AE is any symmetric-key authenticated encryption algorithm. First, Pi
initializes Gatti by invoking Gatti .initialize() that invokes EPID Join(gpk) protocol withI.
ski = ((A, x, y), f )where (A, x, y) is a BBS+ signature on f . More concretely, let p be the group order of G1 .
′′

1A = (g1 T hy2 ) x+γx = Zpy = y ′ + y ′′

mod p
′

where y ′ ← Zp is randomly chosen by Pi and T = hf1 · hy2 is sent to I. y ′′ ← Zp is randomly
chosen by I and the above (A, x, y) is the BBS+ signature on f .
Next, Pi installs a program progw to Gatti . Pi randomly choose a session id sid ∈ Z andsends a message install(sid, progw ) to Gatti and obtains eid from Gatti . Then, Pi initializes
progw by sending a message resume(eid , ”initialize”) to Gatti .
It outputs (ski , ⊥) as (ski , pki ).

Withdraw (B (skB , pkB , pki ) , U (ski , pki , pkB )) We only take param = {gpk}, ski as inputs andneglect (skB , pkB , pki ) and treat them as (⊥, ⊥, ⊥). First, Pi obtains an address ϵ from Gatti .
First progw randomly choose rid to tell Gatti to use the randomness on the RandomTape
specified by rid.

(x, com) ← Gatt .commitment(rid)addr ← Hash(x, com)

5.7. CONSTRUCTION77

The address of escrow account ϵ = addr. The message flow of the above process is complex.
See Figure 5.9 for actual operations between Gatt and progw .
Next, Pi creates a transaction (X → ϵ, β; (p, q, µ)) and publish it to the blockchain C tosend winning amount to the escrow account ϵ, where X is a normal crypto address controlled
by the user i, p, q, µ are the parameters for the probabilistic transferable payments. That is,
p is the lottery ticket winning probability, q is the ticket transaction fee rate, µ is the fixed
number used to specify the block height to calculate VDF.
It outputs (ϵ, ⊥) as a ticket (id, π).
Spend Uj (id, π, pkUi ), Ui (skUi , pkB )

We only take id, π, skUi as inputs, and neglect pkUi , pkB

and treat them as (⊥, ⊥). First, to establish a secure channel, Uj randomly choose sid and a,and sends g a and the attested signature σj to Ui by sending a message resume(sid, eid, ”init keyex”)
to Gattj . Ui generates his temporary receiving address addri from the randomness identifier
rid and randomly choose b, and encrypts it with the shared secret key K = (g a )b and obtains

d i , and sends addr
d i and g b to Pj by sending a message resume(eid, (”get addr”, sid, g a , σj ))addr
to Gattj .

(x, com) = Gatt .commitment(rid)addr = Hash(x, com)
d = AE.EncK (addr)
addr
Next, progw of Pj creates a transaction and calls Gattj .sign(τn+1 ; rid) and obtains the signature σj on (sid, eid, progw , τn+1 ). The transaction consists as follows:τn+1 = addrj → addri , Hash(τn ), σUjsuch thatϵ ≺ τ1 ≺ . . . ≺ τn ≺ τn+1 .

78

CHAPTER 5. VELOCASH

Note that the rid specified here must be the same rid used to output the receiving address
d j returned fromwhen receiving the ticket. Pj sends the encrypted address addr
resume(eid, (”get addr”, sid, g a , σj ))(5.28)

d and rid are recorded within prog ,call to his Gattj when he received the ticket. Since addrw
the rid used when receiving the ticket can be reused when sending.

After that, progw of Pj encrypts (sid, eid, progw , τn+1 , σ) with the shared secret key andobtains τbn+1 . Finally, Pj sends τbn+1 with the attested signature τb.
It outputs ⟨OK, τb∗ ⟩The message flow of the above process is complex. See Figure 5.10 for actual operations
between Gatt and progw .
Deposit (U (id, π, skU , pkU , pkB ) , B (skB , pkB , pkU , L)) We only take id, π, skU as inputs, andneglect pkU , skB , pkB and treat them as (⊥, ⊥). P send his crypto address pk to receive thed by sending a message
winning money and the ticket receiving address addrdresume(sid, eid, (”check winning”, pk, addr))

to Gatt . If the ticket satisfies the winning condition, progw creates a blockchain transactionτ := (addr → pk, Hash(τpre )) and sends it with the attested signature.
It outputs ⟨OK, τb∗ ⟩The message flow of the above process is complex. See Figure 5.11 for actual operations
between Gatt and progw .
Identify (id, π, π ′ ) As described earlier, blockchain-based transferable e-cash systems havethe blockchain C in place of the bank B, this algorithm is executed by any user U. The
user receiving the ticket will verify within Gatt that the ticket is a double-spending one.

5.7. CONSTRUCTION

79

Detection of double-spending attacks is possible if the winning ticket is registered in theblockchain or if one user receives multiple double-spending tickets. See the Definition 11
and 12. (id, π) corresponds to id = Hash(x, com) and π = σ, respectively. Suppose there
exists double-spending tickets (id, π) and (id, π ′ ) such as
addri , (addrj → addri , σj )(5.29)

addri′ , (addrj → addri′ , σj′ )where
σj := (B, K, T, c, sx , sf , sa , sb ),(5.30)
σj′ := (B ′ , K ′ , T ′ , c′ , s′x , s′f , s′a , s′b )respectively. Since EPID signature has the Key Extractor from Lemma 1, the adversary’s
secret key is extractable from σj , σj′ . The extracted secret key f will be registered in thesecret-key based revocation list Priv-RL.

It outputs (⊥, ΠG ) as (⊥, Priv-RL ∪ {f }).

VerifyGuilt ((id, π), ΠG ) In the blockchain-based transferable e-cash systems, this algorithm
is used to verify if a ticket is created from the secret key f registered in the secret-key
revocation list Priv-RL. Let
id = (x, com) = Hash ((B, K, T ), (R1 , R2 ))(5.31)
π = (B, K, T, c, sx , sf , sa , sb )80

CHAPTER 5. VELOCASHand ΠG = Priv-RL = {f1 , f2 , · · · , fn }. It outputs 1 iffotherwise outputs 0.

5.7.1




R̂1 = B sf · K −c







R̂2 = e (T, g2 )−sx · e (h1 , g2 )sf · e (h2 , g2 )sb






·e (h2 , ω)sa · (e(g1 , g2 )/e(T, ω))c
c = Hash(gpk, B, K, T, R̂1 , R̂2 , m)







where m = (addrj → addri )





 ∃ f ′ ∈ Priv-RL, B f ′ = K,

(5.32)

Ticket Transfer Overview

The actual operations of the algorithms described above are processed within Gatt and progw ,and the flow can be complex. The following describes the operations between the wallet owner (described as Wallet) and Gatt and progw for setting up the escrow, making thepayment, and processing the winning ticket.
Step 1: The ticket issuer issues a smart contract escrow account ϵ and confirms that ϵ
has been registered in the blockchain. Step 2: The payee sends the ticket τ to a payee. The
payee verifies that the ticket came from a legitimate wallet and that the escrow account ϵ isregistered correctly in the blockchain. If there is no problem, the payee receives the ticket
and returns the service or product to the payer. Then, the payee signs the ticket with his
wallet and sends it to another user. Step 3: If the ticket received meets the requirements
for lottery winning, The ticket owner can use the ticket to send the winning amount to theiraddress.

Escrow Setup
Figure 5.9 shows the flow diagram. This process is part of Withdraw. It executes a deposit
transaction τl on the output ϵ and registers τl to the blockchain network B. The issuer’s

5.7. CONSTRUCTION

81

wallet WX requests an escrow account ϵ from Gatt . After the wallet obtains ϵ from Gatt ,WX creates a transaction τl that transfer the winning amount β to ϵ and sends it to theblockchain network.
<latexit sha1_base64="ykonS64joM74B9ZgagFkRjsZoDc=">AAAdgnic7VhLj9vWFb5J0zZmH4nbTYFiAMImW8nRqJxxHQd2Jk3r+BEkQSYztmdQUVAp6o7EiC+TV48xwUW7zB/ookCBFuii6M/opn+gi/yALoosU6CbLPrdQ1LijERO4ozTBIiEkS7PPY/vnPPdQ2r6oevEwjA+fObZbzz3zW99+/kLyne++73vv/DixR88jINJZPMHduAG0WHfirnr+PyBcITLD8OIW17f5Qf98S25fzDlUewE/n1xHPKuZw1958ixLQFR7+KFj8x9Lt6a7UbBMLnjp8m7vhpxmztTniZ4K6Xtu9m24zvCsVzn8arGPZ9EC+GdiW/LOInjx8Jy3TQxo2hxkeqn1SIeTzyeaeXrVaUxP+bzTCdbQkUx+3zo+EnMH024b/OBYw0jy0sV3Yy4z2d24HmWPzAnwH5k2SKIEqN9LVVgiF0JKJnB55txPOGRqh1qP43VA2DkQtUOeodautDrXG1f6yZDSwjoa6ZniZFtucndtGcKPhcJNtJV/RDVmS0M4iMSwCS/mqUaYYkFD+1g4gseyVRcPuUuNsx39u8SvhNhhShqZLr8SDS4M2ipjWLrUgzspspjOwpml9KmakbOcCSaMlBFnHMRI/FgwFVLqA2tkaXdfKmx1b7e2jTFiBeKV0qt2DTa18vXTa2pKkneUUEc7wfztEP03qkuYUudOQMx2tky2obtdRUVL/OO32gmWmVZbmhpQoqqqkXOoJeYPIwdN/BT1RxyEatk2O8nv0411TQL1ca8pRaRwS2U98aOWiZDsmRD2i6CSxY6wuO+SBsngzXLzgvpwieC3LPiUboStWQVo3BcXRRn4sch9we3AsdPO4XDrvR4MnDJg7nHxSTyl/E18yZtoddwVeqEkt48JxIp5t7t+wWtswNCXI7BZcnnAkrLjJ2hZ/UOyzTWK5zqZQoS/YzPRL5E0Su68Aa3ZWvzq7fStFFoNTVFR1Wqsv+8gCQeYU16bhnNvjP0S3Dicdo7TBsokQjUReFUnCNh3VQbYetRy/QmTSB9qkBjcKVAq6mAAnO17wb22B5Zjq/6XMyCaCxBPOUGYhrwkSVKR7pUvNv+Ga3Ua+A90TymA2qqejF7WqsAy1O6Lv7Tlp/PCNfPYYbr64d4XstFKdU1taTRrtfM1DWnedULDcjcC9qbTVk5Qw/LN4jKiVs2PzWixfyWPBBL3VQFNpybss1yKOe549FJTOJUzmY9G8766elMg0jKTj8N9V68jLLSS11dbOWLyyx/7QYXL/yCmWzAAmazCfMYZz4TWLvMYjHeHUh95kASQIuzFlPZFjNYCK0uS6AVYeWQBWcpU+BtAjsODQvSMT6HuOrkUh/XMkpM1tKri78IlirTjX8afzU+Nv5h/M34t/FJpa+EfEh0x/juZ7Y87L3wwY/2/3umlYdvwUZLK1joNagFO2KvEFoH6EOSyDzszMP08e8/3r+xpyc/Mf5sfIQM/mR8aPwdOfjT/9h/eY/v/aHGf4Lcpf/quiX4jLAOgVhWOSZdHZGr9F3ILcI4Z+9jlUpt/q9h64M/GgdGz3ij1r6DKFIirbtrvG1iN6L+cUjJN3uT7bJfSo1F/4o4nyWnKjwxm2J1kjfzE8ypjhPiu766krtj9viETiFz8d0npBGYlmBvRKglihZJIyCYrVy1CamArIXoDlYtxLTgz8YqhFZMUgcrn1g1JA+SWUHOT2lb4PDI+5hspd8I8rOzDqk+ora6CfLzckZVnxoXq4CiynNTr99Bt1zKiWNeyGlRXMX4nNB55cSgQT4/Tnvfrp0jT2LRJ64MwF3JYkEdrefEkl3Sdv4pqr1JubnQGNSymVO3ZU0km7qEzqKauLV2GQeGVMsdTGAbki6dJE6cyXhxTDNJeim4k/E5weeU6n6M/ZBOnUAk2Yefga+S1SFhG2A/xt4xzfMdqoaslw/pEVXEI43iJLSwzrgttQ34uobPlHKROGTnZ1RPj3KQERLI32H77C60Ouwq5aHAq5xJMc2akCwmdC+SqBPK4xFFmS5qpeZvk6oluaCyBruM6jTZS1gZQLdJtRjlE6vs4QrV2icWHVG1BeW3SVlcr9xvIoqf3w1lvGwqxVgf0QTwSCMBwps1GLf/Txjl/np8A+rzDB3ZZK8B1Wvop5WzVXp5mbCKfGaP0bXq7DfxXh+3QCUZ7WA1Q4xjmhMWnTWZdzfHlaBOVwlnWsulPXab3f+aS19hLrVgYdFUye4LXxZm7bN7YNfXzPoyMuvVr9ycusXexX1vl/i0/Tn5ZJYqJzsms9C+EF5peWckOz59zntfUNbbT5j1NrLePresI/pd0gGqLl2L/MlT0LPY8rqPKAmhT/Nnpmqf2a/PdI2/YqfePqDfF+s9LPfqfYR0doZrfSz36n3Is+at9VDsnPXsuI+Mh2DU27mX4hd9TNXMdpdSm55VI/YbdDmzqce3S78sppX+i/0nj1BUarbW/7KOvZW92Zm+H9IZcqB9vNb7yf16X0NgGa/1Uuyc1ansl8HuKR+ZNCG5/I/V1un/T60uHm63t15u//y97cuv/yr/39Xz7MfsEk78FqbV67hP77IHzFb2lLnyW+V3G89tXNnY2riaqT77TG7zQ3bitfHq/wAs/kX/</latexit>

progw

Gatt X

Issuer X’s Wallet WX

resume (eid, (”set escrow”))
progw
On receive (”set escrow”) :rid✏Z(x, com) := Gatt .commitment(rid✏ )✏ := Hash(x, com)store unspendCoin[✏] := rid✏
return ✏(sid, eid, ✏,X)⌧l := SignskX (X ! ✏, ; (p, q, µ))send ⌧l to the blockchain network

Figure 5.9: Escrow Setup

Payment with Lottery Ticket
Figure 5.10 shows the flow diagram which shows sending a ticket from X to Y . Suppose that
the X’s wallet has a ticket τn and generates τn+1 or generates τ1 from the escrow account ϵ.
First, the sender X’s wallet WX resumes ”init keyex” to perform Diffie-Hellman key
exchange with the payer Y , and requests invoice to Y ’s wallet WY . Gatt in WY generates
the receiving address and encrypts it with the DH shared secret key, then sends it to WX .
Second, WX processes ticket transfers to the address sent by WY . WX passes to Gatt thed X used to receive the ticket or
address received from WY and the encrypted address addr
create an escrow account in the past.

<latexit sha1_base64="tDPa1cFJIdioBO7wTGpRv1jIDrE=">AABCWXic7VpLjxvHER47cWIziR/xJUAuDWmYkBaXIleWFUhZw9JalgJZ0HpXllbaoTbDYZOccB7UTPPlwfwB/4EcAgRIgByC/Ixc8gdyMHLIKYcgRwfIJYdU17yffOxaKwXaxZI93dXVVV89urpnu2NNtVmr9dUrr37r269957uvv1H53vd/8OZbb7/zwwe2ObEU+rliaqZ12JVtqqkG/ZypTKOHY4vKelejD7ujXT7+cEotWzWN+2wxph1dHhhqX1VkBl3H7zTn0gFld2Z7ljlwPjFc555BLKpQdUpdB34rseFb3rBqqEyVNfWLLMVtA7vCzk8mhsLXcVTDZrKmuY5kWeGDW02TWdSe6NSj8ttZohFd0LlH4zWBpCJ16UA1HJs+nVBDoT1VHliy7laqkkUNOlNMXZeNnjQB2fuywkzLaTUvuxUYh1EukDNQXEeUdJkNFVlzbrnHEqNz5siMuaIb0R1tNy93nATtbpLgEiew4wQHOQQDe7XlkHjcD4gZc8aAdEBudvucvBJqwQdn84Da7gfU/tOMU6cEgSXnhbIcZug598Of2uQhmJAyIj48zqFZuM6jBM2j3HUXhetm6VGzRblmFclmdKyYE4NRizuDRqdUc4u6YQWzR4nMSE2szeb1C7VWY0tiQxqQvBdzmK1W80r8uS7WnQohoq32iKQaBAXpdp3HrlhxrxWKUpHuHtxCEH3gOY/AtL7PS111oNWAcYNQ/lELxs/x2CMSQb8/59Y5IQhSWVvzVQDxXAlAaTevrAULqTh+ODJMUF1z7h5hbtoRJeQqNshM7bHhTrvdvKzoHcCAEOkTo1Z3xCJlGwQBGdSvigga/xFlIg0os2PgHztjVySSFFAE/nHdPYL5HXJ1h8ixcRtEpnGq2FhV9PzRo3FJQHTHvbojabTPaoMnjuxKljoYsvoTpxufLO1TNrEMIiKNKF3DfkCeGr0YLtxTqhnUFxuhXl0H9haHvZqLewC4hzcX38O86kPaTfl7CHlAsBFs1RRuMVKUohvM4FhWPTCrOWieTiBUpYPb+2E2DXIPX1eM9Ik7H++gi5tzl8cthGSVR9P+zftBmM/8UMew5lHtmYSrJjeIZKsDXT4+3CSWo4yCIpIAutCeFt8UbR5KqjE1VYWCbZeIQQKsK4hFz5JnR2yoKqNOwke3Szy03dxOe+jWVmL2+833Sz08Pf/aGUmynSPJZjZauMG2V5j1UwkfHAzsJvd6VpQBwVKhoU57B1g7THbv3d0LlfLySSYJeUnnSnNb0RvEy0g3DUWTp5TcG1MLS1G7E2YAzEeSh4ojIiABHqoBqcaNclEQUATdmNNRvc5z/P2jaJ5XgnXEKMnwaZI5YWN/BiQmPr8GeS3oSlLnsLu6k105OckzEvA+4N9NyURdTcuQQS/og8SJDC3d0e2R68Z2/GrAlQvJM57rY5vMdzzLnNLmUbJ3FNVbqU286j1dbl4p3NELvDnKO7G9XVYUOmZE7Ud7arS38G3lAbXU/qImDcajhrRnqdP9TxscavjymII8dCgzx+MOaB+6dbLTjlcH3dz6obHeVl+039FFVHNEDOMTLbV3/CgjQpyiNo+EgUOMWw+Z+SWzE9XMbjMAmh93VKZTg7k1XKOeVxJxO7iwfky827I9dDNrJiaHqMa5pNhcv9mEAA/8G9V2a6ll68VV2MSwxyD7rqka7lHhgograpdXdhVOa9TQOwZPuvXCqowX8N9o3gwrg4W3a/tbdpgAimKuUawWQb24WmE8PQq38U2LioVXuKQrilQdcZoi1+MyVwtw2mStHEyqhUqenPf6O2n6XFjNKRFQwlSJoMsjKpGxvODxfq5YzsOTGSs0UKw45NvPCsfZpG9vLvqGkpd62fqVU6zmmb+sec6m5nn2pe5z1P2N39EsLfgu4fXBCgXf2QV4eSUZlpFiVHV49WRUp0Bd6aYLy5ram8ePzSvIVI8yJ9kh8eoTot2re0oupO64PLI5s/qT7opFHFRfH9NM9VUkabwOq4YihVF/P33Lwea7QxkKsyzHNOdE4Vj1v8EK2dosORPcIbphiq0oxk8CcQvyIvAwjsBKBeRhJ8GwmucTdwBFY6udc9PjlfbLOXj2OUwxWMtEh/VCzU/neFCyQFqNdc4KCU6hZ4FE8sSNMwrsm7VUGgi3UyxoSmbYYOwma4LlCF9wR6JjW9VMg+9dVMG+43bwoPRMbpxoxCnxtqg5G1KMFX/GTuqI8xh4mSSFYCOFnz8ZfCzKXo8BRdUmMpnKmtojzJINW8aXX6ton9cEOcRDkfQtUye2qYPQj8VCVijQhbaXeYpMkdAtpyLOU9Kt10sCJnzpEcuvODNpmAscqeDCgHj3X6s4PcyApFXA8BpZFgd50kUMNhco4rFMhh7VKFv3lFyS5NL8isMwn1cCnnBKOrhzrwKWWbksMC/EI4Vf6ZxgkzFMlrPPEEmTjR5Zc5eKm6MIp4sXCRtCZOsTm5EuhQdKFNmmK0kLmPo5rCh0uf84AZG7+oaYWavY0Kez4QQylsRbkK433nD8RBaksTD9r5O2AjHXzAu1vM3GOWHeKmDpZY3I6i9m+vjGMolTki0SMshd02Je4giRTqaHggAPck7OzSPX4MzuGP/PujMvU8XY1UHwEjMJfcErADH9yjT7TnZVPkUqrPCyL7wTS12J+f98ReKnZrKZgI3sFhYe+ja//jqD7pdvGc/8xu35ec1IVrh2yguidO2+QgQVX+/Er5eSdybhnU3ZXUHVqxskZ9XzTnwH48yrK14kcN0SBXLRvmtacelWL2jSgq0jF9ZAUt5emhGATzjRWrFFoAiXbR71Xom4Izl52sEDSNYHXLzzssFvcJ4m7u+WvKHm+Ja8o86ouEpKT76+JnlHaFBnjVUzDgfFboMsWXMVJ8rItpZQeZc1eYJlXegkFuBOFvextOK5B5T4/8Ltuk8cSYPco5FR3HsUk//Ls8GIOIJ0xg+XUFoSLCfzLl8z/xaw+jvx4ptkvz4vmeulLQAh9316cBxhMpvYLqmh3k6r0Zbc8hfpFa8z/a/Zx2+fbzVb+EOyjbbfOC/4P3vmO2/0hKpABEnYF6jwVJgIqmBBa0+QBUUYwecAnhxBgxFZYNCeCz8TLgsNwRaG8KTBL4W2IrhCBbj0BBPaE0GHXgPoFRiXYdwWjqDXAO4KUPRgtAGrtoWWMAaqDqwgw7oMxzlHj9sE5lGgiMty5Pca8Kzj2nw256rBnwUziVBt/bX1x9bXrb+0/tT6Z+u/hbwc5MGlW8B315tLx8dvffmjg/8snaUjIsNoFsyolkjNhD5gx6VVQfox9nA9FI/D9Itff31wdb/q/KT1+9a/QIPftb5q/Rl0MKb/Vv7wGd3/TQl/B3Tn/Itxc+DTgvYYJOYo20jr2T6fPm7zX0HL5dT0H4PGl79tPWwdtz4unX8Eq/AePruTw20LRi20H4Ve5C38AvzuOqcI7Ress45ORfLYwhRaSb+ZJzyneJ0xfJejy313JHyRoAn6NPjuoqQWeJqDscOl5lI0sNcCCWaZpyZKyqCvAaur0GrAmjLwU6A1Biobe1VoGehVA+TAPcv0/ZPPDeTQkfsI53K+FvQv13qM+LBSdB3QT/c9qjhqNGiZuCqPm3L6I7CWhjpRyBc8WwRPNnxOMF4pelDPzx9p7tuleWSTGV30lR74LvdihhYt94nIu/jc+Qpob6FuGlD0Sr2ZorU5JtybOiidjJhopfM8HxggljuQgRXo6WAkUfQZzy8WmJM4l8B3PH924HOKuC9gfIxRx2AlboeL4K/cq8coWw/GbRhbYD7fQTQ4Xgb09hERHSmCSGjgLiL71C3gdRk+XdSFy8EtP0M8ddSBr+BA/13hQLgFVEfCJdSjAlx5TrIx14xxxgT3Ii61g3o8xVWmIVbE/5UQLe4LRKgJ5wGdunABWi2QbguxGPoZK87hPcTaQC/qI9oM9dtCLa4UjtdhFcPfDfl6Xlayod3HDKAjhQMSXiuRcfuMZOTj+fL10M4zsMiW8CFI9SHYU/a9lXP5AGVlfs4egdWKtd+C3/x1A6m4R6vQmsEaC8wTMsYa17vjy+UATpdQTrfUl/aFm8L9l770AvtSA2bIfm3ae44860C4Dd710rOeR8/6+QuXp3aFe7Dv7aE/bZ/Qn6QYctxiXAvxmfiV6FuGe8fqOu8/I623N9R6G7TePjWtLTyXHIFUHXxmfuXJsBaLnruwioPSu37NVMzTO326OfyCkfL5Jp4v8jlEY+U8xhg7g1we0Vg5Dx5rei6HYGRZ7XgAGg/Aoz71uQQnehvR9EajXgVrVUv4JVjZm1Mu3x6eLKaF/IPxzVcIkJrl8o9wPM6MzZbyfoAxpAL1Ipd7cryc1wBkGeVyCUaWWco7GeyleHi9Dvbzu692+qYr23iw3Wx/0Hz/s+3zH932b8FeF34snIOIb0O2+gj26T3hc0Fp/v3iaxffvPjW9b/deOXG6zcqHumrr/hz3hUSPzfe/R/DdhBt</latexit>(sid, eid, progw , g a ,d X , (sid, eid, prog , addr
d Y , (g a , g b ), Y ) :On receive (”make payment”, addrw
accept if
d Y , (g a , g b )), Y ) = 1
Verify(gpk, Priv-RL, Sig-RL, (idx, eid, progw , addr
restore aa bstore K := (g )dY)addrY := AE.DecK (addrd X 2 txChain
if addrd X]
ridX := unspentCoin[addr(x, com) := Gatt .commitment(ridX )addrX := Hash(x, com)\
restore ⌧ := txChain[addr
X]

progw

sid 2 Z

X’s Wallet WX

X)

⇣

Y)

⌘

d Y , (g a , g b ),”invoice”, (sid, eid, progw , addr⌘

d Y , (g a , g b ),sid, eid, progw , addr
Y)⇣resume eid, (”get addr”, sid, g a ,X ))Y’s Wallet WY(”request invoice”, (sid, eid, progw , g a ,resume sid, eid, (”init keyex”)

Gatt X⇣d X , (sid, eid, prog , addr
d Y , (g a , g b ),resume sid, eid, (”make payment”, addrw

On receive (”init keyex”, sid, g) :a
Zp
A[sid] := astore A
return g a

progw

progw

Y

⌘

X)

Gatt YOn receive (”get addr”, sid, g a , X ) :accept if
Verify(gpk, Priv-RL, Sig-RL, g a , bX ) = 1bb
Zp , K := (g a )store Key[sid] := K
ridY
Z(x, com) := Gatt .commitment(ridY )addrY := Hash(x, com)d Y := AE.EncK (addrY )addrd Y ] := ridY
store unspentCoin[addrd Y , (g a , g b )return addr

progw

progw

82
CHAPTER 5. VELOCASH

Figure 5.10: Anonymous Payment with Lottery Tickets (Payment from X to Y )(sid, eid, progw , ⌧b, bX )d X , (sid, eid, prog , addr
d Y , (g a , g b ), Y ) :On receive (”make payment”, addrw
accept if
d Y , (g a , g b )), Y ) = 1
Verify(gpk, Priv-RL, Sig-RL, (idx, eid, progw , addr
restore aa bstore K := (g )dY)addrY := AE.DecK (addrd X 2 txChain
if addrd X]
ridX := unspentCoin[addr(x, com) := Gatt .commitment(ridX )addrX := Hash(x, com)\
restore ⌧ := txChain[addrX]s.t. ⌧ = ✏ ⌧1 · · · ⌧nwhere ⌧n = (addrZ ! addrX , Hash(⌧n 1 ), Z ) is a valid transaction
to X from some Z⌧n+1 := (addrX ! addrY , Hash(⌧n ))sid, eid, progw , ⌧n+1 , X := Gatt .sign(⌧n+1 ; ridX )d X]
delete unspentCoin[addr⌧b := AE.EncK (sid, eid, progw , (⌧ ⌧1 · · · ⌧n+1 ), X )dX 2
d X 2 unspentCoin
if addr/ txChain ^ addr
dX = ✏// this must be the case addr
d X]
rid✏ := unspentCoin[addr(x, com) := Gatt .commitment(rid✏ )✏ := Hash(x, com)
⌧1 := (✏ ! addrY , Hash(✏))
sid, eid, progw , (✏ ⌧1 ), X := Gatt .sign((✏ ⌧1 ); rid✏ )d X]
delete unspentCoin[addr⌧b := AE.EncK (sid, eid, progw , (⌧ ⌧1 ), X )abort if ✏ 2/ unspentCoin
return ⌧b

progw

⌘

Y)

⌘

Y

return addrY , (g , g )dY) :On receive (”receive payment”, sid, eid, progw , ⌧b, bX , addr
restore K := Key[sid](sid, eid, progw , ⌧, X ) := AE.DecK (b⌧)// assume ⌧ = {✏ ⌧n } for some n 1
accept if
Verify(gpk, Priv-RL, Sig-RL, (sid, eid, progw , ⌧b, bX ) = 1
Verify(gpk, Priv-RL, Sig-RL, (sid, eid, progw , ⌧, X ) = 1✏ 2 Cdk for some constant k, and not spentd Y ] := ⌧store txChain[addr
return status(2 {0, 1})

progw

⇣
⌘
dY)
resume sid, eid, (”receive payment”, (sid, eid, progw , ⌧b, bX ), addr

(sid, eid, progw , ⌧b, bX )Y)

d Y , (g a , g b ),”invoice”, (sid, eid, progw , addr⇣
d X , (sid, eid, prog , addr
d Y , (g a , g b ),resume sid, eid, (”make payment”, addrw⇣

d Y , (g a , g b ),sid, eid, progw , addr

5.7. CONSTRUCTION
83

84

CHAPTER 5. VELOCASH

Ticket winning and Revocation
When the ticket satisfies the winning condition, the ticket owner sends the winning ticket
to the blockchain network. See Figure 5.11.
The ticket owner sends his address pkY and the encrypted address used to receive theticket to Gatt . Inside Gatt , Gatt creates and returns the transaction to transfer to the address
sent by the ticket owner. Then, the ticket owner receives the transaction and sends it to theblockchain network.
If the winning ticket is a double-spending one, the adversary’s secret key is extracted by
Fork and collision detection.
<latexit sha1_base64="6YppsDY9pmP8YxWQfFae+tlX9J8=">AAAeUXic7VhLjxxXFb4xr6QHSAwbJBTrYveQ7rhnqGnjGNlMCAz2ODJRxjO2J/ZUq6muutNddPWtTtXtl0v1B/IHWCAhgcQC8Q/YsmGPWOQHsEAsg4SQWPDdU1X9rhrHWMGW0q3pvnXPOd/5zuM+elp9zw2VYXz80rkvfPFLX/7Ky6+UNr76ta+/+tr5bzwI/UFgi/u27/nBBy0rFJ4rxX3lKk980A+E1Wt54rjV3dPy46EIQteX99SkLxo9qy3dU9e2FKaa50t/NI+EujM6CPx2dEvG0fuSB8IW7lDEEd6lOfF+Inalq1zLcx+vatyWNDWdvDWQtvYTuTJUlufFkRkE04d4c1ktEOGgJxKtdLyq1BUTMU50kiFUSmZLtF0ZheLDgZC2cFyrHVi9uLRpBkKKke33epZ0zAG4n1q28oPI2L4aww5CzScaTeLo4RshPwYzoXj5uPmwHE/FJ1e2rzaitqUU1Mpmz1Id2/Ki/bhpKjFWEQTxqn4fORlNDcJTmoBJ+jSKy5pBqETf9gdSiUDz98RQeJr4e0f7xGrBq1JZYkxPnKpK6Do1gT9eycQX7Y6wu9zkICJd2b4Y1/gEj5XdzO/Bnbj5sFrj5sh1RMdSUSawHCeItYybgdvuqKqO6BnSmKahCydP6D8vP8/RtPQdwS3FK+VKUvHq5crO9rXalqk6ItN7c673tozta/PP1XKVl6K0hRUt6pY/jk9oPe/md08NyXVUZ3fH2DbsXqPE8TJvyUo1Kj+bOlwvxxGhcu6e8vKK4qIBLLjpyim8Gu91LFfGZW6aKQoHCC0Yjtly4Dowub47tRjIsC+k2vNhdZJLq5ELWBnPgsOSj6tT8HS1RrPlGm9nKdKbg6t6cBxXiFI118EClUXut62wE68QyEPC6kHhBS+DkTUAMXl5J56Hy5K3mobldMTz+dicLxeQU+D5soyWS7K5EGFqVCc2lXkMHCw2n9SWIp5pVAvytoSaEwo3lb/SnaveEmDQWXRpHgo1COS8tzkpZUT0Q9fzZZm7Ibc8HJTOhFPLcV+m1W21oj29tLB25azgt/ygG5OZI5SwlXCWkFd63valwihcs2yS7nkEpVFH6CYgwpLrzOQ0/aMkNTnSYH1RZnmKqzUzdNs9q/kIGVsMDZcEXDRwsubF967kLV91uI17RkiJAWcxxuUkTKi/MZfmdasl7KJ72gLq2cwdMbk5VgHtfglbRKCRqnlQ0+GsyjP0OSNf0xu5oZhTBPuyeYMUsF0L6cxtsqX4xotwxhzevJedwMmNYuHYnTV8Vma9cGZn6OaZl4yWrUGTOhBC0dE7d+DRYWd8qqNOnyghirC4TtHdgOAtz7e7tl5CXAo1wqpLCqSLtny5a752CQcfvfjqYCcdXGLp68A//8qPmMkc5jObDViPCSaZwthjFgvxPsGsZC5mfGgJVmOc7TCD9aHVYBG0AoxcshAsZiWgDWAnoGFhtovPNp5O0lmJZ+0lJGuN6uEvgCVnm8Zfjd8bnxh/Nv5g/N34Ty5WRBia3QTfrcRW9JuvfvSto3+dadXDt2KdmRUsNgtYK3bKfkBsXbDv04yOw04Qho9/+cnR9cPN6LvGb41/IILfGB8bf0IMcvhP+3d3xeGvCvAjxK7x8/MW4TPAuA/GOssh6W7Cc56+h3mLOI7ZLzCKtbb4W7v20a+NY6Np/LTQ/gRe9Iy2bqxB24I0oPoJzBI2e5cdsB9rjWn9Mj+fJqY8PiEbYrTYN+OFzsn308d3cXZ173bZ4wWdbM7Dd4uYBui0CLIOsdYsajQbgMFo5WmbmCrM1eDdxagGnxbwbIz60App1sVIUle1CUF3lp/2p7bNePQIvUu2GjfA/NlR9yk/qjC7EeLrpR2Vv2o8jHzyqtdNsf4JquVRTAL7hd4tsqcQnwNar4I6yEn3j2X0euE+8jQWLeoVB72ru1hRRYt7YtZd2nb8BNneotg8aDiF3Syo2jonupsaxM6inHiFdkkPtCmXu9iBbcw0aCUJ6pmkLya0J2mUrHeSfo7wOaS8TyDv06pT8KTr8D30q+7qPnFzIA8hm9B+vkvZ0PmSmD2ljPRII1sJNYyT3tbaBrCu4jOmWDQPXfkR5bNHMWgPEebfY0dsH1on7ArFUQKq3pNC2mv6ZDGgs0izjiiOD8nLcJornr5NypbuBc4q7BKyU2WXMTLAboty0Ul3rHmENynXkrrolLKtKL4tiuJarrwKLzI9DbW/ZFcKMT6lHaBHGhEY3ijgWP8/cdTy9fwcqvMIFdlib4PV26inlXarRnmLuKp0z+6iavnRb+G93m/GSne0i9EIPia0T1i01nTcjZRXhDxdIZ5xYS8dspvs3ue99AL3Ug0WFu0qybnwvHTWEbuN7vq8s57HzvrhC7dP7bH3ce4dUD/V/8d+Mucypyumoyh/Jn1VTiuju+PJYz78jKKuP2XUdURdf2ZRB/S75ASsGvSs0punorvY7LkFLxGxj9M7Uz5m8uszXoOXSYrtffp9sR5hJivG6NPaaa/FmMmKMfRa661FyCRn3R2PEHEbHfWzFCX7RR9SNhPpbNamu2rAfo4qJzbF/A7ol8UwFz+TP72HLFOjtfizPDZXZKMzsR/QGnKhPVmLvigvxmqDS3ctSiY5q1LJL4ODJYxkNqJ5/R+rneX/T60OHtS3d97a/v7d+qV3fpL+7+pl9m12ESt+B7vVOzinD9h9Zm98Z2N/42Dj7ut/ef3fF9iFc4nquZdSm2+yhdeFjf8CCXiQtQ==</latexit>

progw

Gatt Y

Y’s Wallet WY⇣⌘
dY)
resume sid, eid, (”check winning”, pkY , addr

progw
dY) :
On receive (”check winning”, pkY , addrd Y 2 txChain
if addrdY]
ridY := unspentCoin[addr(x, com) := Gatt .commitment(ridY )addrY := Hash(x, com)\
restore ⌧n+1 := txChain[addrY]
if ⌧n+1 2 win⌧n+2 := (addrY ! pkY , Hash(⌧pre ))return ⌧n+2
if ✏ is already spent on C, then Fork is detectedd\
if txChain contains addr
Z where ⌧n = (addrZ !
daddrr , Hash(⌧pre ), Z ) then Collision is detected
In both cases, there exists ⌧ 0
skKeyExtractor(⌧, ⌧ 0 )return skotherwise return ?

(sid, eid, ⌧n+2 ,Y ,)send ⌧n+2 to the blockchain network

Figure 5.11: Ticket redemption

5.8

Security Analysis

In this section, we analyze whether VeloCash satisfies economic and anonymity properties.

5.8. SECURITY ANALYSIS

85

Finally, we analyze whether the proportional fee scheme and double-spending attacks
detection methods, a requirement of the transferable micropayment scheme, can be achieved
even if the anonymity is preserved.
We construct the theorems under the following assumptions. First, we assume that the
tamper-proof hardware wallet and the collision-resistant hash function exist.
Assumption 1. κ-tamper proof hardware defined in Definition 10 exists.
Assumption 2. For all PPT adversaries A there is a negligible function negl, collisionresistant hash function Hash exists that satisfies the following inequality:

Pr [Hash(x) = Hash(x′ )] < negl(n)(5.33)

where ∀ n ∈ N>0 , x, x′ ∈ {0, 1}|n| and x ̸= x′ .
Next, we describe the assumptions for ensuring EPID’s anonymity and unforgeability.
Assumption 3. The q-SDH problem and the Decisional Diffie-Hellman (DDH) problem arehard.
We assume that the blockchain network is agreed upon among honest users to simplify
the proof.
Assumption 4. A blockchain network is agreed upon by honest users with a public parameterk satisfying the three properties the common prefix property, the chain quality property andthe common-prefix property proposed by Garay et al. [GKL15].

5.8.1

Economic properties

In this section, we verify that the protocol of VeloCash, ΠVC satisfies the economic properties.
Theorem 7 (Soundness). The protocol of VeloCash, ΠVC is sound. More formally, for all
PPT adversaries A, there exists ∃ λ0 ∈ N such that for all security parameter λ ≥ λ0 , ΠVC

86

CHAPTER 5. VELOCASH

satisfies the following inequality:


sound
AsoundA,ΠVC (λ) = Pr ExptA,ΠVC (λ) = 1 < negl(λ).

(5.34)

Proof. Suppose there exists an AESP A1 of wallet W1 and another AESP A2 of wallet W2 ,and both of them are honest. The adversary wins if A1 receives a ticket from the adversary
and spends it on A2 , and A2 refuses. Due to the tamper-proof assumption, the adversary
can not break his tamper-proof wallet and can not perform double-spending attacks. Thus,
to win the game, the adversary has to forge the EPID secret key and creates a ticket witha valid EPID signature. However, since the probability of forging an EPID signature is
negligible small from the EPID’s unforgeability in the Theorem 6, A1 refuses to receiveit.

If the adversary can break his tamper-proof wallet, the adversary will perform doublespending attacks. Suppose the adversary performs double-spending attacks on A1 and otherusers, and the attack is detected. In that case, this must be a case where the adversary’s
secret key is registered in Priv-RL, and A2 refuses payment from A1 . Soundness is broken if
skA ∈/ Priv-RL when A1 receives the ticket from A, but skA ∈ Priv-RL when A2 received theticket from A1 . However, for an adversary to gain sufficient economic benefit from a doublespending attack, a large number of double-spending would be required. From Theorem 3,
there exists an upper bound on the expected utility of the attack. For users who receive
double-spending tickets, it is possible to compensate for the loss by setting an appropriate
issuance.
The temporal collapse of soundness is a universal issue that also exists in E-Cash due tothe timing gap between the execution of the attack and disabling the adversary.

Theorem 8 (Unforgeability). The protocol of VeloCash, ΠVC is unforgeable. More formally, for all PPT adversaries A, there exists there exists ∃ λ0 ∈ N such that for all security

5.8. SECURITY ANALYSIS

87

parameter λ ≥ λ0 , ΠVC satisfies the following inequality:ihUnforg(λ)=
1< negl(λ).
(λ)
=
Pr
Expt
AUnforg
A,ΠVC
A,ΠVC

(5.35)

Proof. The adversary wins the unforgeability game ExptUnforg
A,Π (λ) if he succeeds in creatinga new valid ticket (id, π) which is not included in the supplied coin list SC or to create
multiple proofs π, π ′ for the same ticket id, id, which is included in SC, to get (id, π, π ′ )but never identified as a double-spender by the Identify(id, π, π ′ ) algorithm. The former casecorresponds to the existential unforgeability property of EPID in VeloCash ΠVC . We focus
on the latter case, which is further divided into three cases:
Case 1: Identify(id, π, π ′ ) =⊥This is the case that the adversary’s secret key is not extractable from the double-spendingtickets.
Suppose there exists

such that (x, com, ch, resp)(5.36)V(x, com, ch, resp) = V(x, com, ch′ , resp′ )(5.37)

 (x, com, ch′ , resp′ )= 1.

Since KeyExtractor algorithm in VeloCash compute the secret key f by the following equation:f=sf − s′f.
c − c′(5.38)The probability that KeyExtractor can not output the secret key f is equal to the probability of being ch = ch′ in (x, com, ch, resp) and (x, com, ch′ , resp′ ). In order to be verified

88

CHAPTER 5. VELOCASH

correctly, the two challenges ch, ch′ have to be computed, that is, c and c′ in the EPID
signatures have to be computed by the following equations:c = Hash gpk, B, K, T, R1 , R2 , (addrj → addri , Hash(τpre )) ,′′c = Hash gpk, B, K, T, R1 , R2 , (addrj → addri , Hash(τpre )) .

(5.39)The probability of c = c′ is upper bounded by the following inequality:

Pr [c = c′ ] + Pr [addri = addri′ ] < negl(λ)(5.40)

by the collision resistant property Hash functions. Note that addri and addri′ are hash of
randomly generated commitments (in the form of (x, com)) of honest recipients.
Case 2: (⊥, ΠG ) ← Identify(id, π, π ′ ) ∧VerifyGuilt((id, π), ΠG ) = 0 ∧ VerifyGuilt((id, π ′ ), ΠG ) = 0
This case does not happen unless B = 1. Even if the adversary make id = (x, com) =((B, K, T ), (R1 , R2 )) with B = 1, this case is eliminated by the construction of VeloCash since
the honest receiver does not accept the ticket as Verify algorithm fails by Equation (A.8).
Case 3: Identify(id, π, π ′ ) = (⊥, ΠG ∋ sk) ∧ sk ∈/ ULThis must be the case that the adversary succeeded to forge EPID secret key f . Since
the EPID’s unforgeability property, the probability of succeeding is negligibly small in the
security parameter λ.
Next, consider the case where the different sk′A (= f ′ ) is extracted in Equation (5.37),
that is, the same two com (= (R1 , R2 )) are created with different secret key f .
The following lemma states that, once VerifyGuilt outputs 1 on input one of the signature(idi , πi ) with ΠG for some honest user i, then it outputs 1 for the other signatures (id∗i , πi∗ )with ΠG of the same user i.

5.8. SECURITY ANALYSIS

89

Lemma 2. Let ΠG = Priv-RL. Let (idi , πi ) be the signatures of a user i. Then, for all honestuser i ∈ UL and for all signature (id∗i , πi∗ ) generated by i, the following holds:
VerifyGuilt((idi , πi ), ΠG ) = 1(5.41)⇒ VerifyGuilt((id∗i , πi∗ ), ΠG ) = 1
Proof. Given the condition of the lemma, the signature (idi , πi ) is signed by an honestuser i, hence correct. From the given condition VerifyGuilt((idi , πi ), ΠG ) = 1, we see thatc = Hash(gpk, B, K, T, R̂1 , R̂2 , m) in Equation (5.32) always holds. Therefore, we focus onwhether the last condition in Equation (5.32) holds. Let f be a part of the secret key ofthe user i which is used in signing the two signatures (idi , πi ) and (id∗i , πi∗ ). We consider thefollowing two cases:
Case 1: f ∈ ΠG (= Priv-RL)
VerifyGuilt((id∗i , πi∗ ), ΠG ) = 1 always holds.
Case 2: f ∈/ ΠG (= Priv-RL)
This must be the case that B, K and B ∗ , K ∗ in σ and σ ∗ respectively holds the relation
B f = K and B ∗f = K ∗ for the honest user’s secret key f ∈/ ΠG , But, in order to satisfy thecondition in Equation (5.41), there must exist some f ′ ∈ ΠG different form f ̸= f ′ satisfying′

B f = K.
Recall that B ̸= 1 is randomly chosen generator in G3 of prime order p. Therefore,′

B f = K and B f = K ⇒ f = f ′ .

(5.42)

This contradicts the assumption. Hence, the lemma.

Theorem 9. (Exculpability) The protocol of VeloCash, ΠVC is exculpable. More formally,

90

CHAPTER 5. VELOCASH

for all PPT adversaries A, there exists ∃ λ0 ∈ N such that for all security parameter λ ≥ λ0 ,
ΠVC satisfies the following inequality:


excul
AdvexculA,Π (λ) = Pr ExptA,Π (λ) = 1 < negl(λ).

(5.43)

Proof. (sketch) Assume that there exists a PPT adversary Aex that can win the exculpability
game and can output (id, π, ΠG ) such that VerifyGuilt((id, π), ΠG ) = 1. We show that A
can win the EPID’s anonymity game by using Aex ; however, this contradicts the anonymity
property of EPID stated in Theorem 5. Therefore, there is no Aex that wins the exculpability
game. See the detailed proof in Appendix C.

5.8.2

Anonymity properties

In this section, we verify that the protocol of VeloCash, ΠVC satisfies the anonymity properties.
Assumption 5 (INT-CTXT and IND-CPA). The symmetric-key authenticated encryption
scheme AE consists of three algorithms (Gen, Enc, Dec) where key generation algorithm Gen,
encryption algorithm Enc, and decryption algorithm Dec. AE is INT-CTXT and IND-CPA
secure, for all PPT adversaries A there exists a negligible function negl such that:
AdvINT-CTXT
(λ)
A,AE


INT-CTXT= Pr ExptA,AE(λ) = 1 < negl(λ),(5.44)

AdvIND-CPA
(λ)
A,AE


= Pr ExptIND-CPA(λ) = 1 < negl(λ)
A,AEA
where ExptINT-CTXT(λ) and ExptIND-CPA(λ) corresponds to INT-CTXTA
A,AE
A,AE
SE and IND-CPASE in

Bellare et al. [BN08], respectively.
From Assumption 5 and Bellare et al. [BN08], we see that the symmetric-key authenti-

5.8. SECURITY ANALYSIS

91

cated encryption scheme AE satisfies IND-CCA secure.

Theorem 10 (IND-CCA). From Theorem 3.1 of [BN08], symmetric-key authenticated encryption scheme AE is IND-CCA secure , if for all PPT adversaries A there exists a negligible
function negl such that:(λ) ≤AdvIND-CCA
A,AE(5.45)(λ) < negl(λ)(λ) + AdvIND-CPA
2 · AdvINT-CTXT
A,AE
A,AE
where the probability is taken over all randomness used in the experiment.

Theorem 11 (Coin anonymity (c-an)). For any ϵ0 > 0, the protocol of VeloCash, ΠVC
ϵ0satisfies coin anonymity if k0 < 2p
− 1 where k0 is the number of challenge users pergroup and p is the winning probability. More formally, for all PPT adversaries A, there
exists ∃ λ0 ∈ N such that for all security parameter λ ≥ λ0 , ΠVC satisfies the following
inequality:

Advc-anA,Π (λ) =




c-an
Pr Exptc-an< negl(λ).
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1(5.46)

Proof. Consider the case where k0 = 0, that is, the case of a single challenge user. The
adversary issues and spend the tickets such that




(0)
(0)
(0)
(0)
τb0 = AE.EncK(0) ϵ(0) → i0 , σA , σ
bA ,
0




(1)
(1)
(1)
(1)
τb0 = AE.EncK(1) ϵ(1) → i0 , σA , σbA(5.47)

0

(·)

(·)

(·)

where σA is the adversary’s EPID signature on the message ϵ(·) → i0 and σbA is theadversary’s EPID signature on the ciphertext AE.EncK(·) (·, ·).
0

92

CHAPTER 5. VELOCASH
(0)

(1)

Then, the challenge users i0 and i0 return the adversary the following tickets:
(0)
τb1 =

(1)
τb1 =

AE.EncK(0)1AE.EncK(1)
1





(0)

ϵ

(1)

ϵ

(0)
→ i0 , σA(1)→ i0 , σA

!
 

(0)
, i0 → A, σi(0) , σbi(0) ,
0

0

!
 

(1)
, i0 → A, σi(1) , σbi(1) .
0

(5.48)

0

The adversary can infer two partial messages as follows: m0 : (ϵ(0) → i(0) , ·), (i(0) → A, ·)
0

0

(1)

 m1 : (ϵ(1) → i(1)0 , ·), (i0 → A, ·)(5.49)

such that whose signature parts are hidden from the adversary. It is easy to see that theadversary who wins the IND-CCA game with such partially hidden messages can always win
the standard full message IND-CCA game. Thus, given the anonymity property of EPID
signatures, we can reduce the IND-CCA game of AE to the coin anonymity game.
The above argument holds regardless of the number of challenge users k0 ≥ 1. Thisconcludes the proof.

Open problem of Coin anonymity (c-an) If one of the challenge users wins and theticket is registered in the blockchain, that is when k0 ≥ σ2p0 − 1, the adversary can win thegame in the coin anonymity game. Since the adversary issued and know the escrow account,he can see the challenge user group from the plain-text winning ticket output by progw
registered in the blockchain. The reason for this is that the blockchain does not preserveanonymity. Thus, using a blockchain with anonymity, such as Confidential Transaction or
ZeroCash [BSCG+ 14] may solve the problem.

Theorem 12 (User anonymity (u-an)). The protocol of VeloCash, ΠVC satisfies user anonymity.
More formally, for all PPT adversaries A, there exists ∃ λ0 ∈ N such that for all security

5.8. SECURITY ANALYSIS

93

parameter λ ≥ λ0 , ΠVC satisfies the following inequality:
Advu-anA,Π (λ) =




u-an
< negl(λ).
Pr Exptu-an
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1(5.50)

Proof. Consider the case where k0 = 0, that is, the case of a single challenge user. The
adversary issues and spend the ticket such that


(b)
τb0 =




(b)
bA
AE.EncK0 ϵ → i0 , σA , σ(5.51)

where b ∈ {0, 1}. Then, the challenge user returns the following tickets to the adversary.
(b)
τb1 =

AE.EncK1(b)ϵ → i0 , σA

!
 

(b)
, i0 → A, σi(b) , σbi(b) .
0(5.52)

0

The adversary can infer two partial messages as follows: m0 : (ϵ(0) → i(0) , ·), (i(0) → A, ·)
0

0

(1)

 m1 : (ϵ(1) → i(1)0 , ·), (i0 → A, ·)(5.53)

such that whose signature parts are hidden from the adversary. Similar to the coin anonymity
game, it is easy to see that the adversary who wins the IND-CCA game with such partiallyhidden messages can always win the standard full message IND-CCA game. Thus, given
the anonymity property of the EPID signature, we can reduce IND-CCA of AE to the user
anonymity game. The above argument holds regardless of the number of challenge users
k0 ≥ 1. This concludes the proof.

Theorem 13 (coin transparency (c-tr)). The protocol of VeloCash, ΠVC satisfies cointransparency. More formally, for all PPT adversaries A, there exists ∃ λ0 ∈ N such that

94

CHAPTER 5. VELOCASH

for all security parameter λ ≥ λ0 , ΠVC satisfies the following inequality:
Advc-trA,Π (λ) =




c-tr
< negl(λ).
Pr Exptc-tr
A,Π,1 (λ) = 1 − Pr ExptA,Π,0 (λ) = 1(5.54)

Proof. The adversary receives the tickets as follows:τbn(0) =AE.EncKn−1





(0)
ϵ(0) → τ1 , σi(0) ,
0


(0)
(0)
τ1 → τ2 , σi(0) , · · · ,
1
!


(0)
in−1 → A, σi(0),σbi(0) ,n−1

τbn(1) =AE.EncKn−1




n−1


(1)
ϵ(1) → τ1 , σi(1) ,
0


(1)
(1)
τ1 → τ2 , σi(1) , · · · ,
1
!


(1)
in−1 → A, σi(1),σbi(1) .
n−1

n−1

(5.55)

5.8. SECURITY ANALYSIS

95
(0)

(0)

Next, the adversary sends to user in+1 and in+1 the following tickets respectively.
(0)τbn+1 =

AE.EncKn







τbn(1) =AE.EncKn

0

(0)
(0)
τ1 → τ2 , σi(0)1(0)

in−1 → A, σi(0)

n−1

(0)

A → in+1 , σA





(0)
ϵ(0) → τ1 , σi(0) ,






,··· ,
,
!

,σ
bA ,

(5.56)

(1)
ϵ(1) → τ1 , σi(1) ,
0


(1)
(1)
τ1 → τ2 , σi(1) , · · · ,
1


(1)
in−1 → A, σi(1) ,
n−1
!


(1)
A → in+1 , σA , σbA .

Then, the challenge user returns the following ticket to the adversary.
(b)τbn+k0 +1 =AE.EncKn+k0






(b)
ϵ(b) → τ1 , σi(b) ,
0


(b)
(b)
τ1 → τ2 , σi(b) , · · · ,
1


(b)
in−1 → A, σi(b) ,
n−1


(b)
A → in+1 , σA , · · · ,
!


(b)
in+k0 → A, σi(b)
,σ
bi(b)
n+k0

(5.57)

n+k0

where b ∈ {0, 1}. For the adversary, the n transactions until the adversary receives and96

CHAPTER 5. VELOCASH

signature parts of the returned ticket are hidden. Similar to the user anonymity and coinanonymity game, it is easy to see that the adversary who wins the IND-CCA game withsuch partially hidden messages can always win the standard full message IND-CCA game.
Thus, given the anonymity property of the EPID signature, we can reduce IND-CCA of AE
to the coin transparency game. This concludes the proof.
Interestingly, in the coin transparency game, the adversary can not win the game even if
the ticket is won among the challenge users. This is because the adversary does not issue thetickets and does not know the escrow accounts. Hence, the adversary has no clue to decide
the group of challenge users even from the plain-text tickets registered in the blockchain.
Even if the adversary breaks the tamper-proof wallet, or if the winning ticket is registeredin the blockchain and a series of transactions become known in plain text, the plain text
reveals only temporary hashed values of (x, com) for each transaction and an anonymous
EPID signature.

5.8.3

Double-spending attacks Detection Methods

For double-spending attacks, the attack can be detected perfectly. Furthermore, the adversary can not profit unless the cost of destroying the hardware exceeds the maximum
expected utility that he can obtain.
To achieve both Fork and Collision detection methods, two or more thickets must be
given, and the series of transactions from the escrow account must be referenceable.
Definition 21 (Conditions of Detection methods). Given two series of transactions τ andτ̃ . Fork and Collision Detection is achieved if and only if it satisfies the following conditions:
1. By τ and τ̃ , a series of transactions from the escrow account ϵ are referenceable.
2. If the attack is detected, the adversary’s secret key is extracted and placed on the secretkey based revocation list. Thus, the adversary will not be able to transact with honest
users.

5.8. SECURITY ANALYSIS

97

Theorem 14 (Fork and Collision Detection). Our anonymous transfer scheme achieves
Fork and Collision detection scheme perfectly.

Proof. Assume there exists forked ticket τ and τ̃ . Consider the fork detection. Let τ be theeligible ticket and registered in the blockchain, and let τ̃ be the received ticket and stored in
the wallet’s progw . By comparing τ and τ̃ , the wallet can figure out the adversary’s addressfrom the forked point. Consider the Collision detection. When the wallet receives τ and τ̃ ,it can extract the adversary’s address by the fork detection and KeyExtractor.

Theorem 15. Given two series of transactions τ and τ̃ such that (τ, τ̃ ) ∈ Fork, the doublespender’s secret key can be extractable.

Proof. Given the two transactions τ = {ϵ ≺ τ1 ≺ · · · ≺ τn } and τ̃ = {ϵ̃ ≺ τ̃1 ≺ · · · ≺ τ̃n′ }such as (τ, τ̃ ) ∈ Fork and Theorem 2, we can obtain the double-spending transactions.
The EPID signatures of the double-spending transactions consist of the same (x, com) anddifferent ch, resp respectively since the honest user’s AESP chooses different rid with highprobability, as follows:(x, com, ch, resp)






= ({B, K, T }, {R1 , R2 }, c, {sx , sf , sa , sb })(x, com, ch′ , resp′ )






= ({B, K, T }, {R1 , R2 }, c′ , {s′x , s′f , s′a , s′b }).

(5.58)

From Lemma 1, the double-spender’s secret key can be extractable.

Once the adversary’s address is detected from the forked point, the wallet sends τ and τ̃to the EPID revocation manager R. Then, R registers the adversary’s secret key into the
EPID’s secret key based revocation list Priv-RL.

98

CHAPTER 5. VELOCASH

5.9

Efficiency analysis

In this section, we present the size of each object in our proposed VeloCash and its comparison
with Bauer et al. [BFQ21] in Table 5.1.
The setting for cyclic groups G1 , G2 and G3 and other elements are same as in Appendix A. Note that in Bauer et. [BFQ21] G1 , G2 should be cyclic groups chosen that
Symmetric External Diffie-Hellman assumption (SXDH) holds. On the other hand, in our
VeloCash, G1 , G2 should be the groups that q-Strong Diffie-Hellman (q-SDH) assumption
holds, and G3 should be the group that decisional Diffie-Hellman assumption holds.
Since our VeloCash is a decentralized scheme and there is no online and trusted party
Bank as in [BFQ21], we still need to trust to some extent, the tamper-proof device manufacturer, which is also EPID’s group manager. Therefore, we compare skB and pkB with isk
and gpk, respectively.
At first glance, the ticket size (coin size) of Bauer et al. [BFQ21] appears much larger
than of VeloCash. This is because VeloCash is based on the stronger assumption (but widelyused in industry), such as the existence of tamper-proof devices, whereas [BFQ21] is based
purely on cryptographic assumptions.

Keys

Tickets (Coins)

Bauer et al. [BFQ21]
skB
9|Zp | + 2|G1 | + 2|G2 |pkB
15|G1 | + 8|G2 |skU|Zp | + 2|G1 | + 2|G2 |
pkU
|G1 |
Πguilt 2|G1 |cbstrap 6|Zp | + 147|G1 | + 125|G2 |cstd
54|G1 | + 50|G2 |VeloCashisk |Z∗p |gpk 3|G1 | + 2|G2 | + |G3 |3|Zp | + |G1 |0|Zp |5|Zp | + |G1 | + 2|G3 |7|Zp | + |G1 | + 2|G3 |Table 5.1: A efficiency comparison between our VeloCash and Bauer et al. [BFQ21]. The
coin’s size is |cbstrap | + k|cstd | after k transfers.

5.10. CONCLUSION

5.10

99

Conclusion

In this chapter, we have proposed VeloCash, transferable decentralized probabilistic micropayments which preserve anonymity. For the construction of VeloCash, we utilized a tamperproof wallet consisting of AESP. To achieve double-spending attack detection and preserveanonymity, we add extensions to AESP that allow for randomness tape and requesting EPID
signatures from prog to Gatt .
As discussed in Section 5.8, VeloCash satisfies the u-an property only for the bounded
number of challenge users. This pitfall stems from the fact that blockchain accounts are
not blinded. Constructing probabilistic anonymous micropayments with transferability thatsatisfies the anonymity notion in full is left as an open problem.

100

CHAPTER 5. VELOCASH

Chapter 6
Conclusions
In this thesis, we have proposed solutions to three of the blockchain’s biggest challenges:
Fast payments, High Throughput and Anonymity with Transparency.

Secure Offline Payments in Bitcoin We have achieved a secure fast payments on Bitcoin. Double-spending attacks on fast payments are one of the fatal architectural problems
in Cryptocurrencies. The prior study proposed an offline fast payment scheme that relies ontamper-proof wallets produced by trustworthy manufacturers. With the wallets, the payee
can immediately trust the transactions generated by the wallets without waiting for theirregistration to the blockchain. The prior study required an online trusted timestamp server
or, without one, usability was sacrificed. In contrast, our proposed method does not need
any trusted timestamp server, nor does it sacrifices usability.

Decentralized Probabilistic Micropayments with Transferability We have proposed Decentralized Probabilistic Micropayments with Transferability that allows ticket
distribution among users. As a result, the aggregation of the transactions increases thethroughput of the blockchain, making it possible to realize micropayments. For example, a$1 payment can be made for 10 cent fee.
We have proposed a scheme with a tamper-proof assumption. By proposing a detection
101

102

CHAPTER 6. CONCLUSIONS

method that perfectly detects the double-spending attacks and a detection method thatplaces an upper bound on the expected value of the attack, we forced the adversary to weighthe cost of breaking the tamper-proof hardware against the maximum expected value gained
from the attack.

VeloCash: Anonymous Decentralized Probabilistic Micropayments with Transferability We have achieved anonymity in the transferable decentralized probabilistic micropayments. Micropayments are one of the challenges in cryptocurrencies. Micropaymentson the blockchain have the problem that the fee is high for the transfer amount. As acountermeasure, a method called Layer-two has been proposed to consolidate transactions
outside the blockchain and improve the blockchain’s throughput. As one of the existing
Layer-two schemes, Decentralized Probabilistic Micropayments have been proposed. The
winning amount is registered in the blockchain, and the lottery tickets are issued to be won
with probability p, which allows us to aggregate approximately 1/p transactions into one.
Unfortunately, existing solutions do not allow for ticket transferability, and the smaller p,
the more difficult it is to use them in the real world. Here we have proposed VeloCash, Decentralized Probabilistic Micropayments with Transferability, which preserves Anonymity.
By introducing tamper-proof assumptions for sending and receiving the tickets, we make p
smaller. As a tamper-proof hardware assumption, VeloCash uses Attested Execution Secure
Processors, a formal abstraction of secure processors with attested execution functionality
and Direct Anonymous Attestation to achieve anonymity for sending and receiving tickets.
VeloCash can detect double-spending attacks perfectly and revoke the adversary’s device.

Appendix A
Construction of EPID
There are four types of entities in EPID: an issuer I, a revocation manager R, platformer
P, and verifiers V. EPID consists of the five algorithms:
ΠEPID = {Setup, Join, Sign, Verify, Revoke} .

A.0.1

Setup

Given 1k , issuer I chooses a group pair (G1 , G2 ) of prime order p and let e : G1 × G2 → GT
be a bilinear map function, and a cyclic group G3 of order p where the decisional DiffieHellman problem is hard. Let g1 , g2 , g3 be the generators of G1 , G2 , G3 respectively. I
chooses h1 , h2 ← G1 , γ ← Z∗p , and ω := g2γ . This algorithm outputs(gpk, isk) = ((p, G1 , G2 , G3 , g1 , g2 , g3 , h1 , h2 , w), γ) .

A.0.2

Join

The Join protocol is performed interactively between issuer I and platformer P. The flow
is described in Figure A.1.
I has (gpk, isk) and P takes gpk. Finally, P obtains sk = ((A, x, y), f ) where f is a
103

104

APPENDIX A. CONSTRUCTION OF EPID
Issuer I

Platformer P

f ← Zpy ′ ← Zp′
T = hf1 · hy2

1. T
x ← Zpy ′′ ← Zp′′

1

A = (g1 T hy2 ) x+γ

2. A, x, y ′′y = y ′ + y ′′ mod p
Verify:e(A, ω · g2x ) = e(g1 hf1 hy2 , g2 )Output:sk = ((A, x, y), f )Figure A.1: EPID’s Join protocol
unique membership key and (A, x, y) is a BBS+ signature [ASM06] on f .

A.0.3

Sign

Platformer P inputs gpk, sk := ((A, x, y), f ) , m ∈ {0, 1}∗ , and a signature based revocation
list Sig-RL, then outputs the signature σ as follows:

1. Chooses B ← G3 such that B ̸= 1 and computes
K := B f(A.1)

b := y + ax, T := A · ha2(A.2)

rx ← Zp , rf ← Zp , ra ← Zp , rb ← Zp

(A.3)

2. Chooses a ← Zp and computes

3. It randomly picks

105
4. Computes
R1 := B rf
(A.4)
R2 := e (T, g2 )

−rx

rb

rf

ra

· e (h1 , g2 ) · e (h2 , g2 ) · e (h2 , ω)

5. Computesc = Hash(gpk, B, K, T, R1 , R2 , m)

(A.5)

sx = rx + c · x, sf = rf + c · f,

(A.6)

6. Computes

sa = ra + c · a, sb = rb + c · b
7. Sets σ0 := (B, K, T, c, sx , sf , sa , sb )Then, P verifies the above output values satisfy the following signature of knowledge protocol
as follows:
SPK (x, f, a, b) : B f = K∧e (T, g2 )−x · e (h1 , g2 )f · e (h2 , g2 )b · e (h2 , w)a(A.7)= e(T, ω)/e(g1 , g2 ) (m)A.0.4

VerifyVerifier V inputs gpk, m, a secret key based revocation list Priv-RL, a signature-key based
revocation list Sig-RL, and a signature σ, then verifies the signature as follows:

1. Let σ = (σ0 , σ1 , . . . , σn2 ),where σ0 = (B, K, T, c, sx , sf , sa , sb )2. Verifies?

B, K ∈ G3 and B ̸= 1,?

?

T ∈ G1 , sx , sf , sa , sb ∈ Zp

(A.8)

106

APPENDIX A. CONSTRUCTION OF EPID

3. Computes
R̂1 = B sf · K −c
R̂2 = e (T, g2 )−sx · e (h1 , g2 )sf · e (h2 , g2 )sb(A.9)· e (h2 , ω)sa · (e(g1 , g2 )/e(T, ω))c
4. Verifies?
c = H gpk, B, K, T, R̂1 , R̂2 , m(A.10)?

5. Let Priv-RL = {f1 , . . . , fn1 } . For i = 1, . . . , n1 , it checks that K ̸= B fi
6. Let Sig-RL = {(B1 , K1 ), . . . , (Bn2 , Kn2 )}. For i = 1, . . . , n2 , it verifies that σi is a valid
zero-knowledge proof,noff
SPK (f ) : K = B ∧ Ki ̸= Bi (m).

A.0.5

(A.11)

RevokeSecret key based revocation
Given gpk, Priv-RL, and sk = (A, x, y, f ) to be revoked, revocation manager R updates
Priv-RL as follows:
1. verify the correctness of sk,e(A, g2x ω) = e(g1 hf1 hy2 , g2 )(A.12)

2. appends f in σ0 to Sig-RL
Signature based revocation
Given gpk, Priv-RL, Sig-RL, m, and σ to be revoked, revocation manager R updates Sig-RL
as follows:107
1. checks
Verify(gpk, m, Priv-RL, ∅, σ0 ) = valid
2. appends (B, K) in σ0 to Sig-RL(A.13)

108

APPENDIX A. CONSTRUCTION OF EPID

Appendix B
Security Definition of EPID
An EPID scheme is secure if it satisfies the following three requirements: correctness,anonymity, unforgeability [BCC04, BL10].
The correctness requires that every signature generated by a platform is valid except
when the platform is revoked by the secret key based revocation or the signature based
revocation.
Definition 22. (Correctness) An EPID scheme is correct, for every probabilistic polynomialtime adversary A, if it satisfies the following equation: σ ← Sign(gpk, sk, m, Sig-RL), Verify (gpk, m, Priv-RL, Sig-RL, σ) = valid

where

P

(B.1)

P
⇐⇒ (ski ∈/ Priv-RL) ∧ ( i ∩ Sig-RL = 0 )i is the set of all signatures generated by the platform Pi .

Theorem 16. (Theorem 4 of [BL09]) The EPID scheme is correct.
In the anonymity game, the adversary’s goal is to determine which one of two secret keys
were used in generating the signature. The anonymity game between a challenger and an
adversary A is described in Figure B.1.
109

110

APPENDIX B. SECURITY DEFINITION OF EPID

Definition 23. (Anonymous) An EPID scheme is anonymous, if for every probabilistic
polynomial-time adversary A, the advantage in winning the anonymity game between a challenger is negligible as follows:(λ) =AdvAnonA(λ) = 1 − 1 < negl(λ)
2 · Pr ExptAnon
A

(B.2)

Theorem 17. (Theorem 5 of [BL09]) An EPID scheme is anonymous in the random oracle
model under the decisional Diffie-Hellman assumption in G3 .
Note that the adversary A can not make corrupt queries on the challenge users i0 andi1 .
We say that the EPID scheme is unforgeable if no adversary can win the unforgeability
game described in Figure B.1. In the unforgeability game, the adversary’s goal is to forge avalid signature, given that all secret keys known to the adversary have been revoked.
Definition 24. (Unforgeability) An EPID scheme is unforgeable, if for every probabilistic
polynomial-time adversary A, the advantage in winning the unforgeability game between achallenger is negligible as follows:
AdvUnforg
(λ) =
A
h
i
UnforgPr ExptA (λ) = 1 < negl(λ)(B.3)

Theorem 18. (Theorem 6 of [BL09]) The EPID scheme is unforgeable in the random oracle
model under the strong Diffie-Hellman assumption in (G1 , G2 ).

111

Experiment: ExptAnon
(λ)
A
1:
2:

3:
4:

(gpk, isk) ← A(1λ )(state, i0 , i1 , m)
← AOIssue (·),OJoin (·),OSign (gpk,Sig-RL,·,·),OCorrupt (·) (gpk)b ←$ {0, 1}
σ ← Sign(gpk, skib , m, Sig-RL)

6:b′ ← AOJoin (·),OSign (gpk,Sig-RL,·,·),OCorrupt (·) (state, σ)
if b = b′ , return 1

7:else return 0

5:

Experiment: ExptUnforg
(λ)
A
2:

(gpk, isk) ← Setup(1λ )(Priv-RL∗ , Sig-RL∗ , σ ∗ , m∗ )3:

← AOIssue (·),OJoin (·),OSign (gpk,Sig-RL,·,·),OCorrupt (·) (gpk)
return 1 if all of the following conditions hold:1:1) Verify(gpk, Priv-RL∗ , Sig-RL∗ , σ ∗ , m∗ ) = 1,

4:∧ 2) ∀ i ∈ U, ski ∈ Priv-RL∗ or ∃ σi ∈ Sig-RL∗ ,∧ 3) A did not obtain σ ∗ by making a sign query on m∗else return 0

Oracle: OJoin (i)Oracle: OSign (gpk, Sig-RL, i, m)

Oracle: OCorrupt (i)

1:

1:

1:

2:

if i ∈U
U ← U ∪ {i}2:generate ski

3:

4:

return 1

4:5:else return ⊥3:

if i ∈ Uσ ← Sign(gpk, ski , m, Sig-RL)
return σelse return ⊥2:
3:

if i ∈ U
return ski
else return ⊥Figure B.1: EPID game for Anonymity and Unforgeability

112

APPENDIX B. SECURITY DEFINITION OF EPID

Appendix C

Proof of Theorem 9

To prove exculpability property stated in Theorem 9, we assume there exists a PPT adversary
Aex that wins the exculpability game defined in Definition 15 with non-negligible probability,
namely, that outputs (id, π, ΠG ) such that VerifyGuilt((id, π), ΠG ) = 1.

We will show a reduction that we can construct a PPT adversary A which wins the
EPID anonymity game defined in Definition 23 with non-negligible probability provided
oracle access to Aex is available.
In order to share the same user list between A and Aex , we will not allow Aex access toJoin; instead, A provide a sufficiently long list of users (i1 , . . . , in ) created by A and provide
the list of users to Aex . Note that this modification to the exculpability game does not affectthe success probability of Aex .
In the reduction, A generates the parameter param and skB , and it joins n users andcreates the list of users (i1 , . . . , in ). Then, Aex is executed with input (param, skB , (i1 , . . . , in )),
113

114

APPENDIX C. PROOF OF THEOREM 9

and it outputs (id, π, ΠG ) with non-negligible probability as follows:param ← ParamGen(1λ ); skB ← A(param)(i1 , · · · , in ) ← AOJoin (·)
Spy,UWith,Rcv,S&R,Depo(id, π, ΠG ) ← Aex(param, skB , (i1 , . . . , in ))such that VerifyGuilt((id, π), ΠG ) = 1

Note that the accused double-spender i∗ is contained in the user list (i1 , . . . , in ). Otherwise, given VerifyGuilt((id, π), ΠG ) = 1, Aex must win the unforgeability game in Figure 5.2,
and it contradicts with Theorem 8.
Then, we can easily find out the user i∗ who created the signature (id, π) by iteratively ask all honest users to produce signatures for a message in a form of randomly
chosen commitment, namely, m = (x, com). That is, for i∗ ∈ {i1 , · · · , in }, A queries toOSign (gpk, ski∗ , m, Sig-RL) and gets σij . By Lemma 2, there must exist i∗ ∈ (i1 , . . . , in ) suchthat VerifyGuilt ((m, σi∗ ), ΠG ) = 1. Then, A randomly chooses i¯∗ ∈ {i1 , . . . , in } \ {i∗ }. A
outputs (ΠG , i∗ , i¯∗ , m).
At step 5 in the Anonymity Game defined in Figure 5.3, A outputs b′ = 0 if
VerifyGuilt ((m, σ), ΠG ) = 1(C.1)

otherwise b′ = 1.
By Lemma 2, the adversary A wins the Anonymity Game with non-negligible probability if there exists Aex which wins the Excupability Game defined in Figure 5.3 with
non-negligible probability. This contradicts the anonymity property of EPID stated in Theorem 5, and this reduction is tight. Therefore, there is no Aex that wins the exculpability
game with non-negligible probability.

Bibliography[ABC20]Ghada Almashaqbeh, Allison Bishop, and Justin Cappos. MicroCash: Practical Concurrent Processing of Micropayments. In Financial Cryptography andData Security - FC 2020, Lecture Notes in Computer Science, pages 227–244.
Springer International Publishing, 2020.

[ASM06]

Man Ho Au, Willy Susilo, and Yi Mu. Constant-Size Dynamic k-TAA. In
Security and Cryptography for Networks, Lecture Notes in Computer Science,
pages 111–125, Berlin, Heidelberg, 2006. Springer.

[BBBF18]

Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable Delay Functions. In Advances in Cryptology – CRYPTO 2018, Lecture Notes in
Computer Science, pages 757–788. Springer International Publishing, 2018.

[BCC04]

Ernie Brickell, Jan Camenisch, and Liqun Chen. Direct anonymous attestation.
In Proceedings of the 11th ACM conference on Computer and communications
security, CCS ’04, pages 132–145. Association for Computing Machinery, October 2004.

[BCFK15]

Foteini Baldimtsi, Melissa Chase, Georg Fuchsbauer, and Markulf Kohlweiss.
Anonymous Transferable E-Cash. In Public-Key Cryptography – PKC 2015,
Lecture Notes in Computer Science, pages 101–124, Berlin, Heidelberg, 2015.
Springer.
115

116[BCL09]BIBLIOGRAPHY
Ernie Brickell, Liqun Chen, and Jiangtao Li. Simplified security notions of direct anonymous attestation and a concrete scheme from pairings. International
Journal of Information Security, 8(5):315–330, 2009.

[BFQ21]

Balthazar Bauer, Georg Fuchsbauer, and Chen Qian. Transferable E-Cash: A
Cleaner Model and the First Practical Instantiation. In Public-Key Cryptography – PKC 2021, Lecture Notes in Computer Science, pages 559–590. Springer
International Publishing, 2021.

[BL09]

Ernie Brickell and Jiangtao Li. Enhanced Privacy ID from Bilinear Pairing.
Technical Report 095, 2009. http://eprint.iacr.org/2009/095.

[BL10]

Ernie Brickell and Jiangtao Li. Enhanced Privacy ID from Bilinear Pairing for
Hardware Authentication and Attestation. In 2010 IEEE Second International
Conference on Social Computing, 2010.

[BL12]

Ernie Brickell and Jiangtao Li. Enhanced Privacy ID: A Direct Anonymous Attestation Scheme with Enhanced Revocation Capabilities. IEEE Transactions
on Dependable and Secure Computing, 2012.

[BMW03]Mihir Bellare, Daniele Micciancio, and Bogdan Warinschi. Foundations ofgroup signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In Proceedings of the 22nd international
conference on Theory and applications of cryptographic techniques, EUROCRYPT’03, pages 614–629, Berlin, Heidelberg, May 2003. Springer-Verlag.

[BN08]

Mihir Bellare and Chanathip Namprempre. Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm.
Journal of Cryptology, 21(4):469–491, October 2008.

[BSCG+ 14] Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian
Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous

BIBLIOGRAPHY

117

Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy,
pages 459–474, May 2014. ISSN: 2375-1207.
[CG08]

Sébastien Canard and Aline Gouget. Anonymity in Transferable E-cash. In Applied Cryptography and Network Security, volume 5037, pages 207–223, Berlin,
Heidelberg, 2008. Springer. Series Title: Lecture Notes in Computer Science.

[CGL+ 17]

Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian Miers,
and Pratyush Mishra. Decentralized Anonymous Micropayments. In Advancesin Cryptology – EUROCRYPT 2017, Lecture Notes in Computer Science, pages
609–642. Springer, 2017.

[CGT08]Sébastien Canard, Aline Gouget, and Jacques Traoré. Improvement of Efficiency in (Unconditional) Anonymous Transferable E-Cash. In Financial Cryptography and Data Security, volume 5143, pages 202–214, Berlin, Heidelberg,
2008. Springer. ISSN: 0302-9743, 1611-3349 Series Title: Lecture Notes in
Computer Science.

[Che10]Liqun Chen. A DAA Scheme Using Batch Proof and Verification. In Trust andTrustworthy Computing, Lecture Notes in Computer Science, pages 166–180,
Berlin, Heidelberg, 2010. Springer.

[Cora]

Intel Corporation. A Cost-Effective Foundation for End-to-End IoT Security. https://www.intel.com/content/dam/www/public/us/en/documents/
white-papers/intel-epid-white-paper.pdf.

(accessed February 24th,2022).
[Corb]

Intel Corporation.
ogy.

Intel Enhanced Privacy ID (EPID) Security Technol-

https://www.intel.com/content/www/us/en/developer/articles/

technical/intel-enhanced-privacy-id-epid-security-technology.
html. (accessed February 24th, 2022).

118[CP93]

BIBLIOGRAPHYDavid Chaum and Torben Pryds Pedersen. Transferred Cash Grows in Size.
In Advances in Cryptology — EUROCRYPT’92, Lecture Notes in Computer
Science, pages 390–407, Berlin, Heidelberg, 1993. Springer.

[CPS10]Liqun Chen, Dan Page, and Nigel P. Smart. On the Design and Implementationof an Efficient DAA Scheme. In Smart Card Research and Advanced Application, Lecture Notes in Computer Science, pages 223–237. Springer, 2010.

[CZK+ 19]

Raymond Cheng, Fan Zhang, Jernej Kos, Warren He, Nicholas Hynes, NoahJohnson, Ari Juels, Andrew Miller, and Dawn Song. Ekiden: A Platform for
Confidentiality-Preserving, Trustworthy, and Performant Smart Contracts. In
2019 IEEE European Symposium on Security and Privacy (EuroS&P), pages
185–200, June 2019.

[Dam99]Ivan Damgård. Commitment Schemes and Zero-Knowledge Protocols. In Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer
School, Aarhus, Denmark, July 1998, pages 63–86, Berlin, Heidelberg, 1999.
Springer-Verlag.

[DNY17]Alexandra Dmitrienko, David Noack, and Moti Yung. Secure Wallet-Assisted
Offline Bitcoin Payments with Double-Spender Revocation. In Proceedings ofthe 2017 ACM on Asia Conference on Computer and Communications Security,
ASIA CCS ’17. Association for Computing Machinery, 2017.

[DPS19]Phil Daian, Rafael Pass, and Elaine Shi. Snow White: Robustly Reconfigurable
Consensus and Applications to Provably Secure Proof of Stake. In Financial
Cryptography and Data Security, Lecture Notes in Computer Science, pages
23–41. Springer International Publishing, 2019.

BIBLIOGRAPHY[Fis05]

119

Marc Fischlin. Communication-Efficient Non-interactive Proofs of Knowledge
with Online Extractors. In Advances in Cryptology – CRYPTO 2005, Lecture
Notes in Computer Science, pages 152–168, Berlin, Heidelberg, 2005. Springer.

[FS87]

Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to
Identification and Signature Problems. In Advances in Cryptology — CRYPTO’86, Lecture Notes in Computer Science, pages 186–194, Berlin, Heidelberg,
1987. Springer.

[FS07]

Eiichiro Fujisaki and Koutarou Suzuki. Traceable Ring Signature. In Public
Key Cryptography – PKC 2007, Lecture Notes in Computer Science, pages
181–200, Berlin, Heidelberg, 2007. Springer.

[Fuj11]

Eiichiro Fujisaki. Sub-linear Size Traceable Ring Signatures without Random
Oracles. In Topics in Cryptology – CT-RSA 2011, Lecture Notes in Computer
Science, pages 393–415, Berlin, Heidelberg, 2011. Springer.

[GHS11]

Jie Guo, Lin Hao, and Huimin Sun. A new DAA scheme from one-off public
key. In 2011 International Conference on Electronics, Communications andControl (ICECC), pages 646–649, 2011.

[GKL15]

Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The Bitcoin Backbone Protocol: Analysis and Applications. In Advances in Cryptology - EUROCRYPT
2015, Lecture Notes in Computer Science, pages 281–310, Berlin, Heidelberg,
2015. Springer.

[GMSR+ 20] Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, andArthur Gervais. SoK: Layer-Two Blockchain Protocols. In Financial Cryptography and Data Security, Lecture Notes in Computer Science, pages 201–226.
Springer International Publishing, 2020.

120[KAC12]

BIBLIOGRAPHY
Ghassan O. Karame, Elli Androulaki, and Srdjan Capkun. Double-spending
fast payments in bitcoin. In Proceedings of the 2012 ACM conference on Computer and communications security - CCS 2012, pages 906–917, New York, NY,
USA, 2012. Association for Computing Machinery.

[KRDO17]

Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.
Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In Advances in Cryptology – CRYPTO 2017, Lecture Notes in Computer Science,
pages 357–388. Springer International Publishing, 2017.

[LNE+ 19]

Joshua Lind, Oded Naor, Ittay Eyal, Florian Kelbert, Emin Gün Sirer, andPeter Pietzuch.

Teechain: a secure payment network with asynchronous

blockchain access. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, pages 63–79, New York, NY, USA, 2019.
Association for Computing Machinery.
[MBB+ 19]

Andrew Miller, Iddo Bentov, Surya Bakshi, Ranjit Kumaresan, and Patrick
McCorry. Sprites and State Channels: Payment Networks that Go Faster Than
Lightning. In Financial Cryptography and Data Security, Lecture Notes in
Computer Science, pages 508–526. Springer International Publishing, 2019.

[Nak09]Satoshi Nakamoto. Bitcoin : A peer-to-peer electronic cash system. 2009.

[OO92]

Tatsuaki Okamoto and Kazuo Ohta. Universal Electronic Cash. In Advances in
Cryptology — CRYPTO’91, Lecture Notes in Computer Science, pages 324–337,
Berlin, Heidelberg, 1992. Springer.

[PS96]David Pointcheval and Jacques Stern. Security Proofs for Signature Schemes.
In Advances in Cryptology — EUROCRYPT ’96, Lecture Notes in Computer
Science, pages 387–398, Berlin, Heidelberg, 1996. Springer.

BIBLIOGRAPHY[Ps15]

121

Rafael Pass and abhi shelat. Micropayments for Decentralized Currencies. In
Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, pages 207–218, New York, NY, USA, 2015.
Association for Computing Machinery.

[PSS17]

Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the Blockchain Protocol in Asynchronous Networks. In Advances in Cryptology – EUROCRYPT
2017, Lecture Notes in Computer Science, pages 643–673, Cham, 2017. Springer
International Publishing.

[PST17]

Rafael Pass, Elaine Shi, and Florian Tramèr. Formal Abstractions for Attested
Execution Secure Processors. In Advances in Cryptology – EUROCRYPT, Lecture Notes in Computer Science. Springer International Publishing, 2017.

[Rab83]

Michael O. Rabin. Transaction protection by beacons. Journal of Computerand System Sciences, 27(2):256–267, October 1983.

[Riv97]

Ronald L. Rivest. Electronic lottery tickets as micropayments. In Financial
Cryptography, Lecture Notes in Computer Science, pages 307–314, Berlin, Heidelberg, 1997. Springer.

[SRC15]

Ben Smyth, Mark D. Ryan, and Liqun Chen. Formal analysis of privacy inDirect Anonymous Attestation schemes. Science of Computer Programming,
111:300–317, 2015.

[THO22]

Taisei Takahashi, Taishi Higuchi, and Akira Otsuka. VeloCash: Anonymous
Decentralized Probabilistic Micropayments with Transferability. IEEE Access,2022.

[TO20]Taisei Takahashi and Akira Otsuka. Short Paper: Secure Offline Payments
in Bitcoin. In Workshop on Trusted Smart Contracts In Association with Fi-

122

BIBLIOGRAPHY
nancial Cryptography and Data Security, Lecture Notes in Computer Science,
pages 12–20, Cham, 2020. Springer International Publishing.

[TO21]Taisei Takahashi and Akira Otsuka. Probabilistic Micropayments with Transferability. In Computer Security – ESORICS 2021, Lecture Notes in Computer
Science, pages 390–406, Cham, 2021. Springer International Publishing.

[Whe97]David Wheeler. Transactions using bets. In Security Protocols, Lecture Notes
in Computer Science, pages 89–92, Berlin, Heidelberg, 1997. Springer.

[Woo]

Dr Gavin Wood. ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER. https://gavwood.com/paper.pdf.

[YCH]

YCHARTS.

Bitcoin Average Transaction Fee.

https://ycharts.com/

indicators/bitcoin_average_transaction_fee. (accessed April 5th, 2022).