Use procedural macro to implement g! and s! macros

[LLFourn]

To implement g! and s! I wrote a compiler in rust's macro language: https://github.com/LLFourn/secp256kfun/blob/master/secp256kfun/src/macros.rs#L85. It turns out you can write procedural macros to write expression macros (not just derives): https://doc.rust-lang.org/reference/procedural-macros.html

Rewrite these macros use procedural macros so they are easier to understand. See if this allows for better testing of the macros as well.

[Kixunil]

Why do these even need to be macros? Couldn't you just implement core::ops::* on your types?

[LLFourn]

There's a few reasons:

1. You can compose g!(a * X + b * X) into a double multiplication which is faster than adding the result of two multiplications together.
2. You can improve what the macro compiles out to without updating user code but not with core::ops::*.
3. With core::op::* You have to implement every combination of multiplication with scalars of the lhs and points on the rhs and vise versa and then every combination of references or owned values on lhs and rhs.
4. You have to put &a * &X most of the time. & clutter up everything.

[Kixunil]

3, 4 the types should be copy anyway, they are just a bag of bits

1,2 maybe there is a way to construct a lazy expression using operators and then have a method on it to compute the result but it's probably not worth it

Thanks for explaining!

[LLFourn]

3, 4 the types should be copy anyway, they are just a bag of bits

Not quite. I think allowing copy means that they may be moved around in memory a lot. I wanted to leave the door open to zeroing out all Scalar<Secret, _> after they are dropped. I think the only correct way of doing this is making the backend::Scalar inside Scalar into a Pin<Box<backend::Scalar>> and putting a custom drop impl on backend::Scalar. So if this is the solution then we can't make them copy in general. I'm not sure how I'm going to manage to do this only for Secret scalars though.

1,2 maybe there is a way to construct a lazy expression using operators and then have a method on it to compute the result but it's probably not worth it

That's could be a good alternative if we can come up with the right design. The downside I think will be is that is the expression optmization will have to be done at runtime.

[Kixunil]

I think allowing copy means that they may be moved around in memory a lot.

It doesn't. Values can be moved around in memory a lot even if the type doesn't implement Copy. In reality Copy means WillNeverImplementDrop. Even Pin doesn't guarantee that pieces of the data won't end up in some registers or anywhere else.

The downside I think will be is that is the expression optmization will have to be done at runtime.

Done right, the compiler should optimize-out unreachable branches.

[LLFourn]

I think allowing copy means that they may be moved around in memory a lot.

It doesn't. Values can be moved around in memory a lot even if the type doesn't implement Copy. In reality Copy means WillNeverImplementDrop. Even Pin doesn't guarantee that pieces of the data won't end up in some registers or anywhere else.

Are you claiming there is no point in trying to zero out memory after it's dropped? If this was indeed the case then I would indeed implement Copy for all the types and perhaps try and do the runtime operation optmization as you suggested. Is there some empirical investigation into this claim that demonstrates it?

[Kixunil]

Are you claiming there is no point in trying to zero out memory after it's dropped?

Yes, at least until there's direct compiler support for it. Note also that the only way that memory could be exploited is if the program has a memory bug. Which should be unlikely in Rust already and the effort is probably better spent on preventing the remaining memory bugs.

empirical investigation

I'm not sure what you expect here. I don't have any links but I logically concluded it from following facts:

1. optimization passes can do various surprising things, quite a rabbit hole really: https://www.ralfj.de/blog/
2. there's no interface to tell the optimizer some data is secret
3. move is documented to be memcpy
4. to be sound, all memory must be overwritten before being read from in Rust, including memory coming from allocator
5. the OS zeroes-out pages before handing them to the process, can't find the reference now, I learned it in college, but logically, if you can demonstrate that any usual OS gives your program non-zeroed memory that before belonged to a different user I bet you can get a few million dollars bug bounty.
6. different programs running under the same user can affect each-other in so many ways it doesn't make sense to try separate them (except for changing their user): various debugging interfaces, shell settings, env vars, they share the same file, ...

From 1 and 2 we can conclude there's no way to guarantee zeroing in Rust, or even C! 4 means our memory-safe program won't leak memory, 5 means OS won't leak our memory to other users. 6 means mainly that even though my argument in 5 implies "OS can't leak a page to different user but could to different process under the same user" it doesn't matter.

IDK if you heard, recent announcement from Google claimed that they had so far zero memory vulnerabilities in a bunch of Rust code. So it seems exploitability of non-zeroed memory is very close to zero in practice.

[LLFourn]

hey @Kixunil happy new year :)

I am becoming more and more convinced of your position. I think we can make everything Copy. Thanks a lot for taking the time making these points.
Now it remains to see if we can do this without macros and use some kind of runtime expression optimizer. Here's a few concerns:

