Chunky: Weighted PVSS for field elements

tl;dr: A work-in-progress weighted PVSS for field elements using chunked ElGamal encryption and DeKART range proofs.

Preliminaries

We assume familiarity with:

• PVSS, as an abstract cryptographic primitive.
  • In particular, the notion of a PVSS transcript will be used a lot.
• ElGamal encryption
• Batched range proofs (e.g., DeKART)
• ZKSoKs (i.e., $\Sigma$-protocols that implicitly sign over a message by feeding it into the Fiat-Shamir transform).
• The SCRAPE low-degree test

All of these will be described in more detail in the subsections below.

Notation

Pairing-friendly groups notation

• Let $\GGen(1^\lambda) \rightarrow \mathcal{G}$ denote a probabilistic polynomial-time algorithm that outputs bilinear groups $\mathcal{G} \bydef (\Gr_1, \Gr_2, \Gr_T)$ of prime order $p\approx 2^{2\lambda}$, denoted additively, such that:
  • $\one{1}$ generates $\Gr_1$
  • $\two{1}$ generates $\Gr_2$
  • $\three{1}$ generates $\Gr_T$
• We use $\one{a}\bydef a\cdot \one{1}$ and $\two{b}\bydef b\cdot \two{1}$ and $\three{c}\bydef c\cdot \three{1}$ to denote multiplying a scalar by the group generator

• Let $\F$ denote the scalar field of order $p$ associated with the bilinear groups

• We often use capital letters like $G$ or $H$ to denote group elements in $\Gr_1$
• We often use $\widetilde{G}$ or $\widetilde{H}$ letters to denote group elements in $\Gr_2$

Time-complexity notation

• For time complexities, we use:
  • $\Fadd{n}$ for $n$ field additions in $\F$
  • $\Fmul{n}$ for $n$ field multiplications in $\F$

Other notation

• $[n]\bydef \{1,2,\ldots,n\}$
• $[n) \bydef \{0,1,2,\ldots,n-1\}$

ElGamal encryption

Assuming familiarity with ElGamal encryption:

$E.\mathsf{KeyGen}_H()\rightarrow (\mathsf{dk},\mathsf{ek})$

Generate the key-pair: \begin{align} \dk &\randget\F\\
\ek &\gets \dk \cdot H \end{align}

$E.\mathsf{Enc}_{G,H}\left(\mathsf{ek}, v; r\right) \rightarrow \left(C, R\right)$

Compute: \begin{align} C &\gets v \cdot G + r \cdot \ek\\
R &\gets r \cdot H \end{align}

$E.\mathsf{Dec}_{G}\left(\mathsf{dk}, (C, R)\right) \rightarrow v$

\begin{align} v &\gets \log_G\left(C - \dk\cdot R\right)\\
&= \log_G\left((v \cdot G + r \cdot \ek) - \dk\cdot (r \cdot H)\right)\\
&= \log_G\left(v \cdot G + r \cdot \ek - (r \cdot \dk) \cdot H\right)\\
&= \log_G\left(v \cdot G + r \cdot \ek - r \cdot \ek\right)\\
&= \log_G\left(v \cdot G\right) = v\\
\end{align}

Decryption will only work for sufficiently “small” values $v$ such that computing discrete logarithms on $v \cdot G$ is feasible (e.g., anywhere from 32 bits to 64 bits).

Univariate DeKART batched ZK range proofs

Assuming familiarity with batched ZK range proofs¹. In particular, we will use univariate DeKART as our range proof scheme, formalized below.

$\dekart_b.\setup(N; \mathcal{G})\rightarrow (\mathsf{prk},\mathsf{ck},\mathsf{vk})$

Sets up the ZK range proof to prove batches of size $\le N$, returning a proving key, a commitment key and a verification key. (See implementation here.)

$\dekart_b.\commit(\ck,z_1,\ldots,z_N; \rho)\rightarrow C$

Returns a commitment $C$ to a vector of $N$ values using randomness $\rho$. (See implementation here.)

$\dekart_b.\prove(\prk, C, \ell; z_1,\ldots,z_N, \rho)\rightarrow \pi$

Returns a ZK proof $\pi$ that the $N$ values committed in $C$ are all in $[0, b^\ell)$. (See implementation here.)

