PM double spend security

Title: PM double spend security
Author: @yondonfu

# Brief Description

PM (probabilistic micropayments) is a useful scheme for many-to-many payments with a single funding deposit enabled by universal payment aggregation - as long as the selection process for winning tickets is provably fair, a recipient does not care that a ticket from any individual sender does not pay out because on average it will be paid fairly over the course of many tickets from many senders. Aside from UX concerns, the core challenge to be addressed with PM is defending against double spends which cannot be completely prevented because senders have a single deposit for multiple recipients and payments are offline (meaning that parties do not wait for transactions to confirm on-chain thereby ensuring global consensus on availability of funds).

One approach to deter double spends is to force senders to also have a non-spendable penalty escrow that backs created tickets (in addition to the sender’s funding deposit) as is suggested in [1]. If the sender is caught double spending, its penalty escrow is slashed. As a result, a sender would lack an economic incentive to double spend if the additional utility it can gain is less than the economic loss incurred by having its penalty escrow slashed. However, [1] does not specify how exactly the required penalty escrow should be set.

The problem we are interested in solving is how to set a required penalty escrow for a sender that would deter the sender from double spending. We proceed to discuss the specific requirements for a PM double spend security protocol that involves setting a required penalty escrow below.

# Problem Statement

## Use Cases

A PM double spend security protocol must fulfill or preserve the following use cases:

- A recipient should be able to safely accept payments for transcoding work from an anonymous zero reputation sender with minimal risk
- A recipient should be able to accept simultaneous payments from many senders
- A sender should be able to simultaneously pay many recipients
- A sender should be able to pay any recipient regardless of whether the sender has worked with the recipient in the past before
- A sender should be able to stop paying a recipient and quickly transition to paying a new recipient

## Requirements

- *Bounded additional utility from double spending*: Since we acknowledge that completely preventing double spending is impossible, the security mechanism needs to be able to bound the sender’s additional utility from double spending. If the sender’s utility from double spending is infinity then there is no cost that can be imposed on the sender that would deter double spending.
- *Minimal restrictions on sender set for a recipient*: Ideally, there is no restriction on the senders that a recipient can accept payments from. If there needs to be a restriction on the sender set, the recipient should be able to modify its sender set with minimal overhead (cost in both time and money).
- *Minimal restrictions on recipient set for a sender*: Ideally, there is no restriction on the recipients that a sender can send payments to. If there needs to be a restriction on the recipient set, the sender should be able to modify its recipient set with minimal overhead (cost in both time and money).
- *Sub-linear cost of scaling sender payments to additional recipients*: Any on-chain transactions required should not scale linearly with the number of desired recipients because otherwise, the sender would be better off setting up a unidirectional payment channel with each recipient (the channel set up cost for each recipient is what we are trying to avoid).
- *Minimal switching overhead to work with new marketplace entrant*: In an extreme scenario, all the current recipients in the marketplace might be faulty or charging high prices. So, if a new marketplace entrant is either performant or charging a lower price that satisfies the sender's requirements, the sender would prefer to send payments to the new entrant. The overhead (cost in both time and money) for switching to the new entrant should be low.

## Reasonable Assumptions

- *Rational actors*: Senders and recipients are rational such that they will not take an action where the economic cost > the economic benefit.
- *Free entry and exit in the marketplace*: Both parties are allowed to enter and exit the marketplace as they please. There should be no expectation of a fixed set of senders or a fixed set of recipients. The membership of both sets should be expected to be constantly changing over time.
- *Blockchain availability*: For the purposes of this project, we assume that the underlying blockchain is available and that actors are able to have their transactions confirmed within fixed time windows.

# Candidate Constructions

## Recipient set commitments and payment rate limiting

Chiesa et. al. have presented an anonymous probabilistic payment construction informed by a formal economic analysis of PM double spending [2]. We can try to adapt their construction and leave out the technical details required for anonymity guarantees.

In the context of the Livepeer network, the sender is a broadcaster and the recipient is an orchestrator.

Orchestrators register themselves on-chain and advertise their `serviceURI`, `rewardCut`, `feeShare` and `maxPayRate` within the on-chain registry. Of particular relevance to the current discussion is `maxPayRate` which defines the maximum cumulative value of PM tickets (i.e. the sum of the expected value of tickets) that an orchestrator will accept during a locally defined time period `payWindow` denominated in blocks. We use the Ethereum blockchain as a universal clock that ticks on average every 15 seconds with each new block. An orchestrator will maintain a local counter to track the value of tickets received which is reset at the beginning of each `payWindow`. If the counter value is ever going to exceed `maxPayRate`, the orchestrator stops accepting tickets until the beginning of the next `payWindow`. Thus, an orchestrator rate limits payments accepted during a fixed time period. The default value for `payWindow` should be the expected time to detect double spends which might be a few blocks if orchestrators default to redeeming winning tickets immediately. We define the time to double spend detection to start from when a broadcaster’s deposit is insufficient to cover all of its sent out outstanding winning tickets and to end when the last orchestrator to receive one of those winning tickets detects the double spend.

