Tree Arity (Binary, Quinary)

Overview of tree arity and why it matters in the context of a Merkle Tree

What is tree arity?

Arity is how many children descend from a parent node in a tree. The most common implementation is the binary tree. Trees can have any arbitrary arity depending on the specific use case however. Why does it matter in Merkle Trees though?

Why does it matter in a Merkle Tree?

When updating Merkle Trees on chain it can result in significant gas costs depending on the depth of the tree. To decrease gas costs a solution is to implement a SNARK friendly hashing functions that produces less constraints with higher arity. PoseidonT6 namely is one such function