Join GitHub today
GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.Sign up
The basic proof of custody mechanism works as follows:
There are three types of byzantine behavior that we want to penalize:
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
The next step is for the challenger to ask for the two children of
Note that this whole process is only possible if all of
Now, we have four types of challenges:
Note that we can increase efficiency by merging (1), (2) and (4). We do this as follows:
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,
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
Multi-round game, version 2
We store in the state two lists,
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:
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.
Here's a potential strategy to retain the elegance and simplicity of custody bits, and at the same time make them MPC-friendly.
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.
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
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.