Granted Patent B2

US 11,687,592 · App. 17/332,974 · Granted Jun 27, 2023

Inventors: Shay Benisty (Beer Sheva, IL); Ishai Ilani (Dolev, IL); Tomer Geron (Tel Aviv, IL)

Assignee: Western Digital Technologies, Inc.

G06F16/9027G06F12/0238

Abstract

Claims (243)

1. A computer-implemented method for storing Merkle tree data in a random access memory circuit comprised of memory cells associated with corresponding memory addresses, wherein the Merkle tree data comprises uncle node data, first nephew node data and second nephew node data, the computer-implemented method comprising:

determining a first nephew node memory address by calculating, by a processor configured to store data in the random access memory circuit and using a Merkle tree memory assignment function, a first nephew node memory address indicator based on a first node position vector for a first nephew node that is associated with the first nephew node data;

determining a second nephew node memory address by calculating, by the processor and using the Merkle tree memory assignment function, a second nephew node memory address indicator based on a second node position vector for a second nephew node that is associated with the second nephew node data;

storing, by the processor, the uncle node data at an uncle node memory address;

storing, by the processor, the first nephew node data at the first nephew node memory address; and

storing, by the processor, the second nephew node data at the second nephew node memory address.

2. The computer-implemented method of claim 1 , wherein the uncle node data comprises a hash of a sum of the first nephew node data and the second nephew node data.

3. The computer-implemented method of claim 1 , wherein the uncle node memory address is between the first nephew node memory address and the second nephew node memory address.

4. The computer-implemented method of claim 1 , further comprising determining the uncle node memory address by calculating, using the Merkle tree memory assignment function, an uncle node memory address indicator based on a third node position vector for an uncle node that is associated with the uncle node data.

5. The computer-implemented method of claim 1 , wherein:

storing the uncle node data at the uncle node memory address comprises storing a part of the uncle node data at the uncle node memory address,

storing the first nephew node data at the first nephew node memory address comprises storing a part of the first nephew node data at the first nephew node memory address, and

storing the second nephew node data at the second nephew node memory address comprises storing a part of the second nephew node data at the second nephew node memory address.

6. The computer-implemented method of claim 1 , wherein:

the uncle node data comprises data associated with a first level of a Merkle tree,

the first nephew node data comprises data associated with a second level of the Merkle tree, and

the second nephew node data comprises data associated with the second level of the Merkle tree.

7. The computer-implemented method of claim 1 , wherein:

storing the uncle node data at the uncle node memory address is performed before storing the first nephew node data at the first nephew node memory address, and

storing the uncle node data at the uncle node memory address is performed before storing the second nephew node data at the second nephew node memory address.

8. The computer-implemented method of claim 1 , wherein:

storing the first nephew node data at the first nephew node memory address is performed before storing the uncle node data at the uncle node memory address, and

storing the first nephew node data at the first nephew node memory address is performed before storing the second nephew node data at the second nephew node memory address.

9. The computer-implemented method of claim 1 , wherein:

storing the second nephew node data at the second nephew node memory address is performed before storing the uncle node data at the uncle node memory address, and

storing the second nephew node data at the second nephew node memory address is performed before storing the first nephew node data at the first nephew node memory address.

10. The computer-implemented method of claim 1 , wherein:

the first nephew node memory address indicator is mt([i 1 , i 2 , . . . , i k−1 , i k ]);

the Merkle tree memory assignment function is:

mt

⁡

(

[

i

1

,

⁠

i

2

,

⁠

…

,

⁠

i

k

-

1

,

⁠

i

k

]

)

⁠

=

⁠

[

⁠

∑

j

=

0

k

-

1

(

-

1

)

i

j

×

2

d

-

j

]

-

(

-

1

)

i

k

×

2

d

-

k

+