$\dekart_b.\verify(\vk, C, \ell; \pi)\rightarrow \{0,1\}$

Verifies that the $N$ values committed in $C$ are all in $[0, b^\ell)$. (See implementation here.)

Zero-knowledge Signatures of Knowledge (ZKSoKs)

Assuming familiarity with ZKSoKs², which typically consist of two algorithms:

$\sok.\prove(\mathcal{R}, m, \stmt; \witn) \rightarrow \pi$

Returns a ZK proof of knowledge of $\witn$ s.t. $\mathcal{R}(\stmt;\witn) = 1$ and signs the message $m$ in the process.

$\sok.\verify(\mathcal{R}, m, \stmt; \pi) \rightarrow \{0,1\}$

Verifies a ZK proof of knowledge of some $\witn$ s.t. $\mathcal{R}(\stmt;\witn) = 1$ and that the message $m$ was signed.

The ElGamal-to-KZG NP relation

One of the key ingredients in our PVSS will be a ZK proof of knowledge of share chunks such that they are both ElGamal-encrypted and KZG-committed.

This is captured via the NP relation below: \begin{align} \term{\Retk}\left(\begin{array}{l} \stmt = \left(G, H, \ck, \{\ek_i\}_i,\{C_{i,j,k}\}_{i,j,k}, \{R_{j,k}\}_{j,k}, C\right),\\
\witn = \left(\{s_{i,j,k}\}_{i,j,k}, \{r_{j,k}\}_{j,k}, \rho\right) \end{array}\right) = 1\Leftrightarrow\\
\Leftrightarrow\left\{\begin{array}{rl} (C_{i,j,k}, R_{j,k}) &= E.\enc_{G,H}(\ek_i, s_{i,j,k}; r_{j,k})\\
C& = \dekart_2.\commit(\ck, \{s_{i,j,k}\}_{i,j,k}; \rho) \end{array}\right. \end{align} where the $s_{i,j,k}$’s will be “flattened” as a vector (in a specific order) before being input to $\dekart_2.\commit(\cdot)$.

We will explain how this flattening works later in the $\pvssDeal$ algorithm.

The SCRAPE low-degree test

Explain!

Building a DKG from a non-malleable PVSS

Our goal is to get a weighted DKG³ for field elements amongst the validators of a proof-of-stake blockchain, such that the DKG (final, shared) secret $\term{z}$ is only reconstructable by a fraction $> \term{f}$ of the stake (e.g., $f = 0.5$ or 50%).

To do this, each validator $i$ will “contribute” to $z$ by picking their own secret $\term{z_i} \in \F$ and dealing it to the other validators via $\term{\pvssDeal}$ in a non-malleable fashion. The DKG secret will be set to $z \bydef \sum_{i\in Q} z_i$, where $\term{Q}$ is the set of validators who correctly dealt their $z_i$ via $\pvssDeal$.

Crucially, $Q$ must be large “enough”: i.e., it must have “enough” validators to guarantee that no malicious subset of them can learn (or can bias the choice of) $z$. For example, we could assume only 33% of the stake is malicious and require that $Q$ have more stake than that. In an abundance of caution, in Aptos, we require that $Q$ contains $>$ 66% of the stake.

The DKG is parameterized by $\sizeof{Q}$ and by $f$. Since typically in a DKG the same set of validators will deal a secret amongst themselves, $\sizeof{Q}$ and $f$ are typically set to the same value. Otherwise, if $f > \sizeof{Q}$, then the validators in $Q$ which are fewer than required by $f$ could reconstruct the secret, which defeats the point. Or, if $\sizeof{Q} > f$, then you are requiring more validators to contribute than needed for secrecy, since $f < \sizeof{Q}$ can reconstruct.

First, to ensure that $\sizeof{Q}$ is large “enough”, we require that, in the DKG protocol, each validator digitally-sign their dealt PVSS transcript in a domain-separated fashion (part of the domain separator will be the current consensus epoch number). Without such authentication, $Q$ could be filled with transcripts from one malicious validator impersonating the other ones. Therefore, that malicious validator would have full knowledge of the final DKG secret $z$. No es bueno.

Implication: The DKG protocol needs to be carefully crafted to sign the PVSS transcripts. If done right, the validators’ public keys used for consensus signature can be safely reused as signing public keys for the transcript.

Second, we require that PVSS transcripts obtained from $\pvssDeal$ be non-malleable. To see why this is necessary consider the following scenario:

• two validators $i$ and $j$ have enough stake to make $Q = \{i,j\}$ large enough
• $j$ by itself does not have enough stake
• $i$ deals $z_i \in \F$ and signs the transcript
• $j$ removes $i$’s signature and mauls $i$’s transcript to deal $-z_i + r$ for some $r\randget\F$ it knows
• $j$ signs this mauled transcript
  • $\Rightarrow j$ would have full knowledge of the final DKG secret $z = z_i + (- z_i + r) = r$.

Implication: The PVSS transcript will include a zero-knowledge signature of knowledge (ZKSoK) of the dealt secret $z_i$ over the signing public key used to sign the transcript. This way, the dealt secret cannot be mauled without rendering the transcript invalid. Furthermore, nor can validator $j$ bias the final DKG secret $z$ by appropriating validator $i$’s transcript as their own (i.e., by stripping validator $i$’s signature from the transcript and adding their own).

Non-malleable weighted PVSS algorithms

Notation:

• Let $\term{n}$ denote the number of players
• Let $\term{\maxTotalWeight}$ denote the maximum total weight $\Leftrightarrow$ maximum # of shares that we will ever want to deal in the PVSS
• Let $\term{\ell}$ denote the chunk bit-size (e.g., $\ell=32$ for 32-bit chunks)
• Let $\term{m} = \ceil{\log_2{\sizeof{\F}} / \ell}$ denote the number of chunks per share
• Let $\term{B}\bydef 2^\ell$ denote the maximum value of a chunk (e.g., $B=2^{32}$ for 32-bit chunks)

The algorithms below describe Chunky, a weighted PVSS where only subsets of players with combined weight $> \threshWeight$ can reconstruct the shared secret.

$\mathsf{PVSS}.\mathsf{Setup}(\ell, W_\mathsf{max}; \mathcal{G}, \widetilde{G}) \rightarrow \mathsf{pp}$

Recall that $\emph{\maxTotalWeight}$ is the max. total weight, $\emph{\ell}$ is the # of bits per chunk and $\emph{m}$ is the number of chunks a share is split into.

$\term{\widetilde{G}}$ will be the base used to commit to the shares in $\pvssDeal$.

Step 1: Set up the ElGamal encryption: \begin{align} \term{G},\term{H} &\randget \Gr_1 \end{align}

Step 2: Set up the ZK range proof to batch prove that $\le \maxTotalWeight\cdot m$ share chunks are all $\ell$-bit wide:

\begin{align} (\prk,\ck,\vk) \gets \dekart_2.\setup(\maxTotalWeight\cdot m; \mathcal{G}) \end{align}

Note that DeKART assumes that the field $\F$ admits a $2^\kappa$-th primitive root of unity where $2^\kappa$ is the smallest power of two $\ge \maxTotalWeight\cdot m + 1$. (The ZK range proof needs FFTs of size $\maxTotalWeight\cdot m$.)

Return the public parameters: \begin{align} \pp \gets (\ell, \maxTotalWeight, G, \widetilde{G}, H, \prk,\ck,\vk) \end{align}

$\mathsf{PVSS}.\mathsf{Deal}_\mathsf{pp}\left(t, \{w_i\}_{i\in[n]}, \{\mathsf{ek}_i\}_{i\in [n]}, a_0, \mathsf{ssid}\right) \rightarrow \mathsf{trs}$

$a_0$ is the dealt secret. $w_i$’s are the weights of each player, including the dealer’s (i.e., $w_\pid$). $\ssid$ is a session identifier, which will be set to the consensus epoch number in which the DKG is taking place and calls this PVSS deal algorithm.

Parse public parameters: \begin{align} (\ell, \maxTotalWeight, G, \widetilde{G}, H, \prk,\ck,\vk)\parse\pp \end{align}

Compute the total weight and assert that the public parameters can accomodate it: \begin{align} \label{eq:W} \term{W} &\gets \sum_{i\in[n]} w_i\\
\textbf{assert}\ W &\le \maxTotalWeight \end{align}

Find a $2^\kappa$-th root of unity $\term{\omega} \in \F$ such that we can efficiently compute FFTs of size $W$ (i.e., smallest $2^\kappa \ge W$).

Step 1: Pick the degree-$\threshWeight$ random secret sharing polynomial and compute the $j$th share of player $i$: \begin{align} \term{a_1,\ldots,a_t} &\randget \F\\
\term{f(X)} &\bydef \emph{a_0} + a_1 X + a_2 X^2 + \ldots + a_t X^\threshWeight\\
\label{eq:eval} \term{s_{i, j}} &\gets f\left(\term{\chi_{i,j}}\right),\forall i\in[n],\forall j\in[w_i] \end{align}

Note: Assuming that the set of evaluation points $\emph{\{\chi_{i,j}\}}$ are wisely set to be the the first $W$ roots of unity in $\{\omega^{i’}\}_{i’\in [0,W)}$, then the $s_{i,j}$’s would be quickly-computable in $\Fmul{O(W\log{W})}$ via an FFT.

Step 2: Commit to the shares, $\forall i\in[n],\forall j\in[w_i]$: \begin{align} \term{\widetilde{V}_{i,j}} &\gets s_{i,j} \cdot \widetilde{G} \in \Gr_2\\
\term{\widetilde{V}_0} &\gets a_0 \cdot \widetilde{G} \end{align}

Step 3: Split each share $s_{i,j}$ into $\emph{m}\bydef \ceil{\log_2{\sizeof{\F}}} / \ell$ chunks $\term{s_{i,j,k}}$, of $\ell$-bits each, such that: \begin{align} s_{i,j} &= \sum_{k\in[m]} (2^\ell)^{k-1} \cdot \emph{s_{i,j,k}}\\
&\bydef \sum_{k\in[m]} \emph{B}^{k-1} \cdot s_{i,j,k}\\
\end{align}

Note: Each $s_{i,j,k} \in [0, B)$, where $B = 2^\ell$.

Step 4: $\forall i \in[n], j\in[w_i], k\in[m]$, encrypt the $k$th chunk of the $j$th share of player $i$: \begin{align} \term{r_{j,k}} &\randget \F\ \text{s.t.}\ \sum_{k\in[m]} B^{k-1}\cdot r_{j,k} = 0\\
\term{(C_{i,j,k}, R_{j,k})} &\gets E.\enc_{G,H}(\ek_i, s_{i,j,k}; r_{j,k})\\
&\bydef \left(\begin{array}{l} s_{i,j,k} \cdot G + r_{j,k}\cdot \ek_i\\
r_{j,k}\cdot H\end{array}\right) \end{align}

Observation 1: The randomness has been correlated such that: \begin{align} \label{eq:correlated} \sum_{k\in[m]} B^{k-1} \cdot C_{i,j,k} &= \sum_{k\in[m]} B^{k-1} \cdot (s_{i,j,k} \cdot G + r_{j,k}\cdot \ek_i)\\
&= \underbrace{\sum_{k\in[m]} (B^{k-1} \cdot s_{i,j,k})}_{s_{i,j}} \cdot G + \underbrace{\sum_{k\in [m]} (B^{k-1} \cdot r_{j,k})}_{0}\cdot \ek_i\\
&= s_{i,j} \cdot G + 0 \cdot \ek_i = s_{i,j} \cdot G \end{align}

Observation 2: Different players $i$ will safely re-use the same $r_{j,k}$ randomness.

Observation 3: $\sizeof{\{R_{j,k}\}_{j,k}} = \max_{i\in[n]}{(w_i)} \cdot m$

The cumulative weight up to (but excluding) $i$ is $\term{W_i}$ such that $\emph{W_1} = 0$ and $\emph{W_i} = \sum_{i’\in [1, i)} w_i$. (Note that $W \bydef W_{n+1}$.) This notion helps us “flatten” all the share chunks $s_{i,j,k}$ into an array $\{z_{i’}\}_{i’\in [W \cdot m]}$, where $z_{i’} \bydef s_{i,j,k}$ with $i’\gets \left(\emph{W_i} + (j-1)\right)\cdot m + k \bydef \term{\idx(i,j,k)}$ (see appendix for how the indexing was derived).

Step 5: Prove that the share chunks are correctly encrypted and are all $\ell$-bit long.

First, “flatten” all the shares into a vector. $\forall i\in[n], j\in[w_i],\forall k\in[m]$: \begin{align} \term{z_{i’}} \gets s_{i,j, k},\ \text{where}\ i’ &\bydef \emph{\idx}(i,j,k)\in[W\cdot m] \end{align}

Second, KZG commit to the share chunks and prove they are all in range: \begin{align} \rho &\randget \F\\
\term{C} &\gets \dekart_2.\commit(\ck, z_1, \ldots, z_{W \cdot m}; \rho)\\
\term{\piRange} &\gets \dekart_2.\prove(\prk, C, \ell, z_1, \ldots, z_{W\cdot m}; \rho) \end{align}

Step 6: Compute a signature of knowledge of the dealt secret key $a_0$ over the session ID: \begin{align} \term{\ctx} &\gets (t, \{w_i\}_i, \ssid)\\
\term{\piSok} &\gets \sok.\prove\left(\begin{array}{l} \Retk, \emph{\ctx},\\
\underbrace{G, H, \ck, \{\ek_i\}_i,\{C_{i,j,k}\}_{i,j,k}, \{R_{j,k}\}_{j,k}, C}_{\stmt},\\
\underbrace{s_{i,j,k}\}_{i,j,k}, \{r_{j,k}\}_{j,k}, \rho}_{\witn} \end{array}\right) \end{align}

