Why does Kaspa sort accepted transactions before calculating AcceptedIDMerkleRoot?

Kaspa sorts accepted transactions by their hash before calculating AcceptedIDMerkleRoot as an optimization designed to enable efficient proofs of exclusion. A Merkle tree is a cryptographic structure that summarizes a set of data — in this case, transactions — into a single hash. In an unsorted Merkle tree, proving that a specific transaction was NOT included requires revealing every single node in the tree, which is costly and grows linearly with the number of transactions. In a sorted Merkle tree, you only need to show two neighboring entries — one just below and one just above the missing transaction — which is far cheaper. Kaspa built this optimization in speculatively, but for a beginner the key point is that as of now no application on Kaspa actually uses it, and the protocol designers believe it matters less than proving the order in which transactions were accepted.