cairo_lang_sierra/extensions/modules/
ec.rs

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

cairo_lang_sierra/extensions/modules/
ec.rs
