Broadcaster transcoding verification challenge protocol

[yondonfu]

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 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.

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)

[ericxtang]

Another aspect of this research project is the verification algorithm itself. Currently, the proposed solution is a logistic regression based classifier trained with a dataset published by Livepeer. It's important to think about:

• How this algorithm can be improved overtime, preferably in an automated and incentivized way.
• How to fall back to a more expensive but accurate method when the classifier fails.
• Whether the classifier can be ran in a completely decentralized context with something like Truebit.

Another suggestion is to add the requirement of Parameterized transcoding, where the transcoding setting can be an input, and be captured in the verification workflow.

[yondonfu]

@ericxtang Yeah the verification task/algorithm is certainly a crucial component of the larger verification system - we are already capturing the details around the verification task/algorithm in the transcoding verification research project and this problem statement seeks to capture the details around when the verification task should be run (see the distinction outlined in the "Brief Description" section).

The two research projects will be closely related though and will likely benefit from consistent communication of results/insights!

Another suggestion is to add the requirement of Parameterized transcoding, where the transcoding setting can be an input, and be captured in the verification workflow.

👍 I've added this to the requirements section as Parameterized transcoding options.

[yondonfu]

Here is an updated version of the candidate construction that would support mutually agreed upon verification oracles (i.e. different verification tasks such as bitxeact or metrics based probabilistic verification)