{"id":105665,"date":"2023-02-06T18:15:13","date_gmt":"2023-02-06T18:15:13","guid":{"rendered":"https:\/\/www.dash.org\/?p=105665"},"modified":"2023-02-06T18:15:13","modified_gmt":"2023-02-06T18:15:13","slug":"grovedb-sum-trees","status":"publish","type":"post","link":"https:\/\/www.dash.org\/blog\/grovedb-sum-trees\/","title":{"rendered":"GroveDB Sum Trees"},"content":{"rendered":"

One of the innovative features of Dash Platform<\/a> that we at Dash Core Group are excited to present is a GroveDB feature called <\/span>sum trees<\/span><\/i>. GroveDB sum trees are Merkle AVL trees whose root nodes hold the sum of all integer values in the tree. Any time a value is added, removed, or updated in a sum tree, every parent node and hence the root\u2019s \u201csum value\u201d is updated. Sum trees are a very powerful tool for trustlessly and efficiently retrieving the sum of a set or range of values, as it would take a relatively large, often enormous, amount of computing resources to achieve otherwise. In turn, vital security checks are made highly efficient and simple, and a whole new arena of use cases is opened up for dApps.<\/span><\/p>\n

Architecture<\/span><\/h2>\n

Sum trees have a simple architecture. In addition to the hashes of regular Merkle tree nodes, each node in a sum tree holds a \u201csum value\u201d and an optional \u201csum item\u201d. A <\/span>sum item<\/b> is a key-value pair where the value is a signed integer. It can represent anything that has an integer value, such as an identity\u2019s credit balance or the number of unsold tickets remaining for a concert. A <\/span>sum value<\/b> is the value of a node\u2019s own sum item plus the sum values of its child nodes.<\/span><\/p>\n

\"An<\/p>\n

 <\/p>\n

As illustrated in the diagram above, the sum tree leaf nodes\u2019 sum items are equal to their sum values. There\u2019s nothing to sum. Moving up a layer, each parent node has their own sum item (which is optional, as will be explained next) and a sum value, which is the sum of their child nodes\u2019 sum values plus their own sum item. This structure repeats itself from the leaves up to the tree\u2019s root node, where the entire tree\u2019s sum value is held.<\/span><\/p>\n

Note that all sum tree nodes hold sum values but don\u2019t need to hold a sum item. In other words, you can still hold any type of element in the tree, such as a key-value pair with a string value, a non-sum subtree, or even an integer value that isn\u2019t a sum item. These elements won\u2019t affect the sum value of the tree. You\u2019re therefore able to collect sums in the same tree you use to prove the existence of non-sum elements with Merkle proofs.<\/span><\/p>\n

Application<\/span><\/h2>\n

The general use case for sum trees is to trustlessly and efficiently retrieve the sum of a set or range of values. Developers can implement sum trees in their projects built on Dash Platform or any other platform which implements GroveDB. This section will walk through some example use cases.<\/span><\/p>\n

The Dash Platform engine itself uses sum trees to store the balances of all identities and reward distribution pools, and constantly checks them to ensure there are no inflationary or other bugs present. This is actually a huge innovation for blockchains, as inflationary bugs have been rather common and destructive to blockchains in the past. These checks provide a strong layer of security against them. Dash Platform runs these sum tree checks on every block submitted to consensus, and any which don\u2019t pass are prevented from entering the state.<\/span><\/p>\n

\"Sum<\/p>\n

 <\/p>\n

To illustrate the massive efficiency gains sum trees enable, say you have a tree which contains the number of restaurants that accept Dash in each city of a US state. The root of the tree would be the total number of Dash-accepting restaurants in the state. If you\u2019re a true Dash fanatic, you could compare the root sum value of that state\u2019s tree with those of all the other states to help you determine which state to live in. Say that every city in the US has at least one restaurant that accepts Dash. With sum trees, to get this information, you would only need to query the root node of each state\u2019s tree (50 states), verify the proofs, and compare the values. With regular Merkle trees, you\u2019d need to query every city in every state (over 100,000 cities), verify the proofs for each city, add the values up yourself for each state, and then compare.<\/span><\/p>\n

 <\/p>\n

The efficiency savings in the example above are on the order of 2,000 times. Two other real-world applications where sum trees would be beneficial are:<\/span><\/p>\n