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.

Sign up for GitHub

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

Generalise computation of vanishing polynomial at challenge and lagrange basis and use batch_invert for computing denominators in K #764

Closed
maramihali opened this issue Nov 6, 2023 · 0 comments · Fixed by AztecProtocol/aztec-packages#5510
Closed

Generalise computation of vanishing polynomial at challenge and lagrange basis and use batch_invert for computing denominators in K #764

maramihali opened this issue Nov 6, 2023 · 0 comments · Fixed by AztecProtocol/aztec-packages#5510
Assignees
@lucasxia01
Milestone
Protogalaxy

Comments

@maramihali
Copy link
Contributor

No description provided.

@maramihali maramihali added this to the Protogalaxy milestone Nov 6, 2023
@maramihali maramihali changed the title Generalise computation of vanishing polynomial at challenge and lagrange basis Generalise computation of vanishing polynomial at challenge and lagrange basis and use batch_invert Nov 9, 2023
@maramihali maramihali changed the title Generalise computation of vanishing polynomial at challenge and lagrange basis and use batch_invert Generalise computation of vanishing polynomial at challenge and lagrange basis and use batch_invert for computing denominators in K Nov 9, 2023
@lucasxia01 lucasxia01 mentioned this issue Mar 28, 2024
Merged
lucasxia01 added a commit to AztecProtocol/aztec-packages that referenced this issue Apr 9, 2024
@lucasxia01
feat: generalize protogalaxy to multiple instances (#5510)
f038b70 
Closes AztecProtocol/barretenberg#764.

This PR aims to generalize protogalaxy to multiple instances. In particular, we care about k=2 (1 accumulator and 2 instances) and k=3 and and their performance relative to folding k=1 instance.

We achieve the following numbers:
```
--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
fold_k<UltraFlavor, 1>/16             1039 ms          908 ms            1
fold_k<UltraFlavor, 2>/16             1744 ms         1562 ms            1
fold_k<UltraFlavor, 3>/16             2755 ms         2484 ms            1
fold_k<GoblinUltraFlavor, 1>/16       1431 ms         1231 ms            1
fold_k<GoblinUltraFlavor, 2>/16       2387 ms         2084 ms            1
fold_k<GoblinUltraFlavor, 3>/16       3734 ms         3291 ms            1
```

and client IVC benchmark stays the same:
```
--------------------------------------------------------------------------------    
Benchmark                      Time             CPU   Iterations 
--------------------------------------------------------------------------------    
ClientIVCBench/Full/6      23140 ms        17976 ms            1    
Benchmarking lock deleted.                                                          
client_ivc_bench.json                             100% 3561   106.5KB/s   00:00     
function                                        ms     % sum                        
construct_circuits(t)                         4522    19.75%                        
ProverInstance(Circuit&)(t)                   2060     9.00%
ProtogalaxyProver::fold_instances(t)         12545    54.81%
Decider::construct_proof(t)                    734     3.21%
ECCVMProver(CircuitBuilder&)(t)                158     0.69%
ECCVMProver::construct_proof(t)               1768     7.73%
GoblinTranslatorProver::construct_proof(t)     959     4.19%
Goblin::merge(t)                               145     0.63%

Total time accounted for: 22890ms/23140ms = 98.92%

Major contributors:
function                                        ms    % sum
commit(t)                                     4283   18.71%
compute_combiner(t)                           5702   24.91%
compute_perturbator(t)                        1250    5.46%
compute_univariate(t)                         1386    6.05%

Breakdown of ProtogalaxyProver::fold_instances:
ProtoGalaxyProver_::preparation_round(t)           5297    42.22%
ProtoGalaxyProver_::perturbator_round(t)           1250     9.97%
ProtoGalaxyProver_::combiner_quotient_round(t)     5704    45.47%
ProtoGalaxyProver_::accumulator_update_round(t)     294     2.35%
```
AztecBot pushed a commit that referenced this issue Apr 10, 2024
@lucasxia01 @AztecBot
feat: generalize protogalaxy to multiple instances (#5510)
91dbc34 
Closes #764.

This PR aims to generalize protogalaxy to multiple instances. In particular, we care about k=2 (1 accumulator and 2 instances) and k=3 and and their performance relative to folding k=1 instance.

We achieve the following numbers:
```
--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
fold_k<UltraFlavor, 1>/16             1039 ms          908 ms            1
fold_k<UltraFlavor, 2>/16             1744 ms         1562 ms            1
fold_k<UltraFlavor, 3>/16             2755 ms         2484 ms            1
fold_k<GoblinUltraFlavor, 1>/16       1431 ms         1231 ms            1
fold_k<GoblinUltraFlavor, 2>/16       2387 ms         2084 ms            1
fold_k<GoblinUltraFlavor, 3>/16       3734 ms         3291 ms            1
```

and client IVC benchmark stays the same:
```
--------------------------------------------------------------------------------    
Benchmark                      Time             CPU   Iterations 
--------------------------------------------------------------------------------    
ClientIVCBench/Full/6      23140 ms        17976 ms            1    
Benchmarking lock deleted.                                                          
client_ivc_bench.json                             100% 3561   106.5KB/s   00:00     
function                                        ms     % sum                        
construct_circuits(t)                         4522    19.75%                        
ProverInstance(Circuit&)(t)                   2060     9.00%
ProtogalaxyProver::fold_instances(t)         12545    54.81%
Decider::construct_proof(t)                    734     3.21%
ECCVMProver(CircuitBuilder&)(t)                158     0.69%
ECCVMProver::construct_proof(t)               1768     7.73%
GoblinTranslatorProver::construct_proof(t)     959     4.19%
Goblin::merge(t)                               145     0.63%

Total time accounted for: 22890ms/23140ms = 98.92%

Major contributors:
function                                        ms    % sum
commit(t)                                     4283   18.71%
compute_combiner(t)                           5702   24.91%
compute_perturbator(t)                        1250    5.46%
compute_univariate(t)                         1386    6.05%

Breakdown of ProtogalaxyProver::fold_instances:
ProtoGalaxyProver_::preparation_round(t)           5297    42.22%
ProtoGalaxyProver_::perturbator_round(t)           1250     9.97%
ProtoGalaxyProver_::combiner_quotient_round(t)     5704    45.47%
ProtoGalaxyProver_::accumulator_update_round(t)     294     2.35%
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@lucasxia01 lucasxia01

Labels
None yet
Projects
None yet
Milestone
Protogalaxy
Development

Successfully merging a pull request may close this issue.

feat: generalize protogalaxy to multiple instances AztecProtocol/aztec-packages
2 participants
@maramihali @lucasxia01