Elliptic curve abstraction

[tevador]

In some places (for example here), code specific to the ed25519 elliptic curve leaks into the Seraphis logic.

It would make sense to abstract that away. Makes more sense in the context of the proposal to switch to a different curve, but also would make it easier to check that the code matches the Seraphis specification.

[UkoeHB]

I'm not sure how you would do this. The current code is highly optimized using the existing crypto API, I don't imagine a different API would line up 1:1.

[tevador]

For example, this can be the implementation of a generic ge_sub function:

ge_p3_to_cached(&temp_cache, &X_p3);
ge_sub(&temp_p1p1, &K_t1_p3, &temp_cache);
ge_p1p1_to_p3(&K_t2_p3, &temp_p1p1);

This can be a generic ge_double_scalarmult_vartime function:

ge_dsm_precomp(temp_dsmp, &K_t1_p3);
ge_double_scalarmult_precomp_vartime(&temp_p2, proof.r_t1.bytes, &K_p3, proof.c.bytes, temp_dsmp);

This can be a generic ge_clear_cofactor function:

rct::scalarmult8(K_t1_p3, proof.K_t1);

The generic impl would become something similar to:

ge_frombytes_vartime(&K, K.bytes);

// get K_t1
ge_clear_cofactor(&K_t1, proof.K_t1);
CHECK_AND_ASSERT_THROW_MES(!(ge_is_point_at_infinity_vartime(&K_t1)),
    "verify sp composition proof: invalid proof element K_t1!");

// get KI
CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&KI, KI.bytes) == 0, "ge_frombytes_vartime failed!");

// K_t2 = K_t1 - X - KI
ge_sub(&K_t2, &K_t1, &X);
ge_sub(&K_t2, &K_t2, &KI);

CHECK_AND_ASSERT_THROW_MES(!(ge_p3_is_point_at_infinity_vartime(&K_t2)),
    "verify sp composition proof: invalid proof element K_t2!");

// K_t1 part: [r_t1 * K + c * K_t1]
ge_double_scalarmult_vartime(&temp, proof.r_t1.bytes, &K, proof.c.bytes, &K_t1);
ge_tobytes(part_t1.bytes, &temp);

// K_t2 part: [r_t2 * G + c * K_t2]
ge_double_scalarmult_base_vartime(&temp, proof.c.bytes, &K_t2, proof.r_t2.bytes);
ge_tobytes(part_t2.bytes, &temp_p2);

// KI part:   [r_ki * U + c * KI  ]
ge_double_scalarmult_vartime(&temp, proof.r_ki.bytes, &U, proof.c.bytes, &KI);
ge_tobytes(part_ki.bytes, &temp);

The code would work with any curve that implements the interface. When reading the code, you don't need to care if ge_double_scalarmult_vartime is optimized with a precomputed table or not.

[UkoeHB]

@tevador the main thing I'm confused about is types. Are you A) proposing a template, B) implying that different crypto backends would use the same crypto types (ge_p3 and so on), C) implying you could use some library-level typedefs like using deser_point_t = ge_p3; that can cleanly map to the crypto backend?

[tevador]

implying you could use some library-level typedefs like using deser_point_t = ge_p3; that can cleanly map to the crypto backend?

Yes, the same trick is used by the C++ standard library, for example the RandomNumberDistribution template interface. Types using ECC would need to be templated on the curve implementation and then you would use something like T::point_type instead of ge_p3.

[UkoeHB]

Ok I think it could be done like this (edit: this needs some refinement to reduce duplication):

// eclib_interface.cpp
// interface validation: if the function 'eclib_interface()' compiles then the interface is correctly implemented on type LIBT

