Refactored backend and frontend to avoid use of build tags (curve dependency) #23

ThomasPiellard · 2020-04-20T13:59:20Z

Frontend

The CS and R1CS structures are now Fr agnostic (it uses big.Int now), so the frontend doesn't depend on the chosen Fr, and therefore gnark non longer uses tags. Tests to handle the Montgomery/Regular form of variables are OK (especially in the from/to_binary, select constraints for instance).

Tests are OK, but for creating a circuit, since now big.int are used, some variables can exceed the modulus: it's up to the user to query the modulus (not necessarily the r modulus if custom operations are created) to manually do the modular reduction (cf in point.go in gadgets/...twistededwards/ for instance).

Backend

Assignments now receives big.Int.
Addition of a utils.go file to handle conversion from interface{} to big.Int.

Circuits testing

Testing the correctness of the circuit solver is now done only in the backend/. In the frontend, only the consistency of the compiled circuit (R1CS struct) is tested because it's only what matters from the frontend's perspective. Nevertheless the tests in the backend cover all the subfunctions from cs.go.

Cryptolib

The code previously in /reference (reference implementations for the gadgets) is now at the root of gnark under the name cryptolib/. We might want to move it to gurvy eventually.
The mimc functions implement the hash function interface provided by https://golang.org/pkg/hash/.
For the Merkle tree we should use the package https://godoc.org/github.com/NebulousLabs/merkletree with our mimc functions.
For the cryptolib some code generation is used for the different Fr (in crypotlib/internal).

Gadgets

The gadgets are now at the root of the repo under the folder gadgets/.
Gadgets that depend on the curve (like mimc) are now created by providing the ID of the chosen curve, the constructors are now in a hashmap ID->constructor().
The Merkle trees are wip.

Gob (encoding)

The encoding package has been moved at the root of gnark, previously it was in internal/ preventing its use when using gnark as a module.

go.sum has been updated.

CircleCi whines because of the version, I should have messed with the version :/

…ntext obj), Div needs to be tweaked to work

… twistedEdwards gadgets with bigInt r1cs OK

…the assertions handling in the backend.

…r the cryptolib

gbotrel

WIP review:

Questions:

why are the eddsa and mimc stuff in template form now, generated for each curve?

Remarks:

fix golint errors
please fix the failing test, branch must pass circleCI (see our mini wiki for the version bump helper :) )
can you rename cryptolib package into crypto?
remove these;

gnark [tagless_refactor] $ find . -name "*.backup"
./cryptolib/accumulator/merkle/proof.go.backup
./cryptolib/accumulator/merkle/proof_test.go.backup
./backend/assignment_test.backup
./integration_test.go.backup
./gadgets/accumulator/merkle/proof.go.backup

This part in the circuit examples is not elegant:

	_r1cs := circuit.ToR1CS()
	r1cs := backend_bn256.New(_r1cs)
	return &r1cs

I'ld prefer not exposing (confusing) 2 R1CS to the end user.
Maybe something like this instead:

return backend.NewR1CS(&circuit)

?

gbotrel · 2020-04-22T19:23:36Z

backend/assignment_test.backup

+
+	"github.com/stretchr/testify/require"
+)
+


while is that file commited? need to restore these tests maybe?

ThomasPiellard · 2020-04-23T19:44:57Z

Ok for the remarks (especially this

_r1cs := circuit.ToR1CS()
r1cs := backend_bn256.New(_r1cs)
return &r1cs

) I was planning to change this.

For the first remark:

I think eventually the mimc and eddsa functions (of the cryptolib) should be moved in gurvy or in their own repo, but gnark is not the right place for those. In the optic of moving them in gurvy I generated in advance the template, that should be put in the gurvy's generators... And also it solves as always the lack of generics.

-r1cs.go(backend): added a method to cast from a generic r1cs (with bigInt); added a method to create a r1cs direcly without having to create a frontend's r1cs and then convert it to a specialized field Fr - moved cryptolib/, replaced it by crypto/ - fixed the tags

ggutoski

Thomas presented an overview of the refactor to me in a call. This is a large PR; I focused on the parts Thomas described to me and posted a few comments with only minor suggestions.

ggutoski · 2020-04-28T21:34:21Z

backend/bls377/r1cs.go

+
+		for j := 0; j < len(from.L); j++ {
+			to.L[j].ID = from.L[j].ID
+			to.L[j].Coeff.SetBigInt(&from.L[j].Coeff)


It is not clear from this code where the actual casting is happening. At first glance the entire Cast method looks like an ordinary deep copy. The only casting that happens in this method is on lines 83, 87, 91. I had to dig a bit to notice that to.L[j].Coeff is of type fr.Element whereas from.L[j].Coeff is of type big.Int, and the method SetBigInt is where the actual conversion from big.Int to fr.Element occurs.

I don't know what to suggest here. Perhaps nothing. Perhaps some additional comments would suffice, or perhaps we can rename some members to make it clear that the two Coeff members have different types.

ggutoski · 2020-04-28T22:00:34Z

backend/bls377/fft_test.go

@@ -16,12 +16,12 @@ See the License for the specific language governing permissions and
 limitations under the License.


Don't forget to remove the +build tags :)

Why is this file inside bls377 and nowhere else? Should we generate fft_test from template, too?

ggutoski · 2020-04-28T22:55:47Z

backend/utils.go

+			panic("unable to set big.Int from base10 string")
+		}
+	case big.Int:
+		val = c1


