<p>Consider a &quot;fantasy sports&quot; setting where <span class="math-container">$m$</span> contestants each pick <span class="math-container">$k$</span> players from a set of <span class="math-container">$n$</span> players before a game. The state can be represented by a Boolean matrix <span class="math-container">$\mathbf{A}$</span> of size <span class="math-container">$m \times n$</span> where each row has exactly <span class="math-container">$k$</span> non-zero entries with the <span class="math-container">$i$</span>-th row being the subset of <span class="math-container">$n$</span> players picked by the <span class="math-container">$i$</span>-th contestant.</p>
<p>After the match is played, each of the <span class="math-container">$n$</span> players get a score in <span class="math-container">$\mathbb{R}$</span> representing their performance. Let <span class="math-container">$\mathbf{v} \in \mathbb{R}^n$</span> 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 <span class="math-container">$\underset{i\in [m]}{\operatorname{argmax}} \mathbf{A} \cdot \mathbf{v}$</span>.</p>
<p>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?</p>
<p>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.</p>
<p>My partial attempt is as follows. Assume contestants are <span class="math-container">$a_1, \ldots, a_m$</span>.</p>
<ol>
<li>Each contestant <span class="math-container">$a_i$</span> sends their input <span class="math-container">$\mathbf{A}_i$</span> to Bob.</li>
<li>Bob generates a random nonce <span class="math-container">$z_i$</span>, computes a hash <span class="math-container">$h_i = h(\mathbf{A}_i \circ z_i)$</span>, sends <span class="math-container">$z_i$</span> to <span class="math-container">$a_i$</span>, and publishes <span class="math-container">$h_i$</span> on chain. Note one can think of the values <span class="math-container">$h_1, \ldots, h_m$</span> as encrypted version of matrix <span class="math-container">$\mathbf{A}$</span>.</li>
<li>Each contestant can verify that Bob committed their value correctly on chain.</li>
<li>Once the match is played, everyone knows <span class="math-container">$\mathbf{v}$</span>, it is essentially public.</li>
<li>Bob computes the matrix vector product <span class="math-container">$\mathbf{r} = \mathbf{A} \cdot \mathbf{v}$</span> and publishes this product on chain.</li>
<li>Bob publishes a &quot;proof&quot; so that each <span class="math-container">$a_i$</span> can verify that the published result <span class="math-container">$\mathbf{r}$</span> is indeed computed correctly as claimed by only examining everything that is published so far: <span class="math-container">$h_1, \ldots, h_m$</span>, <span class="math-container">$\mathbf{v}$</span>, and this &quot;proof&quot;.</li>
</ol>
<p>How do I accomplish Step (6) above?</p>

CC BY-SA 4.0
2022-10-10T23:17:31.703Z
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.
mhum
CC BY-SA 4.0
2022-10-11T00:20:20.630Z
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....
Madhav Jha
<interactive-proofs><zero-knowledge><homomorphic-encryption>
Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed
Madhav Jha
# Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed

(Asked by: username_0 on 2022-10-09)

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?

**Tags:** interactive-proofs, zero-knowledge, homomorphic-encryption
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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....  

---

## 0 answers

