Adding telescope benchmarks #55

rrtoledo · 2024-11-06T13:13:16Z

Content

Relates to #54

Depends on #105

rrtoledo · 2024-11-11T13:26:39Z

Should we remove the benchmarks checking the variance of the number of repetitions (the dfs_bound is so high that we never repeat, which makes criterion fails when generating the plot), or should we lower dfs_bound to observe some variances in retry_counter?
-> Do we want the retry_counter to increase?

Some local tests showed me that we would need to reduce dfs_bound by a factor 100. Choosing this number would feel a bit arbitrary (Is this the right number for all lambdas...?) so I am not sure it is the best option.

tolikzinovyev · 2024-11-11T15:37:43Z

@tolikzinovyev @curiecrypt @djetchev

Should we remove the benchmarks checking the variance of the number of repetitions (the dfs_bound is so high that we never repeat, which makes criterion fails when generating the plot), or should we lower dfs_bound to observe some variances in retry_counter? -> Do we want the retry_counter to increase?

Some local tests showed me that we would need to reduce dfs_bound by a factor 100. Choosing this number would feel a bit arbitrary (Is this the right number for all lambdas...?) so I am not sure it is the best option.

Removing the benchmark sounds reasonable!

rrtoledo · 2024-11-13T11:17:43Z

I find @tolikzinovyev idea the best. What do you think @curiecrypt @djetchev ?

tolikzinovyev · 2024-11-14T05:22:28Z

I will not have time to review this PR before Monday, unfortunately, since it is a pretty large.

tolikzinovyev

Nice usage of advanced criterion features. Left high-level comments.

benches/centralized_telescope.rs

benches/criterion_helpers.rs

src/centralized_telescope/algorithm.rs

benches/centralized_telescope.rs

curiecrypt

I think it seems pretty good and mature. I left a few comments and could go for another round after the conversations are resolved.

Cargo.toml

benches/centralized_telescope.rs

benches/criterion_helpers.rs

src/centralized_telescope/algorithm.rs

benches/common/test_vectors.rs

curiecrypt

I just reviewed the centralized_telescope benches.
Just very minor suggestions, other than that, it looks very good.

benches/common/criterion_helpers.rs

README.md

benches/centralized_telescope/proof_size.rs

benches/centralized_telescope/number_steps.rs

benches/centralized_telescope/proving_time.rs

benches/centralized_telescope/verifying_time.rs

Co-authored-by: curiecrypt <[email protected]>

curiecrypt

LGTM 👍

tolikzinovyev

The code structure, benchmarks duration and variable names have definitely improved, thank you!

tolikzinovyev · 2024-12-27T16:03:36Z

src/centralized_telescope/algorithm.rs

+    }
+}
+
+/// Prove routing


There is a typo. But also there is no need to document internal functions if the documentation doesn't say more than the function name.

tolikzinovyev · 2024-12-27T16:04:50Z

src/centralized_telescope/algorithm.rs

@@ -52,6 +51,35 @@ pub(super) fn verify(setup: &Setup, proof: &Proof) -> bool {
    proof_hash(setup, &round)
 }

+/// Internal module for tests and benchmarks


Suggested change

/// Internal module for tests and benchmarks

/// Internal module for tests and benchmarks. Do not use.

tolikzinovyev · 2024-12-27T16:18:38Z

src/centralized_telescope/wrapper.rs

@@ -8,7 +8,8 @@ use crate::utils::types::Element;
 /// The main centralized Telescope struct with prove and verify functions.
 #[derive(Debug, Clone, Copy)]
 pub struct Wrapper {
-    setup: Setup,
+    /// Centralized telescope internal parameters
+    pub setup: Setup,


I think this shouldn't be public. Instead of calling CentralizedTelescope::create(), we can run parameter derivation and use CentralizedTelescope::create_unsafe().

tolikzinovyev · 2024-12-27T16:22:35Z

benches/centralized_telescope/verifying_time.rs

+    );
+}
+
+criterion_main!(criterion_group::centralized_verifying_time,);


Suggested change

criterion_main!(criterion_group::centralized_verifying_time,);

criterion_main!(criterion_group::centralized_verifying_time);

tolikzinovyev · 2024-12-27T16:46:41Z

benches/centralized_telescope/proof_size.rs

@@ -0,0 +1,42 @@
+//! Benchmarking the proof size of the Centralized Telescope scheme


I think this originally wasn't part of the PR. Could we postpone it to a later PR?

tolikzinovyev · 2024-12-27T16:55:13Z

benches/common/criterion_helpers.rs

