Summary chains in distributed systems

Patent metadata

Field	Value
Publication number	US-10855445-B2
Application number	US-201815909266-A
Country	US
Kind code	B2
Filing date	Mar 1, 2018
Priority date	Mar 1, 2018
Publication date	Dec 1, 2020
Grant date	Dec 1, 2020

Abstract

Certain aspects of the present disclosure provide techniques for summarizing data in a distributed system. Embodiments include generating an ordered list of blocks by iterating through a first group of blocks of a hash chain starting at a last block of the hash chain and adding each of the first group of blocks of the hash chain to the ordered list. Embodiments further include generating summary data by applying a summary function to the first group of blocks based on the ordered list. The summary function may take the ordered list as an input and provide the summary data of the first group of blocks as an output. Embodiments further include generating a summary block comprising the summary data and adding the summary block to a summary chain.

First claim

What is claimed is:

1. A computer-implemented method for summarizing data in a distributed system, comprising:
generating an ordered list of blocks by:
iterating through a first group of blocks of a hash chain starting at a last block of the hash chain; and
adding each of the first group of blocks of the hash chain to the ordered list; and

generating summary data by applying a summary function to the first group of blocks based on the ordered list, wherein the summary function takes the ordered list as an input and provides the summary data of the first group of blocks as an output;
generating a summary block comprising the summary data;
adding the summary block to a summary chain;
determining that a periodic threshold has been met;
generating a new ordered list of blocks by:
iterating through a second group of blocks of the hash chain starting at a current last block of the hash chain, wherein the second group of blocks was added to the hash chain after the first group of blocks; and
adding each of the second group of blocks to the new ordered list;

generating new summary data by applying the summary function to the second group of blocks based on the new ordered list, wherein the summary function takes the new ordered list as an input and provides the new summary data of the second group of blocks as an output;
generating a new summary block comprising the new summary data and a pointer to the summary block; and
adding the new summary block to the summary chain.

2. The computer-implemented method of claim 1 , wherein the periodic threshold comprises one of: a time period; a number of blocks added to the hash chain; an amount of data added to the hash chain, or a value of a variable stored in the hash chain.

3. The computer-implemented method of claim 1 , further comprising: performing an audit of the data by iterating through the summary chain and analyzing the summary data.

4. The computer-implemented method of claim 3 , further comprising:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit of the data by iterating through the hash chain and analyzing the data.

5. The computer-implemented method of claim 1 , wherein the summary function comprises one or more of: a summation; a balance calculation; and a net change.

6. The computer-implemented method of claim 1 , wherein the summary function comprises:
generating a periodic chain comprising the first group of blocks in a reverse order from the order in which they are stored on the hash chain; and
returning the periodic chain as the summary data.

7. A system comprising: one or more processors; and a non-transitory computer-readable medium comprising instructions that, when executed, cause the one or more processors to perform an operation for summarizing data in a distributed system, the operation comprising:
generating an ordered list of blocks by:
iterating through a first group of blocks of a hash chain starting at a last block of the hash chain; and
adding each of the first group of blocks of the hash chain to the ordered list; and

generating summary data by applying a summary function to the first group of blocks based on the ordered list, wherein the summary function takes the ordered list as an input and provides the summary data of the first group of blocks as an output;
generating a summary block comprising the summary data;
adding the summary block to a summary chain;
determining that a periodic threshold has been met;
generating a new ordered list of blocks by:
iterating through a second group of blocks of the hash chain starting at a current last block of the hash chain, wherein the second group of blocks was added to the hash chain after the first group of blocks; and
adding each of the second group of blocks to the new ordered list;

generating new summary data by applying the summary function to the second group of blocks based on the new ordered list, wherein the summary function takes the new ordered list as an input and provides the new summary data of the second group of blocks as an output;
generating a new summary block comprising the new summary data and a pointer to the summary block; and
adding the new summary block to the summary chain.

8. The system of claim 7 , wherein the periodic threshold comprises one of: a time period; a number of blocks added to the hash chain; an amount of data added to the hash chain, or a value of a variable stored in the hash chain.

9. The system of claim 7 , wherein the operation further comprises: performing an audit of the data by iterating through the summary chain and analyzing the summary data.

10. The system of claim 9 , wherein the operation further comprises:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit of the data by iterating through the hash chain and analyzing the data.

11. The system of claim 7 , wherein the summary function comprises one or more of: a summation; a balance calculation; and a net change.

12. The system of claim 7 , wherein the summary function comprises:
generating a periodic chain comprising the first group of blocks in a reverse order from the order in which they are stored on the hash chain; and
returning the periodic chain as the summary data.

13. A non-transitory computer-readable medium comprising instructions that, when executed, cause the one or more processors to perform an operation for summarizing data in a distributed system, the operation comprising:
generating an ordered list of blocks by:
iterating through a first group of blocks of a hash chain starting at a last block of the hash chain; and
adding each of the first group of blocks of the hash chain to the ordered list; and

generating summary data by applying a summary function to the first group of blocks based on the ordered list, wherein the summary function takes the ordered list as an input and provides the summary data of the first group of blocks as an output;
generating a summary block comprising the summary data;
adding the summary block to a summary chain;
determining that a periodic threshold has been met;
generating a new ordered list of blocks by:
iterating through a second group of blocks of the hash chain starting at a current last block of the hash chain, wherein the second group of blocks was added to the hash chain after the first group of blocks; and
adding each of the second group of blocks to the new ordered list;

generating new summary data by applying the summary function to the second group of blocks based on the new ordered list, wherein the summary function takes the new ordered list as an input and provides the new summary data of the second group of blocks as an output;
generating a new summary block comprising the new summary data and a pointer to the summary block; and
adding the new summary block to the summary chain.

14. The non-transitory computer-readable medium of claim 13 , wherein the periodic threshold comprises one of: a time period; a number of blocks added to the hash chain; an amount of data added to the hash chain, or a value of a variable stored in the hash chain.

15. The non-transitory computer-readable medium of claim 13 , wherein the operation further comprises: performing an audit of the data by iterating through the summary chain and analyzing the summary data.

16. The non-transitory computer-readable medium of claim 15 , wherein the operation further comprises:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit

Assignees

• Intuit Inc

Inventors

• Gabriel Michael R
• Scott Glenn

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L9/3297 Primary

  involving time stamps, e.g. generation of time stamps · CPC title

• H04L9/0637 Primary

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title