zerocaf

A pure-Rust implementation of elliptic curve operations over the Doppio-curve

3 unstable releases

 0.2.0 Jul 26, 2019 Jul 4, 2019 Jul 3, 2019

#808 in Cryptography

380KB
2.5K SLoC

WARNING: WIP Repo.

Fast, efficient and bulletproof-friendly cryptographic operations.

This repository contains an implementation of the Doppio curve over the Ristretto Scalar field: a pure Rust implementation designed by Dusk team.

Special thanks to Isis Agora Lovecruft and Henry de Valence for them implementation of Curve25519-dalek library, which has been so useful in order to get some of the basic arithmetic ops and the structure of our library.

Ristretto curve

Ristretto is a technique for constructing prime order elliptic curve groups with non-malleable encodings.

The Ristretto protocol arose as an extension of Mike Hamburg's Decaf approach to cofactor elimination, which is applicable to curves of cofactor 4, whereas the Ristretto is designed for non-prime-order curves of cofactor 8 or 4. Ristretto was designed by the dalek-cryprography team, specifically, Henry de Valence and Isis Agora Lovecruft to whom we greatly appreciate their work and dedication.

Ristretto Scalar Field And Bulletproofs.

Originally designed to abstract non-prime-order curves into prime-order scalar fields, the Ristretto abstraction would have been far too inefficient to implement for Bulletproofs zero-knowledge proof. Therefore the Ristretto scalar field is used to solve all negative impacts of using cofactors equalling 8 on the Ristretto curve.. The strategy is to use a Ristretto embedded curve (also called Doppio Curve), as the initial operations within zerocaf are performed therein. zerocaf opens up new opportunities for the use cases of zero-knowledge proofs inside the Dusk Network protocol as well as making a Bulletproof-integrated ring signature substitute possible, with orders of magnitude performance improvements compared to the fastest ringsig implementation.

Within this library, the implementation of the Ristretto to construct the curve with desired properties is made possible by defining the curve over the scalar field, using only a thin abstraction layer, which in turn allows for systems that use signatures to be safely extended with zero-knowledge protocols. These zero-knowledge protocols are utilised with no additional cryptographic assumptions and minimal changes in the code. The Ristretto scalar field is Bulletproof friendly, which makes it possible to use both cryptographic protocols in tandem with one another, as they are centric to contemporary applications of elliptic curve operations.

Special thanks to @ebfull who triggered this work with the following tweet:

Here's an "embedded" curve over ristretto255's scalar field

-x^2 + y^2 = 1 - (86649/86650)x^2y^2

which is Ristretto-ready and birationally equivalent to

