Incentive-Alignment: Approval Voting

[Lldenaurois]

Problem Statement

In the current protocol, validators have no incentive to complete the Approval Voting step and advance parachain block finality. This needn't necessarily present an attack surface since we assume that 2f among 3f+1 validators are honest and do not deviate from the consensus protocol, but it could present a mis-alignment of incentives that causes some validators who run on less performant hardware to fall-behind without any incentives to upgrade their hardware. If multiple validators fall subject to this equilibrium, the entire network could incur significant finality lag.

Overview

Therefore, we present a simplified lottery scheme that enables validators to incur a benefit for their approval assignment and subsequent approval vote. One particular aspect of the scheme we present below is that validators will only incur an incentive if they are able to issue their approval vote in the 0-th tranche. The reason for this is two-fold:

1. By issuing incentives only for Approval Votes in the 0-th tranche, we ensure that the incentive structure is heavily skewed towards preferring to complete Approval Voting as fast as possible, thereby incentivizing validators to run Approval Voting in the most efficient fashion.
2. The scheme we present does not apply to later tranches because in any tranche after the 0-th tranche there exists an incentive to collude with other validators to present Approval Votes without the work having ever been computed honestly.

Background

PendingMessage::Assignment includes an IndirectAssignmentCert, which includes a relay_block hash, validator index and AssignmentCert.

In addition, the AssignmentCert includes both a VRFOutput and VRFProof.

When a validator receives a PendingMessage::Approval, this includes a signature on the ApprovalVote(CandidateHash) and the SessionIndex under their ValidatorKey.

Both Assignments and Approvals are gossip'd among all validators in the validator network via the ApprovalDistribution subsystem.

Construction

Validators keep track of the VRFOutput for all PendingMessage::Assignments. When PendingMessage::Approvals are received over-the-wire for approvals in the 0-th tranche, the receiving validator can sign the approving validator's VRFOutput with their own VRFKey to issue an ApprovalTicket. ApprovalTickets are valid extrinsics that will issue rewards on-chain for both the Voter and the Ticket issuer.

Every time another validator receives an PendingMessage::Assignment over the wire (in ApprovalDistribution), the IndirectAssignmentCert is imported into the ApprovalVoting subsystem via the CheckAndImportAssignmentMessage. The validator should store the IndirectAssignmentCert for that assignment, i.e. in a HashMap<(SessionIndex, CandidateHash), IndirectAssignmentCert>. The ApprovalVoting subsystem should prune entries for these entries as new blocks are finalized.

As subsequent PendingMessage::Approvals are received over the wire, they are imported into the ApprovalVoting subsystem, upon validating that an approval was issued for the 0-th tranche, the ApprovalVoting subsystem should spawn a task that request a signature on the associated ApprovalAssignment's VRFOutput under their VRF key. When this VRFProof is received, the task concludes and produces an ApprovalTicket.

This ApprovalTicket defines a method which translates this ApprovalTicket into an extrinsic which is subsequently gossip'd amongst all validators.

A block producer can collate these extrinsics (From<ApprovalTicket>), and subsequently include them in their block.

[rphmeier]

We want to avoid keeping too many assignments in memory in case finality lags for some reason. It could blow up to gigabytes relatively quickly.

We also only need to draw tickets on RelayVRFModulo assignments, not on other kinds. Tranche 0 should be almost entirely populated by RelayVRFModulo.

Rather than having a separate task for each lottery drawing, it would make more sense to have a simple lottery worker task which does nothing but draw tickets.

I'd like some more discussion of requirements in the runtime in order to verify tickets - for example, where we keep the historical mapping of included candidate hashes and candidate indices, as well as where we keep historical BABE VRFs. The disputes module already keeps track of the historical candidates, although not their cores, so we can extract that out to the shared module, perhaps, or put it in the inclusion module.

