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![rc_output_info.clone(), OutputVarInfo {
152                        ty: nonzero_ecpoint_ty,
153                        ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
154                    }],
155                    ap_change: SierraApChange::Known { new_vars_only: false },
156                },
157                // Failure.
158                BranchSignature {
159                    vars: vec![rc_output_info],
160                    ap_change: SierraApChange::Known { new_vars_only: false },
161                },
162            ],
163            fallthrough: Some(0),
164        })
165    }
166}
167
168/// Libfunc for unwrapping the x,y values of an EC point.
169#[derive(Default)]
170pub struct EcUnwrapPointLibfunc {}
171impl NoGenericArgsGenericLibfunc for EcUnwrapPointLibfunc {
172    const STR_ID: &'static str = "ec_point_unwrap";
173
174    fn specialize_signature(
175        &self,
176        context: &dyn SignatureSpecializationContext,
177    ) -> Result<LibfuncSignature, SpecializationError> {
178        let felt252_ty = context.get_concrete_type(Felt252Type::id(), &[])?;
179        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
180        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
181
182        let felt252_partial_param_0_output_info = OutputVarInfo {
183            ty: felt252_ty,
184            ref_info: OutputVarReferenceInfo::PartialParam { param_idx: 0 },
185        };
186        // TODO(orizi): Consider making the returned `y` value non-zero.
187        Ok(LibfuncSignature::new_non_branch(
188            vec![nonzero_ecpoint_ty],
189            vec![felt252_partial_param_0_output_info.clone(), felt252_partial_param_0_output_info],
190            SierraApChange::Known { new_vars_only: true },
191        ))
192    }
193}
194
195/// Libfunc for unwrapping the x,y values of an EC point.
196#[derive(Default)]
197pub struct EcNegLibfunc {}
198impl NoGenericArgsGenericLibfunc for EcNegLibfunc {
199    const STR_ID: &'static str = "ec_neg";
200
201    fn specialize_signature(
202        &self,
203        context: &dyn SignatureSpecializationContext,
204    ) -> Result<LibfuncSignature, SpecializationError> {
205        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
206
207        Ok(LibfuncSignature::new_non_branch(
208            vec![ecpoint_ty.clone()],
209            vec![OutputVarInfo {
210                ty: ecpoint_ty,
211                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
212            }],
213            SierraApChange::Known { new_vars_only: true },
214        ))
215    }
216}
217
218/// Libfunc for checking whether the given `EcPoint` is the zero point.
219#[derive(Default)]
220pub struct EcIsZeroLibfunc {}
221impl NoGenericArgsGenericLibfunc for EcIsZeroLibfunc {
222    const STR_ID: &'static str = "ec_point_is_zero";
223
224    fn specialize_signature(
225        &self,
226        context: &dyn SignatureSpecializationContext,
227    ) -> Result<LibfuncSignature, SpecializationError> {
228        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
229        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
230
231        Ok(LibfuncSignature {
232            param_signatures: vec![ParamSignature::new(ecpoint_ty)],
233            branch_signatures: vec![
234                // Zero.
235                BranchSignature {
236                    vars: vec![],
237                    ap_change: SierraApChange::Known { new_vars_only: true },
238                },
239                // NonZero.
240                BranchSignature {
241                    vars: vec![OutputVarInfo {
242                        ty: nonzero_ecpoint_ty,
243                        ref_info: OutputVarReferenceInfo::SameAsParam { param_idx: 0 },
244                    }],
245                    ap_change: SierraApChange::Known { new_vars_only: true },
246                },
247            ],
248            fallthrough: Some(0),
249        })
250    }
251}
252
253/// Libfunc for initializing an EC state from an EC point.
254#[derive(Default)]
255pub struct EcStateInitLibfunc {}
256impl NoGenericArgsGenericLibfunc for EcStateInitLibfunc {
257    const STR_ID: &'static str = "ec_state_init";
258
259    fn specialize_signature(
260        &self,
261        context: &dyn SignatureSpecializationContext,
262    ) -> Result<LibfuncSignature, SpecializationError> {
263        Ok(LibfuncSignature::new_non_branch(
264            vec![],
265            vec![OutputVarInfo {
266                ty: context.get_concrete_type(EcStateType::id(), &[])?,
267                ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
268            }],
269            SierraApChange::Known { new_vars_only: false },
270        ))
271    }
272}
273
274/// Libfunc for initializing an EC state from an EC point.
275#[derive(Default)]
276pub struct EcStateAddLibfunc {}
277impl NoGenericArgsGenericLibfunc for EcStateAddLibfunc {
278    const STR_ID: &'static str = "ec_state_add";
279
280    fn specialize_signature(
281        &self,
282        context: &dyn SignatureSpecializationContext,
283    ) -> Result<LibfuncSignature, SpecializationError> {
284        let state_ty = context.get_concrete_type(EcStateType::id(), &[])?;
285        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
286        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
287
288        Ok(LibfuncSignature::new_non_branch(
289            vec![state_ty.clone(), nonzero_ecpoint_ty],
290            vec![OutputVarInfo {
291                ty: state_ty,
292                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
293            }],
294            SierraApChange::Known { new_vars_only: false },
295        ))
296    }
297}
298
299/// Libfunc for initializing an EC state from an EC point.
300#[derive(Default)]
301pub struct EcStateFinalizeLibfunc {}
302impl NoGenericArgsGenericLibfunc for EcStateFinalizeLibfunc {
303    const STR_ID: &'static str = "ec_state_try_finalize_nz";
304
305    fn specialize_signature(
306        &self,
307        context: &dyn SignatureSpecializationContext,
308    ) -> Result<LibfuncSignature, SpecializationError> {
309        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
310        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
311
312        Ok(LibfuncSignature {
313            param_signatures: vec![ParamSignature::new(
314                context.get_concrete_type(EcStateType::id(), &[])?,
315            )],
316            branch_signatures: vec![
317                // Non-zero.
318                BranchSignature {
319                    vars: vec![OutputVarInfo {
320                        ty: nonzero_ecpoint_ty,
321                        ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
322                    }],
323                    ap_change: SierraApChange::Known { new_vars_only: false },
324                },
325                // Zero.
326                BranchSignature {
327                    vars: vec![],
328                    ap_change: SierraApChange::Known { new_vars_only: false },
329                },
330            ],
331            fallthrough: Some(0),
332        })
333    }
334}
335
336/// Libfunc for applying the EC op builtin: given an EC state `S`, a scalar `M` and an EC point `Q`,
337/// computes a new EC state `S + M * Q`.
338#[derive(Default)]
339pub struct EcStateAddMulLibfunc {}
340impl NoGenericArgsGenericLibfunc for EcStateAddMulLibfunc {
341    const STR_ID: &'static str = "ec_state_add_mul";
342
343    fn specialize_signature(
344        &self,
345        context: &dyn SignatureSpecializationContext,
346    ) -> Result<LibfuncSignature, SpecializationError> {
347        let ec_builtin_ty = context.get_concrete_type(EcOpType::id(), &[])?;
348        let ec_state_ty = context.get_concrete_type(EcStateType::id(), &[])?;
349        let ecpoint_ty = context.get_concrete_type(EcPointType::id(), &[])?;
350        let nonzero_ecpoint_ty = nonzero_ty(context, &ecpoint_ty)?;
351
352        Ok(LibfuncSignature::new_non_branch_ex(
353            vec![
354                ParamSignature::new(ec_builtin_ty.clone()).with_allow_add_const(),
355                ParamSignature::new(ec_state_ty.clone()),
356                ParamSignature::new(context.get_concrete_type(Felt252Type::id(), &[])?),
357                ParamSignature::new(nonzero_ecpoint_ty),
358            ],
359            vec![OutputVarInfo::new_builtin(ec_builtin_ty, 0), OutputVarInfo {
360                ty: ec_state_ty,
361                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
362            }],
363            SierraApChange::Known { new_vars_only: true },
364        ))
365    }
366}
cairo_lang_sierra/extensions/modules/ec.rs

cairo_lang_sierra/extensions/modules/
ec.rs
