from Hacker News

Binius: Highly efficient proofs over binary fields

by fbrusch on 5/11/24, 6:55 AM with 20 comments

  • by Retr0id on 5/12/24, 10:23 AM

    I don't quite have the background to read this article as-is, could anyone recommend an introduction to STARKs? My google search results are full of cryptocurrency blogspam.

  • by graycat on 5/12/24, 10:04 AM

    The linear algebra book by E. Nering does the material over finite fields.

    As I recall, Nering was an E. Artin student at Princeton.

  • by DoctorOetker on 5/12/24, 9:20 AM

    > But this also means that the coordinate must be sampled from a set large enough that the attacker cannot guess it by random chance. If the modulus is near ( 2 ^ 256 ), this is clearly the case. But with a modulus of ( 2 ^ 64 - 2 ^ 32 + 1 ), we're not quite there, and if we drop to ( 2 ^ 31 - 1 ), it's definitely not the case. Trying to fake a proof two billion times until one gets lucky is absolutely within the range of an attacker's capabilities.

    > To stop this, we sample r from an extension field. For example, you can define y where y ^ 3 = 5, and take combinations of 1, y and y ^ 2 .

    This reads like trying to increase entropy without adding entropy. Given the analogy of bruteforcing a low entropy preimage in a hash, Concatenating the secret preimage with itself, or adding capitalization on the second occurence etc. does not increase entropy, its just a constant factor in computational complexity which both attacker and defender suffer.

    I am probably misunderstanding what's written, but I suspect its due to the unclear exposition...

  • by photonthug on 5/12/24, 4:42 AM

    the summary convinced me I don’t have the background to read the article, but that is easily the best diagram I’ve seen all week.

  • by uptownfunk on 5/12/24, 5:20 AM

    Wow great article, I like the recaps

  • by downvotetruth on 5/12/24, 4:57 AM