Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

x/crypto/bn256: wrong formulas in comments #48143

Open
zhangzhanli opened this issue Sep 2, 2021 · 4 comments
Open

x/crypto/bn256: wrong formulas in comments #48143

zhangzhanli opened this issue Sep 2, 2021 · 4 comments
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Unreleased

Comments

@zhangzhanli
Copy link

zhangzhanli commented Sep 2, 2021 •
edited by cherrymui

bn256/gfp6.go : 251 in latest version of go

// On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
// = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
//
// So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)

while the right one is :

// On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
// = τ²(y²-xz) + τ(ξx²-yz) + (z²-ξxy)
//
// So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-xz)

in addition, http://arxiv.org/pdf/0904.0854v3.pdf which is referenced by optate.go : 9 also has wrong formulas :

截屏2021-09-02 下午5 42 01
@cherrymui cherrymui changed the title golang.org/x/crypto/bn256: wrong formulas x/crypto/bn256: wrong formulas Sep 2, 2021
@gopherbot gopherbot added this to the Unreleased milestone Sep 2, 2021
@cherrymui
Copy link
Member

It looks the code actually does

        C := newGFp2(pool)
        C.Square(a.y, pool)
        t1.Mul(a.x, a.z, pool)
        C.Sub(C, t1)

i.e. C = (y²-xz) without ξ.

@zhangzhanli do you suggest only the comment is wrong or the implementation as well? Thanks.

cc @FiloSottile @agl @katiehockman @rolandshoemaker

@cherrymui cherrymui added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 2, 2021
@zhangzhanli
Copy link
Author

@cherrymui Yes, it seems the source code works as expected. As for full addition, since we use mixed addition instead , so there is no impact on miller's algorithm.

@cherrymui cherrymui changed the title x/crypto/bn256: wrong formulas x/crypto/bn256: wrong formulas in comments Sep 22, 2021
@cherrymui cherrymui added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 22, 2021
@cherrymui
Copy link
Member

Thanks.

@gopherbot
Copy link

Change https://golang.org/cl/361374 mentions this issue: crypto: fix wrong formulas in comments

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
3 participants
@gopherbot @cherrymui @zhangzhanli