core_utils/circuit/
circuit_id.rs

1//! Deterministic, cross-machine identity for a [`v2`](crate::circuit::v2) circuit.
2//!
3//! [`CircuitId`] is a blake3 digest over the canonical little-endian `bincode` encoding of a
4//! circuit's gates (in definition order) and outputs. Two circuits map to the same id iff they
5//! have the same gates in the same order and the same outputs, which makes it a cheap stand-in
6//! for full circuit equality (e.g. when parties must agree on which circuit to run).
7//!
8//! The encoding is byte-identical across machines because every value reachable inside a
9//! [`Gate`](crate::circuit::v2::Gate) serializes to a fixed-width little-endian representation and
10//! `bincode` itself encodes lengths as `u64` and enum discriminants as `u32` with no dependence on
11//! pointer width or endianness. The id is *not* stable across code changes that reorder or insert
12//! gate/op enum variants, since the bincode encoding embeds the variant index — this is acceptable
13//! (and desirable) for agreement, where parties must run compatible code regardless.
14
15use primitives::algebra::elliptic_curve::Curve;
16use serde::{Deserialize, Serialize};
17
18use crate::circuit::v2::Circuit;
19
20/// A deterministic 256-bit identity of a [`v2`](crate::circuit::v2) circuit, used for inexpensive
21/// circuit equality checks.
22#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)]
23pub struct CircuitId([u8; 32]);
24
25impl CircuitId {
26    /// Computes the id of the given circuit.
27    ///
28    /// Hashes the circuit's canonical `bincode` encoding (its `CompressedCircuit` form: gates in
29    /// order, then outputs), reusing the same representation circuits are serialized with on the
30    /// wire.
31    pub fn of<C: Curve>(circuit: &Circuit<C>) -> Self {
32        let bytes =
33            bincode::serialize(circuit).expect("circuit bincode serialization is infallible");
34        Self(*blake3::hash(&bytes).as_bytes())
35    }
36
37    /// Returns the raw 32-byte digest.
38    pub fn as_bytes(&self) -> &[u8; 32] {
39        &self.0
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use primitives::algebra::elliptic_curve::Curve25519Ristretto as C;
46
47    use super::*;
48    use crate::circuit::v2::{AlgebraicType, FieldShareBinaryOp, Gate, Input};
49
50    fn input<C: Curve>() -> Gate<C> {
51        Gate::Input(Input::SecretPlaintext {
52            inputer: 0,
53            algebraic_type: AlgebraicType::ScalarField,
54            batch_size: 1,
55        })
56    }
57
58    /// Builds a small `(x0 + x1) + (x2 + x3)` circuit using only the public API.
59    fn sample_circuit() -> Circuit<C> {
60        let mut circuit = Circuit::new();
61        let i0 = circuit.add_gate(input()).unwrap();
62        let i1 = circuit.add_gate(input()).unwrap();
63        let i2 = circuit.add_gate(input()).unwrap();
64        let i3 = circuit.add_gate(input()).unwrap();
65        let l = circuit
66            .add_gate(Gate::FieldShareBinaryOp {
67                x: i0,
68                y: i1,
69                op: FieldShareBinaryOp::Add,
70            })
71            .unwrap();
72        let r = circuit
73            .add_gate(Gate::FieldShareBinaryOp {
74                x: i2,
75                y: i3,
76                op: FieldShareBinaryOp::Add,
77            })
78            .unwrap();
79        let top = circuit
80            .add_gate(Gate::FieldShareBinaryOp {
81                x: l,
82                y: r,
83                op: FieldShareBinaryOp::Add,
84            })
85            .unwrap();
86        circuit.add_output(top).unwrap();
87        circuit
88    }
89
90    /// The same circuit always maps to the same id.
91    #[test]
92    fn deterministic() {
93        assert_eq!(
94            CircuitId::of(&sample_circuit()),
95            CircuitId::of(&sample_circuit())
96        );
97    }
98
99    /// A bincode round-trip preserves the id.
100    #[test]
101    fn stable_across_serialization_roundtrip() {
102        let circuit = sample_circuit();
103        let bytes = bincode::serialize(&circuit).unwrap();
104        let restored: Circuit<C> = bincode::deserialize(&bytes).unwrap();
105        assert_eq!(CircuitId::of(&circuit), CircuitId::of(&restored));
106    }
107
108    /// Reordering gates (same multiset, different order) changes the id.
109    #[test]
110    fn order_sensitive() {
111        // Two distinct inputers so the two input gates are not identical, letting us build the
112        // same set of gates in two different orders.
113        let mut a = Circuit::<C>::new();
114        let a0 = a.add_gate(input()).unwrap();
115        let a1 = a
116            .add_gate(Gate::Input(Input::SecretPlaintext {
117                inputer: 1,
118                algebraic_type: AlgebraicType::ScalarField,
119                batch_size: 1,
120            }))
121            .unwrap();
122        let a2 = a
123            .add_gate(Gate::FieldShareBinaryOp {
124                x: a0,
125                y: a1,
126                op: FieldShareBinaryOp::Add,
127            })
128            .unwrap();
129        a.add_output(a2).unwrap();
130
131        let mut b = Circuit::<C>::new();
132        let b0 = b
133            .add_gate(Gate::Input(Input::SecretPlaintext {
134                inputer: 1,
135                algebraic_type: AlgebraicType::ScalarField,
136                batch_size: 1,
137            }))
138            .unwrap();
139        let b1 = b.add_gate(input()).unwrap();
140        let b2 = b
141            .add_gate(Gate::FieldShareBinaryOp {
142                x: b0,
143                y: b1,
144                op: FieldShareBinaryOp::Add,
145            })
146            .unwrap();
147        b.add_output(b2).unwrap();
148
149        assert_ne!(CircuitId::of(&a), CircuitId::of(&b));
150    }
151
152    /// Editing a gate changes the id.
153    #[test]
154    fn gate_sensitive() {
155        let mut add = Circuit::<C>::new();
156        let x = add.add_gate(input()).unwrap();
157        let y = add.add_gate(input()).unwrap();
158        let z = add
159            .add_gate(Gate::FieldShareBinaryOp {
160                x,
161                y,
162                op: FieldShareBinaryOp::Add,
163            })
164            .unwrap();
165        add.add_output(z).unwrap();
166
167        let mut mul = Circuit::<C>::new();
168        let x = mul.add_gate(input()).unwrap();
169        let y = mul.add_gate(input()).unwrap();
170        let z = mul
171            .add_gate(Gate::FieldShareBinaryOp {
172                x,
173                y,
174                op: FieldShareBinaryOp::Mul,
175            })
176            .unwrap();
177        mul.add_output(z).unwrap();
178
179        assert_ne!(CircuitId::of(&add), CircuitId::of(&mul));
180    }
181
182    /// Different outputs over identical gates change the id.
183    #[test]
184    fn output_sensitive() {
185        let mut base = Circuit::<C>::new();
186        let x = base.add_gate(input()).unwrap();
187        let y = base.add_gate(input()).unwrap();
188        let z = base
189            .add_gate(Gate::FieldShareBinaryOp {
190                x,
191                y,
192                op: FieldShareBinaryOp::Add,
193            })
194            .unwrap();
195
196        let mut out_z = base.clone();
197        out_z.add_output(z).unwrap();
198
199        let mut out_x = base.clone();
200        out_x.add_output(x).unwrap();
201
202        assert_ne!(CircuitId::of(&out_z), CircuitId::of(&out_x));
203    }
204}
core_utils/circuit/circuit_id.rs

core_utils/circuit/
circuit_id.rs
