News for hackers. Stuff that matters.
Re:Ask HN: What weird or hard problems are you trying to solve? by nightcracker on Sunday July 05, 2020 @07:27PM (#23743094)
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.

Re:Ask HN: What weird or hard problems are you trying to solve? by krspykrm on Monday July 06, 2020 @07:24AM (#23746718)
Good topic. Have you seen this high-performance Reed-Solomon implementation (1) or Wirehair (2)? Thoughts?

1) https://github.com/klauspost/reedsolomon

2) https://github.com/catid/wirehair

Re:Ask HN: What weird or hard problems are you trying to solve? by nightcracker on Monday July 06, 2020 @07:54AM (#23746931)
No and yes.

For fast Reed-Solomon I'm aware of this: 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.

Re:Ask HN: What weird or hard problems are you trying to solve? by nemo1618 on Monday July 06, 2020 @02:46AM (#23745325)
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-opti...
Re:Ask HN: What weird or hard problems are you trying to solve? by nightcracker on Monday July 06, 2020 @03:21AM (#23745510)
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.
Re:Ask HN: What weird or hard problems are you trying to solve? by sdinsn on Sunday July 05, 2020 @09:37PM (#23743856)
Re:Ask HN: What weird or hard problems are you trying to solve? by nightcracker on Monday July 06, 2020 @07:50AM (#23746894)
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.