Feat/fflonk

[ThomasPiellard]

Description

Implementation of shplonk Implementation of fflonk (only the commitment)

Type of change

Please delete options that are not relevant.

• [ ] Bug fix (non-breaking change which fixes an issue)
• [x] New feature (non-breaking change which adds functionality)
• [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
• [ ] This change requires a documentation update

How has this been tested?

Please describe the tests that you ran or implemented to verify your changes. Provide instructions so we can reproduce.

• [x] see fflonk_test.go
• [x] see shplonk_test_go

Checklist:

• [x] I have performed a self-review of my code
• [x] I have commented my code, particularly in hard-to-understand areas
• [x] I have made corresponding changes to the documentation
• [x] I have added tests that prove my fix is effective or that my feature works
• [x] I did not modify files generated from templates
• [x] golangci-lint does not output errors locally
• [x] New and existing unit tests pass locally with my changes
• [x] Any dependent changes have been merged and published in downstream modules

[github-actions[bot]]

📦 github.com/consensys/gnark-crypto/ecc/bls12-377/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:132: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-377/fflonk/fflonk_test.go:132
        	Error:      	Received unexpected error:
        	            	Fr does not contain all the t-th roots of 1
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bls12-378/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-378/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bls12-381/fflonk ❌ TestFflonk 100ms

    fflonk_test.go:80: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-381/fflonk/fflonk_test.go:80
        	Error:      	Received unexpected error:
        	            	invalid polynomial size (larger than SRS or == 0)
        	Test:       	TestFflonk

❌ TestGetIthRootOne 0s

    fflonk_test.go:132: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-381/fflonk/fflonk_test.go:132
        	Error:      	Received unexpected error:
        	            	Fr does not contain all the t-th roots of 1
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:132: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls24-317/fflonk/fflonk_test.go:132
        	Error:      	Received unexpected error:
        	            	Fr does not contain all the t-th roots of 1
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bw6-756/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-756/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bw6-761/fflonk ❌ TestFflonk 290ms

    fflonk_test.go:80: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-761/fflonk/fflonk_test.go:80
        	Error:      	Received unexpected error:
        	            	invalid polynomial size (larger than SRS or == 0)
        	Test:       	TestFflonk

❌ TestGetIthRootOne 0s

    fflonk_test.go:132: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-761/fflonk/fflonk_test.go:132
        	Error:      	Received unexpected error:
        	            	Fr does not contain all the t-th roots of 1
        	Test:       	TestGetIthRootOne

[github-actions[bot]]

📦 github.com/consensys/gnark-crypto/ecc/bls12-381/fflonk ❌ TestFflonk 80ms

    fflonk_test.go:80: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-381/fflonk/fflonk_test.go:80
        	Error:      	Received unexpected error:
        	            	invalid polynomial size (larger than SRS or == 0)
        	Test:       	TestFflonk

❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-381/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bls24-315/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls24-315/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bw6-761/fflonk ❌ TestFflonk 200ms

    fflonk_test.go:80: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-761/fflonk/fflonk_test.go:80
        	Error:      	Received unexpected error:
        	            	invalid polynomial size (larger than SRS or == 0)
        	Test:       	TestFflonk

❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-761/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

[github-actions[bot]]

📦 github.com/consensys/gnark-crypto/ecc/bls12-381/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls12-381/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bls24-315/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bls24-315/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

📦 github.com/consensys/gnark-crypto/ecc/bw6-761/fflonk ❌ TestGetIthRootOne 0s

    fflonk_test.go:140: 
        	Error Trace:	/home/runner/work/gnark-crypto/gnark-crypto/ecc/bw6-761/fflonk/fflonk_test.go:140
        	Error:      	An error is expected but got nil.
        	Test:       	TestGetIthRootOne

[ivokub]

@ThomasPiellard - I don't touch the branch currently - I'll add the documentation and examples after you have finished.

[ivokub]

As a note - we discussed with @ThomasPiellard about how to compute the n-ths roots of the input points. But in the field implementations we have, n is usually a power of two and we can do successive square roots.

[ivokub]

A few TODOs for another PR to improve the packages:

• instead of using []fr.Element for points in shplonk, we could define a structure a la struct Points { Pts []fr.Element, Shape shplonk.PointShape}. Depending on the shape of the points (they are roots of unity, or some known powers etc.) we can have different approaches for polynomial multiplication etc.