Charanjit Jutla presented the PayTree payment mechanism. He started with a summary of the major steps in micro-payments systems and pointed out that it is crucial to make payments from customers to merchants computationally efficient. Public key signatures are the most reliable way of authenticating or verifying payments, but they are computationally expensive. The idea is therefore to minimize the number of public key signatures that are required in issuing or authenticating (a sequence of) certificates for payments.
Charanjit briefly explained the workings of PayWord, a scheme that explores this idea. Based on Lamport's one-time password scheme, PayWord only requires one public key signature to issue a number of payment certificates. By linking the validity of future payments to the validity of a previous payment through cheap hash functions, the cost of the signature operation is amortized.
PayWord, however, is not able to determine who the cheater is when fraud occurs. For instance, if a certificate is presented more than once for redemption, the bank does not know if the customer double spent it, or if the merchant colluded with another merchant. Also, it is not well suited for web surfing, because payment certificates generated by a signature can not be spent with different merchants.
The idea of PayTree was then presented. It is based on Merckle's authentication tree scheme, and uses the following data structure: a tree whose leaf nodes are labeled by secret random values, whose internal nodes are labeled by the hash value of the nodes' successors, and whose root is signed. Because of the tree structure, PayTree is more flexible and allows payments to different merchants to be made using different parts of the tree. This means that multiple merchants can now share the cost of a public key signature. Charanjit proceeded to describe ways of issuing and verifying payments in three different scenarios. In the first scenario, a tree is used to pay only one merchant; in the second scenario, a tree is used to pay multiple honest merchants; in the last scenario, multiple merchants with arbitrary behaviors are considered. The computational complexity of each of the cases is presented.
In the basic PayTree mechanism, the individual payments all share the same value and each tree has a pre-defined total value associated with it. But PayTree can be slightly modified to implement trees with multiple denominations, unlimited payment potential or divisible coins. It can also be used as a module of other payment systems.
Someone in the audience commented that the flexibility of PayTree increases bandwidth and storage consumption. Charanjit agreed.