Check out the new USENIX Web site. next up previous
Next: Panel Discussion Up: Session VII: Protocols Previous: PayTree: ``Amortized-Signature'' for Flexible

Agora: A Minimal Distributed Protocol for Electronic Commerce

Eran Gabber and Abraham Silberschatz, Bell Labs

Eran Gabber presented Agora, a micro-payment protocol that relies on the assumption that public key signatures are not that expensive. The goal was to design a micro-payment protocol that is compatible with existing tools and protocols, scalable and distributed, and whose overhead per transaction is minimal. The overhead that matters is given by the number of messages and signatures required by the protocol for a typical transaction. Micro-payments that have been proposed so far are not designed with the number of messages in mind. They are not concerned with compatibility with existing web protocols either.

Agora fulfills the requirements mentioned above. It is minimal: a typical transaction does not generate more messages than what is required for web browsing. It is distributed: a typical transaction can be verified by the merchant without contacting any online authority. It enables online purchases: one does not need to go to a broker first to get scrips.

Eran went on to describe the protocol. There are five kinds of entities: a central authority, who certifies the banks' public keys; banks, who manage accounts; customers; merchants; and arbiters, who also need to be registered with the central authority. Both customers and merchants have accounts (with expiration dates) at the bank. The expiration date helps in housekeeping billings and payments, and lessens the effect of brute force attacks. A billing period is associated with the lifetime of each account. Everybody has public keys and private keys. New sets of keys are generated for each billing period. Whenever the merchant starts with a new pair of keys, he or she takes them to the central authority for certification. When customers change their keys, they go to their banks to get new certificates for the next billing period. A certificate is a customer ID, signed by the customer's bank, and includes the expiration date, an account number and the customer's public key. The certificate is used as a promise of payment. Banks would only issue new certificates to customers that paid their bills for the previous period.

For a typical transaction, the protocol uses four messages. The first message has the customer asking for price quotations; the second message has the merchant reply with the quotations; the third message contains the purchase order from the customer; and the last message, from the merchant, contains the goods (or error messages). This is the same number of messages that free web browsing takes. The first message is generated when the customer clicks on a link containing a page of price quotations; the page is displayed to the customer when the second message is received; the third message is generated when the customer clicks on an specific item; the item is then returned in the last message and displayed to the customer.

Note that the merchant sends more quotations than have been asked for. This is an advantage, because if the customer decides to purchase a second item on the same page of quotations, only two message are needed in the transaction. Also, only one signature is used for each page of quotations.

Because it is assumed that merchants distrust banks with whom they have not had relationships before, the first time the merchant receives a certificate issued by a bank that he or she does not know, the merchant may go to his or her own bank and verify the unknown bank's public key. (Every bank's key certification is broadcast to all the other banks by the central authority.)

Merchants can therefore accept certificates in a distributed fashion, and only submit them at the end of each billing period. This offline mechanism does allow merchants to be defrauded in situations where they accept certificates from accounts that have been revoked or expired.

Eran continued with a security analysis. Because all messages are signed, authenticity, tamper-proofness, and non-repudiability are guaranteed. Because all messages come with sequence numbers, replay attacks and double charging by merchants can be prevented. But, as mentioned before, full distribution makes fraud possible in this protocol. To lessen the possibility of fraud, it is possible to enhance the protocol and have merchants talk to customers' banks now and then. (Banks need to keep track of all revoked certificates.)

If the customer sends a purchase order, which constitutes a promise to pay, and never gets anything back or gets something else, then he or she can go to the arbiter and present the quotation (which includes the description of the goods) and the purchase order. The arbiter can then demand the goods. If the merchant does not comply with the demand, the arbiter has the power to revoke the transaction.

During the question period, Mark Manasse asked about the impact of doing digital signatures on the latency of transactions. Eran replied that the customers' machines are assumed to be idle, so there is no problem there. Merchants, however, should have a farm of PCs dedicated to signature generation and verification. Also, one can always use optimized signatures to make things more efficient. Marvin Sirbu commented that Agora reduces the number of messages by transferring liability to the merchant. Eran agreed.

next up previous
Next: Panel Discussion Up: Session VII: Protocols Previous: PayTree: ``Amortized-Signature'' for Flexible
Alma Whitten