Broadcaster transcoding verification challenge protocol

Title: Broadcaster transcoding verification challenge protocol
Author: @yondonfu

# Brief Description

Transcoding verification in the Livepeer network is a three part problem:

- Part 1: What is the verification task that can be used to verify the validity of a transcoded result for an input segment and the requested transcoding options (i.e. rendition)?
- Part 2: Who runs the verification task and submits the result to slash an orchestrator in the event of a fault? How do interested actors determine that the verification task was executed correctly?
- Part 3: When should the verification task be executed?

This problem statement will focus on part 3. In the V1 protocol, the verification task is executed when an orchestrator (using Streamflow terminology - they are referred to as transcoders in V1) submits a segment for verification which consists of the following steps:

- The orchestrator commits to a range of [transcode receipts](https://github.com/livepeer/wiki/blob/streamflow/SPEC.md#transcode-receipt) using a Merkle root (the leaves of the tree are the receipts). Each receipt corresponds to a segment that the orchestrator claims to have transcoded.
- After the commitment transaction is confirmed, the hash of the following block is used as a pseudorandom source along with the current global verification rate (i.e. 1 out of 1000 segments) to challenge segments included in the orchestrator's commitment.
- The orchestrator must submit each challenged segment for verification which entails providing input segment metadata, transcoded result metadata and the IPFS storage location of the input segment data. The verifier is expected to run the verification task on the input segment data pulled from IPFS.

For more details on the V1 challenge protocol, see the [V1 spec](https://github.com/livepeer/wiki/blob/streamflow/SPEC.md#claiming-and-verifying-work).

A few of the downsides of the V1 challenge protocol include:

- Expensive verification costs for an honest orchestrator. These costs include ETH transaction costs today, but in the future could include additional costs native to the protocol used for executing the verification task (i.e. Truebit)
- Data availability. The orchestrator is responsible for keeping the input segment data available on IPFS, but is also disincentivized from making it available - if the verifier is unable to fetch the data, then it is unable to run the verification task. There are additional issues with untrusted verifiers (i.e. Truebit) around distinguishing between cases where a orchestrator falsely claims that data is available and cases where a verifier falsely claims that data is not available, but we leave these issues for discussion external to this problem statement.
- Complexities involved with submitting a commitment for a discontinuous range of receipts (in V1, the range is continuous for simplicity).

As a part of Streamflow, we are exploring a challenge protocol that is broadcaster driven as opposed to orchestrator driven. The broadcaster is responsible for running a verification task locally on a sample of transcoded results returned from an orchestrator and challenging segments for verification.

The problem we are interested in solving is how a broadcaster should detect segments to challenge and how it should invoke the challenge. We proceed to discuss the specific requirements for a broadcaster transcoding verification challenge protocol below.

# Problem Statement

## Use Cases

A broadcaster transcoding verification protocol must fulfill or preserve the following use cases:

- A broadcaster should be able to detect invalid transcoded results
- A broadcaster does not have to verify every single transcoded result
- A broadcaster can control how often transcoded results need to be verified
- A broadcaster should be able to submit a segment for verification with high confidence that it will result in a slashing proof for a byzantine orchestrator.

## Requirements

- **Parameterized verification rate**: The broadcaster can set the value of a verification rate parameter that determines how often transcoded results need to be verified locally. The value used reflects a tradeoff between safety and cost.
- **Parameterized transcoding options**: The broadcaster should be able to challenge a segment and trigger verification using a specific transcoding option (i.e. rendition).
- **Segment data cryptographically bound to broadcasters**: The verifier needs to be able to verify not only that the input segment data provided for verification is actually the data that an orchestrator used to produce a transcoded result, but also that the data originated from a particular broadcaster
- **Transcoded results cryptographically bound to orchestrator**: The broadcaster needs to not only challenge invalid transcoded results, but also prove that the results were produced by a particular orchestrator.

## Reasonable Assumptions

- **Low overhead verification task**: The verification task incurs a low overhead that is less than that of re-transcoding a segment (i.e. bitexact verification) and it is thus economical for the broadcaster to run the task itself. Note: The metrics based transcoding verification research project should determine whether this assumption is valid longer term.
- **Access to off-chain storage**: The data used for verification is too large to be submitted on-chain, so thus need to be stored off-chain. The details of the storage provider can be ignored for the purposes of this problem - the provider could be S3, IPFS, Swarm, etc. We assume that both the broadcaster and verifier will have access to the provider such that data can be stored/pinned and fetched in a timely manner.
- **Centralized verifier**: For simplicity, we assume that the verifier responsible for executing the verification task during a challenge and submitting a result to slash an orchestrator in the event of a fault is a single privileged and trusted actor.
- **Verifier knows about all valid transcoding options**: We assume that all the possible transcoding options on the network are known to the verifier and that the verification task is capable of doing checks for all of these options.

# Candidate Constructions

## Local verification of random samples

For every input segment `seg_data` with a set of requested transcoding options `t_opts` that a broadcaster sends to an orchestrator, the broadcaster also sends the signature `b_sig = sign(b_priv_key, H(seg_data) + H(t_opts))`. `b_sig` cryptographically binds the input segment and the set of transcoding options pair to the broadcaster.

For every transcoded result `t_res` that for an input segment `seg_data` that an orchestrator sends to a broadcaster, the orchestrator also sends the signature `o_sig = sign(o_priv_key, H(seg_data) + H(t_res))` to the broadcaster. `o_sig` cryptographically binds the input segment and transcoded result pair to the orchestrator.

The broadcaster defines a verification rate parameter `v_rate` - every `v_rate` segment that it sends, the broadcaster will randomly sample a transcoded result from the set of all transcoded results received for the last `v_rate` segments.

Let `seg_data` be the sampled input segment, `t_opts` be the set of transcoding options for the sampled input segment, `t_res` be the sampled transcoded result and `t_res_opt` be the specific transcoding option (i.e. rendition) corresponding to `t_res`. The broadcaster runs the verification task using `seg_data`, `t_res` and `t_res_opt` which results in a pass or fail. If the verification passes, the broadcaster does nothing. If the verification fails, the broadcaster initiates an on-chain challenge:

1. The broadcaster uploads `seg_data` at `seg_data_storage` and `t_res` at `t_res_storage` at a storage provider i.e. IPFS
2. The broadcaster submits `H(seg_data)`, `H(t_res)`, `t_res_opt`, `t_opts`, `o_sig`, `b_sig`, `seg_data_storage` and `t_res_storage` to the verification contract.
3. The verification contract checks that `o_sig` is valid for `H(seg_data)` and `H(t_res)`
4. The verification contract checks that `b_sig` is valid for `H(seg_data)` and `H(t_opts)`
5. The verification contract checks that `t_res_opt` is in `t_opts`
6. If the above checks pass, the off-chain verifier fetches `seg_data` from `seg_data_storage` and `t_res` from `t_res_storage`. The off-chain verifier checks that `seg_data` matches `H(seg_data)` provided on-chain and that `t_res` matches `H(t_res)` provided on-chain.
7. The off-chain verifier runs the verification task using `seg_data`, `t_res` and `t_res_opt`. The result (pass or fail) is submitted back to the contract.
8. If pass, nothing happens. If fail, the orchestrator (address recoverable from `o_sig`) is slashed.

## Open Problems/Questions

- Should orchestrators be slashed multiple times if multiple broadcasters initiate challenges that are successful? If so, should the orchestrator be kicked out (making it not slashable) after some point?
- In the V1 protocol, slashed funds are burned. Is there any value in sending slashed funds to the broadcaster that initiated a successful challenge?
- When using a protocol like Truebit for executing a verification task, the task giver is required to provide a deposit in order to not only incentive third party verifiers. We assume that a centralized verifier is altruistic and does not require an economic incentive to check work. However, without this deposit requirement, the centralized verifier could be vulnerable to spam/griefing attacks - a broadcaster can initiate challenges that force the centralized verifier to execute the verification task and submit results back on-chain. If the transaction cost for initiating a challenge < the computation task of executing the verification task + the transaction cost of submitting the result back on-chain, then there is a griefing factor > 1 meaning for every $1 cost incurred by the broadcaster, it can incur > $1 of harm to the verifier. The broadcaster likely needs to be bonded (i.e. lock up capital) to initiate a challenge and if the challenge is successful the broadcaster gets its bond back.

# Objectives & Key Results

**Objective 1**: Design a broadcaster transcoding verification challenge 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 broadcaster transcoding verification challenge 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] V1 protocol challenge protocol ([spec](https://github.com/livepeer/wiki/blob/streamflow/SPEC.md#claiming-and-verifying-work))

Start by reading the linked V1 protocol specification, then compare its challenge flow with the broadcaster-driven construction in this issue. Work through the stated requirements, assumptions, candidate protocol, and open problems. Done means producing either a technical specification and security explanation, or an explanation that the protocol is impossible with revised requirements and assumptions.

Written by the indexing model from the issue text.