Proof of custody game design

[vbuterin]

The basic proof of custody mechanism works as follows:

• For every (eg. 2 week) period p, each validator calculates rk[p] = BLS_sign(key=validator_privkey, msg=p) as their round key.
• For every crosslink they participate in during that period, if that crosslink has data with chunks D[0] ... D[size(D)-1], for each D[i] they compute C[i] = mix(rk[p], D[i]) where mix is some function where for any rk, mix(rk, x) depends on x. They compute R = custody_root(D) as Merkle root of the C[i] values and sign R mod 2 along with the crosslink (this is their "custody bit")
• During period p + 1, the validator must reveal prevseed=rk[p], and the chain can verify that it is a correct value via BLS_verify(key=validator.pubkey, msg=p, sig=prevseed)

There are three types of byzantine behavior that we want to penalize:

1. Revealing rk[p] too early
2. Signing with some random custody bit because D is unavailable
3. Signing with the incorrect custody bit because even if D is available, the validator wishes to be malicious

For (1) we can have a special-purpose slashing condition; the only requirement is that anyone must be able to trigger the condition and gain from doing so, so there should be a commit-reveal game to allow participants to trigger it without the block proposers being able to frontrun them.

(2) and (3) are similar cases, except (3) is more tractable. In case (3), once rk[p] is revealed, any third party can recompute custody_root(D), check if the bit matches, and if the bit does not match start a challenge game, which they know ahead of time they will be able to win. First, they challenge to ask for the complete custody root, which must match the bit that has already been provided. At this point, the responder is free to respond with an arbitrary value of R that matches the same bit; for any D, it is almost always possible to find some data D' which differs from D in only one block where custody_root(D') mod 2 is either 0 or 1. At this point, the responder has (and the challenger knows that the responder has) committed to some value which is not equal to custody_root(D).

The next step is for the challenger to ask for the two children of R' (we'll call them C0 and C1). When the responder responds, the challenger can check which of the two don't match the corresponding values in the real custody Merkle tree for D. The challenger then asks for the two children of either C0 or C1. This repeats log(size(D)) times until eventually the responder must respond with some C[i] as well as a Merkle branch for the corresponding D[i]. The chain will check and find that the provided C[i] does not match mix(rk[p], D[i]), and the responder can be penalized and the challenger can win. At this point, if the responder responds correctly, the challenger can be penalized.

Note that this whole process is only possible if all of D is available, so challengers can know whether or not they can successfully challenge. If D is not available, then we also need a challenge game which allows participants to ask for specific branches of D and demand an answer. Because data availability suffers from fisherman's dilemma problems, it's likely participants will not bother challenging unless challenging is free; hence, the proposed solution is to only allow block proposers to challenge, and give them a free allotment of challenges in each block, expecting them to fill the allotment.

Now, we have four types of challenges:

1. Input: attestation A, validator index v, data index i. Output: a Merkle branch of D[i] with the root matching A.data_commitment.
2. Input: attestation A, validator index v. Output: a root R matching get_custody_bit(A, v)
3. Input: attestation A, validator index v, index i, depth d, branch B, where B has as root the R value previously submitted by validator v. Output: the two children whose parent is the leaf in B.
4. Input: attestation A, validator index v, index i. Output: a Merkle branch of D[i] and C[i] with the roots matching A.data_commitment and the R value previously submitted by validator v.

Note that we can increase efficiency by merging (1), (2) and (4). We do this as follows:

• Input: attestation A, validator index v, data index i. Output: a Merkle branch of D[i] and C[i] with the roots matching, for the first branch, A.data_commitment, and for the second branch, the same R value as was submitted during any previous time the same validator answered a challenge for the same attestation.

We can also decrease the round count of the game, by asking for 2^k descendants some height k below the provided node (eg. 16 descendants 4 levels down). In this way, in the worst case (eg. a 2**24-sized data tree), the game would take only six rounds, instead of ~24.

How to implement the multi-round game

The main saving grace of all of the above is that the only game where honest challengers are not guaranteed to win (the branch challenge) only requires one round of challenging (all challenges can be done in parallel). Going beyond that, any honest challenger should be assured of victory, and hence willing to put down a deposit.

For each "exited" validator, we will maintain a counter, challenge_round, which starts at zero, and a bool was_challenged_this_round. When the validator reaches the end of their withdrawal queue, the following happens:

• If there were no challenges during this challenge_round of the validator (ie. was_challenged_this_round = False), or if challenge_round = 6, the validator withdraws successfully
• If there were challenges (any valid challenge sets was_challenged_this_round to True), the validator can skip back to the end of the exit queue as soon as they respond to all extant challenges, with challenge_round += 1 and was_challenged_this_round reset to False.
• Challenging during round 0 is restricted to proposers. Challenging during round i+1 is restricted to anyone who challenged during round i.

