Hash subtrees for grouping components by component type
AssigneeR3 Ltd.
InventorsKonstantinos Chalkias, Michael Christopher Hearn, Rick Parker, Andrius Dagys
Life of this patent
Estimating the term…
Abstract
A system for generating a hash tree with components grouped by component type is provided. Each non-leaf node of the hash tree has a hash of the hashes of its child nodes, and a leaf node has a hash of a component of the hash tree. The system generates, for each component type, a component subtree for that component type based on the leaf nodes that have hashes of the components of that component type. The system then generates a root subtree of the hash tree based on leaf nodes that are the root nodes of the component subtrees. The combination of the root subtree and the component subtrees form the hash tree.
Claims36
A method performed by a computing system for generating a hash tree of nodes having hashes, a non-leaf node having a hash of the hashes of its child nodes and a leaf node having a hash of a component of the hash tree, the method comprising:
- accessing an indication of components of the hash tree, each component having a component type;
- for each component type, generating a component subtree for that component type based on the hashes of the components of that component type;
- and
- generating a root subtree of the hash tree with root nodes of the component subtrees being leaf nodes of the root subtree.
A method performed by a computing system for generating a hash tree of nodes, a non-leaf node having a hash of the hashes of its child nodes and a leaf node having a hash of a component, the method comprising:
- when a target component includes fields,
- for each field, generating a target subcomponent that includes the field;
- generating a referencing component that includes a reference to each target subcomponent;
- and
- including in the hash tree the target subcomponents and the referencing component in place of the target component.
A computing system comprising:
- one or more computer-readable storage mediums storing executable instructions for controlling the computing system to generate a hash tree of nodes having hashes, a non-leaf node having a hash of the hashes of its child nodes and a leaf node having a hash of a component of the hash tree, each component having a component type, the generating comprising:
- for each component type, generating a component subtree for that component type based on the hashes of the components of that component type;
- and
- generating a root subtree of the hash tree with root nodes of the component subtrees being leaf nodes of the root subtree;
- and
- one or more processors for executing the instructions stored in the one or more computer-readable storage mediums.
One or more computer-readable storage mediums storing a hash tree, the hash tree comprising:
- components of the hash tree, each component having a component type;
- for each component type, a component subtree for that component type based on the hashes of the components of that component type;
- and
- a root subtree of the hash tree with root nodes of the component subtrees being leaf nodes of the root subtree.
One or more computer-readable storage mediums storing a portion of a hash tree of nodes having hashes, a non-leaf node having a hash of the hashes of its child nodes and a leaf node having a hash of a component of the hash tree, each component having a component type, the hash tree including a component subtree for each component type, the portion comprising:
- each component that is to be visible;
- a root node of the hash tree;
- and
- for each component type,
- a root node of the component subtree of that component type;
- and
- a root node of each highest-level subtree of the component subtree of that component type for which each component of that component subtree is not visible.
A method performed by a computing system for verifying that all components of a component type of a hash tree of nodes are visible in a portion extracted from the hash tree, the hash tree has components grouped by component type, the hash tree having a component root node of a component subtree for the component type, the method comprising:
- for each component of the component type that is included in the portion, generating a hash of the component;
- and
- generating a leaf node that indicates the hash of that component;
- generating a component hash tree from the generated leaf nodes;
- and
- when a root hash of the generated component hash tree matches the component root hash of the component subtree of the portion, indicating that all components of the component type are visible in the portion.
Dependencies are inferred from the claim text.