Polar Coded Merkle Tree: Improved Detection of Data Availability Attacks in Blockchain Systems
share
Lights nodes are commonly used in blockchain systems to combat the storage burden. However, light nodes are known to be vulnerable to data availability (DA) attacks where they accept an invalid block with unavailable portions. Previous works have used LDPC codes with Merkle Trees to mitigate DA attacks. However, LDPC codes have issues in the finite length due to the NP-hardness of ascertaining the minimum stopping set size, and in the asymptotic regime due to probabilistic guarantees on code performance. We circumvent both issues by proposing the novel Polar Coded Merkle Tree (PCMT) which is a Merkle Tree built from the encoding graphs of polar codes. We provide a specialized polar code construction called Sampling-Efficient Freezing that efficiently calculates the minimum stopping set size, thus simplifying design. PCMT performs well in detecting DA attacks for large transaction block sizes.
READ FULL TEXT