Short Paper: Secure Offline Payments in Bitcoin
Taisei Takahashi and Akira Otsuka
Institute of Information Security
Yokohama, Japan{mgs174503,otsuka}@iisec.ac.jp

Abstract. Double-spending attacks on fast payments are one of thefatal architectural problems in Cryptocurrencies. Dmitrienko et al. proposed an offline fast payment scheme that relies on tamper-proof wallets
produced by trustworthy manufacturers. With the wallets, the payee
can immediately trust the transactions generated by the wallets without
waiting for their registration to the blockchain. Secure coin-preloading to
the wallet is important, while illegal coin-preloading can cause over/doublespending by the trusted wallets. For this, they proposed an interesting
protocol that makes use of a fragment of the main blockchain to prove tothe wallets the legitimacy of preloaded coins. One drawback is that, in
proving that the fragment are from honest miners, their protocol requires
a trusted online time-stamp server so that the wallets can verify thetimestamps to see if the blocks in the fragment is mined with sufficiently
large amount of computing resources. Otherwise, it sacrifices usability.
In order to eliminate such an online trustee, in this paper we took the
opposite approach that the payee (not the wallets) verifies the legitimacy
of preloaded coins at the time of offline payment. As a consequence, ourresult shows that, with light-weight tamper-proof wallets, completely decentralized offline payment is possible without any modification to theexisting Bitcoin network.
Keywords: blockchain · offline payment · tamper-proof wallet.

1

Introduction

Double-spending attacks on fast payments [4] are the one of the fatal architectural problems in Cryptocurrencies. Double spending refers to the payment
where the same coin is spent 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 double-spending attacks on fast payment
assuming the security of tamper-proof wallet. Dmitrienko et al. [1] pointed outthat 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 [4]. Offline
immediate payments is long demanding in cryptocurrencies. In practice, without changing the ongoing systems, “fast payment” is widely used such that the2

Taisei Takahashi et al.

payee could accept the transaction immediately by checking the signature, andthe payer’s balance for confirming that the payer has enough money to spend.
Karame et al. [4] pointed out that, for such a fast payment scheme, doublespending attack is possible if a malicious payer makes use of the race conditionof the double-spending transactions that reach the payees with different timing in the peer-to-peer network. Dmitrienko proposed a solution for immediatepayment and offline payments that relies on tamper-proof wallets manufactured
by trustworthy manufacturer and deploys time-based transaction confirmation
verification mechanism. They make use of a fragment of the main blockchain toprove the legitimacy of preloaded coins to the wallets. Their scheme solved the
double-spending problem as Karame et al. suggested. The wallet loses their credibility if a malicious user succeeds to pre-load illegal coins by intention. Thus,
it is enormously important to establish secure coin preloading to the wallet. In
order to achieve this, Dmitrienko propose an interesting protocol that proves
the fact that a pre-loading payment to the wallet existed using a subchain, afragment of the main blockchain. They considered that a subchain is a part ofthe mainchain if and only if the total PoW to mine the blocks in the subchain isgreater than some predetermined lower-bound and the average time to produce
the subchain is less than some constant time period. Thus, to verify the proof
inside the tamper-proof wallet, it is necessary to measure the total computation time consumed to generate the subchain objectively. (A) A trivial solution
to this is to assume a trusted time-stamp server, which supplies a time-stamp
to a block everytime the corresponding block is created. (B) Another solution
proposed in [1] 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 the trusted time-stamp server requires the additional trusted third party. The construction (B) is decentralized,
but it sacrifices the usability to the great extent.
Other studies of interest include Teechan, an offline payment channel, proposed by Lind et al. [5]. It assumes tamper-proof wallets in both side and achievesoffline payments. However, it has to deposit some fund, which corresponds toour preloading, 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.
In the theoretical aspect, Juan Garay et al. [3] formulated the basic propertiesof the blockchain in Bitcoin [6] such as “common prefix” and “chain quality,” assuming that the hashing power of an adversary controlling a fractionof the parties is strictly less than 1/2. Further extensions are made for variabledifficulty [2], a security analysis in the “semi-synchronous” network model [7].
We propose a novel offline payment scheme alternative to the Dmitrienko’s
protocol. The advantage of our scheme is its fully decentralization, that is, itdoes not assume any external trusted time-stamp server. Further, we do notneed to set any expiration time to the pre-loaded coins.

