Hash tree computation device
AssigneeKoninklijke Philips N.V.
InventorMeilof Geert Veeningen
Life of this patent
Estimating the term…
Abstract
Some embodiments are directed to a hash tree computation device. The hash tree computation device computes a top hash of a hash tree. A hash preimage of a leaf node of the hash tree comprises a type of the leaf node. A hash preimage of an internal node of the hash tree comprises a type count comprising a number of descendants of the internal node having a given type. The hash tree computation device computes the top hash by computing hashes of a current node and of its ancestors, where a hash of an ancestor is computed based on its type count, the type count being computed from types or type counts of its descendants.
Claims16
A hash tree computation device configured to compute a top hash of a hash tree with respect to a current node, the current node having a given type, the current node being a leaf node, a node of the hash tree having a hash, the top hash being a hash of a root node of the hash tree, a hash preimage of a leaf node of the hash tree comprising a content of the leaf node and a type of the leaf node, a hash preimage of an internal node of the hash tree comprising a type count of the internal node and at least one hash of a child of the internal node, a type count of an internal node of the hash tree comprising a number of descendants of the internal node having the given type, the hash tree computation device comprising
- a memory,
- a processor configured to
- obtain a hash preimage of the current node, a set of hashes of proof nodes from a set of proof nodes, and a set of types or type counts of proof nodes from the set of proof nodes, the set of proof nodes comprising siblings of the current node and siblings of ancestors of the current node,
- compute a hash of the current node and a set of hashes of ancestors of the current node, the computed hashes comprising the top hash, computing a hash of an ancestor of the current node comprising computing a type count of said ancestor from types or type counts of children of said ancestor, the children of said ancestor being comprised in the set of proof nodes and the current node,
- store the computed top hash in the memory.
A proof verification device configured to verifying correctness of a set of result nodes with respect to a known top hash of a hash tree, a node of the hash tree having a hash, the top hash being a hash of a root node of the hash tree, a hash preimage of a leaf node of the hash tree comprising a content of the leaf node and a type of the leaf node, a hash preimage of an internal node of the hash tree comprising a type count of the internal node and at least one hash of a child of the internal node, a type count of an internal node of the hash tree comprising a number of descendants of the internal node having the given type, a set of result nodes comprising leaf nodes of the hash tree having a given type, the size of the set of result nodes matching the type count of the root node of the hash tree, the proof verification device comprising
- a communication interface configured for digital communication with a hash tree computation device,
- a processor configured to
- receive from the hash tree computation device a cryptographic verifiable computation proof, the hash tree computation device obtaining the set of result nodes and iteratively repeating a computation comprising selecting a current node from the set of result nodes and computing a hash of the current node and a set of hashes of ancestors of the current node, the current node having the given type, the current node being a leaf node, the computed hashes comprising the top hash, computing a hash of an ancestor of the current node comprising computing a type count of said ancestor from types or type counts of children of said ancestor, said computing of the hash and the set of hashes being performed as a verifiable computation, the cryptographic verifiable computation proof proving that said computing was performed correctly,
- verifying the cryptographic verifiable computation proof with respect to the given type and the known top hash.
A hash tree providing device configured to provide a set of result nodes of a hash tree to a hash tree computation device, the set of result nodes comprising leaf nodes of the hash tree having a given type, a node of the hash tree having a hash, a hash preimage of a leaf node of the hash tree comprising a content of the leaf node and a type of the leaf node, a hash preimage of an internal node of the hash tree comprising a type count of the internal node and at least one hash of a child of the internal node, a type count of an internal node of the hash tree comprising a number of descendants of the internal node having the given type, the hash tree providing device comprising
- a memory configured to store hash preimages of leaf nodes of the hash tree and hashes and types or type counts of nodes of the hash tree,
- a communication interface configured for communication with the hash tree computation device,
- a processor configured to
- obtain the given type and determine the set of result nodes, the size of the set of result nodes matching the type count of the root node of the hash tree,
- iteratively repeat a computation comprising
- selecting a current node from the set of result nodes,
- retrieving from the memory a hash preimage of the current node and proof information about a set of proof nodes, the set of proof nodes comprising siblings of the current node and siblings of ancestors of the current node, the proof information in at least one iteratively repeated computation comprising at least one of a hash, a hash preimage, a type, and a type count of a proof node from the set of proof nodes,
- sending the hash preimage and the proof information to the hash tree computation device.
A hash tree computation method configured for computing a top hash of a hash tree with respect to a current node, the current node having a given type, the current node being a leaf node, a node of the hash tree having a hash, the top hash being a hash of a root node of the hash tree, a hash preimage of a leaf node of the hash tree comprising a content of the leaf node and a type of the leaf node, a hash preimage of an internal node of the hash tree comprising a type count of the internal node and at least one hash of a child of the internal node, a type count of an internal node of the hash tree comprising a number of descendants of the internal node having the given type, the hash tree computation method comprising
- obtaining a hash preimage of the current node, a set of hashes of proof nodes from a set of proof nodes, and a set of types or type counts of proof nodes from the set of proof nodes, the set of proof nodes comprising siblings of the current node and siblings of ancestors of the current node,
- computing a hash of the current node and a set of hashes of ancestors of the current node, the computed hashes comprising the top hash, computing a hash of an ancestor of the current node comprising computing a type count of said ancestor from types or type counts of children of said ancestor, the children of said ancestor being comprised in the set of proof nodes and the current node,
- storing the computed top hash in a memory.
Dependencies are inferred from the claim text.