Architecture<\/span><\/h2>\nSum 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<\/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>\nNote 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