Data structure for orphan transactions

A computer program embodied on non-transitory computer-readable storage media and configured so as, when run on one or more processors, the one or more processors perform a method comprising:

• maintaining a data structure representing orphan transactions, wherein:
• an orphan transaction is a blockchain transaction having at least one parent transaction that is one of an unavailable transaction and a different orphan transaction;
• an unavailable transaction is a transaction that is not available to a validation pipeline of a blockchain node;
• the data structure comprises a directed graph of nodes and edges, wherein each node of the graph represents either a respective orphan transaction or a respective unavailable transaction, wherein each edge connecting a respective parent node to a respective child node represents the spending of an output of the respective transaction represented by the respective parent node by an input of the respective transaction represented by the respective child node;
• and
• each node of the graph is associated with a respective transaction identifier of the respective transaction represented by that node and comprises:
• a) a respective indegree value that is one of:
• (i) a first value indicating that the respective transaction has an unknown number of parent transactions that are either unavailable transactions or orphan transactions;
• (ii) a zero value indicating that the respective transaction has no parent transactions that are either unavailable transactions or orphan transactions;
• and
• (iii) a value indicating the number of respective parent transactions of the respective transaction that are either unavailable transactions or orphan transactions;
• and
• b) a list of respective references of respective child nodes, if any, that are connected to that node by respective edges.

A data structure embodied on non-transitory computer readable media and representing orphan transactions, wherein an orphan transaction is a blockchain transaction having at least one parent transaction that is an unavailable transaction and/or at least one parent transaction that is a different orphan transaction, wherein an unavailable transaction is a transaction that is not available to a validation pipeline of a blockchain node, and wherein:

• the data structure comprises a directed graph of nodes and edges, wherein each node of the graph represents either a respective orphan transaction or a respective unavailable transaction, wherein each edge connecting a respective parent node to a respective child node represents the spending of an output of the respective transaction represented by the respective parent node by an input of the respective transaction represented by the respective child node;
• and
• wherein each node of the graph is associated with a respective transaction identifier of the respective transaction represented by that node and comprises:
• a) a respective indegree value, wherein the respective indegree value is one of:
• i) a first value indicating that the respective transaction has an unknown number of parent transactions that are either unavailable transactions or orphan transactions, or
• ii) a zero value indicating that the respective transaction has no parent transactions that are either unavailable transactions or orphan transactions, or
• iii) a value indicating the number of respective parent transactions of the respective transaction that are either unavailable transactions or orphan transactions;
• and
• b) a list of respective references of respective child nodes, if any, that are connected to that node by respective edges.