METHOD AND SYSTEM FOR DESYNCHRONIZATION RECOVERY FOR PERMISSIONED BLOCKCHAINS USING BLOOM FILTERS

• US 20170344435A1
• Filed: 05/24/2016
• Published: 11/30/2017
• Est. Priority Date: 05/24/2016
• Status: Active Grant

• Current Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Original Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Inventors: DAVIS, Steven Charles
• Granted Patent: US 10,198,325 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method for recovery of missing or extra data using a bloom filter includes: storing a plurality of transaction messages, each including a transaction value; generating a bloom filter of the transaction messages, the bloom filter being generated using a number of hash rounds and with a size at least double the number of transaction messages; generating a recover message including the number of transaction messages, the number of hash rounds, the size, and the generated bloom filter; transmitting the recover message to a consensus node; receiving a response message from the consensus node, the response message including at least one additional transaction message; and inserting the at least one additional transaction message into the plurality of transaction messages.

Claims

1. A method for recovery of missing or extra data using a bloom filter, comprising:

storing, in a transaction database of a processing server, a plurality of transaction messages, wherein each transaction message includes a structured data set related to a blockchain transaction including at least a transaction value;

generating, by a generation module of the processing server, a bloom filter of the plurality of transaction messages, wherein the bloom filter is generated using a predetermined number of hash rounds and has a size of at least double a count of the plurality of transaction messages stored in the transaction database;

generating, by the generation module of the processing server, a recover message, wherein the recover message includes at least the count of the plurality of transaction messages, the predetermined number of hash rounds, the size, and the generated bloom filter;

electronically transmitting, by a transmitting device of the processing server, the generated recover message to at least one consensus node;

receiving, by a receiving device of the processing server, a response message from one or more of the at least one consensus nodes, wherein the response message includes at least one additional transaction message; and

executing, by a querying module of the processing server, a query on the transaction database to insert the at least one additional transaction message.

2. The method of claim 1, further comprising:

generating, by a hashing module of the processing server, a Merkle root for the plurality of transaction messages using a transaction reference associated with the transaction value included in each of the plurality of transaction messages;

receiving, by the receiving device of the processing server, a proposal message from each of the at least one consensus nodes, wherein the proposal message includes at least a proposed Merkle root; and

verifying, by a verification module of the processing server, that the generated Merkle root is not equivalent to the proposed Merkle root included in each received proposal message prior to electronically transmitting the generated recover message.

3. The method of claim 2, further comprising:

generating, by the hashing module of the processing server, a new Merkle root for the plurality of transaction messages and the at least one additional transaction message using a transaction reference associated with the transaction value included in each respective transaction message; and

verifying, by the verification module of the processing server, that the new Merkle root is equivalent to the proposed Merkle root included in each received proposal message.

4. The method of claim 2, further comprising:

generating, by the hashing module of the processing server, the transaction reference associated with the transaction value included in each of the plurality of transaction messages by hashing the respective transaction value using a predetermined hashing algorithm.

5. The method of claim 2, further comprising:

sorting, by the querying module of the processing server, the transaction reference associated with the transaction value included in each of the plurality of transaction messages based on a natural ordering prior to generating the Merkle root.

6. The method of claim 1, wherein

each of the plurality of transaction messages further includes a specific slot identifier,

the recover message and response message each further includes the specific slot identifier, and

each of the at least one additional transaction messages includes the specific slot identifier.

7. The method of claim 1, wherein the bloom filter is generated using a predetermined hashing algorithm for each of the predetermined number of hash rounds.

8. A method for recovery of missing or extra data using a bloom filter, comprising:

storing, in a transaction database of a processing server, a plurality of transaction messages, wherein each transaction message includes a structured data set related to a blockchain transaction including at least a transaction value;

generating, by a generation module of the processing server, a bloom filter of the plurality of transaction messages, wherein the bloom filter is generated using a predetermined number of hash rounds and has a size of at least double a count of the plurality of transaction messages stored in the transaction database;

generating, by the generation module of the processing server, a recover message, wherein the recover message includes at least the count of the plurality of transaction messages, the predetermined number of hash rounds, the size, and the generated bloom filter;

