cairo_lang_sierra/extensions/modules/
ec.rs

1use super::felt252::Felt252Type;
2use super::non_zero::nonzero_ty;
3use super::range_check::RangeCheckType;
4use crate::define_libfunc_hierarchy;
5use crate::extensions::lib_func::{
6    BranchSignature, DeferredOutputKind, LibfuncSignature, OutputVarInfo, ParamSignature,
7    SierraApChange, SignatureSpecializationContext,
8};
9use crate::extensions::{
10    NamedType, NoGenericArgsGenericLibfunc, NoGenericArgsGenericType, OutputVarReferenceInfo,
11    SpecializationError,
12};
13use crate::ids::GenericTypeId;
14
15// Type representing the EcOp builtin.
16#[derive(Default)]
17pub struct EcOpType {}
18impl NoGenericArgsGenericType for EcOpType {
19    const ID: GenericTypeId = GenericTypeId::new_inline("EcOp");
20    const STORABLE: bool = true;
21    const DUPLICATABLE: bool = false;
22    const DROPPABLE: bool = false;
23    const ZERO_SIZED: bool = false;
24}
25
26/// An EC point is a pair (x,y) on the curve.
27#[derive(Default)]
28pub struct EcPointType {}
29impl NoGenericArgsGenericType for EcPointType {
30    const ID: GenericTypeId = GenericTypeId::new_inline("EcPoint");
31    const STORABLE: bool = true;
32    const DUPLICATABLE: bool = true;
33    const DROPPABLE: bool = true;
34    const ZERO_SIZED: bool = false;
35}
36
37/// An EC state is an EC point and a pointer to a random EC point shift.
38#[derive(Default)]
39pub struct EcStateType {}
40impl NoGenericArgsGenericType for EcStateType {
41    const ID: GenericTypeId = GenericTypeId::new_inline("EcState");
42    const STORABLE: bool = true;
43    const DUPLICATABLE: bool = true;
44    const DROPPABLE: bool = true;
45    const ZERO_SIZED: bool = false;
46}
47
48define_libfunc_hierarchy! {
49    pub enum EcLibfunc {
50        IsZero(EcIsZeroLibfunc),
51        Neg(EcNegLibfunc),
52        StateAdd(EcStateAddLibfunc),
53        TryNew(EcCreatePointLibfunc),
54        StateFinalize(EcStateFinalizeLibfunc),
55        StateInit(EcStateInitLibfunc),
56        StateAddMul(EcStateAddMulLibfunc),
57        PointFromX(EcPointFromXLibfunc),
58        UnwrapPoint(EcUnwrapPointLibfunc),
59        Zero(EcZeroLibfunc),
60    }, EcConcreteLibfunc
61}
62
63/// Libfunc for returning the zero point (the point at infinity).
64#[derive(Default)]
65pub struct EcZeroLibfunc {}
66impl NoGenericArgsGenericLibfunc for EcZeroLibfunc {
67    const STR_ID: &'static str = "ec_point_zero";
68
69    fn specialize_signature(
70        &self,
71        context: &dyn SignatureSpecializationContext,
72    ) -> Result<LibfuncSignature, SpecializationError> {
73        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
74
75        Ok(LibfuncSignature::new_non_branch(
76            vec![],
77            vec![OutputVarInfo {
78                ty: ecpoint_ty,
79                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Const),
80            }],
81            SierraApChange::Known { new_vars_only: true },
82        ))
83    }
84}
85
86/// Libfunc for creating an EC point from its coordinates `x` and `y`.
87/// If `(x, y)` is not on the curve, nothing is returned.
88#[derive(Default)]
89pub struct EcCreatePointLibfunc {}
90impl NoGenericArgsGenericLibfunc for EcCreatePointLibfunc {
91    const STR_ID: &'static str = "ec_point_try_new_nz";
92
93    fn specialize_signature(
94        &self,
95        context: &dyn SignatureSpecializationContext,
96    ) -> Result<LibfuncSignature, SpecializationError> {
97        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
98        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
99        let felt252_param = ParamSignature::new(context.get_concrete_type(Felt252Type::id(), &[])?);
100
101        Ok(LibfuncSignature {
102            param_signatures: vec![felt252_param.clone(), felt252_param],
103            branch_signatures: vec![
104                // Success.
105                BranchSignature {
106                    vars: vec![OutputVarInfo {
107                        ty: nonzero_ecpoint_ty,
108                        ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
109                    }],
110                    ap_change: SierraApChange::Known { new_vars_only: false },
111                },
112                // Failure.
113                BranchSignature {
114                    vars: vec![],
115                    ap_change: SierraApChange::Known { new_vars_only: false },
116                },
117            ],
118            fallthrough: Some(0),
119        })
120    }
121}
122
123/// Libfunc for creating an EC point from its x coordinate.
124///
125/// If there exists `y` such that `(x, y)` is on the curve, either `(x, y)` or `(x, -y)` (both
126/// constitute valid points on the curve) is returned.
127/// Otherwise, nothing is returned.
128#[derive(Default)]
129pub struct EcPointFromXLibfunc {}
130impl NoGenericArgsGenericLibfunc for EcPointFromXLibfunc {
131    const STR_ID: &'static str = "ec_point_from_x_nz";
132
133    fn specialize_signature(
134        &self,
135        context: &dyn SignatureSpecializationContext,
136    ) -> Result<LibfuncSignature, SpecializationError> {
137        let felt252_ty = context.get_concrete_type(Felt252Type::id(), &[])?;
138        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
139        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
140        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
141
142        let rc_output_info = OutputVarInfo::new_builtin(range_check_type.clone(), 0);
143        Ok(LibfuncSignature {
144            param_signatures: vec![
145                ParamSignature::new(range_check_type).with_allow_add_const(),
146                ParamSignature::new(felt252_ty),
147            ],
148            branch_signatures: vec![
149                // Success.
150                BranchSignature {
151                    vars: vec![
152                        rc_output_info.clone(),
153                        OutputVarInfo {
154                            ty: nonzero_ecpoint_ty,
155                            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
156                        },
157                    ],
158                    ap_change: SierraApChange::Known { new_vars_only: false },
159                },
160                // Failure.
161                BranchSignature {
162                    vars: vec![rc_output_info],
163                    ap_change: SierraApChange::Known { new_vars_only: false },
164                },
165            ],
166            fallthrough: Some(0),
167        })
168    }
169}
170
171/// Libfunc for unwrapping the x,y values of an EC point.
172#[derive(Default)]
173pub struct EcUnwrapPointLibfunc {}
174impl NoGenericArgsGenericLibfunc for EcUnwrapPointLibfunc {
175    const STR_ID: &'static str = "ec_point_unwrap";
176
177    fn specialize_signature(
178        &self,
179        context: &dyn SignatureSpecializationContext,
180    ) -> Result<LibfuncSignature, SpecializationError> {
181        let felt252_ty = context.get_concrete_type(Felt252Type::id(), &[])?;
182        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
183        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
184
185        let felt252_partial_param_0_output_info = OutputVarInfo {
186            ty: felt252_ty,
187            ref_info: OutputVarReferenceInfo::PartialParam { param_idx: 0 },
188        };
189        // TODO(orizi): Consider making the returned `y` value non-zero.
190        Ok(LibfuncSignature::new_non_branch(
191            vec![nonzero_ecpoint_ty],
192            vec![felt252_partial_param_0_output_info.clone(), felt252_partial_param_0_output_info],
193            SierraApChange::Known { new_vars_only: true },
194        ))
195    }
196}
197
198/// Libfunc for unwrapping the x,y values of an EC point.
199#[derive(Default)]
200pub struct EcNegLibfunc {}
201impl NoGenericArgsGenericLibfunc for EcNegLibfunc {
202    const STR_ID: &'static str = "ec_neg";
203
204    fn specialize_signature(
205        &self,
206        context: &dyn SignatureSpecializationContext,
207    ) -> Result<LibfuncSignature, SpecializationError> {
208        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
209
210        Ok(LibfuncSignature::new_non_branch(
211            vec![ecpoint_ty.clone()],
212            vec![OutputVarInfo {
213                ty: ecpoint_ty,
214                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
215            }],
216            SierraApChange::Known { new_vars_only: true },
217        ))
218    }
219}
220
221/// Libfunc for checking whether the given `EcPoint` is the zero point.
222#[derive(Default)]
223pub struct EcIsZeroLibfunc {}
224impl NoGenericArgsGenericLibfunc for EcIsZeroLibfunc {
225    const STR_ID: &'static str = "ec_point_is_zero";
226
227    fn specialize_signature(
228        &self,
229        context: &dyn SignatureSpecializationContext,
230    ) -> Result<LibfuncSignature, SpecializationError> {
231        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
232        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
233
234        Ok(LibfuncSignature {
235            param_signatures: vec![ParamSignature::new(ecpoint_ty)],
236            branch_signatures: vec![
237                // Zero.
238                BranchSignature {
239                    vars: vec![],
240                    ap_change: SierraApChange::Known { new_vars_only: true },
241                },
242                // NonZero.
243                BranchSignature {
244                    vars: vec![OutputVarInfo {
245                        ty: nonzero_ecpoint_ty,
246                        ref_info: OutputVarReferenceInfo::SameAsParam { param_idx: 0 },
247                    }],
248                    ap_change: SierraApChange::Known { new_vars_only: true },
249                },
250            ],
251            fallthrough: Some(0),
252        })
253    }
254}
255
256/// Libfunc for initializing an EC state from an EC point.
257#[derive(Default)]
258pub struct EcStateInitLibfunc {}
259impl NoGenericArgsGenericLibfunc for EcStateInitLibfunc {
260    const STR_ID: &'static str = "ec_state_init";
261
262    fn specialize_signature(
263        &self,
264        context: &dyn SignatureSpecializationContext,
265    ) -> Result<LibfuncSignature, SpecializationError> {
266        Ok(LibfuncSignature::new_non_branch(
267            vec![],
268            vec![OutputVarInfo {
269                ty: context.get_concrete_type(EcStateType::id(), &[])?,
270                ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
271            }],
272            SierraApChange::Known { new_vars_only: false },
273        ))
274    }
275}
276
277/// Libfunc for initializing an EC state from an EC point.
278#[derive(Default)]
279pub struct EcStateAddLibfunc {}
280impl NoGenericArgsGenericLibfunc for EcStateAddLibfunc {
281    const STR_ID: &'static str = "ec_state_add";
282
283    fn specialize_signature(
284        &self,
285        context: &dyn SignatureSpecializationContext,
286    ) -> Result<LibfuncSignature, SpecializationError> {
287        let state_ty = context.get_concrete_type(EcStateType::id(), &[])?;
288        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
289        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
290
291        Ok(LibfuncSignature::new_non_branch(
292            vec![state_ty.clone(), nonzero_ecpoint_ty],
293            vec![OutputVarInfo {
294                ty: state_ty,
295                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
296            }],
297            SierraApChange::Known { new_vars_only: false },
298        ))
299    }
300}
301
302/// Libfunc for initializing an EC state from an EC point.
303#[derive(Default)]
304pub struct EcStateFinalizeLibfunc {}
305impl NoGenericArgsGenericLibfunc for EcStateFinalizeLibfunc {
306    const STR_ID: &'static str = "ec_state_try_finalize_nz";
307
308    fn specialize_signature(
309        &self,
310        context: &dyn SignatureSpecializationContext,
311    ) -> Result<LibfuncSignature, SpecializationError> {
312        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
313        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
314
315        Ok(LibfuncSignature {
316            param_signatures: vec![ParamSignature::new(
317                context.get_concrete_type(EcStateType::id(), &[])?,
318            )],
319            branch_signatures: vec![
320                // Non-zero.
321                BranchSignature {
322                    vars: vec![OutputVarInfo {
323                        ty: nonzero_ecpoint_ty,
324                        ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
325                    }],
326                    ap_change: SierraApChange::Known { new_vars_only: false },
327                },
328                // Zero.
329                BranchSignature {
330                    vars: vec![],
331                    ap_change: SierraApChange::Known { new_vars_only: false },
332                },
333            ],
334            fallthrough: Some(0),
335        })
336    }
337}
338
339/// Libfunc for applying the EC op builtin: given an EC state `S`, a scalar `M` and an EC point `Q`,
340/// computes a new EC state `S + M * Q`.
341#[derive(Default)]
342pub struct EcStateAddMulLibfunc {}
343impl NoGenericArgsGenericLibfunc for EcStateAddMulLibfunc {
344    const STR_ID: &'static str = "ec_state_add_mul";
345
346    fn specialize_signature(
347        &self,
348        context: &dyn SignatureSpecializationContext,
349    ) -> Result<LibfuncSignature, SpecializationError> {
350        let ec_builtin_ty = context.get_concrete_type(EcOpType::id(), &[])?;
351        let ec_state_ty = context.get_concrete_type(EcStateType::id(), &[])?;
352        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
353        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
354
355        Ok(LibfuncSignature::new_non_branch_ex(
356            vec![
357                ParamSignature::new(ec_builtin_ty.clone()).with_allow_add_const(),
358                ParamSignature::new(ec_state_ty.clone()),
359                ParamSignature::new(context.get_concrete_type(Felt252Type::id(), &[])?),
360                ParamSignature::new(nonzero_ecpoint_ty),
361            ],
362            vec![
363                OutputVarInfo::new_builtin(ec_builtin_ty, 0),
364                OutputVarInfo {
365                    ty: ec_state_ty,
366                    ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
367                },
368            ],
369            SierraApChange::Known { new_vars_only: true },
370        ))
371    }
372}
cairo_lang_sierra/extensions/modules/ec.rs

cairo_lang_sierra/extensions/modules/
ec.rs