y^2 = x^3 + 346598x^2 + x (and it's twist secure)

Any other suggestions?

— Sean Bowe (@ebfull) January 22, 2019

Details

Curve parameters:

Variable Value Explanation
Equation Edwards -x²+y²=1-$\frac{86649}{86650}$x²y² -
a -1 -
d $\frac{86649}{86650}$ -
B $\frac{8}{9}$ Edwards Basepoint Y-coordinate With X > 0

Montgomery y²=x³+346598*x²+x

| u(P) | 17 | u coordinate of the Montgomery Basepoint, X-coordinate |
| A | 346598 | |

Weierstrass y²=x³+ax+b
a 2412335192444087404657728854347664746952372119793302535333983646055108025796
b 1340186218024493002587627141304258192751317844329612519629993998710484804961
x 2412335192444087404657728854347664746952372119793302535333983646095151532546
y 6222320563903764848551041754877036140234555813488015858364752483591799173948
Variable Value Explanation
G 2²⁵² - 121160309657751286123858757838224683208 Curve order
p 2²⁵² + 27742317777372353535851937790883648493 Prime of the field

| r | 2²⁴⁹ - 15145038707218910765482344729778085401 | Prime of the Sub-Group |\

Encoding / Decoding tools

In order to work with our points along the curve, or any non trivial computuaions, for example those with tough notations - there has been a set of tools and examples which have been created to make facilitate the Encoding/Decoding processes. These can be found at: tools/src/main.rs

Examples

num_from_bytes_le(&[76, 250, 187, 243, 105, 92, 117, 70, 234, 124, 126, 180, 87, 149, 62, 249, 16, 149, 138, 56, 26, 87, 14, 76, 251, 39, 168, 74, 176, 202, 26, 84]);
// Prints: 38041616210253564751207933125345413214423929536328854382158537130491690875468

let res = to_field_elem_51(&"1201935917638644956968126114584555454358623906841733991436515590915937358637");
println!("{:?}", res);
// Gives us: [939392471225133, 1174884015108736, 2226020409917912, 1948943783348399, 46747909865470]

hex_bytes_le("120193591763864495696812611458455545435862390684173399143651559091593735863735685683568356835683");
// Prints: Encoding result -> [63, 41, b7, c, b, 79, 94, 7b, 21, d2, fe, 7b, c8, 89, c9, 7f, 76, c8, 9b, a3, 58, 18, 39, a, f2, d2, 7c, 17, ed, 7f, 6, c4, 9d, 44, f3, 7c, 85, c2, 67, e]
// Put the 0x by yourseleves and if there's any value alone like c padd it with a 0 on the left like: 0x0c

// Prints: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787



When performing operations with large values, such as: 2²⁵² - 121160309657751286123858757838224683208, it is recomended to compute them through SageMath, as the user interface adheres to these types of functions. From SageMath, they can be converted in a consistent format and easily compiled into Rust.

Note: the refactoring relations are expressed as indentations

• Build Scalar Arithmetics and Scalar Struct definition.
• Find the proper radix value for FieldElement.
• Add the required constants for computation.
• implement Subtraction.
• Implement Byte-encoding/decoding.
• Implement From for uint native types.
• Implement Ord, PartialOrd, Eq & PartialEq.
• Implement Multiplication on u64-backend with u128 usage.
• Implement Squaring.
• Implement Half for even numbers.
• Implement Modular Negation.
• Implement Montgomery_reduction.
• Define Montgomery_reduction algorithm.
• Create FieldElement Struct and implement the basic operations we need on a u64 backend.
• Find the proper radix value for FieldElement.
• Add basic and needed constants.
• Implement Reduce function to make the FieldElements fit on a 5 u64-bit limbs.
• Implement Subtraction.
• Implement Byte-encoding/decoding.
• Implement From for uint native types.
• Implement Ord, PartialOrd, Eq & PartialEq.
• Implement Multiplication on u64-backend with u128 usage.
• Implement Squaring.
• Implement Half for even numbers
• Implement Modular Negation.
• Implement Montgomery_reduction.
• Define Montgomery_reduction algorithm.
• Implement Modular inversion.
• Add proper tests for every function.
• Implement Edwards Points
• Implement Twisted Edwards Extended Coordiantes.
• Implement Point Subtraction.
• Implement Point Doubling.
• Implement Scalar Mul.
• Implement from_bytes conversions.
• Implement to byte conversions.
• Implement compressed Edwards point Y-coordinate.
• Implement Twisted Edwards Projective Coordiates.
• Implement Point Subtraction.
• Implement Point Doubling.
• Implement Scalar Mul.
• Implement from_bytes conversions.
• Implement to byte conversions.
• Implement compressed Edwards point Y-coordinate.
• Represent Edwards points as Ristretto points using wrapping function (research).
• Cargo doc testing and improvement.
• Decide the best use cases of the various Edwards coordinate types (compressed, standard, extended, projective).
• Benchmark different implementations and algorithms.
• Research About Niels and ProjectiveNiels coordinates usage.
• Implement Ristretto Mapping.
• Build and test torsion points.
• Test all point operations for Edwards Points.
• Implement Montgomery and Edwards operations & functions.

Operations with large numbers are recommended to be done in SageMath, from which they can be converted in a continuous format with rust and compiled easily after each computation.

~2.5MB
~55K SLoC