electronically transmitting, by a transmitting device of the processing server, the generated recover message to at least one consensus node;

receiving, by a receiving device of the processing server, a response message from one or more of the at least one consensus nodes, wherein the response message includes at least a second bloom filter, an indicated number of hash rounds, an indicated filter size, and a number of expected transaction messages;

identifying, by a data identification module of the processing server, at least one transaction message of the plurality of transaction messages not included in the second bloom filter based on the included transaction value and the indicated number of hash rounds, indicated filter size, number of expected transaction messages, and second bloom filter; and

executing, by a querying module of the processing server, a query on the transaction database to delete the at least one identified transaction message.

9. The method of claim 8, wherein the number of expected transaction messages is less than the count of the plurality of transaction messages.

10. The method of claim 8, wherein the indicated filter size is at least double the number of expected transaction messages.

11. The method of claim 8, wherein an updated count of the plurality of transaction messages after execution of the query is equivalent to the number of expected transaction messages.

12. The method of claim 8, further comprising:

generating, by a hashing module of the processing server, a Merkle root for the plurality of transaction messages using a transaction reference associated with the transaction value included in each of the plurality of transaction messages;

receiving, by the receiving device of the processing server, a proposal message from each of the at least one consensus nodes, wherein the proposal message includes at least a proposed Merkle root; and

verifying, by a verification module of the processing server, that the generated Merkle root is not equivalent to the proposed Merkle root included in each received proposal message prior to electronically transmitting the generated recover message.

13. The method of claim 12, further comprising:

generating, by the hashing module of the processing server, a new Merkle root for the plurality of transaction messages after deletion of the at least one identified transaction message using a transaction reference associated with the transaction value included in each respective transaction message; and

verifying, by the verification module of the processing server, that the new Merkle root is equivalent to the proposed Merkle root included in each received proposal message.

14. The method of claim 12, further comprising:

generating, by the hashing module of the processing server, the transaction reference associated with the transaction value included in each of the plurality of transaction messages by hashing the respective transaction value using a predetermined hashing algorithm.

15. The method of claim 12, further comprising:

sorting, by the querying module of the processing server, the transaction reference associated with the transaction value included in each of the plurality of transaction messages based on a natural ordering prior to generating the Merkle root.

16. The method of claim 8, wherein

each of the plurality of transaction messages further includes a specific slot identifier, and

the recover message and response message each further includes the specific slot identifier.

17. The method of claim 8, wherein the bloom filter is generated using a predetermined hashing algorithm for each of the predetermined number of hash rounds.

18. A system for recovery of missing or extra data using a bloom filter, comprising:

a transaction database of a processing server configured to store a plurality of transaction messages, wherein each transaction message includes a structured data set related to a blockchain transaction including at least a transaction value;

a generation module of the processing server configured to generate

a bloom filter of the plurality of transaction messages, wherein the bloom filter is generated using a predetermined number of hash rounds and has a size of at least double a count of the plurality of transaction messages stored in the transaction database, and

a recover message, wherein the recover message includes at least the count of the plurality of transaction messages, the predetermined number of hash rounds, the size, and the generated bloom filter;

a transmitting device of the processing server configured to electronically transmit the generated recover message to at least one consensus node;

a receiving device of the processing server configured to receive a response message from one or more of the at least one consensus nodes, wherein the response message includes at least one additional transaction message; and

a querying module of the processing server configured to execute a query on the transaction database to insert the at least one additional transaction message.

19. The system of claim 18, further comprising:

a verification module of the processing server; and

a hashing module of the processing server configured to generate a Merkle root for the plurality of transaction messages using a transaction reference associated with the transaction value included in each of the plurality of transaction messages, wherein

the receiving device of the processing server is further configured to receive a proposal message from each of the at least one consensus nodes, wherein the proposal message includes at least a proposed Merkle root, and

the verification module of the processing server is configured to verify that the generated Merkle root is not equivalent to the proposed Merkle root included in each received proposal message prior to electronically transmitting the generated recover message.

20. The system of claim 19, wherein

