Summary chains in distributed systems

Patent metadata

Field	Value
Publication number	US-11664974-B2
Application number	US-202017083418-A
Country	US
Kind code	B2
Filing date	Oct 29, 2020
Priority date	Mar 1, 2018
Publication date	May 30, 2023
Grant date	May 30, 2023

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, comprising:
generating summary data by applying a summary function to a first group of blocks, wherein the summary function takes a list of the first group of blocks 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, wherein the periodic threshold comprises one of: a time period; a number of blocks added to a chain; an amount of data added to the chain; or a value of a variable stored in the chain;
generating new summary data by applying the summary function to a second group of blocks, wherein the summary function takes a new list of the second group of blocks as input data and provides the new summary data of the second group of blocks as output data;
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 , further comprising: performing an audit of the data, wherein performing the audit comprises iterating through the summary chain.

3. The computer-implemented method of claim 2 , further comprising:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit of the data, wherein performing the additional audit comprises iterating through a chain comprising the first group of blocks and the second group of blocks.

4. 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.

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

6. The method of claim 1 , wherein the list of the first group of blocks and the new list of the second group of blocks are ordered lists.

7. A system comprising: one or more processors; and a memory comprising instructions that, when executed by the one or more processors, cause the system to perform a method for summarizing data in a distributed system, the method comprising:
generating summary data by applying a summary function to a first group of blocks, wherein the summary function takes a list of the first group of blocks 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, wherein the periodic threshold comprises one of: a time period; a number of blocks added to a chain; an amount of data added to the chain; or a value of a variable stored in the chain;
generating new summary data by applying the summary function to a second group of blocks, wherein the summary function takes a new list of the second group of blocks as input data and provides the new summary data of the second group of blocks as output data;
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 method further comprises: performing an audit of the data, wherein performing the audit comprises iterating through the summary chain.

9. The system of claim 8 , wherein the method further comprises:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit of the data, wherein performing the additional audit comprises iterating through a chain comprising the first group of blocks and the second group of blocks.

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

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

12. The system of claim 7 , wherein the list of the first group of blocks and the new list of the second group of blocks are ordered lists.

13. A computer-implemented method for summarizing data, comprising:
generating summary data by applying a summary function to a first group of blocks of a chain, wherein the summary function takes a list of the first group of blocks 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, wherein the periodic threshold comprises one of: a time period; a number of blocks added to a chain; an amount of data added to the chain; or a value of a variable stored in the chain;
generating new summary data by applying the summary function to a second group of blocks, wherein the summary function takes a new list of the second group of blocks as input data and provides the new summary data of the second group of blocks as output data, and wherein the second group of blocks was added to the chain after the first group of blocks;
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 computer-implemented method of claim 13 , further comprising: performing an audit of the data, wherein performing the audit comprises iterating through the summary chain.

15. The computer-implemented method of claim 14 , further comprising:
determining, based on the audit, that additional analysis is needed; and
performing an additional audit of the data, wherein performing the additional audit comprises iterating through the chain.

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

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

Assignees

• Intuit Inc
• Intuti Inc

Inventors

• Gabriel Michael R
• Scott Glenn

Classifications

• H04L9/3297 Primary

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

• H04L9/50

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

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · 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