mithril_stm/circuits/halo2/
circuit.rs

1use ff::Field;
2use group::Group;
3use midnight_circuits::ecc::curves::CircuitCurve;
4use midnight_circuits::instructions::{
5    AssignmentInstructions, ConversionInstructions, PublicInputInstructions,
6};
7use midnight_circuits::types::{
8    AssignedBit, AssignedNative, AssignedNativePoint, AssignedScalarOfNativeCurve,
9};
10use midnight_proofs::circuit::{Layouter, Value};
11use midnight_proofs::plonk::Error;
12use midnight_zk_stdlib::{Relation, ZkStdLib, ZkStdLibArch};
13
14use crate::circuits::halo2::constants::{DST_LOTTERY, DST_UNIQUE_SIGNATURE};
15use crate::circuits::halo2::gadgets::{
16    verify_lottery, verify_merkle_path, verify_unique_signature,
17};
18use crate::circuits::halo2::off_circuit::merkle_tree::{MTLeaf, MerklePath};
19use crate::circuits::halo2::off_circuit::unique_signature::Signature;
20use crate::circuits::halo2::types::{Jubjub, JubjubBase, LotteryIndex, MerkleRoot, Msg};
21
22type F = JubjubBase;
23type C = Jubjub;
24
25#[derive(Clone, Default, Debug)]
26pub struct StmCircuit {
27    // k in mithril: the required number of distinct lottery indices slots needed to create a valid multi-signature
28    quorum: u32,
29    // m in mithril: the number of lotteries that a user can participate in to sign a message
30    num_lotteries: u32,
31    merkle_tree_depth: u32,
32}
33
34impl StmCircuit {
35    pub fn new(quorum: u32, num_lotteries: u32, merkle_tree_depth: u32) -> Self {
36        Self {
37            quorum,
38            num_lotteries,
39            merkle_tree_depth,
40        }
41    }
42}
43
44impl Relation for StmCircuit {
45    type Instance = (MerkleRoot, Msg);
46    type Witness = Vec<(MTLeaf, MerklePath, Signature, LotteryIndex)>;
47
48    fn format_instance(instance: &Self::Instance) -> Result<Vec<F>, Error> {
49        Ok(vec![instance.0, instance.1])
50    }
51
52    fn circuit(
53        &self,
54        std_lib: &ZkStdLib,
55        layouter: &mut impl Layouter<F>,
56        instance: Value<Self::Instance>,
57        witness: Value<Self::Witness>,
58    ) -> Result<(), Error> {
59        assert!(self.quorum < self.num_lotteries);
60
61        let merkle_root: AssignedNative<F> =
62            std_lib.assign_as_public_input(layouter, instance.map(|(x, _)| x))?;
63        let msg: AssignedNative<F> =
64            std_lib.assign_as_public_input(layouter, instance.map(|(_, x)| x))?;
65
66        // Compute H_1(merkle_root, msg)
67        let hash = std_lib.hash_to_curve(layouter, &[merkle_root.clone(), msg.clone()])?;
68
69        let generator: AssignedNativePoint<C> = std_lib.jubjub().assign_fixed(
70            layouter,
71            <C as CircuitCurve>::CryptographicGroup::generator(),
72        )?;
73
74        let dst_signature: AssignedNative<_> =
75            std_lib.assign_fixed(layouter, DST_UNIQUE_SIGNATURE)?;
76        let dst_lottery: AssignedNative<_> = std_lib.assign_fixed(layouter, DST_LOTTERY)?;
77        let lottery_prefix = std_lib.poseidon(
78            layouter,
79            &[dst_lottery.clone(), merkle_root.clone(), msg.clone()],
80        )?;
81
82        let witness = witness.transpose_vec(self.quorum as usize);
83
84        let mut pre_index: AssignedNative<_> = std_lib.assign(layouter, Value::known(F::ZERO))?;
85        for (i, wit) in witness.into_iter().enumerate() {
86            let index: AssignedNative<F> =
87                std_lib.assign(layouter, wit.clone().map(|(_, _, _, i)| F::from(i as u64)))?;
88
89            // Check index order
90            if i > 0 {
91                let is_less = std_lib.lower_than(layouter, &pre_index, &index, 32)?;
92                std_lib.assert_true(layouter, &is_less)?;
93            }
94
95            pre_index = index.clone();
96
97            let vk = std_lib
98                .jubjub()
99                .assign(layouter, wit.clone().map(|(x, _, _, _)| x.0.0))?;
100
101            let target: AssignedNative<F> =
102                std_lib.assign(layouter, wit.clone().map(|(x, _, _, _)| x.1))?;
103
104            // Assign sibling Values.
105            let assigned_merkle_siblings = std_lib.assign_many(
106                layouter,
107                wit.clone()
108                    .map(|(_, x, _, _)| x.siblings.iter().map(|x| x.1).collect::<Vec<_>>())
109                    .transpose_vec(self.merkle_tree_depth as usize)
110                    .as_slice(),
111            )?;
112
113            // Assign sibling Position.
114            let assigned_merkle_positions = std_lib.assign_many(
115                layouter,
116                wit.clone()
117                    .map(|(_, x, _, _)| x.siblings.iter().map(|x| x.0.into()).collect::<Vec<_>>())
118                    .transpose_vec(self.merkle_tree_depth as usize)
119                    .as_slice(),
120            )?;
121
122            // Assert merkle positions are binary values.
123            let assigned_merkle_positions = assigned_merkle_positions
124                .iter()
125                .map(|pos| std_lib.convert(layouter, pos))
126                .collect::<Result<Vec<AssignedBit<F>>, Error>>()?;
127
128            let sigma: AssignedNativePoint<_> = std_lib
129                .jubjub()
130                .assign(layouter, wit.clone().map(|(_, _, sig, _)| sig.sigma))?;
131            let s: AssignedScalarOfNativeCurve<C> = std_lib
132                .jubjub()
133                .assign(layouter, wit.clone().map(|(_, _, sig, _)| sig.s))?;
134            let c_native = std_lib.assign(layouter, wit.map(|(_, _, sig, _)| sig.c))?;
135            let c: AssignedScalarOfNativeCurve<C> =
136                std_lib.jubjub().convert(layouter, &c_native)?;
137
138            verify_merkle_path(
139                std_lib,
140                layouter,
141                &vk,
142                &target,
143                &merkle_root,
144                &assigned_merkle_siblings,
145                &assigned_merkle_positions,
146            )?;
147
148            verify_unique_signature(
149                std_lib,
150                layouter,
151                &dst_signature,
152                &generator,
153                &vk,
154                &s,
155                &c,
156                &c_native,
157                &hash,
158                &sigma,
159            )?;
160
161            verify_lottery(std_lib, layouter, &lottery_prefix, &sigma, &index, &target)?;
162        }
163
164        // m can be put as a public instance or a constant
165        let m = std_lib.assign_fixed(layouter, F::from(self.num_lotteries as u64))?;
166        let is_less = std_lib.lower_than(layouter, &pre_index, &m, 32)?;
167
168        std_lib.assert_true(layouter, &is_less)
169    }
170
171    fn used_chips(&self) -> ZkStdLibArch {
172        ZkStdLibArch {
173            jubjub: true,
174            poseidon: true,
175            sha2_256: false,
176            sha2_512: false,
177            keccak_256: false,
178            sha3_256: false,
179            secp256k1: false,
180            bls12_381: false,
181            base64: false,
182            nr_pow2range_cols: 2,
183            automaton: false,
184            blake2b: false,
185        }
186    }
187
188    fn write_relation<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
189        writer.write_all(&self.quorum.to_le_bytes())?;
190        writer.write_all(&self.num_lotteries.to_le_bytes())?;
191        writer.write_all(&self.merkle_tree_depth.to_le_bytes())
192    }
193
194    fn read_relation<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
195        // Buffers to read 4 bytes for each `u32` field.
196        let mut quorum_bytes = [0u8; 4];
197        let mut num_lotteries_bytes = [0u8; 4];
198        let mut merkle_tree_depth_bytes = [0u8; 4];
199
200        // Read the values into their corresponding buffers.
201        reader.read_exact(&mut quorum_bytes)?;
202        reader.read_exact(&mut num_lotteries_bytes)?;
203        reader.read_exact(&mut merkle_tree_depth_bytes)?;
204
205        // Convert the byte arrays back into `u32` values.
206        let quorum = u32::from_le_bytes(quorum_bytes);
207        let num_lotteries = u32::from_le_bytes(num_lotteries_bytes);
208        let merkle_tree_depth = u32::from_le_bytes(merkle_tree_depth_bytes);
209
210        // Construct and return the `StmCircuit` instance.
211        Ok(Self {
212            quorum,
213            num_lotteries,
214            merkle_tree_depth,
215        })
216    }
217}
mithril_stm/circuits/halo2/circuit.rs

mithril_stm/circuits/halo2/
circuit.rs
