Summary
In the recent service incentivization MVP proposal, I feel that I have not given enough attention to prior work. This post aims to close this gap. I discuss previous solutions mentioned here and elsewhere that seemed most relevant, and outline potential next steps for our protocol.
Design Goals
Let us revisit our design goals for the service incentivization MVP based on off-chain payments:
- Security: Prevent trivial fraud; no catastrophic loss from a single session.
- Unlinkability: Break the link between payment and service provision.
- Bearer instruments: Possession of a ticket grants service access rights.
- Efficiency: Support for batch operations; no per-request on-chain transactions.
- Simplicity: Minimal protocol and contract surface for rapid iteration.
- Upgradeability: Clear path to improvements.
Note on terminology: in this post, we look through the lens of a marketplace, where payers (or senders) are users of a service, and payees (or receivers) are (service) providers.
Why Off-Chain
Off-chain payments solve problems that even fast, low-fee blockchains cannot escape. High-performance blockchains (L2s, L3s) often rely on centralized sequencers that can censor or reorder transactions. Low or zero fees usually mean someone else is paying the cost. Physical limits, such as the speed of light, constrain how fast truly decentralized consensus can be reached. For these reasons, off-chain interactions make sense even when blockchains are cheap to use.
Unlinkability in a Single-Provider World
We start from a simple one-to-one interaction in the classical client-server model. Multiple clients may exist, but each client-server relation is independent. We will later generalize to a multi-server scenario.
Unlinkability in a single-server setup can be achieved with blind signatures stemming from 1980s Chaumian e-cash. Indeed, itâs a bit strange to refer to these protocols as off-chain as blockchains didnât exist back then. In any case: the main design goal of these systems was unlinkability.
Unlinkability means de-linking payment from service provision. The framework works as follows. One central server receives payment and provides service. A client pays for a service upfront and receives blinded tickets. The client then uses unblinded tickets to pay the same server. The server cannot correlate a service request with the funding transaction.
Modern zero-knowledge proofs provide richer anonymized condition checking beyond signature verification. A user can prove in zero knowledge that they are eligible for service via proof of payment, proof of membership, or similar mechanisms. RLN exemplifies this approach.
Moving to a Multi-Provider World
Double-spending becomes a key problem in a multi-provider world. A user can request services from several Service Providers and try to spend the same ticket more than once. Blockchains prevent double-spending by keeping a synchronized global state, but as weâre moving off-chain, we must confront double-spending again.
In ZK systems, double-spending is normally prevented with nullifiers. Spending a coin reveals its unique nullifier, invalidating the coin. The nullifier is marked as spent, stopping repeated use.
Purely off-chain payments face a challenge: each nullifier must be checked against a synchronized nullifier set, which means we still need global state synchronization. In a one-to-one client-server setting, no synchronization was required as only one server existed. On each transaction, the server would check the incoming nullifier against its nullifier set and reject potential double-spends.
In a decentralized setting, a blockchain provides global state synchronization but only at the granularity of its finalization time. Until a transaction is finalized, a payer can attempt double-spending. Consequently, payment receivers (Service Providers) can only process one request per finalization window.
This is problematic for latency and granularity. Both sides of a transaction depend on staying in sync. Senders need the current membership set root to generate proofs (as seen in RLN). Receivers need the nullifier set to verify payments.
Payment Channels
Payment channels allow two parties to transact off-chain. A channel opens with an on-chain deposit. Parties sign updated balances as state. Only final settlement requires an on-chain transaction. Double-spend protection comes from the on-chain dispute mechanism. The advantages are low latency and minimal extra security assumptions compared to L1. The main drawback is poor capital efficiency: in a multi-hop path, funds are locked at every hop.
Funds in payment channels are not bearer instruments. A payment state is specific to one channel and cannot simply be transferred between users. In contrast, blinded tickets can be transferred off-band between users before being spent.
There is also linkability concern if a user maintains a direct channel to a provider. Paying via a network is of course possible, but that requires channel liquidity management on the receiverâs end. Moreover, under some conditions, payment paths can be partially reconstructed by intermediary nodes. There is also no zero-knowledge condition checking built in.
Conclusion: native payment channels are not a good fit for our purposes. However, payment channels could serve as a funding rail in the wider design. This isolates channel complexity to the initial funding phase. For example, a user could pay via Lightning to a sponsoring service, receive blinded tickets, then spend those tickets elsewhere off-chain.
Off-Chain Payments and Double-Spend Tolerance
Off-chain payments must deal with the fundamental trade-off: real-time state sync versus double-spend risk. Without global synchronization, a receiver cannot reliably verify a payment. But waiting for global sync increases latency. When double-spending cannot be fully prevented, receivers have to tolerate some risk and punish cheaters later if needed. Punishment mechanisms include reputation loss or slashing deposits. Different architectures mainly vary in how they handle double-spend risks.
Punishing double-spends also costs time and resources. An off-chain ticket payment can only be considered final when the ticket is redeemed. Redeeming each ticket immediately brings back on-chain costs and delays.
Receivers must balance security and efficiency. Redeeming each ticket ASAP gives best security but worst efficiency. Batch redemption optimizes on-chain costs at greater risk of double-spend. Some providers may choose to tolerate some double-spends for better UX or user growth. Serving users without collateral increases risk but could grow the user base.
Nullifier Set Storage
Nullifier set storage is a core problem in off-chain payments. There must be a shared state to verify spent tickets and prevent double-spends.
Centralized storage is simplest. One server acts as the âMint,â like in classic Chaumian e-cash. This gives unlinkability but not decentralization. A quorum model spreads trust among multiple servers. This improves resilience but enables censorship if a majority colludes. A permissionless consensus network puts the nullifier set on a separate blockchain. But building a new chain with ZK primitives is non-trivial. Smart contracts on existing blockchains can also store the nullifier set, avoiding a single point of failure. This is the preferred approach for our use case.
Double-Spend Punishment: Reputation vs Financial
Double-spend punishment can be handled by reputation or financial penalty. Each option has trade-offs.
Reputation-based punishment bans a userâs ID after cheating. This is easy to implement but vulnerable to Sybil attacks: cheaters can create new identities. Still, banning on reputation costs little, so it is worth applying even if imperfect. Caveat: large-scale spam could bloat the database of banned IDs (might be addressed via Bloom filters).
Financial punishment means collateral is slashed after proven cheating. A user must deposit extra funds up front. Collateral must be in addition to the value of the tickets to ensure cheaters risk some value on top of nominal cost of service. Slashing deters cheating but ties up capital and adds UX friction. Slashing rewards need careful design.
One possible concern is âself-slashingâ. If the whistleblower gets the slashed funds, a cheater could report themselves and recover their deposit. Instead, most slashed funds should go to affected Service Providers. For example: 10% to the reporter to incentivize third-party monitoring, and 45% to each of the two affected Service Providers (assuming cross-provider double-spend). If double-spending targets one provider, that provider receives 90%. Incentives and splits need more research.
Conclusion: we should combine reputation bans and financial slashing. Slashing amounts should be adjusted by each service or provider. Further fine-tuning depends on implementation details.
Nullifier Hijacking and Provider-Bound Nullifiers
Nullifier hijacking is a risk in off-chain redemption. If any Service Provider can redeem a given nullifier, attackers can front-run and steal it. The risk applies regardless of where nullifiers are announced (mempool, bulletin board, etc). It is similar to MEV frontrunning: observers exploit an announced but unconfirmed action.
Other ZK systems use binding to defend against hijacking. Zcash separates nullifiers from spend authorization and uses note commitments for recipient binding. ZKAP applies HMACs to tie tickets to client requests. This stops man-in-the-middle hijacking and repurposing tickets in another context.
In our context, eligibility proofs must be provider-bound to prevent ticket hijacking. Provider-binding potentially means smaller anonymity sets. However, on-chain redemption makes provider linkage public in any case (at least without extra anonymization like stealth addresses).
We suggest binding nullifiers to Service Providers at spend time. An alternative approach could be to maintain a unified nullifier set, but with an extra on-chain commit-reveal scheme at redemption time. Further research needed to address concerns such as smart contract spamming with invalid commitments.
Scalability via Probabilistic Payments and Randomness Sources
Off-chain systems increase throughput by minimizing on-chain interactions. The goal is to reduce interactions between users, service providers, and the nullifier set. Every interaction has latency and cost, even without transaction fees.
Probabilistic payments help by reducing the number of on-chain transactions. An unbiased ticket resolution mechanism is required for deciding if a ticket wins. The coin toss protocol is one approach. It uses an interactive flow where two parties commit to and then XOR random values. If the result meets a predefined adjustable target (a-la proof-of-work), the ticket wins.
Abort attacks, which are typical for naive commit-reveal schemes, are not a concern here. If the ticket wins, the receiver has an incentive to follow the protocol to redeem payment. If the ticket loses, no further action is required anyway. The payment receiver will only hurt themselves by withholding their random value on the last step.
Blockhash randomness is a non-interactive alternative to a coin toss. A ticket commits to a future block height. The randomness comes from the last block hash at that height, combined with the ticket hash. A ticket wins if this combined value is below a tunable target. Another, even simpler alternative, derives randomness just from the ticket hash itself, with no external randomness sources. The drawback here is potential âticket miningâ (re-generating a ticket or aborting the protocol depending on an upcoming result).
Finally, Fractional Message Transfer (FMT) is a cryptographic protocol that can replace above-mentioned ticket resolution methods. FMT encrypts messages so the receiver can decrypt only with probability p. If decryption succeeds, the receiver can redeem the ticket. More on FMTâs privacy properties in the next section.
Probabilistic payments require careful ticket management. If tickets in a payment stream share a nullifier, more than one ticket may win by chance. An honest user must never send another ticket derived from the same nullifier until receiving an ACK from the Service Provider.
Unlinkability of Probabilistic Payments
Probabilistic payments produce two outcomes: null-payments and macro-payments. Macro-payments reveal the nullifier on-chain. This makes macro-payments linkable by anyone. However, in honest use, each nullifier appears on-chain only once. A repeated nullifier on-chain signals a double-spend. Compare to Zcash: every transaction reveals its nullifier; consensus mechanism rejects repeated nullifiers as double-spend.
Null-payments have a separate linkability issue. Null-payments do not leave any on-chain trace, so external observers cannot see them. However, in naive coin-toss protocols, the nullifier is revealed to the receiver for all tickets (both winning and losing). This lets the Service Provider link null-payments and macro-payments.
Fractional Message Transfer (FMT) solves null-payments linkability by hiding losing ticket nullifiers. Only winning tickets have their nullifiers revealed. Coin-toss and blockhash methods do not have this property. AFAIK, FMT is the only solution to provide null-payment unlinkability.
Prior Work
MICROPAY1 and Orchid
MICROPAY1 and Orchid enable probabilistic micropayments using a coin-toss protocol. Slashing is used as a penalty for double-spending, enforced by an extra deposit. MICROPAY1 uses Bitcoin multisig and a trusted escrow. Orchid adapts this to Ethereum. Both schemes generate a ticket using random commitments from both parties. The winner is decided by XOR.
DAM (Decentralized Anonymous Micropayments)
DAM provides probabilistic payments with both slashing and unlinkability of null-payments. It is built on DAP and Fractional Message Transfer (FMT). FMT encrypts a message so that the receiver can decrypt it with probability p. If decryption fails, the receiver gains no information. Keys are set so the sender cannot cheat by skewing the winning odds. Only if decryption succeeds does the ticket become spendable on-chain.
The key difference from MICROPAY1 and Orchid is the use of FMT instead of XOR-based coin-toss. FMT ensures nullifiers for losing tickets remain secret, maintaining unlinkability. Fractional Hiding guarantees the receiver only learns payment details if they win. The protocol requires a sufficient slashable deposit to deter cheating. Only winning (macro-payment) tickets appear on-chain, making them double-spend detectable.
Nym and ZK-Nyms
Nym provides anonymous access to mixnets using credentials. Users deposit NYM tokens, present proof to a quorum, and receive a signed credential. Each usage is unlinkable due to credential re-randomization. Nymâs system relies on the Coconut selective disclosure credential scheme (see also: Offline e-cash paper). It supports distributed threshold issuance, public and private attributes, re-randomization, and multiple unlinkable selective attribute revelations.
Credential signatures can be verified without blockchain state sync, but this introduces some trust in the quorum. Double-spend protection comes from blacklisting user IDs and slashing new deposits for offenders. Attackers can circumvent this by changing identities, but this adds friction. There is a local double-spend filter via off-chain Bloom filters. A staking and reward system exists for Service Providers (out of scope for our purposes now).
HOPR
HOPR uses payment channels with probabilistic tickets for a mixnet incentive layer. Randomness for ticket generation is derived from the specific data packet, binding tickets to their respective packets. This design prevents reusing tickets across nodes. HOPRâs architecture centers on path-based payments and onion routing. Each hop in a path is paid via the channel.
This model does not directly apply to our marketplace use case, where services are not always path-based or involve data transfer. Our target is a universal marketplace, not mixnet-only routing. Adapting HOPRâs channel design would make null-payments linkable within each channel. HOPRâs anonymity relies on the underlying onion-routed network; without it, we would need additional mixing methods.
Summary Table
| Property | DAM | Orchid | ZKAP | Nym | HOPR | Our Protocol (MVP) | Our Protocol (post-MVP) |
|---|---|---|---|---|---|---|---|
| Who Issues Tickets | Self-issue | Self-issue | Server | Quorum | Self-issue | Self-issue | Self-issue |
| Who Stores Nullifier Set | Smart Contract | Smart Contract | Server | Quorum | N/A | Smart Contract | Smart Contract |
| Probabilistic Payments | FMT | Coin-toss | - | N/A | Ticket Hash | FMT | FMT |
| Providers | Multi | Multi | Single | Multi | Multi | Single | Multi |
| Double-Spend Punishment | Slashing | Slashing | N/A | Reputation + Slashing | N/A | Reputation | Reputation + Slashing |
Positioning Our Protocol Architecture within Prior Work
Finally, let us position the proposed protocol in the context of design decisions discussed so far.
Let us consider how probabilistic payments apply to our proposed protocol. There are two main interactions:
- User to Service Provider: The user spends a ticket to get service.
- Service Provider to TicketRegistry: The provider redeems a ticket for payment.
First, consider the user-to-provider step. Every request requires a separate interaction by definition. We cannot reduce the number of interactions, but we can make each one cheaper. Proof generation is usually expensive. With probabilistic payments, the user generates a zero-knowledge proof once. They then use this proof to generate multiple randomized eligibility proofs (like batching).
Second, look at the provider-to-contract interaction. Each ticket must eventually be redeemed on-chain. With probabilistic payments, only winning tickets (âmacro-paymentsâ) go on-chain. There is no need to report losing tickets or update nullifier sets for them.
Overall, probabilistic payments improve efficiency of both interactions in our architecture. For users, they amortize proof generation cost. For providers, they concentrate on-chain fees onto winning tickets only. This improves the trade-off providers face between redeeming immediately vs accumulating non-redeemed tickets for batch redemption with higher double-spend risk.
The proposed architecture can be as follows. Our protocol largely implements the DAM concept to build a multi-provider marketplace with probabilistic payments. Probabilistic tickets use FMT, not centralized coin-toss. No centralized ticket issuer. A smart contract stores nullifiers. Slashing deposits deters double-spend. Waku or similar acts as an optional bulletin board for nullifier pre-sync. Provider reputation is decentralized and deposit-based, inspired by EigenTrust. Compared to Orchid, we swap XOR lottery for FMT ticket resolution. Users self-generate probabilistic tickets with no centralized issuer.
MVP and Post-MVP Improvements
For MVP, we keep it simple. Only one service provider. No probabilistic payments or FMT needed. Providers can detect double-spends locally. Nullifier sync between parties is unnecessary.
After MVP, several upgrades might be implemented.
Nullifier Pre-Sync
Nullifier pre-sync reduces reliance on blockchain sync. A Waku topic can hold nullifier events before on-chain redemption. This setup offers fast, ephemeral nullifier sharing. Waku supports lightweight, peer-to-peer message exchange. Long-term storage is unnecessary since nullifiers eventually go on-chain.
Provider Reputation
Service Provider reputation prevents abuse by providers. A provider might accept payment and refuse service. We counter this with reputation tracking. Local reputation deters serial cheats, as shown in our incentivization PoC. Long-term, aim for decentralized global reputation, like EigenTrust.
Service Discovery
Discovery in P2P networks is how nodes find and connect to each other without central servers. It lets peers locate relevant service providers in a distributed environment. For a marketplace with many services, it is important to efficiently find nodes that offer a given service. Service discovery will be developed for a fully fledged marketplace, as previously discussed.
Open Questions
Nullifier Binding to Service Providers
Should nullifiers be linked to Service Providers at spending time? Does this impact privacy or security? Does the on-chain redemption by providers make this a non-issue? Is there a way to improve this? Binding tickets to providers can be done with HMAC. Smart contracts likely cannot verify HMAC efficiently. Applicability evaluation is needed.
Efficient Multi-Ticket Batch Redemption
Batch redemption reduces receiver costs. Can we redeem multiple tickets in a cryptographically efficient batch? Is it possible to achieve O(log N) or even O(1) redemption complexity? A single invalid (double-spent) ticket can invalidate the whole batch. Larger batches are efficient but fragile to errors. Can pre-checking a nullifier set help before submitting on-chain? Requires a dedicated protocol design discussion.
Time-Lock Puzzles
Time-lock puzzles or VDFs could be added to tickets at spending time. They introduce time delays to help providers detect double-spending. The downside is user experience slowdown. Investigate if this addition is viable or necessary.