Now, for economics (this is the part I am still less confident about). If a validator successfully answers all challenges, then every validator that challenged can be penalized some amount. If a responder does not answer challenges and the time hits some timeout period, then all validators that challenge get a reward out of the responder's deposit (these rewards could be evenly split, or only given to the first challenger of each challenge round, or split among the challengers of each round in a decreasing schedule, eg. the kth challenger of each round gets a reward of (6/pi**2) / k**2 (the 6/pi**2 constant set so that rewards add up to a maximum of 1 per period).

[vbuterin]

Multi-round game, version 2

We store in the state two lists, pending_data_challenges and pending_challenge_games.

There is no longer a 18-hour minimum validator withdrawal time. Instead, the withdrawal queue always picks the 4 validators each epoch that exited the earliest for which all pending data challenges have been answered (data challenges can be made only for validators < 1 week after exiting). However, these validators are not immediately withdrawn; instead, they are assigned a "waiting for challenge games" status. If a validator has been waiting for challenge games for more than 18 hours and no challenge games have been started, the validator can exit.

Any validator can start a challenge game against any other validator by putting down 1 ETH as a deposit. The challenge game consists of the following process:

• Challenge game started
• Respondent must respond within 90 days by providing the full custody root; this must be consistent with all other custody roots provided
• Challenger has 14 days to ask for 16 degree-4 grandchildren of the root (otherwise the 1 ETH is forfeited)
• Respondent has 90 days to answer with the grandchildren
• Challenger has 14 days to ask for 16 degree-5 grandchildren of any one of the provided values
• Repeat until the respondent provides part of the bottom layer of the tree. Then the challenger can ask for a specific branch of the data within those provided values, and then the chain can verify whether or not mix(rk[p], D[i]) matches the provided C[i]

If the respondent can correctly respond to a game, the respondent gains 0.5 ETH and the challenger loses 1 ETH; if the respondent fails to respond, the respondent loses (1 + calculated anti-correlation penalty) ETH and the challenger recovers their deposit plus half of the penalty. If there are N > 1 games in progress, then all rewards and penalties are multipled by 1/N.

Hence, with the exception of the first round, challenging and responding is broken up into discrete games with a challenger and respondent.

[JustinDrake]

Here's a potential strategy to retain the elegance and simplicity of custody bits, and at the same time make them MPC-friendly.

1. For the purposes of custody bits only, use an MPC- and SNARK-friendly hash function such as MiMC.
   • We get SNARK-friendliness "for free" from the Ethereum 2.0 design goal of MPC-friendliness.
   • It's OK to use an experimental hash function such as MiMC. If it breaks the damage is contained to custody.
   • There are now two avenues to MPC-friendliness for staking pools. The first is to have an n-of-m MPC. The second is where a dedicated pool member computes the custody bit and provides a SNARK proof to the other pool members.
2. We introduce a non-interactive slashing condition whereby a whistleblower can present a SNARK proof that a specific custody bit is wrong.
   • By using Sonic we don't have to worry about the trusted setup.
3. (Optional) To handle data availability and retrievability, we introduce a one-round slashing condition whereby a challenger may request a specific data chunk from a validator. The challenged validator must respond with the data chunk plus a SNARK of a custody bit salted with a recent random number.
   • The SNARK of a recent custody bit handles cases where the data is unavailable.
   • The communicated data chunk handles data retrievability.
   • I marked this slashing condition as "optional" because I don't expect data to ever be unavailable if the first slashing condition is enforced. My recommendation would be to not implement this challenge game, at least not for phase 1.

Notice that SNARK proofs are not required in the optimistic case, and when they are required the relevant party has a lot of time (hours, days or however long we want) to build the SNARK.

[vbuterin]

MIMC is MPC-friendler than other hash functions, but not super MPC-friendly; it still requires something like 100 rounds of communication. The strategies that require fewer rounds get their mixing properties by mixing different fields, which is unfortunately not a very SNARK-friendly thing to do....

I'm also wary of this particular use case because the SNARK scheme failing would lead not to degradation of security of an isolated component of the system, but to innocent validators getting slashed, possibly undetectably. From my last day of thinking about it I don't think the game complexity difference between a SNARK and a Truebit-style game is that large (certainly much smaller than the internals and circuit construction of the SNARK). In either case, we need a multi-round exit game: the first round for challenging missing bits of D, and the second round for using the revealed information about D to launch a challenge.

In the second case, if we adopt the interactive game approach, once the challenge game starts it's a self-contained gadget, and from the point of view of the rest of the system we'll know at some point that it resolves. We can get rid of complexity involving list handling and 1/N rewards above by allowing only one challenge game per attestation per respondent, whoever starts one first. The possibility that a bad validator will challenge themselves and claim their own money can be handled as above by making the reward only half the penalty.