mod.rs
1 // Copyright (c) 2025-2026 ACDC Network 2 // This file is part of the alphavm library. 3 // 4 // Alpha Chain | Delta Chain Protocol 5 // International Monetary Graphite. 6 // 7 // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com). 8 // They built world-class ZK infrastructure. We installed the EASY button. 9 // Their cryptography: elegant. Our modifications: bureaucracy-compatible. 10 // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours. 11 // 12 // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0 13 // All modifications and new work: CC0 1.0 Universal Public Domain Dedication. 14 // No rights reserved. No permission required. No warranty. No refunds. 15 // 16 // https://creativecommons.org/publicdomain/zero/1.0/ 17 // SPDX-License-Identifier: CC0-1.0 18 19 use crate::{ 20 fft::DensePolynomial, 21 msm::variable_base::VariableBase, 22 polycommit::{kzg10, optional_rng::OptionalRng, PCError}, 23 srs::{UniversalProver, UniversalVerifier}, 24 AlgebraicSponge, 25 }; 26 use alphavm_curves::traits::{AffineCurve, PairingCurve, PairingEngine, ProjectiveCurve}; 27 use alphavm_fields::{One, Zero}; 28 use hashbrown::HashMap; 29 use itertools::Itertools; 30 31 use anyhow::{bail, ensure, Result}; 32 use rand::{RngCore, SeedableRng}; 33 use std::{ 34 borrow::Borrow, 35 collections::{BTreeMap, BTreeSet}, 36 convert::TryInto, 37 marker::PhantomData, 38 ops::Mul, 39 }; 40 41 mod data_structures; 42 pub use data_structures::*; 43 44 mod polynomial; 45 pub use polynomial::*; 46 47 /// Polynomial commitment based on [\[KZG10\]][kzg], with degree enforcement and 48 /// batching taken from [[MBKM19, “Sonic”]][sonic] (more precisely, their 49 /// counterparts in [[Gabizon19, “AuroraLight”]][al] that avoid negative G1 50 /// powers). The (optional) hiding property of the commitment scheme follows the 51 /// approach described in [[CHMMVW20, “Marlin”]][marlin]. 52 /// 53 /// [kzg]: http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf 54 /// [sonic]: https://eprint.iacr.org/2019/099 55 /// [al]: https://eprint.iacr.org/2019/601 56 /// [marlin]: https://eprint.iacr.org/2019/1047 57 #[derive(Clone, Debug)] 58 pub struct SonicKZG10<E: PairingEngine, S: AlgebraicSponge<E::Fq, 2>> { 59 _engine: PhantomData<(E, S)>, 60 } 61 62 impl<E: PairingEngine, S: AlgebraicSponge<E::Fq, 2>> SonicKZG10<E, S> { 63 pub fn load_srs(max_degree: usize) -> Result<UniversalParams<E>, PCError> { 64 kzg10::KZG10::load_srs(max_degree) 65 } 66 67 pub fn trim( 68 pp: &UniversalParams<E>, 69 supported_degree: usize, 70 supported_lagrange_sizes: impl IntoIterator<Item = usize>, 71 supported_hiding_bound: usize, 72 enforced_degree_bounds: Option<&[usize]>, 73 ) -> Result<(CommitterKey<E>, UniversalVerifier<E>)> { 74 let trim_time = start_timer!(|| "Trimming public parameters"); 75 let max_degree = pp.max_degree(); 76 77 let enforced_degree_bounds = enforced_degree_bounds.map(|bounds| { 78 let mut v = bounds.to_vec(); 79 v.sort_unstable(); 80 v.dedup(); 81 v 82 }); 83 84 let (shifted_powers_of_beta_g, shifted_powers_of_beta_times_gamma_g) = if let Some(enforced_degree_bounds) = 85 enforced_degree_bounds.as_ref() 86 { 87 if enforced_degree_bounds.is_empty() { 88 (None, None) 89 } else { 90 let highest_enforced_degree_bound = *enforced_degree_bounds.last().unwrap(); 91 if highest_enforced_degree_bound > supported_degree { 92 bail!( 93 "The highest enforced degree bound {highest_enforced_degree_bound} is larger than the supported degree {supported_degree}" 94 ); 95 } 96 97 let lowest_shift_degree = max_degree - highest_enforced_degree_bound; 98 99 let shifted_ck_time = start_timer!(|| format!( 100 "Constructing `shifted_powers_of_beta_g` of size {}", 101 max_degree - lowest_shift_degree + 1 102 )); 103 104 let shifted_powers_of_beta_g = pp.powers_of_beta_g(lowest_shift_degree, pp.max_degree() + 1)?; 105 let mut shifted_powers_of_beta_times_gamma_g = BTreeMap::new(); 106 // Also add degree 0. 107 for degree_bound in enforced_degree_bounds { 108 let shift_degree = max_degree - degree_bound; 109 // We have an additional degree in `powers_of_beta_times_gamma_g` beyond 110 // `powers_of_beta_g`. 111 let powers_for_degree_bound = pp 112 .powers_of_beta_times_gamma_g() 113 .range(shift_degree..max_degree.min(shift_degree + supported_hiding_bound) + 2) 114 .map(|(_k, v)| *v) 115 .collect(); 116 shifted_powers_of_beta_times_gamma_g.insert(*degree_bound, powers_for_degree_bound); 117 } 118 119 end_timer!(shifted_ck_time); 120 121 (Some(shifted_powers_of_beta_g), Some(shifted_powers_of_beta_times_gamma_g)) 122 } 123 } else { 124 (None, None) 125 }; 126 127 let powers_of_beta_g = pp.powers_of_beta_g(0, supported_degree + 1)?; 128 let powers_of_beta_times_gamma_g = pp 129 .powers_of_beta_times_gamma_g() 130 .range(0..=(supported_hiding_bound + 1)) 131 .map(|(_k, v)| *v) 132 .collect::<Vec<_>>(); 133 if powers_of_beta_times_gamma_g.len() != supported_hiding_bound + 2 { 134 return Err( 135 PCError::HidingBoundToolarge { hiding_poly_degree: supported_hiding_bound, num_powers: 0 }.into() 136 ); 137 } 138 139 let mut lagrange_bases_at_beta_g = BTreeMap::new(); 140 for size in supported_lagrange_sizes { 141 let lagrange_time = start_timer!(|| format!("Constructing `lagrange_bases` of size {size}")); 142 if !size.is_power_of_two() { 143 bail!("The Lagrange basis size ({size}) is not a power of two") 144 } 145 if size > pp.max_degree() + 1 { 146 bail!("The Lagrange basis size ({size}) is larger than the supported degree ({})", pp.max_degree() + 1) 147 } 148 let domain = crate::fft::EvaluationDomain::new(size).unwrap(); 149 let lagrange_basis_at_beta_g = pp.lagrange_basis(domain)?; 150 assert!(lagrange_basis_at_beta_g.len().is_power_of_two()); 151 lagrange_bases_at_beta_g.insert(domain.size(), lagrange_basis_at_beta_g); 152 end_timer!(lagrange_time); 153 } 154 155 let ck = CommitterKey { 156 powers_of_beta_g, 157 lagrange_bases_at_beta_g, 158 powers_of_beta_times_gamma_g, 159 shifted_powers_of_beta_g, 160 shifted_powers_of_beta_times_gamma_g, 161 enforced_degree_bounds, 162 }; 163 164 let vk = pp.to_universal_verifier()?; 165 166 end_timer!(trim_time); 167 Ok((ck, vk)) 168 } 169 170 /// Outputs commitments to `polynomials`. 171 /// 172 /// If `polynomials[i].is_hiding()`, then the `i`-th commitment is hiding 173 /// up to `polynomials.hiding_bound()` queries. 174 /// 175 /// `rng` should not be `None` if `polynomials[i].is_hiding() == true` for 176 /// any `i`. 177 /// 178 /// If for some `i`, `polynomials[i].is_hiding() == false`, then the 179 /// corresponding randomness is `Randomness<E>::empty()`. 180 /// 181 /// If for some `i`, `polynomials[i].degree_bound().is_some()`, then that 182 /// polynomial will have the corresponding degree bound enforced. 183 #[allow(clippy::format_push_string)] 184 pub fn commit<'b>( 185 universal_prover: &UniversalProver<E>, 186 ck: &CommitterUnionKey<E>, 187 polynomials: impl IntoIterator<Item = LabeledPolynomialWithBasis<'b, E::Fr>>, 188 rng: Option<&mut dyn RngCore>, 189 ) -> Result<(Vec<LabeledCommitment<Commitment<E>>>, Vec<Randomness<E>>), PCError> { 190 let rng = &mut OptionalRng(rng); 191 let commit_time = start_timer!(|| "Committing to polynomials"); 192 193 let mut pool = alphavm_utilities::ExecutionPool::<Result<_, _>>::new(); 194 for p in polynomials { 195 let seed = rng.0.as_mut().map(|r| { 196 let mut seed = [0u8; 32]; 197 r.fill_bytes(&mut seed); 198 seed 199 }); 200 201 kzg10::KZG10::<E>::check_degrees_and_bounds( 202 universal_prover.max_degree, 203 ck.enforced_degree_bounds.as_deref(), 204 p.clone(), 205 )?; 206 let degree_bound = p.degree_bound(); 207 let hiding_bound = p.hiding_bound(); 208 let label = p.label().to_string(); 209 210 pool.add_job(move || { 211 let mut rng = seed.map(rand::rngs::StdRng::from_seed); 212 add_to_trace!(|| "PC::Commit", || format!( 213 "Polynomial {} of degree {}, degree bound {:?}, and hiding bound {:?}", 214 label, 215 p.degree(), 216 degree_bound, 217 hiding_bound, 218 )); 219 220 let (comm, rand) = { 221 let rng_ref = rng.as_mut().map(|s| s as _); 222 match p.polynomial { 223 PolynomialWithBasis::Lagrange { evaluations } => { 224 let domain = crate::fft::EvaluationDomain::new(evaluations.evaluations.len()).unwrap(); 225 let lagrange_basis = ck 226 .lagrange_basis(domain) 227 .ok_or(PCError::UnsupportedLagrangeBasisSize(domain.size()))?; 228 assert!(domain.size().is_power_of_two()); 229 assert!(lagrange_basis.size().is_power_of_two()); 230 kzg10::KZG10::commit_lagrange( 231 &lagrange_basis, 232 &evaluations.evaluations, 233 hiding_bound, 234 rng_ref, 235 )? 236 } 237 PolynomialWithBasis::Monomial { polynomial, degree_bound } => { 238 let powers = if let Some(degree_bound) = degree_bound { 239 ck.shifted_powers_of_beta_g(degree_bound).unwrap() 240 } else { 241 ck.powers() 242 }; 243 244 kzg10::KZG10::commit(&powers, &polynomial, hiding_bound, rng_ref)? 245 } 246 } 247 }; 248 249 Ok((LabeledCommitment::new(label.to_string(), comm, degree_bound), rand)) 250 }); 251 } 252 let results: Vec<Result<_, PCError>> = pool.execute_all(); 253 254 let mut labeled_comms = Vec::with_capacity(results.len()); 255 let mut randomness = Vec::with_capacity(results.len()); 256 for result in results { 257 let (comm, rand) = result?; 258 labeled_comms.push(comm); 259 randomness.push(rand); 260 } 261 262 end_timer!(commit_time); 263 Ok((labeled_comms, randomness)) 264 } 265 266 pub fn combine_for_open<'a>( 267 universal_prover: &UniversalProver<E>, 268 ck: &CommitterUnionKey<E>, 269 labeled_polynomials: impl ExactSizeIterator<Item = &'a LabeledPolynomial<E::Fr>>, 270 rands: impl ExactSizeIterator<Item = &'a Randomness<E>>, 271 fs_rng: &mut S, 272 ) -> Result<(DensePolynomial<E::Fr>, Randomness<E>)> 273 where 274 Randomness<E>: 'a, 275 Commitment<E>: 'a, 276 { 277 ensure!(labeled_polynomials.len() == rands.len()); 278 let mut to_combine = Vec::with_capacity(labeled_polynomials.len()); 279 280 for (p, r) in labeled_polynomials.zip_eq(rands) { 281 let enforced_degree_bounds: Option<&[usize]> = ck.enforced_degree_bounds.as_deref(); 282 283 kzg10::KZG10::<E>::check_degrees_and_bounds(universal_prover.max_degree, enforced_degree_bounds, p)?; 284 let challenge = fs_rng.squeeze_short_nonnative_field_element::<E::Fr>(); 285 to_combine.push((challenge, p.polynomial().to_dense(), r)); 286 } 287 288 Ok(Self::combine_polynomials(to_combine)) 289 } 290 291 /// On input a list of labeled polynomials and a query set, `open` outputs a 292 /// proof of evaluation of the polynomials at the points in the query 293 /// set. 294 pub fn batch_open<'a>( 295 universal_prover: &UniversalProver<E>, 296 ck: &CommitterUnionKey<E>, 297 labeled_polynomials: impl ExactSizeIterator<Item = &'a LabeledPolynomial<E::Fr>>, 298 query_set: &QuerySet<E::Fr>, 299 rands: impl ExactSizeIterator<Item = &'a Randomness<E>>, 300 fs_rng: &mut S, 301 ) -> Result<BatchProof<E>> 302 where 303 Randomness<E>: 'a, 304 Commitment<E>: 'a, 305 { 306 ensure!(labeled_polynomials.len() == rands.len()); 307 let poly_rand: HashMap<_, _> = 308 labeled_polynomials.into_iter().zip_eq(rands).map(|(poly, r)| (poly.label(), (poly, r))).collect(); 309 310 let open_time = start_timer!(|| format!( 311 "Opening {} polynomials at query set of size {}", 312 poly_rand.len(), 313 query_set.len(), 314 )); 315 316 let mut query_to_labels_map = BTreeMap::new(); 317 318 for (label, (point_name, point)) in query_set.iter() { 319 let labels = query_to_labels_map.entry(point_name).or_insert((point, BTreeSet::new())); 320 labels.1.insert(label); 321 } 322 323 let mut pool = alphavm_utilities::ExecutionPool::<_>::with_capacity(query_to_labels_map.len()); 324 for (_point_name, (&query, labels)) in query_to_labels_map.into_iter() { 325 let mut query_polys = Vec::with_capacity(labels.len()); 326 let mut query_rands = Vec::with_capacity(labels.len()); 327 328 for label in labels { 329 let (polynomial, rand) = 330 poly_rand.get(label as &str).ok_or(PCError::MissingPolynomial { label: label.to_string() })?; 331 332 query_polys.push(*polynomial); 333 query_rands.push(*rand); 334 } 335 let (polynomial, rand) = 336 Self::combine_for_open(universal_prover, ck, query_polys.into_iter(), query_rands.into_iter(), fs_rng)?; 337 let _randomizer = fs_rng.squeeze_short_nonnative_field_element::<E::Fr>(); 338 339 pool.add_job(move || { 340 let proof_time = start_timer!(|| "Creating proof"); 341 let proof = kzg10::KZG10::open(&ck.powers(), &polynomial, query, &rand); 342 end_timer!(proof_time); 343 proof 344 }); 345 } 346 let batch_proof = pool.execute_all().into_iter().collect::<Result<_, _>>().map(BatchProof).map_err(Into::into); 347 end_timer!(open_time); 348 349 batch_proof 350 } 351 352 pub fn batch_check<'a>( 353 vk: &UniversalVerifier<E>, 354 commitments: impl IntoIterator<Item = &'a LabeledCommitment<Commitment<E>>>, 355 query_set: &QuerySet<E::Fr>, 356 values: &Evaluations<E::Fr>, 357 proof: &BatchProof<E>, 358 fs_rng: &mut S, 359 ) -> Result<bool> 360 where 361 Commitment<E>: 'a, 362 { 363 let commitments: BTreeMap<_, _> = commitments.into_iter().map(|c| (c.label().to_owned(), c)).collect(); 364 let batch_check_time = start_timer!(|| format!( 365 "Checking {} commitments at query set of size {}", 366 commitments.len(), 367 query_set.len(), 368 )); 369 let mut query_to_labels_map = BTreeMap::new(); 370 371 for (label, (point_name, point)) in query_set.iter() { 372 let labels = query_to_labels_map.entry(point_name).or_insert((point, BTreeSet::new())); 373 labels.1.insert(label); 374 } 375 376 assert_eq!(proof.0.len(), query_to_labels_map.len()); 377 378 let mut randomizer = E::Fr::one(); 379 380 let mut combined_comms = BTreeMap::new(); 381 let mut combined_witness = E::G1Projective::zero(); 382 let mut combined_adjusted_witness = E::G1Projective::zero(); 383 384 ensure!(query_to_labels_map.len() == proof.0.len()); 385 for ((_query_name, (query, labels)), p) in query_to_labels_map.into_iter().zip_eq(&proof.0) { 386 let mut comms_to_combine: Vec<&'_ LabeledCommitment<_>> = Vec::new(); 387 let mut values_to_combine = Vec::new(); 388 for label in labels.into_iter() { 389 let commitment = 390 commitments.get(label).ok_or(PCError::MissingPolynomial { label: label.to_string() })?; 391 392 let v_i = values 393 .get(&(label.clone(), *query)) 394 .ok_or(PCError::MissingEvaluation { label: label.to_string() })?; 395 396 comms_to_combine.push(commitment); 397 values_to_combine.push(*v_i); 398 } 399 400 Self::accumulate_elems( 401 &mut combined_comms, 402 &mut combined_witness, 403 &mut combined_adjusted_witness, 404 vk, 405 comms_to_combine.into_iter(), 406 *query, 407 values_to_combine.into_iter(), 408 p, 409 Some(randomizer), 410 fs_rng, 411 )?; 412 413 randomizer = fs_rng.squeeze_short_nonnative_field_element::<E::Fr>(); 414 } 415 416 let result = Self::check_elems(vk, combined_comms, combined_witness, combined_adjusted_witness); 417 end_timer!(batch_check_time); 418 result 419 } 420 421 pub fn open_combinations<'a>( 422 universal_prover: &UniversalProver<E>, 423 ck: &CommitterUnionKey<E>, 424 linear_combinations: impl IntoIterator<Item = &'a LinearCombination<E::Fr>>, 425 polynomials: impl IntoIterator<Item = LabeledPolynomial<E::Fr>>, 426 rands: impl IntoIterator<Item = &'a Randomness<E>>, 427 query_set: &QuerySet<E::Fr>, 428 fs_rng: &mut S, 429 ) -> Result<BatchLCProof<E>> 430 where 431 Randomness<E>: 'a, 432 Commitment<E>: 'a, 433 { 434 let label_map = 435 polynomials.into_iter().zip_eq(rands).map(|(p, r)| (p.to_label(), (p, r))).collect::<BTreeMap<_, _>>(); 436 437 let mut lc_polynomials = Vec::new(); 438 let mut lc_randomness = Vec::new(); 439 let mut lc_info = Vec::new(); 440 441 for lc in linear_combinations { 442 let lc_label = lc.label().to_string(); 443 let mut poly = DensePolynomial::zero(); 444 let mut randomness = Randomness::empty(); 445 let mut degree_bound = None; 446 let mut hiding_bound = None; 447 448 let num_polys = lc.len(); 449 // We filter out l.is_one() entries because those constants are not committed to 450 // and used directly by the verifier. 451 for (coeff, label) in lc.iter().filter(|(_, l)| !l.is_one()) { 452 let label: &String = label.try_into().expect("cannot be one!"); 453 let (cur_poly, cur_rand) = 454 label_map.get(label as &str).ok_or(PCError::MissingPolynomial { label: label.to_string() })?; 455 if let Some(cur_degree_bound) = cur_poly.degree_bound() { 456 if num_polys != 1 { 457 bail!(PCError::EquationHasDegreeBounds(lc_label)); 458 } 459 assert!(coeff.is_one(), "Coefficient must be one for degree-bounded equations"); 460 if let Some(old_degree_bound) = degree_bound { 461 assert_eq!(old_degree_bound, cur_degree_bound) 462 } else { 463 degree_bound = cur_poly.degree_bound(); 464 } 465 } 466 // Some(_) > None, always. 467 hiding_bound = core::cmp::max(hiding_bound, cur_poly.hiding_bound()); 468 poly += (*coeff, cur_poly.polynomial()); 469 randomness += (*coeff, *cur_rand); 470 } 471 472 let lc_poly = LabeledPolynomial::new(lc_label.clone(), poly, degree_bound, hiding_bound); 473 lc_polynomials.push(lc_poly); 474 lc_randomness.push(randomness); 475 lc_info.push((lc_label, degree_bound)); 476 } 477 478 let proof = 479 Self::batch_open(universal_prover, ck, lc_polynomials.iter(), query_set, lc_randomness.iter(), fs_rng)?; 480 481 Ok(BatchLCProof { proof }) 482 } 483 484 /// Checks that `values` are the true evaluations at `query_set` of the 485 /// polynomials committed in `labeled_commitments`. 486 pub fn check_combinations<'a>( 487 vk: &UniversalVerifier<E>, 488 linear_combinations: impl IntoIterator<Item = &'a LinearCombination<E::Fr>>, 489 commitments: impl IntoIterator<Item = &'a LabeledCommitment<Commitment<E>>>, 490 query_set: &QuerySet<E::Fr>, 491 evaluations: &Evaluations<E::Fr>, 492 proof: &BatchLCProof<E>, 493 fs_rng: &mut S, 494 ) -> Result<bool> 495 where 496 Commitment<E>: 'a, 497 { 498 let BatchLCProof { proof } = proof; 499 let label_comm_map = commitments.into_iter().map(|c| (c.label(), c)).collect::<BTreeMap<_, _>>(); 500 501 let mut lc_commitments = Vec::new(); 502 let mut lc_info = Vec::new(); 503 let mut evaluations = evaluations.clone(); 504 505 let lc_processing_time = start_timer!(|| "Combining commitments"); 506 for lc in linear_combinations { 507 let lc_label = lc.label().to_string(); 508 let num_polys = lc.len(); 509 510 let mut degree_bound = None; 511 let mut coeffs_and_comms = Vec::new(); 512 513 for (coeff, label) in lc.iter() { 514 if label.is_one() { 515 for ((label, _), ref mut eval) in evaluations.iter_mut() { 516 if label == &lc_label { 517 **eval -= coeff; 518 } 519 } 520 } else { 521 let label: &String = label.try_into().unwrap(); 522 let &cur_comm = label_comm_map 523 .get(label as &str) 524 .ok_or(PCError::MissingPolynomial { label: label.to_string() })?; 525 526 if cur_comm.degree_bound().is_some() { 527 if num_polys != 1 || !coeff.is_one() { 528 bail!(PCError::EquationHasDegreeBounds(lc_label)); 529 } 530 degree_bound = cur_comm.degree_bound(); 531 } 532 coeffs_and_comms.push((*coeff, cur_comm.commitment())); 533 } 534 } 535 let lc_time = start_timer!(|| format!("Combining {num_polys} commitments for {lc_label}")); 536 lc_commitments.push(Self::combine_commitments(coeffs_and_comms)); 537 end_timer!(lc_time); 538 lc_info.push((lc_label, degree_bound)); 539 } 540 end_timer!(lc_processing_time); 541 542 let combined_comms_norm_time = start_timer!(|| "Normalizing commitments"); 543 let comms = Self::normalize_commitments(lc_commitments); 544 ensure!(lc_info.len() == comms.len()); 545 let lc_commitments = lc_info 546 .into_iter() 547 .zip_eq(comms) 548 .map(|((label, d), c)| LabeledCommitment::new(label, c, d)) 549 .collect::<Vec<_>>(); 550 end_timer!(combined_comms_norm_time); 551 552 Self::batch_check(vk, &lc_commitments, query_set, &evaluations, proof, fs_rng) 553 } 554 } 555 556 impl<E: PairingEngine, S: AlgebraicSponge<E::Fq, 2>> SonicKZG10<E, S> { 557 fn combine_polynomials<'a, B: Borrow<DensePolynomial<E::Fr>>>( 558 coeffs_polys_rands: impl IntoIterator<Item = (E::Fr, B, &'a Randomness<E>)>, 559 ) -> (DensePolynomial<E::Fr>, Randomness<E>) { 560 let mut combined_poly = DensePolynomial::zero(); 561 let mut combined_rand = Randomness::empty(); 562 for (coeff, poly, rand) in coeffs_polys_rands { 563 let poly = poly.borrow(); 564 if coeff.is_one() { 565 combined_poly += poly; 566 combined_rand += rand; 567 } else { 568 combined_poly += (coeff, poly); 569 combined_rand += (coeff, rand); 570 } 571 } 572 (combined_poly, combined_rand) 573 } 574 575 /// MSM for `commitments` and `coeffs` 576 fn combine_commitments<'a>( 577 coeffs_and_comms: impl IntoIterator<Item = (E::Fr, &'a Commitment<E>)>, 578 ) -> E::G1Projective { 579 let (scalars, bases): (Vec<_>, Vec<_>) = coeffs_and_comms.into_iter().map(|(f, c)| (f.into(), c.0)).unzip(); 580 VariableBase::msm(&bases, &scalars) 581 } 582 583 fn normalize_commitments(commitments: Vec<E::G1Projective>) -> impl ExactSizeIterator<Item = Commitment<E>> { 584 let comms = E::G1Projective::batch_normalization_into_affine(commitments); 585 comms.into_iter().map(|c| kzg10::KZGCommitment(c)) 586 } 587 } 588 589 impl<E: PairingEngine, S: AlgebraicSponge<E::Fq, 2>> SonicKZG10<E, S> { 590 #[allow(clippy::too_many_arguments)] 591 fn accumulate_elems<'a>( 592 combined_comms: &mut BTreeMap<Option<usize>, E::G1Projective>, 593 combined_witness: &mut E::G1Projective, 594 combined_adjusted_witness: &mut E::G1Projective, 595 vk: &UniversalVerifier<E>, 596 commitments: impl ExactSizeIterator<Item = &'a LabeledCommitment<Commitment<E>>>, 597 point: E::Fr, 598 values: impl ExactSizeIterator<Item = E::Fr>, 599 proof: &kzg10::KZGProof<E>, 600 randomizer: Option<E::Fr>, 601 fs_rng: &mut S, 602 ) -> Result<()> { 603 let acc_time = start_timer!(|| "Accumulating elements"); 604 // Keeps track of running combination of values 605 let mut combined_values = E::Fr::zero(); 606 607 // Iterates through all of the commitments and accumulates common degree_bound 608 // elements in a BTreeMap 609 ensure!(commitments.len() == values.len()); 610 for (labeled_comm, value) in commitments.into_iter().zip_eq(values) { 611 let acc_timer = start_timer!(|| format!("Accumulating {}", labeled_comm.label())); 612 let curr_challenge = fs_rng.squeeze_short_nonnative_field_element::<E::Fr>(); 613 614 combined_values += &(value * curr_challenge); 615 616 let comm = labeled_comm.commitment(); 617 let degree_bound = labeled_comm.degree_bound(); 618 619 // Applying opening challenge and randomness (used in batch_checking) 620 let coeff = randomizer.unwrap_or_else(E::Fr::one) * curr_challenge; 621 let comm_with_challenge: E::G1Projective = comm.0.mul(coeff); 622 623 // Accumulate values in the BTreeMap 624 *combined_comms.entry(degree_bound).or_insert_with(E::G1Projective::zero) += &comm_with_challenge; 625 end_timer!(acc_timer); 626 } 627 628 // Push expected results into list of elems. Power will be the negative of the 629 // expected power 630 let mut bases = vec![vk.vk.g, -proof.w]; 631 let mut coeffs = vec![combined_values, point]; 632 if let Some(random_v) = proof.random_v { 633 bases.push(vk.vk.gamma_g); 634 coeffs.push(random_v); 635 } 636 *combined_witness += if let Some(randomizer) = randomizer { 637 coeffs.iter_mut().for_each(|c| *c *= randomizer); 638 proof.w.mul(randomizer) 639 } else { 640 proof.w.to_projective() 641 }; 642 let coeffs = coeffs.into_iter().map(|c| c.into()).collect::<Vec<_>>(); 643 *combined_adjusted_witness += VariableBase::msm(&bases, &coeffs); 644 end_timer!(acc_time); 645 Ok(()) 646 } 647 648 fn check_elems( 649 vk: &UniversalVerifier<E>, 650 combined_comms: BTreeMap<Option<usize>, E::G1Projective>, 651 combined_witness: E::G1Projective, 652 combined_adjusted_witness: E::G1Projective, 653 ) -> Result<bool> { 654 let check_time = start_timer!(|| "Checking elems"); 655 let mut g1_projective_elems = Vec::with_capacity(combined_comms.len() + 2); 656 let mut g2_prepared_elems = Vec::with_capacity(combined_comms.len() + 2); 657 658 for (degree_bound, comm) in combined_comms.into_iter() { 659 let shift_power = if let Some(degree_bound) = degree_bound { 660 // Find the appropriate prepared shift for the degree bound. 661 vk.prepared_negative_powers_of_beta_h 662 .get(°ree_bound) 663 .cloned() 664 .ok_or(PCError::UnsupportedDegreeBound(degree_bound))? 665 } else { 666 vk.vk.prepared_h.clone() 667 }; 668 669 g1_projective_elems.push(comm); 670 g2_prepared_elems.push(shift_power); 671 } 672 673 g1_projective_elems.push(-combined_adjusted_witness); 674 g2_prepared_elems.push(vk.vk.prepared_h.clone()); 675 676 g1_projective_elems.push(-combined_witness); 677 g2_prepared_elems.push(vk.vk.prepared_beta_h.clone()); 678 679 let g1_prepared_elems_iter = E::G1Projective::batch_normalization_into_affine(g1_projective_elems) 680 .into_iter() 681 .map(|a| a.prepare()) 682 .collect::<Vec<_>>(); 683 684 ensure!(g1_prepared_elems_iter.len() == g2_prepared_elems.len()); 685 let g1_g2_prepared = g1_prepared_elems_iter.iter().zip_eq(g2_prepared_elems.iter()); 686 let is_one: bool = E::product_of_pairings(g1_g2_prepared).is_one(); 687 end_timer!(check_time); 688 Ok(is_one) 689 } 690 } 691 692 #[cfg(test)] 693 mod tests { 694 #![allow(non_camel_case_types)] 695 696 use super::{CommitterKey, SonicKZG10}; 697 use crate::{crypto_hash::PoseidonSponge, polycommit::test_templates::*}; 698 use alphavm_curves::bls12_377::{Bls12_377, Fq}; 699 use alphavm_utilities::{rand::TestRng, FromBytes, ToBytes}; 700 701 use rand::distributions::Distribution; 702 703 type Sponge = PoseidonSponge<Fq, 2, 1>; 704 type PC_Bls12_377 = SonicKZG10<Bls12_377, Sponge>; 705 706 #[test] 707 fn test_committer_key_serialization() { 708 let rng = &mut TestRng::default(); 709 let max_degree = rand::distributions::Uniform::from(8..=64).sample(rng); 710 let supported_degree = rand::distributions::Uniform::from(1..=max_degree).sample(rng); 711 712 let lagrange_size = |d: usize| if d.is_power_of_two() { d } else { d.next_power_of_two() >> 1 }; 713 714 let pp = PC_Bls12_377::load_srs(max_degree).unwrap(); 715 716 let (ck, _vk) = PC_Bls12_377::trim(&pp, supported_degree, [lagrange_size(supported_degree)], 0, None).unwrap(); 717 718 let ck_bytes = ck.to_bytes_le().unwrap(); 719 let ck_recovered: CommitterKey<Bls12_377> = FromBytes::read_le(&ck_bytes[..]).unwrap(); 720 let ck_recovered_bytes = ck_recovered.to_bytes_le().unwrap(); 721 722 assert_eq!(&ck_bytes, &ck_recovered_bytes); 723 } 724 725 #[test] 726 fn test_single_poly() { 727 single_poly_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 728 } 729 730 #[test] 731 fn test_quadratic_poly_degree_bound_multiple_queries() { 732 quadratic_poly_degree_bound_multiple_queries_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 733 } 734 735 #[test] 736 fn test_linear_poly_degree_bound() { 737 linear_poly_degree_bound_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 738 } 739 740 #[test] 741 fn test_single_poly_degree_bound() { 742 single_poly_degree_bound_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 743 } 744 745 #[test] 746 fn test_single_poly_degree_bound_multiple_queries() { 747 single_poly_degree_bound_multiple_queries_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 748 } 749 750 #[test] 751 fn test_two_polys_degree_bound_single_query() { 752 two_polys_degree_bound_single_query_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 753 } 754 755 #[test] 756 fn test_full_end_to_end() { 757 full_end_to_end_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 758 println!("Finished bls12-377"); 759 } 760 761 #[test] 762 fn test_single_equation() { 763 single_equation_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 764 println!("Finished bls12-377"); 765 } 766 767 #[test] 768 fn test_two_equation() { 769 two_equation_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 770 println!("Finished bls12-377"); 771 } 772 773 #[test] 774 fn test_two_equation_degree_bound() { 775 two_equation_degree_bound_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 776 println!("Finished bls12-377"); 777 } 778 779 #[test] 780 fn test_full_end_to_end_equation() { 781 full_end_to_end_equation_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 782 println!("Finished bls12-377"); 783 } 784 785 #[test] 786 #[should_panic] 787 fn test_bad_degree_bound() { 788 bad_degree_bound_test::<Bls12_377, Sponge>().expect("test failed for bls12-377"); 789 println!("Finished bls12-377"); 790 } 791 792 #[test] 793 fn test_lagrange_commitment() { 794 crate::polycommit::test_templates::lagrange_test_template::<Bls12_377, Sponge>() 795 .expect("test failed for bls12-377"); 796 println!("Finished bls12-377"); 797 } 798 }