ZIP-2: Court Dispute Mechanism

# ZIP-2: Court Dispute Mechanism Author: Dr. Malte Kliemann ## Introduction Zeitgeist's dispute system allows users to dispute the report made by a market's oracle. The dispute system is modular and delegates the responsibility of resolving a dispute to the market's dispute mechanism (MDM). The system is modular in the sense that all MDMs implement the same specification. Currently, three dispute mechanisms are available (although two of them are disabled): - `authorized`, which allow an authority (on-chain address) specified by the market creator to force set the outcome in case of a dispute. - `simple-disputes`, which simply assumes that the last dispute is correct when the dispute period ends (disabled and deprecated). - `court`, a jury-based court system similar to [Kleros](https://kleros.io). Currently, only a proof-of-concept implementation is available, and it currently differs from Kleros in some key points. The court is planned to be the primary market dispute mechanism (MDM) of Zeitgeist. This proposal is a specification for the first production version of the court. We will frequently refer to the Kleros [Yellow Paper], which details the court's behavior. For a detailed introduction to Zeitgeist's dispute system, see ZIP-0. ### Summary The court consists of a pool of _jurors_, each of whom has a certain amount of ZTG _staked_. When a court case if opened, a fixed amount of jurors are selected randomly. The probability of a juror getting selected is proportional to their stake. A juror can be selected multiple times for the same case. Following the selection of the jury, the jurors vote in secret and only later reveal their vote. The outcome that receives the plurality of votes wins. Those who voted for the losing outcome are slashed. The purpose of this is to find what Game Theory calls a _Schelling point_, a canonical choice made in the _absence of communication_. By slashing losers, straying from the canonical choice is punished. The choices available to the jury are selected by letting _parties_ commit a fixed amount of funds to an outcome. All funded outcomes are considered by the jury. All losing parties' bond are slashed, and the losing parties pay an additional arbitration fee to the jury. The court will allow appeals to be made. Subsequent iterations will require linearly more jurors and exponentially more arbitration fees. ## Court Specification ### Joining and leaving the court A Zeitgeist account may become a member of the court by staking some amount $s$ of ZTG which is at least the _minimum stake amount_ $\mathrm{min_stake}$. The staked amount measures the commitment of the user and determines the following properties: - The court member's probability of selection for jury duty - The number of simultaneous disputes the member can be juror for The purpose of $\mathrm{min_stake}$ is to make the system resistant to Sybil attacks. A user can split their funds over multiple accounts and join the court with each of them, but they will gain no advantage from this. The account is allowed to change the amount of staked funds, as long as it doesn't decrease below $\mathrm{min_stake}$ multiplied by the number of disputes the member is currently a juror for, but to ensure that users don't try to hop on specific court cases, a _lock up period_ is put in place. ### Gate-keeping and dispute parties When dealing with scalar markets or categorical markets with a large number of outcomes, the small amount of votes the jury has would be streched too thin and the risk of having "clone" candidates (outcomes which are technically distinct, yet very similar) is quite large. To solve this problem, we eliminate the lion's share of outcomes using _gate-keeping_. Before a court case is even opened and a jury is put together, candidates must be selected. A user can select a candidate by _backing_ it with a certain amount of funds. The funds are reserved and will be slashed if the candidate loses the dispute. The user(s) backing a candidate form a _dispute party_. Crowdfunding the funds for backing a candidate should be possible to allow everyone to play their part in initiating a dispute. See [Yellow Paper] 4.8.2.1 for details. In addition to the backing, the dispute parties must post collateral for the arbitration fee. The winning dispute party gets their collateral back at the end of the dispute round, while the losing parties each pay their share of the arbitration fee. If only one candidate is backed, that candidate wins the dispute by default. There will be no jury. If multiple candidates are available, the jury will be selected randomly and each juror will vote on one of the candidates. Particularly in scalar markets, this should eliminate most outcomes and will create a certain clone-resistance (if Alice wants to back outcome $x$, but Bob has already backed outcome $y$ which is very close to $x$, then Alice might not back $x$). Unless it has already lost a round, the reported outcome will be one of the candidates, backed by the oracle's oracle bond. See [Yellow Paper] 4.8.1-4.8.2 for details and additional suggestions. ### Jury composition and selection The number of jurors per dispute is equal to $$ n = 2^d * \texttt{JurorsPerDispute} + 2^d - 1 $$ where $d$ is the number of previous disputes (this matters during appeals); in other words, the number of jurors in the next round is twice the amount of jurors than the previous round, plus one. We suggest `JurorsPerDispute = 3`. Note that the number of jurors is always odd, which increases the likelihood of obtaining a clear plurality decision. The jury is selected randomly as follows. Let $(J_1, \ldots, J_N)$ be the list of all court members and $s_i$ their free staked amount (the staked amount that is not already bound in other disputes) in Pennock. Associate with every juror $J_k$ the range $R_k = \left[\sum_{i=1}^{k-1} s_i, \sum_{i=1}^{k} s_i\right)$ (where $\sum_{i=1}^0 s_i = 0$). Let $t$ be the total amount of free staked funds and take $n$ random integers in $[0, t)$. If one of these numbers is contained in $R_k$, then $J_k$ is selected. If a juror is selected multiple times, they receive multiple voices in the decision. #### Example Suppose that the following accounts are members of court. | Token owner | Staked | Range | Weight | | ----------- | ------ | ----------- | ------ | | Alice | 100 | 0-99 | 1 | | Bob | 1000 | 99-1099 | 3 | | Charlie | 300 | 1100 - 1399 | 0 | | David | 200 | 1400 - 1599 | 1 | ![](https://i.imgur.com/unEHVKP.png) The random numbers are $42$, $300$, $456$, $1099$ and $1411$. Thus, Alice and David get one vote, and Bob gets three. Charlie is not selected as juror.  ### Committing and revealing votes Recall that jurors cast their vote in secret during the _voting phase_ and later reveal their vote during the _vote aggregation phase_. This ensures that jurors aren't influenced by what votes other jurors cast (without the secrecy, the jury would not approximate a Schelling point). This means that the vote must be sent to the chain in encrypted form and later be revealed. To implement this, it is necessary that jurors modify the data they send with a pinch of `salt`. This `salt` is usually just a cryptographic random number that the juror must remember and later use to reveal their vote. The salted data is called the _commitment_. If a juror fails to vote or fails to reveal their vote during the vote aggregation phase, they are removed from the case and slashed to the tune of `SlashPercentage * min_amount`. If a juror reveals their vote too soon, they are automatically slashed by `ExposeSlashPercentage * min_amount`. Revealing your vote too soon is a serious misbehavior, as it puts the jury's integrity at risk, so the `ExposeSlashPercentage` should be fairly high. #### Exposing collusion Malicious jurors will attempt to collude to sway the ruling away from the Schelling point for profit. But this can only work if the malicious jurors know each other's vote, which means they have to expose each other's salt to one another. The [Yellow Paper] suggests in the following mechanism to disincentivize this behavior. If a user can prove that they know another juror's salt, they can _expose_ that juror by calling an extrinsic. If they can supply the correct salt, the exposed juror is slashed for `ExposeSlashPercentage * min_stake` and removed from the jury. If the salt is not correct, the other user is slashed, instead (implying that the user needs `min_stake` ZTG in their account). This makes it a high-risk maneuver to ever give someone your salt. **Note.** Slashing all of the juror's funds would make the court vulnerable to Sybil attacks. ### Vote aggregation and token redistribution When the aggregation phase is over, the votes cast by the jurors are counted and the plurality outcome is declare the _winner_. Let $n$ be the number of jurors and $c$ the number of parties. If there is a plurality, then the tokens of the participants are redistributed as follows: - The jurors who sided with losing outcomes are slashed by $\texttt{SlashPercentage} \cdot \texttt{min_stake}$ ZTG. - Let $w$ be the number of jurors who sided with the winning outcome. Each of the jurors who sided with the winning outcome receives $$ \frac{n - w}{w} \cdot \texttt{SlashPercentage} \cdot \texttt{min_stake} \; \mathsf{ZTG}. $$ (The amount slashed from the losers is distributed amongst the winners.) - The arbitration fees bonded by the winning party are unreserved - The losing parties pay arbitration fees to each juror who sided with the winning outcome: $$ \frac{1}{c - 1} \cdot \texttt{ArbitrationFeePerJuror} \; \mathsf{ZTG}, $$ so in total they lose $\frac{w}{c - 1} \cdot \texttt{ArbitrationFeePerJuror}$ ZTG. The remaining funds per losing party, $$ \frac{n - w}{c - 1} \cdot\texttt{ArbitrationFeePerJuror} \; \mathsf{ZTG}, $$ are unreserved. If there is no plurality (say, two outcomes received two votes each), then the dispute is considered indeterminate, unless the candidate that won the last round is one of the candidates tied for the win, in which case we declare that candidate the winner. The [Yellow Paper] is unclear on what should be done in case of a tie. #### Advanced voting mechanisms The [Yellow Paper] points out some attack vectors against the Plurality voting system in 4.7.2.1: > When there are more than two options, under a Plurality voting system, the following may occur: > > - If there are many very similar honest options (or “clones”), they will divide the votes of jurors that are attempting to vote honestly, decreasing the probability that any one of them wins. Anticipating this effect, jurors might instead vote for a distinguished but dishonest choice. For example, imagine that in our contractor use-case above there were several different options that gave Bob another week, another eight days, or another nine days respectively. Then the collective odds of these options being chosen could fall below the odds of a single “give Bob more time” option, [...] > - To the degree that no single option is likely to receive more than 50% of the votes, this lowers the bar for the number of votes that attackers need to corrupt to pass a dishonest result, [...]. This is followed by a discussion of more advanced voting systems which solve these problems at the cost of higher time complexity. Schulze, for example, has a time complexity of $O(c^3)$ where $c$ is the number of candidates, so at least in the case of scalar markets, this creates a DDoS vulnerability (at great cost for the attacker). WoodSIRV might be a good middle ground, although the [Yellow Paper] exposes a bias in the incentive system (see footnote 21 on page 17). In all instances, it might be possible to spread the calculations over multiple blocks by doing work whenever a vote is revealed, or by using our garbage collection system. For now, it is probably the best approach to stick with the Plurality voting system (as did Kleros) and later implement other options. ### Appeals After the aggregation period, the court publishes the decision made by the jurors, and the _appeal phase_ begins, during which dispute parties can back candidates. As soon as a candidate is backed, the court goes into the next round. If no appeals are made, the tokens bonded by the dispute parties are redistributed as follows: The party that funded the winning outcome receives the bonds provided by the losing parties. **Note.** It might be a good idea to consider if the winner of the previous round should always be considered as candidate, without requiring any backing. ### Life cycle  ## Remarks ### Significant Differences to the Kleros Implementation - Our court system does not have a court tree (see [Yellow Paper] 4.3) which branches off into sub-courts.  ### Significant differences to the proof-of-concept implementation - The lack of a commit-reveal scheme means that the proof-of-concept implementation does to approximate a Schelling point, but rather incentivizes jurors to vote for what the previous jurors have already voted on. - The proof-of-concept implementation is vulnerable to Sybil attacks. - There are no fees in the proof-of-concept implementation. This means that the court is a zero-sum game, which disincentivizes unanimous decisions. - The proof-of-concept implementation uses pseudo-random numbers, which means that malicious users can game the system to their advantage. ### Future Work As the size of the court increases and statistics on how the court dispute mechanism is used (the average number of dispute parties per dispute, for example), we should consider making some changes: #### Court tree The court tree allows users to specify areas of expertise (_economics_, _sports_, etc.) to increase their likelihood of selection for disputes that concern topic they are knowledgeable about. Given that one of our concerns is that the court might be underpopulated, this doesn't seem like a useful feature. However, in the future, this might significantly increase the quality of the decisions made by juries. #### Advanced voting systems As described above, the Plurality voting system is somewhat vulnerable when more than two candidates are in play. Adding additional voting systems should be a mid- to long-term goal. ## Implementation ### Random Number Generation  ### Encryption & salt Submitting and revealing votes is done using the following interface: ```rust type HashSize = /* ... */; type Hash = [u8; HashSize]; pub trait CommitRevealScheme { type DisputeId: /* ... */; type Vote: AsRef<[u8]>; type Salt: AsRef<[u8]>; type Hasher: sp_core::Hasher; fn submit_commitment( origin: OriginFor<T>, dispute_id: DisputeId, commitment: Hash, ) -> DispatchResult; fn reveal_vote( origin: OriginFor<T>, dispute_id: DisputeId, salt: Salt, vote: Vote, ) -> DispatchResult; } ``` Let `hash` be some cryptographic hash function available to `substrate`. The commitment the juror makes to the blockchain is `hash(vote ++ address ++ salt)`, where `++` denotes concatenation. The juror's `address` is included as checksum. The `reveal_vote` extrinsic verifies that `hash(vote ++ address ++ salt)` matches the commitment made previously. **Note.** Exposing jurors should only be allowed during the voting phase. Otherwise, we run the risk of malicious users frontrunning people's `reveal_vote` calls with `expose` calls, stealing their funds and voiding their vote. ### Notes on jury selection, vote aggregation and voting systems - It's important to observe the distinction between _free_ staked funds and staked funds that are currently locked in court cases to ensure that there are always enough funds to be slashed when a juror misbehaves. - One pain point of the implementation is that the jury selection algorithm requires us to find which range $R_k$ each random number belongs to. We need a $O(\log n)$ solution for this. - Jurors should be allowed to change their vote during the voting period. This won't create any vulnerabilities, since people can only see the commitment. - Although the aggregation phase can be ended as soon as all jurors have revealed their vote, it's probably a good idea to not do that in order to keep the appeal phase as predictable as possible. - The voting system should be a configuration variable of `pallet-court` or even a parameter of dispute creation. This will allow us to easily maintain new voting systems alongside old ones, and test new voting systems on Battery Station before deploying them on the mainnet. ### Gateway and `pallet-crowdfunding` The crowdfunding function should be abstracted into its own pallet, rewarding us with better encapsulation and less code duplication. We may want to update `global-disputes` to use the crowdfunding pallet for selecting outcomes to vote on. ### User interface The primary technical challenge for jurors is cryptographically generating the salt, calculating their commitment (which must be done _before_ even submitting the `vote` extrinsic), and storing their salts properly to prevent loss and theft. Depending on the value of `min_stake`, the salts might be medium to high value items. Ideally, the juror will only specify `vote` when submitting their vote through an application. Their address is already known, and the salt should be cryptographically generated by the app. Furthermore, the app should encrypt the salt using the account's private key and/or display a seed phrase representing the salt and urge the user to backup this phrase. Another very important feature is displaying to a user which court cases they are involved in. The juror should always be aware which court case they are involved in. A nice-to-have would be a service on email/Twitter/Discord/etc. that messages members of court when they are involved in a case based on their on-chain identity. These pain points of implementing this need to be carefully discussed with the frontend team as soon as possible: - Cryptographic hashing in JavaScript - Representing the hash using a seed phrase - Encrypting the salt using the account's private key - Notification bot on social media/email ### On-chain deployment A concern when adding court to the available dispute mechanisms is that the set of jurors will be too small at the outset, resulting in a lack of diversity in the selection of jurors. There are two mitigation tactics: - The Zeitgeist Foundation should fund accounts for ten Zeitgeist Team members to be become jurors. The Foundation should also reserve at least 1,000,000 ZTG to boost the funds available on these accounts to prevent a 51% attack by whales. - Marketing and Community Management should advertise the court to community members and maybe even incentivize them joining court. The point here is not necessarily to get the most competent individuals, but to diversify the court collective over as many individuals as possible. As markets with `dispute_mechanism = MarketDisputeMechanism::Court` can only be created after the update, depending on the configuration of the minimum market duration, the Team will have a certain amount of time to set this plan into motion. The second approach requires rigorous preparation of learning material for how court works: - A blog post introducing the basic mechanics should be published - [docs.zeitgeist.pm] should be updated - Video tutorials should be created - In-app documentation should be available #### Suggested configuration values | Variable | Value | | ------------------------ | ---------- | | MinStake | 10,000 ZTG | | ArbitrationFeePerJuror | 1,000 ZTG | | CandidateBacking | 10,000 ZTG | | ExposeSlashPercentage | 100% | | SlashPercentage | 10% | | JurorsPerDispute | 3 | | VotingPhaseDuration | 4d | | AggregationPhaseDuration | 4d | | NominationPhaseDuration | 4d |