How to store a permutation compactly (2022)

by velmu • 3 years ago

57 36 3 years ago

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_pm234• 3 years ago

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

xigoi3• 3 years ago

Those are from Edvard, not Václav.

adamnemecek3• 3 years ago

Remind me which ethnicities were those?

Also what was the relationship between members of those ethnicities and Nazis?

Here's something to jog your memory

https://en.wikipedia.org/wiki/1938_German_parliamentary_elec...

defrost• 3 years ago

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 )

pxeger1• 3 years ago

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.

H8crilA3• 3 years ago

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• 3 years ago

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.

shiftingleft• 3 years ago

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• 3 years ago

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

H8crilA3• 3 years ago

Only in cryptocurrency, i.e. in the cargo cult of finance.

In real world finance a common stock is proof of making a useful investment at some point in the past, when the stock certificate was issued in return for capital. Same with other tradeable and non-tradeable assets.

Dylan168073• 3 years ago

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.

CrampusDestrus2• 3 years ago

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

div72• 3 years ago

For something to be used in PoW, it needs to be both hard to solve and easy to verify. Protein folding checks the first box but not the second. As an example, prime number calculations check the both boxes and there's Primecoin which bases its proof algorithm on prime chains.

This only applies if you prefer to be trustless though. If you are willing shed a bit, you can trust Folding@Home's scoreboard data (and whoever supplies the data to you) to use it as a pseudo-"PoW" and run a proper proof algorithm beneath. (which is also done by a number of coins like Banano, Curecoin, Gridcoin. You can see their people on the leaderboard with weird names like x_ALL_x, x_GRC_x or just bunch of non-sensical alphanumeric characters.)

sacnoradhq• 3 years ago

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• 3 years ago

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

joe__f• 3 years ago

That's like, the study of concealed animals?

foobarbecue• 3 years ago

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

0xFFOOFF• 3 years ago

God you guys post the most boring things.

atesti• 3 years ago

Is there any source code or ready to use library?

How to store a permutation compactly (2022)

Related Stories