2

Preliminaries– C: a blockchain.

Short Paper: Secure Offline Payments in Bitcoin

3– Bi : i-th block in C is a triple hhash(Bi−1 ), xi , noncei.
– τ : 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 et al. [3]. All players are bounded interactive turing machines and are allsynchronized and message are exchanged in a discrete time frame called round.
t,n{EXECΠ,A,Z(z)}z∈{0,1}∗ denotes the random variable ensemble that determines
the output of the environment Z on input z for a protocol Π with adversary A.
t,n
VIEWΠ,A,Z(z) denotes the concatenated view of all parties after the completiont,nof an execution EXECΠ,A,Z(z). A “flat” model is assumed where all parties
executes exactly q mining trials (hash queries) per round. Then, each mining
trials by various players are 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. [3] 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 . Then, we
have the followings.
Lemma 1. (Common-Prefix Lemma [3]) Assume a typical execution and consider two chains C1 and C2 such that len(C2 ) ≥ len(C1 ). If C1 is adopted by anhonest party at round r, and C2 is either adopted by an honest party or diffuseddk
dk
at round r, then C1 ≤ C2 and C2  C1 , for k ≥ 2ηκf .
Theorem 1. (Chain Growth Theorem [3]) Assume a typical execution, for anyt,nhonest party P with chain C in VIEWΠ,A,Z, it holds that for any s ≥ ηκ rounds
there are at least (1 − )f · s blocks added to the chain of P .

3

Secure Offline Bitcoin Payments

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

4

Taisei Takahashi et al.
Fig. 1. Coin Pre-loading protocol
Bitcoin Network
B

Payer X
bl , x, PKX , skX

Wallet W
balance, PKW , skW
1. w

2. τl
Confirm τl with Biw ← hash(PKW )τl ← Sign(skX ; x → w, bl )4. τl , τel

3. Bi

5. statusbalance ← bl
Store {τl , τel }Coin Preloading In the coin-preloading phase, the payer X requests a new
account w from the wallet (Step 1), then create the preloading transaction τltransferring bl bitcoins from her account x to w and commit it to the networks(Step 2). As soon as τl is verified and integrated into the Bitcoin network ina block, say Bi , X takes Bi (Step 3), and provides τl and the witness of themembership 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 preloadingfor every account w such that once an amount bl is preloaded to w, the wallet W
never accepts preloading transaction to w any more and only makes payments
while balance ≥ 0. It is not hard to extend it to multiple coin preloading.
Secure Offline Transaction In the offline transaction 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 balance by 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 createdwithin the tamper-proof wallet by signing with skT . The resulting τo , proof andcertT , a trustworthy vendor certificate, are sent to Y (Step 3). Y accepts thetransaction if τl is confirmed and τo is valid and issued by a tamper-proof wallet.
More formally, Y accepts τo and proof if and only ifcert T is trustworthyVerify(PKT ; proof) = 1
τo ∈ (VCY ∩ Sign(skW ; w → ·,bo ))τl ∈ Cdk ∩ Sign(·; · → w, bl )Y

If all checks succeed, Y stores τo , proof and replies to W with status (Step4).
Coin Redemption and Wallet Revocation When Y gets online, Y proceeds
to the coin redemption and wallet revocation phase. Y broadcasts τo to the Bit1
2

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

Short Paper: Secure Offline Payments in Bitcoin

5Fig. 2. Offline transaction protocol
Wallet W
balance, PKW , skW , skT ,{τl , τel }Payer Xx, PKX , skX , certT