1. Making some kind of ScalarExpr or PointExpr enum which contains variants for different kinds of operations like multiplication and addition etc will involve using Box and therefore alloc. We'd need to use non-optimized operations in situations without an allocator. With macros you can optimize the expressions at compile time regardless of alloc. Although iirc right now linear combinations of points already needs alloc (but I think could be done without it with const generics).
2. Actually evaluating the expression will require the user to call .eval which adds some friction. To avoid this you could try making everything a ScalarExpr or PointExpr and coercing it into the actual scalar lazily when you need to.
3. Ironically, ScalarExpr and PointExpr non-copy! So implementing all the core::op on it will be annoying again.

So my current thinking is to make everything copy regardless of secrecy but to still using macros for arithmetic expressions.

[Kixunil]

Happy new year to you too!

I don't think it would involve enum or a Box. I was thinking more like:

#[derive(Copy, Clone)]
pub struct Add<Op1, Op2> where Op1: Expr, Op2: Expr<Output=Op1::Output>, Op1::Output: AactualAdd {
    operand1: Op1,
    operand2: Op2,
}

#[derive(Copy, Clone)]
pub struct Mul<Op1, Op2> where Op1: Expr, Op2: Expr, Op1::Output: ActualMul<Op2::Output>, Op2::Output: ActualMul<Op1::Output> {
    operand1: Op1,
    operand2: Op2,
}

#[derive(Copy, Clone)]
pub struct Neg<Op> {
    operand: Op,
}

pub trait ActualAdd {
    fn actual_add(self, rhs: Self) -> Self;
}

pub trait ActualMul<Rhs> {
    type Output;

    fn actual_mul(self, rhs: Rhs) -> Self::Output;
}

pub trait Expr: Copy {
    type Output: ActualAdd;
    // If Self is Mul these should be the operands, uninhabited otherwise
    type MulOp1;
    type MulOp2;

    fn eval(self) -> Self::Output;

    /// Returns Ok if Self is Mul
    // have more such functions for other optimizations
    #[inline]
    fn to_mul(self) -> Option<Mul<Self::MulOp1, Self::MulOp2>> {
        None
    }
}

impl<Op1: Expr, Op2: Expr<Output=Op1::Output>> Expr for Add<Op1, Op2> {
    type Output = Op1::Output;
    type MulOp1 = Infallible;
    type MulOp2 = Infallible;

    fn eval(self) -> Self::Output {
        match (self.operand1.to_mul(), self.operand2.to_mul()) {
            (Some(op1), Some(op2)) => {
                let op1_1 = op1.operand1.eval();
                let op1_2 = op1.operand2.eval();
                let op2_1 = op2.operand1.eval();
                let op2_2 = op2.operand2.eval();
                if op1_1 == op2_1 {
                    op1_1.actual_mul(op1_2.actual_add(op2_2))
                } else if op1_1 == op2_2 {
                    op1_1.actual_mul(op1_2.actual_add(op2_1))
                } else if op1_2 == op2_1 {
                    op1_2.actual_mul(op1_1.actual_add(op2_2))
                } else if op1_2 == op2_2 {
                    op1_2.actual_mul(op1_1.actual_add(op2_1))
                } else {
                    op1_1.actual_mul(op1_2).actual_add(op2_1.actual_mul(op_2_2))
                }
            },
            _ => self.operand1.eval().actual_add(self.operand2.eval()),
        }
    }
}

impl<Rhs> Add<Rhs> for Scalar where Rhs: Expr<Output=Scalar> {
    type Output = Add<Scalar, T>;

    fn add(self, rhs: Rhs) -> Self::Output {
        Add {
            operand1: self,
            operand2: rhs,
        }
    }
}

// impl the remaining ops the same way.

impl Expr for Scalar {
    type Output = Self; 
    type MulOp1 = Infallible;
    type MulOp2 = Infallible;
    fn eval(self) -> Self::Output { self }
}

impl Expr for Point {
    type Output = Self; 
    type MulOp1 = Infallible;
    type MulOp2 = Infallible;
    fn eval(self) -> Self::Output { self }
}

Will likely need a bit more tweaking of types&such but should work. It pretty much bypasses specialization (which would be much nicer).

[LLFourn]

Fascinating! I see a trait instead of an enum approach might work too. I would have two traits fwiw ScalarExpr and PointExpr and drop the ::Output to simplify. I might have a crack at this. I do feel like this might be going beyond the limits of good taste because there is already a lot of trait based indirection in this library already and layering this on top will make it even harder to figure out wtf is actually happening.

[LLFourn]

I made the g! and s! macros into proc_macros in #170.