2020/10/14 by Debarnab Mitra, Mitra, Debarnab, Lev Tauz +3
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Cryptography and Security (cs.CR) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2010.07363
openalex publication_date 2020/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In certain blockchain systems, light nodes are clients that download only a\nsmall portion of the block. Light nodes are vulnerable to data availability\n(DA) attacks where a malicious node hides an invalid portion of the block from\nthe light nodes. Recently, a technique based on erasure codes called Coded\nMerkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect\na DA attack with high probability. The CMT is constructed using LDPC codes for\nfast decoding but can fail to detect a DA attack if a malicious node hides a\nsmall stopping set of the code. To combat this, Yu et al. used well-studied\ntechniques to design random LDPC codes with high minimum stopping set size.\nAlthough effective, these codes are not necessarily optimal for this\napplication. In this paper, we demonstrate a more specialized LDPC code design\nto improve the security against DA attacks. We achieve this goal by providing a\ndeterministic LDPC code construction that focuses on concentrating stopping\nsets to a small group of variable nodes rather than only eliminating stopping\nsets. We design these codes by modifying the Progressive Edge Growth algorithm\ninto a technique called the entropy-constrained PEG (EC-PEG) algorithm. This\nnew method demonstrates a higher probability of detecting DA attacks and allows\nfor good codes at short lengths.\n