Methods and systems for generating and updating Merkle trees for an evolving data series and applications thereof

1 . A computer-implemented method for authenticating messages relative to a hash-based data authentication structure, the computer-implemented method comprising:

producing a first signed data structure, wherein the first signed data structure comprises a first subset of a plurality of node hash values from the hash-based data authentication structure, wherein the first subset is selected according to a selected strategy and configured to authenticate messages relative to the hash-based data authentication structure;

producing a second signed data structure, wherein the second signed data structure comprises a second subset of the plurality of node hash values from the hash-based data authentication structure, wherein the second subset comprises the first subset with one or more of at least one added node hash value or at least one removed node hash value;

enabling a signed data structure provider to provide to a verifier the first signed data structure and the second signed data structure; and

enabling an authentication path provider to provide to the verifier an authentication path formed relative to the first signed data structure or the second signed data structure,

wherein the verifier determines whether to use the first signed data structure based on the authentication path, and performs a verification procedure, wherein the verifier determines whether to use the first signed data structure by:

obtaining the authentication path formed relative to the first signed data structure or the second signed data structure; and

determining, based on information associated with the authentication path, whether the authentication path can be verified relative to the first signed data structure.

2 . The computer-implemented method of claim 1 , wherein the verification procedure further comprises the verifier:

obtaining a third signed data structure from the signed data structure provider responsive to determining that the authentication path cannot be verified relative to the first signed data structure; and

verifying the authentication path relative to the first signed data structure or the third signed data structure.

3 . The computer-implemented method of claim 1 , wherein the verification procedure further comprises the verifier:

verifying the authentication path relative to the first signed data structure responsive to determining that the authentication path can be verified relative to the first signed data structure.

4 . The computer-implemented method of claim 1 , wherein the selected strategy comprises at least one or more of a full strategy, a single strategy, a basic binary strategy, an extended binary strategy, a spaced strategy, a variable spaced strategy, a bounded strategy, a spaced and bounded strategy, a spaced extended binary strategy, and a bounded extended binary strategy.

5 . The computer-implemented method of claim 1 , wherein producing the first signed data structure comprises grouping elements that are to be added to a data series into data series batches that have identifiers that start at one greater than a highest element identifier in a current data series authenticated by the verifier.

6 . The computer-implemented method of claim 1 , further comprising creating a long-lived data structure for a data series based on a subseries of the data series that is anticipated not to change during a period of time.

7 . The computer-implemented method of claim 1 , further comprising constructing multiple data structures that can be used as authenticators for subsets of an expanding data series.

8 . The computer-implemented method of claim 1 , further comprising producing and using multiple reference values from multiple data structures, wherein the multiple data structures comprise an unbalanced data structure having subtrees from which the multiple reference values are obtained.

9 . The computer-implemented method of claim 1 , further comprising performing a batch updating process using a merge method, wherein an initial authenticator is created with a number of leaves that is a largest power of two that is less than or equal to a number of resource record sets in a data series.

10 . The computer-implemented method of claim 1 , wherein the selected strategy authenticates long-lived data elements that are anticipated not to change during a period of time, and wherein another strategy authenticates changing data elements.

11 . The computer-implemented method of claim 1 , further comprising publishing the plurality of node hash values in the first signed data structure as synthesized public keys.

12 . The computer-implemented method of claim 11 , wherein at least one of the synthesized public keys is used as at least one of: a domain name system security extension (DNSSEC) key signing key or a DNSSEC zone signing key.

13 . The computer-implemented method of claim 1 , further comprising publishing, in an internet public key infrastructure (PKI) as a synthesized public key, information sufficient to validate the plurality of node hash values in at least one of the first signed data structure or the second signed data structures.

14 . A computer-implemented method for authenticating messages relative to a hash-based data authentication structure, the computer-implemented method comprising:

obtaining, from a signed data structure provider, a first signed data structure, wherein the first signed data structure comprises a first subset of a plurality of node hash values from the hash-based data authentication structure, wherein the first subset is selected according to a selected strategy and configured to authenticate messages relative to the hash-based data authentication structure;

obtaining, from an authentication path provider, an authentication path formed relative to a second signed data structure, wherein the second signed data structure comprises a second subset of the plurality of node hash values from the hash-based data authentication structure, wherein the second subset comprises the first subset with one or more of at least one added node hash value or at least one removed node hash value;

determining, based on information associated with the authentication path, whether the authentication path can be verified relative to the first signed data structure;

responsive to determining that the authentication path cannot be verified relative to the first signed data structure, obtaining, from the signed data structure provider, a third signed data structure, wherein the third signed data structure is a modified version of the first signed data structure; and

verifying the authentication path relative to the first signed data structure or the third signed data structure, and wherein verifying the authentication path comprises:

obtaining the authentication path formed relative to the first signed data structure or the second signed data structure; and

determining, based on information associated with the authentication path, whether the authentication path can be verified relative to the first signed data structure.

15 . The computer-implemented method of claim 14 , wherein the selected strategy comprises at least one or more of a full strategy, a single strategy, a basic binary strategy, an extended binary strategy, a spaced strategy, a variable spaced strategy, a bounded strategy, a spaced and bounded strategy, a spaced extended binary strategy, and a bounded extended binary strategy.

16 . The computer-implemented method of claim 14 , further comprising publishing the first subset as synthesized public keys.

17 . The computer-implemented method of claim 1 , wherein the first subset is selected from a plurality of levels of the hash-based data authentication structure.

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

the first subset is associated with a first range of node hash value identifiers,

the second subset is associated with a second range of node hash value identifiers, and

determining whether to use the first signed data structure comprises:

determining a third range represented by the authentication path, and

determining whether the third range corresponds to the first range.