Skip to content
This repository was archived by the owner on Feb 17, 2025. It is now read-only.

Optimize constraint_computation_code #36

Closed
vo-nil opened this issue Oct 18, 2023 · 0 comments
Closed

Optimize constraint_computation_code #36

vo-nil opened this issue Oct 18, 2023 · 0 comments
Assignees
@vo-nil

Comments

@vo-nil
Copy link
Contributor

vo-nil commented Oct 18, 2023

Detect whether terms in a constraint are degrees of one variable. If true, call internal pure function, that powers to fixed degree.

Before (merkle_tree_poseidon example):

prod = 18422443583819058574249409890267113052353155664151173080611735213692213565494;
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);
prod = mulmod(prod, basic_marshalling.get_uint256_be(blob, 3040), modulus);

After:

prod = utils.pow7(basic_marshalling.get_uint256_be(blob, 3040), 18422443583819058574249409890267113052353155664151173080611735213692213565494);
@vo-nil vo-nil self-assigned this Oct 18, 2023
vo-nil added a commit that referenced this issue Oct 18, 2023
@vo-nil
Added power optimizations #36
f07e93b
vo-nil added a commit that referenced this issue Oct 18, 2023
@vo-nil
Add test namespace #36
162ae63
vo-nil added a commit that referenced this issue Oct 20, 2023
@vo-nil
Reworked gates generation, now it is possible to split on constraint …
660c54e 
…boundary. #36
ETatuzova pushed a commit that referenced this issue Oct 23, 2023
@vo-nil
Added power optimizations #36 (#37)
4fa65a8 
* Added power optimizations #36

* Add test namespace #36

* Reworked gates generation, now it is possible to split on constraint boundary. #36
@vo-nil vo-nil closed this as completed Oct 23, 2023
ETatuzova pushed a commit that referenced this issue Feb 1, 2024
@vo-nil @ETatuzova
Added power optimizations #36 (#37)
8f0185a 
* Added power optimizations #36

* Add test namespace #36

* Reworked gates generation, now it is possible to split on constraint boundary. #36
ETatuzova added a commit that referenced this issue Feb 5, 2024
@ETatuzova
Remove unuzed files #21
1a8df24 
Proof generating is syncronized with marshalling-zk #21

Copyrights added #21

Code structure changed #21

Gates files splitted #21

Lookups splitted #21

Zero-indices in permutation argument updated #21

std::couts removed #21

Commented code deleted, lookup_libs_list.json deleted #21

Direct public input updated#21

Split gate computations in libraries with given threshold #24

Split gates and lookups into multiple libs #24

Inline cheap gate evaluation in contract code #24

Done with lookups inlining #24

rm comment #24

Remove non-working CI#29

The haviest FRI function optimized #29

Add variable initialization #33

Added polynomial detection and Horner's formula #32 (#35)

* Added polynomial detection and Horner's formula #32

* Removed debug tracing #32

Added power optimizations #36 (#37)

* Added power optimizations #36

* Add test namespace #36

* Reworked gates generation, now it is possible to split on constraint boundary. #36

Multiply gate argument result on mask polynomial value #41

46 check values in etha point (#48)

* contract returs status #45

* EVM verifier interface update #45 NilFoundation/evm-placeholder-verification#81

* remove utils.sol if no helper functions generated #45 NilFoundation/evm-placeholder-verification#81

* Added check values for eta points #46

Added grinding mask check in EVM code #49 (#50)

* Added grinding mask check in EVM code #49

* added example of custom mask #49 NilFoundation/crypto3-zk-marshalling#53 NilFoundation/evm-placeholder-verification#84

38 commitment unchecked (#40)

* Added unchecked to commitment_scheme #38

* Added unchecked on all functions in commitment scheme #38

* Multiply gate argument result on mask polynomial value #41

* Remove extra parameter #38

* rm extra arguments #38

* Ensure that at lease one constraint is included in module #38

* whitespace cleanup #38

* rm debug print #38

---------

Co-authored-by: e.tatuzova <[email protected]>

Added events and removed gas estimation from solidity code #45 NilFoundation/evm-placeholder-verification#86

Reworked to single event with boolean paramter #45

46 check values in etha point (#55)

* Commitents is in input file #39

* Placeholder verifier random values generation #39

* Recursive verifier template and basic generator added #39

* Basic placeholder verifier done #39

* U and V #39

* Lookups #39

* Pow operation optimized #39

* Merkle proofs #39

* Some changes for actor-zk-compatibility #39

* Pow operation optimized #39

* Pow function updated. Specialized pow functions for small degrees hardcoded #39

* Work with eta points updated and commented #39

* prepare_U_and_V optimized #39

* Optimize row count for combinedQ computation #39

* Bug in pow2 function #39

* remove utils.sol if no helper functions generated #45 NilFoundation/evm-placeholder-verification#81

* Added check values for eta points #46

* Reworked checking values to keccak of blob #46

* Correct keccak computation #46

* Code cleanup #46

* Removed recursive tests

* Tests are now working #46

---------

Co-authored-by: e.tatuzova <[email protected]>

Revert "46 check values in etha point (#55)" (#56)

This reverts commit e32cdd5.

Changing get_fri_params to get_commitment_params, due to change in zk.

Events, lpc functions update, eta point #60

Remove console.log from colinear check #62

Commitents is in input file #39

Placeholder verifier random values generation #39

Recursive verifier template and basic generator added #39

Basic placeholder verifier done #39

U and V #39

Lookups #39

Pow operation optimized #39

Merkle proofs #39

Some changes for actor-zk-compatibility #39

Pow operation optimized #39

Pow function updated. Specialized pow functions for small degrees hardcoded #39

Work with eta points updated and commented #39

prepare_U_and_V optimized #39

Optimize row count for combinedQ computation #39

Bug in pow2 function #39

Removign 256 as parameter to __builtin_assigner_fri_cosets.

46 check values in etha point cherry pick for 39 (#57)

* remove utils.sol if no helper functions generated #45 NilFoundation/evm-placeholder-verification#81

* Added check values for eta points #46

* Correct keccak computation #46

* Code cleanup #46

* Removed recursive tests

* Tests are now working #46

Recursive verifier generation updated for last zk changes  #39

Public input length parameter #39

Lookups processing updated #39

Q polynomial degree crypto3-zk compatibility #39

EVM verifier and recursive verifier gen updated #39

Batching in recursive verifier changed #65

Remove console.log from colinear check #62

Add consistent testing

Recursive verifier public input processing added #39

Public input processing enabled #65

Remove comments with old code #65

EVM verifier updated #65

EVM verifier for lookups issues fixed #65

Recursive tests updated #65

Add recursive generator, update EVM verifier #39

39 branch prepared to merge #39

Delete couts #39

Update LPC batching.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@vo-nil vo-nil

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@vo-nil