Maintaining blocks of a blockchain in a partitioned blockchain network
A computer-implemented method and system is provided that maintains blocks of a blockchain across nodes of a sharded blockchain network, wherein each node is a member of one or more shards of a plurality of active shards. The method and system employ a given node that is a member of a particular subset of the plurality of active shards to generate data representing a new block of the blockchain and store the data representing the new block. Such data includes i) a list of transaction identifiers for transactions that are part of the new block and associated with the particular subset of the plurality of active shards, and/or ii) a Partial Merkle Tree for the new block.
1. A computer-implemented method for maintaining blocks of a blockchain across nodes of a sharded blockchain network comprising a plurality of shards, wherein:
each node is a member of one or more shards, and each node stores a UTXO set for each shard of which it is a member and block data for all shards of which it is a member;
the method comprising, at a given node that is a member of a particular subset of the plurality of shards:
receiving a new block of the blockchain including a plurality of transactions;
generating data representing the new block, by:
generating a list of transaction identifiers for a first plurality of transactions that are part of the new block and associated with the particular subset of the plurality of shards; and
generating a Partial Merkle Tree from transaction identifiers for a second plurality of transactions that are part of the new block;
storing the data representing the new block in the block data for the shard; and
propagating the block data to other nodes in the shard;
wherein in generating the data representing the new block, the node validates transactions having an input that relates to a UTXO stored in one of its stored UTXO sets, while bypassing validation of transactions that are part of the new block and not having an input that relates to a UTXO stored in one of its stored UTXO sets.
2. The computer-implemented method according to claim 1 , wherein:
the list of transaction identifiers does not include transaction identifiers for transactions that are part of the new block and not associated with the particular subset of the plurality of shards.
3. The computer-implemented method according to claim 2 , wherein:
the list of transaction identifiers is generated by constructing an initial list of transaction identifiers for the new block based upon data included in the new block, and processing the initial list of transaction identifiers to remove any transaction identifier corresponding to a transaction that is not associated with the particular subset of the plurality of shards.
4. The computer-implemented method according to claim 1 , wherein:
the Partial Merkle Tree includes hash values derived from transactions that are part of the new block and not associated with the particular subset of the plurality of shards, while omitting hash values derived from transactions that are part of the new block and associated with the particular subset of the plurality of shards.
5. The computer-implemented method according to claim 1 , wherein:
the Partial Merkle Tree is generated by constructing a Full Merkle Tree for the new block based upon data included in the new block, and processing the Full Merkle Tree to substitute placeholders for hash values derived from transactions that are part of the new block and associated with the particular subset of the plurality of shards.
6. The computer-implemented method according to claim 5 , wherein:
processing the Full Merkle Tree further includes iterating from a bottom level to root level of the Full Merkle Tree and removing two hash values for an adjacent-node pair and leaving a parent hash value.
7. The computer-implemented method according to claim 5 , wherein:
processing the Full Merkle Tree further includes iterating from a bottom level to root level of the Full Merkle Tree and substituting a placeholder for a hash value of a parent tree node that has two child nodes which do not both represent a hash value derived from transactions that are not associated with the particular subset of the plurality of shards.
8. The computer-implemented method according to claim 1 , further comprising:
operating the node to process the Partial Merkle Tree to compute a Merkle root hash value for block validation without requiring access to the transactions that are part of the block and not associated with the particular subset of the plurality of shards.
9. The computer-implemented method according to claim 8 , wherein:
processing of the Partial Merkle Tree to compute the Merkle root hash value iterating from a lower level to root level of the Partial Merkle Tree and replacing a placeholder with a hash value calculated from corresponding child hash values of the Partial Merkle Tree.
10. The computer-implemented method according to claim 1 , wherein:
the transaction identifier list and the Partial Merkle Tree vary amongst the nodes based on node membership and an allocation of the transactions amongst the shards.
11. A system, comprising:
a processor; and
memory including executable instructions that, as a result of execution by the processor, cause the system to perform at least part of the computer-implemented method of claim 1 .
12. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to perform at least part of the computer-implemented method of claim 1 .