template <typename LIBT>
void eclib_interface()
{
    // types
          LIBT::pubkey       PUBKEY;
    const LIBT::pubkey CONST_PUBKEY;

          LIBT::scalar       SCALAR;
    const LIBT::scalar CONST_SCALAR;

          LIBT::secret_scalar       SECRET_SCALAR;
    const LIBT::secret_scalar CONST_SECRET_SCALAR;

    // type derivation
    static_assert(std::is_base_of<LIBT::scalar, LIBT::secret_scalar >::value, "");

    // to_byte conversions
    using       bytes_t =       unsigned char*;
    using const_bytes_t = const unsigned char*;

          bytes_t pk2b  = LIBT::to_bytes(      PUBKEY); (void)pk2b;
    const_bytes_t pk2cb = LIBT::to_bytes(CONST_PUBKEY); (void)pk2cb;
          bytes_t sc2b  = LIBT::to_bytes(      SCALAR); (void)sc2b;
    const_bytes_t sc2cb = LIBT::to_bytes(CONST_SCALAR); (void)sc2cb;

    // functions
    LIBT::scalar_mul_base(CONST_SCALAR, PUBKEY);
}

// instantiate the interface for each type we want to support
void instances()
{
    eclib_interface<eclib_ed25519>();
}

// eclib_ed25519.h
// ed25519 implementation
namespace crypto
{
struct eclib_ed25519 final
{
using pubkey        = crypto::public_key;
using scalar        = crypto::ec_scalar;
using secret_scalar = crypto::secret_key;

static       unsigned char* to_bytes(      pubkey &key) noexcept
{ return reinterpret_cast<      unsigned char*>(key.data); }
static const unsigned char* to_bytes(const pubkey &key) noexcept
{ return reinterpret_cast<const unsigned char*>(key.data); }

static       unsigned char* to_bytes(      scalar &scalar) noexcept
{ return reinterpret_cast<      unsigned char*>(scalar.data); }
static const unsigned char* to_bytes(const scalar &scalar) noexcept
{ return reinterpret_cast<const unsigned char*>(scalar.data); }

static void scalar_mul_base(const scalar &scalar, pubkey &pubkey_out);
};  //eclib_ed25519
} //namespace crypto

// eclib_ed25519.cpp
void eclib_ed25519::scalar_mul_base(const ec_scalar &scalar, ec_pubkey &pubkey_out)
{
//ge_3 and these function calls would need to redirect to other stuff in the eclib_ed25519 interface, or possibly redirect to a template that can be shared by different backends
    ge_p3 temp_p3;
    scalar temp_scalar;
    sc_reduce32copy(to_bytes(temp_scalar), to_bytes(scalar)); //do this beforehand!
    ge_scalarmult_base(&temp_p3, to_bytes(temp_scalar));
    ge_p3_tobytes(to_bytes(pubkey_out), &temp_p3);
}

// seraphis_crypto.h
namespace sp
{
using eclib = crypto::eclib_ed25519;
} //namespace sp

It's doable, but quite a large undertaking to implement and validate all the functions (not to mention all the review required), plus refactoring everything in the seraphis library.

Note that RandomNumberDistribution is a concept, not a template.

[iamamyth]

If you look at the examples in the stdlib (e.g. https://en.cppreference.com/w/cpp/header/random), prior to c++20 (which introduces concepts for compiler interface validation assistance), it seems the convention favors documented requirements which the implementation assumes, and won't compile unless honored, but doesn't necessarily aid in honoring them. In other words, you can punt on the work of making it easy to add new curves, so long as you provide a documented contract of the requirements for a curve. At compile time, a bogus curve may generate confusing compile errors, but will error. If and when c++20 becomes the minimum standard, you could add concepts.

[UkoeHB]

@iamamyth I meant concept in an abstract sense, not C++20 concepts.

[iamamyth]

@iamamyth I meant concept in an abstract sense, not C++20 concepts.

Yes I understood as much, I merely meant to suggest that you can separate creating a usable point type interface from making it easy to implement new point types (if such a separation simplifies the former task).

[UkoeHB]

I wrote a demo for this:

core crypto interface (this must be implemented by all crypto libraries) utils library (these are functions that use the underlying core crypto library) defining a new lib and instantiating the predefined utils and checking the core interface was fully implemented using a lib