How to store a permutation compactly (2022)

[sacnoradhq]

Dan Boneh's intro cryptography course is excellent.[0] The closest to a Khan Academy "cryptography edition" one can find.

0. https://www.coursera.org/learn/crypto

PS: I must be old because I can't get past the neologism of "crypto" abused to mean "cryptocurrency" rather than "cryptography."

[remcob]

I started reading the ‘crypto’ in cryptocurrency as in cryptozoology. It makes more sense that way.

[shiftingleft]

> Chia replaces Nakamoto’s energy hungry proof-of-work consensus with an eco-friendly proof-of-space.

Don't be fooled, proof-of-space will eat up SSDs like no tomorrow and you're still hoarding HDDs for little gain.

Proofs of space prove that you're storing some useless data. Typically you use HDDs to store the useless data, but to prepare such a HDD you need an SSD. The setup process will perform so many writes that the SSD will be garbage very soon.

[throwaway8451]

"Proof of" is a euphemism for "waste of resources" in general.

[CrampusDestrus]

Why can't they use Folding@Home as proof of something?

[Dylan16807]

If you're doing it seriously you'll create plots in RAM and your SSDs will be fine.

Still a waste of space, but a gentler one.

[defrost]

Hmm,

Daniel Bernstein was only 24 when he bought the first of the Bernstein v. United States series to the courts.

https://en.wikipedia.org/wiki/Bernstein_v._United_States

Nice work there.

( connection being Verified fast formulas for control bits for permutation networks by djb

https://cr.yp.to/papers/controlbits-20200923.pdf )

[H8crilA]

If you're looking for a proof that the Benesh network can implement any permutation (of size 2^n):

https://eng.libretexts.org/Bookshelves/Computer_Science/Prog...

The proof is not super complicated, but it for sure isn't trivial.

[TontonNestor]

The author seems to think it's a simple exercise, but I agree with you, the proof that you linked, which uses graph coloring, and those in the Beneš or Waksman articles, which use Hall's theorem, are per se easy to understand, but rather hard to come up with.

[adamnemecek]

For anyone who cares, Beneš network was invented by Václav Beneš, son of the former president of Czechoslovakia Edvard Beneš https://en.wikipedia.org/wiki/Edvard_Bene%C5%A1

[throw_pm23]

Also known for the eponymous Beneš-decrees which collectively stripped ethnic minorities of certain basic rights, property, and citizenship after the war.

https://en.wikipedia.org/wiki/Bene%C5%A1_decrees

[pxeger1]

It's interesting that the author feels the need to justify why this would be useful in practice. I can imagine this could be useful in many contexts - and regardless, I'd be content for this to just be a purely academic exercise.

[foobarbecue]

I love that Chia doesn't have miners, it has "farmers."

[atesti]

Is there any source code or ready to use library?

[0xFFOOFF]

God you guys post the most boring things.