Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Diagonal Node Data Block Matrix For Adding Hash-Linked Records And Deleting Arbitrary Records While Preserving Hash-Based Integrity Assurance

Patent Number: 11,175,826


Provided is a process including: initializing a data block matrix; making supra-diagonal nodes that include at most one more node than sub-diagonal nodes; making a hash nodes with a hash sequence length that is proportional to a number of nodes in the row or column of nodes in which the hash node is arranged; and writing data blocks in nodes of the data block matrix such that a number of data blocks in nodes in the data block matrix is less than (N.sup.2-N) for N number of nodes in the data block matrix, wherein the data block matrix has dispersed data blocks.

patent description

This note describes a data structure, which can be referred to as a block matrix, that supports the ongoing addition of hash-linked records while also allowing the deletion of arbitrary records, preserving hash-based integrity assurance that other blocks are unchanged. The block matrix data structure may have utility for incorporation into applications requiring integrity protection that currently use permissioned blockchains. This capability could for example be useful in meeting privacy requirements such as the European Union General Data Protection Regulation (GDPR), which requires that organizations make it possible to delete all information related to a particular individual, at that person's request.

The data block matrix uses an array of blocks, with hash values for each row and column. This structure makes it possible to delete or modify a particular block with hash values, assuring that other blocks have not been affected. That is, the integrity of blocks that have not been deleted is assured. Blocks can be deleted by overwriting with zeroes or other values, with one row and one column hash recalculated; specifically, after deleting block i, j, row i, and column j, hash values are recalculated.

The data structure ensures the following properties:

   Balance: The upper half (above diagonal) contains at most one additional cell more than the lower half does.

   Hash sequence length: This is the number of blocks in a row or column hash proportional to

   N for a matrix with N blocks by the balance property.

   Number of blocks: The total number of data blocks in the matrix is N2 - N because the diagonal is null.

   Block dispersal: No consecutive blocks appear in the same row or column.

Created September 13, 2022, Updated December 14, 2023