Return the transcript: \begin{align} \term{\pi} &\gets \left(C, \piRange, \piSok\right)\\
\trs &\gets \left(\widetilde{V}_0, \{\widetilde{V}_{i,j}\}_{i,j\in[w_i]}, \{C_{i,j,k}\}_{i,j\in[w_i],k}, \{R_{j,k}\}_{j\in[\max_i{w_i}],k}, \emph{\pi}\right) \end{align}

$\mathsf{PVSS}.\mathsf{Verify}_\mathsf{pp}\left(\mathsf{trs}, t, \{w_i\}_{i\in[n]}, \{\mathsf{ek}_i\}_{i\in[n]}, \mathsf{ssid}\right) \rightarrow \{0,1\}$

Parse public parameters: \begin{align} (\ell, \cdot, G, \widetilde{G}, H, \cdot,\cdot,\vk)\parse\pp \end{align}

Parse the transcript: \begin{align} \left(\widetilde{V}_0, \{\widetilde{V}_{i,j}\}_{i,j\in[w_i]}, \{C_{i,j,k}\}_{i,j\in[w_i],k}, \{R_{j,k}\}_{j\in[\max_i{w_i}],k}, \left(C, \piRange, \piSok\right)\right)\parse\trs \end{align}

Let the total weight $W$ be defined as before in Eq. \ref{eq:W}.

