This post was co-authored by Pedro Henrique Bufulin de Almeida and Severiano Sisneros.

Introduction

You’re a coffee shop owner looking to minimize your costs of doing business. You notice that credit card transaction fees are inflating the price you charge to your customers. So you have an idea: rather than paying with credit card for each transaction, you let your customers pay with an IOU. At the end of the month you tally the customer’s IOUs and ask the customer to pay the total amount using a single credit card transaction. But, what happens if you have a customer who runs up a large tally and then never comes back? It would be great if you could prove that all the IOUs came from the untrustworthy customer and also prove that the value of sum of all the IOUs, allowing you to charge the customer’s credit card without their involvement.

Cryptographers solved the first half of the problem in the early days of public-key cryptography by inventing digital signatures. In this post we’re going to talk about how cryptographers solved the full problem using something called a homomorphic signature scheme.

You may have heard the word “homomorphic” before, most likely in the context of homomorphic encryption. Essentially all this means is that if you have two values that are the output of some function and add them together, then the result is the same as first adding the two inputs together and then calculating the function on the sum; if X = H(x) and Y = H(y) then X + Y = H(x + y). For homomorphic signatures, this function is a digital signature.

Back to our coffee shop example. You now know about homomorphic signatures, so you ask all of your customers to digitally sign their IOUs with a homomorphic signature scheme. Now when the wily customer decides to not show up, you can simply add up all of their signed IOUs. The result is a single IOU with a valid signature for the total amount owed by the customer. You can send this IOU and the signature to the customer’s bank, they can verify that the signature belongs to them, that the signature is valid, and the bank can charge the customers account for the total amount you are owed, all without requiring any interaction from the customer. Great!

This solution is particularly interesting in blockchain applications, where transaction fees are particularly high. In this case, the “bank” is a smart contract. You can submit a single transaction which verifies the homomorphic signature and transfers the amount owed from the customer’s account to you. This is way cheaper than having to submit and verify all the individual signatures and enables interesting protocols like micropayment channels.

This post discusses design and optimization of verifiable micropayments over a state channel, a feature of Semiotic Labs’ GraphTally library for The Graph. The Graph is a decentralized data services protocol, allowing customers to index and access all blockchain data.

Micropayments Using State Channels

An Ethereum-based state channel lets users conduct numerous transactions off-chain without the cost and potential delay of executing and finalizing each transaction on the EVM. In the case where transactions are payment transfers (a payment channel), the cost associated with fees can be greatly reduced, especially when the value of each payment is low (a so-called micropayment).

In the basic model of a state channel the only on-chain transactions required are smart contract operations to open and close the channel. Participants in the state channel conduct a series of transactions off-chain and agree upon state changes by collectively signing them. When the channel closes, payments are distributed and the state change is finalized on the Ethereum mainnet. Users can resolve a disputed state update by finalizing the last transaction which was signed by all participants.

We can authenticate and verify the integrity of transactions with digital signatures. Semiotic Labs’ GraphTally (formerly known as Timeline Aggregation Protocol - TAP) provides a library for verifying ECDSA signatures on transactions in a payment channel. GraphTally is a tool for a single party sending micropayments to one or more receivers. The receipt for each micropayment is signed, then verified by the TAP Aggregator. The Aggregator adds together the values of all payments and creates a new signed receipt reflecting the combined value. The final receipt can be verified on-chain, where the change of state will be applied.

The process carried out by GraphTally requires validating each signature individually. We can make this more efficient by aggregating the signatures and performing a single verification that applies to a combination of the receipts. BLS signatures are currently used on the Beacon Chain for a similar purpose, aggregating validator signatures on Merkle trie roots. In this context, multiple public keys are used to sign a single message, then the signatures are added together and verified. We would like to have a sender sign multiple messages (e.g., receipts) and verify the signature aggregate in one step. BLS can do this, but the signature aggregate is not a valid signature on a combination of messages. The receiver must compute a hash of each message to verify the signature aggregate.

Instead, we look to homomorphic signature schemes (HSS), where the aggregated signature is a valid signature on the sum of messages. Semiotic Labs has developed a Rust implementation, h2s2, of the protocol outlined below. We will see that when we can perform some offline precomputation, the work of verifying an aggregated signature is constant.

Homomorphic Signatures for Cheap and Trustless Micropayments

The network coding scheme $\text{NCS}_1$ of Boneh et. al. is an HSS consisting of four algorithms Setup, Sign, Combine, and Verify. We refer the reader to the paper for the details of the protocol, including security proofs, and here just go through the algorithms applied to our context.

The parties involved when using a signature scheme are the sender (signing messages) and the receiver (verifying signatures). For example, the sender might query an Indexer and sign a receipt for a payment amount. The Indexer (receiver) serving the query obtains the receipt and redeems the payment amount on-chain. The verifier (Indexer) verifies each signed receipt it receives from the sender and executes the Combine algorithm to aggregate the signatures. There is a smart contract on the mainnet which verifies the aggregated signature in order to finalize the accumulated microtransactions. We are concerned with the costs of verifying this signature on-chain.

Aggregation

The main part of the scheme we discuss here is the aggregation and verification of signatures. The Combine algorithm aggregates multiple message signatures into one, which is valid for a combination of the respective messages:

$$m_{\text{agg}} = \sum_{i=1}^{N} m_i$$ $$\sigma_{\text{agg}} = \sum_{i=1}^{N} \sigma_i,$$

