Using hash chains

  In order to lessen the computational burden on B, in this section we sketch an approach that requires far less from B computationally but that still provides some degree of nonrepudiable evidence to A. It employs the well-known idea of hash chaining, which has been used in the past for efficient user authentication [Hal94] and micropayments [RS95], among other things.

Again we assume that there is a well-known (i.e., authenticated) public key for B. When A signs up for B's click-through payment program, B generates a large, unpredictable number s, applies a one-way hash function (e.g., [SHA95]) f to it k times to produce $\ell = f^k(s)$, digitally signs the pair ${\tt <}k, \ell{\tt \gt}$,and sends ${\tt <}k, \ell{\tt \gt}$ and the signature to A. Note that all of this takes place when A registers for the click-through program, not on the critical path of referrals. Once this is set up, rather than passing a digital signature back to A during a referral, B simply passes back the pair ${\tt <}i, \ell' {\tt \gt}$ to A, where $\ell' = f^{k-i}(s)$, for the i-th referral ($1 \le i \le k$) that A gives it. B can pass the pair ${\tt <}i, \ell' {\tt \gt}$ to A using techniques like those of Section 4.1. A can verify the correctness of this pair by verifying that $\ell = f^i(\ell')$. In the event of a dispute, A need only present the digitally signed pair ${\tt <}k, \ell{\tt \gt}$ and a pair ${\tt <}i, \ell' {\tt \gt}$ where $\ell = f^i(\ell')$ to convince a third party that B received at least i referrals from A.

This scheme has some disadvantages in comparison to that of Section 4.2.1. The main disadvantage is that B can later repudiate the user's IP address in this scheme. In payment programs that pay only for ``unique'' referrals, A's inability to record the user IP address in a way that prevents B from later repudiating it could leave A at a disadvantage in a dispute. An agreement that B returns a referral record (i.e., a new pair ${\tt <}i, f^{k-i}(s){\tt \gt}$) only for unique referrals may restore the balance, but only if A is prepared to verify, when B refuses to return a referral record, that the referred user was a repeat user. A second disadvantage of this scheme is that it must periodically be ``refreshed''; i.e., once k referrals from A to B have been made, then A must obtain a new signed pair ${\tt <}k', f^{k'}(s') {\tt \gt}$from B.