High performance distributed system of record with unspent transaction output (UTXO) database snapshot integrity

Patent metadata

Field	Value
Publication number	US-11720453-B2
Application number	US-202017011626-A
Country	US
Kind code	B2
Filing date	Sep 3, 2020
Priority date	Apr 28, 2020
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

A method operative in association with a set of transaction handling computing elements that comprise a network core that receive and process transaction requests into an append-only immutable chain of data blocks, wherein a data block is a collection of transactions, and wherein presence of a transaction recorded within a data block is verifiable via a cryptographic hash, and wherein Unspent Transaction Output (UTXO) data structures supporting the immutable chain of data blocks are maintained in a UTXO database, wherein a UXTO is an output from a finalized transaction that contains a value. The technique herein includes periodically snapshotting a given portion of the UTXO database to generate a hash. The hash of the snapshot is recorded within the immutable chain of data blocks, and preferably within a given block header. In responsive to a receipt of a recovery request, and to facilitate recovery of the system to a provably-known state, a consensus algorithm is executed over the UXTO snapshot.

First claim

The invention claimed is:

1. A method operative in association with a set of transaction handling computing elements that comprise a network core that receive and process transaction requests into an append-only immutable chain of data blocks, wherein a data block is a collection of transactions, and wherein presence of a transaction recorded within a data block is verifiable via a cryptographic hash, and wherein Unspent Transaction Output (UTXO) data structures supporting the immutable chain of data blocks are maintained in a UTXO database, wherein a UXTO is an output from a finalized transaction that contains a value, comprising:
as the append-only immutable chain of data blocks is being generated, periodically snapshotting a given portion of the UTXO database to generate a snapshot;
applying a given function to the snapshot to generate a hash of the snapshot;
recording the hash of the snapshot within the immutable chain of data blocks at a location that is downstream of a block at which the snapshot was initiated, wherein the location is determined based on a number of UTXOs in the given portion; and
responsive to a receipt of a recovery request, executing a consensus algorithm over the UXTO snapshot to recover the given portion of the UTXO database.

2. The method as described in claim 1 wherein the given portion of the UTXO database is a shard of the UTXO database.

3. The method as described in claim 1 wherein the append-only immutable chain of data blocks is a blockchain.

4. The method as described in claim 1 wherein the hash certifies authenticity of the snapshot.

5. The method as described in claim 1 wherein the hash is recorded into a block header of a block in the append-only immutable chain of data blocks.

6. The method as described in claim 5 wherein the hash is included in a hash used to form a next block of the append-only immutable chain of data blocks at the location.

7. The method as described in claim 1 wherein the recovery request is associated with an attempt to restore the set of transaction handling computing elements into a provably-known state.

8. The method as described in claim 7 wherein a restore into the provably-known state includes:
obtaining the snapshot, together with a chain of transactions included in the immutable chain of data blocks while the snapshot was being created and the hash recorded therein;
restoring the UTXO database;
while the UTXO database is being restored, re-generating the hash of the snapshot;
replaying each of the transactions generated starting with a first block, and continuing until a given block that contains the snapshot hash is reached; and
verifying the re-generated snapshot hash and the hash of the given block.

9. The method as described in claim 1 wherein at least one UTXO data structure is configured to include information either in addition to or in lieu of an address and value to define a Transaction Output (TXO).

10. The method as described in claim 9 wherein the TXO has an associated type.

11. The method as described in claim 10 wherein the associated type is one of: a Reference TXO (RTXO), and an idempotency TXO (ITXO).

12. A method operative in association with a set of transaction handling computing elements that comprise a network core that receive and process transaction requests into an append-only immutable chain of data blocks, wherein a data block is a collection of transactions, and wherein presence of a transaction recorded within a data block is verifiable via a cryptographic hash, and wherein Unspent Transaction Output (UTXO) data structures supporting the immutable chain of data blocks are maintained in a UTXO database, wherein a UXTO is an output from a finalized transaction that contains a value, comprising:
sharding the UTXO database into a set of partitions;
storing each partition of the UTXO database independently from other partitions in the set of partitions;
for at least one partition:
periodically snapshotting UTXOs therein to generate a hash;
recording the hash of the snapshot within the immutable chain of data blocks at a location that is downstream of a block at which the snapshot was initiated, wherein the location is determined based on a number of UTXOs in the partition; and

responsive to a receipt of a recovery request, executing a consensus algorithm over the UXTO snapshot for the at least one partition.

13. The method as described in claim 12 wherein the recovery request is associated with an attempt to restore the set of transaction handling computing elements into a provably-known state.

14. The method as described in claim 13 wherein a restore into the provably-known state includes:
for the at least one partition:
obtaining the snapshot, together with a chain of transactions included in the immutable chain of data blocks while the snapshot was being created and the hash recorded therein;
restoring the UTXO database;
while the UTXO database is being restored, re-generating the hash of the snapshot;
replaying each of the transactions generated starting with a first block, and continuing until a given block that contains the snapshot hash is reached; and
verifying the re-generated snapshot hash and the hash of the given block.

15. The method as described in claim 12 further including snapshotting at least one other partition of the set of partitions.

16. The method as described in claim 15 further computing a checksum for a UTXO snapshot that comprises the at least one partition and the at least one other partition.

17. The method as described in claim 15 wherein the at least one partition and the at least other partition are snapshotted concurrently.

Assignees

• Akamai Tech Inc

Inventors

• Sears William R
• Alshenibr Leen
• Erb Samuel

Classifications

• G06F11/1474 Primary

  in transactions (updating of structured data in databases G06F16/23) · CPC title

• G06F11/1004

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F21/64

  Protecting data integrity, e.g. using checksums, certificates or signatures · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title