Dusk-Zerocaf

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:

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`

from_radix_to_radix_10("1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", 16u32);
// 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.

Roadmap:

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 Addition.
    • 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 Addition.
    • 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.
    • Research about addition chains inversion methods.
  • Add proper tests for every function.

• Implement Edwards Points

  • Implement Twisted Edwards Extended Coordiantes.
    • Implement Point Addition.
    • 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 Addition.
    • 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.