5 ms·

In case your code theory is a bit rusty, practically this means that recovering from transmission errors (bitflips, lost packets) will be faster if this encoder

by cynusx 4y ago

In case your code theory is a bit rusty, practically this means that recovering from transmission errors (bitflips, lost packets) will be faster if this encoder is used. It will lower CPU requirements on routers and network infrastructure if adopted and potentially your torrent download may be validated faster. Nothing impacting blockchains, which was my first thought.

adrian_b 4y ago
The author explains in the README that this specific algorithm is not suited for some of the applications of Reed-Solomon codes, e.g. hardware RAID controllers or communication channels. However, it is appropriate for protecting archive files against corruption, by adding redundancy that enables the recovery of the complete file when any part of it is lost, as long as the lost parts do not exceed the size of the extra redundant data. I happen to add such Reed-Solomon redundancy to all my backup/archive files (using "PAR2"). For multi-terabyte archived data, the Reed-Solomon computation can be quite time-consuming, second only to compression, so a faster algorithm can be useful.
lijogdfljk 4y ago
Yea. On the note of Blockchains, i have been long fascinated by immutable storage engines. Blockchain being just one implementation in the broader landscape. I've implemented several of them... and with that said, i often wanted to add Reed Solomon simply because i found it fascinating. Truly an ingenious "trick". Though i never got past the idea phase, as it felt i was just double encoding everything and if bits were to flip then my storage mechanisms (HDD/S3/etc) would be the one seeing the flip and fixing it. I figured my software was never going to see bitflips to make this type of feature useful. I'd be curious if any blockchains/immutable storage/etc actually use this type of error recovery. Ie if the layer _above_ network and storage actually benefit from error recovery. Since i often expect both network and storage themselves to bake error recovery in.. /shrug
- jlokier 4y ago
  In blockchains, aside from the usual reasons you would store data with error-detection and correction (ordinary data resiliance in storage and transmission), Reed-Solomon is used for: - Data Availability Proofs, which allows a node to prove it has (or had) access to all the data in a block by transmitting only a tiny subset of that data, which is derived from the RS code and a Merkle hash of the data. - Execution Proofs, which allows a node to prove the result of an arbitrary and arbitrarily long program executed on data without the recipient having to redo the execution, by transmitting only a tiny subset of the RS code and higher-order codes of the computation's state trace. Data Availablity Proofs are used with cryptoeconomic incentive structures to ensure that a complete set of data is being stored and periodically checked, and not just the small amount of data that is popular at any given moment. So, like BitTorrent except more reliable because it uses more than just voluntary cooperation; it incentivises keeping whole repositories of data instead of just the popular files within them at any given moment. Execution Proofs are used with Ethereum-like blockchains to pass around compact summaries of state updates from running code in smart contracts, without all the nodes needing to store or fetch the full state of each contract's memory, or even needing to perform the execution locally to verify it. Smaller Execution Proofs are used in simpler blockchains for the state updates associated with balance transactions. The data proofs use Reed-Solomon on reasonable sized data blocks, and the trend is towards multidimensional RS, as with other applications. The second uses Reed-Solomon on much larger vectors than 2^20 points, for long computations, and requires the FFT approach for reasonable performance. However there is still a reasonable upper limit where it makes sense to split the trace up, and for that it's possible to make an Execution Proof of a program which verifies another Execution Proof.

by cynusx 4y ago

adrian_b 4y ago

The author explains in the README that this specific algorithm is not suited for some of the applications of Reed-Solomon codes, e.g. hardware RAID controllers or communication channels. However, it is appropriate for protecting archive files against corruption, by adding redundancy that enables the recovery of the complete file when any part of it is lost, as long as the lost parts do not exceed the size of the extra redundant data. I happen to add such Reed-Solomon redundancy to all my backup/archive files (using "PAR2"). For multi-terabyte archived data, the Reed-Solomon computation can be quite time-consuming, second only to compression, so a faster algorithm can be useful.

lijogdfljk 4y ago

Yea. On the note of Blockchains, i have been long fascinated by immutable storage engines. Blockchain being just one implementation in the broader landscape. I've implemented several of them... and with that said, i often wanted to add Reed Solomon simply because i found it fascinating. Truly an ingenious "trick". Though i never got past the idea phase, as it felt i was just double encoding everything and if bits were to flip then my storage mechanisms (HDD/S3/etc) would be the one seeing the flip and fixing it. I figured my software was never going to see bitflips to make this type of feature useful. I'd be curious if any blockchains/immutable storage/etc actually use this type of error recovery. Ie if the layer _above_ network and storage actually benefit from error recovery. Since i often expect both network and storage themselves to bake error recovery in.. /shrug

jlokier 4y ago
In blockchains, aside from the usual reasons you would store data with error-detection and correction (ordinary data resiliance in storage and transmission), Reed-Solomon is used for: - Data Availability Proofs, which allows a node to prove it has (or had) access to all the data in a block by transmitting only a tiny subset of that data, which is derived from the RS code and a Merkle hash of the data. - Execution Proofs, which allows a node to prove the result of an arbitrary and arbitrarily long program executed on data without the recipient having to redo the execution, by transmitting only a tiny subset of the RS code and higher-order codes of the computation's state trace. Data Availablity Proofs are used with cryptoeconomic incentive structures to ensure that a complete set of data is being stored and periodically checked, and not just the small amount of data that is popular at any given moment. So, like BitTorrent except more reliable because it uses more than just voluntary cooperation; it incentivises keeping whole repositories of data instead of just the popular files within them at any given moment. Execution Proofs are used with Ethereum-like blockchains to pass around compact summaries of state updates from running code in smart contracts, without all the nodes needing to store or fetch the full state of each contract's memory, or even needing to perform the execution locally to verify it. Smaller Execution Proofs are used in simpler blockchains for the state updates associated with balance transactions. The data proofs use Reed-Solomon on reasonable sized data blocks, and the trend is towards multidimensional RS, as with other applications. The second uses Reed-Solomon on much larger vectors than 2^20 points, for long computations, and requires the FFT approach for reasonable performance. However there is still a reasonable upper limit where it makes sense to split the trace up, and for that it's possible to make an Execution Proof of a program which verifies another Execution Proof.