Method of electronic payments that prevents double-spending

• US 5,839,119 A
• Filed: 09/27/1996
• Issued: 11/17/1998
• Est. Priority Date: 09/27/1996
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Krsul, Ivan V., Demers, Alan J., Mudge, J. Craig
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Myhre, James W.
• Application Number:
  US08/721,484
• Time in Patent Office: 781 Days
• Field of Search: 705/26, 705/39, 705/40, 705/41, 308/4, 308/24
• US Class Current: 705/39
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/10 specially adapted for electronic funds transfer [EFT] systems; specially adapted for home banking systems
• CPC Class Codes: G06Q 20/102 Bill distribution or payments
• CPC Class Codes: G06Q 20/105 involving programming of a portable memory device, e.g. IC cards, "electronic purses"
• CPC Class Codes: G06Q 20/29 characterised by micropayments
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes

Abstract

A method of generating electronic monetary tokens that supports off-line transactions while preventing double-spending. Generation of electronic token halves by a financial services provider begins in response to a request from a buyer to generate electronic monetary tokens to be used with an identified seller. First, the financial services provider generates a multiplicity of electronic monetary tokens. Second, the provider splits each electronic monetary token into two electronic token halves and associates with each the same serial number. These electronic token halves when combined recreate the electronic monetary token from which they were generated, but by themselves neither electronic token half has any value. Nor can either electronic half by itself be used to create the electronic monetary token without the token half'"'"'s mate. After splitting all of the electronic monetary tokens, the services provider assigns a half of each electronic token the seller and the other half of each electronic token to the buyer. The buyer and seller can now engage in multiple transactions off-line of the financial services provider.

Claims

1. A method of generating electronic monetary tokens that supports payments between a buyer and a seller off-line of a financial services provider while preventing double spending, the method comprising:

a) generating a first multiplicity of electronic monetary tokens in response to a request from the buyer for use with the seller;

b) splitting each electronic monetary token into two electronic token halves having a same serial number, each pair of electronic tokens halves having the same serial number recreating the electronic monetary token when combined together, each electronic token half having no monetary value;

c) delivering a subset of the electronic token halves to the seller; and

d) delivering another subset of the electronic token halves to the buyer.

2. The method of claim 1 further comprising:

e) storing in a database entry the session serial numbers of the electronic monetary tokens.

3. The method of claim 2 further comprising:

f) in response to a redemption request including a first electronic monetary token, detecting an attempt to double spend the first electronic monetary token using a session serial number of the first electronic monetary token and the database entry.

4. The method of claim 2 further comprising:

f) in response to a redemption request from the buyer including a first electronic token half having a first session serial number;

1) redeeming electronic monetary tokens received from the seller;

2) noting as invalid the sessions serial numbers of the electronic monetary tokens received from the seller using the database entry; and

3) detecting an attempt to double spend the first electronic token half using the database entry.

5. The method of claim 1 further comprising:

e) generating a second multiplicity of electronic authorization tokens in response to a request from the buyer for use with the seller and proof of an assertion about the buyer;

f) splitting each electronic authorization token into two authorization token halves having a same serial number, each pair of authorization token halves having the same serial number recreating the electronic authorization token when combined together, each authorization token half having no authority without an authorization token half having the same serial number;

g) delivering a subset of the authorization token halves to the seller; and

h) delivering another subset of the authorization token halves to the buyer.

6. The method of claim 5 further comprising:

i) storing in a database entry the session serial numbers of the electronic monetary tokens.

7. The method of claim 6 further comprising:

f) in response to a redemption request including a first electronic monetary token, detecting an attempt to double spend the first electronic monetary token using a session serial number of the first electronic monetary token and the database entry.

8. The method of claim 6 further comprising:

f) in response to a redemption request including a first electronic token half having a first session serial number;

1) redeeming electronic monetary tokens received from the seller;

2) noting as invalid the sessions serial numbers of the electronic monetary tokens received from the seller using the database entry; and

3) detecting an attempt to double spend the first electronic token half using the database entry.

9. A method of supporting electronic payments between a buyer and a seller off-line of a financial services provider that prevents double-spending, the method comprising the steps of:

a) generating a first number of electronic monetary tokens in response to a request from the buyer for use with the seller, the first number being greater than two, each electronic token having a second number of bits representing a monetary value of the electronic monetary token;

c) splitting each of the first number of electronic monetary tokens into two electronic token halves by;

c1) for each electronic token creating a first token half by generating a random string having a third number of bits equal to the second number of bits;

c2) for each electronic monetary token creating a second token half by performing a bitwise XOR using the electronic monetary token and the first token half;

c3) for electronic monetary token associating with each token half a serial number, each electronic token half having no monetary value alone and combining with another electronic token half having a same serial number to recreate an electronic monetary token;

d) electronically transmitting to the seller a first subset of the electronic token halves, none of the first subset of electronic token halves having a same serial number; and

e) electronically transmitting to the buyer a second subset of the electronic token halves, none of the second subset of electronic token halves having a same serial number.

10. The method of claim 9 further comprising the step of:

f) delivering a good to the buyer in response to receipt of a one of the electronic token halves of the second subset if off-line of the financial services provider the one of the electronic token halves from the second subset combines with a one of the electronic token halves from the first subset to recreate an electronic monetary token.

