Minor feature Request: Is it possible to have AddAssign?

[sanket1729]

First off, thanks for this awesome library. I will be using this to implement prototypes of Bulletproofs and Bulletproof++.

/// Compute the q-weighted inner product of two vectors.
fn inner_product(a: &[Scalar<Public, Zero>], b: &[Scalar<Public, Zero>]) -> Scalar<Public, Zero> {
    let mut res = s!(0);
    let res = res.mark::<Public>();
    for (a, b) in a.iter().zip(b.iter()) {
        res += s!(a * b); // Can be done as s!(res + a*b), but is it efficient?
    }
    res
}

Error:

error[E0368]: binary assignment operation `+=` cannot be applied to type `Scalar<secp256kfun::marker::Public, secp256kfun::marker::Zero>`
  --> secp256kfun/examples/norm_arg.rs:68:9
   |
68 |         res += s!(a * b);
   |         ---^^^^^^^^^^^^^
   |         |
   |         cannot use `+=` on type `Scalar<secp256kfun::marker::Public, secp256kfun::marker::Zero>`

Please make the last priority of things that you are doing.

1. Does the current implementation have additional copies every time in the loop? Or is there a better way to compute the inner product of two scalars?

2. s!(res + a * b) returns a Secret Marked value even when all values are public.

[sanket1729]

Also is it possible to do multi-scalar exponentiation?

[sanket1729]

Any other way to do hash_to_curve? That is, some deterministic way to convert a scalar into a Point whose DL is unknown

[LLFourn]

Hey @sanket1729. That's awesome!

I didn't want to implement Add because I wanted to only have one way to do it with the expression macros. AddAssign seems like a reasonable choice though. I'll do it.

1. Does the current implementation have additional copies every time in the loop? Or is there a better way to compute the inner product of two scalars?

This looks fine. In general the APIs don't mutate or consume existing points/scalars and create new ones. Probably even in the new AddAssign implementation this will be the case.

Also is it possible to do multi-scalar exponentiation?

In the EC group? Yes. You have to use op::lincomb explicitly atm. I want to introduce a syntax for linear combination in g! like g!(scalars [*] points) but haven't got to it yet.

Any other way to do hash_to_curve? That is, some deterministic way to convert a scalar into a Point whose DL is unknown

Next release I hope! I noticed the downstream crate k256 that I vendor'd for the backend arithmetic has implemented https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.txt this year. I should be able to copy that implementation.

2. s!(res + a * b) returns a Secret Marked value even when all values are public.

Yeah every Scalar is Secret when it is output from an operation while every point is Public. Doing type algebra to say that the result is Public if all of the inputs are Public is a cool idea but it caused too much type parameter friction for users IIRC which is why I went for that simpler rule instead. Perhaps with some new compiler features it will become possible to do that.

FYI at the moment with the k256 backend everything will use the same underlying constant time algorithm regardless of secrecy anyway. So there's no need to micromanage it for performance (can still be useful from a explanatory point of view to show the reader that this scalar is public). I'm experimenting on how to have faster variable time algorithms without nightly features now and it's going well so in the next release there might be a few token examples of faster operations if things are marked Public but they will likely not have much of an impact. The "secrecy" feature is really just there so that in the future if we add variable time lincomb algorithms etc you'll benefit from them without changing code.

Another note the .mark API is going away in the next release in favor of just calling .public (this is already in master).

[sanket1729]

@LLFourn thanks for the response.

You have to use op::lincomb explicitly atm. I want to introduce a syntax for linear combination in g! like g!(scalars [*] points) but haven't got to it yet.

Thanks, worked like a charm. One slightly annoying thing about that API is that it did not work cleanly with iterators whose Item is returning a value instead of a reference to value. This forces the caller to some computation results in a collection.

let e = Scalar::random(); //challenge
let scalar_iter = // An iterator returning powers of e, The item here must be `Scalar` (cannot be `&Scalar` as we cannot return a reference to something we create)

op::lincomb(scalar_iter, ...) ; // Compiler error . We must first collect into a vector and then call iter

One way would be use the Borrow trait so that Iterator<Item = A> where A : Borrow<Scalar>.

can still be useful from an explanatory point of view to show the reader that this scalar is public

The annotations are really good. Adding extra types and generics that force coders to think carefully is really good.

The macros are really good. Is it possible to modify them to use array elements in them? Right now, I have to do something like:

    let (w_0, l_0, c_0) = (w[0], l[0], c[0]);
	assert_eq!(v, s!(w_0*w_0 + l_0*c_0));

One last question: Is there any parallelization ongoing here? I am trying to bench Bulletproofs++ and want to make sure that none of the internal operations any doing parallelization.

[LLFourn]

@LLFourn thanks for the response.

You have to use op::lincomb explicitly atm. I want to introduce a syntax for linear combination in g! like g!(scalars [*] points) but haven't got to it yet.

Thanks, worked like a charm. One slightly annoying thing about that API is that it did not work cleanly with iterators whose Item is returning a value instead of a reference to value. This forces the caller to some computation results in a collection.

let e = Scalar::random(); //challenge
let scalar_iter = // An iterator returning powers of e, The item here must be `Scalar` (cannot be `&Scalar` as we cannot return a reference to something we create)

op::lincomb(scalar_iter, ...) ; // Compiler error . We must first collect into a vector and then call iter

One way would be use the Borrow trait so that Iterator<Item = A> where A : Borrow<Scalar>.

ACK. Good idea.

The annotations are really good. Adding extra types and generics that force coders to think carefully is really good.

The macros are really good. Is it possible to modify them to use array elements in them? Right now, I have to do something like:

    let (w_0, l_0, c_0) = (w[0], l[0], c[0]);
	assert_eq!(v, s!(w_0*w_0 + l_0*c_0));

Yeah I hate this and it has been on my todo for some time as part of #6. The work is 1/3 done.

One last question: Is there any parallelization ongoing here? I am trying to bench Bulletproofs++ and want to make sure that none of the internal operations any doing parallelization.

Nope. FYI it's using the complete protective formula addition + endomorphism + strauss aglorithm for the lincomb courtesy of the k256 implementation. It should give you a decent idea of BP++ vs BP relative performance at least. I'd be interested to know what you think of https://eprint.iacr.org/2020/152 as an option too.

[LLFourn]

Fixed in #120

Created #124 for hash_to_curve and #125 for API friction in calling lincomb