Step 1: Verify that the committed shares encode a degree-$t$ polynomial via the SCRAPE LDT⁴: \begin{align} \term{\alpha} &\randget \F\\
\textbf{assert}\ &\scrape.\lowdegreetest(\{(0, V_0)\} \cup \{(\chi_{i,j}, V_{i,j})\}_{i,j}, t, W; \emph{\alpha}) \end{align}

Note: Recall that the $\emph{\chi_{i,j}}$’s are the roots of unity used to evaluate the secret-sharing polynomial $f(X)$ during dealing (see Eq. \ref{eq:eval}).

May need to feed in the size of the evaluation domain to SCRAPE for the super-efficient algorithm.

Step 2: Check that ciphertexts encrypt the committed shares: \begin{align} \term{\beta_{i,j}} &\randget\{0,1\}^\lambda\\
\label{eq:multi-pairing-check} \textbf{assert}\ &\pair{\sum_{i\in[n],j\in[w_i],k\in[m]} (B^{k-1}\cdot\emph{\beta_{i,j}})\cdot C_{i,j,k}}{\widetilde{G}} \equals \pair{G}{\sum_{i\in[n],j\in[w_i]} \emph{\beta_{i,j}}\cdot \widetilde{V}_{i,j}} \end{align}

Step 3: Verify the range proof: \begin{align} \textbf{assert}\ \dekart_2.\verify(\vk, C, \ell; \piRange) \equals 1 \end{align}

