Comments (3)
Hi @critesjosh. To answer your questions:
What new features does the merging of this PR unlock?
This PR provides data structures and methods on them that allow you to carry out computations involving elliptic curves over the (mathematical) field corresponding to Field
. For the field currently at our disposal, applications would involve a curve embedded in BN254, e.g. the Baby Jubjub curve.
In slightly more detail:
- Data structures
- Elliptic curve configurations (
std::ec::{tecurve,montcurve,swcurve}::{affine,curvegroup}::Curve
), i.e. the specific elliptic curve you want to use, which would be specified using any one of the methodsstd::ec::{tecurve,montcurve,swcurve}::{affine,curvegroup}::new
which take the coefficients in the defining equation together with a generator point as parameters. I go into a bit of detail regarding the distinction between the various curves in the comments innoir_stdlib/src/ec.nr
, but the gist of it is that the elliptic curves of interest are usually expressed in one of the standard forms implemented here (Twisted Edwards, Montgomery and Short Weierstraß), and in addition to that, you could choose to useaffine
coordinates (Cartesian coordinates - the usual (x,y) - possibly together with a point at infinity) orcurvegroup
coordinates (some form of projective coordinates requiring more coordinates but allowing for more efficient implementations of elliptic curve operations). Conversions between all of these forms are provided, and under the hood these conversions are done whenever an operation is more efficient in a different representation (or a mixed coordinate representation is employed). - Points (
std::ec::{tecurve,montcurve,swcurve}::{affine,curvegroup}::Point
), i.e. points lying on the elliptic curve. For a curve configurationc
and a pointp
, it may be checked checked thatp
does indeed lie onc
by callingc.contains(p1)
.
- Elliptic curve configurations (
- Methods (given a choice of curve representation, e.g.
use std::ec::tecurve::affine::Curve
anduse std::ec::tecurve::affine::Point
)- The zero element is given by
Point::zero()
, and we can verify whether a pointp: Point
is zero by callingp.is_zero()
. - Equality: Points
p1: Point
andp2: Point
may be checked for equality by callingp1.eq(p2)
. - Addition: For
c: Curve
and pointsp1: Point
andp2: Point
on the curve, adding these two points is accomplished by callingc.add(p1,p2)
. - Negation: For a point
p: Point
,p.negate()
is its negation. - Subtraction: For
c
andp1
,p2
as above, subtractingp2
fromp1
is accomplished by callingc.subtract(p1,p2)
. - Scalar multiplication: For
c
as above,p: Point
a point on the curve andn: Field
, scalar multiplication is given byc.mul(n,p)
. If insteadn :: [u1; N]
, i.e.n
is a bit array, thebit_mul
method may be used instead:c.bit_mul(n,p)
- Multi-scalar multiplication: For
c
as above and arraysn: [Field; N]
andp: [Point; N]
, multi-scalar multiplication is given byc.msm(n,p)
. - Coordinate representation conversions: The
into_group
method converts a point or curve configuration in the affine representation to one in the CurveGroup represetnsion, andinto_affine
goes in the other direction. - Curve representation conversions:
tecurve
andmontcurve
curves and points are equivalent and may be converted between one another by callinginto_montcurve
orinto_tecurve
on their configurations or points.swcurve
is more general and a curvec
of one of the other two types may be converted to this representation by callingc.into_swcurve()
, whereas a pointp
lying on the curve given byc
may be mapped to its correspondingswcurve
point by callingc.map_into_swcurve(p)
. - Map-to-curve methods: The Elligator 2 method of mapping a field element
n: Field
into atecurve
ormontcurve
with configurationc
may be called asc.elligator2_map(n)
. For all of the curve configurations, the SWU map-to-curve method may be called asc.swu_map(z,n)
, wherez: Field
depends onField
andc
and must be chosen by the user (the conditions it needs to satisfy are specified in the comments here).
- The zero element is given by
Do you have any examples/references of how these new primitives are used in Noir?
The ec_baby_jubjub
test illustrates all of the above primitives on various forms of the Baby Jubjub curve. A couple of more interesting examples in Noir would be:
- Public-key cryptography: Given an elliptic curve and a 'base point' on it, determine the public key from the private key.
This is a matter of using scalar multiplication. In the case of Baby Jubjub, for example, this code would do:
use dep::std::ec::tecurve::affine::Curve;
use dep::std::ec::tecurve::affine::Point;
fn bjj_pub_key(priv_key: Field) -> Point
{
let bjj = Curve::new(168700, 168696, G::new(995203441582195749578291179787384436505546430278305826713579947235728471134,5472060717959818805561601436314318772137091100104008585924551046643952123905));
let base_pt = Point::new(5299619240641551281634865583518297030282874472190772894086521144482721001553, 16950150798460657717958625567821834550301663161624707787222815936182638968203);
bjj.mul(priv_key,base_pt)
}
This would come in handy in a Merkle proof.
- EdDSA signature verification: This is a matter of combining these primitives with a suitable hash function. See noir-lang/noir#1136 for the case of Baby Jubjub and the Poseidon hash function.
Hope that helps!
from docs.
hi, @ax0, I am looking into documenting your contribution and have a few questions.
What new features does the merging of this PR unlock? Do you have any examples/references of how these new primitives are used in Noir?
from docs.
added via this pr (#89)
from docs.
Related Issues (20)
- bb.js-created proof fails when checking via the UltraVerifier contract, when circuits has mixed input types, uint and Filed arguments. HOT 2
- Document Noir PR 2541
- Document Noir PR 2541 HOT 1
- Document `nargo backend`
- Document Noir PR 2668 (1 contract per package) HOT 4
- Document `noir_js` HOT 2
- Document `test(should_fail)`
- Document Noir PR 2703 HOT 1
- Document extra steps needed for updating to Nargo v0.11 HOT 1
- Document assertion messages
- Document Noir PR 2713
- Document Noir PR 2754
- Document Noir PR 2764
- Document Noir PR 2776
- Document Noir PR 2803
- Document Noir PR 2815
- Document Noir PR 2899
- Document Noir PR 3081
- Document Noir PR 3081 HOT 1
- Document PR 3032 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from docs.