Authenticated index data structure with back-pointers

1. A computing device of a decentralized network comprising:

a network interface configured to couple the computing device to the decentralized network;

a hardware processor; and

a non-transitory computer readable storage medium storing program instructions for execution by the hardware processor in order to cause the computing device to:

detect an addition of a first block in a fork of a blockchain via the decentralized network, wherein the first block stores a plurality of transactions, and wherein the fork comprises a prior block;

generate an adaptive radix trie (ART) for the first block, wherein the ART comprises a root node;

determine that a first transaction in the plurality of transactions corresponds to a first key and a first value;

determine a path based on a hash of the first key;

determine that the path shares a prefix with a second path corresponding to a second node in a second ART for the prior block;

modify the ART for the first block to include a child of the root node that is a back-pointer that references the second node in the second ART for the prior block;

copy the second node; and

replace the back-pointer with the copy of the second node, wherein the copy of the second node is a child node of the root node.

2. The computing device of claim 1 , wherein a third node is a child of the second node in the second ART, and wherein the program instructions, when executed, further cause the computing device to modify the modified ART to include a child of the copy of the second node that is a second back-pointer to the third node.

3. The computing device of claim 2 , wherein the program instructions, when executed, further cause the computing device to:

determine that a portion of the path and a portion of a third path corresponding to the third node match;

copy the third node; and

replace the second back-pointer with the copy of the third node such that the copy of the third node is a child node of the copy of the second node.

4. The computing device of claim 3 , wherein a fourth node is a child of the third node in the second ART, and wherein the program instructions, when executed, further cause the computing device to modify the second ART to include a child of the copy of the third node that is a third back-pointer to the fourth node.

5. The computing device of claim 1 , wherein the program instructions, when executed, further cause the computing device to modify the modified ART to include a child of the copy of the second node that is a leaf node representing the first transaction.

6. The computing device of claim 5 , wherein the program instructions, when executed, further cause the computing device to:

determine a value hash based on a hash of the first value; and

store the value hash in the leaf node.

7. The computing device of claim 1 , wherein the program instructions, when executed, further cause the computing device to:

determine that a second transaction in the plurality of transactions corresponds to a second key and a second value;

determine a third path based on a hash of the second key;

determine that the third path shares a prefix with the second path corresponding to the copy of the second node and a fourth path corresponding to a third node in a third ART for a third block in the fork; and

modify the modified ART for the first block to include a child of the copy of the second node that is a second back-pointer that references the third node in the third ART for the third block.

8. The computing device of claim 1 , wherein the computing device is a peer device in the decentralized network.

9. A computer-implemented method comprising:

under control of a computing device in a decentralized network,

detecting an addition of a first block in a fork of a blockchain via the decentralized network, wherein the first block stores a plurality of transactions, and wherein the fork comprises a prior block;

generating an adaptive radix trie (ART) for the first block, wherein the ART comprises a root node;

determining that a first transaction in the plurality of transactions corresponds to a first key and a first value;

determining a path based on a hash of the first key;

determining that the path shares a prefix with a second path corresponding to a second node in a second ART for the prior block;

modifying the ART for the first block to include a child of the root node that is a back-pointer that references the second node in the second ART for the prior block;

copying the second node; and

replacing the back-pointer with the copy of the second node, wherein the copy of the second node is a child node of the root node.

10. The computer-implemented method of claim 9 , wherein

a third node is a child of the second node in the second ART, and wherein the computer-implemented method further comprises modifying the modified ART to include a child of the copy of the second node that is a second back-pointer to the third node.

11. The computer-implemented method of claim 10 , further comprising:

determining that a portion of the path and a portion of a third path corresponding to the third node match;

copying the third node; and

replacing the second back-pointer with the copy of the third node such that the copy of the third node is a child node of the copy of the second node.

12. The computer-implemented method of claim 11 , wherein

a fourth node is a child of the third node in the second ART, and wherein the computer-implemented method further comprises modifying the second ART to include a child of the copy of the third node that is a third back-pointer to the fourth node.

13. The computer-implemented method of claim 9 , further comprising modifying the modified ART to include a child of the copy of the second node that is a leaf node representing the first transaction.

14. The computer-implemented method of claim 13 , further comprising:

determining a value hash based on a hash of the first value; and

storing the value hash in the leaf node.

15. Non-transitory, computer-readable storage media comprising computer-executable instructions for using back-pointers to form a materialized view of a fork in a blockchain, wherein the computer-executable instructions, when executed by a computer system in a decentralized network, cause the computer system to:

detect an addition of a first block in the fork of the blockchain via the decentralized network, wherein the first block stores a plurality of transactions, and wherein the fork comprises a prior block;

generate an adaptive radix trie (ART) for the first block, wherein the ART comprises a root node;

determine that a first transaction in the plurality of transactions corresponds to a first key and a first value;

determine a path based on a hash of the first key;

determine that the path shares a prefix with a second path corresponding to a second node in a second ART for the prior block;

modify the ART for the first block to include a child of the root node that is a back-pointer that references the second node in the second ART for the prior block;

copy the second node; and

replace the back-pointer with the copy of the second node, wherein the copy of the second node is a child node of the root node.

16. The non-transitory, computer-readable storage media of claim 15 , wherein a third node is a child of the second node in the second ART, and wherein the computer-executable instructions further cause the computer system to modify the modified ART to include a child of the copy of the second node that is a second back-pointer to the third node.

17. The non-transitory, computer-readable storage media of claim 16 , wherein the computer-executable instructions further cause the computer system to:

determine that a portion of the path and a portion of a third path corresponding to the third node match;

copy the third node; and

replace the second back-pointer with the copy of the third node such that the copy of the third node is a child node of the copy of the second node.