Using Merkle trees at Paylias

Merkle trees are pretty cool.

For a while now I’ve been searching for an efficient solution to the problem of clearing payments between parties on-chain.

Allow me first to describe the problem and then I'll explain how Merkle trees fit into our solution.

Setting the stage

At Paylias we’re building a payment network that runs as an alternative to existing networks like Visa and Mastercard. Unlike these traditional networks that work with banks which in turn issue credentials to their customers in the form of primary account numbers (PANs), Paylias works with fintechs, challenger banks and marketplaces that issue aliases to their customers.

At its core though the premise remains the same. Just like these other networks, Paylias allows customers to make and receive payments. The key difference however is that the actual money movement never touches traditional payment rails. Instead we rely on stablecoins to facilitate the transfer of value between the participant members on Paylias.

This is where the problem arises. Bear with me a little more and I promise we’ll get to see how Merkle trees fit into the solution.

Paylias facilitates both push and pull payments through aliases meaning that a customer, John, that uses a hypothetical challenger bank, Accrue, can push money to his friend Alice's alias, alice@paymo, who uses a hypothetical mobile wallet, Paymo. Similarly a merchant that uses a hypothetical payment processor, Safepay, can pull funds from a customers wallet at the hypothetical Newbank when the customer enters their alias patrick@newbank on the checkout page.

At the end of every day (or more generally a cutoff window), Paylias aggregates all transactions and calculates the net position between different participants.

To visualize this let’s assume that there are three participants; Accrue, New Bank and Safepay. Throughout the day, their customers make a total of 10 transactions between each other.

Transaction Log

Based on this log we can calculate how much each participant owes and to whom by grouping all transactions as payables and receivables.

Who Owes What and to Whom

We can now go a step further and calculate the total amount owed by and owed to each participant across all payables and receivables

Net Position Summary

So what's the problem?

Here’s where things get interesting. If Safepay, New Bank and Accrue were to settle this using traditional payment rails like ACH, Wires or even RTP, they would submit a batch file in a prescribed format to their bank based on the calculations in the Who Owes What and to Whom (second) table. Their bank would run the file through the clearing network of choice which would debit the payer account and credit the receiver account.

Paylias could do this as well. We can generate a payout file for each participant with line items detailing how much to send and to whom. The participants could run this file through their banks and the network could clear.

However, this would still mean that the actual money movement relies on traditional payment rails and not the blockchain. And with such an amazing piece of technology available, it would be a shame not to use it — especially since it’s designed for this very purpose!

But if New Bank were to submit a list of its payables to a smartcontract on the blockchain this would be very inefficient since it would involve looping through a list of payables. Now extrapolate that to potentially hundreds of payables across a few thousand participants and you’ve got a nightmare of high gas fees!

Merkle trees (finally)

I had heard about Merkle trees and knew that they were used as a data structure in programming for quite some time but I never delved too deep into their inner workings or actual use cases. I won’t provide you with a technical explanation of what Merkle trees are — the internet will do a much better job than I could — but I will say that, in the case of Paylias, Merkle trees can prove ownership of a participant in a daily settlement round.

Here’s a very contrived example of how Merkle trees work

Imagine a forest accountant verifying who gets paid in a village.

• Everyone writes their name and how much they’re owed on a note.
• The accountant seals each note with a wax stamp (hash).
• Pairs of notes are bundled and sealed again — this repeats until there’s one final seal at the top (the Merkle Root).
• The accountant publishes just this final seal in the village square.

Now someone comes and says, “I’m owed 10 coins!”

To prove it:

• They show their original note
• Plus the seals from their siblings all the way up to the top

The accountant can rebuild the entire top seal using those and say: “Yes, this matches the public seal — you are indeed owed this amount.”

So how does this apply to Paylias to solve network clearing using stablecoins on the blockchain? Glad you asked!

At the end of every round Paylias generates a Merkle tree based on the data in the Net Position Summary (third) table and submits the root of the tree to a smartcontract. Then, sibling hashes, collectively called proofs are made available to each participant along with how much they owe or are owed. For example, a sample JSON representation available through the Paylias might look like this

{
  "partner_id": "part_94e85f55-1a04-4a79-9134-c4ce3a9d665d",
  "amount": "1500000",
  "kind": "creditor",
  "proof": [
    "0x9a8f...",
    "0xbe32...",
    "0x71ef...",
    "0x23ab..."
  ]
}

Suppose Paylias is a network of 7 participants. Here is what the Merkle tree would look like

         Root
       /      \
     H01       H23
    /  \       /  \
  H0   H1    H2   H3
 / \   / \   / \   / \
L0 L1 L2 L3 L4 L5 L6 L7

If you’re at position L3

• Your data: Tx3 = L3
• Your sibling at level 0 is L2
• At the next level: H0
• At the next level: H23 (opposite subtree)

So your Merkle proof is [L2, H0, H23]

Knowing this, each participant can deposit their payables or withdraw their receivables.

To withdraw:

1. You prove: “I am address A and I’m owed 100 USDC”
2. You provide:
   • The amount
   • The Merkle proof (siblings up the tree)
3. The smartcontract computes the Merkle root and compares with the stored root
4. If it matches, you get paid!

To deposit we can follow the same logic: the debtor provides a Merkle proof proving they owe an exact amount, then deposits it.

Here is an example Solidity function that verifies the Merkle proofs once a participant calls the deposit or withdraw function

/// @dev Standard Merkle proof verification (sorted pair hashing)
function verifyMerkleProof(bytes32[] memory proof, bytes32 root, bytes32 leaf) public pure returns (bool) {
    bytes32 computedHash = leaf;
    for (uint256 i = 0; i < proof.length; i++) {
        bytes32 proofElement = proof[i];
        computedHash = computedHash <= proofElement
            ? keccak256(abi.encode(computedHash, proofElement))
            : keccak256(abi.encode(proofElement, computedHash));
    }
    return computedHash == root;
}

Why is this better? Well for starters we've replaced a potentially large list of payables with a much smaller list of proofs. But secondly, this is scalable! With a Merkle tree verifying 10 or 10,000 entries still takes only O(log n). Additionally, if the smartcontract were to, for instance, loop through a list of mapping(address => uint256) representing a list of payment obligations for a specific debitor, there is a high probability that some calls to stablecoin.transferFrom would fail. Using our Merkle tree approach prevents this.

If we attempt to calculate potential storage sizes of the Merkle tree on chain and gas costs of verifying each participants claims, we can see the potential benefits.

The size of a Merkle proof depends on the number of leaves in the tree, specifically: Proof size=log 2​(n)

Where:

• n = number of participants
• Each proof element is a bytes32 type = 32 bytes

Gas estimate includes proof verification only, not transfer

Ethereum block gas limits are currently ~30 million gas, so a proof of 500–600 bytes is trivially acceptable — especially since each withdraw() and deposit() call is a separate on-chain transaction.

Using Merkle trees allows for on-chain settlement between different participants allowing them to clear their obligations, crucially in a trustless way without the need for intermediary banks. Participants can transparently see who has and has not cleared their dues and the network can continue to clear with minimal intervention around the clock.

If you’re interested in learning more I’d love to tell you about what we’re building and the opportunities we see ahead for Paylias! You can reach out to me at ziyad@paylias.xyz