Fair exchange payments for VOD transcoding

Nobody has claimed this yet.

## Terms

B = Broadcaster
O = Orchestrator
T = Transcoder

## Background

While live video transcoding requires continued interaction between B & O, VOD transcoding does not need to be performed in real time which allows for a number of desirable outcomes (as pointed out by @j0sh and @f1l1b0x):

- B does not need to remain available during the transcoding process. Instead, B can "fire and forget" by sending all segments to O and then discontinue network interactions until a later point in time thereby removing B as a bottleneck in the transcoding process.
- After receiving all the segments, O can decide when to perform the transcoding depending on current network demand and spreading out work across low demand periods which can result in lower services costs for O.
- O can parallelize work by dividing B's segments into different batches that can be passed to multiple Ts. Once all the work is complete, O can stitch the segments back together to form the end mp4 file to be sent to B. This type of workflow would result in much faster and more efficient VOD transcoding (i.e. faster than real-time).

In order to achieve these properties, the protocol requires a method of fair exchange without a trusted third party. Fair exchange is defined by the following scenario: Alice & Bob both have goods that they would like to atomically trade with each other such that either both parties receive the goods or neither party receives the goods. Unfortunately, there is cryptography paper stating that [fair exchange is impossible without a trusted third party](https://pdfs.semanticscholar.org/208b/22c7a094ada20736593afcc8c759c7d1b79c.pdf). We can get around this issue in a live video context using micropayment mechanisms based on payment channels or probabilistic micropayments and a tit-for-tat strategy that allows either party to drop out if service stops (i.e. B stops paying or O stops sending transcoded segments). However, using micropayment mechanisms with a tit-for-tat strategy results in continued interaction between B & O which would prevent the protocol from achieving the properties outlined above. Fortunately, there is a workaround to the impossibility result using a cryptoeconomic scheme [1].

The Ethereum research team fleshed this scheme out further into a proof of custody construction that is meant to be used as a part of the sharding architecture [3], but we might be able to borrow it for VOD job payments at least as a base. Here is the beginning of one possible workflow:

## Workflow

1. B & O negotiate a price per pixel based on B's requires transcoding options which allows B to calculate the total price for a VOD job.
2. B deposits the full payment for the VOD job into a contract and indicates a block in the future `endBlock` as the deadline for completing the VOD job.
3. B sends all the segments for the VOD job to O. O checks that the payment in the contract is appropriate based on the agreed upon price per pixel and the received segments.
4. At some point before `endBlock`, O transcodes all of the segments and creates an mp4 file `F` representing the end transcoded output. O splits `F` into 32 byte chunks and merklizes the chunks to create `MerkleRoot(F)`.
5. O uses a secret `S` to XOR with each of the 32 byte chunks of `F` which results in an output `T(F)`. O then merklizes the chunks of `T(F)` to create `MerkleRoot(T(F))`.
6. O submits `MerkleRoot(F)` and `MerkleRoot(T(F))` to the contract as commitments to the transcoded mp4 file. If O does not submit these commitments to the contract before `endBlock`, B can withdraw its payment.
7. O sends B `T(F)`. Upon receiving `T(F)`, B checks if the merklized chunks of `T(F)` match the commitment `MerkleRoot(T(F))`. B then notifies the contract which kicks off a reveal period that ends at `endRevealBlock`. If O does not send B anything, B just waits until `endBlock` to withdraw.
8. O submits the secret `S` to the contract which kicks off a challenge period that ends at `endChallengeBlock`. If O does not submit the `S` before `endRevealBlock`, then O is slashed.
9. B uses `S` to retrieve the original chunks of `T(F)`. Let `F'` be the file formed by putting together the unmixed chunks of `T(F)`. If B finds that `MerkleRoot(F') != MerkleRoot(F)`, B plays a TrueBit-like binary search challenge game with O.
10. B picks a random index `i` and asks O for the Merkle proof for the inclusion of chunk `i` in `MerkleRoot(F)`. If this chunk `i` corresponds to the chunk with the same index in `F'` we proceed with the binary search algorithm described in [3]. The idea is that B can keep narrowing down the number of chunks until it finds a chunk in `MerkleRoot(F)` that does not match the chunk it has for `MerkleRoot(F')`. Once the incorrect chunk `m` is found B can submit the proof for the inclusion of chunk `m` in `MerkleRoot(F)` and the proof for inclusion of the mixed chunk `m` in `MerkleRoot(T(F))`. The contract will verify the proofs, use the secret `S` to unmix the chunk for `MerkleRoot(T(F))` and compare it with the chunk for `MerkleRoot(F)`. If the chunks are different then O is slashed. This game can be played off-chain, but if O stops responding (because it knows it will lose), B can take the game on-chain (although I think O can always grief B if it knows it is going to lose and always make B take the game on-chain to incur transaction costs). If the game is taken on-chain and O does not respond within some timeout period, O is slashed.
11. If `MerkleRoot(F') == MerkleRoot(F)`, O can withdraw B's payment from the contract after `endChallengeBlock`. The payment is sent to the BondingManager contract to be distributed amongst O and its delegators.

This scheme only tries to allow B to pay O atomically for a transcoded file (i.e. O only gets paid if B gets the file), but makes no guarantees that the file is correctly transcoded. After B obtains the file, it could run through a verification process or maybe there could be another period in this scheme allowing for B to challenge O for verification before O gets paid if B determines that a segment was incorrectly transcoded.

## Additional Resources

Most of the described workflow is based off ideas from the following posts:

[1][Fair exchange without a trusted third party](https://ethresear.ch/t/fair-exchange-without-a-trusted-third-party/255)
[2][Enforcing windback (validity and availability), and a proof of custody](https://ethresear.ch/t/enforcing-windback-validity-and-availability-and-a-proof-of-custody/949)
[3][Extending skin-in-the-game of notarization with proofs of custody](https://ethresear.ch/t/extending-skin-in-the-game-of-notarization-with-proofs-of-custody/1639)

Start by reading the proposed Workflow, especially the contract deadlines, Merkle-root commitments, reveal period, and challenge game. Review the linked fair-exchange and proof-of-custody resources, then define an implementable protocol for atomically paying for VOD transcoding and specify how correctness challenges and verification should be handled.

Written by the indexing model from the issue text.