2
$\begingroup$

Consider a "fantasy sports" setting where $m$ contestants each pick $k$ players from a set of $n$ players before a game. The state can be represented by a Boolean matrix $\mathbf{A}$ of size $m \times n$ where each row has exactly $k$ non-zero entries with the $i$-th row being the subset of $n$ players picked by the $i$-th contestant.

After the match is played, each of the $n$ players get a score in $\mathbb{R}$ representing their performance. Let $\mathbf{v} \in \mathbb{R}^n$ be this score vector. The winner of the fantasy sports is the contestant with the highest subset-score where the subset-score is the sum of scores of the players picked in the subset. That is, the winner is given by $\underset{i\in [m]}{\operatorname{argmax}} \mathbf{A} \cdot \mathbf{v}$.

Suppose we want to determine the winner and convince every contestant that the winner is as claimed without revealing contestants inputs, how can we do that?

I am thinking this in the context of Ethereum blockchain, assume there is one trusted (centralized off-chain) organizer Bob, and looking for practical implementable solutions.

My partial attempt is as follows. Assume contestants are $a_1, \ldots, a_m$.

  1. Each contestant $a_i$ sends their input $\mathbf{A}_i$ to Bob.
  2. Bob generates a random nonce $z_i$, computes a hash $h_i = h(\mathbf{A}_i \circ z_i)$, sends $z_i$ to $a_i$, and publishes $h_i$ on chain. Note one can think of the values $h_1, \ldots, h_m$ as encrypted version of matrix $\mathbf{A}$.
  3. Each contestant can verify that Bob committed their value correctly on chain.
  4. Once the match is played, everyone knows $\mathbf{v}$, it is essentially public.
  5. Bob computes the matrix vector product $\mathbf{r} = \mathbf{A} \cdot \mathbf{v}$ and publishes this product on chain.
  6. Bob publishes a "proof" so that each $a_i$ can verify that the published result $\mathbf{r}$ is indeed computed correctly as claimed by only examining everything that is published so far: $h_1, \ldots, h_m$, $\mathbf{v}$, and this "proof".

How do I accomplish Step (6) above?

$\endgroup$
2
  • $\begingroup$ If you wish to keep $A$ secret, then I fear that step #5 may leak information. In particular, for each row in $A$, you can just test all $n^k$ possibilities and see which one lines up with the corresponding entry in the result vector $r$. For cases where $k$ and/or $n$ are small, this may be a non-trivially exploitable flaw. $\endgroup$
    – mhum
    Oct 10, 2022 at 23:17
  • $\begingroup$ Agree step #5 does leak information about A but wondering if the problem can be solved ignoring this issue. Later maybe a better framing would be how to output a ranked list in a zero knowledge way.... $\endgroup$
    – Madhav Jha
    Oct 11, 2022 at 0:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.