QuadIron: an Open Source Library for Number Theoretic Transform-Based Erasure Codes

QuadIron is an open source C++11 library that focuses on newly applicable erasure code techniques using number theoretic transforms (FFT) on prime fields. As drive density continues to be driven higher in keeping with Moore’s Law, the price of storage continues to fall. This makes extra data copies cheaper. We can now imagine storing data reliably on relatively unreliable Internet servers by making extra copies. For example, generating and spreading thousand of fragments from a file cut in hundreds of fragments makes it possible to reconstruct the data while having only a tenth of the total data available e.g. 100 + 1000. QuadIron provides a framework to generate such erasure codes efficiently.

Reed-Solomon codes can be seen as polynomial operations that can be implemented by number theoretic transforms and accelerated by different fast Fourier transform algorithms according to characteristics of the fields. We present a library, QuadIron, which implements the state of the art of FFTs in prime and extension fields, and a set of optimizations to make them practical for a very large number of symbols.

Learning Objectives:
1. Learn about FFT-based codes (additive and multiplicative FFTs)
2. Use of FFT codes on decentralized storage (e.g. blockchain-based storage)