varuna.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 super::Certificate; 20 use crate::{ 21 fft::EvaluationDomain, 22 polycommit::sonic_pc::{ 23 Commitment, 24 CommitterUnionKey, 25 Evaluations, 26 LabeledCommitment, 27 QuerySet, 28 Randomness, 29 SonicKZG10, 30 }, 31 r1cs::{ConstraintSynthesizer, SynthesisError}, 32 snark::varuna::{ 33 ahp::{AHPError, AHPForR1CS, CircuitId, EvaluationsProvider}, 34 proof, 35 prover, 36 witness_label, 37 CircuitProvingKey, 38 CircuitVerifyingKey, 39 Proof, 40 SNARKMode, 41 UniversalSRS, 42 VarunaVersion, 43 }, 44 srs::UniversalVerifier, 45 AlgebraicSponge, 46 SNARKError, 47 SNARK, 48 }; 49 use alphavm_curves::PairingEngine; 50 use alphavm_fields::{One, PrimeField, ToConstraintField, Zero}; 51 use alphavm_utilities::{dev_eprintln, dev_println, to_bytes_le, ToBytes}; 52 use rand::RngCore; 53 54 use anyhow::{anyhow, bail, ensure, Result}; 55 use core::marker::PhantomData; 56 use itertools::Itertools; 57 use rand::{CryptoRng, Rng}; 58 use std::{borrow::Borrow, collections::BTreeMap, ops::Deref, sync::Arc}; 59 60 use crate::srs::UniversalProver; 61 62 /// The Varuna proof system. 63 #[derive(Clone, Debug)] 64 pub struct VarunaSNARK<E: PairingEngine, FS: AlgebraicSponge<E::Fq, 2>, SM: SNARKMode>( 65 #[doc(hidden)] PhantomData<(E, FS, SM)>, 66 ); 67 68 impl<E: PairingEngine, FS: AlgebraicSponge<E::Fq, 2>, SM: SNARKMode> VarunaSNARK<E, FS, SM> { 69 /// The personalization string for this protocol. 70 /// Used to personalize the Fiat-Shamir RNG. 71 pub const PROTOCOL_NAME: &'static [u8] = b"VARUNA-2023"; 72 73 // TODO: implement optimizations resulting from batching 74 // (e.g. computing a common set of Lagrange powers, FFT precomputations, 75 // etc) 76 pub fn batch_circuit_setup<C: ConstraintSynthesizer<E::Fr>>( 77 universal_srs: &UniversalSRS<E>, 78 circuits: &[&C], 79 ) -> Result<Vec<(CircuitProvingKey<E, SM>, CircuitVerifyingKey<E>)>> { 80 let index_time = start_timer!(|| "Varuna::CircuitSetup"); 81 82 let universal_prover = &universal_srs.to_universal_prover()?; 83 84 let mut circuit_keys = Vec::with_capacity(circuits.len()); 85 for circuit in circuits { 86 let mut indexed_circuit = AHPForR1CS::<_, SM>::index(*circuit)?; 87 // TODO: Add check that c is in the correct mode. 88 // Ensure the universal SRS supports the circuit size. 89 universal_srs.download_powers_for(0..indexed_circuit.max_degree()?).map_err(|e| { 90 anyhow!("Failed to download powers for degree {}: {e}", indexed_circuit.max_degree().unwrap()) 91 })?; 92 let coefficient_support = AHPForR1CS::<E::Fr, SM>::get_degree_bounds(&indexed_circuit.index_info)?; 93 94 // Varuna only needs degree 2 random polynomials. 95 let supported_hiding_bound = 1; 96 let supported_lagrange_sizes = [].into_iter(); // TODO: consider removing lagrange_bases_at_beta_g from CommitterKey 97 let (committer_key, _) = SonicKZG10::<E, FS>::trim( 98 universal_srs, 99 indexed_circuit.max_degree()?, 100 supported_lagrange_sizes, 101 supported_hiding_bound, 102 Some(coefficient_support.as_slice()), 103 )?; 104 105 let ck = CommitterUnionKey::union(std::iter::once(&committer_key)); 106 107 let commit_time = start_timer!(|| format!("Commit to index polynomials for {}", indexed_circuit.id)); 108 let setup_rng = None::<&mut dyn RngCore>; // We do not randomize the commitments 109 110 let (mut circuit_commitments, commitment_randomnesses): (_, _) = SonicKZG10::<E, FS>::commit( 111 universal_prover, 112 &ck, 113 indexed_circuit.interpolate_matrix_evals()?.map(Into::into), 114 setup_rng, 115 )?; 116 let empty_randomness = Randomness::<E>::empty(); 117 ensure!(commitment_randomnesses.iter().all(|r| r == &empty_randomness)); 118 end_timer!(commit_time); 119 120 circuit_commitments.sort_by(|c1, c2| c1.label().cmp(c2.label())); 121 let circuit_commitments = circuit_commitments.into_iter().map(|c| *c.commitment()).collect(); 122 indexed_circuit.prune_row_col_evals(); 123 let circuit_verifying_key = CircuitVerifyingKey { 124 circuit_info: indexed_circuit.index_info, 125 circuit_commitments, 126 id: indexed_circuit.id, 127 }; 128 let circuit_proving_key = CircuitProvingKey { 129 circuit_verifying_key: circuit_verifying_key.clone(), 130 circuit: Arc::new(indexed_circuit), 131 committer_key: Arc::new(committer_key), 132 }; 133 circuit_keys.push((circuit_proving_key, circuit_verifying_key)); 134 } 135 136 end_timer!(index_time); 137 Ok(circuit_keys) 138 } 139 140 fn init_sponge<'a>( 141 fs_parameters: &FS::Parameters, 142 inputs_and_batch_sizes: &BTreeMap<CircuitId, (usize, &[Vec<E::Fr>])>, 143 circuit_commitments: impl Iterator<Item = &'a [crate::polycommit::sonic_pc::Commitment<E>]>, 144 ) -> FS { 145 let mut sponge = FS::new_with_parameters(fs_parameters); 146 sponge.absorb_bytes(Self::PROTOCOL_NAME); 147 for (batch_size, inputs) in inputs_and_batch_sizes.values() { 148 sponge.absorb_bytes(&(*batch_size as u64).to_le_bytes()); 149 for input in inputs.iter() { 150 sponge.absorb_nonnative_field_elements(input.iter().copied()); 151 } 152 } 153 for circuit_specific_commitments in circuit_commitments { 154 sponge.absorb_native_field_elements(circuit_specific_commitments); 155 } 156 sponge 157 } 158 159 fn init_sponge_for_certificate( 160 fs_parameters: &FS::Parameters, 161 verifying_key: &CircuitVerifyingKey<E>, 162 ) -> Result<FS> { 163 let mut sponge = FS::new_with_parameters(fs_parameters); 164 sponge.absorb_bytes(&to_bytes_le![&Self::PROTOCOL_NAME]?); 165 sponge.absorb_bytes(&verifying_key.circuit_info.to_bytes_le()?); 166 sponge.absorb_native_field_elements(&verifying_key.circuit_commitments); 167 sponge.absorb_bytes(&verifying_key.id.0); 168 Ok(sponge) 169 } 170 171 fn absorb_labeled_with_sums( 172 comms: &[LabeledCommitment<Commitment<E>>], 173 sums: &[prover::MatrixSums<E::Fr>], 174 sponge: &mut FS, 175 ) { 176 let commitments: Vec<_> = comms.iter().map(|c| *c.commitment()).collect(); 177 Self::absorb_with_sums(&commitments, sums, sponge) 178 } 179 180 fn absorb_labeled(comms: &[LabeledCommitment<Commitment<E>>], sponge: &mut FS) { 181 let commitments: Vec<_> = comms.iter().map(|c| *c.commitment()).collect(); 182 Self::absorb(&commitments, sponge); 183 } 184 185 fn absorb(commitments: &[Commitment<E>], sponge: &mut FS) { 186 let sponge_time = start_timer!(|| "Absorbing commitments"); 187 sponge.absorb_native_field_elements(commitments); 188 end_timer!(sponge_time); 189 } 190 191 fn absorb_with_sums(commitments: &[Commitment<E>], sums: &[prover::MatrixSums<E::Fr>], sponge: &mut FS) { 192 let sponge_time = start_timer!(|| "Absorbing commitments and message"); 193 Self::absorb(commitments, sponge); 194 Self::absorb_sums(sums, sponge); 195 end_timer!(sponge_time); 196 } 197 198 fn absorb_sums(sums: &[prover::MatrixSums<E::Fr>], sponge: &mut FS) { 199 for sum in sums.iter() { 200 sponge.absorb_nonnative_field_elements([sum.sum_a, sum.sum_b, sum.sum_c]); 201 } 202 } 203 } 204 205 impl<E: PairingEngine, FS, SM> SNARK for VarunaSNARK<E, FS, SM> 206 where 207 E::Fr: PrimeField, 208 E::Fq: PrimeField, 209 FS: AlgebraicSponge<E::Fq, 2>, 210 SM: SNARKMode, 211 { 212 type BaseField = E::Fq; 213 type Certificate = Certificate<E>; 214 type FSParameters = FS::Parameters; 215 type FiatShamirRng = FS; 216 type Proof = Proof<E>; 217 type ProvingKey = CircuitProvingKey<E, SM>; 218 type ScalarField = E::Fr; 219 type UniversalProver = UniversalProver<E>; 220 type UniversalSRS = UniversalSRS<E>; 221 type UniversalVerifier = UniversalVerifier<E>; 222 type VerifierInput = [E::Fr]; 223 type VerifyingKey = CircuitVerifyingKey<E>; 224 225 fn universal_setup(max_degree: usize) -> Result<Self::UniversalSRS> { 226 let setup_time = start_timer!(|| { format!("Varuna::UniversalSetup with max_degree {max_degree}",) }); 227 let srs = SonicKZG10::<E, FS>::load_srs(max_degree).map_err(Into::into); 228 end_timer!(setup_time); 229 srs 230 } 231 232 /// Generates the circuit proving and verifying keys. 233 /// This is a deterministic algorithm that anyone can rerun. 234 fn circuit_setup<C: ConstraintSynthesizer<E::Fr>>( 235 universal_srs: &Self::UniversalSRS, 236 circuit: &C, 237 ) -> Result<(Self::ProvingKey, Self::VerifyingKey)> { 238 let mut circuit_keys = Self::batch_circuit_setup::<C>(universal_srs, &[circuit])?; 239 ensure!(circuit_keys.len() == 1); 240 Ok(circuit_keys.pop().unwrap()) 241 } 242 243 /// Prove that the verifying key commitments commit to the indexed circuit's 244 /// polynomials 245 fn prove_vk( 246 universal_prover: &Self::UniversalProver, 247 fs_parameters: &Self::FSParameters, 248 verifying_key: &Self::VerifyingKey, 249 proving_key: &Self::ProvingKey, 250 ) -> Result<Self::Certificate> { 251 // Initialize sponge 252 let mut sponge = Self::init_sponge_for_certificate(fs_parameters, verifying_key)?; 253 // Compute challenges for linear combination, and the point to evaluate the 254 // polynomials at. The linear combination requires `num_polynomials - 1` 255 // coefficients (since the first coeff is 1), and so we squeeze out 256 // `num_polynomials` points. 257 let mut challenges = sponge.squeeze_nonnative_field_elements(verifying_key.circuit_commitments.len()); 258 let point = challenges.pop().ok_or(anyhow!("Failed to squeeze random element"))?; 259 let one = E::Fr::one(); 260 let linear_combination_challenges = core::iter::once(&one).chain(challenges.iter()); 261 262 let circuit_id = std::iter::once(&verifying_key.id); 263 let circuit_poly_info = AHPForR1CS::<E::Fr, SM>::index_polynomial_info(circuit_id); 264 265 // We will construct a linear combination and provide a proof of evaluation of 266 // the lc at `point`. 267 let mut lc = crate::polycommit::sonic_pc::LinearCombination::empty("circuit_check"); 268 for (label, &c) in circuit_poly_info.keys().zip(linear_combination_challenges) { 269 lc.add(c, label.clone()); 270 } 271 272 let query_set = QuerySet::from_iter([("circuit_check".into(), ("challenge".into(), point))]); 273 let committer_key = CommitterUnionKey::union(std::iter::once(proving_key.committer_key.as_ref())); 274 275 let empty_randomness = vec![Randomness::<E>::empty(); 12]; 276 let certificate = SonicKZG10::<E, FS>::open_combinations( 277 universal_prover, 278 &committer_key, 279 &[lc], 280 proving_key.circuit.interpolate_matrix_evals()?, 281 &empty_randomness, 282 &query_set, 283 &mut sponge, 284 )?; 285 286 Ok(Self::Certificate::new(certificate)) 287 } 288 289 /// Verify that the verifying key commitments commit to the indexed 290 /// circuit's polynomials Verify that the verifying key's circuit_info 291 /// is correct 292 fn verify_vk<C: ConstraintSynthesizer<Self::ScalarField>>( 293 universal_verifier: &Self::UniversalVerifier, 294 fs_parameters: &Self::FSParameters, 295 circuit: &C, 296 verifying_key: &Self::VerifyingKey, 297 certificate: &Self::Certificate, 298 ) -> Result<bool> { 299 // Ensure the VerifyingKey encodes the expected circuit. 300 let circuit_id = &verifying_key.id; 301 let state = AHPForR1CS::<E::Fr, SM>::index_helper(circuit)?; 302 if state.index_info != verifying_key.circuit_info { 303 bail!("Circuit info mismatch, expected {:?}, got {:?}", verifying_key.circuit_info, state.index_info); 304 } 305 if state.id != *circuit_id { 306 bail!("Circuit ID mismatch, expected {:?}, got {:?}.", circuit_id, state.id); 307 } 308 309 // Make sure certificate is not hiding 310 if certificate.pc_proof.is_hiding() { 311 bail!("Certificate should not be hiding"); 312 } 313 314 // Initialize sponge. 315 let mut sponge = Self::init_sponge_for_certificate(fs_parameters, verifying_key)?; 316 317 // Compute challenges for linear combination, and the point to evaluate the 318 // polynomials at. The linear combination requires `num_polynomials - 1` 319 // coefficients (since the first coeff is 1), and so we squeeze out 320 // `num_polynomials` points. 321 let mut challenges = sponge.squeeze_nonnative_field_elements(verifying_key.circuit_commitments.len()); 322 let point = challenges.pop().ok_or(anyhow!("Failed to squeeze random element"))?; 323 let combiners = core::iter::once(E::Fr::one()).chain(challenges); 324 325 // We will construct a linear combination and provide a proof of evaluation of 326 // the lc at `point`. 327 let (lc, evaluation) = 328 AHPForR1CS::<E::Fr, SM>::evaluate_index_polynomials(state, circuit_id, point, combiners)?; 329 330 ensure!(verifying_key.circuit_commitments.len() == lc.terms.len()); 331 let commitments = verifying_key 332 .iter() 333 .cloned() 334 .zip_eq(lc.terms.keys()) 335 .map(|(c, label)| LabeledCommitment::new(format!("{label:?}"), c, None)) 336 .collect_vec(); 337 let evaluations = Evaluations::from_iter([(("circuit_check".into(), point), evaluation)]); 338 let query_set = QuerySet::from_iter([("circuit_check".into(), ("challenge".into(), point))]); 339 340 SonicKZG10::<E, FS>::check_combinations( 341 universal_verifier, 342 &[lc], 343 &commitments, 344 &query_set, 345 &evaluations, 346 &certificate.pc_proof, 347 &mut sponge, 348 ) 349 } 350 351 /// This is the main entrypoint for creating proofs. 352 /// You can find a specification of the prover algorithm in: 353 /// <https://github.com/ProvableHQ/protocol-docs> 354 fn prove_batch<C: ConstraintSynthesizer<E::Fr>, R: Rng + CryptoRng>( 355 universal_prover: &Self::UniversalProver, 356 fs_parameters: &Self::FSParameters, 357 varuna_version: VarunaVersion, 358 keys_to_constraints: &BTreeMap<&CircuitProvingKey<E, SM>, &[C]>, 359 zk_rng: &mut R, 360 ) -> Result<Self::Proof> { 361 let prover_time = start_timer!(|| "Varuna::Prover"); 362 if keys_to_constraints.is_empty() { 363 bail!(SNARKError::EmptyBatch); 364 } 365 366 let mut circuits_to_constraints = BTreeMap::new(); 367 for (pk, constraints) in keys_to_constraints { 368 circuits_to_constraints.insert(pk.circuit.deref(), *constraints); 369 } 370 let prover_state = AHPForR1CS::<_, SM>::init_prover(&circuits_to_constraints, zk_rng)?; 371 372 // extract information from the prover key and state to consume in further 373 // calculations 374 let mut batch_sizes = BTreeMap::new(); 375 let mut circuit_infos = BTreeMap::new(); 376 let mut inputs_and_batch_sizes = BTreeMap::new(); 377 let mut total_instances = 0usize; 378 let mut public_inputs = BTreeMap::new(); // inputs need to live longer than the rest of prover_state 379 let num_unique_circuits = keys_to_constraints.len(); 380 let mut circuit_ids = Vec::with_capacity(num_unique_circuits); 381 for pk in keys_to_constraints.keys() { 382 let batch_size = prover_state.batch_size(&pk.circuit).ok_or(anyhow!("Batch size not found."))?; 383 let public_input = prover_state.public_inputs(&pk.circuit).ok_or(anyhow!("Public input not found."))?; 384 let padded_public_input = 385 prover_state.padded_public_inputs(&pk.circuit).ok_or(anyhow!("Padded public input not found."))?; 386 let circuit_id = pk.circuit.id; 387 batch_sizes.insert(circuit_id, batch_size); 388 circuit_infos.insert(circuit_id, &pk.circuit_verifying_key.circuit_info); 389 inputs_and_batch_sizes.insert(circuit_id, (batch_size, padded_public_input)); 390 public_inputs.insert(circuit_id, public_input); 391 total_instances = total_instances.saturating_add(batch_size); 392 393 circuit_ids.push(circuit_id); 394 } 395 ensure!(prover_state.total_instances == total_instances); 396 397 let committer_key = CommitterUnionKey::union(keys_to_constraints.keys().map(|pk| pk.committer_key.deref())); 398 399 let circuit_commitments = 400 keys_to_constraints.keys().map(|pk| pk.circuit_verifying_key.circuit_commitments.as_slice()); 401 402 let mut sponge = Self::init_sponge(fs_parameters, &inputs_and_batch_sizes, circuit_commitments.clone()); 403 404 // -------------------------------------------------------------------- 405 // First round 406 407 let prover_state = AHPForR1CS::<_, SM>::prover_first_round(prover_state, zk_rng)?; 408 409 let first_round_comm_time = start_timer!(|| "Committing to first round polys"); 410 let (first_commitments, first_commitment_randomnesses) = { 411 let first_round_oracles = prover_state.first_round_oracles.as_ref().unwrap(); 412 SonicKZG10::<E, FS>::commit( 413 universal_prover, 414 &committer_key, 415 first_round_oracles.iter().map(Into::into), 416 SM::ZK.then_some(zk_rng), 417 )? 418 }; 419 end_timer!(first_round_comm_time); 420 421 Self::absorb_labeled(&first_commitments, &mut sponge); 422 423 let (verifier_first_message, verifier_state) = AHPForR1CS::<_, SM>::verifier_first_round( 424 &batch_sizes, 425 &circuit_infos, 426 prover_state.max_constraint_domain, 427 prover_state.max_variable_domain, 428 prover_state.max_non_zero_domain, 429 &mut sponge, 430 )?; 431 // -------------------------------------------------------------------- 432 433 // -------------------------------------------------------------------- 434 // Second round 435 436 let (second_oracles, prover_state) = 437 AHPForR1CS::<_, SM>::prover_second_round(&verifier_first_message, prover_state, zk_rng)?; 438 439 let second_round_comm_time = start_timer!(|| "Committing to second round polys"); 440 let (second_commitments, second_commitment_randomnesses) = SonicKZG10::<E, FS>::commit( 441 universal_prover, 442 &committer_key, 443 second_oracles.iter().map(Into::into), 444 SM::ZK.then_some(zk_rng), 445 )?; 446 end_timer!(second_round_comm_time); 447 448 Self::absorb_labeled(&second_commitments, &mut sponge); 449 450 let (verifier_second_msg, verifier_state) = 451 AHPForR1CS::<_, SM>::verifier_second_round(verifier_state, &mut sponge, varuna_version)?; 452 // -------------------------------------------------------------------- 453 454 // -------------------------------------------------------------------- 455 // Preparation for third round 456 457 let (prover_prepare_third_message, prover_state, verifier_prepare_third_msg, verifier_state) = { 458 match varuna_version { 459 VarunaVersion::V1 => (None, prover_state, None, verifier_state), 460 VarunaVersion::V2 => { 461 let (prover_prepare_third_message, prover_state) = AHPForR1CS::<_, SM>::prover_prepare_third_round( 462 &verifier_first_message, 463 &verifier_second_msg, 464 prover_state, 465 zk_rng, 466 )?; 467 468 Self::absorb_sums( 469 &prover_prepare_third_message.sums.clone().into_iter().flatten().collect_vec(), 470 &mut sponge, 471 ); 472 473 let (verifier_prepare_third_msg, verifier_state) = 474 AHPForR1CS::<_, SM>::verifier_prepare_third_round( 475 verifier_state, 476 &batch_sizes, 477 &circuit_infos, 478 &mut sponge, 479 )?; 480 481 (Some(prover_prepare_third_message), prover_state, Some(verifier_prepare_third_msg), verifier_state) 482 } 483 } 484 }; 485 // -------------------------------------------------------------------- 486 487 // -------------------------------------------------------------------- 488 // Third round 489 490 let (prover_third_message, third_oracles, prover_state) = AHPForR1CS::<_, SM>::prover_third_round( 491 &verifier_first_message, 492 &verifier_second_msg, 493 &verifier_prepare_third_msg, 494 prover_state, 495 zk_rng, 496 varuna_version, 497 )?; 498 499 let third_round_comm_time = start_timer!(|| "Committing to third round polys"); 500 let (third_commitments, third_commitment_randomnesses) = SonicKZG10::<E, FS>::commit( 501 universal_prover, 502 &committer_key, 503 third_oracles.iter().map(Into::into), 504 SM::ZK.then_some(zk_rng), 505 )?; 506 end_timer!(third_round_comm_time); 507 508 match varuna_version { 509 VarunaVersion::V1 => { 510 let prover_third_message = prover_third_message 511 .clone() 512 .ok_or_else(|| anyhow!("Expected prover to contribute sums in the third round."))?; 513 if prover_prepare_third_message.is_some() { 514 return Err(anyhow!("Expected prover to not contribute sums in the prepare third round."))?; 515 } 516 Self::absorb_labeled_with_sums( 517 &third_commitments, 518 &prover_third_message.sums.into_iter().flatten().collect_vec(), 519 &mut sponge, 520 ); 521 } 522 VarunaVersion::V2 => { 523 if prover_third_message.is_some() { 524 return Err(anyhow!("Expected prover to not contribute sums in the third round."))?; 525 } 526 Self::absorb_labeled(&third_commitments, &mut sponge); 527 } 528 } 529 530 // Extract the prover's third message to be used in the verifier's third round. 531 let prover_third_message = match varuna_version { 532 VarunaVersion::V1 => prover_third_message, 533 VarunaVersion::V2 => prover_prepare_third_message, 534 } 535 .ok_or_else(|| anyhow!("Prover did not contribute sums in the expected round."))?; 536 537 let (verifier_third_msg, verifier_state) = 538 AHPForR1CS::<_, SM>::verifier_third_round(verifier_state, &mut sponge)?; 539 // -------------------------------------------------------------------- 540 541 // -------------------------------------------------------------------- 542 // Fourth round 543 544 let (prover_fourth_message, fourth_oracles, mut prover_state) = 545 AHPForR1CS::<_, SM>::prover_fourth_round(&verifier_second_msg, &verifier_third_msg, prover_state, zk_rng)?; 546 547 let fourth_round_comm_time = start_timer!(|| "Committing to fourth round polys"); 548 let (fourth_commitments, fourth_commitment_randomnesses) = SonicKZG10::<E, FS>::commit( 549 universal_prover, 550 &committer_key, 551 fourth_oracles.iter().map(Into::into), 552 SM::ZK.then_some(zk_rng), 553 )?; 554 end_timer!(fourth_round_comm_time); 555 556 Self::absorb_labeled_with_sums(&fourth_commitments, &prover_fourth_message.sums, &mut sponge); 557 558 let (verifier_fourth_msg, verifier_state) = 559 AHPForR1CS::<_, SM>::verifier_fourth_round(verifier_state, &mut sponge)?; 560 // -------------------------------------------------------------------- 561 562 // We take out values from state before they are consumed. 563 let first_round_oracles = prover_state.first_round_oracles.take().unwrap(); 564 let index_a_polys = 565 prover_state.circuit_specific_states.values_mut().flat_map(|s| s.a_polys.take().unwrap()).collect_vec(); 566 let index_b_polys = 567 prover_state.circuit_specific_states.values_mut().flat_map(|s| s.b_polys.take().unwrap()).collect_vec(); 568 569 // -------------------------------------------------------------------- 570 // Fifth round 571 let fifth_oracles = AHPForR1CS::<_, SM>::prover_fifth_round(verifier_fourth_msg, prover_state, zk_rng)?; 572 573 let fifth_round_comm_time = start_timer!(|| "Committing to fifth round polys"); 574 let (fifth_commitments, fifth_commitment_randomnesses) = SonicKZG10::<E, FS>::commit( 575 universal_prover, 576 &committer_key, 577 fifth_oracles.iter().map(Into::into), 578 SM::ZK.then_some(zk_rng), 579 )?; 580 end_timer!(fifth_round_comm_time); 581 582 Self::absorb_labeled(&fifth_commitments, &mut sponge); 583 584 let verifier_state = AHPForR1CS::<_, SM>::verifier_fifth_round(verifier_state, &mut sponge)?; 585 // -------------------------------------------------------------------- 586 587 // Gather prover polynomials in one vector. 588 let polynomials: Vec<_> = index_a_polys 589 .into_iter() 590 .chain(index_b_polys) 591 .chain(first_round_oracles.into_iter()) 592 .chain(second_oracles.into_iter()) 593 .chain(third_oracles.into_iter()) 594 .chain(fourth_oracles.into_iter()) 595 .chain(fifth_oracles.into_iter()) 596 .collect(); 597 ensure!( 598 polynomials.len() 599 == num_unique_circuits * 6 + // numerator and denominator for each matrix sumcheck 600 AHPForR1CS::<E::Fr, SM>::num_first_round_oracles(total_instances) + 601 AHPForR1CS::<E::Fr, SM>::num_second_round_oracles() + 602 AHPForR1CS::<E::Fr, SM>::num_third_round_oracles() + 603 AHPForR1CS::<E::Fr, SM>::num_fourth_round_oracles(num_unique_circuits) + 604 AHPForR1CS::<E::Fr, SM>::num_fifth_round_oracles() 605 ); 606 607 // Gather commitments in one vector. 608 let witness_comm_len = if SM::ZK { first_commitments.len() - 1 } else { first_commitments.len() }; 609 let mask_poly = SM::ZK.then(|| *first_commitments[witness_comm_len].commitment()); 610 let witness_commitments = first_commitments[..witness_comm_len] 611 .iter() 612 .map(|c| proof::WitnessCommitments { w: *c.commitment() }) 613 .collect_vec(); 614 let fourth_commitments_chunked = fourth_commitments.chunks_exact(3); 615 let (g_a_commitments, g_b_commitments, g_c_commitments) = fourth_commitments_chunked 616 .map(|c| (*c[0].commitment(), *c[1].commitment(), *c[2].commitment())) 617 .multiunzip(); 618 619 #[rustfmt::skip] 620 let commitments = proof::Commitments { 621 witness_commitments, 622 mask_poly, 623 h_0: *second_commitments[0].commitment(), 624 g_1: *third_commitments[0].commitment(), 625 h_1: *third_commitments[1].commitment(), 626 g_a_commitments, 627 g_b_commitments, 628 g_c_commitments, 629 h_2: *fifth_commitments[0].commitment(), 630 }; 631 632 // Gather commitment randomness together. 633 let indexer_randomness = vec![Randomness::<E>::empty(); 6 * num_unique_circuits]; 634 let commitment_randomnesses: Vec<Randomness<E>> = indexer_randomness 635 .into_iter() 636 .chain(first_commitment_randomnesses) 637 .chain(second_commitment_randomnesses) 638 .chain(third_commitment_randomnesses) 639 .chain(fourth_commitment_randomnesses) 640 .chain(fifth_commitment_randomnesses) 641 .collect(); 642 643 let empty_randomness = Randomness::<E>::empty(); 644 if SM::ZK { 645 ensure!(commitment_randomnesses.iter().any(|r| r != &empty_randomness)); 646 } else { 647 ensure!(commitment_randomnesses.iter().all(|r| r == &empty_randomness)); 648 } 649 650 // Compute the AHP verifier's query set. 651 let (query_set, verifier_state) = AHPForR1CS::<_, SM>::verifier_query_set(verifier_state); 652 let lc_s = AHPForR1CS::<_, SM>::construct_linear_combinations( 653 &public_inputs, 654 &polynomials, 655 &prover_third_message, 656 &prover_fourth_message, 657 &verifier_state, 658 varuna_version, 659 )?; 660 661 let eval_time = start_timer!(|| "Evaluating linear combinations over query set"); 662 let mut evaluations = std::collections::BTreeMap::new(); 663 for (label, (_, point)) in query_set.to_set() { 664 if !AHPForR1CS::<E::Fr, SM>::LC_WITH_ZERO_EVAL.contains(&label.as_str()) { 665 let lc = lc_s.get(&label).ok_or_else(|| AHPError::MissingEval(label.to_string()))?; 666 let evaluation = polynomials.get_lc_eval(lc, point)?; 667 evaluations.insert(label, evaluation); 668 } 669 } 670 671 let evaluations = proof::Evaluations::from_map(&evaluations, batch_sizes.clone()); 672 end_timer!(eval_time); 673 674 sponge.absorb_nonnative_field_elements(evaluations.to_field_elements()); 675 676 let pc_proof = SonicKZG10::<E, FS>::open_combinations( 677 universal_prover, 678 &committer_key, 679 lc_s.values(), 680 polynomials, 681 &commitment_randomnesses, 682 &query_set.to_set(), 683 &mut sponge, 684 )?; 685 686 let proof = Proof::<E>::new( 687 batch_sizes, 688 commitments, 689 evaluations, 690 prover_third_message, 691 prover_fourth_message, 692 pc_proof, 693 )?; 694 proof.check_batch_sizes()?; 695 ensure!(proof.pc_proof.is_hiding() == SM::ZK); 696 697 end_timer!(prover_time); 698 Ok(proof) 699 } 700 701 /// This is the main entrypoint for verifying proofs. 702 /// You can find a specification of the verifier algorithm in: 703 /// <https://github.com/ProvableHQ/protocol-docs> 704 fn verify_batch<B: Borrow<Self::VerifierInput>>( 705 universal_verifier: &Self::UniversalVerifier, 706 fs_parameters: &Self::FSParameters, 707 varuna_version: VarunaVersion, 708 keys_to_inputs: &BTreeMap<&Self::VerifyingKey, &[B]>, 709 proof: &Self::Proof, 710 ) -> Result<bool> { 711 if keys_to_inputs.is_empty() { 712 bail!(SNARKError::EmptyBatch); 713 } 714 715 proof.check_batch_sizes()?; 716 let batch_sizes_vec = proof.batch_sizes(); 717 let mut batch_sizes = BTreeMap::new(); 718 for (i, (vk, public_inputs_i)) in keys_to_inputs.iter().enumerate() { 719 batch_sizes.insert(vk.id, batch_sizes_vec[i]); 720 721 if public_inputs_i.is_empty() { 722 bail!(SNARKError::EmptyBatch); 723 } 724 725 if public_inputs_i.len() != batch_sizes_vec[i] { 726 bail!(SNARKError::BatchSizeMismatch); 727 } 728 } 729 730 // collect values into structures for our calculations 731 let mut max_num_constraints = 0; 732 let mut max_num_variables = 0; 733 let mut max_non_zero_domain = None; 734 let mut public_inputs = BTreeMap::new(); 735 let mut padded_public_vec = Vec::with_capacity(keys_to_inputs.len()); 736 let mut inputs_and_batch_sizes = BTreeMap::new(); 737 let mut input_domains = BTreeMap::new(); 738 let mut circuit_infos = BTreeMap::new(); 739 let mut circuit_ids = Vec::with_capacity(keys_to_inputs.len()); 740 for (&vk, &public_inputs_i) in keys_to_inputs.iter() { 741 max_num_constraints = max_num_constraints.max(vk.circuit_info.num_constraints); 742 max_num_variables = max_num_variables.max(vk.circuit_info.num_public_and_private_variables); 743 744 let non_zero_domains = AHPForR1CS::<_, SM>::cmp_non_zero_domains(&vk.circuit_info, max_non_zero_domain)?; 745 max_non_zero_domain = non_zero_domains.max_non_zero_domain; 746 747 let input_domain = EvaluationDomain::<E::Fr>::new(vk.circuit_info.num_public_inputs) 748 .ok_or(anyhow!("Failed to create EvaluationDomain from num_public_inputs"))?; 749 input_domains.insert(vk.id, input_domain); 750 751 let input_fields = public_inputs_i 752 .iter() 753 .map(|input| { 754 let input = input.borrow().to_field_elements()?; 755 ensure!(input.len() > 0); 756 ensure!(input[0] == E::Fr::one()); 757 if input.len() > input_domain.size() { 758 bail!(SNARKError::PublicInputSizeMismatch); 759 } 760 Ok(input) 761 }) 762 .collect::<Result<Vec<_>, _>>()?; 763 764 let (padded_public_inputs_i, parsed_public_inputs_i): (Vec<_>, Vec<_>) = { 765 input_fields 766 .iter() 767 .map(|input| { 768 let input_len = input.len().max(input_domain.size()); 769 let mut new_input = Vec::with_capacity(input_len); 770 new_input.extend_from_slice(input); 771 new_input.resize(input_len, E::Fr::zero()); 772 dev_println!("Number of padded public variables: {}", new_input.len()); 773 let unformatted = prover::ConstraintSystem::unformat_public_input(&new_input); 774 (new_input, unformatted) 775 }) 776 .unzip() 777 }; 778 let circuit_id = vk.id; 779 public_inputs.insert(circuit_id, parsed_public_inputs_i); 780 padded_public_vec.push(padded_public_inputs_i); 781 circuit_infos.insert(circuit_id, &vk.circuit_info); 782 circuit_ids.push(circuit_id); 783 } 784 for (i, (vk, &batch_size)) in keys_to_inputs.keys().zip(batch_sizes.values()).enumerate() { 785 inputs_and_batch_sizes.insert(vk.id, (batch_size, padded_public_vec[i].as_slice())); 786 } 787 let max_constraint_domain = 788 EvaluationDomain::<E::Fr>::new(max_num_constraints).ok_or(SynthesisError::PolyTooLarge)?; 789 let max_variable_domain = 790 EvaluationDomain::<E::Fr>::new(max_num_variables).ok_or(SynthesisError::PolyTooLarge)?; 791 let max_non_zero_domain = max_non_zero_domain.ok_or(SynthesisError::PolyTooLarge)?; 792 793 let comms = &proof.commitments; 794 let proof_has_correct_zk_mode = if SM::ZK { 795 proof.pc_proof.is_hiding() & comms.mask_poly.is_some() 796 } else { 797 !proof.pc_proof.is_hiding() & comms.mask_poly.is_none() 798 }; 799 if !proof_has_correct_zk_mode { 800 dev_eprintln!( 801 "Found `mask_poly` in the first round when not expected, or proof has incorrect hiding mode ({})", 802 proof.pc_proof.is_hiding() 803 ); 804 return Ok(false); 805 } 806 807 let verifier_time = start_timer!(|| format!("Varuna::Verify with batch sizes: {batch_sizes:?}")); 808 809 let first_round_info = AHPForR1CS::<E::Fr, SM>::first_round_polynomial_info(batch_sizes.iter()); 810 811 let mut first_comms_consumed = 0; 812 let mut first_commitments = batch_sizes 813 .iter() 814 .flat_map(|(circuit_id, &batch_size)| { 815 let first_comms = comms.witness_commitments[first_comms_consumed..][..batch_size] 816 .iter() 817 .enumerate() 818 .map(|(j, w_comm)| { 819 LabeledCommitment::new_with_info( 820 &first_round_info[&witness_label(*circuit_id, "w", j)], 821 w_comm.w, 822 ) 823 }); 824 first_comms_consumed += batch_size; 825 first_comms 826 }) 827 .collect_vec(); 828 829 if SM::ZK { 830 first_commitments.push(LabeledCommitment::new_with_info( 831 first_round_info.get("mask_poly").ok_or(anyhow!("Missing mask_poly"))?, 832 comms.mask_poly.ok_or(anyhow!("Missing mask_poly"))?, 833 )); 834 } 835 836 let second_round_info = AHPForR1CS::<E::Fr, SM>::second_round_polynomial_info(); 837 let second_commitments = [LabeledCommitment::new_with_info(&second_round_info["h_0"], comms.h_0)]; 838 839 let third_round_info = AHPForR1CS::<E::Fr, SM>::third_round_polynomial_info(max_variable_domain.size()); 840 let third_commitments = [ 841 LabeledCommitment::new_with_info(&third_round_info["g_1"], comms.g_1), 842 LabeledCommitment::new_with_info(&third_round_info["h_1"], comms.h_1), 843 ]; 844 845 let fourth_round_info = 846 AHPForR1CS::<E::Fr, SM>::fourth_round_polynomial_info(circuit_infos.clone().into_iter()); 847 let fourth_commitments = comms 848 .g_a_commitments 849 .iter() 850 .zip_eq(comms.g_b_commitments.iter()) 851 .zip_eq(comms.g_c_commitments.iter()) 852 .zip_eq(circuit_ids.iter()) 853 .flat_map(|(((g_a, g_b), g_c), circuit_id)| { 854 [ 855 LabeledCommitment::new_with_info(&fourth_round_info[&witness_label(*circuit_id, "g_a", 0)], *g_a), 856 LabeledCommitment::new_with_info(&fourth_round_info[&witness_label(*circuit_id, "g_b", 0)], *g_b), 857 LabeledCommitment::new_with_info(&fourth_round_info[&witness_label(*circuit_id, "g_c", 0)], *g_c), 858 ] 859 }) 860 .collect_vec(); 861 862 let fifth_round_info = AHPForR1CS::<E::Fr, SM>::fifth_round_polynomial_info(); 863 let fifth_commitments = [LabeledCommitment::new_with_info(&fifth_round_info["h_2"], comms.h_2)]; 864 865 let circuit_commitments = keys_to_inputs.keys().map(|vk| vk.circuit_commitments.as_slice()); 866 let mut sponge = Self::init_sponge(fs_parameters, &inputs_and_batch_sizes, circuit_commitments.clone()); 867 868 // -------------------------------------------------------------------- 869 // First round 870 let first_round_time = start_timer!(|| "First round"); 871 Self::absorb_labeled(&first_commitments, &mut sponge); 872 let (_, verifier_state) = AHPForR1CS::<_, SM>::verifier_first_round( 873 &batch_sizes, 874 &circuit_infos, 875 max_constraint_domain, 876 max_variable_domain, 877 max_non_zero_domain, 878 &mut sponge, 879 )?; 880 end_timer!(first_round_time); 881 // -------------------------------------------------------------------- 882 883 // -------------------------------------------------------------------- 884 // Second round 885 let second_round_time = start_timer!(|| "Second round"); 886 Self::absorb_labeled(&second_commitments, &mut sponge); 887 let (_, verifier_state) = 888 AHPForR1CS::<_, SM>::verifier_second_round(verifier_state, &mut sponge, varuna_version)?; 889 end_timer!(second_round_time); 890 // -------------------------------------------------------------------- 891 892 // -------------------------------------------------------------------- 893 // Prep third round 894 let verifier_state = { 895 match varuna_version { 896 VarunaVersion::V1 => verifier_state, 897 VarunaVersion::V2 => { 898 let prepare_third_round_time = start_timer!(|| "Prep third round"); 899 Self::absorb_sums(&proof.third_msg.sums.clone().into_iter().flatten().collect_vec(), &mut sponge); 900 let (_, verifier_state) = AHPForR1CS::<_, SM>::verifier_prepare_third_round( 901 verifier_state, 902 &batch_sizes, 903 &circuit_infos, 904 &mut sponge, 905 )?; 906 end_timer!(prepare_third_round_time); 907 verifier_state 908 } 909 } 910 }; 911 // -------------------------------------------------------------------- 912 913 // -------------------------------------------------------------------- 914 // Third round 915 let third_round_time = start_timer!(|| "Third round"); 916 match varuna_version { 917 VarunaVersion::V1 => { 918 Self::absorb_labeled_with_sums( 919 &third_commitments, 920 &proof.third_msg.sums.clone().into_iter().flatten().collect_vec(), 921 &mut sponge, 922 ); 923 } 924 VarunaVersion::V2 => { 925 Self::absorb_labeled(&third_commitments, &mut sponge); 926 } 927 } 928 let (_, verifier_state) = AHPForR1CS::<_, SM>::verifier_third_round(verifier_state, &mut sponge)?; 929 end_timer!(third_round_time); 930 // -------------------------------------------------------------------- 931 932 // -------------------------------------------------------------------- 933 // Fourth round 934 let fourth_round_time = start_timer!(|| "Fourth round"); 935 936 Self::absorb_labeled_with_sums(&fourth_commitments, &proof.fourth_msg.sums, &mut sponge); 937 let (_, verifier_state) = AHPForR1CS::<_, SM>::verifier_fourth_round(verifier_state, &mut sponge)?; 938 end_timer!(fourth_round_time); 939 // -------------------------------------------------------------------- 940 941 // -------------------------------------------------------------------- 942 // Fifth round 943 let fifth_round_time = start_timer!(|| "Fifth round"); 944 945 Self::absorb_labeled(&fifth_commitments, &mut sponge); 946 let verifier_state = AHPForR1CS::<_, SM>::verifier_fifth_round(verifier_state, &mut sponge)?; 947 end_timer!(fifth_round_time); 948 // -------------------------------------------------------------------- 949 950 // Collect degree bounds for commitments. Indexed polynomials have *no* 951 // degree bounds because we know the committed index polynomial has the 952 // correct degree. 953 954 let commitments: Vec<_> = circuit_commitments 955 .into_iter() 956 .flatten() 957 .zip_eq(AHPForR1CS::<E::Fr, SM>::index_polynomial_info(circuit_ids.iter()).values()) 958 .map(|(c, info)| LabeledCommitment::new_with_info(info, *c)) 959 .chain(first_commitments) 960 .chain(second_commitments) 961 .chain(third_commitments) 962 .chain(fourth_commitments) 963 .chain(fifth_commitments) 964 .collect(); 965 966 let query_set_time = start_timer!(|| "Constructing query set"); 967 let (query_set, verifier_state) = AHPForR1CS::<_, SM>::verifier_query_set(verifier_state); 968 end_timer!(query_set_time); 969 970 sponge.absorb_nonnative_field_elements(proof.evaluations.to_field_elements()); 971 972 let mut evaluations = Evaluations::new(); 973 974 let mut current_circuit_id = "".to_string(); 975 let mut circuit_index: i64 = -1; 976 977 for (label, (_point_name, q)) in query_set.to_set() { 978 if AHPForR1CS::<E::Fr, SM>::LC_WITH_ZERO_EVAL.contains(&label.as_ref()) { 979 evaluations.insert((label, q), E::Fr::zero()); 980 } else { 981 if label != "g_1" { 982 let circuit_id = CircuitId::from_witness_label(&label).to_string(); 983 if circuit_id != current_circuit_id { 984 circuit_index += 1; 985 current_circuit_id = circuit_id; 986 } 987 } 988 let eval = proof 989 .evaluations 990 .get(circuit_index as usize, &label) 991 .ok_or_else(|| AHPError::MissingEval(label.clone()))?; 992 evaluations.insert((label, q), eval); 993 } 994 } 995 996 let lc_time = start_timer!(|| "Constructing linear combinations"); 997 let lc_s = AHPForR1CS::<_, SM>::construct_linear_combinations( 998 &public_inputs, 999 &evaluations, 1000 &proof.third_msg, 1001 &proof.fourth_msg, 1002 &verifier_state, 1003 varuna_version, 1004 )?; 1005 end_timer!(lc_time); 1006 1007 let pc_time = start_timer!(|| "Checking linear combinations with PC"); 1008 let evaluations_are_correct = SonicKZG10::<E, FS>::check_combinations( 1009 universal_verifier, 1010 lc_s.values(), 1011 &commitments, 1012 &query_set.to_set(), 1013 &evaluations, 1014 &proof.pc_proof, 1015 &mut sponge, 1016 )?; 1017 end_timer!(pc_time); 1018 1019 if !evaluations_are_correct { 1020 dev_eprintln!("SonicKZG10::Check failed using final challenge: {:?}", verifier_state.gamma); 1021 } 1022 1023 end_timer!(verifier_time, || format!( 1024 " SonicKZG10::Check for AHP Verifier linear equations: {}", 1025 evaluations_are_correct & proof_has_correct_zk_mode 1026 )); 1027 Ok(evaluations_are_correct & proof_has_correct_zk_mode) 1028 } 1029 }