Decentralized Sparse Matrix Multiplication Under Byzantine Attacks

Distributed computations, such as distributed matrix multiplication, can be vulnerable to significant security issues, notably Byzantine attacks. These attacks may target either worker nodes or servers, potentially leading to faulty results that can significantly degrade the overall performance. Therefore, detecting Byzantine attackers and mitigating their effects are crucial in such systems. Motivated by the goal of establishing a secure decentralized matrix-multiplication system, we first introduce a verification method named Common Tag, inspired by the well-known Freivalds’ algorithm, able to verify the multiplication results independent of their associated input matrices. Then, we propose two schemes for sparse matrix multiplication where a group of nodes collaboratively performs a computation task over a logical ring. We consider a subset of Byzantine nodes in the system that may arbitrarily corrupt either their result or any other result passing through them. In Scheme I considering the highly sparse nature of input matrices, we assume that each node has sufficient capacity to store the entire input matrices, and the nodes forward the read-only versions of their computed blocks so that other nodes cannot corrupt them. In Scheme II, we relax the above assumptions, firstly, by considering a limited storage capacity for each node. Secondly, we introduce more powerful adversaries capable of corrupting other nodes’ results by relaxing the read-only assumption. The results demonstrate the feasibility of both schemes and show a significant improvement in terms of distortion over the case where no detection happens. The results also provide a trade-off between the computational complexity required at each node and the reconstruction distortion in both schemes.