When a broadcaster creates its penalty escrow, it first observes the on-chain registry and fetches the ETH addresses and `maxPayRate` values of the orchestrators that it would like to work with. The broadcaster can select the entire orchestrator set or it can select a subset to reduce its penalty escrow requirements. This might be preceded by requests to also fetch pricing information from the orchestrators. Then, the broadcaster generates a Merkle sum tree (the use of this data structure is similar to its usage in the proofs of liability described in this [paper](https://www.tik.ee.ethz.ch/file/b89cb24ad2fa4e7ef01426d318c9b98b/decker2015making.pdf)) with each leaf as a ETH address and `maxPayRate` pair. At the end of the generation process, the broadcaster should have a Merkle root and the sum total of the leaf `maxPayRate` values. The broadcaster should then set its penalty escrow equal to the sum total of the leaf `maxPayRate` values and store the Merkle root on-chain. We call this Merkle root the broadcaster’s `receipientCommitment`.

When a broadcaster works with an orchestrator, the broadcaster must prove to the orchestrator that it was included in the broadcaster’s `recipientCommitment`:

- Given a Merkle authentication path (tree nodes from leaf to root), the orchestrator can confirm that its ETH address was included in the tree corresponding to a broadcaster's on-chain `recipientCommitment`.
- A valid authentication path will also mean that the orchestrator’s `maxPayRate` added with the node values in the path result in the broadcaster’s current penalty escrow. We can relax this condition to instead require the broadcaster’s current penalty escrow to be greater than or equal to the resulting sum of adding the values in the authentication path. Thus, if the orchestrator decreases its `maxPayRate`, the broadcaster doesn’t have to update its `recipientCommitment`
- If we assume that orchestrators will only work with a broadcaster upon receiving a valid Merkle authentication path for the broadcaster’s current `recipientCommitment`, then any given orchestrator knows that if `n` orchestrators work with a broadcaster then the broadcaster’s penalty escrow is sufficient for the `maxPayRate` values defined by those `n` orchestrators.

To summarize, by having orchestrators enforce their own payment rate limits based on their own time windows for double spend detection and having broadcasters commit to a recipient set ahead of time, this construction bounds the time to double spend detection, recipient set and recipient payment rates which results in bounded additional utility from double spending for broadcasters. The required penalty escrow for a broadcaster can then be set to this maximum additional utility from double spending.

### Open Problems/Questions

- Should orchestrators be able to update their `maxPayRate` values? If so, we might want to restrict the time period during which these values can be updated on-chain (perhaps during a round lock period) so that broadcasters have an easier time generating a `recipientCommitment` and adjusting their penalty escrow with fixed `maxPayRate` values.
- Should `maxPayRate` be based on the expected value of all received tickets or the face value of received winning tickets (or should both be rate limited)? The latter is the safest in the worst case where a malicious sender is really lucky and creates many winning tickets simultaneously, but increases penalty escrow requirements while the former just focuses on the average case.
- Is it ok for orchestrators to define their own `payWindow` values locally?
- Are there serious vulnerabilities to collusion between malicious broadcasters and orchestrators to harm other orchestrators by deviating from the described protocol?

# Objectives & Key Results

**Objective 1**: Design a PM double spend security protocol that fulfills the above requirements.
- **KR1**: Produce a technical specification for the protocol
- **KR2**: Produce a written explanation of why the protocol is secure under the above assumptions

If **Objective 1** is believed to be impossible, then consider:

**Objective 2**: Prove that a PM double spend security protocol that fulfills the above requirements does not exist.
- **KR1**: Produce a written explanation of why such a protocol under the above assumptions does not exist
- **KR2**: Produce a suggestion for an alternate objective based on updated requirements and assumptions

When a "written explanation" is mentioned, a logically constructed argument will usually suffice. Ideally, a rigorous proof (i.e. mathematical) would be provided. However, since not everyone is trained in writing those types of proofs and in the interest of promoting more open participation, the former should be adequate.

# Suggested Reading

[1] Pass & Shelat. “Micropayments for Decentralized Currencies”. ([paper](https://eprint.iacr.org/2016/332.pdf))
[2] Chiesa et. al. “Decentralized Anonymous Micropayments”. ([paper](https://eprint.iacr.org/2016/1033.pdf))
[3] Micali et. al. "Micropayments Revisited". ([paper](https://people.csail.mit.edu/rivest/pubs/MR02a.pdf))
[4] Salamon et. al. "Orchid: Enabling Decentralized Network Formation and Probabilistic Micro-Payments". ([paper](https://www.orchid.com/whitepaper.pdf))

Start by reading the suggested papers, especially Pass & Shelat and Chiesa et al., then evaluate the recipient-set commitment and payment-rate-limiting construction against the stated use cases and requirements. Done means producing a technical specification and a written security explanation, or proving that no protocol can satisfy the assumptions and proposing revised requirements.

Written by the indexing model from the issue text.