Merkleize Payer Reports?

[neekolas]

One nagging concern with Payer Reports is their potentially unbounded size. If we want a report that covers 1,000,000 messages there can theoretically be 1,000,000 payers each with a minuscule balance change.

Large reports will hit transaction size limits when submitted, and gas limits when we attempt to settle them all at once.

Merkle Trees offer the prospect of us having Payer Reports of unlimited size without hitting gas or transaction limits.

How it would work

1. When Nodes create a Payer Report they would create a Merkle Tree where each leaf represents the hash of a blob containing the payer address, their total spend in the report period, and any other metadata we want to store (maybe we want the total number of messages sent by the payer or other metadata to be used for rebate calculations)
2. The onchain payer report only contains the Merkle Root
3. The report gets enough attestations that it can be confirmed
4. Anyone can settle the usage of an individual payer (or batch of payers) by submitting the original blob and a Merkle Proof showing its inclusion in the tree. This allows us to break up a very large report into many transactions to settle if needed.

Challenges

We need to make sure that an individual payer's component of the report cannot be settled more than once. That requires some extra bookkeeping.

Some ideas:

• We maintain a list of hashes that have already been settled onchain, and then eventually delete that list when the report is completely paid out. Easiest...but adds on-chain storage cost. Still effectively unlimited in size because it allows for settlement to be broken into multiple transactions.
• We use a Sparse Merkle Tree instead of a regular Merkle Tree, and provide "update proofs" when settling individual payers. This allows the Merkle Root to change each time a set of payers is settled. Would need to figure out how the caller can know which nodes have been removed so that they can provide subsequent update proofs based on the current tree.
• Maybe there is some way to have a settlement remove an entire branch of the tree (some number of payer blobs) and replace the Merkle Root with a new hash representing the remaining branches. Would need to be provable that the new Root represents the remainder of the tree with nothing added or removed. Not sure if there is a version of Merkle Trees that supports this. Sparse Merkle Trees are close, but the updates have to be one node at a time as far as I can tell.
• Something else...?

[neekolas]

OK. I think I have an idea that is workable on paper.

We would store the Payer Reports as a standard Merkle Tree. We would also store the size of the tree (number of payers) and a mutable offset. The settleUsage function would take a batch Merkle Proof of N items. The trick is that we would enforce that the items included in the proof must be siblings and must be evaluated left to right starting from the offset. After each batch is settled we adjust the offset by the number of items in the proof.

As it happens, OpenZeppelin has a set of Merkle Tree utilities that should be helpful here, although we would need to add some more (and potentially scary) validations to make sure that the proof always starts at the offset and that all the leaves contained in the proof are siblings.

I jammed with ChatGPT on this and it all seems plausible at least. Would require very thorough auditing to verify this works as expected and can't be gamed.

[fbac]

Storing a Merkle Tree is definitely ideal, as we'd only store a bytes32 hash per PayerReport.

Some considerations:

Regarding the verification process, to verify the inclusion in a merkle tree we'd also have to provide other branch hashes, such as in:

                        [Merkle Root]
                           /     \
                      [Node A]   [Node B]
                        /   \
            [Node A1]         [Node A2]
             /    \            /    \
           L1      L2        L3      L4

To verify a batch (L3,L4), we'd have to provide the hashes of both leaves, [Node A1] and [Node B].

Based on the chatGPT session, I believe the additional branch hashes are provided in the bytes32 calldata proof[].

L3, L4 should be provided to the settleUsage function as an array of contiguous payers with their amounts, not hashes. We still need the address and the amount to settle the debt.

I'm considering the following function signature:

function settleUsage(
    address originatorNode,
    uint256 reportIndex,
    uint256 offset,
    address[] calldata payers,
    uint256[] calldata amounts,
    bytes32[] calldata proof
) external;

The algorithm remains the same:

• Compute all the hashes of leaves on this batch, hash(payers[i], amounts[i]).
• Compute the branch hash and the validity of the Merkle Tree.
• Pay out.