[HN Gopher] Binius: Highly efficient proofs over binary fields
___________________________________________________________________
Binius: Highly efficient proofs over binary fields
Author : fbrusch
Score : 82 points
Date : 2024-05-11 06:55 UTC (1 days ago)
(HTM) web link (vitalik.eth.link)
(TXT) w3m dump (vitalik.eth.link)
| photonthug wrote:
| 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.
| downvotetruth wrote:
| > Square root is expensive
|
| https://reddit.com/r/math/comments/tc7lur/computing_square_r...
| eapriv wrote:
| This is not in any way related to the asymptotic time bounds
| discussed in the article.
| orlp wrote:
| 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.
| eapriv wrote:
| Even this is not in any way related to the asymptotic time
| bounds discussed in the article.
| dlubarov wrote:
| 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.
| johndough wrote:
| What is "expensive" in this context? Wolfram Alpha can solve
| it in a fraction of a second. https://www.wolframalpha.com/in
| put?i=solve+y%5E2+mod+%282%5E... >>> x =
| 113338949109682836687814795709948365013 >>> n = 1
| >>> y = 80490928931346377909947075573303248723 +
| 170141183460469231731687303715884105727 * n >>> y**2
| % (2**127 - 1) == x True
|
| EDIT: Looks like we got lucky here since 2^127 - 1 happens to
| be prime.
| uptownfunk wrote:
| Wow great article, I like the recaps
| DoctorOetker wrote:
| > 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...
| zmgsabst wrote:
| 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.
| dlubarov wrote:
| 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.
| graycat wrote:
| The linear algebra book by E. Nering does the material over
| finite fields.
|
| As I recall, Nering was an E. Artin student at Princeton.
| Retr0id wrote:
| 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.
| sevazhidkov wrote:
| Big fan of this series of lectures:
| https://youtu.be/h-94UhJLeck?si=0bEeB9VjmwRXIWTB.
| dlubarov wrote:
| 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...
___________________________________________________________________
(page generated 2024-05-12 23:01 UTC)