where $m_1,…,m_N$ are the individual messages and $\sigma_1,…,\sigma_N$ are the signatures on the respective messages.

In the $\text{NCS}_1$ scheme, each signature has a weight in the base field which is included as a coefficient in the sum (similar for the combined messages). Here, we assume all weights are equal to 1.

Verification of Combination

The smart contract verifies the aggregated signature by checking:

$$e(\sigma_{agg}, Q) = e\left(\sum_{i=1}^{N} H(id,i) + m_{agg} \cdot P, R \right)$$

In the following paragraph, we offer some notes on the parameters involved. The chief operation to notice in the equation above is the sum of hash values, $\sum_{i=1}^{N} H(id,i)$. This can be a costly operation to perform at verification time, but this cost is eliminated if the calculation is done off-chain.

We use the pairing-friendly curve BN254 over scalar field $\mathbb{F}_p$, with associated groups $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ and type three bilinear pairing $e:\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$, as laid out in the Ethereum precompile contracts EIP-196 and EIP-197. $H:\{0,1\}^* \rightarrow \mathbb{G}_1$ is a hash-to-curve function to map identifiers and tags to group elements. The sender is associated with an unpredictable identifier $id \in \mathbb{Z}_p^*$ which stays consistent for the duration of the payment channel. The identifier is concatenated with an index $i$ (we use an unsigned integer type) indicating the receipt being signed. This ensures that $H(id,i)$ is distinct for each micropayment. $P$ and $Q$ are generators of $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, and $R$ is the public key used for signing the messages.

Cost of Verification

If the values $P$, $Q$ and $R$ are initialized as part of the smart contract, then the verification of the combination requires:

• A scalar multiplication in $\mathbb{G}_1$, which costs 40,000 gas.
• A pairing equality check, which costs 260,000 gas.

The gas estimates above are based on the figures in EIP-196 and 197.

Verification also requires computation of the sum $\sum_{i=1}^{N} H(id,i)$. This is $N$ point additions, as well as the computation of the hash-to-curve function itself in each instance. When verifying signatures on thousands of micropayments, this will dominate the cost of verification.

To avoid doing this computation on the EVM, the verification smart contract can be initialized with a precomputed value $H_{\text{agg}} = \sum_{i=1}^{N} H(id,i)$ based on the expected number of receipts $N$.

A Multi-Key Protocol

What if we want to aggregate signatures on microtransactions from multiple senders? Aranha and Pagnin present an adaptation of $\text{NCS}_1$ to use multiple public-secret key pairs and identifiers. We will not walk through the details of the extension here, but note the operations involved in verification of the aggregated signature. For $t$ distinct senders (identifiers) signing accumulated micropayments:

• $t$ scalar multiplications in $\mathbb{G}_1$, which cost 40,000 gas each.
• $t$ point additions in $\mathbb{G}_1$, which cost 500 gas each.
• $t$ group multiplications in $\mathbb{G}_T$. Operations in $\mathbb{G}_T$ tend to be expensive due to the size of elements involved.
• $t$ pairing computations, which again may be costly.
• A pairing equality check, which costs 260,000 gas.

Additionally, we need $t$ computations $\sum_{i \in I} H(id,i)$, one for each distinct identifier, where the sum runs over the aggregated receipts for a given $id$. There is also a sorting that the verifier needs to perform in order to group the incoming ($id$, index) pairs by identifier.

As noted above, the on-chain verification smart contract may avoid computing a sum of hash-to-curve values by accepting precomputed values $H_{\text{agg}} = \sum_{i=1}^{N} H(id,i)$, which depend on the $id$ and the expected number of receipts $N$ associated with that identifier.

Benchmarks

The following benchmarks were conducted on an M2 MacBook Air using our Rust implementation h2s2. We are showing the time taken to sign a single message, verify a single message, aggregate a batch of messages (in this case 32), and verify the aggregated signature. There are a few things we can point out about these benchmarks. Signing individual messages is fast, taking about 82us per message. Verifying a single message takes a little longer, about 1.2ms. Aggregating a batch of signatures is fast, taking about 57us to aggregate 32 signatures. The most important thing we notice, is that verifying an aggregate signature takes about the same time as verifying a single signature, i.e. the verification time does not depend on the nunmber of signatures used to compute the aggregate. This is because we are precomputing the sum of the hash-to-curve values, as mentioned in the previous section. For blockchain applications, this means we can batch verify any number of signatures and the on-chain costs will be independent of the number of signatures in the batch.

82us to sign a single message

1.2ms to verify a single message

58us to combine 32 signatures

1.1ms to verify an a batch of 32 signatures

Conclusion

By leveraging homomorphic signature schemes, we can significantly reduce the computational costs associated with verifying aggregated micropayments, while maintaining the security and integrity of off-chain transactions. Semiotic Labs’ work with GraphTally and the h2s2 implementation demonstrates the potential to enhance efficiency without compromising trust. The innovations discussed here provide a robust framework for scaling Ethereum-based micropayments, making them a practical option for a wide range of use cases.

We hope to have given you a high-level understanding of how homomorphic signatures work and how they can be used to solve a practical problem for blockchain applications. If you want more details, we also a have a more technical whitepaper here.

If any of this sounds interesting to you or if you’ve encountered similar problems, please reach out!