risc0_circuit_bigint/
lib.rs

1// Copyright 2024 RISC Zero, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
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
15pub mod byte_poly;
16mod codegen_prelude;
17pub mod rsa;
18#[cfg(feature = "prove")]
19pub mod zkr;
20
21#[cfg(not(target_os = "zkvm"))]
22mod host;
23#[cfg(not(target_os = "zkvm"))]
24pub use host::*;
25
26#[cfg(target_os = "zkvm")]
27mod guest;
28#[cfg(target_os = "zkvm")]
29pub use guest::*;
30
31#[cfg(not(feature = "make_control_ids"))]
32pub(crate) mod control_id;
33
34#[cfg(test)]
35mod op_tests;
36#[cfg(test)]
37#[cfg(feature = "prove")]
38mod rsa_tests;
39#[cfg(test)]
40mod test_harness;
41
42pub(crate) mod generated {
43    #![allow(dead_code)]
44    #![allow(clippy::all)]
45
46    use crate::codegen_prelude::*;
47    include! {"bigint.rs.inc"}
48}
49
50use std::borrow::Borrow;
51
52use anyhow::{ensure, Context, Result};
53use byte_poly::{BytePoly, BITS_PER_COEFF};
54use num_bigint::BigUint;
55use risc0_binfmt::{tagged_list, Digestible};
56use risc0_circuit_recursion::CHECKED_COEFFS_PER_POLY;
57use risc0_zkp::core::{digest::Digest, hash::sha::Sha256};
58
59pub use generated::PROGRAMS;
60
61// PO2 to use to execute bigint ZKRs.
62pub const BIGINT_PO2: usize = 18;
63
64const CLAIM_LIST_TAG: &str = "risc0.BigIntClaims";
65
66#[derive(Default, Debug)]
67pub struct BigIntContext {
68    pub in_values: Vec<BigUint>,
69
70    pub constant_witness: Vec<BytePoly>,
71    pub public_witness: Vec<BytePoly>,
72    pub private_witness: Vec<BytePoly>,
73}
74
75/// Information about a big integer included in a bigint witness.
76#[derive(Debug)]
77pub struct WitnessInfo {
78    pub bits: usize,
79    pub label: usize,
80    pub public: bool,
81    pub min_bits: usize,
82}
83
84impl WitnessInfo {
85    // Number of coefficients/field elements used by this bigint
86    pub fn coeffs(&self) -> usize {
87        const ROUND_WIDTH: usize = BITS_PER_COEFF * CHECKED_COEFFS_PER_POLY;
88        let polys = self.bits.div_ceil(ROUND_WIDTH);
89        polys * CHECKED_COEFFS_PER_POLY
90    }
91}
92
93pub struct BigIntProgram<'a> {
94    pub name: &'a str,
95    pub witness_info: &'a [WitnessInfo],
96    pub unconstrained_eval_fn: fn(&mut BigIntContext) -> anyhow::Result<()>,
97    // Control ID of this program
98    pub control_id: Digest,
99    // Control root of a merkle tree with a single element containing control_id
100    pub control_root: Digest,
101    // Number of claims to be verified per invocation of the ZKR
102    pub iters: usize,
103}
104
105#[derive(Debug, Clone)]
106pub struct BigIntClaim {
107    pub public_witness: Vec<BytePoly>,
108}
109
110impl BigIntClaim {
111    pub fn new(public_witness: Vec<BytePoly>) -> Self {
112        BigIntClaim { public_witness }
113    }
114
115    pub fn from_biguints(
116        prog_info: &BigIntProgram,
117        biguints: &[impl ToOwned<Owned = BigUint>],
118    ) -> Self {
119        assert_eq!(biguints.len(), prog_info.witness_info.len());
120        let public_witness: Vec<BytePoly> = biguints
121            .iter()
122            .zip(prog_info.witness_info.iter())
123            .map(|(val, wit_info)| BytePoly::from_biguint(val.to_owned(), wit_info.coeffs()))
124            .collect();
125        BigIntClaim { public_witness }
126    }
127}
128
129impl Digestible for BigIntClaim {
130    fn digest<S: Sha256>(&self) -> Digest {
131        let mut u32s: Vec<u32> = Vec::new();
132
133        for wit in self.public_witness.iter() {
134            u32s.extend(wit.clone().into_padded_u32s())
135        }
136
137        tracing::trace!("digest of {} u32s: {:x?}", u32s.len(), u32s);
138        *S::hash_raw_data_slice(&u32s)
139    }
140}
141
142pub(crate) fn claim_list_digest<S: Sha256>(
143    prog: &BigIntProgram,
144    claims: &[impl Borrow<BigIntClaim>],
145) -> Result<Digest> {
146    ensure!(
147        claims.len() <= prog.iters,
148        "Tried to verify {} claims in a {}-claim bigint program",
149        claims.len(),
150        prog.iters
151    );
152    let mut digests: Vec<Digest> = Vec::with_capacity(prog.iters);
153    digests.extend(
154        claims
155            .iter()
156            .map(Borrow::borrow)
157            .map(Digestible::digest::<S>),
158    );
159    digests.resize(
160        prog.iters,
161        *digests
162            .last()
163            .context("At least one claim must be specified in a list of claims")?,
164    );
165    Ok(tagged_list::<S>(CLAIM_LIST_TAG, &digests))
166}
167
168pub(crate) fn pad_claim_list<'a>(
169    prog: &BigIntProgram,
170    claims: &'a [impl Borrow<BigIntClaim>],
171) -> Result<Vec<&'a BigIntClaim>> {
172    ensure!(
173        claims.len() <= prog.iters,
174        "Tried to verify {} claims in a {}-claim bigint program",
175        claims.len(),
176        prog.iters
177    );
178    let mut claim_refs: Vec<&BigIntClaim> = Vec::with_capacity(prog.iters);
179    claim_refs.extend(claims.iter().map(Borrow::borrow));
180    claim_refs.resize(
181        prog.iters,
182        claim_refs
183            .last()
184            .context("At least one claim must be specified in a list of claims")?,
185    );
186    Ok(claim_refs)
187}
risc0_circuit_bigint/lib.rs

risc0_circuit_bigint/
lib.rs
