# US 2021/0334409 A1 · Integrity verification in cloud key-value stores

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0334409 A1
- Document ID: US20210334409A1
- Status: Published application
- Kind: A1
- Application number: 16/858,776
- Filed: 2020-04-27
- Published: 2021-10-28
- Earliest claimed: 2020-04-27
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Grisha Weintraub; Alon Kadosh
- Web page: https://patentgrep.com/patent/US20210334409A1

## CPC

- G06F 21/64: Protecting data integrity, e.g. using checksums, certificates or signatures
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/9014: {hash tables}
- H04L 9/3236: {using cryptographic hash functions}
- H04L 9/3247: {involving digital signatures}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A computer-based system and method for verifying integrity of data in a key-value database, including assigning each key that is supported by the key-value database to a bucket in a keys database. Upon storing a pair of a value and a key in the key-value database, storing in the bucket assigned to the key a presence indicator indicative of a presence of the key in the key-value database. A bucket is assigned to a key by applying a predetermined function on the key. When reading a value from the key-value database, if the response is empty: getting from the keys database the bucket associated with the key and searching the bucket for the presence indicator associated with the key. If the presence indicator associated with the key is found in the bucket determining that the key-value database is not complete.

## Claims

### Claim 1

A method for verifying integrity of data in a computerized key-value database, the method comprising:
assigning, by a computer processor, each key that is supported by the computerized key-value database to one of a plurality of buckets in a computerized key database; and
upon storing a pair of a value and an associated key in the computerized key-value database, storing by the computer processor in the bucket assigned to the associated key a presence indicator indicative of a presence of the associated key in the key-value database.

### Claim 2 (depends on 1)

The method of claim 1, wherein assigning the bucket to a key is performed by applying a predetermined function on the key, wherein the function includes a hash operation that is applied on the key, followed by a modulus operation, wherein the bucket key equals the result of the modulus operation.

### Claim 3 (depends on 1)

The method of claim 1, wherein the presence indicator comprises a copy of the key.

### Claim 4 (depends on 1)

The method of claim 1, comprising signing the bucket with a digital signature.

### Claim 5 (depends on 1)

The method of claim 1, wherein storing the presence indicator in the bucket comprises:
applying a Bloom filter to the associated key and other keys that are stored in the bucket; and
storing the result of the Bloom filter in the bucket.

### Claim 6 (depends on 1)

The method of claim 1, comprising, upon storing a pair of a value and an associated key in the computerized key-value database, signing the value using a digital signature.

### Claim 7 (depends on 1)

The method of claim 1, wherein the computerized key-value database and the computerized key database are provided as a service in a cloud computing environment.

### Claim 8

A method for verifying integrity of data in a computerized key-value database, the method comprising:
sending, by a computer processor, a request to retrieve a value from a key-value database, the request comprising the associated key;
obtaining, by the computer processor, a response from the key-value database;
if the response includes a value:
verifying the correctness of the value using a digital signature of the value; and
if the response does not include a value:
obtaining, by the computer processor, from a keys database a bucket associated with the key;
searching, by the computer processor, the bucket for a presence indicator associated with the key;
if the presence indicator associated with the key is not found in the bucket determining, by the computer processor, that the response is legitimate; and
if the presence indicator associated with the key is found in the bucket determining, by the computer processor, that the key-value database is not complete.

### Claim 9 (depends on 8)

The method of claim 8, wherein obtaining the bucket associated with the key from the keys database comprises:
sending a request to retrieve the bucket from the keys database, the request comprising a bucket key, wherein the bucket key is calculated by applying a predetermined function on the key, wherein the function includes a hash operation that is applied on the key, followed by a modulus operation, wherein the bucket key equals the result of the modulus operation.

### Claim 10 (depends on 8)

The method of claim 8, wherein the presence indicator comprises a copy of the key, wherein searching the bucket for the presence indicator comprises searching for the copy of the key.

### Claim 11 (depends on 8)

The method of claim 8, wherein obtaining the response from the key-value database comprises obtaining a digital signature of the bucket, the method comprising verifying correctness of the bucket using the digital signature of the bucket.

### Claim 12 (depends on 8)

The method of claim 8, wherein the computerized key-value database and the computerized key database are provided as a service in a cloud computing environment.

### Claim 13

A system for verifying completeness of data in a computerized key-value database, the system comprising:
a memory; and
a processor configured to:
assign each key that is supported by the computerized key-value database to one of a plurality of buckets in a computerized key database; and
upon storing a pair of a value and an associated key in the computerized key-value database, storing in the bucket assigned to the associated key a presence indicator indicative of a presence of the associated key in the key-value database.

### Claim 14 (depends on 13)

The system of claim 13, the processor is configured to assign the bucket to a key by applying a predetermined function on the key, wherein the function includes a hash operation that is applied on the key, followed by a modulus operation, wherein the bucket key equals the result of the modulus operation.

### Claim 15 (depends on 13)

The system of claim 13, wherein the presence indicator comprises a copy of the key.

### Claim 16 (depends on 13)

The system of claim 13, the processor is configured to sign the bucket with a digital signature.

### Claim 17 (depends on 13)

The system of claim 13, wherein the processor is configured to store the presence indicator in the bucket by:
applying a Bloom filter to the associated key and other keys that are stored in the bucket; and
storing the result of the Bloom filter in the bucket.

### Claim 18 (depends on 13)

The system of claim 13, wherein the processor is configured to, upon storing a pair of a value and an associated key in the computerized key-value database, sign the value using a digital signature.

### Claim 19 (depends on 13)

The system of claim 13, wherein the computerized key-value database and the computerized key database are provided as a service in a cloud computing environment.
