17 research outputs found
Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs
No full textInternational audienceThe bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize the arithmetic of finite fields by improving on the well-known Coarsely Integrated Operand Scanning (CIOS) modular multiplication. This is a contribution of independent interest that applies to many different contexts. Second, we propose a new coordinate system for twisted Edwards curves tailored for the Pippenger MSM algorithm.Accelerating the MSM over these curves is critical for deployment of recursive proof< systems applications such as proof-carrying-data, blockchain rollups and blockchain light clients. We implement our work in Go and benchmark it on two different CPU architectures (x86 and arm64). We show that our implementation achieves a 40-47% speedup over the state-of-the-art implementation (which was implemented in Rust). This MSM implementation won the first place in the ZPrize competition in the open division “Accelerating MSM on Mobile” and will be deployed in two real-world applications: Linea zkEVM by ConsenSys and probably Celo network
EdMSM: Multi-Scalar-Multiplication for SNARKs and Faster Montgomery multiplication
No full textThe bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize the arithmetic of finite fields by improving on the well-known Coarsely Integrated Operand Scanning (CIOS) modular multiplication. This is a contribution of independent interest that applies to many different contexts. Second, we propose a new coordinate system for twisted Edwards curves tailored for the Pippenger MSM algorithm.
Accelerating the MSM over these curves is critical for deployment of recursive proof systems applications such as proof-carrying-data, blockchain rollups and blockchain light clients. We implement our work in Go and benchmark it on two different CPU architectures (x86 and arm64). We show that our implementation achieves a 40-47% speedup over the state-of-the-art implementation (which was implemented in Rust). This MSM implementation won the first place in the ZPrize competition in the open division “Accelerating MSM on Mobile” and will be deployed in two real-world applications: Linea zkEVM by ConsenSys and probably Celo network
ConsenSys/gnark: v0.6.0
No full text[v0.6.0] - 2022-01-03
Important: next release (v0.7.0) will be compatible with Go1.18+ only
Breaking changes
circuit.Define(curveID, api) -> circuit.Define(api); added api.Curve() to retrieve curve info
api.Constant(...) was removed. Can now directy assign values with = operator in the circuit definition and the witness assignment.
frontend.Variable is now an alias for interface{}
assert helper is now under gnark/test. Instead of taking a CompiledConstraintSystem it takes a Circuit as input, enabling easier tests accross curves and proving schemes through the use of test/TestingOption (WithBackends(backend.GROTH16), WithCurves(ecc.BN254), ...)
api.NewHint handles multiple outputs and custom solver Hint definition has changed
Feat
added explicit warning when parser encounters unadressable struct field #169
FromInterface supports uintXX and intXX types closes #197
lighter stack trace by default for circuits, more verbose when -tags=debug provided
added api.Tag and api.AddCounter to measure number of constraints in portion of circuit
api.DivUnchecked does not handle zero divisor. api.Div does.
added frontend.IsConstant and ConstantValue apis
add support for bw6-633 curve
added api.Lookup2 method (2-bit lookup)
frontend: plonk frontend directly implements the frontend.API interface instead of building on top of the R1CS builder
std: fields and pairing over BLS24-315 in BW6-633 circuit
test: add Run for running circuit test configurations as subtests
test: add Log method for logging in subtests
test: assert helper cross check constraint system solver results with big.Int test execution engine
Perf
std: verifying a Pairing (bls12-377, Groth16) inside a circuit went from ~40k constraints to less than <12k constraints
Fix
fixes #169 ensure frontend.Circuit methods are defined on pointer receiver
fixes #178 by adding cbor.MaxMapPairs options when reading R1CS
fixed AssertIsBoolean in plonk (mul by constant failed)
fixes #168 adds context to a non-deterministic compilation error in the Assert object
frontend: reduce constant by modulus
frontend: plonk compiler now outputs a reasonable number of constraints #186
Build
updated to gnark-crypto v0.6.0
Pull Requests
Merge pull request #192 from ConsenSys/multi-hint
Merge pull request #220 from ConsenSys/feat-from-interface
Merge pull request #217 from ConsenSys/fix-internal-compiled
Merge pull request #191 from ConsenSys/assert-subtests
Merge pull request #200 from ConsenSys/refactor/frontend
Merge pull request #205 from ConsenSys/fix/constant-mod-reduction
Merge pull request #186 from ConsenSys/fix/plonk_constraints
Merge pull request #185 from ConsenSys/feat/bw6-633
Merge pull request #189 from ConsenSys/lookup2
Merge pull request #183 from ivokub/hint-registry
Merge pull request #182 from ConsenSys/std/pairing
Merge pull request #176 from ConsenSys/feat-constraint-counter
Merge pull request #180 from ConsenSys/refactor-variable-interface
Merge pull request #173 from ConsenSys/feat-debug-ta
ConsenSys/gnark-crypto: v0.6.0
No full text[v0.6.0] - 2021-12-22
Feat
plookup: added plookup lookup proof
field: generate optimized addition chains for Sqrt & Legendre exp functions
field: added field.SetInt64, support for intX and uintX #109
field: added UnmarshalJSON and MarshalJSON on fields
field: added field.Text(base) to return field element string in a given base, like big.Int
field: field.SetString now supports 0b 0o 0x prefixes (base 2, 8 and 16)
kzg: test tampered proofs whith quotient set to zero
bls24: Fp-Fp2-Fp4-Fp12-Fp24 tower
Fix
fixes #104 code generation for saturated modulus like secp256k1 incorrect. added secp256k1 test
Perf
field inverse is ~30-70% faster (implements Pornin's optimizations)
bls12-381: faster Miller loop (sparse-sparse mul)
bls12-381: faster final exp (faster expt)
bn254: better short addition chain for Expt()
bn254: addchain with max squares (weighting mul x2.6 cyclosq)
Pull Requests
Merge pull request #111 from ConsenSys/field-intX-support
Merge pull request #114 from ConsenSys/fix-dynamic-link
Merge pull request #108 from ConsenSys/perf/bls12381-pairing
Merge pull request #106 from ConsenSys/improvement/field-inv-pornin20
Merge pull request #105 from ConsenSys/field-from-json
Merge pull request #83 from ConsenSys/experiment/BLS24
Merge pull request #102 from ConsenSys/feat/plookup
Merge pull request #97 from ConsenSys/feat-addchain
Merge pull request #99 from ConsenSys/feat-addchain-exp
ConsenSys/gnark: v0.6.4
No full text
[v0.6.4] - 2022-02-15
Build
update to gnark-crpto v0.6.1
Feat
Constraint system solvers (Groth16 and PlonK) now run in parallel
Fix
api.DivUnchecked with PlonK between 2 constants was incorrect
Perf
EdDSA: std/algebra/twistededwards takes ~2K less constraints (Groth16). Bandersnatch benefits from same improvments.
Pull Requests
Merge pull request #259 from ConsenSys/perf-parallel-solver
Merge pull request #261 from ConsenSys/feat/kzg_updated
Merge pull request #257 from ConsenSys/perf/EdDSA
Merge pull request #253 from ConsenSys/feat/fft_coset
ConsenSys/gnark: v0.6.1
No full text[v0.6.1] - 2022-01-28
Build
go version dependency bumped from 1.16 to 1.17
Feat
added witness.MarshalJSON and witness.MarshalBinary
added ccs.GetSchema() - the schema of a circuit is required for witness json (de)serialization
added ccs.GetConstraints() - returns a list of human-readable constraints
added ccs.IsSolved() - moved from groth16 / plonk to the CompiledConstraintSystem interface
added witness.Public() to return Public part of the witness
addition of Cmp in the circuit API
Refactor
compiled.Visbility -> schema.Visibiility
witness.WriteSequence -> schema.WriteSequence
killed ReadAndProve and ReadAndVerify (plonk)
killed ReadAndProve and ReadAndVerify (groth16)
remove embbed struct tag for frontend.Variable fields
Docs
backend: unify documentation for options
frontend: unify docs for options
test: unify documentation for options
Pull Requests
Merge pull request #244 from ConsenSys/plonk-human-readable
Merge pull request #237 from ConsenSys/ccs-get-constraints
Merge pull request #233 from ConsenSys/feat/api_cmp
Merge pull request #235 from ConsenSys/witness-public-api
Merge pull request #232 from ConsenSys/cleanup-231-group-options
Merge pull request #230 from ConsenSys/ccs-schema
Merge pull request #229 from ConsenSys/ccs-issolved-api
Merge pull request #228 from ConsenSys/witness-json
Merge pull request #226 from ConsenSys/feat-circuit-schema
Merge pull request #227 from ConsenSys/build-update-go1.17
Merge pull request #222 from ConsenSys/perf/std-sw-gl
Consensys/gnark-crypto: v0.10.1
No full textSecurity
Fixed bug in hashing to field when computing and verifying ECDSA signatures (#427, fix #428). Thanks @samngmco for reporting.
Full Changelog: https://github.com/Consensys/gnark-crypto/compare/v0.10.0...v0.10.
Consensys/gnark: v0.8.1
No full textSecurity
Update gnark-crypto dependency to include security fix.
What's Changed
Fix the example in README.md by @aybehrouz in https://github.com/Consensys/gnark/pull/478
Full Changelog: https://github.com/Consensys/gnark/compare/v0.8.0...v0.8.
ConsenSys/gnark-crypto: v0.10.0
No full textWhat's Changed
Fixes
fix: invalid infinity point decoding throws error by @gbotrel in https://github.com/ConsenSys/gnark-crypto/pull/363
New features / refactor
feat: FFT signature now takes variadic options by @gbotrel in https://github.com/ConsenSys/gnark-crypto/pull/345
feat: add ECDSA public key recover from message, signature and recovery info by @ivokub in https://github.com/ConsenSys/gnark-crypto/pull/347
expose bn254 tower to gnark by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/354
Export BW6-761 E3/E6 by @SherLzp in https://github.com/ConsenSys/gnark-crypto/pull/359
Expose BLS12-381 tower by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/360
Perf
perf: sis tensor commitment by @gbotrel in https://github.com/ConsenSys/gnark-crypto/pull/344
Add support for parallelization in the tensor-commitment by @AlexandreBelling in https://github.com/ConsenSys/gnark-crypto/pull/263
Perf/tensor commitment by @AlexandreBelling in https://github.com/ConsenSys/gnark-crypto/pull/341
perf(stark-curve): no subgroup check on prime-order curve by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/349
perf(bw6-756): optimize GT subgroup membership by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/351
perf: optimize BLS24-317 final exp by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/356
perf: tweaks in iop/ kzg/ packages by @gbotrel in https://github.com/ConsenSys/gnark-crypto/pull/361
perf & refactor: pairings by @yelhousni in https://github.com/ConsenSys/gnark-crypto/pull/366
New Contributors
@ivokub made their first contribution in https://github.com/ConsenSys/gnark-crypto/pull/347
@SherLzp made their first contribution in https://github.com/ConsenSys/gnark-crypto/pull/359
@jtraglia made their first contribution in https://github.com/ConsenSys/gnark-crypto/pull/364
Full Changelog: https://github.com/ConsenSys/gnark-crypto/compare/v0.9.1...v0.10.
Consensys/gnark-crypto: v0.11.2
No full textWhat's Changed
Fix some typos by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/394
Adding testing for deserialization of G1 and G2 points by @asanso in https://github.com/Consensys/gnark-crypto/pull/393
Fix some implicit memory aliasing in for loops by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/395
Do not XOR with zero by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/398
Disable check shadowing in govet linter by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/397
Add a bunch of "nosec G404" comments in test code by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/399
Enable misspell linter & fix findings by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/401
Fix RSis.CopyWithFreshBuffer by @AlexandreBelling in https://github.com/Consensys/gnark-crypto/pull/402
feat: Marshal [][]fr.Element by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/400
Run golangci-lint on generated files by @jtraglia in https://github.com/Consensys/gnark-crypto/pull/396
docs: ConsenSys -> Consensys by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/406
msm: semaphore to limit CPUs + better split strategy (up to 25% perf boost on 96cores) by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/403
Feat/fold pedersen by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/407
fix: do not read empty slices as nil by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/410
fix: incorrect semaphore init could cause msm deadlock by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/411
edwards: optimize point negation by @jsign in https://github.com/Consensys/gnark-crypto/pull/413
Feat/gkr custom gates by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/419
perf: fast path for SIS with logTwoBound: 8, logTwoDegree: 6 by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/416
feat: add WriteRawTo, UnsafeReadFrom to kzg.ProvingKey by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/422
Fix/gkr eq bug by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/421
feat: add AsyncReadFrom to fr.Vector and fft.Domain by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/424
fix: ECDSA HashToInt bytes-bits mismatch by @ivokub in https://github.com/Consensys/gnark-crypto/pull/428
Small optimization over the memory usage of MiMC by @AlexandreBelling in https://github.com/Consensys/gnark-crypto/pull/435
perf: improve fft domain memory footprint by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/437
Refactor/gkr test vectors by @Tabaie in https://github.com/Consensys/gnark-crypto/pull/425
v0.11.2 by @gbotrel in https://github.com/Consensys/gnark-crypto/pull/438
New Contributors
@asanso made their first contribution in https://github.com/Consensys/gnark-crypto/pull/393
@jsign made their first contribution in https://github.com/Consensys/gnark-crypto/pull/413
Full Changelog: https://github.com/Consensys/gnark-crypto/compare/v0.11.1...v0.11.
