How to store a permutation compactly (2022)(hackmd.io)
hackmd.io
How to store a permutation compactly (2022)
https://hackmd.io/@dabo/rkP8Pcf9t
37 comments
> 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.
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.
"Proof of" is a euphemism for "waste of resources" in general.
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.
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.
But this isn't proof, that financial stock certificate. It's actually fiat: the clearinghouse or the national registry says who owns what and the court can change it.
The crypto version of proof is closer to a bearer bond or a bar of gold: whoever has possession has possession.
The crypto version of proof is closer to a bearer bond or a bar of gold: whoever has possession has possession.
Yes, you pointed out why the analogy isn't perfect, all the while missing the point entirely.
In cargo cults it would be like complaining that the control tower made of wood has the wrong number of windows, all the while missing the fact that you don't have any aircraft.
In cargo cults it would be like complaining that the control tower made of wood has the wrong number of windows, all the while missing the fact that you don't have any aircraft.
No, the point I'm making is that there are conflicting definitions of proof here. The same word means different things.
If two crypto bros go to court, the one who refuses to follow the judges ruling gets to stay in jail. How does crypto help with that? Possession is 9/10ths, but the state is 100%.
Why can't they use Folding@Home as proof of something?
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.)
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.)
Well, I used F@H as an example. Are there truly no PoW algorithms that satisfy both conditions and actually represent some useful IRL result?
It's a pretty narrow set of calculations that are very expensive but easy to verify. You have to be looking for needles in a haystack, and the haystack has to be gargantuan but not involve all that much data transfer.
So unless you feel that it's useful to find prime numbers, good luck.
So unless you feel that it's useful to find prime numbers, good luck.
The more "useful" you PoW algorithm is, the cheaper 51% attacks on your chain will be. To be maximally secure, a PoW algorithm should only generate useless data.
Do you know PoW could work with backup data? It would be great if people could have a little backup space for the price of some compute, instead of cash or "free" backup.
Are you looking for Sia and Storj?
I would say Filecoin but very strange things are going on with that coin and I can't wrap my head around how you're supposed to actually store things.
I would say Filecoin but very strange things are going on with that coin and I can't wrap my head around how you're supposed to actually store things.
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.
Still a waste of space, but a gentler one.
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 )
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 )
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.
https://eng.libretexts.org/Bookshelves/Computer_Science/Prog...
The proof is not super complicated, but it for sure isn't trivial.
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.
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
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
https://en.wikipedia.org/wiki/Bene%C5%A1_decrees
Those are from Edvard, not Václav.
Sure, the GP mentioned Edvard.
The word “also” in your comment implies that you're talking about the subject of the parent comment, which is Václav.
I meant it as continuing the sentence about Edvard, and in any case presidents are more likely to pass decrees than computer scientists. But anyway I see I stepped on a nerve with the comment.
> But anyway I see I stepped on a nerve with the comment.
What? I just wanted to clarify your comment since it seemed to say the wrong thing.
What? I just wanted to clarify your comment since it seemed to say the wrong thing.
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...
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...
Whichever they were, the concept of "collective sin" applied to an ethnic group is atrocious.
Dude, 99 percent support for Hitler.
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.
[deleted]
I love that Chia doesn't have miners, it has "farmers."
Is there any source code or ready to use library?
God you guys post the most boring things.
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."