Computing device providing Merkle tree-based credibility certification, storage device, and method for operating storage device

Patent metadata

Field	Value
Publication number	US-12574229-B2
Application number	US-202318297623-A
Country	US
Kind code	B2
Filing date	Apr 9, 2023
Priority date	Nov 15, 2022
Publication date	Mar 10, 2026
Grant date	Mar 10, 2026

Abstract

A storage device included in a computing device which provides Merkle tree-based credibility certification may generate a random hash value by hashing an erase count and a seed of each of a plurality of super blocks, may generate a Merkle tree in which the random hash value is a leaf node, for each of the plurality of super blocks, may generate a plurality of private keys corresponding to the plurality of super blocks, respectively, on the basis of root nodes of Merkle trees of the plurality of respective super blocks, and may transmit private key information including the plurality of private keys to a host device. The host device may use the private key information in credibility certification of the storage device.

First claim

What is claimed is:

1 . A computing device comprising:
a storage device configured
to generate a random hash value by hashing an erase count and a seed of each of a plurality of super blocks,
to generate a Merkle tree in which the random hash value is a leaf node, for each of the plurality of super blocks,
to generate a plurality of private keys corresponding to the plurality of super blocks, respectively, on the basis of root nodes of Merkle trees of the plurality of respective super blocks, and
to transmit private key information including the plurality of private keys to a host device,
wherein the erase count of each of the plurality of super blocks is a value increased when the each of the plurality of super blocks is erased.

2 . The computing device according to claim 1 , further comprising:
the host device configured to transmit a credibility certification request to the storage device, to compare a plurality of private keys received as a response to the credibility certification request and previously received private key information, and to transmit a credibility certification result to the storage device.

3 . The computing device according to claim 2 , wherein the seed is a randomizing seed that is used for the storage device to randomize data received from the host device.

4 . The computing device according to claim 2 , wherein the host device transmits the credibility certification request during a boot sequence of the storage device.

5 . The computing device according to claim 4 , wherein the storage device is set to a normal mode or an emergency mode according to the credibility certification result.

6 . The computing device according to claim 1 , wherein the private key information includes private keys of the plurality of respective super blocks, one or more dummy keys and the number of private keys.

7 . The computing device according to claim 6 , wherein, when transmitting a plurality of private keys as a response to a credibility certification request from the host device, the storage device further includes and transmits one or more dummy keys.

8 . A storage device comprising:
a memory including a plurality of memory blocks that are divided into a plurality of super blocks; and a controller configured to generate a random hash value by hashing an erase count and a seed of each of the plurality of super blocks, to generate a Merkle tree in which the random hash value is a leaf node, for each of the plurality of super blocks, to generate private keys corresponding to the plurality of super blocks, respectively, on the basis of root nodes of Merkle trees of the plurality of respective super blocks and store the private keys in the memory, and to transmit private key information including the private keys to an external device, wherein the erase count of each of the plurality of super blocks is a value increased when the each of the plurality of super blocks is erased.

9 . The storage device according to claim 8 , wherein, when a first super block is erased among the plurality of super blocks, the controller
increases an erase count of the first super block, adds a random hash value corresponding to the increased erase count as a leaf node of a Merkle tree corresponding to the first super block, and updates the Merkle tree corresponding to the first super block and a private key corresponding to the first super block.

10 . The storage device according to claim 8 , wherein a private key of a third super block among the plurality of super blocks is generated on the basis of a root node of a Merkle tree of the third super block and a private key of a second super block.

11 . The storage device according to claim 10 , wherein the controller updates the private key of the second super block, and thereafter, updates the private key of the third super block on the basis of the updated private key of the second super block and the root node of the Merkle tree of the third super block.

12 . The storage device according to claim 11 , wherein, when at least one private key among private keys of the plurality of respective super blocks is updated, the controller transmits private key information including the updated private key to the external device.

13 . The storage device according to claim 8 , wherein the private key information further includes the number of private keys included in the private key information and one or more dummy keys.

14 . The storage device according to claim 8 , wherein the controller receives a credibility certification request from the external device, and, as a response to the credibility certification request, transmits private keys of the plurality of respective super blocks to the external device, by further including one or more dummy keys.

15 . The storage device according to claim 14 , wherein the controller receives a credibility certification result corresponding to the credibility certification request from the external device, and is set to a normal mode or an emergency mode according to the credibility certification result.

16 . The storage device according to claim 15 , wherein the credibility certification request is received during a boot sequence operation of the controller.

17 . The storage device according to claim 8 , wherein the seed is a randomizing seed that is used for the controller to randomize data received from the external device.

18 . A method for operating a storage device, comprising:
generating a random hash value by hashing an erase count and a seed of each of a plurality of super blocks; generating a Merkle tree in which the random hash value is a leaf node, for each of the plurality of super blocks; generating a private key of each of the plurality of super blocks on the basis of a root node of the Merkle tree of each of the plurality of super blocks, and storing the private key in a memory; and transmitting private key information including the private key of each of the plurality of super blocks to an external device, wherein the erase count of each of the plurality of super blocks is a value increased when the each of the plurality of super blocks is erased.

19 . The method according to claim 18 , further comprising:
receiving a credibility certification request from the external device; transmitting a plurality of private keys and one or more dummy keys stored in the memory to the external device in response to the credibility certification request; and setting a normal mode or an emergency mode on the basis of a credibility certification result corresponding to the credibility certification request.

20 . The method according to claim 18 , further comprising:
increasing, when one super block among the plurality of super blocks is erased, an erase count of the erased super block; adding a random hash value corresponding to the increased erase count as a leaf node of a Merkle tree of the erased super block; and updating the Merkle tree of the erased super block and a private key of the erased super block.

Assignees

• Sk Hynix Inc

Inventors

• Jang In Jong

Classifications

• H04L9/0825

  using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates · CPC title

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• H04L2209/08

  Randomization, e.g. dummy operations or using noise · CPC title

• H04L9/0822

  using key encryption key · CPC title

• H04L9/50 Primary

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