Add interface for bls12-381

[perturbing]

Hello Aiken stdlib maintainers,

I'm excited to submit my first pull request, which introduces a new BLS12-381 interface to the Aiken standard library!

As a summary, I propose to add three new submodules, all under the umbrella module bls12_381. These are:

• g1.ak: A simple interface for basic operations on G1 elements derived from builtin functions.
• g2.ak: A simple interface for basic operations on G2 elements derived from builtin functions.
• scalar.ak: An interface that implements the bls12-381 scalar field over the integers.

I have one remark on the scalar field. Currently, taking an exponential in plutus is costly. Which means that the operations, like scale/recip/div in this module, are very costly onchain, I still added these functions for completeness.

That said, most proof systems do use an exponent, but can rely on a little trick. That is, for scalar^n we can fix in our protocol that n=2^k for some k. Which means that we can reduce the complexity of the tree created in the repeated squaring method. I called this function pow_of_two.

Feel free to change any naming in this lib as you like to better fit the rest (I tried my best in following your standards).

[rvcas]

This looks super solid to me, I think @MicroProofs has some questions about Scalar

[rvcas]

We haven't forgotten this PR we're just putting merging it on hold until we decide how to handle the PlutusV3 script context changes.

[perturbing]

Sounds good, no rush :)

[logicalmechanism]

I wanted to comment on this as I have been working with BLS12381 a lot now in anticipation of V3.

Would be a good idea to add in a equals function that wraps around, builtin.bls12_381_g1_equal(left,right) and builtin.bls12_381_g2_equal(left,right).

Consider changing how scaler works all together. Very rarely do you ever want to be working with the integer type when building BLS encrpytion algorithms. The limitation of the datum int type at 2^64-1 is too small and not secure. It is very common to use bytearrays and do a conversion, let number: Int = builtin.bytearray_to_integer(True, number_bytearray). Then we are not limited by the integer size when a redeemer or datum needs to carry an integer type.

An example of this use case is given in my seed elf wallet implementation using a variation of a Schnorr signature.

Having these functions from this PR in the stdlib is really going to help avoiding mixing between stdlib and builtin calls.

With these addtions from this PR I will be implementing some BLS specific additions to the Assist library, specifically implementing all the algorithms from Registry type.

[perturbing]

HI @logicalmechanism , thank you for the review!

Would be a good idea to add in a equals function that wraps around, builtin.bls12_381_g1_equal(left,right) and builtin.bls12_381_g2_equal(left,right).

I added them :)

Consider changing how scaler works all together. Very rarely do you ever want to be working with the integer type when building BLS encrpytion algorithms. The limitation of the datum int type at 2^64-1 is too small and not secure. It is very common to use bytearrays and do a conversion, let number: Int = builtin.bytearray_to_integer(True, number_bytearray). Then we are not limited by the integer size when a redeemer or datum needs to carry an integer type.

I disagree that this would be a better interface as the low level operations always work over the integers (as you cannot add byte strings as integers in plutus yet (see bitwise primitives)), but how about I add a function scalar.add_from_bs and the reverse?

@rvcas , can you please consider from a UI perspective if I named all function properly?

[perturbing]

Hi @KtorZ,

I noticed that the PR was closed, but I didn't see an explanation for the closure. Could you please provide more context on the decision? I'd appreciate any feedback or guidance on how I might adjust the implementation to meet the project's needs.

And as always, thanks for the time and consideration :smile:

[KtorZ]

@perturbing arf. It wasn't closed. It was merged, but because I rebased it and made a few adjustments on top, Github probably shows it as "closed".

But it's live and released already 😬:

• https://aiken-lang.github.io/stdlib/
• https://github.com/aiken-lang/stdlib/releases/tag/v2.1.0

[perturbing]

@KtorZ , Ah yeah, I missed that, only got the email it closed.

You did change some things, right? Please note that you cannot encode bls points in flat encoding in scripts. So having this in the interface makes less sense than what I did in the above pr here. So in scripts you always have to decompress any point.

Did you change something else beside the constants?

But hey, my first contribution is live :smiley:

[KtorZ]

@perturbing I wasn't aware that it was decided to not allow flat encoding of uncompressed G1 and G2 in the end; this wasn't the case initially and somewhat missed that change.

Since I still believed that uncompressing on-demand every time would be both cumbersome and expensive, we did something at the compiler-level (so starting from 1.3.0) to hoist BLS uncompressed points when found in code. This way, from an Aiken's perspective, one can simply write code the way I wrote it for the stdlib. And, this results in a lambda introducing the uncompressed point as a variable used everywhere else. This changes ensures that: (1) we never actually have to flat-encode an uncompressed point and (2) uncompression happens only once and only when necessary (i.e. the program depends at least once on the point).

[perturbing]

@KtorZ , that is my fault, I did not finish the above review which mentioned that change..... (I saw it, but missed the pending status)

I wasn't aware that it was decided to not allow flat encoding of uncompressed G1 and G2 in the end

An initial preliminary design did allow for it, but it was shown that this could be an attack vector for spam. That is, create a script with a lot of bls points and some simple script logic. This way, in phase 1 of the execution, each node does the checks that this big list of bls points are indeed valid points (this is not cheap, as you can see from the ExUnits of the decompress builtin), for which you do not pay.

In short, the initial CIP introduced a new type in the plutus language, and one should check for such additions that deserializing is constant or linear given the size of the new type. See this addition to CIP 35.