{

-

i

1

-

1

,

k

=

1

i

1

-

2

,

k

>

1

;

[i 1 , i 2 , . . . , i k−1 , i k ] is the first node position vector;

i 1 is a first layer position of a linked higher level node of a first level of a Merkle tree;

i 2 is a second layer position of a linked higher level node of a second level of the Merkle tree;

i k−1 is a (k−1)th layer position of an uncle node that is associated with the uncle node data, in a (k−1) th level of the Merkle tree;

i k is a kth layer position of the first nephew node in a k th level of the Merkle tree;

i 0 =0; and

d is a depth indicator that is indicative of a depth of the Merkle tree.

11. The computer-implemented method of claim 1 , further comprising:

storing the uncle node data at a range of uncle node memory addresses that comprises the uncle node memory address;

storing the first nephew node data at a range of first nephew node memory addresses that comprises the first nephew node memory address; and

storing the second nephew node data at a range of second nephew node memory addresses that comprises the second nephew node memory address.

12. The computer-implemented method of claim 11 , wherein:

memory addresses of the range of first nephew node memory addresses are less than memory addresses of the range of uncle node memory addresses, and memory addresses of the range of second nephew node memory addresses are greater than memory addresses of the range of uncle node memory addresses; or

memory addresses of the range of first nephew node memory addresses are greater than memory addresses of the range of uncle node memory addresses and memory addresses of the range of second nephew node memory addresses are less than memory addresses of the range of uncle node memory addresses.

13. The computer-implemented method of claim 11 , wherein:

the range of first nephew node memory addresses and the range of uncle node memory addresses form a first consecutive range of memory addresses, and

the range of uncle node memory addresses and the range of second nephew node memory addresses form a second consecutive range of memory addresses.

14. An apparatus for storing Merkle tree data in a random access memory circuit comprised of memory cells associated with corresponding memory addresses, wherein the Merkle tree data comprises uncle node data, first nephew node data and second nephew node data, the apparatus comprising:

a data bus configured for exchanging data with the random-access memory circuit; and

a processor configured to:

determine a first nephew node memory address by calculating, using a Merkle tree memory assignment function, a first nephew node memory address indicator based on a first node position vector for a first nephew node that is associated with the first nephew node data;

determine a second nephew node memory address by calculating, using the Merkle tree memory assignment function, a second nephew node memory address indicator based on a second node position vector for a second nephew node that is associated with the second nephew node data;

store, through the data bus, the uncle node data at an uncle node memory address in the random access memory circuit;

store, through the data bus, the first nephew node data at the first nephew node memory address in the random access memory circuit; and

store, through the data bus, the second nephew node data at the second nephew node memory address in the random access memory circuit.

15. An apparatus for storing Merkle tree data in a random access memory circuit, wherein the Merkle tree data comprises uncle node data, first nephew node data and second nephew node data, the apparatus comprising:

a processor configured to store data in the random access memory circuit;

a memory;

means, stored in the memory for execution by the processor, for determining a first nephew node memory address by calculating, using a Merkle tree memory assignment function, a first nephew node memory address indicator based on a first node position vector for a first nephew node that is associated with the first nephew node data;

means, stored in the memory for execution by the processor, for determining a second nephew node memory address by calculating, using the Merkle tree memory assignment function, a second nephew node memory address indicator based on a second node position vector for a second nephew node that is associated with the second nephew node data;

means, stored in the memory for execution by the processor, for storing the uncle node data at an uncle node memory address;

means, stored in the memory for execution by the processor, for storing the first nephew node data at the first nephew node memory address; and

means, stored in the memory for execution by the processor, for storing the second nephew node data at the second nephew node memory address.

16. The apparatus of claim 14 , wherein:

the first nephew node memory address indicator is mt([i 1 , i 2 , . . . , i k− 1, i k ]);

the Merkle tree memory assignment function is:

m

⁢

t

⁡

(

[

i

1

,

i

2

,

…

,

i

k

-

1

,

i

k

]

)

=

[

∑

k

-

1

j

=

0

(

-

1

)

i

j

×

2

d

-

j

]

-

(

-

1

)

i

k

×

2

d

-

k

+

{

-

i

1

-

1

,

k

=

1

i

1

-

2

,

k

>

1

;

[i 1 , i 2 , . . . , i k−1 , i k ] is the first node position vector;

i 1 is a first layer position of a linked higher level node of a first level of a Merkle tree;

i 2 is a second layer position of a linked higher level node of a second level of the Merkle tree;

i k−1 is a (k−1)th layer position of an uncle node that is associated with the uncle node data, in a (k−1) th level of the Merkle tree;

i k is a kth layer position of the first nephew node in a k th level of the Merkle tree;

i 0 =0; and

d is a depth indicator that is indicative of a depth of the Merkle tree.

17. The apparatus of claim 14 , wherein:

the uncle node data comprises data associated with a first level of a Merkle tree,

the first nephew node data comprises data of associated with a second level of the Merkle tree, and

the second nephew node data comprises data associated with the second level of the Merkle tree.

18. The apparatus of claim 14 , wherein:

the uncle node data is stored at a range of uncle node memory addresses that comprises the uncle node memory address,

the first nephew node data is stored at a range of first nephew node memory addresses that comprises the first nephew node memory address, and

the second nephew node data is stored at a range of second nephew node memory addresses that comprises the second nephew node memory address.

19. The apparatus of claim 18 , wherein:

memory addresses of the range of first nephew node memory addresses are less than memory addresses of the range of uncle node memory addresses and memory addresses of the range of second nephew node memory addresses are greater than memory addresses of the range of uncle node memory addresses; or

memory addresses of the range of first nephew node memory addresses are greater than memory addresses of the range of uncle node memory addresses and memory addresses of the range of second nephew node memory addresses are less than memory addresses of the range of uncle node memory addresses.

20. The apparatus of claim 18 , wherein:

the range of first nephew node memory addresses and the range of uncle node memory addresses form a first consecutive range of memory addresses, and

the range of second nephew node memory addresses and the range of uncle node memory addresses form a second consecutive range of memory addresses.

Assignments (10)