snarkvm_ledger_coinbase/
lib.rs

1// Copyright (C) 2019-2023 Aleo Systems Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7// http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![forbid(unsafe_code)]
16#![allow(clippy::too_many_arguments)]
17#![warn(clippy::cast_possible_truncation)]
18
19mod helpers;
20pub use helpers::*;
21
22mod hash;
23use hash::*;
24
25#[cfg(test)]
26mod tests;
27
28use console::{
29    account::Address,
30    prelude::{anyhow, bail, cfg_iter, ensure, has_duplicates, Network, Result, ToBytes},
31};
32use snarkvm_algorithms::{
33    fft::{DensePolynomial, EvaluationDomain},
34    polycommit::kzg10::{UniversalParams as SRS, KZG10},
35};
36use snarkvm_curves::PairingEngine;
37use snarkvm_fields::Zero;
38use snarkvm_synthesizer_snark::UniversalSRS;
39
40use aleo_std::prelude::*;
41use std::sync::Arc;
42
43#[cfg(not(feature = "serial"))]
44use rayon::prelude::*;
45
46#[derive(Clone)]
47pub enum CoinbasePuzzle<N: Network> {
48    /// The prover contains the coinbase puzzle proving key.
49    Prover(Arc<CoinbaseProvingKey<N>>),
50    /// The verifier contains the coinbase puzzle verifying key.
51    Verifier(Arc<CoinbaseVerifyingKey<N>>),
52}
53
54impl<N: Network> CoinbasePuzzle<N> {
55    /// Initializes a new `SRS` for the coinbase puzzle.
56    #[cfg(any(test, feature = "setup"))]
57    pub fn setup(config: PuzzleConfig) -> Result<SRS<N::PairingCurve>> {
58        // The SRS must support committing to the product of two degree `n` polynomials.
59        // Thus, the SRS must support committing to a polynomial of degree `2n - 1`.
60        let total_degree = (2 * config.degree - 1).try_into()?;
61        let srs = KZG10::load_srs(total_degree)?;
62        Ok(srs)
63    }
64
65    /// Load the coinbase puzzle proving and verifying keys.
66    pub fn load() -> Result<Self> {
67        let max_degree = N::COINBASE_PUZZLE_DEGREE;
68        // Load the universal SRS.
69        let universal_srs = UniversalSRS::<N>::load()?;
70        // Trim the universal SRS to the maximum degree.
71        Self::trim(&*universal_srs, PuzzleConfig { degree: max_degree })
72    }
73
74    pub fn trim(srs: &SRS<N::PairingCurve>, config: PuzzleConfig) -> Result<Self> {
75        // As above, we must support committing to the product of two degree `n` polynomials.
76        // Thus, the SRS must support committing to a polynomial of degree `2n - 1`.
77        // Since the upper bound to `srs.powers_of_beta_g` takes as input the number
78        // of coefficients. The degree of the product has `2n - 1` coefficients.
79        //
80        // Hence, we request the powers of beta for the interval [0, 2n].
81        let product_domain = Self::product_domain(config.degree)?;
82
83        let lagrange_basis_at_beta_g = srs.lagrange_basis(product_domain)?;
84        let fft_precomputation = product_domain.precompute_fft();
85        let product_domain_elements = product_domain.elements().collect();
86
87        let vk = CoinbaseVerifyingKey::<N> {
88            g: srs.power_of_beta_g(0)?,
89            gamma_g: <N::PairingCurve as PairingEngine>::G1Affine::zero(), // We don't use gamma_g later on since we are not hiding.
90            h: srs.h,
91            beta_h: srs.beta_h(),
92            prepared_h: srs.prepared_h.clone(),
93            prepared_beta_h: srs.prepared_beta_h.clone(),
94        };
95
96        let pk = CoinbaseProvingKey {
97            product_domain,
98            product_domain_elements,
99            lagrange_basis_at_beta_g,
100            fft_precomputation,
101            verifying_key: vk,
102        };
103
104        Ok(Self::Prover(Arc::new(pk)))
105    }
106
107    /// Returns a prover solution to the coinbase puzzle.
108    pub fn prove(
109        &self,
110        epoch_challenge: &EpochChallenge<N>,
111        address: Address<N>,
112        nonce: u64,
113        minimum_proof_target: Option<u64>,
114    ) -> Result<ProverSolution<N>> {
115        // Retrieve the coinbase proving key.
116        let pk = match self {
117            Self::Prover(coinbase_proving_key) => coinbase_proving_key,
118            Self::Verifier(_) => bail!("Cannot prove the coinbase puzzle with a verifier"),
119        };
120
121        let polynomial = Self::prover_polynomial(epoch_challenge, address, nonce)?;
122
123        let product_evaluations = {
124            let polynomial_evaluations = pk.product_domain.in_order_fft_with_pc(&polynomial, &pk.fft_precomputation);
125            pk.product_domain.mul_polynomials_in_evaluation_domain(
126                polynomial_evaluations,
127                &epoch_challenge.epoch_polynomial_evaluations().evaluations,
128            )?
129        };
130        let (commitment, _rand) = KZG10::commit_lagrange(&pk.lagrange_basis(), &product_evaluations, None, None)?;
131
132        let partial_solution = PartialSolution::new(address, nonce, commitment);
133
134        // Check that the minimum target is met.
135        if let Some(minimum_target) = minimum_proof_target {
136            let proof_target = partial_solution.to_target()?;
137            ensure!(
138                proof_target >= minimum_target,
139                "Prover solution was below the necessary proof target ({proof_target} < {minimum_target})"
140            );
141        }
142
143        let point = hash_commitment(&commitment)?;
144        let product_eval_at_point = polynomial.evaluate(point) * epoch_challenge.epoch_polynomial().evaluate(point);
145
146        let proof = KZG10::open_lagrange(
147            &pk.lagrange_basis(),
148            pk.product_domain_elements(),
149            &product_evaluations,
150            point,
151            product_eval_at_point,
152        )?;
153        ensure!(!proof.is_hiding(), "The prover solution must contain a non-hiding proof");
154
155        debug_assert!(KZG10::check(&pk.verifying_key, &commitment, point, product_eval_at_point, &proof)?);
156
157        Ok(ProverSolution::new(partial_solution, proof))
158    }
159
160    /// Returns `true` if the solutions are valid.
161    pub fn check_solutions(
162        &self,
163        solutions: &CoinbaseSolution<N>,
164        epoch_challenge: &EpochChallenge<N>,
165        proof_target: u64,
166    ) -> Result<()> {
167        let timer = timer!("CoinbasePuzzle::verify");
168
169        // Ensure the solutions are not empty.
170        ensure!(!solutions.is_empty(), "There are no solutions to verify for the coinbase puzzle");
171
172        // Ensure the number of partial solutions does not exceed `MAX_PROVER_SOLUTIONS`.
173        if solutions.len() > N::MAX_SOLUTIONS {
174            bail!(
175                "The solutions exceed the allowed number of partial solutions. ({} > {})",
176                solutions.len(),
177                N::MAX_SOLUTIONS
178            );
179        }
180
181        // Ensure the puzzle commitments are unique.
182        if has_duplicates(solutions.puzzle_commitments()) {
183            bail!("The solutions contain duplicate puzzle commitments");
184        }
185        lap!(timer, "Perform initial checks");
186
187        // Verify each prover solution.
188        if !cfg_iter!(solutions).all(|(_, solution)| {
189            solution.verify(self.coinbase_verifying_key(), epoch_challenge, proof_target).unwrap_or(false)
190        }) {
191            bail!("The solutions contain an invalid prover solution");
192        }
193        finish!(timer, "Verify each solution");
194
195        Ok(())
196    }
197
198    /// Returns the coinbase proving key.
199    pub fn coinbase_proving_key(&self) -> Result<&CoinbaseProvingKey<N>> {
200        match self {
201            Self::Prover(coinbase_proving_key) => Ok(coinbase_proving_key),
202            Self::Verifier(_) => bail!("Cannot fetch the coinbase proving key with a verifier"),
203        }
204    }
205
206    /// Returns the coinbase verifying key.
207    pub fn coinbase_verifying_key(&self) -> &CoinbaseVerifyingKey<N> {
208        match self {
209            Self::Prover(coinbase_proving_key) => &coinbase_proving_key.verifying_key,
210            Self::Verifier(coinbase_verifying_key) => coinbase_verifying_key,
211        }
212    }
213}
214
215impl<N: Network> CoinbasePuzzle<N> {
216    /// Checks that the degree for the epoch and prover polynomial is within bounds,
217    /// and returns the evaluation domain for the product polynomial.
218    pub(crate) fn product_domain(degree: u32) -> Result<EvaluationDomain<N::Field>> {
219        ensure!(degree != 0, "Degree cannot be zero");
220        let num_coefficients = degree.checked_add(1).ok_or_else(|| anyhow!("Degree is too large"))?;
221        let product_num_coefficients = num_coefficients
222            .checked_mul(2)
223            .and_then(|t| t.checked_sub(1))
224            .ok_or_else(|| anyhow!("Degree is too large"))?;
225        assert_eq!(product_num_coefficients, 2 * degree + 1);
226        let product_domain =
227            EvaluationDomain::new(product_num_coefficients.try_into()?).ok_or_else(|| anyhow!("Invalid degree"))?;
228        assert_eq!(product_domain.size(), (product_num_coefficients as usize).checked_next_power_of_two().unwrap());
229        Ok(product_domain)
230    }
231
232    /// Returns the prover polynomial for the coinbase puzzle.
233    fn prover_polynomial(
234        epoch_challenge: &EpochChallenge<N>,
235        address: Address<N>,
236        nonce: u64,
237    ) -> Result<DensePolynomial<<N::PairingCurve as PairingEngine>::Fr>> {
238        let input = {
239            let mut bytes = [0u8; 76];
240            epoch_challenge.epoch_number().write_le(&mut bytes[..4])?;
241            epoch_challenge.epoch_block_hash().write_le(&mut bytes[4..36])?;
242            address.write_le(&mut bytes[36..68])?;
243            nonce.write_le(&mut bytes[68..])?;
244
245            bytes
246        };
247        Ok(hash_to_polynomial::<<N::PairingCurve as PairingEngine>::Fr>(&input, epoch_challenge.degree()))
248    }
249}
snarkvm_ledger_coinbase/lib.rs

snarkvm_ledger_coinbase/
lib.rs
