The linear algebra book by E. Nering does the material over finite fields.
As I recall, Nering was an E. Artin student at Princeton.
Binius: Highly efficient proofs over binary fields
11–20 of 25 posts
Re: Binius: Highly efficient proofs over binary fields
#12> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_r...
That's a square root in real arithmetic. In finite fields you don't operate over the real numbers, but the numbers within the field.
An example of a finite field is the numbers modulo a prime, like p = 2^127 - 1.
Now, please find the square root of x = 113338949109682836687814795709948365013 mod 2^127 - 1. That is, find some number y such that y * y mod (2^127 - 1) = x.
Re: Binius: Highly efficient proofs over binary fields
#13I 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.
Re: Binius: Highly efficient proofs over binary fields
#14I 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.
Big fan of this series of lectures: https://youtu.be/h-94UhJLeck?si=0bEeB9VjmwRXIWTB.
Re: Binius: Highly efficient proofs over binary fields
#15> 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 ran…
My understanding is that you do your math over some field F.
But then when you choose a random point to test your polynomial, you randomly select from G = F[5^1/3], an extension of the original field. And test your polynomial using arithmetic in that larger field.
The increased entropy happens when you select at random from the extended field — there’s more elements in G than in F, so an attacker has a lower chance of guessing your random value.
Re: Binius: Highly efficient proofs over binary fields
#16> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_r...
That's a square root in real arithmetic. In finite fields you don't operate over the real numbers, but the numbers within the field. An example of a finite field is the numbers modulo a prime, like p = 2^127 - 1. Now, please find the square root of x = 113338949109682836687814795709948365013 mod 2^127 - 1. That is, find some number y such that y * y mod (2^127 - 1) = x.
Even this is not in any way related to the asymptotic time bounds discussed in the article.
Re: Binius: Highly efficient proofs over binary fields
#17I 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.
I recommend Alan Szepieniec's series of posts for a clear, direct mathematical description of how they work - https://aszepieniec.github.io/stark-anatomy/
Vitalik also has this more informal series of explainer posts - https://vitalik.eth.limo/general/2017/11/09/starks_part_1.ht...
Re: Binius: Highly efficient proofs over binary fields
#18Earlier quoted context omitted.
That's a square root in real arithmetic. In finite fields you don't operate over the real numbers, but the numbers within the field. An example of a finite field is the numbers modulo a prime, like p = 2^127 - 1. Now, please find the square root of x = 113338949109682836687814795709948365013 mod 2^127 - 1. That is, find some number y such that y * y mod (2^127 - 1) = x.
Even this is not in any way related to the asymptotic time bounds discussed in the article.
Right - in case it's not clear to all, the square root metric Vitalik mentions is about measuring both proof size and verifier complexity. Neither the prover nor the verifier is doing any square root computations.
Re: Binius: Highly efficient proofs over binary fields
#19> 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 ran…
My understanding is that you do your math over some field F. But then when you choose a random point to test your polynomial, you randomly select from G = F[5^1/3], an extension of the original field. And test your polynomial using arithmetic in that larger field. The increased entropy happens when you select at random from the extended field — there’s more elements in G than in F, so an attacker has a lower chance o…
Exactly - we sample uniformly from an extension field, so entropy is proportional to the extension field size. The base field is almost irrelevant from a security perspective, since things like the Schwartz-Zippel lemma just care about the size of the field we sample from, even if the polynomial in question is (also) a polynomial over some smaller subfield.
Re: Binius: Highly efficient proofs over binary fields
#20> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_r...
That's a square root in real arithmetic. In finite fields you don't operate over the real numbers, but the numbers within the field. An example of a finite field is the numbers modulo a prime, like p = 2^127 - 1. Now, please find the square root of x = 113338949109682836687814795709948365013 mod 2^127 - 1. That is, find some number y such that y * y mod (2^127 - 1) = x.
What is "expensive" in this context? Wolfram Alpha can solve it in a fraction of a second. https://www.wolframalpha.com/input?i=solve+y%5E2+mod+%282%5E...
>>> x = 113338949109682836687814795709948365013
>>> n = 1
>>> y = 80490928931346377909947075573303248723 + 170141183460469231731687303715884105727 * n
>>> y**2 % (2**127 - 1) == x
True