Dynamic commitment subsets pre-proposal

Context

The Livepeer protocol uses probabilistic micropayments (PM) as a payment model. The probabilistic micropayment model allows to aggregate bulks of payments associated to off-chain work and to settle them on-chain while 1) preserving a high level of pricing granularity 2) providing security guarantees to both the consumer (broadcaster) and the worker (orchestrator). In order to ensure that an orchestrator cannot be cheated by a malicious broadcaster, a broadcaster is required to escrow an amount of collateral equal to the maximum free value that they can extract from the network. The upper bound of extractable free value can be calculated as: size(O) * Max(U), where size(O) is the size of orchestrators set and Max(U) is the maximum estimated value of the utility that each orchestrator provides to a broadcaster.
The main downside of the described approach is that it binds a broadcaster’s collateral requirements to the size of the set of orchestrators in a directly proportional fashion. Subsequently, as to avoid mandating unreasonable collateral requirements to broadcasters, a hardcap to the number of orchestrators has been set in the protocol.
The goal of the current pre-proposal is to draft a solution to remove the orchestrator hard-cap from the protocol without proportionally increasing the capital requirements for broadcasters.

Proposed solution

The current collateral requirements assume that every orchestrator (O) is equally eligible to perform transcoding work for a broadcaster (B). In practice, and specifically in the case of Livepeer, that is not the case: as transcoding is a highly performance-oriented activity, the portion of suitable Os for a broadcaster is inevitably a subset of the global set of active Os. As such, forcing a B to provide collateral for the entire set of Os proves to be capital inefficient.
An alternative course of action is to allow a B to select a subset of Os - from now on referred as commitment subset. The underlying rationale is that:

  1. it would linearly decrease the collateral requirements for Bs.
  2. it is in the best interest of a rational B to select suitable Os. Hence, not only such a feature would not lead to any undesirable centralization side-effect but, by removing the constraint of a maximum number of Os, it would enable more Os to join the Livepeer network. A higher number of Os means that more Os would compete to provide a better service to Bs. Tangentially, an overall better QoS might drive up the demand-side of the network, ultimately leading to a network effect that would benefit both Bs and Os.

An additional benefit of the proposed solution is that it is focused towards optimizing the current micropayment model rather than switching to a completely new system.
On a high-level, a B would run an off-chain O discovery process either at regular intervals or on demand. The off-chain discovery process would include the selection of a subset of size K of the most suitable Os. The list of the selected O addresses would then be hashed as leaves of a Merkle Tree to generate a Merkle root. The computed Merkle root would then be added as an additional field to the current schema of a ticket. Additionally, some other fields (i.e.: the O’s leaf in the Merkle Tree) might be added as to facilitate the O’s task of generating a proof of membership in the given Merkle Tree. Subsequently, an O would then be considered eligible to redeem a B’s winning ticket if their address is part of the Merkle Tree representing the B’s commitment subset. An additional constraint that would put in place an ‘expiration date’ to the commitment set is being considered: if validated, it would mean that the eligible O would have x + n rounds to redeem their winning ticket.
Some other edge cases and constraints that have been evaluated:

  • The proposed solution allows a Broadcaster to commit to multiple commitment subsets at the same time. This is to take into account possible edge cases where the B’s initially selected subset of Os proves to be unsuitable at a later time - either partially or fully. In that case, a B would be able to promptly commit to another O subset - with the side-effect that they would have to escrow additional collateral for the newly generated subset.
  • The proposed solution attempts to decouple the O selection mechanism from the O commitment mechanism as much as possible. This is aligned with the view that computationally intensive tasks should be performed off-chain, whereas the main responsibility of the on-chain business logic is to be the security layer for the economic activity of the protocol. This means that the current proposal is not strictly concerned with what criteria should be used off-chain to select the Os - which should also allow to progressively refine them or refactor them without resulting in protocol contracts’ upgrades.
  • As to guarantee the economic security of both Bs and Os, the implementation of the current proposal shall:
  1. Ensure that an orchestrator cannot redeem the same winning ticket twice from the same broadcaster.
  2. Ensure that an orchestrator cannot redeem the same winning ticket twice from different broadcasters.
  3. Ensure that different broadcasters with the same orchestrators commitment subset generated during the same roundId are associated with different merkle roots.
  4. Ensure that the broadcaster cannot change the Merkle Root (or an alternative data structure) representing the commitment subset in a way that would compromise the fair payment of an O (i.e: changing it within an ongoing round where an O has performed/is in the process of performing work for a B)

