Authors: Dan Boneh, @b-wagn, @arantxazapico
We thank Gottfried Herold for dicussion and feedback.
Intro: RLNC for Ethereum
As suggested in this post, Ethereum can benefit from Random Linear Network Coding (RLNC) to speed up the network. This approach avoids sending full blocks during propagation, thereby significantly reducing the amount of data in transit. This will work as follows:
The Block Proposer P_{prop} can parse the block as a matrix \mathbf{M}=(\vec{m}_1,\ldots,\vec{m}_N)\in(\mathbb{F}^M)^N. Instead of distributing the entire block, it can send N linearly independent vectors in the subspace A generated by the columns of the matrix. That is, vectors of the form \vec{v}= \mathbf{M} \cdot \vec{a} \in \mathbb{F}^M for some \vec{a}\in \mathbb{F}^N. Along with each vector \vec{v} \in \mathbb{F}^M the proposer P_{prop} sends:
- the coefficients vector \vec{a} \in \mathbb{F}^N,
- succinct homomorphic commitments[1] \vec{\mathsf{C}} = (\mathsf{C}_1,\ldots,\mathsf{C}_N) to the vectors \vec{m}_1,\ldots,\vec{m}_N \in \mathbb{F}^M respectively, and
- a BLS signature \sigma on the tuple (\vec{v}, \vec{a}, \vec{\mathsf{C}}) using P_{prop}'s secret key.
This way, P_{prop} sends (\vec{v}, \vec{a}, \vec{\mathsf{C}}, \sigma) to each peer in its mesh, which is only (M + N) field elements plus N commitments and a signature, instead of the entire block \mathbf{M} and a signature on its header.
On input (\mathsf{pk},\vec{v}, \vec{a}, \vec{\mathsf{C}},\sigma), the Receiving peers verify the signature w.r.t. \mathsf{pk}, and can verify \vec v is indeed in the subspace signed by P_{prop} and vector \vec a contains the correct coefficients by checking
Upon receiving k tuples \bigl\{(\mathsf{pk}_i,\vec{v}_i, \vec{a}_i, \vec{\mathsf{C}}_i,\sigma_i)\bigr\}_{i=1}^k and after verifying that all the vectors \vec{v}_1,\ldots,\vec{v}_k are in A and the correctness of the vectors \vec a_i, peer P can become a Sending Peer. Let \mathbf{V} \in \mathbb{F}^{M \times k} be the matrix whose columns are \vec{v}_1,\ldots,\vec{v}_k, and let \mathbf{A} \in \mathbb{F}^{N \times k} be the matrix whose columns are \vec{a}_1,\ldots,\vec{a}_k. Since the received tuples are valid, we know that
\mathbf{V} = \mathbf{M} \cdot \mathbf{A}. \tag{1}
The peer samples a new vector \vec{r} \in\mathbb{F}^k, sets
and sends (\mathsf{pk},\vec{v}', \vec{a}', \vec{\mathsf{C}},\sigma) to its peers. Observe that \vec{v}' = \mathbf{M} \cdot \vec{a}', as required for a valid broadcast (indeed, we simply multiplied both sides of (1) by \vec{r}).
After receiving N linearly independent vectors \vec v_1, \ldots, \vec v_N \in \mathbb{F}^M with corresponding vectors of coefficients \vec b_1, \ldots, \vec b_N \in \mathbb{F}^N such that \vec v_i=\sum_{i=1}^N b_{ij}\vec m_j for all i=1,\ldots.N, the receiver P can be a Reconstructor and use those linear combinations to recover (\vec m_1, \ldots, \vec m_N) and thus the entire block \mathbf{M}.
As noted in the original post, the communication problem with this approach is twofold: each new vector in A travels along with N commitments and N coefficients.
In this post, we explain how Linearly-homomorphic Signatures and in particular the work of Boneh, Freeman, Katz, and Waters (BFKW) from 2008 can prevent the communication of multiple commitments across the peers.
Disclaimer:The ideas we present below already exist in the literature or have appeared in previous ethresearch discussions. We do not claim scientific novelty. Our goal is to collect and summarize these ideas in one place, to save others from repeatedly rediscovering the same techniques through scattered chats and threads.
Linearly-homomorphic Signatures
A Linearly-homomorphic signature scheme (LHSS) is a signing scheme for which only the secret key owner can create signatures on fresh vectors of its choice. Any entity with access to the public key can combine these signatures to create just one that verifies with respect to any linear combination of the original ones, that is, can sign any vector in the subspace generated by the original messages. Formally:
Definition (Boneh et al., 2008): A linearly homomorphic signature scheme (LHSS) over a vector space A\subseteq\mathbb{F}^N is a tuple of probabilistic, polynomial-time algorithms (\mathsf{Setup, Sign, Combine, Verify}) with the following functionality:
- \mathsf{Setup}(n, pp)\to(\mathsf{sk,pk}): On input a security parameter n and additional public parameters pp that include the dimension N of the ambient space and the dimension k of subspaces to be signed, this algorithm outputs a secret key \mathsf{sk} and a public key \mathsf{pk}.
- \mathsf{Sign}(\mathsf{sk, id}, \vec m)\to\sigma: On input a secret key \mathsf{sk}, an identifier \mathsf{id}\in\{0, 1\}^n, and a vector \vec m\in A, this algorithm outputs a signature \sigma.
- \mathsf{Combine}(\mathsf{pk}, \mathsf{id}, \{(a_i, \sigma_i)\}_{i=1}^k)\to\sigma: On input a public key \mathsf{pk}, an identifier \mathsf{id}, and a set of tuples \{(a_i, \sigma_i)\}_{i=1}^k with a_i\in\mathbb{F}, this algorithm outputs a signature \sigma. (This \sigma is intended to be a signature on \sum_{i=1}^k a_i \vec m_i.)
- \mathsf{Verify}(\mathsf{pk}, \mathsf{id},\vec v, Ï)\to1/0: On input a public key \mathsf{pk}, an identifier \mathsf{id}\in\{0,1\}^n, a vector \vec v\in A, and a signature \sigma, this algorithm outputs either 0 (reject) or 1 (accept).
For completeness, we require that for each (\mathsf{sk, pk}) output by \mathsf{Setup}(n, pp), we have that:
- For all \mathsf{id}\in\{0,1\}^n and \vec v\in A, if \sigma\gets\mathsf{Sign}(\mathsf{sk, id}, \vec v) then \mathsf{Verify}(\mathsf{pk}, \mathsf{id},\vec v, Ï)=1.
- For all \mathsf{id}\in\{0,1\}^n and all sets of triples \{(a_i, \sigma_i, \vec v_i)\}_{i=1}^k if it holds that \mathsf{Verify}(\mathsf{pk}, \mathsf{id},\vec m_i, Ï_i)=1 for all i \in [k], then \mathsf{Verify}(\mathsf{pk}, \mathsf{id}, \sum_{i=1}^\ell a_i \vec m_i, \mathsf{Combine}(\mathsf{pk}, \mathsf{id}, \{a_i, \sigma_i)\}_{i=1}^k)= 1.
The security notion we need to capture here is that no party other than the \mathsf{sk} holder should be able to claim a signature \sigma^* on a vector \vec v^* that verifies with respect to \mathsf{pk} unless \vec v^*\in A . Therefore, we define the following game between a challenger and an adversary:
- Setup Phase. The challenger runs (\mathsf{sk,pk})\gets\mathsf{Setup}(n, pp) and sends \mathsf{pk} to the adversary \mathcal{A}.
- Query Phase. The adversary now makes a polynomial number q of oracle queries, where the i-th query has the following form:
- The oracle takes as input a set of vectors \vec{v}_{i,1},\dots,\vec{v}_{i,k} \in \mathbb{F}^M.
- We let A_i \subseteq \mathbb{F}^N be the subspace generated by these vectors.
- The oracle samples \mathsf{id}\gets \{0,1\}^n, and computes \sigma_{i,j}\gets\mathsf{Sign}(\mathsf{sk}, \mathsf{id}_i, \vec{v}_{i,j}) for all j=1, \ldots, k.
- It outputs (\mathsf{id}_i, (\sigma_{i,j})_{j=1}^k).
- Forgery Phase. The adversary outputs a triple (\mathsf{id}^*, \vec v^*\neq 0, \sigma^*). We say that it wins the game if the following two hold:
- Valid signature: we have \mathsf{Verify}(\mathsf{pk}, \mathsf{id}^*,\vec v^*, \sigma^*)=1;
- Freshness: we have \mathsf{id}^*\notin\{\mathsf{id}_i\}_{i=1}^q or \vec v^*\notin A_i for every i\in [q] with \mathsf{id}^* = \mathsf{id}_i.
The scheme is secure if no efficient (i.e., PPT) adversary wins this game with non-negligible probability.
Intuitively, this security property states that any signature that verifies with respect to the given public key \mathsf{pk} and an identity \mathsf{id}^*, must be on a vector in the span of the vectors that the honest signer signed with respect to \mathsf{id}^*.
Linearly-homomorphic Signatures in RLNC
Below, we explain how the BFKW Linearly-homomorphic Signature scheme can be used to replace commitments in the RLNC protocol.
The block proposer owns the secret key \mathsf{sk} and thus is the only one that can create âfreshâ signatures. In this setting, we require that they parse the block as a matrix and sign the columns of it.
That means the proposer gets to set the subspace A. All other users can combine those signatures to create signatures on linear combinations of the vectors that define the block (by the completeness property).
By the security property, if a signature verifies with respect to the block proposerâs public key, it is then a linear combination of the original signatures, and thus a signature on a linear combination of the original vectors.
To generate new coefficients, or even to reconstruct the original vectors after receiving N linearly-independent vectors, peer P has access to the new signature \sigma and a set of coefficients \vec a that the sender claims to be the coefficients that combine the original signatures \sigma_1, \ldots, \sigma_N to \sigma. The receiving peer needs to verify not only that \sigma is a linear combination of the block proposerâs signatures, which is true iff \mathsf{Verify} outputs 1, but also that the coefficients of that linear combination are indeed the ones in \vec b.
In order to verify each signatures with respect to the specific coefficients that conform the linear combination, we formally extend the functionality of LHS schemes by slightly modifying its syntax as hinted in the seminal work:
- \mathsf{RLNC}.\mathsf{Sign}(\mathsf{sk, id}, \vec m_i, i): Let \vec e_i\in\mathbb{F}^N be the unity vector that takes value 1 in the position i and 0 everywhere else (that is, is the i-th vector in the canonical basis of \mathbb{F}^N) and output \sigma\gets\mathsf{Sign}(\mathsf{sk, id}, \vec m_i|| \vec e_i)
- \mathsf{RLNC}.\mathsf{Verify}(\mathsf{pk}, \mathsf{id},\vec v, \sigma, \vec a)\to1/0: Set \vec v'=\vec v|| \vec a and output \mathsf{Verify}(\mathsf{pk}, \mathsf{id},\vec v', \sigma)
Essentially, by adding the vector \vec e_i to the message \vec m_i, we will have that the last N elements of any signed vector \vec v will be the unique coefficients that represent \vec v as a linear combination of the messages \{\vec m_i\} signed by the \mathsf{sk} holder. Intuitively, by the unforgeability property of the LHSS, if the \mathsf{Verify} algorithm outputs 1 on input \vec v, \vec a, then \vec v=\sum a_i \vec m_i except with negligible probability.
Threat Model
When implementing RLNC for block propagation, we assume an honest block proposer and set aside general networking attacks. Still, the system must remain resilient against Denial of Service (DoS) attacksâspecifically pollution attacks. In this scenario, an adversary attempts to disrupt the propagation of block \mathbf M by injecting a malicious vector \vec vâČ\notin A, with A being the subspace defined by the original block data. This is covered by the security property of LHS, that requests that no adversary can generate valid signatures for vectors that are not in A.
The inclusion of a string \mathsf{id}\in\{0,1\}^n within the signature serves as a unique identifier for a specific subspace. This allows a participant to sign multiple subspaces using the same public key while preventing vectors from different spaces from being combined, e.g., if this participant takes the role of the block proposer in multiple slots. Specifically, if a user signs subspace V_1 at time t_1 and subspace V_2 at time t_2, no party should be able to forge signatures on vectors in \mathsf{span}(V_1\cup V_2) that verify against \mathsf{pk}. While the BFKW protocol requires \mathsf{id} to be unpredictable, the block propagation setting further requires \mathsf{id} to be tied to a specific block. To satisfy both conditions, we set \mathsf{id}=H(\mathsf{num_{slot}},\mathsf{salt}), where \mathsf{salt} is sampled randomly by the proposer during signing, H is a hash function (modeled as a random oracle), and \mathsf{num_{slot}} is the slot number of the proposed block.
The BFKW scheme for RLNC
We present the linearly-homomorphic signature scheme in BFKW with the new RLNC-specific syntax. Note that BFKW works similarly to BLS signatures that are already implemented in Ethereum. The main difference is that instead of signing messages, the users sign vectors and thus compute M hashes per signature (where M is the dimension of the vectors) instead of one. Consider a bilinear group (\mathbb{G}_1,\mathbb{G}_2, \mathbb{G}_T, p, e), g_1, g_2 generators of \mathbb{G}_1 and \mathbb{G}_2, respectively, and a hash function H:\{0,1\}^*\times \{0,1\}^*\to \mathbb{G}_2 modeled as a random oracle.
- \mathsf{RLNC.Setup}(n, pp)\to(\mathsf{sk,pk}): Sample \mathsf{sk}\gets\mathbb{F}, set \mathsf{pk}=g_1^{\mathsf{sk}}.
Let A=\mathsf{span}\{\vec m_1,\ldots, \vec m_N\}, \vec m_i\in\mathbb{F}^M. - \mathsf{RLNC.Sign}(\mathsf{sk, id}, \vec m, N)\to\sigma:
- Set \vec m'=\vec m || \vec e_i for \vec e_i\in\mathbb{F}^N being the i-th unity vector and i the position of \vec m in the ordered basis of A.
- Output \sigma\in\mathbb{G}_2 as follows:
\sigma=\left(\prod\limits_{s=1}^M H(\mathsf{id},s)^{m'_{s}}\right)^{\mathsf{sk}} - \mathsf{RLNC.Combine}(\mathsf{pk}, \mathsf{id}, \{(a_i, \sigma_i, \vec v_i)\}_{i=1}^k)\to(\vec v, \sigma, \vec a):\vec v=\sum_{i=1}^k a_i\vec v_i, \qquad \sigma=\prod_{i=1}^k \sigma_i^{a_i}
- \mathsf{RLNC.Verify}(\mathsf{pk}, \mathsf{id},\vec v, Ï, \vec a)\to1/0:
- Set \vec v'=\vec v||\vec a
- Output 1 if and only if
e\big(g_1, \sigma\big)=e\left(pk, \prod_{s=1}^M H(\mathsf{id}, s)^{v'_s}\right)
Security: The protocol presented above is complete and secure in the random oracle model under the co-computational Diffie Hellman (co-CDH) assumption in (\mathbb{G}_1, \mathbb{G}_2). The co-CDH assumption in (\mathbb{G}_1, \mathbb{G}_2) states that it is computationally infeasible to compute g_1^x\in\mathbb{G}_1 given g_1\in\mathbb{G}_1 and g_2, g_2^x\in\mathbb{G}_2.
RLNC with Linearly-homomorphic Signatures
The result of replacing homomorphic commitments by the linearly-homomophic signature scheme of BFKW in the protocol proposed here is the following:
Proposer
Proposerâs key pair is (sk, pk=g_2^{sk}). On input block \mathbf{M}\in\mathbb{F}^{M\times N}, the proposer samples \mathsf{salt}\gets\{0,1\}^n and sets \mathsf{id}=H(\mathsf{num_{slot}},\mathsf{salt}).
- For each i\in[N]:
- \sigma_i\gets \mathsf{RLNC.Sign}(sk, \mathsf{id}, \vec m_i, i):
- For each user u_j\in D
- Sample \vec a_j\gets \mathbb{F}^N
- \sigma_j\gets\mathsf{RLNC.Combine}(pk, \mathsf{id}, {(a_{j,i}, \sigma_i)}_{i=1}^N)
- Send \pi_j=(\mathsf{salt}, \vec v_j, \vec a_j, \sigma_j), where \vec v_j=\sum_{j=1}^N {a_{i,j}} \vec m_i
Receiving Peers
- Parse (\mathsf{salt}, \vec v, \vec a, \sigma)\gets \pi
- Output b\gets\mathsf{RLNC.Verify}(pk, \mathsf{id}, \vec v, \sigma, \vec a)
Sending Peers
On input (\pi_1, \ldots, \pi_L):
- Parse (\mathsf{salt}, \vec v_i, \vec a_i, \sigma_i)\gets \pi_i for all i\in [L]
- Sample \vec a'\gets\mathbb{F}^L
- Compute \mathsf{id}=H(\mathsf{num_{slot}, salt})
- \sigma\gets\mathsf{RLNC.Combine}(pk, \mathsf{id}, (a'_i, \sigma_i)_{i=1}^L)
- Set \vec v=\sum_{i=1}^L a'_i \vec v_i
- Redefine vector \vec a with a_i=a'_i\sum_{i=1}^L a_j
- Output \pi=(\vec v, \vec a, \sigma)
On the efficiency
Below we set a comparison with the proposal by Potuz. Note that in the LHS approach, we trade efficiency of P_{prop} and the receiving/sender peers to avoid sending N group elements to the network.
- Proposer:
- Signing a message involves computing M hashes H to \mathbb{G}_2 and then performin M group operations in \mathbb{G}_2, whereas in the previous approach involved only M group operations for a Pedersen commitment.
- Receiver:
- Verifying the signature is M \mathbb{G}_1 operations and two pairings. Verifying a commitment is 2M \mathbb{G} operations.
- Sender:
- Performs L\mathbb{G}_1 operations to compute the new signature in addition to the LM field operations it already performs in the previous approach to compute the new vector \vec v.
- Communication:
- Each signature is 1\mathbb{G}_2 element, same as the Pedersen commitments. With the previous approach, we have N commitments that can be communicated as a sidecar, while in the signature approach we have 1 group element being communicated per time.
- Reconstruction: Works the same way as before, after receiving N linearly-independent vectors and verifying they are indeed in the subspace A, any node can reconstruct block \mathbf M by solving a system of equations.
| Pedersen Commitments | Linearly-Homomorphic Signatures | |
|---|---|---|
| Committing(P_{prop}) to one vector | M\ \mathbb{G} ops | M\ \mathbb{G}_2 ops, M hashes to \mathbb{G}_2 |
| Receiver (Verify \vec v\in A) | Commit | Commit + 2 pairings |
| Sender | LM\ \mathbb{F} ops | LM\ \mathbb{F} ops, L \ \mathbb{G}_2 ops |
| Communication | N\ \mathbb{G}, N\ \mathbb{F} | 1\ \mathbb{G}_2, N\ \mathbb{F} |
Future Work
A natural extension of this work is the transition toward post-quantum (PQ) security. The BFKW scheme, while efficient, relies on the hardness of the co-CDH problem in bilinear groups, which is susceptible to attacks by large-scale quantum computers. To future proof RLNC-based block propagation, we should explore Linearly Homomorphic Signatures schemes based on post-quantum assumptions.
There are proposals which suggest that the commitments \mathsf{C}_1, \ldots, \mathsf{C}_N and the signature on them can travel the network independently of the newly generated vectors. â©ïž