Step 4: Verify the SoK: \begin{align} \term{\ctx} &\gets (t, \{w_i\}_i, \ssid)\\
\textbf{assert}\ &\sok.\verify\left(\begin{array}{l} \Retk, \emph{\ctx},\\
\underbrace{G, H, \ck, \{\ek_i\}_i,\{C_{i,j,k}\}_{i,j,k}, \{R_{j,k}\}_{j,k}, C}_{\stmt};\\
\piSok \end{array}\right) \equals 1 \end{align}

$\mathsf{PVSS}.\mathsf{Decrypt}_\mathsf{pp}\left(\mathsf{trs}, \mathsf{dk}, i, w_i\right) \rightarrow \{s_{i,j}\}_j \in \F$

$i\in[n]$ is the ID of the player who is decrypting their share(s) from the transcript. Recall that $\emph{m}\bydef \ceil{\log_2{\sizeof{\F}} / \ell}$ is the number of chunks per share.

Parse public parameters: \begin{align} (\ell, \cdot, G, \cdot, \cdot, \cdot,\cdot,\cdot)\parse\pp \end{align}

Parse the transcript: \begin{align} \left(\cdot, \cdot, \{C_{i,j,k}\}_{i,j\in[w_i],k}, \{R_{j,k}\}_{j\in[\max_i{w_i}],k},\cdot\right)\parse\trs \end{align}

