4 ms·

Improving the performance of fountain codes and applying them securely to peer 2 peer file sharing. A fountain code is an almost magical algorithm that can spl

Improving the performance of fountain codes and applying them securely to peer 2 peer file sharing. A fountain code is an almost magical algorithm that can split a file of size n up into a (practically) infinite stream of blocks of size b, such that collecting any n/b blocks out of the stream can reconstruct the file. Applied to p2p file sharing it effectively can eliminate rare pieces as well as the need to communicate which pieces people have. Related topic here is homomorphic hashing. Unless I find something better before September my master thesis will be on this topic.

sdinsn 6y ago
Similar to this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
- nightcracker 6y ago
  Shamir's Secret Sharing is roughly equivalent to Reed-Solomon erasure coding, using the same idea. The fountain codes I'm interested in are built from the perspective of inverting boolean matrices, and XOR'ing the right blocks together.
nemo1618 6y ago
Erasure codes are so cool. This was posted to HN a while back, did you see it? https://www.cberner.com/2019/03/30/raptorq-rfc6330-rust-optimization/ https://www.cberner.com/2019/03/30/raptorq-rfc6330-rust-opti...
- nightcracker 6y ago
  Yes, I've seen it. RaptorQ is a decent algorithm but I want to improve and simplify on it. It claims to be linear but it is not, it's actually O(n sqrt n) for large n and constant b.
krspykrm 6y ago
Good topic. Have you seen this high-performance Reed-Solomon implementation (1) or Wirehair (2)? Thoughts? 1) https://github.com/klauspost/reedsolomon https://github.com/klauspost/reedsolomon 2) https://github.com/catid/wirehair https://github.com/catid/wirehair
- nightcracker 6y ago
  No and yes. For fast Reed-Solomon I'm aware of this: https://github.com/Bulat-Ziganshin/FastECC https://github.com/Bulat-Ziganshin/FastECC. It's kind of amazing how far Reed-Solomon has come, thanks to the fast fourier transform. At the very large problem sizes it does slow down more and more though. If cleverly applied (e.g. layering erasure codes) you can make it go very far indeed. I don't like how hardware support is essentially necessary to make the larger field sizes necessary for bigger instances fast. Wirehair is very interesting, and I hope to study it well and describe it more formally as part of my Master's thesis. I'm not aware of any academical analysis of it. I did look into it enough to diagnose it suffers from the same O(n sqrt n) issue that RaptorQ does, again for very large instances. The issue lies in having to do Gaussian Elimination for a submatrix (to solve the inactivated columns) near the end of decoding, and this submatrix can be on the order of O(sqrt n). I'm interested in 'very large instances' because ideally I'd be able to create an efficient fountain code with block sizes on the order of the size of a UDP packet, disk page or QR code, which has some very interesting applications.

sdinsn 6y ago

Similar to this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

nightcracker 6y ago
Shamir's Secret Sharing is roughly equivalent to Reed-Solomon erasure coding, using the same idea. The fountain codes I'm interested in are built from the perspective of inverting boolean matrices, and XOR'ing the right blocks together.

nemo1618 6y ago

Erasure codes are so cool. This was posted to HN a while back, did you see it? https://www.cberner.com/2019/03/30/raptorq-rfc6330-rust-optimization/ https://www.cberner.com/2019/03/30/raptorq-rfc6330-rust-opti...

nightcracker 6y ago
Yes, I've seen it. RaptorQ is a decent algorithm but I want to improve and simplify on it. It claims to be linear but it is not, it's actually O(n sqrt n) for large n and constant b.

krspykrm 6y ago

Good topic. Have you seen this high-performance Reed-Solomon implementation (1) or Wirehair (2)? Thoughts? 1) https://github.com/klauspost/reedsolomon https://github.com/klauspost/reedsolomon 2) https://github.com/catid/wirehair https://github.com/catid/wirehair

nightcracker 6y ago
No and yes. For fast Reed-Solomon I'm aware of this: https://github.com/Bulat-Ziganshin/FastECC https://github.com/Bulat-Ziganshin/FastECC. It's kind of amazing how far Reed-Solomon has come, thanks to the fast fourier transform. At the very large problem sizes it does slow down more and more though. If cleverly applied (e.g. layering erasure codes) you can make it go very far indeed. I don't like how hardware support is essentially necessary to make the larger field sizes necessary for bigger instances fast. Wirehair is very interesting, and I hope to study it well and describe it more formally as part of my Master's thesis. I'm not aware of any academical analysis of it. I did look into it enough to diagnose it suffers from the same O(n sqrt n) issue that RaptorQ does, again for very large instances. The issue lies in having to do Gaussian Elimination for a submatrix (to solve the inactivated columns) near the end of decoding, and this submatrix can be on the order of O(sqrt n). I'm interested in 'very large instances' because ideally I'd be able to create an efficient fountain code with block sizes on the order of the size of a UDP packet, disk page or QR code, which has some very interesting applications.