We don't need a separate gossip system, but we should have something like a runtime API for transforming ApprovalTicket into an extrinsic - this has to be done through a runtime API because the node-side code doesn't have information about the transaction format.

[burdges]

I'd consider this text miss-leading:

1. By issuing incentives only for Approval Votes in the 0-th tranche, we ensure that the incentive structure is heavily skewed towards preferring to complete Approval Voting as fast as possible, thereby incentivizing validators to run Approval Voting in the most efficient fashion.
2. The scheme we present does not apply to later tranches because in any tranche after the 0-th tranche there exists an incentive to collude with other validators to present Approval Votes without the work having ever been computed honestly.

We're merely proposing to only reward RelayVRFModulo because doing so is fairly easy and will push validators into running better hardware, and sampling can be made light enough for the optimized relay chain.

---

We've three assignment types,

• RelayVRFModulo occupies most of tranche zero and most checks overall,
• RelayVRFDelay serves two roles of "toping up" the assignments and replacing no shows,
• RelayEquivocation works like RelayVRFDelay so that it can top up and replace no shows, but seeds based upon candidates that differ between equivocations, so that equivocation in block production cannot give an adversary advance knowledge of approval checkers.

We should reward all three types but we currently verify RelayVRFDelay and RelayEquivocation assignments subjectively off-chiain, and verifying them deterministically on-chain requires running the whole approval scheduler gadget on-chain. We designed the approval scheduler gadget to run on-chain for that purpose, but.. We must do more optimization work first, including making system functionality run on parachains since this rewards system itself would likely run on a parachain.

We've no such concern with RelayVRFModulo since tranche zero assignments are objective, which then makes random sampling possible. It's false this rewards being fast since a slow tranche zero assignment trumps its no-shows, even in the off-chain approval scheduler gadget. Afaik, it's false that rewarding later tranches incentivizes collusion, because either a no-show gets replaced by the gadget or not, which then controls rewards. As I said, we're merely proposing to only reward RelayVRFModulo because doing so is easy and will push validators into running better hardware, and sampling can be made light enough for the optimized relay chain.

As an aside, if we consider the future on-chain approval scheduler gadget again, then there is a "malicious no-show" concern where Eve no-shows so that random honest validators Alice and Bob begin checking, and then Eve completes her check. As Eve makes Alice and Bob waste resources for work for which they'll never be paid, Eve thus forces Alice and Bob to provision more expensive hardware or bandwidth than Eve requires. We doubt this helps Eve much though. In fact, the future on-chain approval scheduler gadget should not slowly accumulate assignments and approval votes on-chain, but instead make one block producer place all assignments and approval votes on-chain simultaneously, meaning Eve then races with block producers and might occasionally loose. We could tweak block production logic to increase the rate at which Eve loses, although doing so sounds ugly.

Just fyi, we've not even implemented RelayEquivocation because exploiting such knowledge is extremely dangerous and requires extensive development time.

[burdges]

VRFOutput is renamed to VRFPreOut in schnorkel because it's actually not the output. You obtain the output by calling make_bytes or make_rng::<ChaChaRng> to hash the input and output together.

At a formal level, we view this hash as a random oracle and thus as a pseudo-random function family keyed by the output and run on the input. VRFOutput alone yields only a verifiable unpredictable function (VUF), which actually suffices for many purposes, but hashes are cheap so why bother with VUFs?

---

ApprovalTickets have five parts:

1. Reference to a candidate being included,
2. Reference to a BABE VRF output for the relay chain block where included.
3. Assignment VRF that inputs the BABE VRF output
4. Approval vote,
5. Ticket authorization VRF that inputs the Assignment VRF output.

I think both 1 and 2 should ideally be MMR proofs of recent block headers and bodies, but maybe some reference into the chain state directly too. We'll want the MMR stuff for doing this or the full gadget on a parachain anyways I think.

I'll remark that 5 could sign the whole transaction, which we do for assignments, but this is a small optimization and not required.