the hashing module of the processing server is further configured to generate a new Merkle root for the plurality of transaction messages and the at least one additional transaction message using a transaction reference associated with the transaction value included in each respective transaction message, and

the verification module of the processing server is further configured to verify that the new Merkle root is equivalent to the proposed Merkle root included in each received proposal message.

21. The system of claim 19, wherein the hashing module of the processing server is further configured to generate the transaction reference associated with the transaction value included in each of the plurality of transaction messages by hashing the respective transaction value using a predetermined hashing algorithm.

22. The system of claim 19, wherein the querying module of the processing server is further configured to sort the transaction reference associated with the transaction value included in each of the plurality of transaction messages based on a natural ordering prior to generating the Merkle root.

23. The system of claim 18, wherein

each of the plurality of transaction messages further includes a specific slot identifier,

the recover message and response message each further includes the specific slot identifier, and

each of the at least one additional transaction messages includes the specific slot identifier.

24. The system of claim 18, wherein the bloom filter is generated using a predetermined hashing algorithm for each of the predetermined number of hash rounds.

25. A system for recovery of missing or extra data using a bloom filter, comprising:

a transaction database of a processing server configured to store a plurality of transaction messages, wherein each transaction message includes a structured data set related to a blockchain transaction including at least a transaction value;

a generation module of the processing server configured to generate

a bloom filter of the plurality of transaction messages, wherein the bloom filter is generated using a predetermined number of hash rounds and has a size of at least double a count of the plurality of transaction messages stored in the transaction database, and

a recover message, wherein the recover message includes at least the count of the plurality of transaction messages, the predetermined number of hash rounds, the size, and the generated bloom filter;

a transmitting device of the processing server configured to electronically transmit the generated recover message to at least one consensus node;

a receiving device of the processing server configured to receive a response message from one or more of the at least one consensus nodes, wherein the response message includes at least a second bloom filter, an indicated number of hash rounds, an indicated filter size, and a number of expected transaction messages;

a data identification module of the processing server configured to identify at least one transaction message of the plurality of transaction messages not included in the second bloom filter based on the included transaction value and the indicated number of hash rounds, indicated filter size, number of expected transaction messages, and second bloom filter; and

a querying module of the processing server configured to execute a query on the transaction database to delete the at least one identified transaction message.

26. The system of claim 25, wherein the number of expected transaction messages is less than the count of the plurality of transaction messages.

27. The system of claim 25, wherein the indicated filter size is at least double the number of expected transaction messages.

28. The system of claim 25, wherein an updated count of the plurality of transaction messages after execution of the query is equivalent to the number of expected transaction messages.

29. The system of claim 25, further comprising:

a verification module of the processing server; and

a hashing module of the processing server configured to generate a Merkle root for the plurality of transaction messages using a transaction reference associated with the transaction value included in each of the plurality of transaction messages, wherein

the receiving device of the processing server is further configured to receive a proposal message from each of the at least one consensus nodes, wherein the proposal message includes at least a proposed Merkle root, and

the verification module of the processing server is configured to verify that the generated Merkle root is not equivalent to the proposed Merkle root included in each received proposal message prior to electronically transmitting the generated recover message.

30. The system of claim 29, wherein

the hashing module of the processing server is configured to generate a new Merkle root for the plurality of transaction messages after deletion of the at least one identified transaction message using a transaction reference associated with the transaction value included in each respective transaction message, and

the verification module of the processing server is configured to verify that the new Merkle root is equivalent to the proposed Merkle root included in each received proposal message.

31. The system of claim 29, wherein the hashing module of the processing server is further configured to generate the transaction reference associated with the transaction value included in each of the plurality of transaction messages by hashing the respective transaction value using a predetermined hashing algorithm.

32. The system of claim 29, wherein the querying module of the processing server is further configured to sort the transaction reference associated with the transaction value included in each of the plurality of transaction messages based on a natural ordering prior to generating the Merkle root.

33. The system of claim 25, wherein

each of the plurality of transaction messages further includes a specific slot identifier, and

the recover message and response message each further includes the specific slot identifier.

34. The system of claim 25, wherein the bloom filter is generated using a predetermined hashing algorithm for each of the predetermined number of hash rounds.