RLNC Optimizations

ethresear.ch

RLNC Optimizations Author: Gottfried Herold Thanks to Arantxa Zapico and Benedikt Wagner for helpful feedback. This is part of a 3-part series of blog posts related to RLNC, that discuss Optimizations for RLNC (this document) Linearly Homomorphic Signatures for RLNC Security of RLNC TL;DR: There are some optimizations possible to reduce the communication overhead of RLNC. A significant part of the overhead comes from having to transmit, if done naively, N field elements (in a large field) for RLNC coefficients. The most promising optimization we describe here reduces that to roughly N-k field elements + a moderate number of extra bits, whenever the sender already has k chunks (out of N required ones), without significantly hampering the probability of successfully disseminating messages. Introduction to RLNC In Ethereum, we frequently face the challenge of efficient data dissemination . A party (say, Alice) holds a piece of data, and we want to ensure that all (or most) other parties (Bob, Charlie, Dave, etc.) receive this data as quickly as possible — while minimizing the bandwidth burden on everyone involved. A typical example is a block proposer (Alice) holding a new block (or blobs, in the context of DAS), which needs to be propagated to all nodes in the network. Recently, it has been suggested and extensively discussed that random linear network coding (RLNC) could be used to address this dissemination problem (see here and here ). In this post, we take another close look at RLNC, explore ways to improve its practical efficiency, and analyze it in a way that accounts for adversarial behaviour. Disclaimer. Most or all of the ideas we present here 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, to save others from repeatedly rediscovering the same techniques through scattered chats and threads. Problem Statement and Notation Before we dive into RLNC, we recall the problem statement and fix some notation used throughout the post. We mostly follow the notation in this post . We consider one dedicated party P_{prop} , holding a message \vec{M} \in (\mathbb{F}^M)^N . Throughout, we will call this party the proposer , even though data dissemination may show up in other places in the protocol. We also consider a set of receiving parties, and our goal is that each of those parties receives the proposer’s message \vec{M} . The reader may imagine that all parties are connected to roughly D peers. How RLNC works Here is how RLNC works: The idea is that every party P has, at each point in time t , some knowledge about the proposer’s message \vec{M}=(\vec{m}_1,\ldots,\vec{m}_N)\in(\mathbb{F}^M)^N . This knowledge comes in the form of linear relations. Such a linear relation consists of a (known to P ) relation vector \vec{a}\in \mathbb{F}^N , for which P knows the product \vec{v}= \sum_{j=1}^N a_i \vec{m}_i \in \mathbb{F}^M, which we call the message chunk corrsponding to \vec{a} . Now observe that if P knows the message chunk corresponding to any k relation vectors \vec{a}_1,\ldots,\vec{a}_k , it can, by simple linear algebra, easily compute it for any relation vector \vec{a} in the span A of the \vec{a}_i . This way, the span A measures how much P knows about \vec{M} , with A=\{0\} meaning P knows nothing and A = \mathbb{F}^N means P fully knows \vec{M} . In this document, we shall call A the known space of P at time t . For any \vec{a}\in A , the party P can procure a pair (\vec{a},\vec{v}) with \vec{v}=\sum_j a_j \vec{m}_j that contains knowledge about \vec{m} that may potentially be useful for other parties. The RLNC protocol itself starts with P_{prop} knowing all of \vec{M} in the above sense (so its known space is \mathbb{F}^M ) and the known space of all other honest parties being \{0\} . Then each party P will try to propagate its knowledge to each of its peers. Whenever P sends a message to a peer P' , the sender samples some \vec{a}\in A uniformly at random from its known space and sends P' that \vec{a} , together with the message chunk \vec{v}=\sum_{j=1}^N a_i\vec{m}_i . This has the effect of changing the recipient’s known space from A' to the span of A' and \vec{a} . Furthermore, we shall add some data integrity protection mechanism (essentially a so-called linearly homomorphic signature under P_{prop} 's public key) intended to prevent malicious actors from sending messages with invalid \vec{v} that do not satisfy the \vec{v}=\sum_i a_i\vec{m}_i relation. Somewhat more formally, at each point in time, every (honest) party P stores k relation vectors \vec{a}_1,\ldots,\vec{a}_k with \vec{a}_i\in\mathbb{F}^N , together with corresponding message chunks \vec{v}_1,\ldots \vec{v}_k , with \vec{v}_i\in\mathbb{F}^M . some data related to message integrity Those data are supposed to be related to the initial proposer’s message by \vec{v}_i = \sum_{j=1}^N a_{ij} \vec{m}_j , i.e., for each \vec{a}_i that a party P has stored, it knows the scalar product \vec{v}_i of \vec{M} with that vector. Initially, P_{prop} starts with the N unit vectors \vec{a}_1 = (1,0,0,\ldots), \vec{a}_2 = (0,1,0,0,\ldots), \ldots with corresponding \vec{v}_i = \vec{m}_i . The other honest parties start without any relation vectors. Now, honest parties P will keep sending messages to each of its peers. Assume k is the number of relation vectors \vec{a}_1,\ldots,\vec{a}_k stored by P at the time of sending. Then it samples r_1,\ldots,r_k\in\mathbb{F} uniformly and computes \vec{a} = \sum_i r_i \vec{a}_i \vec{v} = \sum_i r_i \vec{v}_i Some data integrity information C and sends \vec{a} , \vec{v} and C to its peer. Note that \vec{v} is the corresponding message chunk for \vec{a} and we select fresh randomness for each message and each peer. On receiving such a message, a peer P' first validates the data integrity information C ; if this fails, then P' ignores the message (and potentially blacklists the sender). Otherwise, the P' adds \vec{a} and \vec{v} to its stored relation vectors and message chunks. Once P' obtains N linearly independent relation vectors, P' can compute and output \vec{M} : If we organize those N relation vectors into a matrix B and the message chunks into a vector (of vectors) \mathbf{v} , we have \vec{M} = B^{-1}\mathbf{v} , provided the message chunks are related to relation vectors in the intended way. Note that P' can (and should) still send messages to its peers after outputting \vec{M} . Note that, as explained above, peers that have 0 relation vectors would constantly send useless messages with \vec{a} = \vec{0} and \vec{v}=\vec{0} , but this can be easily avoided. Furthermore, each peer actually only ever has to store at most N relation vectors, as only their span matters. In practice, we can keep some number k of relation vectors in a matrix B in echelon form (with rows corresponding to the relation vectors, so the row span is exactly the known space). Then, whenever we receive a new message with relation vector \vec{a} that passed data integrity validation, we reduce \vec{a} wrt. B ; if this results in \vec{0} , then \vec{a} already was in the known space, so the incoming message was useless and we ignore it. Otherwise, we can add a new row to B , resulting in a larger matrix, still in echelon form. This way, we only ever need to sample k random field elements per outgoing message and we perform the matrix inversion as we collect messages, rather than at the end, thereby reducing latency. We will also see below that keeping B in echelon form is useful for bandwidth-saving optimizations. Why RLNC works Let us give an intuitive reasoning why RLNC works (assuming everyone is honest): every peer in the network communicates one linear relation per message about \vec{m} to its peers. In fact, if a honest peer P with known space A sends a message with relation vector \vec{a} to another honest peer P' with known space A' and A\not\subseteq A' , then there is least a 1-1/|\mathbb{F}| chance that \vec{a}\notin A' . In this case, the known space of P' will grow. Consequently, as P and P' exchange message (assume for simplicity that no other messages are sent to either P or P' by other parties), their known spaces will eventually converge to the span of the union of A and A' . This way, knowledge about the message propagates outward from the proposer until it reaches all connected peers in the network. In fact, we may reasonably hope (depending on the network topology) that if a peer does not yet know all of \vec{M} , then each of its received message will increase the rank of its known space, so, ideally, peers learn \vec{M} after only N incoming messages. Dishonest setting In a more realistic setting, we need to assume that an adversary is present and we have a deadline by which we want each peer to have received knowledge about all of \vec{m} . It is instructive to look at what can go wrong now: The proposer P_{prop} may be malicious and send inconsistent data and/or only send messages with relation vectors from a strict subspace of \mathbb{F}^N , thereby withholding parts of \vec{M} . An adversary might send bad messages where the relation vector \vec{a} and message chunk \vec{v} are not related in the intended way, i.e. where \vec{v} \neq \sum_j a_j \vec{m}_j . An honest peer might not receive N messages by honest peers by the time the deadline has passed. An honest peer might receive N or more messages by honest peers by the time the deadline has passed, but too many of those messages are useless, (i.e. have a relation vector that already is in the known space) Let us briefly discuss how to tackle each of these issues. For more details, we refer to an upcoming post that specifically discusses this. Malicious Proposer If P_{prop} is malicious, there is not much RLNC can do, as there might be no meaningful \vec{M} to disseminate in the first place. Also, different parties might end up reconstructing different \vec{M} (or, if they receive more than N messages, those messages are inconsistent). The data integrity mechanism will be meaningless here, as those contain signatures under P_{prop} 's keys and P_{prop} is malicious. In the Ethereum use cases, the case of a malicious P_{prop} is solved by the consensus protocol, where the block header acts as a commitment to \vec{M} . Parties that reconstruct \vec{M} need to check the reconstructed \vec{M} against that commitment. We will assume the proposer is honest from now on. Adversarial bad messages Regarding the second issue of message with \vec{v} \neq \sum_j a_j \vec{m}_j , this is what the data integrity mechanism is for. As the purpose of this note is to explain practical optimizations for RLNC (and why those are secure), we defer to the separate blog post Linearly-homomorphic signatures for RLNC for more details on only focus on the consequences on efficiency here. The data integrity mechanism has several consequences on efficiency: Firstly, they are a source of complexity and cause computational overhead from having to compute signatures and verifying them. Clearly, we have to send extra data (essentially a signature) with every message we send, thereby consuming bandwidth. It puts restrictions on what fields \mathbb{F} we can use for RLNC. The proposal detailed in Linearly-homomorphic signatures for RLNC uses the BFKW scheme, which uses BLS signatures. As a consequence, the field \mathbb{F} will be the BLS scalar field, which for BLS12-381 means \mathbb{F} will be a prime-order field with a 255 bit prime. Parties do not receive enough messages by the deadline The third issue just means that there is not enough bandwidth going from the proposer (via multiple paths) to the recipient. There is nothing we can do about this. Parties receive too many useless messages For the actual success probability of RLNC in our setting, we provide a detailed analysis in the upcoming 3rd post of this series of posts about RLNC, which gives an upper bound on the failure rate that a given honest recipient P does not learn all of \vec{M} by the deadline, in an appropriate adversarial setting. Our analysis also covers the optimizations that we describe in this note. As the definitions required to precisely state the result of the analysis are somewhat technical, we only give an intuition and state the conclusions of the analysis here, in order to explain why our optimizations described later make sense. Roughly speaking, image that there is a backbone communication graph G_{RLNC} that encodes message-sent with corresponding message-received events for messages sent between honest parties, including relevant timing information for those events. We assume that an adversary cannot prevent/delay these messages, but may introduce additional messages. We assume that the data integrity scheme is perfect, so those additional messages have consistent \vec{v} and \vec{a} . We can then consider the probability (over the randomness used when honest peers select their relation vectors) that in a given run of RLNC, some peer P learns all of \vec{M} . We show that the probability that a peer P does not learn the message is upper bounded by \Pr[\text{$P$ does not learn $\vec{M}$}] \leq \binom{C}{C-N+1} p^{C-N+1} D^{C-N+1}\prod_{i=1}^{C-N+1}\binom{C-i}{N-1}. Here, C is (roughly) the number of edge-disjoint paths in G_{RLNC} connecting the proposer with P (thereby measuring the width of G_{RLNC}) and we require C to be at least N . The parameter D is an upper bound on the lenght of these paths, thereby measuring the depth of G_{RLNC} . The term p is related to how honest parties choose their randomness. Notably, p is given by p=\max_{A' \subsetneqq A} \{\Pr[\text{honest $P$ with known space $A$ outputs relation vector in $A'$}]\}, where A'\subsetneqq A \subseteqq \mathbb{F}^N range over linear spaces, where wlog. \dim A' = \dim A - 1 . The probability space is for P sending a single message (we assume that P chooses independent randomness for the relation vector of each outgoing message). We have p=1/|\mathbb{F}| for RLNC as described above. Importantly, our bound generalizes to some variants we describe below where we change the way the randomness is generated: If honest parties P select their relation vectors as \vec{a} = \sum_i r_i \vec{a}_i , where \vec{a}_i are a basis of P 's known space and the r_i are uniform and independent from a smaller set S\subset \mathbb{F} rather than all of \mathbb{F} , then p=1/|S| . Reducing Communication Overhead The Naive Approach and Its Efficiency Recall that in RLNC as described above, the participants (both the original sender and intermediate nodes) send chunks to each of their peers consisting of some message chunks \vec{v}\in \mathbb{F}^M relation vectors vectors \vec{a}\in\mathbb{F}^N some data C related to message integrity. We require (and in a potentially malicious setting, we shall use C to guarantee this, unless P_{prop} is dishonest) that v is related to the original message \vec{M} = (m_1,\ldots,m_N) via v=\sum a_i m_i . One big concern about RLNC is that the need to transmit both C and the relation vectors \vec{a} create some extra overhead. For considerations on C , we refer to Linearly-homomorphic signatures for RLNC . With this proposal, the overhead from C is given by N elements from \mathbb{F} and 1 elliptic curve point from \mathbb{G}_2 (on the appropriate pairing-friendly curve). In this note, we only care about ways to reduce the cost to transmit \vec{a} . First, let us start by estimation the total impact of this overhead: measured as a fraction of the size of the message chunk(s), which should be thought of as the payload, the relation vectors adds an extra \frac{N}{M} increase in message size. We note that the overhead from C is approximately the same; in particular, even if we completely eliminated the overhead from the relation vectors, we can at best reduce the total overhead by less than 50\% . One way to reduce the overhead is to make N smaller (while keeping the total size N\cdot M of the message to be disseminated constant). However, this comes at the cost of larger M , meaning our individual chunks need to be larger. In the extreme case with N=1 , we just send the full data in one chunk, so we essentially [1] perform no RLNC encoding at all. In fact, one main reason we view the message as an element from (\mathbb{F}^M)^N rather than \mathbb{F}^{K} with K=MN is exactly to control this tradeoff between overhead and chunk size. An alternative (but equivalent) way of viewing this is that we run M separate instances of RLNC (each with M=1 ), but we share the relation vector between the instances, thereby only need to transmit the relation vector once. Small Coefficients Approach We now consider the parameters N and M and also the field size fixed. Due to the way RLNC specifies that the relation vectors \vec{a} are chosen/constructed, they are essentially uniformly random. Hence, we cannot really do better (for an individual chunk, at least) than send N\log_2(|\mathbb{F}|) bits for information-theoretic reasons. So the only ways to improve here is to modify the distribution of the \vec{a} . Let us assume (as is essentially forced upon us by C ) that \mathbb{F} is a (large) prime field. The most simple modification is to try to use \vec{a} with small coeffcients, say -B\leq a_i \leq B for each a_i and some bound B\ll |\mathbb{F}| . Then we only require N\log_2(2B+1) bits to communicate \vec{a} . Indeed, this can give some improvements and may be a valid option, but this approach comes with three main limitations and issues: The first limitation is that involved parties other than the proposer cannot choose the relation vectors \vec{a} freely. Instead, they received k \leq N (valid) incoming chunks with linearly independent relation vectors \vec{a}^{(1)},\ldots,\vec{a}^{(k)} from their peers. The relation vectors \vec{a} of their own outgoing chunks must be of the form \vec{a} = \sum_{i=1}^k r_i \vec{a}^{(i)} . One reason is that, unless \vec{a} is in the span of the \vec{a}^{(i)} , the sending party does not know the corresponding payload v=\sum a_i m_i . So if we want \vec{a} to be still small, we would choose small r_i , say |r_i| \leq B' . Then, provided the incoming \vec{a}^{(i)} have coefficients bounded by B , the outgoing coefficients are bounded by k\cdot B \cdot B' . Taking B'=B , with this scheme, the size of coefficients grows by a factor of kB \leq NB at every hop, so at i hops away from the proposer, the coefficients will have coefficients bounded by B^iN^{i-1} . Once this exceeds |\mathbb{F}| , we can just switch back to a more naive encoding and scheme. A consequence is this small-coefficient scheme mostly benefits the parties that are close to the proposer. The second limitation is that in an adversarial scenario, it is straightforward to shut down this optimization (unless countermeasures are taken): a malicious party could just send an (otherwise honestly generated) chunk with large coefficient vector to some honest party P . Then outgoing messages by P will also have large coefficient vectors (and so do the outgoing messages of those that P sent messages to etc.) A potential countermeasure is to just ignore message with unexpectedly large coefficient vectors: if this is used for block propagation in Ethereum, we basically know at what time the proposer sent their message. Assume that message propagation takes time t . If we receive a message at time T with large coefficients of size >B^iN^{i-1} for some i , we know that (if it was honest) this message corresponds to a distance at least i+1 from the proposer in the appropriate message graph. If (i+1)\cdot t > T , there is some dishonesty going on and we can just ignore the incoming message; essentially, we need to mandate a lower bound on message propagation time (and, if needed, delay sending messages). This adds complexity and might slow down propagation. The third issue is that by choosing the r_i from a smaller set, this might harm the functionality of RLNC and increase the probability of “bad randomness” in the above sense . Importantly, the RLNC protocol can tolerate such failures in a setting where we just continue to send messages: all that goes wrong is that a given participant receives some useless messages and might require more than N message to reconstruct the original message. In fact, the analysis we cited above extends to this setting and the only effect is a worse p -term with p=1/(2B+1) . Now, since the proposed message integrity scheme forces a field size with |\mathbb{F}| \approx 2^{255} , the failure rate of the original scheme is complete overkill; for our application a failure rate of maybe 0.1\%\approx 2^{-10} might even be good enough. So reducing that (overkill) security level to gain some efficiency seems worthwhile. Further improvements We note that the small coefficients approach can be slightly improved further (but we do not analyze this): Parties whose known space is \mathbb{F}^N , i.e., that can reconstruct all of \vec{M} , can actually “reset” the coefficients to size B , undoing the per-hop coefficient growth. The coefficient growth by k B' per hop is a worst-case bound that comes from summing k terms with random signs. If k is large, we expect a lot of cancellations. At the expense of some resampling, this can be used to bring the growth down to O(\sqrt{k}\cdot \textrm{poly}(\log(k)) B' ; the security loss due to resampling can be alleviated by increasing B' by a O(\textrm{poly}(\log(N))) factor. Tree of Hashes Instead of using a bounded domain \{-B,\ldots,+B\} each party could also sample the randomness as H(s) where H is some hash function (modelled as a random oracle for simplicity) and s is a small seed from some space S . Concretely, whenever a party with known space A of rank k and basis \vec{a}_1,\ldots \vec{a}_k needs to choose a relation vector for an outgoing message, it uniformly samples a random seed s from some domain S of appropriate size and deterministically derives r_1,\ldots,r_r from H(s,k) . We then choose the outgoing relation vector as \vec{a} := \sum r_i \vec{a}_i . Note here that \vec{a} depends on some basis \vec{a}_1,\ldots\vec{a}_k of A , not just on A . For the proposer, we may use the standard basis of \mathbb{F}^N , so \vec{a} = \vec{r} . Now, in the case of the proposer sending a message, instead of communicating \vec{a} , the proposer can simply send the hash seed s (and k=N ) and the recipient can then derive the relation vector on its own. In the case of intermediate nodes, we can proceed similarly: Instead of sending a relation vector, they send their hash seed s (and k ), together with the (tree of) hash seeds they had received themselves (which also defines their used basis of the known space). This allows the recipient to reconstruct the coefficient vector from the hash seeds. Variant Instead of a random oracle H to derive r_1,\ldots, r_k via H(s,k) , we may choose s from S\subsetneqq\mathbb{F} and simply set r_i = s^i , i.e. we use a simple polynomial instead of a hash function. This has the advantage of being cheaper to compute and actually allowing a formal analysis. Analysis This scheme has similar downsides to the small coefficients approach due to the fact that the size of the hash tree that needs to be communicated grows with each hop from the proposer. Let us compare efficiency to the small-coefficients approach (where S=\{-B,\ldots,+B\} for a fair comparison). Compared to small coefficients approach, the first hop is significantly cheaper: In the small coefficients approach, we send N small elements, so N \log(|S|) bits. With the hashes, we only need \log(|S|) . Regarding coefficient growth (without the \sqrt{k} -optimization variant in the small coefficients approach), in the small coefficients approach, if we have k incoming messages encoded with b_1,\ldots, b_k bits, then the outgoing message consists of approximately \max_i b_i + \log k + \log(|S|/2) bits. By contrast, with the hashes, we require approximately \sum b_i + \log(|S|) bits, which constitutes significantly worse growth. We ignore the need to communicate k , bounds, and the tree structure here for simplicity. As we can see, the hash-tree is better (only) if the trees remain shallow/very unbalanced. Note that the security of the general version is hard to analyse (the p -term in our security bound depends on the hash function H ). For the polynomial variant with s chosen from a set of size S , a simple application of the Schwartz-Zippel Lemma gives p\leq N/|S| . Reusing Randomness In the Ethereum use-cases, we may want to use RLNC repeatedly, where we expect the network in each instantiation to be the same (or similar) to the previous one. One way to capitalize that is for parties to re-use the same randomness for an outgoing message as in previous RLNC instances if they encounter the same known space as in the previous instance and should send a message to the same party. This couples the success/failure rates of those instances (but we may simply signal this), but we can save on communication by employing a general-purpose (stateful) compression function over each (persistent) connection to each peer. Note that in the Tree of Hashes approach, we may use the same randomness even if we do not have the exact same incoming hash tree as in a previous instantiation; this still gives some savings. However, the security of this in a malicious setting is completely unclear. Projective Coordinates We observe that for RLNC, it is only the (1-dimensional) subspace spanned by relation vectors \vec{a} that matters, not the relation vectors \vec{a} themselves. Also, if \vec{a} = 0 is the all-zero vector, the message is useless, so we should not send it at all. Consequently, we may work with projective coordinates to save (roughly) one field element per message. We concretely propose (due to compatibility with other improvements suggested below) that we normalize each \vec{a} such that the first non-zero entry is 1; we can thereby omit it, at the expense of needing to communicate the number of leading zero coefficients. Reduce Subspaces by what is already known A generalization of the above is to communicate (higher-dimensional) subspaces instead of 1-dimensional subspaces: Assume honest P is to send a message to P' and both P and P' know that A' is a subspace of P' 's known space. The main way this can happen is due to messages sent between P and P' : we can take A' as the span of relation vectors of all messages sent from P to P' and and ones received by P from P' . Note that messages sent by P might not (yet) have been received by P' (and P might not know this), but that will turn out not to matter, as long as it is eventually received. In this case, the relation vector \vec{a} that P sends only matters modulo A' . Consequently, we may (by taking some canonical representative) choose \vec{a} from the quotient space \mathbb{F}^N / A' , which has a dimension of N-\dim A' , hence we may save \dim A' coefficients. Concretely, we may choose as our representative a vector that is row-reduced modulo A' . Concrete implementation To make this a little less abstract, let us elaborate what this means in concrete terms: Echelon Form Let us first make some simplification to make the algorithms much easier to state: Remember that every party P has some known space A at each time. We may assume that P stores a basis \vec{a}_1,\ldots,\vec{a}_k of that space in reduced echelon form. Let us consider the k\times N matrix whose rows are the \vec{a}_i . For simplicity, we now impose that this basis has in fact the form B = \begin{pmatrix} 1 & 0 & 0 & * & * & \ldots \\ 0 & 1 & 0 & * & * &\ldots \\ 0 & 0 & 1 & * & * & \ldots \end{pmatrix} = \mathbb{1}_k || B', i.e. it starts with a k\times k identity matrix followed by B' ; the restriction here is that the projection of A to the first k coordinates has full rank k . Otherwise B would have some all-0 columns among the first k columns. If that were to happen, we can deal with it by permuting the columns of the matrix accordingly; to communicate this permutation, P only needs to send the indices of the relevant 0-columns. Note that this generalizes the issue above , where we needed to communicate the number of leading zeros, from a single row to a matrix. Choosing outgoing relation vectors Let us assume P has already sent some messages to P' and received some messages from P' . Let \tilde{A} be the span of all those relation vectors. Our algorithm actually only needs to know the rank \tilde{k} of \tilde{A} and where the all-zero columns are. By construction, we know that \tilde{A}\subseteq A . Again, we assume that the reduced row echelon form \tilde{B} of \tilde{A} starts with a \tilde{k}\times \tilde{k} identity matrix; otherwise we may need to permute columns again. Note that after we permuted columns to bring B into good shape, we only need to permute among the first k columns to also bring \tilde{B} into good shape. As a consequence, we may assume that both B and \tilde{B} have appropriate good shape with the same permutation of columns. If P needs to send a relation vector to P' , we simply ignore the first \tilde{k} vectors: P constructs the outgoing relation vector as \vec{a} = \sum_{i=\tilde{k}+1}^{k} r_i \vec{a}_i. where the r_i are chosen unformly. Since the \vec{a}_i are rows of a matrix in reduced echelon form, this means \vec{a} has the form \vec{a} = (0,\ldots, 0, r_{\tilde{k}+1}, r_{\tilde{k}+2}, \ldots r_{k}, *,\ldots, *) starting with \tilde{k} = \dim \tilde{A} many zeros that we do not need to communicate. Again, since only the 1-dimensional span of \vec{a} matters, we may rescale so that the first non-zero element among the r_i is 1 and we can also omit transmitting it (at the expense of transmitting the number of leading zeros). This corresponds to the projective optimization we explained above. In practice, for an exponentially large field, the first non-zero coefficient is r_{\tilde{k}+1} with all but negligible probability. This means we may just always set r_{\tilde{k}+1} to 1, choose the other coefficients uniformly (rather than rescaling) and avoid transmitting the number of leading zeros. Analysis The reason why this works is that for any \vec{a}' that we would choose in the normal way (without this optimization), there exists some (in fact unique) \vec{b}' in A' such that \vec{a} = \vec{a}' - \vec{b} has the form above. The distribution of the r_i defined by this is uniformly random. In fact, this can be obtained by row-reducing \vec{a}' wrt A' . We then normalize by setting the first non-zero coefficient to 1 as in projective optimization . Since choosing either \vec{a} or \vec{a}' as relation vector and sending it to P' has exactly the same effect on P' 's known space, this optimization does not change the success rate of the protocol at all. In practice, this optimization means that after each message sent/received to the same party, the number of coefficients we need to transmit drops by one. As far as computation is concerned, parties actually need to perform less computation in this variant. Column Permutations One annoying aspect is that we sometimes need to permute columns to ensure the matrices are in appropriate form. We note that in order to communicate those permutations, we only need to communicate where the all-zero columns are (the convention is to just move those after the good columns while retaining the ordering otherwise), which can be done by at most 1 bit per column (or less). An alternative to this approach that may be easier to implement is to just temporarily ignore any incoming relation vectors that would put B not into good shape and not add them to the known space. Note that once we receive other relation vectors, those temporarily ignored vectors may then be added again later; equivalently, we ignore (for outgoing messages) sufficiently many bottom rows of B resp. \tilde{B} . We remark that, for exponentially large fields, all-zero columns in B resp. temporarily ignored messages will, with overwhelming probability, only arise from either adversarial action or, with our optimization in place, from out-of-order messages. Unfortunately, it is hard for parties to attribute the malicious behaviour. In fact, whenever an honest party would have to temporarily ignore a message (which actually may become useful later), it would (with overwhelming probability) not have received a message at all without adversarial action or it is an out-of-order message. Communicating subspaces Let us consider the optimization above in the case where honest P sends i messages to P' and no messages is sent from P' to P . If we organize the relation vectors that P sent (as rows) into a matrix, then this matrix has triangular form \begin{pmatrix} 1 & * & * & * & \ldots\\ 0 & 1 & * & * & \ldots \\ 0 &0 &1 & * &\ldots\end{pmatrix} ands its row space is exactly by which the know space of P' grows from receiving those relation vectors. Now, if we suppose that P would send all those messages at once rather than sequentially, then we can do better: P can in fact send relation vectors, which, when organized as a matrix has the form \begin{pmatrix} 1 & 0 & 0 & * & \ldots\\ 0 & 1 & 0 & * & \ldots \\ 0 &0 &1 & * &\ldots\end{pmatrix} by row reducing the first vectors by the later ones. In practice, this means just leaving out even more summands in the computation of each \vec{a} : if \tilde{k} is the rank of the known space that the recipient already knows and P sent \ell relation vectors \vec{a}^{(1)},\ldots, \vec{a}^{(\ell)} in one go, then we can compute \vec{a}^{(j)} = \vec{a}_{\tilde{k}+j} + \sum_{i=\tilde{k}+\ell+1}^\tilde{k} r_i^{(j)} \vec{a}_i \quad \text{for $1\leq j \leq \ell$} This again reduces both communication and computation, but has the downside that we need to send more data in one packet. To put another way, the first messages with \vec{a}^{(1)} is not as useful to the recipient P' until it has also received the messages \vec{a}^{(2)}\ldots \vec{a}^{(\ell)} , in the following sense: if P' uses \vec{a}^{(1)} to construct outgoing messages itself towards some party P'' , it will contribute less to the overall propagation, because the relation vector might already be in the known span of P'' . Note here that P' using \vec{a}^{(1)} can only help propagation and will not actively hurt security, but the probability that the the vector is useful for P'' is lower than if P' had obtained and used some \vec{a}^{(1)} that was constructed without this optimization. Sparse Coefficient Sets Let us take a closer look again at the optimization we described above , where we used the fact that the sender knows that the recipient already knows some subspace. In this setting, the relation vector that P constructs has the form \vec{a} = (0,\ldots, 0, r_{\tilde{k}+1}, \ldots, r_{k}, *,\ldots, *), (For this discussion, it is simpler to explain if we do not normalize the first non-zero coefficient to 1 here). Observe that r_{\tilde{k}+1},\ldots, r_{k} are directly given by the randomness chosen by P . This allows P to use either small entries for those coefficients or choose them in a structured way. E.g., we might choose r_i = H(s,i,\tilde{k}) \text{ for }\tilde{k}+1 \leq i \leq k or we might choose r_i = s^{i-1-\tilde{k}} \text{ for }\tilde{k}+1 \leq i \leq k for random s from a sufficiently large appropriate space, similar to the optimization we described here and here . As above, for small coefficients, this means they are less costly to transmit. With structured randomness, we need to only transmit a (possibly short) seed s and \tilde{k} resp. \tilde{k}' . Note that, as opposed to the optimizations where we introduced the idea of small coefficients, this does not suffer from any kind of growth as we perform hops in the communication network; however, this optimization is limited by the rank of the known space of the sender. Roughly speaking, we save one coefficient per rank of the sender’s known space. We also note that (for the structured randomness case), it supersedes the optimizations from the sender knowing part of the recipients’ known space , since the latter optimization eliminates coefficients that are now determined by s ; it still saves computation, though. The security implications from the analysis from here and here carry over; in particular, we recommend the use of a simple polynomial over using a hash function. Abstract view A more abstract linear-algebra description of the above optimization is as follows: Suppose some party P has a known space A of dimension 1\leq k \leq N . In order to select a relation vector, it has to sample a point \vec{a} (or the 1-dimensional subspace spanned by it, if using projective coordinates) on this known space. Instead of choosing k coordinates and then sending a vector of length N , we may instead sample an (affine [2] , i.e. not neccessarily passing through \vec{0} ) subspace A^\circ of complementary dimension N-k and selecting \vec{a} as the intersection of A and A^\circ . This subspace A^\circ may be chosen in a structured way, using a (small) seed s . Now, instead of sending the relation vector \vec{a}=a_1,\ldots, a_N as part of the RLNC message, the sender can now instead send a description of A^\circ (via s ) and only N-k coordinates a_1,\ldots, a_{N-k} . From these data, the receiver can easily recover \vec{a} by solving a system of equations. (The concrete description above chooses the implicit A^\circ in such a way that solving this system of equations becomes trivial.) If we follow the definition of RLNC exactly, we would still choose a random single field element a\in\mathbb{F} and then send a along with a\cdot \vec{M} . This single field element a and multiplication by it is useless. ↩︎ Note that intersecting with an affine space of dimension N-k can be viewed (in a non-unique way) as first intersecting with a linear space of dimension N-k+1 , which generically results in a line of intersection (i.e. gives a projective \vec{a} ) and afterwards intersecting with an affine space of dimension N-1 to arbitrarily pick some canonical affine representation of that projective point. ↩︎ 1 post - 1 participant Read full topic