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$.
- Each contestant $a_i$ sends their input $\mathbf{A}_i$ to Bob.
- 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}$.
- Each contestant can verify that Bob committed their value correctly on chain.
- Once the match is played, everyone knows $\mathbf{v}$, it is essentially public.
- Bob computes the matrix vector product $\mathbf{r} = \mathbf{A} \cdot \mathbf{v}$ and publishes this product on chain.
- 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?
