It turns out there is an attack on the BrainSTARK proof system [1]. The tutorial was extended to explain and fix the attack.
22 karma · joined May 2, 2012
A STARK [1] allows you to prove the correct execution of a computer program. The verifier can verify the resulting proof with less resources than it takes to naïvely re-execute the program.
Brainfuck [2] is a Turing-complete programming language that corresponds to a relatively straightforward instruction set architecture.
With this tutorial you will be able to prove and verify the correct execution of arbitrary Brainfuck programs.
[1]: https://aszepieniec.github.io/stark-anatomy/ [2]: https://en.wikipedia.org/wiki/Brainfuck
The first cipher to have this property was, I think, LowMC (2015). There have been a bunch more proposals since -- MiMC (2016), GMiMC (2019), Starkad and Poseidon (2019), Vision and Rescue (2019), and Rescue-Prime [1] (2020). I may be missing some; there was a rapid development in this field in the last years.
But in order to successfully make an argument along the lines of "more gun control will save lives", they must also cite statistics of the kind "how many lives are saved by guns". Obviously, if guns cause the death of 12000 people yearly and save the lives of 100000 people yearly, gun control is a bad idea. On the other hand, if they only save the lives of 100 people yearly, it might be a good idea after all. I have yet to see a single article on the internet citing such a number. Why is it so hard to find such a statistic?
The number of lives saved by guns (not counting police and military guns) is quite impossible to count. One might succeed in counting the number of cases where guns are used in self-defense, even though these cases usually go unnoticed. But how do you count the number of cases where the would-be perpetrator chooses not to commit the crime on account of a gun being present in defense of the would-be victim? Or doesn't even start to think about the crime?
This is a classic case of Bastiat's "that which is not seen". Because the statistic cannot be calculated, people do not take it into account. But they should if they want to make an effective argument for more gun control based on statistics.
Because the relevant statistics cannot be calculated, statistics should not be used in policy debates such as the one about gun control. Rather, let us reason about the unseen consequences of the actions of individuals as well as of the government. Without involving emotional arguments from either side.