# Grid signature distribution in BEAM Kamil Salakhiev 𝕏 [@kamil_abiy](http://x.com/kamil_abiy) <i class="bi bi-globe"></i> qdrvm.io --- <style> .two-column-layout { column-count: 2; /* Set column number */ column-gap: 20px; max-width: 100%; overflow: hidden; } /* Media query for mobile devices */ @media (max-width: 768px) { .two-column-layout { column-count: 1; /* Switch to single column on small screens */ column-gap: 0; /* Optional: Set gap to 0 for single column */ } } .markdown-body, .ui-infobar { max-width: unset !important; } .two-column-layout ul, .two-column-layout ol { margin: 0; padding-left: 20px; } .two-column-layout strong { font-weight: bold; } .two-column-layout em { font-style: italic; } .two-column-layout h1, .two-column-layout h2, .two-column-layout h3, .two-column-layout h4, .two-column-layout h5, .two-column-layout h6 { margin-top: 0; } </style> ## Assumptions 1. $n=16384$ $(2^{14})$ validators 2. Each validator generates a 1.5KB signature 3. In addition to the validators there are untrusted, altruistic aggregators (provers) that generate SNARK to prove the signatures are valid 4. The addresses of the validators are known and could be matched with their signing public keys --- ## Goal * Design a network structure that allows $\frac{2}{3}n + 1$ of signatures to be aggregated as quickly as possible --- ## 2d grid <div class="two-column-layout">  ### - Each validator uses the common source of randomness to form *grid view* - Each <span style="color:red">validator</span> maintains $\sqrt{n}$ connections with <span style="color:blue">column neighbors</span> and $\sqrt{n}$ connections with <span style="color:green">row neighbors</span> </div> --- ## Distribution pattern  --- ## Benefits * Distance between any two validators is at most 2 hops * In gossipsub distance is $\approx 5.41$ for $N=2^{14},k=6$ * $O(n)$ signature messages in the validators network per signature * \+ additional $O(n^{\frac{3}{2}})$ `IHAVE` messages * Each validator can receive the same message from at most 2 peers <!-- ## Grid communication complexity (per signature) * Step 3. The remaining $n-2\sqrt{n}$ validators propagate `IHAVE` messages in orthogonal direction * $(n-2\sqrt{n})\times \sqrt{n}\approx O(n^{\frac{3}{2}})$ messages containing `IHAVE` * Total 2064384 `IHAVE` messages (31.5MB) for $n=2^{14}=16384$ validators --> <!-- --- ## Grid traffic consumption (per validator) * Each validator would propagate a signature message from each of its row/column neighbor to each of column/row neighbor * resulting into $2\sqrt{n}\times \sqrt{n}$ signature messages * Each validator would propagate `IHAVE` message to each of its non-neighbor validator * resulting into $(n-2\sqrt{n})\times 2\sqrt{n}$ `IHAVE` messages * Total outbound bandwidth required per validator (assuming 4-seconds slot, 3 seconds to vote, 16384 validators): 651264 bytes / 3 seconds = 1.65Mbps bandwidth is required --> <!-- --- ## Gossipsub communication complexity (per signature) > Note. Assuming gossipsub 1.1 without IDONTWANT 1. Each peer will propagate a new message to $k$ random peers 2. $N \gg n$ total nodes 3. Total messages in the network per signature: $O(N\times n \times k)$: * 98304 signature messages (144MB) for $N=16384,k=6$ * 6000000 signature messages (8789MB) for $N=1000000,k=6$ --> <!-- --- ## Gossipsub traffic consumption (per peer) 1. Each peer would propagate each signature message to $k$ random peers 2. $n$ total peers producing a signature 3. So each peer would distribute $n\times k$ signature messages * 98304 signature messages (144MB), 3 seconds to vote: 384MBps bandwidth is required --> <!-- --- ## Impact of malicious peers in grid Step 3. of grid distribution is needed to prevent eclipse attack scenario when two malicious peers can eclipse one validator from receiving a signature message. Let's break down such scenario. ### Two malicious nodes example Suppose the grid is 4x4. * Let's say s is at (2,2). * Its row neighbors are (2,1), (2,3), (2,4). * Column neighbors are (1,2), (3,2), (4,2). * If (2,1) and (1,2) are both malicious. Then: * Step 1: s sends to row neighbors (2,1), (2,3), (2,4) and column neighbors (1,2), (3,2), (4,2). * In step 2, malicious nodes (2,1) and (1,2) do not forward. * The other row neighbors (2,3), (2,4) forward to their column neighbors (1,3), (3,3), (4,3), (1,4), (3,4), (4,4) * The other column neighbors (3,2), (4,2) forward to their row neighbors: (3,1), (3,3), (3,4), (4,1), (4,3), (4,4) * Only (1,1) is not getting the signature message after step 2. * However, it receives `IHAVE` message from other non-malicious row and column neighbors and therefore requests the missing signature message from one of these nodes ### m malicious nodes * From the previous example we observed that two malicious nodes can eclipse one validator, if malicious nodes were positioned in the same row and column of validator $s$ producing the original signature message. * As result eclipsed validator would need to perform a signature request after receiving `IHAVE` In a worst case for $m$ malicious nodes that do not propagate signatures and are optimally distributed between rows and columns to maximize the number of blocked messages there would be $\approx\frac{m^2}{2}$ eclipsed validators, that would need to fetch the signature message after receiving `IHAVE`, i.e. causing additional $\frac{m^2}{2}$ messages * However, this also means that these malicious nodes would not propagate $\frac{m^2}{2}$ signature messages, therefore, total number of signature message remains the same * The latency in such scenario for nodes eclipsed during step 2, would be increased by `IHAVE` message communication + 1 signature message sent from honest validator --> --- ## Signature aggregation * Aggregators cannot join grid lattice * Aggregating nodes are untrusted entities with no stake * Aggregators may join or leave the network dynamically --- ## Challenges with a single grid - All validators receive all signatures - No benefit for aggregators - Network traffic congestion - Each validator will receive $O(n)$ signatures within a single slot - $\approx 128Mbps$ incoming bandwidth is required (assuming 3 seconds to distribute signatures) --- ## Signature aggregation with grid  --- ## Conclusion - Grid is effective protocol for fast message distribution among validators - Grid could be helpful in accelerating of signatures batch collection --- ## Thanks! Link to slides