# Livepeer Probabilistic Micropayments

## Ticket Data Structure

We assume the use of an [interactive coin flipping protocol](#selecting-winning-tickets) for selecting winning tickets.

A ticket *T* consists of the following fields:

- *recipient*: The Ethereum address of the recipient.
- *faceValue*: The face value of the ticket which is payable to the recipient if the ticket wins.
- *winProb*: The probability of the ticket winning represented as a number between 0 and 2²⁵⁶ - 1.
- *senderNonce*: A random nonce generated by the sender that is used to create a uniquely identifiable ticket and to determine if a ticket wins.
- *recipientRandHash*: The hashed commitment to a random number *recipientRand* generated by the recipient.
- *auxData*: Additional auxilary data that can be used to determine ticket validity i.e. a creation timestamp.

Within the Livepeer network, the sender is the broadcaster who is sending tickets as payments for video transcoding and the recipient is the orchestrator who is accepting tickets as payments for video transcoding.

A broadcaster sends *T* and *SIG_B(T)* to an orchestrator. If *T* is a winning ticket, an orchestrator provides *T*, *SIG_B(T)* and *recipientRand* to a TicketBroker contract in order redeem the ticket.

## Selecting Winning Tickets

As a starting point, we can use a coin flipping protocol. See this [gist](https://gist.github.com/yondonfu/352ae689b0d802cc6e3f5403739b4e6a) for analysis on alternative winning ticket selection protocols.

## Ticket Creation and Redemption

If a broadcaster and orchestrator are connecting for the first time or if the orchestrator has revealed its last *recipientRand* value used with the broadcaster, the two parties execute the following handshake protocol:

1. Assume that the orchestrator has a persistent secret *recipientSecret*.
2. The orchestrator generates a random seed *recipientSeed* and the random number *recipientRand = H(recipientSecret, recipientSeed)*. The orchestrator then creates the commitment *recipientRandHash = H(recipientRand)* which it sends to the sender along with *recipientSeed*.

For each new ticket *T*, a broadcaster will

1. Include *recipientRandHash* in *T*.
2. Include appropriate values for *recipient*, *faceValue* and *winProb* in *T*.
3. Generate a random number *senderNonce* which is included in *T*.
4. Send *T*, *SIG_B(H(T))* and *recipientSeed* to the orchestrator.

TODO: Handle *auxData*

For a received ticket *T*, an orchestrator will

1. Compute *recipientRand = H(recipientSecret, recipientSeed)*.
2. Check if *recipientRandHash = H(recipientRand)*. If not, reject the ticket.
3. Check that the *recipient* address is the orchestrator's receiving address.
4. Check that *SIG_broadcaster(H(T))* is a valid signature over the hash of *T* that corresponds to the broadcaster's address.
5. Check that *H(H(T), receipientRand) < winProb*. *H(T)* is a unique identifier for *T* since *senderNonce* is a random number. *recipientRand* is the preimage for the hashed commitment *recipientRandHash* included in *T*.

Steps 1 and 2 allow the orchestrator to track minimal state for the random numbers it creates for tickets.

For a received winning ticket *T*, an orchestrator will

1. Submit a transaction to the TicketBroker contract with *T*, *recipientRand* and *SIG_broadcaster(H(T))*.
2. Check that *T* as identified by *H(T)* has not been redeemed already.
3. Check that *H(recipientRand)* == *recipientRandHash*.
4. Recover the broadcaster payer address via *SIG_broadcaster(H(T))*.
5. Check that the broadcaster has a penalty escrow.
6. Check that *H((T), recipientRand) < winProb* to determine if *T* won.
7. If the broadcaster's deposit < *faceValue*, burn the broadcaster's penalty escrow and transfer the remainder of the broadcaster's deposit to the orchestrator. Else, transfer *faceValue* from the broadcaster's deposit to the orchestrator.
8. Mark the ticket identified by *H(T)* as redeemed to prevent replay attacks.

One UX problem to note is that if broadcasters do not know which tickets have won, they are still at risk of accidentally double spending if they are unlucky and send multiple winning tickets whose cumulative value exceeds their current deposit. Without knowledge of winning tickets (this risk is increased with higher face values for tickets), broadcasters cannot accurately determine how much of their deposit is actually remaining if orchestrators do not immediately redeem tickets as soon as they receive winning tickets. As a result, broadcasters might end up sending out too many tickets without properly topping of their deposits.

In the optimistic scenario with honest actors, an orchestrator can send a message to a broadcaster whenever it receives a winning ticket prior to revealing the winning ticket on-chain. The message will allow the broadcaster to confirm that a previous ticket it sent won thereby allowing the broadcaster to update its internal view of its deposit prior to the deposit being updated on-chain.

### Possible Improvements

**1. Ticket expiration**

Tickets can include an expiration timestamp as *auxData*. An orchestrator will be unable to redeem a winning ticket on-chain after its expiration timestamp. Alternatively, tickets can include a creation timestamp as *auxData* and the TicketBroker contract will enforce a constant validity period for a ticket based on its creation timestamp.

Ticket expirations have a few benefits:

- They force orchestrators to reveal winning tickets within a bounded amount of time
- They reduce the time required to detect double spends since orchestrators receive faster updates about a broadcaster's deposit

**2. Batch ticket redemption**

We can make ticket redemption more cost effective by redeeming multiple winning tickets at once. The simplest form of batching can be achieved by having the TicketBroker contract implement a batch winning ticket redemption function. However, with this approach, the gas cost of ticket redemption still increases linearly with each winning ticket.

More efficient batch ticket redemption can be achieved with techniques such as cryptoeconomic interactive challenge games and zkSNARKs/zkSTARKs. We leave this area as an area for future research.

**3. Confirmation signatures**

For the following discussion, we assume the use of ticket expirations. When a orchestrator informs a broadcaster of a winning ticket, the broadcaster responds with a confirmation signature of the form *SIG_broadcaster(H(faceValue))* to the orchestrator. The orchestrator can submit the confirmation signature to the contract instead of the winning ticket to claim payment.

The confirmation signature is useful for the orchestrator because:

- On-chain signature verification is cheaper than full on-chain winning ticket validation thereby saving costs for the orchestrator.
- With batch payment claims, aggregating confirmation signature validation is easier than aggregating winning ticket validation since there are less operations involved (i.e. if using something like a zkSNARK).
- The confirmation signature can be used to claim payments without any time restrictions as opposed to the ticket. The purpose of the time restriction on tickets is to incentivize orchestrators to reveal to broadcasters that a ticket won, but if the orchestrator reveals to a broadcaster that a ticket won off-chain, then there no longer needs to be a time restriction for claiming payments.

The broadcaster can refuse to provide the orchestrator with a confirmation signature after learning of a winning ticket. In this case, the orchestrator still has the original ticket which can be submitted on-chain to claim payment before the ticket expires.

The orchestrator can refuse to reveal the old random number to the broadcaster such that the broadcaster will not know that a previous ticket won. In this case, the orchestrator will still have to reveal the old random number when it claims payment prior to ticket expiration.

The downside of this solution is that for every winning ticket, the broadcaster needs to send an additional network message for the confirmation signature. Note: the orchestrator already needs to send an additional network message for the hashed commitment of a new random number once it claims payment for a ticket on-chain.

## Delayed Withdrawals

A malicious sender might try to front-run recipients that detect double spends (i.e. receiving a winning ticket resulting in a macropayment except the sender's `deposit` is insufficient to cover the macropayment) by withdrawing their `penaltyEscrow` right before a recipient's transaction which indicates a double spend (resulting in the slashing of the `penaltyEscrow`) is confirmed on-chain.

We can prevent this front-run attack with delayed withdrawals. The TicketBroker contract defines a global parameter `unlockPeriod` (an example value could be 1 week worth of blocks). When a sender wants to withdraw its `deposit` and `penaltyEscrow` it calls `unlock()` which

- Transitions the sender from the `Locked` state to `Unlocking` state until `withdrawBlock = block.number + unlockPeriod`. The sender must wait until `withdrawBlock` in order to withdraw its `deposit` and `penaltyEscrow`.
- Emits a `Unlock` event. Recpients that are currently accepting tickets from the sender can watch for this event. When this event is emitted, recpients can redeem all their winning tickets on-chain and slash the sender for any detected double spends knowing that the sender cannot move its funds until `withdrawBlock`. Furthermore, recpients can stop working with the sender once they see this event.

At `withdrawBlock`, the sender transitions from the `Unlocking` state to the `Unlocked` state and the sender can then call `withdraw` to transfer the sender's remaining `deposit` and `penaltyEscrow` to the sender's account.

If the sender wants to cancel a withdrawal, it can call `cancelUnlock()` which will transition the sender from the `Unlocking` state to the `Locked` state preventing a future withdrawal. Alternatively, if the sender calls `fundDeposit()` or `fundPenaltyEscrow()`, the sender will also transition from the `Unlocking` state to the `Locked` state.

Note that while this delayed withdrawal scheme can prevent a sender from prematurely withdrawing its `penaltyEscrow` to front-run orchestrators that detect double spends, it cannot stop a broadcaster from generating a winning ticket for another account (the randomness generation for a ticket is collaborative so if the sender is also the recipient the sender can always generate winning tickets) that it owns which then redeems the winning ticket to transfer the sender's `deposit` to the new account. Thus, a sender can front-run a recipient to double spend by giving the recipient a valid winning ticket and then emptying out the sender's `deposit` before the recipient can redeem its winning ticket. In this case, the recipient would detect a double spend and slash the sender's `penaltyEscrow`. Preventing this type of attack is a matter of ensuring a sender has a `penaltyEscrow` that can actually deter double spends which we can address separately.

## Bounding the Additional Utility of Double Spends

Given the offline nature of probabilistic payments (parties do not wait for transactions to be confirmed in a global ledger), double spends cannot be completely prevented. However, double spends can be deterred using broadcaster penalty escrows. In order for a penalty escrow to effectively deter double spends, its value must be greater than the additional utility a broadcaster can gain from double spending across multiple orchestrators. If we consider an unlimited set of orchestrators without any limits on the value transacted for each orchestrator then a broadcaster essentially has unbounded additional utility from double spending which is problematic. As a result, a probabilistic micropayment system needs to implement restrictions on the following values in order to bound the additional utility gained from double spends:

1. The time required for a double spend to be detected
2. The cumulative value of probabilistic payments sent before a double spend is detected
3. The cumulative value of macropayments (winning tickets) sent before a double spend is detected

If we can bound the above values then we can also bound the additional utility gained from double spends which can be used to derive the required penalty escrow value for broadcasters.

## Transcoding Price Menus

Orchestrators maintain transcoding price menus that specify the pricing information for various components in the transcoding pipeline such as decoding, encoding, resizing and other transformations. Given a set of desired transcoding options, anyone can derive the final price per pixel required by an orchestrator based on its currently advertised price menu. The menu also enables capability discovery. While an initial version can be simplified into a table of input and output rendition pairs matched to a price per pixel, subsequent versions can be more expressive (see this [description](https://hackmd.io/8KZ1jaEUQxmhfpcHw1hiwQ?view#Price-Menus) for an example).

A broadcaster can fetch price menus from orchestrators either just-in-time right before video needs to be transcoded or passively if the broadcaster is online by querying orchestrators at a regular interval. Whether a broadcaster is fetching price menus actively or passively, it will build up an internal database of the price menus for orchestrators in the marketplace. Thus, in the best case scenario, a broadcaster will not need to send any additional network messages when it needs video to be transcoded because it can use the price menus stored in its internal database to select orchestrators and construct tickets.

## Selecting Ticket Parameters

Each segment a broadcaster sends to an orchestrator will include the following metadata:

- *inputRendition* - The video profile of the input video.
- *transcodingOptions* - A string containing a serialized list of video renditions corresponding to the desired transcoded renditions for the input video.

An orchestrator will accept a ticket as payment based upon the ticket's *faceValue* and *winProb*. There are a few considerations when choosing values for these parameters:

- *faceValue* - The value of a winning ticket. This parameter along with *winProb* determines the expected value of a ticket which represents a payment for *pixelsPerTicket* number of pixels. A higher value increases the opportunity cost of capital lock up for the broadcaster because 1) the broadcaster will want to pad its deposit by a larger amount to protect itself from the scenario where it sends out consecutive winning tickets that would otherwise completely drain its deposit 2) the broadcaster will need a larger penalty escrow that properly reduces the economic incentive for double spending a ticket with a large face value. At the same time, a higher value allows for a lower *winProb* value which can decrease Ethereum transaction costs for the orchestrator.
- *winProb* - The probability of a ticket winning. This parameter along with *faceValue* determines the expected value of a ticket which represents a payment for *pixelsPerTicket* number of pixels. A lower value decreases the Ethereum transaction costs incurred by an orchestrator since there are less winning tickets to claim, but results in a higher *faceValue*.

Orchestrators will advertise a minimum *faceValue* for all tickets which is calculated as follows:

# Use the current average gas price and multiplier (larger or
# smaller depending on desired speed of transaction confirmation)
# to calculate the gas price to be used for transaction submission
gasPrice = gasPrice * GAS_PRICE_MULTIPLIER

# Assume that the gas usage for claiming a ticket is well defined
transactionCost = TICKET_CLAIM_GAS * gasPrice
minFaceValue = transactionCost * ticketMargin

For a desired set of transcoding options, a broadcaster can use its internal database of price menus for an orchestrator to calculate *pricePerPixel*. The expected value of a ticket *expTicketValue* is calculated as:

expTicketValue = pricePerPixel * pixels

where *pixels* is the number of pixels a ticket will pay for. This value does not need to be agreed upon ahead of time - from an orchestrator's point of view it just cares about `expTicketValue` (which is derived from *faceValue* and *winProb*). As a result, this creates flexibility for a broadcaster to decide the frequency of ticket emission because a broadcaster can not only control the size of segments, but also the number of pixels each ticket pays for.

The broadcaster sends a ticket with *faceValue* and *winProb* to the orchestrator whenever the following condition is true:

pixelCount * pricePerPixel >= expTicketValue

The orchestrator will also monitor the broadcaster's deposit and if the deposit is ever insufficient to cover *faceValue*, the orchestrator will stop transcoding segments and disconnect from the broadcaster (at this point the orchestrator is able to claim the ticket to drain the broadcaster's deposit and slash the broadcaster's penalty escrow).

## Transcoding Verification

A broadcaster can define *verificationInterval* - it will wait to receive this many sets of transcoded segments (where each set of transcoded segments contains a transcoded segment for each of the requested video profiles) before running an internal verification protocol that consists of randomly sampling all the transcoded segments received thus far and running a heuristic based transcoding verification task on each of the sampled transcoded segments along with their corresponding input segments. If the task fails for any of the segments, the broadcaster can initiate an on-chain challenge that invokes an on-chain verification contract that could be backed by a verifiable computation system (i.e. Truebit).

If we have long unbonding periods for orchestrators, broadcasters that suspect malicious behavior by orchestrators (perhaps because they watched their own stream and something looks off) have a stored record with signatures from orchestrators so they could always perform offline forensics to find segments that were not transcoded properly that would fail on-chain verification.

TODO: Settlement period for ticket claims to allow broadcaster funds to be clawed back if successful on-chain verification to slash the orchestrator is triggered? Would be pretty annoying to have this per ticket. Might be ok with batch payment claims. Without batch payments claims, might be ok to not have a settlement period and not give broadcasters guarantees of ability to claw back funds - instead they know that if they find misbehavior they know the economic value associated with the orchestrator that they can burn. Need to think about this.

## A Note on VOD

While probabilistic micropayments is a compelling payment mechanism for live video transcoding, it does not work as well for video on demand (VOD) transcoding. An ideal VOD transcoding workflow would have the broadcaster send all video segments up front and the orchestrator would return the transcoded data at some later time. This "fire and forget" workflow results in a fair exchange problem: how do we guarantee that the broadcaster receives all of the transcoded video and that the orchestrator receives the full payment at the later time? A tit-for-tat micropayment based strategy using a mechanism such as probabilistic micropayments works around the fair exchange problem (since either party can drop out if the other stops responding with minimal harm to either party) at the cost of increased network interaction overhead.

We leave the design of a fire and forget VOD transcoding compatible payment mechanism for the future.