11. The method claim 9 further comprising the step of:

f) storing in a database entry the serial numbers of each pair of electronic token halves generated during step c).

12. The method of claim 11 further comprising the steps of:

g) in response to a redemption request from the seller including a first electronic monetary token, detecting an attempt to double spend the first electronic monetary token using a session serial number of the first electronic token and the database entry.

13. The method of claim 11 further comprising the steps of:

g) in response to a redemption request from the buyer including a first electronic token half having a first session serial number;

1) redeeming electronic monetary tokens received from the seller;

2) noting as invalid the sessions serial numbers of the electronic monetary tokens received from the seller using the database entry; and

3) detecting an attempt by the buyer to double spend the first electronic token half using the database entry.

14. The method of claim 9 further comprising the steps of:

f) generating a third number of electronic authorization tokens in response to a request from the buyer for use with the seller and proof of an assertion about the buyer, each electronic authorization token having a fourth number of bits representing the assertion about the buyer;

g) splitting each of the third number of electronic authorization tokens into two authorization token halves by;

g1) for each electronic authorization token creating a first authorization token half by generating a random string having a fifth number of bits equal to the fourth number of bits;

g2) for each electronic authorization token creating a second authorization token half by performing a bitwise XOR using the electronic authorization token and the first authorization token half;

g3) for each electronic authorization token associating with each authorization token half a serial number, each authorization token half having no authority alone and combining with another authorization token half having a same serial number to recreate an electronic authorization token;

d) electronically transmitting to the seller a first subset of the authorization token halves, none of the first subset of authorization token halves having a same serial number; and

e) electronically transmitting to the buyer a second subset of the authorization token halves, none of the second subset of authorization token halves having a same serial number.

15. A method of generating electronic tokens that supports off-line transactions between a first party and a second party, the method comprising:

a) generating a first multiplicity of electronic tokens in response to a request from the first party for use with the second party;

b) splitting each electronic token into two electronic token halves having a same serial number, each pair of electronic tokens halves having the same serial number recreating the electronic token when combined together, each electronic token half being unintelligible without an electronic token half having the same serial number;

c) assigning a subset of the electronic token halves to the second party; and

d) assigning another subset of the electronic token halves to the first party.

16. The method of claim 15 further comprising:

e) storing in a database entry the serial numbers of the electronic tokens.

17. The method of claim 16 further comprising:

f) in response to a redemption request including a first electronic token, detecting an attempt to double spend the first electronic token using a serial number of the first electronic token and the database entry.

18. The method of claim 16 further comprising:

f) in response to a redemption request including a first electronic token half having a first serial number;

1) noting as invalid the serial numbers of the electronic tokens received from the second party using the database entry; and

2) detecting an attempt to double spend the first electronic token half using the first serial number and the database entry.

19. The method of claim 15 wherein splitting each electronic token comprises:

1) for each electronic token creating a first token half by generating a random string having a number of bits equal to a number of bits of the electronic token;

2) for each electronic token creating a second token half by performing a bitwise XOR using the electronic token and the first token half.

20. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory for a method of supporting off-line electronic transactions between a buyer and a seller that prevents double-spending, the method comprising;

1) generating a first number of electronic tokens in response to a request from the buyer for use with the seller, the first number being greater than two, each electronic token having a second number of bits;

2) splitting each of the first number of electronic monetary tokens into two electronic token halves by;

A) for each electronic token creating a first token half by generating a random string having a third number of bits equal to the second number of bits;

B) for each electronic token creating a second token half by performing a bitwise XOR using the electronic token and the first token half;

C) for electronic token associating with each token half a serial number, each electronic token half being unintelligible alone and combining with another electronic token half having a same serial number to recreate an electronic token;

3) assigning to the seller a first subset of the electronic token halves, none of the first subset of electronic token halves having a same serial number; and

4) assigning to the buyer a second subset of the electronic token halves, none of the second subset of electronic token halves having a same serial number.

21. The article of manufacture of claim 20 wherein the instructions stored in the memory further comprise:

5) storing in a database entry the session serial numbers of the electronic monetary tokens.

22. The article of manufacture of claim 21 wherein the instructions stored in the memory further comprise:

6) in response to a redemption request from the seller including a first electronic monetary token, detecting an attempt to double spend the first electronic monetary token using a session serial number of the first electronic token and the database entry.

23. The article of manufacture of claim 21 wherein the instructions stored in the memory further comprise:

6) in response to a redemption request from the buyer including a first electronic token half having a first session serial number;

A) redeeming electronic monetary tokens received from the seller;

B) noting as invalid the sessions serial numbers of the electronic monetary tokens received from the seller using the database entry; and

C) detecting an attempt by the buyer to double spend the first electronic token half using the first session serial number and the database entry.

24. The article of manufacture of claim 20 wherein the instructions stored in the memory further comprise:

5) generating a second multiplicity of electronic authorization tokens in response to a request from the buyer for use with the seller and proof of an assertion about the buyer;

6) splitting each electronic authorization token into two authorization token halves having a same serial number, each pair of authorization token halves having the same serial number recreating the electronic authorization token when combined together, each authorization token half having no authority without an authorization token half having the same serial number;

7) delivering a subset of the authorization token halves to the seller; and

8) delivering another subset of the authorization token halves to the buyer.