+            BenchmarkId::new(
+                bench_name,
+                format!(
+                    "params={{λsec:{}, λrel:{}, Sp:{} ({}%), n_p:{}, n_f:{}}}",


Example of current output:
params={λsec:80, λrel:80, Sp:1000 (80%), n_p:80, n_f:60}.

As before, I think this is confusing because S_p is the size of prover's input and it's actually 800. Suggest the following output instead.
params={λsec:80, λrel:80, |Sp|:800 (80%), n_p:80, n_f:60}

tolikzinovyev · 2024-12-27T16:56:33Z

benches/common/criterion_helpers.rs

+            BenchmarkId::new(
+                bench_name,
+                format!(
+                    "params={{λsec:{}, λrel:{}, Sp:{} ({}%), n_p:{}, n_f:{}}}",


nit: also suggest a space after colons

tolikzinovyev · 2024-12-27T17:21:16Z

src/centralized_telescope/algorithm.rs

+}
+
+/// Prove routing
+fn prove_routine(setup: &Setup, prover_set: &[Element]) -> (u64, u64, Option<Proof>) {


We don't use the number of retries anywhere, right? If not, let's not return it.

tolikzinovyev · 2024-12-27T19:42:49Z

benches/centralized_telescope/number_steps.rs

+    let mut total_steps = 0u64;
+    for _ in 0..n {
+        // Setup
+        let (mut dataset, telescope) = setup(&mut rng, param);


I still really think the setup should run before this loop. I think this loop (where n is typically from 1 to 4 in our benchmarks) is intended to filter out external noises like unpredictable scheduling of processes by the OS. It is not intended to reduce the inherent variance of the measured value (here, number of dfs steps). By running the setup inside the loop, the measurement distribution becomes more concentrated around the average than it actually is.

I ran some experiments. This is for Centralized - Steps/Prove/params={λsec:64, λrel:64, Sp:1000 (90%), n_p:90, n_f:60}.

Original code:
$Screenshot 2024-12-27 at 12-27-12 Centralized - Steps_Prove_params {λsec 64 λrel 64 Sp 1000 (90%) n_p 90 n_f 60} - Criterion rs$

Setup is moved to before the for loop:
$Screenshot 2024-12-27 at 12-33-21 Centralized - Steps_Prove_params {λsec 64 λrel 64 Sp 1000 (90%) n_p 90 n_f 60} - Criterion rs$

Difference:
$Screenshot 2024-12-27 at 12-33-55 Centralized - Steps_Prove_params {λsec 64 λrel 64 Sp 1000 (90%) n_p 90 n_f 60} - Criterion rs$

You can see that moving the setup outside the loop makes the PDF graph wider which is what it should be.

Interestingly, the mean also changes by a lot, +34%. This is due to a small number of samples, currently 100. I ran the benchmark one more time:
$Screenshot 2024-12-27 at 12-51-49 Centralized - Steps_Prove_params {λsec 64 λrel 64 Sp 1000 (90%) n_p 90 n_f 60} - Criterion rs$

Changing the number of samples to 1000 fixes the crazy variance. Perhaps, we should do this too.

tolikzinovyev · 2024-12-27T20:07:41Z

benches/common/test_vectors.rs

+    use super::super::criterion_helpers::centralized::BenchParam;
+
+    /// This case corresponds to the minimum security requirements with optimistic set_size
+    const LOW_PARAM: BenchParam = BenchParam {


Suppose I want to run a benchmark with particular n_p, n_f and |S_p| (size of prover's input). Currently, I would need to think hard to figure out how to correctly set the percentages and set_cardinality here.

A better option could be to have

pub struct BenchParam { pub lambda_sec: f64, pub lambda_rel: f64, pub set_cardinality: u64, pub set_size: u64, pub lower_bound: u64, }

and have utility functions in this file that generate these structs based on percentages. There would be no low / mid / high cases in criterion_helpers.rs benchmarks(), instead they would be generated here.

What do you think?

rrtoledo added the enhancement New feature or request label Nov 6, 2024

rrtoledo self-assigned this Nov 6, 2024

rrtoledo marked this pull request as draft November 6, 2024 13:13

rrtoledo linked an issue Nov 6, 2024 that may be closed by this pull request

Adding centralized benchmarks #54

Open

rrtoledo force-pushed the raph@bench-centralized branch 2 times, most recently from de0fb2a to 88d69ab Compare November 11, 2024 12:47

rrtoledo marked this pull request as ready for review November 11, 2024 13:22

rrtoledo requested review from tolikzinovyev, djetchev and curiecrypt November 13, 2024 11:17

tolikzinovyev reviewed Nov 19, 2024

View reviewed changes

curiecrypt reviewed Nov 20, 2024

View reviewed changes

rrtoledo requested review from curiecrypt and tolikzinovyev November 26, 2024 15:27

rrtoledo force-pushed the raph@bench-centralized branch from 14f4fb0 to 3fdfe36 Compare December 5, 2024 20:08

rrtoledo marked this pull request as draft December 5, 2024 20:08

rrtoledo force-pushed the raph@bench-centralized branch 2 times, most recently from 9f13518 to e27b0d4 Compare December 10, 2024 19:16

rrtoledo marked this pull request as ready for review December 12, 2024 12:01

rrtoledo force-pushed the raph@bench-centralized branch 4 times, most recently from b540e25 to a54996e Compare December 12, 2024 16:15

rrtoledo commented Dec 12, 2024

View reviewed changes

benches/common/test_vectors.rs Outdated Show resolved Hide resolved

rrtoledo changed the title ~~Adding benchmarks~~ Centralized Telescope - Adding benchmarks Dec 13, 2024

rrtoledo force-pushed the raph@bench-centralized branch from 63a4cef to 07fc567 Compare December 13, 2024 11:09

rrtoledo force-pushed the raph@bench-centralized branch from 5d2b638 to 5ab0b6f Compare December 13, 2024 15:25

curiecrypt requested changes Dec 13, 2024

View reviewed changes

rrtoledo force-pushed the raph@bench-centralized branch from 5ab0b6f to cba63c9 Compare December 13, 2024 15:29

rrtoledo changed the title ~~Adding telescope & lottery benchmarks~~ Adding telescope benchmarks Dec 13, 2024

rrtoledo mentioned this pull request Dec 13, 2024

Bench lottery #107

Open

rrtoledo and others added 22 commits December 16, 2024 11:03

Tests/utils: renaming utils as common as menionned in rust book

8582d73

Benches/common: Adding criterion helpers

897d7e0

Centralized_helper/algo: adding public bench function

66f9d8c

Centralized_telescope/wrapper: Exposing wrapper fields

b24e002

Benches/common/test_vectors: Adding test vectors

6149e80

Benches/centralized_telescope/utils.rs: Adding bench setup

f8bc6d3

Benches/centralized_telescope: Adding step bench

5efd6de

Benches/common/mod.rs: Removing unused constant warnings

0c1a75d

Benches/centralized_telescope: Adding proving time bench

950e06a

Benches/centralized_telescope: Adding verification time bench

64e453d

Benches/centralized_telescope: Adding proving size bench

1514824

Update benches/common/test_vectors.rs

c03cba8

benches/centralized: misc

c6e0996

CentralizedTelescope: Putting bench in internal module

80601ae

Update benches/centralized_telescope/number_steps.rs

bbca150

Co-authored-by: curiecrypt <[email protected]>

Update benches/centralized_telescope/number_steps.rs

d57b12d

Co-authored-by: curiecrypt <[email protected]>

Update benches/centralized_telescope/verifying_time.rs

e02723a

Co-authored-by: curiecrypt <[email protected]>

Update benches/centralized_telescope/verifying_time.rs

9834875

Co-authored-by: curiecrypt <[email protected]>

Update benches/centralized_telescope/proving_time.rs

b589039

Co-authored-by: curiecrypt <[email protected]>

Update benches/centralized_telescope/proving_time.rs

a713434

Co-authored-by: curiecrypt <[email protected]>

Aligning | in proof size

1e9533d

Benches: Using longer variable names

f422cdb

rrtoledo force-pushed the raph@bench-centralized branch from 350cc03 to f422cdb Compare December 16, 2024 11:06

curiecrypt approved these changes Dec 16, 2024

View reviewed changes

tolikzinovyev reviewed Dec 27, 2024

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Adding telescope benchmarks #55

Adding telescope benchmarks #55

rrtoledo commented Nov 6, 2024 •

edited

Loading

rrtoledo commented Nov 11, 2024

tolikzinovyev commented Nov 11, 2024

rrtoledo commented Nov 13, 2024

tolikzinovyev commented Nov 14, 2024

tolikzinovyev left a comment

curiecrypt left a comment

curiecrypt left a comment

curiecrypt left a comment

tolikzinovyev left a comment

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

tolikzinovyev Dec 27, 2024

	/// Internal module for tests and benchmarks
	/// Internal module for tests and benchmarks. Do not use.

	criterion_main!(criterion_group::centralized_verifying_time,);
	criterion_main!(criterion_group::centralized_verifying_time);

		@@ -0,0 +1,42 @@
		//! Benchmarking the proof size of the Centralized Telescope scheme

Adding telescope benchmarks #55

Are you sure you want to change the base?

Adding telescope benchmarks #55

Conversation

rrtoledo commented Nov 6, 2024 • edited Loading

Content

rrtoledo commented Nov 11, 2024

tolikzinovyev commented Nov 11, 2024

rrtoledo commented Nov 13, 2024

tolikzinovyev commented Nov 14, 2024

tolikzinovyev left a comment

Choose a reason for hiding this comment

curiecrypt left a comment

Choose a reason for hiding this comment

curiecrypt left a comment

Choose a reason for hiding this comment

curiecrypt left a comment

Choose a reason for hiding this comment

tolikzinovyev left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rrtoledo commented Nov 6, 2024 •

edited

Loading