Assessing the Efficiency of Polynomial Commitment Schemes in Erasure Code-Based Data Distribution
摘要
In distributed storage systems, reliability and availability can be largely enhanced by the use of erasure codes. With such codes, data is split into k source shards, then encoded into n output shards stored in different nodes. To retrieve the full data, at least k shards must be downloaded before starting the decoding process. Nevertheless, if a shard is modified, either intentionally or accidentally, the decoding process will generate incorrect data. To allow the independent verification of each shard without having to decode the entire dataset, the encoder can add cryptographic commitments, and possibly an additional proof, to each output shard to certify its integrity. In this paper, we explore several commitment-based schemes: \({\textbf {KZG}}^+\) , an extension of [2, 9]; aPlonK-PC, the commitment part of [1]; and Semi-AVID-PC, the commitment part of [12]. These schemes apply polynomial evaluations similar to the Reed-Solomon coding technique. However, commitment-based schemes can lead to significant computational overhead and increased storage requirements. We provide a comparative analysis to help designers of distributed storage systems in choosing the most suitable proof method and associated elliptic curve, taking into account factors like data size, information dispersal, and the frequency of validity checks relative to proof creation. We find that Semi-AVID-PC is usually the best choice on all the metrics we measured, using both x86_64 and ARMv8 architectures. In scenarios where the input data sizes and verification frequencies are substantial, aPlonK-PC proves to be as efficient.