Step 1: Decrypt all of player $i$’s share chunks $\{s_{i,j,k}\}_{i,j\in[w_i],k\in[m]}$: \begin{align} s_{i,j,k}\gets E.\dec_{G}\left(\dk_i, (C_{i,j,k}, R_{j,k})\right) \end{align}

Step 2: Assemble the chunks back into shares: \begin{align} s_{i,j}\gets \sum_{k\in[m]} (2^\ell)^{k-1} \cdot s_{i,j,k} \end{align}

Acknowledgements

The weighted PVSS in this blog post has been co-designed with Rex Fernando and Wicher Malten at Aptos Labs.

Appendix: The $i’\gets \mathsf{idx}(i,j,k)$ indexing

It may be easiest to understand the $\idx(i,j,k) = (W_i + (j-1))\cdot m + k$ formula by considering an example.

Say the number of chunks per share is $m = 4$ and that we have $n=4$ players with weights $[ w_1, w_2, w_3, w_4 ] = [2, 1, 3, 2]$

Then, the cumulative weights will be $[ W_1, W_2, W_3, W_4 ] = [ 0, 2, 3, 6]$

“Flattening out” the shares, we’d get:

Player 1:

    s_{1,1,1}, s_{1,1,2}, s_{1,1,3},
    1          2          3         

    s_{1,2,1}, s_{1,2,2}, s_{1,2,3},
    4          5          6         

Player 2:
    s_{2,1,1}, s_{2,1,2}, s_{2,1,3},
    7          8          9         

Player 3:
    s_{3,1,1}, s_{3,1,2}, s_{3,1,3},
    10         11         12        

    s_{3,2,1}, s_{3,2,2}, s_{3,2,3},
    13         14         15        

    s_{3,3,1}, s_{3,3,2}, s_{3,3,3},
    16         17         18        

Player 4:
    s_{4,1,1}, s_{4,1,2}, s_{4,1,3},
    19         20         21        

    s_{4,2,1}, s_{4,2,2}, s_{4,2,3},
    22         23         24

Observations:

1. Player $i$’s share chunks start at index $W_i\cdot m + 1$.
2. To get to the chunks of the $j$th share (of player $i$) add $(j-1)\cdot m$ to that.
3. To get to the $k$th chunk (of the $j$th share of player i) add $k-1$ to that.

So: \begin{align} \idx(i,j,k) &= ((W_i \cdot m + 1) + ((j-1) \cdot m) + (k-1)\\
&= ((W_i \cdot m) + ((j-1) \cdot m) + k\\
&= (W_i + (j-1)) \cdot m + k\\
\end{align}

For example, when $i = 3, j = 3, k = 2$, we get: \begin{align} (W_i + (j-1)) \cdot m + k &= (W_3 + (3-1)) \cdot 3 + 2\\
&= (3 + 2) \cdot 3 + 2\\
&= 5 \cdot 3 + 2 = 17 \end{align} as expected for $s_{3,3,2}$.

References

For cited works, see below 👇👇