Payee Yy, PKY , skY

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cert T is trustworthyVerify(PKT ; proof) = 1
·, bo )τo ∈ VCY ∩ Sign(skW ; w → dkτl ∈ CY ∩ Sign(·; · → w, bl )3. Sign(skY ; status)

Fig. 3. Coin redemption and double-spending wallet revocation protocol
Bitcoin Network
B

Payee Yτo , proof, P KY , skY

Manufacturer T
P KT , skT

1. τointegrate τo into B

2. C0Yif τo ∈
/ V 0dkCYτr ← Sign(skY ; proof, cancel τo )
3. τr

4. τT

T issuesτT = Sign(skT ; T → y, bo )after investigation of τr .

coin network in order to redeem the coins received from W (Step 1). Next, theBitcoin network verifies τo and integrates it to the blockchain. The payee Y observes the Bitcoin network and periodically updates its local chain C0Y reflecting
the newly mined blocks (Step 2). Y waits until τo is confirmed or τo becomes
invalid, τo ∈/ VC0Y . If τo is invalid, Y initiates revocation by creating a revocationtransaction τr = Sign(skY ; proof, cancel τo ) and send it to the Manufacturer T(Step 3). T investigate τr and in order to compensate Y for the damage of bo ,issues τT then committed to the Bitcoin network (Step 4).

6

4

Taisei Takahashi et al.

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 a set of all possible valid transactions with respect toC such that
VC = {τ | τ is valid with respect to C}.
valid transactions are correctly formed and not over-spent more than thebalance of the payer’s account as far as regarding the given blockchain C as the
mainchain. Once valid transactions are broadcasted to Bitcoin network by peers,
they may be integrated into the mainchain if the given chain C is shared byhonest miners, and thus the transaction is valid for those honest miners. Notethat this is not guaranteed. Because the given chain C may contradicts with thelocalchains of other honest miners. Furthermore, the set of valid transactions willchange 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 , thatis, τ ∈ 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 thatC  CX for all X ∈ H. where  is a prefix relation [3]. 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 proofof a form Sign(skT ; τo , τl ) with respect to a localchain C if and only ifcert T is issued by a trustworthy provider





Verify(PKT ; proof) = 1τ is a transaction of a form Sign(sk ; w → ·, b )
o
W
o
(1)

τ
is
a
transaction
of
a
form
Sign(·;
·
→
w,
b
)
l
l





τo ∈ VCτl ∈ Cdk
3

Dmitrienko [1] have introduced a slightly different term CheckSyntaxT for transaction
validation. CheckSyntaxT refers to the syntactical conformance of transactions to therequirements in the blockchain. On the other hand, valid refers to all the requirements for integrating into the blockchain. Those are the syntactical conformance oftransactions, correctness of payer’s signature and further requirements such as “thepayer’s account must exist”, “balance after the transaction must not be negative.”
4
In Bitcoin, the requirements (e.g., Bitcoin Improvement Proposals) are subject tochange. New proposals will be incorporated in the requirements after agreed amongmajority of miners through voting process in the blockchain.
5
In practice, a transaction is confirmed after the block that contains the transaction
has at least 6 blocks built on top. This is the situation where our notion of confirmed
is satisfied with high probability.

Short Paper: Secure Offline Payments in Bitcoin

7

where cert T is a certificate issued to a public key PKT which is generated withina tamper-proof wallet W at the production time. (PKW , skW ) is a key pairgenerated by W, and w is an account related to PKW .
In the offline payment, a payee Y verifies the received transaction τo by aproof Sign(skT ; τo , τl ) with his localchain CY . If all of the above conditions are
satisfied, Y is convinced that the coin-preloading transaction to the payer’s walletτl is confirmed by all honest players with overwhelming probability in k. As far
as the tamper-proof wallet honestly produces the payment transaction τo , Y canbelieve that τo is not an overspending transaction and will be confirmed later on.
To see whether τl satisfies the last condition τl ∈ Cdk , 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 a form of a Merkle Tree and B only keeps the root hash value ofthe tree. Let τel be a witness of the membership proof, or a set of all sibling hashvalues in every branch in the path from the root to the leaf τl . Using the witness
τel , the membership proof can be efficiently proved since there exists a function
member(·) such that(
1 if τ ∈ Bmember(B, τ, τe) =0 otherwise
We replace the proof with Sign(skT ; τo , τl , τel ) where offline payee needs efficiency.
Theorem 2. We assume there exists a tamper-proof wallet W . Given a security
parameter k and an offline transaction τo accepted by a payee Y such that τo isverified by a proof = Sign(skw ; τo , τl ) with respect to the payee’s localchain CY ,the probability that the transaction τo , later on, changes its state to invalid is
dknegligible in k. That is, with CY  C0Y , we havePr[τo ∈
/ VC0 | τo is verified by proof with respect to CY ] < negl(k).
dkYProof. Given τo is verified by proof with respect to CY , equation (1) holds. Under the tamper-proof assumption, the tamper-proof wallet W never overspends
exceeding the preloaded balance bl . Therefore, if the preloading transaction τl is
confirmed, that is, τl ∈ CX for all X ∈ H, then the offline transaction τo cannot
become invalid with respect to C0Y .
dk
Since τl is already in 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 satisfy Cdk  CZ with negligible error probability in k. Substituting
dk
C → CY , τl ∈ CY contradicts with τl ∈/ CZ . Thus, τl must be confirmed with
arbitrarily high probability 1 − negl(k) with the security parameter k. Hence thetheorem.
ut
In the case τo ∈/ VC0dk where the offline transaction τo is turned out toY

be invalid later on with respect to the payee’s evolved localchain C0Y ( CY ),dk8

Taisei Takahashi et al.

this must be the case where the tamper-proof wallet assumption is broken andτo is found to be an overspent transaction. Even in this case, the preloadingtransaction τ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 (1) for all
honest player X ∈ H with 1 − negl(k).
cert T 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 dkl
XThis fact convinces all honest players. Given τo is invalid with respect to C0Y , thatis, τo ∈/ VC0dk , the redeeming transaction τr = Sign(skY ; proof, cancel τo ) becomesYvalid with respect to CX  CY for all X ∈ H with arbitrarily high probability
1 − negl(k). The trustworthy provider of the tamper-proof wallet or an insurancecompany might compensate Y for the damage of bo after τr is confirmed.
0dk

5Conclusion

In this paper, we have shown that, with light-weight tamper-proof wallets, completely decentralized offline payment is possible without any modification to theexisting Bitcoin network. Our protocol requires the coin pre-loading transaction
is confirmed and its block is delivered to every possible payee before the firstoffline payment is made. This should be the best possible for Bitcoin network.
Lastly, we thank anonymous reviewers for their valuable comments.

References
1. Dmitrienko, A., Noack, D., Yung, M.: Secure Wallet-Assisted Offline Bitcoin Payments with Double-Spender Revocation. AsiaCCS (2017)
2. Garay, J.A., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol with chainsof variable difficulty. In: CRYPTO (1). Lecture Notes in Computer Science, vol.
10401, pp. 291–323. Springer (2017)
3. Garay, Juan A, Kiayias, Aggelos, Leonardos, Nikos: The Bitcoin Backbone Protocol- Analysis and Applications. EUROCRYPT 9057(Chapter 10), 281–310 (2015)
4. Karame, G.O., Androulaki, E., Capkun, S.: Double-spending fast payments in bitcoin. In: CCS. pp. 906–917. ACM (2012)
5. Lind, J., Eyal, I., Pietzuch, P.R., Sirer, E.G.: Teechan: Payment channels
using trusted execution environments. https://arxiv.org/abs/1612.07766 (2016),
https://arxiv.org/pdf/1612.07766.pdf, accessed: 2017-03-09
6. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash systems (11 2008), https://bitcoin.org/bitcoin.pdf
7. Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous
networks. In: EUROCRYPT (2). Lecture Notes in Computer Science, vol. 10211,
pp. 643–673 (2017)