Xiang Shao, School of Information Technology, Griffith University, QLD, 9726. Email: X.Shao@griffith.edu.au
Dr Anne Thuy-Anh Nguyen, School of Information Technology, Griffith University, QLD, 9726. Email: A.Nguyen@griffith.edu.au
Dr Vallipuram Muthukkumarasamy, School of Information Technology, Griffith University, QLD, 9726. Email: V.Muthu@griffith.edu.au
Micropayments, which are of tiny value and high volumes, are too small to warrant the cost of the current electronic financial transactions. The proliferation of value added content providers over the global information infrastructure, and the easy access to ubiquitous networking certainly demands a micropayment system, which is cost effective, secure and easy to use. In this paper we propose an efficient micropayment system, which is mainly based on simple hash functions and digital signature rather than relying on computationally more complex and costly cryptographic algorithms. The proposed WebCoin system’s architecture and protocols are explained in detail.
The traditional payment systems currently used by most e-commerce sites are not suitable for high-volume, tiny-valued transactions. When delivering low cost information with a value of only a few cents or even lower, such as a piece of music or an article in a magazine, the traditional electronic payment approach is far from ideal. On the contrary, digital order and delivery require, in most cases, a method of instant payment without high overhead cost and time lags. It is obvious that an efficient system to handle this trade is needed. As the transactions concerned involve only very small amounts of money, such a payment is called micropayment (Manasse, 1995; Rvest and Shamir, 1996; Yen and Kuo, 1998).
The design of a micropayment system is usually quite different from that of the traditional electronic payment system. In a typical former system, a customer makes a purchase and gives a small payment to a merchant over the Internet. The merchant then has to verify it before providing services to the customer. Rivest and Shamir (1996) have proposed a micropayment system called Payword that allows customer to purchase small valued products over the computer network. Cryptographic techniques such as digital signature and one-way hash function are used in their micropayment system. Similar applications of these techniques can be found in Glassman et al (1995), Yen and Kuo (1998), and Lee and Kim (2002).
There are some alternatives or improved approaches based on the concept of Payword, such as MicroMint (Rivest and Shamir, 1996), Wenbo Scheme (Mao 1996), NetPay (Dai and Lo, 1999) and so on. Although hash chained payword was soon developed for multiple shopping by several payment schemes, a strong cryptography and computation burden at both the user and vendor sides still exist. The heavy computation is a direct consequence of generating and verifying digital signature, as well as computing hash function. Most of the micropayment systems are still in proposal or in trial stages. Sometimes they may not yet move to an operational status due to security doubts and risks involved, for example double-spending and low anonymity problems. Up to now, there is no single solution that has found a wider acceptance. In the next section, we will propose and analyse a conceptual model of a micropayment system and its protocol. Discussion on system efficiency and security analyses follows in Section 3.
A general micropayment system named WebCoin is proposed in this section. It is an efficient, secure, easily available, and debit-based model of a micropayment system, which can be used for purchasing online information and services on a pay-per-click basis via the Internet.
The WebCoin micropayment system consists of three main players: user, vendor (e.g. online merchants) and broker. The system’s net server acts as a broker. WebCoin provides an offline micropayment model using lightweight hashing-based encryption. Only users and vendors are involved in each payment transaction. The broker is responsible for the registration of users and vendors, the detection of user’s double-spending and vendor’s over-charging, and the maintenance of vendors’ and users’ accounts.
In the WebCoin system, a user has to register with the broker and applies for an account. Before the user asks a vendor for service, he has to create coin chains that act as the currency payable to the vendor. The latter then needs to inspect to ascertain that the user is legal and that the coin chains are legitimately generated. Afterwards, the vendor collects the user’s coins and redeems the payment from the broker. Figure 1 portrays the basic architecture of the proposed WebCoin model and the relationships among the players.
In this model, it is assumed that the broker is honest and is trusted by both the users and the vendors. The vendors are less trusted and the users may or may not be honest. There is no dependency on user trust in this approach.
Figure 1: WebCoin system architecture
For the purpose of clear notation, the symbols required in
the system are defined as follows: the Broker, User and Vendor are represented
as B, U, and V, respectively. Their corresponding
public keys are denoted as 
, 
,
, and the private keys, 
,
, 
.
The user-shared-key is abbreviated as USK. The hash-chain coin is represented
by 
, where i = 1, 2,
…, n. A signed message M can be denoted as {M}SK
while a message encrypted by user-shared-key as {M}USK. In
order to make the user-created coins payable to multiple vendors, the value
of each coin is required to be the same and small, for example, 1 cent. The
value could be re-defined according to the requirements of different systems.
To reduce the computation burden of the hash function both in coin generation
at the user side and in coin verification at the vendor side, we introduce a
double-chain to create coins and a coin index to keep track of them. Two hash
functions h1 and h2 are used and the coin chains generated
by h1 and h2 are represented as one-unit chain - 
,
and ten-unit chain - 
, respectively.
The indexes of the spent coin (
and 
), g and k correspondingly,
will be recorded at both the user and vendor sides for further debit and credit
processing.
The WebCoin protocol consists of four phases: (a) the registration, (b) initiation, (c) transaction, and (d) redemption, and some phases contain several steps.
(a) Registration Phase
In this phase, the relationships among the broker, user and vendor are established. The broker is responsible for the registration and maintenance of the user and vendor’s accounts. At the beginning, the vendor and user have to register and obtain an account from the broker. The vendor then gives authority to the broker to sign coin with which the registered user can make an Internet purchase. The broker constructs accounts for the vendor and user who has to put a minimum deposit into his account before purchasing. The payment details are transmitted to the broker through a secure authenticated channel, such as SSL.
(b) Initiation Phase
In this phase, the user’s first payment is set up. The broker
imposes a spending limit for the user and creates two coin models, 
and
, both of which can be used by
the user to mint coins for multiple vendors. These models are also used as the
coin authenticator for the vendor. The broker subsequently issues and signs
a certificate for the user. The certificate will contain coin models and the
user’s spending limit as well as user’s public key. It is valid during a given
period of time, normally one day. The broker can refuse to issue a new certificate
when the coin balance or if the user has engaged in cheating.
When the user starts to make a purchase from a vendor, he has to sign a purchase commitment message and send it to the vendor. The message holds the broker-signed certificate for the vendor to verify his legitimacy. Figure 2 shows the message flows in the initiation phase, which contains the following process steps.
Figure 2: Message flows in the initiation phase
After successful login, the user requests a certificate from the broker. The certificate authorises the user to create coins that could be redeemed by vendors from the broker.
To response to the user’s request, the broker needs to check the user’s balance. If the balance is zero, the broker prompts the user to purchase new coins. According to the user’s account balance, the broker sets up the maximum spending limit (Max). The Max could be same as the user’s balance or as a total ratio pre-set by the broker.
The broker creates coin models -- root coins for the user who
could use them to mint coins when needed. The server randomly picks up two large
numbers, x, y, then uses hash computation to generate two
coin models: one-cent-coin and
ten-cent-coin , where
, 
(1)
The broker issues a digitally signed certificate, keeps one
copy, and transfers the original to the user. The certificate contains the broker’s
identification (
), user’s identification
(
), user’s public key (),
expiration date (E), and information about coin-chain (C)
including two coin models, and
and Max.
(2)
The user certificate is defined by
= {,
, ,
E, C } (3)
It has to be renewed by the broker each time after the user has successfully logged into the system. The broker issues a certificate to the user only if his account is in good standing.
To ensure that the certificate was signed by the broker, the
user can apply the broker’s public key to verify it. He then extracts the coin
models, , ,
and Max from C. The user stores the certificate for the next
step.
Before the user transfers coins for the payment, he has to send the vendor a purchase commitment (PC), which contains information such as IDs of the user and vendor, purchase date as well as the user certificate. It is defined by
PC = { ,
, ,
D } (4)
PC is signed by the user. For multiple shopping, the user should send PC to different vendors.
(c) Transaction Phase
In this phase, coins are created by the user, who generates
two coin-chains with appropriate lengths according to the goods value. Coin-chains
are based on the original root coins - and
in the user’s certificate or
derived from the replaced root coins - the stored last-spent-coins for the previous
payment. The user can purchase goods from multiple vendors by using the same
chains. It is very convenient for frequent micropayments to multiple vendors
during the user’s net-surfing. He only needs to send the value of the last coins
in both hash-chains with the chains’ starting and ending indexes to the vendor,
who verifies the validity of the last coin by re-hashing the root coins. Figure
3 shows the message flows in the transaction phase.
Figure 3: Message flows in the transaction phase
Assume that the user wants to buy/download some information
goods from several vendors 
, the
transaction procedure for the user and vendor is shown as follows.
The vendor has to verify the purchase commitment signed and sent by the user. He also needs to verify the embedded user certificate by applying the broker’s public key. If both of them are valid, the vendor will check whether the purchase date D is within the expiration date E. If it is true, he will store the purchase commitment, and send the URL of the goods that the user requested. Otherwise, the vendor will abandon the protocol. The URL is encrypted by a shared key USK. The key will be sent to the user for decrypting the URL after he pays the correct coins for the goods. The vendor will set a session for the URL to prevent the user from re-accessing the URL next time without paying.
The user computes the hash functions and creates coin chains
according to and
from the certificate sent by the broker. He can mint coins as much as he needs.
For example, he starts to conduct the first purchase in a day and the goods
value is n cents. Then he could decide he needs to mint that i one-cent
coins and j ten-cent coins, where
i = mod (n, 10), j = int (n / 10) (5)
Here two coin chains are generated as follows,
(6)
(7)
If it is not his first purchase in a day, that means the user
has already created some coins before the current payment. Let the previous
last-spent one-cent-coin be denoted as 
,
and the previous last-spent ten-cent-coin as 
,
the coin chains will be expressed as follows:
(8)
(9)
where g = 0, 1, 2,… Max-1 and
k = 0, 1, 2, … Max/10-1
Then 
and 
are
the last coins of two different coin-chains that the user creates for the payment.
Before coins are created, the length of each chain is decided according to Max
(which refers to the maximum spending limit mentioned in Step 2 of the previous
phase) and the index of the previous last-spent coins.
When the user intends to purchase some information goods from a vendor, he
applies his secret key to sign
the payment message PM and sends to the vendor. The PM consists
of the following attributes:
PM = { g, k, ,
, i, j, T
} (10)
g and k are the indexes of the root coins
(starting coins) for one-cent-coin chain and ten-cent-coin chain, respectively.
While (g+i) and (k+j) are the indexes of the end coins, ,
for the two chains, they will
become the root coins when the next payment occurs. As T denotes the
timestamp, it prevents the user from replaying. The vendor could easily know
user’s previous spent amount (PSA) by calculating
PSA = g + k*10 (11)
Therefore, the last-spent-coins ,
, and corresponding index g+i,
k+j will be stored in the user’s side (eg., in IE toolbar) as the root
coins for generating the next spending coins. They also are recorded in the
vendor’s side as the coin authenticator for verifying the next coins for the
same user (See the next step for details). It is noted that the user creates
and spends his coins in an increasing order.
The vendor verifies and authenticates payment message PM
using the user’s public key .
As mentioned in the first step of this phase, the vendor has received the purchase
commitment containing user’s certificate , from which he can extract the expire
date E, Max, ,
, and .
Subsequently, the following sub-steps are performed: (1) The vendor will calculate
the user’s previous spent amount PSA (See equation 11). (2) The vendor
compares Max (user’s spending limit) with PSA and spending
amount (SDA), which is defined as:
SDA = i + j*10 (12)
If the Max is greater than the sum of PSA
and SDA, that means i and j are valid. Otherwise,
the user is overspending; the vendor refuses the key delivery. (3) The vendor
starts to verify the coins by re-hashing. He checks
to find out whether the user is in the first time shopping on his site on that
day.
If yes, the vendor will extract and
from ,
rehashing them to obtain 
and 
,
the same way as the user mints coins.
(13)
where hash computation runs g+i times
(14)
where hash computation runs k+j times
If no, the vendor will search the database to locate,
retrieve the last-spent-coins 
and
, which the user sent last time,
and then gets index p, q, and runs hash operation to obtain
and .
(15)
where hash computation runs g+i-p times
(16)
where hash computation runs k+j-q times
(4) The vendor compares the hashing results and
, with the value ,
in the payment message, if both
of them match, the coins are proved valid. Otherwise, the coins are forged.
After validating coins, the vendor will send the user a shared
key for decrypting the URL of the information goods. He then stores the last
spent ,
and the corresponding index g+i, k+j into the database for
the coin redemption or for the coin verification in the next purchase made by
the same user.
(d) Redemption Phase
In this phase, the user and vendor’s balance is updated. The
vendor will collect all payment messages PMs, sort and group them by
user’s ID () in user’s certificate,
then send to the broker. For each user, the vendor has to send the broker the
last coins of each chain and the corresponding indexes, along with .
He should also request redemption before the coin expiration date. The broker
verifies redemption messages, user’s certificate and confirms the limit length
of hash-chain (according to the Max embedded in user’s certificate that was
issued by the broker himself). Using the coin models and
, the broker verifies the value
of last coin by rehashing. If the value is valid, the broker deposits the corresponding
amount of money in the vendor’s account and debits the users at the same time.
Figure 4 shows the message flows in the redemption phase.
Figure 4: Message flows in the redemption phase
There are several steps involved in this phase:
When the user finishes Internet shopping and logs off the system,
he sends the last-spent-coins ,
and index g+i, k+j
to the system. Then the broker will calculate the his total spending by computing
, where
(17)
And then the broker updates his account.
At the end of the day, the vendor sends the redemption messages
RMs to the broker. It is signed by using the vendor’s secret key
. RM contains the vendor’s
ID (), and all user’s payment
information. For each user, his purchase commitments PC, all PMs
and the sum of his total spending 
(SUM) are all included in RM, which is defined as
RM = { ,
(,
PC, (PM),
(SUM) ) }
(18)
The broker verifies the vendor’s signature in RM
using the vendor’s public key ,
and checks the validity of the date extracted from certificate embedded in
each PC. In fact, the broker can recognise each certificate since
he has signed it. He subsequently verifies the last coins in each PM by computing
hash function in the same way as the vendor does. If all coins are valid,
the broker calculates total value -
(SDA) of all spending amount (See equation 12) of each user of this
vendor. Then he compares (SDA)
with (Sum) signed
by the vendor. If they are the same, the broker adds an amount of
(SUM) to the vendor’s account, otherwise an amount of
(SDA). This is because of the fact that the user signs
(SDA) instead of (SUM).
The broker collects all RMs, groups
(PM) from each RM according to ,
aggregates all (SDA)
from different RMs with the same ,
and then generates 
, where
=
( (SDA) ) (19)
is then compared with
(in Step 1 of this phase). If
is greater than ( >=
), it is acceptable because
some the vendors might take responsibility of the coin loss or redeem coin
after its expiry date. Otherwise, it is detected that the user was double-spending
or using forged coins.
The broker verifies all the coin collected by vendors. If the coins are valid, the broker updates accounts of the user and vendor immediately, and then deposits the vendor periodically.
In this section, the protocol of WebCoin system has been described in detail. The following section will give an analysis and discussion on how the WebCoin system enhances efficiency and security in micropayment.
In WebCoin, the user creates coins as he needs and exchanges them for goods from vendors, who verify the coins and redeem them from the broker. The added features in WebCoin are the combination of hash-chains and digital signature mechanisms. The coins in this system are the hashed values in a chain, typically involve some kind of digital signatures, which means that at least one signature generation and verification are required to process coin chains.
The key innovation of the proposed system is the use of double hash-chain and coin index. Using the former for creating coins requires much less hash computation compared to single chain, especially when a larger-value payment occurs. The use of coin index not only reduces hash operations at both user and vendor sides, but also minimises the public key operations in each transaction. This section provides a qualitative analysis and discussion of system efficiency and security. A qualitative comparison of the proposed system with other micropayment systems is also presented.
In order to reduce the overhead cost of each payment transaction and enhance the efficiency of the proposed micropayment system, three options are considered. The first option is to minimise the heavy computations in the system; the second is to transfer some of he computations offline; and the third is to reduce the storage requirements for both user and vendor sides.
Minimising Computation. It is clear that the computation of the signature scheme is much more costly and time-consuming in comparison with hash functions. Therefore, to reduce the number of public key operations, the hash function is applied in the proposed system whenever possible. There are a small number of public-key operations involved per purchase in the WebCoin system. At the first transaction of the day, user has to generate a signature along with the payment message sent to the first vendor, who will verify two signatures by applying the corresponding public keys. One signature is in the user’s certificate signed by the broker of WebCoin system and the other embedded in the payment message signed by the user. From the second payment to the same vendor, the user also needs to generate a signature for each payment message; however, the vendor only needs to verify the user’s signature. Since the former has already recorded user’s ID and the last-spent-coin which is proven valid, the only thing he needs to do is to apply hash computation to prove the validity of the last coin that the user sent for each payment without verifying the broker’s signature embedded in user’s certificate again. As a result, the vendor only has to perform signature verification once per transaction per user except for the first payment.
The use of double-hash-chain and coin index significantly reduces
the iteration of hash operation, especially when a comparable large-value payment
(i.e. more than 10 cents) occurs. The double hash-chain, and
, are represented in the WebCoin
system as one-cent coin chain and ten-cent coin chain, respectively. The former
is used to generate one-cent-coins for a very-small-value purchase under 10
cents, while the latter is particularly suitable for larger value. When a large
number of coins is needed, the total number of hash computation can be reduced
dramatically by using double hash chain instead of one chain. As the output
length of the hash function is
longer than that of the hash function ,
an added advantage is that an attacker who intends to break the hash function
will experience much more difficulty
than breaking . Using the coin
index is another way to reduce the number of usage of the hash function. During
the coin creation processing, the user does not need to create a whole coin
chain in advance. Instead, he mints coins as needed. Coins in a chain are made
in sequence order, starting from the root coin (coin model made by the broker),
and ending at the last-spent-coin (the indexed coin). The latter in turned is
used as root coin for creating the next coin in the following purchase. Coins
in a chain are payable to all vendors, that means the user does not need to
create different chains for different vendors. During the coin verification
processing, instead of passing a whole chain of coins, only the last coin and
its index are signed and sent to vendor for verification. Instead of checking
the whole signed coin chain for each transaction, the vendor only needs to verify
the last coin value by using previous recorded index, at the same time stores
its value and index for further verification.
Offline Operation. WebCoin is an essentially offline system. The user only needs to contact the broker at the beginning of each certificate lifetime in order to obtain a new-signed certificate. In each transaction, the broker is not involved. To improve the system efficiency, some of the operations are transferred offline, such as the vendor’s sending of the redemption messages and the broker’s authentication of all certificates and payment processing in the redemption phase. As a result, the load of the online communication with the system is reduced to the minimum; and the bottleneck at peak time is avoided.
Less Storage Required. The use of coin index reduces the storage requirements for all parties in the system. The broker does not need to maintaining a large database to contain all spend coins. The user’s certificate, the sum of all his spending, and the value and index of the last-spent-coin need to be stored on the user side. These data are replaced after each purchase. On the other side, the vendor has to record each payment message for redemption purpose. Both the coin information stored in the vendor’s database and goods information recorded in the user’s toolbar are temporary and valid only for a short period (say, one day) in order to reduce storage requirements.
The proposed system provides adequate security by applying hash function and digital signature techniques. The user certificate is signed by the broker in WebCoin system. It certifies the coin model, with which all coins created can be accepted by vendors and redeemed by the broker before their expiration dates. Therefore, the vendor could verify the user’s payments without contacting the broker in each transaction. Note that in this scheme, the coin chains are related to both the broker and user, that means the broker is responsible for creating root coin for the coin chain only, while the user needs to mint the rest of coins by operating hash functions. The micro payments are made by the user’s revealing successive last-coins of the hashed coin-chain to the vendor. Digital signature is applied to authenticate the user certificate, the payment message and redemption message. The following sub-sections describe the major security concerns: how the WebCoin system prevents coin forgery, over-spending and detects double-spending.
Forgery Prevention. The essential feature of the hash chain
is that the value instructions of the coin are as un-forgeable as coins in the
chain. The one-way and collision-resistance features of the hash function make
it impossible to create the same coin as one in the coin chain, or pre-image
the next coin without the previous one. As forgery of coins is made difficult
by using hash function, this ensures that generating a valid coin is computationally
infeasible for anybody but the user, even if all the previous coins in the chain
are known. Furthermore, creating fake coins would require the forgery of the
broker’s digital signature. As it authenticates and certifies the initial chain
of coins, forged coins can be easily identified by the by re-hashing the chain.
Overspending Prevention. The WebCoin system is a debit-based scheme where a user’s consumption in a certain period (one day) cannot exceed the maximum spending (Max). This value for each user is pre-set by the broker according to the user’s account balance or his specific request. Max provides less opportunity for fraud since no purchases can be made against an account with insufficient funds. The limit is embedded in the user certificate, which is signed and sent by the broker to the user who in turn sends to the vendor for each payment. Max is valid during the lifetime of a user’s certificate. The vendor can verify the excess of the limit by checking a user’s certificate at the Initiation Phase.
In each transaction, the user has to send the vendor the payment message, which the user’s previous spent amount PSA is indicated (See equation 11). With Max and PSA, the vendor can easily find whether the daily limit is exceeded (equation 12). If not, the vendor immediately sends the requested key for encrypted URL to the user and stores the payment message. Otherwise the request is denied (See details in Step 3 of Transaction Phase). Consequently, overspending is prevented even at the multiple vendor’s level.
Double-spending and Over-charging Detection. The broker in the proposed system collects the coins and checks each of them using hash operations. In fact, he keeps the original coin model for the chains, so reused coins can be discovered in this stage. For prevention, the broker needs to specify the rules to the users. If one reuses a coin and thus violates the rules, the broker can terminate the user’s spending privileges by placing his name on a “black-list” during this period. This list will be published and inspected by the vendors, who can reject a purchase during the transaction phase. Furthermore, the broker can refuse to issue the certificate during the next period, in which case, the user’s credit will be terminated.
When a vendor double deposits the payment, the signature for payment message is replayed because he cannot forge the user’s signature. As the vendor is not anonymous to the broker at the Redemption Phase, he can be caught easily.
This paper presents a secure, efficient and simple Internet payment mechanism
appropriate for selling inexpensive information and services, delivered online.
In the proposed WebCoin micropayment system, novel features for coin creation
and verification using double-hash-chain and coin index are introduced. In the
process, one-way hash function and cryptographic signature schemes are integrated
to reduce computation cost. The proposed system is also suitable for use with
multiple vendors. While most micropayment systems are still in the proposal
or in trial stages, the widespread usage of micropayment systems on the Internet
will become unavoidable in the near future.
Dai, X. and Lo, B. (1999) ‘NetPay – An Efficient Protocol for Micropayments on the WWW’, in Proceedings of Fifth Australian World Wide Web Conference. Available online [HREF1] [2003 Sept. 15].
Glassman, S., Manasse, M., Abadi, M., Gauthier, P. and Sobalvarro, P. (1995) ‘Millicent Protocol for Inexpensive Electronic Commerce’, World Wide Web Journal, vol. 1, no. 1, pp.603-618.
Hwang, M-S. (2001) ‘A Simple Micro-payment Scheme’, Journal of Systems & Software, vol.55, no.3, pp. 221-229.
Lee, M., and Kim, K. (2002) ‘A Micro-payment System for Multiple-Shopping’, presented in SCIS 2002 Symposium on Cryptography and Information Security, Shirahama, Japan, Jan.29-Feb.1. Available online [HREF2] [2003 Jun. 2].
Manasse, M. (1995) ‘The Millicent Protocols for Electronic Commerce’, in Proceedings of the First USENIX Workshop on Electronic Commerce, USENIX press, New York, pp.117-123.
Mao, B. (1996) ‘A Simple Cash Payment Technique for the Internet’, in Proceedings of European Symposium on Research in Computer Science (ESORICS’96), Springer-Verlag, September.
Rivest, R and Shamir, A. (1996) ‘PayWord and MicroMint: Two Simple Micropayment Schemes’, in Proceedings of The Fourth Cambridge workshop on Security Protocols, Cambridge, pp. 69-87.
Yen, S.M. and Kuo, P.Y. (1998) ‘Improved Micro-Payment System’,
in Proceedings of the Eighth National Conference on Information Security, Taiwan,
pp. 175-186.