# Reed-Solomn coding in Polkadot
We've found [our Reed-Solomn crate](https://github.com/darrenldl/reed-solomon-erasure) to be considerably slower than we'd like.
We'll use this over the short term since the crate was designed for our use case. This document outlines future work for more drastic improvements.
See also: https://codyplanteen.com/assets/rs/gf256_prim.pdf
## Arithmetic
Our [`simd-accel` feature](https://github.com/darrenldl/reed-solomon-erasure/blob/master/simd_c/reedsolomon.c) already implements $\mathbb{F}_{2^{16}}$ using [Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions](https://www.ssrc.ucsc.edu/media/pubs/c9a735170a7e1aa648b261ec6ad615e34af566db.pdf) by James Plank, Kevin Greenan, and Ethan Miller. It builds upon $\mathbb{F}_{2^4}$ because SIMD prefers 16-by-16 tables.
We should check if this code actually produces reasonable assembler, which maybe rustc churn breaks. Syed wants to try plugging in the gf-complete code directly.
We could experement with $\mathbb{F}_{2^{12}}$, but this looks like considerable work for minimal gain.
### Formal derivatives
[*An Efficient (n,k) Information Dispersal Algorithm based on Fermat Number Transforms*](https://www.citi.sinica.edu.tw/papers/whc/3450-F.pdf) by Sian-Jheng Lin and Wei-Ho Chung provides an impressively fast Reed-Solomn encoding algorithm over Fermat fields. You'll find a brief explanation of its formal deriviative trick in [FastECC's readme](https://github.com/Bulat-Ziganshin/FastECC#faster).
[*Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes*](https://arxiv.org/abs/1404.3458) by Lin, Han and Chung then provides a related design suitable for binary fields and [their FFTs](https://vitalik.ca/general/2019/05/12/fft.html), for which they provide a [research implementation](https://github.com/SianJhengLin/Fast-algorithms-of-Reed-Solomon-erasure-codes) over $\mathbb{F}_{2^8}$.
ALSO https://www.citi.sinica.edu.tw/papers/whc/5524-F.pdf
Among the Reed-Solomn libraries over $\mathbb{F}_{2^{16}}$ we've glanced over the fastest appears to be [leopard](https://github.com/catid/leopard) by Chris Taylor, which builds upon the second paper's research implementation by adding optimized SIMD instructions. We found leopard only implements a high rate code, meaning it [requires fewer parity shards than data shards](https://github.com/catid/leopard/issues/16). We require a low rate code for Polkadot, which makes direct deployment impossible (see also [leopard#14](https://github.com/catid/leopard/issues/14) and [wirehair#16](https://github.com/catid/wirehair/issues/16)).
We also need to understand our code, and so should our auditers, but leopard consists of hard to read C-assembler translated directly from the second paper with bespoke unexplained optimizations.
In fact, there are two related papers by the same authors that better describe the [high rate code](https://github.com/catid/leopard/blob/master/docs/HighRateDecoder.pdf) roughly corresponding to leopard, and also describe the [low rate code](https://github.com/catid/leopard/blob/master/docs/LowRateDecoder.pdf) corresponding more to what Polkadot requires. There is a non-functional `encodeL` function resembling Algorithm 1 from the [Lin, Han and Chung paper](https://arxiv.org/abs/1404.3458), but not this low rate code paper.
<img style="float: right;" src="https://www.thirtythreeforty.net/posts/2020/05/hacking-reolink-cameras-for-fun-and-profit/riir.png" alt="Rewrite it in Rust" width="200" />
We should understand the [low rate code paper](https://github.com/catid/leopard/blob/master/docs/LowRateDecoder.pdf) and the he [Lin, Han and Chung paper](https://arxiv.org/abs/1404.3458) along with any dependencies, probably correct the [research implementation](https://github.com/SianJhengLin/Fast-algorithms-of-Reed-Solomon-erasure-codes), and then rewrite it readably in Rust. Initially we'll optimize more for readability, without using SIMD, but perhaps exploring the leopard source for optimization ideas.
[*Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes*](https://arxiv.org/abs/1404.3458)
We'd then later do a SIMD implementation similar to leopard, but compatable with our readable implementaiton.
### Frobenius Additive FFT
As discussed in [leopard#5](https://github.com/catid/leopard/issues/5), there is a faster Frobenius FFT described in [*Frobenius Additive Fast Fourier Transform*](https://arxiv.org/pdf/1802.03932.pdf) by Liu, Chen, Chen, Kuo, and Yang, along with a [Python implemntation](https://github.com/fast-crypto-lab/Frobenius_AFFT).
and previously in [*The Frobenius FFT*](http://www.texmacs.org/joris/ffft/ffft.pdf) by Joris van der Hoevena and Robin Larrieu.
In fact, the resarch code and leopard already implement [Additive Fast Fourier Transforms over Finite Fields](http://www.math.clemson.edu/~sgao/papers/GM10.pdf) by Shuhong Gao and Todd Mateer, so one question remains about how much improvement this yields.
We should thus also understand this Frobenius Additive FFT and further optimize our implementation since the Chris Tayler envisions a 5x speed up.
###
https://gitlab.com/eddyb/medimgrs/

Academia vs industry research: Advising and support of Parity teams like parachains, staking, etc. and W3F teams like spec and grants. In progress.. Redesigns of staking & slashing (Kian) Time disputes Avoid tragedies of the commons by adjusting slashish Add billing for time overruns, untangling delays from security

2/5/2023It makes more sense if you’ve read The Extended Phenotype by Richard Dawkins, which Dawkins considers to be his greatest work. “Procession" Evolution "A cradle Earth, horizons unseen New world in thirst, for the arcane We are, singers of the gone We remember, as along came life”

9/7/2022Validator rewards in Polkadot/Kusama Idealy almost all rewards in Kusama/Polkadot would come from work done securing parachains, including work supporting XCMP. We should continue some rewards for relay chain block production and finality of course, but their levels shall be greatly reduced. We have several plausible archetectures for rewards along two axes, rewarding only tranche zero vs all tranches, and rewarding deterministically vs probabaistically. Reward all tranches for all candidates We'd rerun the approvals loop on-chain after approvals happened off-chain, which avoids requiring good randomness. We worry this looks heavy, so we'd likely do this as a system parachain, which adds complexity. Reward all tranches but only for random candidates We'd likely never do this since its our most complex option, do to both sampling code and running the full approvals loop, but it provides a mechanism for the relay chain to non-zero tranches.

12/22/2021Polkadot should scale linearly in the number of validators, well once parachains work, including direct UDP connections between validators. We impove security if we diversify our validator operator pool too. We therfore want W3F to invite fresh-but-good validator operators into the communite and nominate their nodes, but this risks W3F being slashed. It's impossible to mitigate slashing risk while staking unknown people (see slashing section below). We could vet new validators whom we stake, and we should do some of this, but vetting becomes time intensive. Instead we should vet validator operators using their past public activity on peer-to-peer networks, which for diversity should ideally lie not be crypto-currency networks. There are three enormous peer-to-peer networks that fit this critertia, Tor, I2P, and Bittorrent. We'd presuably start new operators on a test network, or Kusama, and then graduate them to Kusama and Polkadot. Tor Tor provides a near perfect resource here. Tor actively avoids node hosting infrastructure homogenaity, ala EC2, etc., so Tor operators bring hosting diversity and thus security. Tor spends considerable effort teaching operators about basic operational security for peer-to-peer nodes. Tor even educates operators about interactions with law enforcement. Also, Tor operators can be solicited via Tor's mailing lists.

2/16/2021
Published on ** HackMD**