mpdpf.rs 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127
  1. use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
  2. use dpf::mpdpf::{DummyMpDpf, MultiPointDpf, SmartMpDpf};
  3. use dpf::spdpf::{DummySpDpf, HalfTreeSpDpf};
  4. use rand::{thread_rng, Rng};
  5. use utils::field::{Fp, FromHash};
  6. use utils::hash::AesHashFunction;
  7. const LOG_DOMAIN_SIZES: [u32; 4] = [8, 12, 16, 20];
  8. fn setup_points<F: FromHash>(log_domain_size: u32) -> (Vec<u64>, Vec<F>) {
  9. assert_eq!(log_domain_size % 2, 0);
  10. let domain_size = 1 << log_domain_size;
  11. let number_points = 1 << (log_domain_size / 2);
  12. let alphas = {
  13. let mut alphas = Vec::<u64>::with_capacity(number_points);
  14. while alphas.len() < number_points {
  15. let x = thread_rng().gen_range(0..domain_size);
  16. match alphas.as_slice().binary_search(&x) {
  17. Ok(_) => continue,
  18. Err(i) => alphas.insert(i, x),
  19. }
  20. }
  21. alphas
  22. };
  23. let betas: Vec<F> = (0..number_points)
  24. .map(|x| F::hash_bytes(&x.to_be_bytes()))
  25. .collect();
  26. (alphas, betas)
  27. }
  28. fn bench_mpdpf_keygen<MPDPF, F>(c: &mut Criterion, dpf_name: &str, field_name: &str)
  29. where
  30. MPDPF: MultiPointDpf<Value = F>,
  31. F: Copy + FromHash,
  32. {
  33. let mut group = c.benchmark_group(format!("{}-{}-keygen", dpf_name, field_name));
  34. for log_domain_size in LOG_DOMAIN_SIZES.iter() {
  35. let (alphas, betas) = setup_points(*log_domain_size);
  36. group.bench_with_input(
  37. BenchmarkId::new("without-precomputation", log_domain_size),
  38. log_domain_size,
  39. |b, &log_domain_size| {
  40. let mpdpf = MPDPF::new(1 << log_domain_size, 1 << (log_domain_size / 2));
  41. b.iter(|| {
  42. let (_key_0, _key_1) = mpdpf.generate_keys(&alphas, &betas);
  43. });
  44. },
  45. );
  46. group.bench_with_input(
  47. BenchmarkId::new("with-precomputation", log_domain_size),
  48. log_domain_size,
  49. |b, &log_domain_size| {
  50. let mut mpdpf = MPDPF::new(1 << log_domain_size, 1 << (log_domain_size / 2));
  51. mpdpf.precompute();
  52. b.iter(|| {
  53. let (_key_0, _key_1) = mpdpf.generate_keys(&alphas, &betas);
  54. });
  55. },
  56. );
  57. }
  58. group.finish();
  59. }
  60. fn bench_mpdpf_evaluate_domain<MPDPF, F>(c: &mut Criterion, dpf_name: &str, field_name: &str)
  61. where
  62. MPDPF: MultiPointDpf<Value = F>,
  63. F: Copy + FromHash,
  64. {
  65. let mut group = c.benchmark_group(format!("{}-{}-evaluate_domain", dpf_name, field_name));
  66. for log_domain_size in LOG_DOMAIN_SIZES.iter() {
  67. let (alphas, betas) = setup_points(*log_domain_size);
  68. group.bench_with_input(
  69. BenchmarkId::new("without-precomputation", log_domain_size),
  70. log_domain_size,
  71. |b, &log_domain_size| {
  72. let mpdpf = MPDPF::new(1 << log_domain_size, 1 << (log_domain_size / 2));
  73. let (key_0, _key_1) = mpdpf.generate_keys(&alphas, &betas);
  74. b.iter(|| {
  75. mpdpf.evaluate_domain(&key_0);
  76. });
  77. },
  78. );
  79. group.bench_with_input(
  80. BenchmarkId::new("with-precomputation", log_domain_size),
  81. log_domain_size,
  82. |b, &log_domain_size| {
  83. let mut mpdpf = MPDPF::new(1 << log_domain_size, 1 << (log_domain_size / 2));
  84. mpdpf.precompute();
  85. let (key_0, _key_1) = mpdpf.generate_keys(&alphas, &betas);
  86. b.iter(|| {
  87. mpdpf.evaluate_domain(&key_0);
  88. });
  89. },
  90. );
  91. }
  92. group.finish();
  93. }
  94. fn bench_mpdpf<MPDPF, F>(c: &mut Criterion, dpf_name: &str, field_name: &str)
  95. where
  96. MPDPF: MultiPointDpf<Value = F>,
  97. F: Copy + FromHash,
  98. {
  99. bench_mpdpf_keygen::<MPDPF, F>(c, dpf_name, field_name);
  100. bench_mpdpf_evaluate_domain::<MPDPF, F>(c, dpf_name, field_name);
  101. }
  102. fn bench_all_mpdpf(c: &mut Criterion) {
  103. bench_mpdpf::<DummyMpDpf<Fp>, _>(c, "DummyMpDpf", "Fp");
  104. bench_mpdpf::<SmartMpDpf<Fp, DummySpDpf<Fp>, AesHashFunction<u16>>, _>(
  105. c,
  106. "SmartMpDpf<Dummy,Aes>",
  107. "Fp",
  108. );
  109. bench_mpdpf::<SmartMpDpf<Fp, HalfTreeSpDpf<Fp>, AesHashFunction<u16>>, _>(
  110. c,
  111. "SmartMpDpf<HalfTree,Aes>",
  112. "Fp",
  113. );
  114. }
  115. criterion_group!(
  116. name = benches;
  117. config = Criterion::default().sample_size(10);
  118. targets = bench_all_mpdpf
  119. );
  120. criterion_main!(benches);