Ok I'm being nitpicky here. From package big docs:

To "copy" an Int value, an existing (or newly allocated) Int must be set to a new value using the Int.Set method; shallow copies of Ints are not supported and may lead to errors.

We probably should not be using the = operator to copy a big.Int. (It sure would have been nice of them to support shallow copies!)

ggutoski · 2020-04-28T23:03:30Z

backend/bls377/groth16/assert.go

+
+// assert helpers
+
+// Assert is a helper to test circuits


Name clash with debug.Assert. Perhaps we should use the name "assert" for only one of these objects.

ggutoski · 2020-04-29T22:27:01Z

crypto/accumulator/merkle/proof.go.backup

@@ -1,8 +1,8 @@
 package merkle


another .backup file.

gbotrel and others added 18 commits April 2, 2020 20:25

frontend/: wip, temporary R1CS data struct using big.Int

d0029c5

backend/: checkpoint refactoring

1bf01be

backend/: checkpoint refactoring

9bd28bb

checkpoint :(

299e7d5

WIP: using big.Int in frontend to avoid build tags

98137f3

wip, fr agnostic r1cs tests OK

3b1144c

wip, fixed generation generators for utils.go, gadget needs reorg (co…

0dc462c

…ntext obj), Div needs to be tweaked to work

frontend: fixed division-by-constant constraint

13c8e70

refactoring gadgets

60456e9

regenerated version ...

b6db966

wip refactoring gadgets, tests ok

c6ad99b

eddsa (cryptolib) is cleaned up, code generation for eddsa, tests for…

f898a7c

… twistedEdwards gadgets with bigInt r1cs OK

Eddsa gadget with bigInt r1cs works. Refactoring needs to be done in …

5be7e7e

…the assertions handling in the backend.

moved encoding from internal so it can be used from elsewhere

483fba1

regenerated version :/

e396b06

make gofmt happy...

1907ffa

Mimcs (cryptolib) implement the go Hash interface, code generation fo…

6fedfbb

…r the cryptolib

backend: cleaned asserts

e0ff260

ThomasPiellard added the new feature label Apr 20, 2020

ThomasPiellard requested review from ggutoski and gbotrel April 20, 2020 13:59

gbotrel reviewed Apr 22, 2020

View reviewed changes

gbotrel changed the title ~~Tagless refactor~~ Refactored backend and frontend to avoid use of build tags (curve dependency) Apr 23, 2020

fixes #23

2150ebe

-r1cs.go(backend): added a method to cast from a generic r1cs (with bigInt); added a method to create a r1cs direcly without having to create a frontend's r1cs and then convert it to a specialized field Fr - moved cryptolib/, replaced it by crypto/ - fixed the tags

ggutoski reviewed Apr 29, 2020

View reviewed changes

ThomasPiellard merged commit 725dbc7 into develop May 11, 2020

ThomasPiellard deleted the tagless_refactor branch May 11, 2020 17:28

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Refactored backend and frontend to avoid use of build tags (curve dependency) #23

Refactored backend and frontend to avoid use of build tags (curve dependency) #23

ThomasPiellard commented Apr 20, 2020

gbotrel left a comment •

edited

gbotrel Apr 22, 2020

ThomasPiellard commented Apr 23, 2020 •

edited

ggutoski left a comment

ggutoski Apr 28, 2020

ggutoski Apr 28, 2020

ggutoski Apr 28, 2020

ggutoski Apr 28, 2020

ggutoski Apr 28, 2020

ggutoski Apr 29, 2020

		@@ -16,12 +16,12 @@ See the License for the specific language governing permissions and
		limitations under the License.

Refactored backend and frontend to avoid use of build tags (curve dependency) #23

Refactored backend and frontend to avoid use of build tags (curve dependency) #23

Conversation

ThomasPiellard commented Apr 20, 2020

Frontend

Backend

Circuits testing

Cryptolib

Gadgets

Gob (encoding)

gbotrel left a comment • edited

Choose a reason for hiding this comment

gbotrel Apr 22, 2020

Choose a reason for hiding this comment

ThomasPiellard commented Apr 23, 2020 • edited

ggutoski left a comment

Choose a reason for hiding this comment

ggutoski Apr 28, 2020

Choose a reason for hiding this comment

ggutoski Apr 28, 2020

Choose a reason for hiding this comment

ggutoski Apr 28, 2020

Choose a reason for hiding this comment

ggutoski Apr 28, 2020

Choose a reason for hiding this comment

ggutoski Apr 28, 2020

Choose a reason for hiding this comment

ggutoski Apr 29, 2020

Choose a reason for hiding this comment

gbotrel left a comment •

edited

ThomasPiellard commented Apr 23, 2020 •

edited