Data structures

mapping(address broadcasterAddress => mapping(uint256 commitmentCounter => bytes32 commitmentSubsetMerkleRoot)) broadcasterCommitmentSubsets;

mapping(address => mapping(uint256 commitmentCounter => Reserve)) reserves;

commitmentCounter is a monotonically increasing integer whose purpose is to:

  1. allow a B to commit to different O subsets simultaneously
  2. allow an O to query the funds (deposit + reserve) associated to a commitment subset, i.e.:
function remainingReserve(address _reserveHolder, uint256 _commitmentCounter) internal view override returns (uint256) {
        return reserves[_reserveHolder][_commitmentCounter].funds;
    }

Broadcaster commitment to Orchestrator subset interface

/**
 * @dev Sets a broadcaster's subset of eligible orchestrators
 * @param _commitmentSubsetMerkleRoot merkle root derived from the merkle tree whose leaves are the addresses of the selected orchestrators
 * @param _commitmentSubsetExpiry roundId after which the commitment would stop being valid
 */
function setCommitmentSubset(
    bytes32 _commitmentSubsetMerkleRoot, 
    uint256 _commitmentSubsetExpiry
) external;

Protocol Refactoring

In case the pre-proposal will be approved, the implementation of the drafted solution will include the refactoring of:

  • the B’s ‘unlock’ and ‘withdrawal’ logic
  • the O’s ticket redemption logic
  • possibly, the data structure - doubly linked list- currently representing the O pool
  • adding additional fields to the Ticket struct and, possibly, refactoring how its hash is being calculated

Alternative data structures

Some alternative data structures are being considered for the implementation of the present solution:

  • a bitmap rather than a merkle root. A broadcaster could represent their commitment subset with a bitmap. The bitmap would be such that the i-th bit would represent the i-th O in the current set of actively registered Os: 1 would represent the membership of the given O in a B’s commitment subset and 0 would represent its non-membership. The main advantages of the bitmap approach are its gas consumption and that it’d probably require less refactoring of the internal data structures representing the globally active O set than the Merkle Tree approach. The main concern would be that it provides less security guarantees than the cryptographic proof of membership provided by Merkle Trees - which would warrant a more thorough audit effort.
  • a global B ‘reserve vault’ rather than a reserve associated to each commitment subset. The required reserves of the global reserve vault would be calculated based on a counter keeping track of the total number of orchestrators in the currently active commitment subsets of a B. This would allow to have more lean data structures and a better UX for B withdrawals.

Note

The implementation specs drafted above have not been yet rigorously tested and might be subject to changes if they will be proven incorrect or should a better implementation be found. However, even in case of changes, the implementation specs will conform to the present proposal in case it will be approved.

3 Likes

This looks great Riccardo, thanks for getting this together! One initial question I have is with the storage of the commitment Merkle tree leaf nodes to construct the proof - there would need to be some off-chain communication between B <> O to ensure the Orchestrator has the leaf nodes available for proofs (to be able to redeem tickets). I would imagine this would mean that we would need the O to cache leaf nodes each time they receive a ticket or a pointer to storage in IPFS? Also, I am not familiar with how many broadcaster nodes can be run at once, but if there can be more than one, how would broadcasters communicate those leaf nodes to each other?

Broadcasters can choose the Orchestrators they want to broadcast to, it would be a good place to start if that automatically modified the deposit requirements, but I’m sure it’s much more complicated than that.