search

protolambda / go-kzg

FFT, data-recovery and KZG commitments, a.k.a. Kate commitments, in Go - *super experimental*
MIT License
90 stars 26 forks source link

Expose modulus publicly, add BatchInvModFr, ExpModFr, EvaluatePolyInEvaluationForm #25

Closed roberto-bayardo closed 1 year ago

roberto-bayardo commented 2 years ago

These are two minor changes we made for our EIP-4844 work where we found we needed to use the value of MODULUS, and also needed to do batch inverse mod operations for efficiency.

roberto-bayardo commented 2 years ago

just noticed @Inphi submitted the BatchIvModFr part of this PR in github.com/protolambda/go-kzg/24

protolambda commented 1 year ago

Reverted the modulus global var changes, Herumi panics when setting Fr to the modulus value, and rightly so. The Fr type is supposed to be in the range 0 to modulus (exclusive!). Creating a global value of type Fr set to the modulus value beats the whole purpose. Upon parsing 32 bytes to a Fr it already checks if the value fits. See bls.FrFrom32 and bls.ValidFr to that. Some other BLS libraries may be able to represent numbers larger than the modulus in the Fr type, but this functionality is not supposed to be used.

In geth I see you do not use this modulus global, and in prysm I see MODULUS_STR is used to initialize blob.blsModulus, a big.Int, which is fine, but still hacky.

So I took some time to upstream the EvaluatePolyInEvaluationForm version in prysm from here: https://github.com/Inphi/prysm/blob/04dac7ea5f11c510f03898fddefac317f8a8f42a/beacon-chain/core/blob/sidecar.go#L230

I added a test to check if the same polynomial in coefficient form and evaluation form can be evaluated to the same y value, for random different x values. In the process of doing that I noticed there's some dead code in the original:

        var denom bls.Fr
        bls.SubModFr(&denom, x, &rootsOfUnity[i])

which I think is still there from when it didn't do the batch invert. And the (1 - x**WIDTH) part seems to be (x**WIDTH - 1) but I'm not sure why the code doesn't match the comment, it does pass tests that way (and not like the comment). @asn-d6 can you give this a look?

roberto-bayardo commented 1 year ago

Yeah the exported MODULUS was a mistake I forgot to undo after changing to MODULUS_STR, thanks for catching that. It would be convenient to leave MODULUS_STR (or some other exported value of the modulus) here so we don't have to copy paste it in geth/prysm?

Re: 1-x**WIDTH, I think @Inphi wrote that function which we copy/pasted to prysm from Geth. Maybe a bug that just happened to work due to modulus math?

Inphi commented 1 year ago

Re: 1-x**WIDTH, I think @Inphi wrote that function which we copy/pasted to prysm from Geth. Maybe a bug that just happened to work due to modulus math?

Yup, that's a bug. It should be the other way around.

protolambda commented 1 year ago

Checked with Kev, bug in comment confirmed, cross-checked it against a post by dankrad. Updated the comments to fix and clarify.

roberto-bayardo commented 1 year ago

@protolambda can we leave some version of modulus exported? If not string, then how about a bignum?

protolambda commented 1 year ago

@roberto-bayardo brought it back as const ModulusStr. Using the right typing/functions is always preferable, but if you have to use it, the const exposes the value without any accidental mutations / effects on bls code.

roberto-bayardo commented 1 year ago

Thank you @protolambda looks great! Please merge at your convenience.