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_SIGNATURE};
15use crate::circuits::halo2::gadgets::{
16    verify_lottery, verify_merkle_path, verify_unique_signature,
17};
18use crate::circuits::halo2::types::{
19    Jubjub, JubjubBase, LotteryIndex, MTLeaf, MerklePath, MerkleRoot, SignedMessageWithoutPrefix,
20};
21use crate::signature_scheme::{PrimeOrderProjectivePoint, UniqueSchnorrSignature};
22
23type F = JubjubBase;
24type C = Jubjub;
25
26#[derive(Clone, Default, Debug)]
27pub struct StmCircuit {
28    // k in mithril: the required number of distinct lottery indices slots needed to create a valid multi-signature
29    quorum: u32,
30    // m in mithril: the number of lotteries that a user can participate in to sign a message
31    num_lotteries: u32,
32    merkle_tree_depth: u32,
33}
34
35impl StmCircuit {
36    pub fn new(quorum: u32, num_lotteries: u32, merkle_tree_depth: u32) -> Self {
37        Self {
38            quorum,
39            num_lotteries,
40            merkle_tree_depth,
41        }
42    }
43}
44
45impl Relation for StmCircuit {
46    type Instance = (MerkleRoot, SignedMessageWithoutPrefix);
47    type Witness = Vec<(MTLeaf, MerklePath, UniqueSchnorrSignature, LotteryIndex)>;
48
49    fn format_instance(instance: &Self::Instance) -> Result<Vec<F>, Error> {
50        Ok(vec![instance.0, instance.1])
51    }
52
53    fn circuit(
54        &self,
55        std_lib: &ZkStdLib,
56        layouter: &mut impl Layouter<F>,
57        instance: Value<Self::Instance>,
58        witness: Value<Self::Witness>,
59    ) -> Result<(), Error> {
60        assert!(self.quorum < self.num_lotteries);
61
62        let merkle_root: AssignedNative<F> =
63            std_lib.assign_as_public_input(layouter, instance.map(|(x, _)| x))?;
64        let msg: AssignedNative<F> =
65            std_lib.assign_as_public_input(layouter, instance.map(|(_, x)| x))?;
66
67        // Compute H_1(merkle_root, msg)
68        let hash = std_lib.hash_to_curve(layouter, &[merkle_root.clone(), msg.clone()])?;
69
70        let generator: AssignedNativePoint<C> = std_lib.jubjub().assign_fixed(
71            layouter,
72            <C as CircuitCurve>::CryptographicGroup::generator(),
73        )?;
74
75        let dst_signature: AssignedNative<_> = std_lib.assign_fixed(layouter, DST_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.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_value = wit
129                .clone()
130                .map_with_result(|(_, _, sig, _)| {
131                    let (u, v) = sig.commitment_point.get_coordinates();
132                    PrimeOrderProjectivePoint::from_coordinates(u, v).map(|point| point.0)
133                })
134                .map_err(|e| {
135                    Error::Synthesis(format!(
136                        "invalid commitment point: not on curve or not prime order: {e:?}"
137                    ))
138                })?;
139            let sigma: AssignedNativePoint<_> = std_lib.jubjub().assign(layouter, sigma_value)?;
140            let s: AssignedScalarOfNativeCurve<C> = std_lib
141                .jubjub()
142                .assign(layouter, wit.clone().map(|(_, _, sig, _)| sig.response.0))?;
143            let c_native = std_lib.assign(layouter, wit.map(|(_, _, sig, _)| sig.challenge.0))?;
144            let c: AssignedScalarOfNativeCurve<C> =
145                std_lib.jubjub().convert(layouter, &c_native)?;
146
147            verify_merkle_path(
148                std_lib,
149                layouter,
150                &vk,
151                &target,
152                &merkle_root,
153                &assigned_merkle_siblings,
154                &assigned_merkle_positions,
155            )?;
156
157            verify_unique_signature(
158                std_lib,
159                layouter,
160                &dst_signature,
161                &generator,
162                &vk,
163                &s,
164                &c,
165                &c_native,
166                &hash,
167                &sigma,
168            )?;
169
170            verify_lottery(std_lib, layouter, &lottery_prefix, &sigma, &index, &target)?;
171        }
172
173        // m can be put as a public instance or a constant
174        let m = std_lib.assign_fixed(layouter, F::from(self.num_lotteries as u64))?;
175        let is_less = std_lib.lower_than(layouter, &pre_index, &m, 32)?;
176
177        std_lib.assert_true(layouter, &is_less)
178    }
179
180    fn used_chips(&self) -> ZkStdLibArch {
181        ZkStdLibArch {
182            jubjub: true,
183            poseidon: true,
184            sha2_256: false,
185            sha2_512: false,
186            keccak_256: false,
187            sha3_256: false,
188            secp256k1: false,
189            bls12_381: false,
190            base64: false,
191            nr_pow2range_cols: 2,
192            automaton: false,
193            blake2b: false,
194        }
195    }
196
197    fn write_relation<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
198        writer.write_all(&self.quorum.to_le_bytes())?;
199        writer.write_all(&self.num_lotteries.to_le_bytes())?;
200        writer.write_all(&self.merkle_tree_depth.to_le_bytes())
201    }
202
203    fn read_relation<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
204        // Buffers to read 4 bytes for each `u32` field.
205        let mut quorum_bytes = [0u8; 4];
206        let mut num_lotteries_bytes = [0u8; 4];
207        let mut merkle_tree_depth_bytes = [0u8; 4];
208
209        // Read the values into their corresponding buffers.
210        reader.read_exact(&mut quorum_bytes)?;
211        reader.read_exact(&mut num_lotteries_bytes)?;
212        reader.read_exact(&mut merkle_tree_depth_bytes)?;
213
214        // Convert the byte arrays back into `u32` values.
215        let quorum = u32::from_le_bytes(quorum_bytes);
216        let num_lotteries = u32::from_le_bytes(num_lotteries_bytes);
217        let merkle_tree_depth = u32::from_le_bytes(merkle_tree_depth_bytes);
218
219        // Construct and return the `StmCircuit` instance.
220        Ok(Self {
221            quorum,
222            num_lotteries,
223            merkle_tree_depth,
224        })
225    }
226}
mithril_stm/circuits/halo2/circuit.rs

mithril_stm/circuits/halo2/
circuit.rs
