CPU overhead of wrapping BLS points in tuples or custom types

[dkaidalov]

While implementing a SNARK verifier in Aiken we've encountered a big CPU overhead when carrying BLS points (G1Element and G2Element) in tuples or custom types.
It seems putting a point in a tuple and then destructuring a tuple incurs additional decompression, which is very expensive.

Here are the tests:

use aiken/crypto/bls12_381/g1.{generator, decompress}
use aiken/crypto/bls12_381/scalar.{
  Scalar, from_int,
}
use aiken/crypto/bitwise.{State}


test decompressed_point_in_tuple() {
    let g1_generator_bytes = #"97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb"
    let point = decompress(g1_generator_bytes)

    let tuple_with_point: (G1Element, Int) = (point, 1)
    let (g1, _) = tuple_with_point                      // seems like destructuring a tuple invokes additional uncompression
    
    expect g1 == point
}

test compressed_point_in_tuple() {
    let g1_generator_bytes = #"97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb"
    
    let tuple_with_point: (ByteArray, Int) = (g1_generator_bytes, 1)
    let (bytes, _) = tuple_with_point
    
    let point = decompress(bytes)
    
    expect point == point
}

test decompressed_point() {
    let g1_generator_bytes = #"97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb"
    let point = decompress(g1_generator_bytes)

    expect point == point
}

test scalar_in_tuple() {
    let scalar: State<Scalar> = from_int(738453)

    let tuple_with_scalar: (State<Scalar>, Int) = (scalar, 1)
    let (s, _) = tuple_with_scalar
    
    expect s == scalar
}

test scalar() {
    let scalar: State<Scalar> = from_int(738453)
    expect scalar == scalar
}

From the benchmarks it looks like when putting in a tuple a point is compressed/decompressed under the hood.

PASS [mem:   4.60 K, cpu: 110.14 M] decompressed_point_in_tuple
PASS [mem:   4.04 K, cpu:  54.32 M] compressed_point_in_tuple
PASS [mem:   1.92 K, cpu:  53.75 M] decompressed_point
PASS [mem:   3.53 K, cpu:  905.1 K] scalar_in_tuple
PASS [mem:   1.00 K, cpu: 220.14 K] scalar

It is quite unexpected to see such behavior, is it documented somewhere?
I don't see such overhead in Plinth.

[KtorZ]

That's correct and expected. Points cannot be put uncompressed in tuples (or any data structures for that matter). So there's an implicit compression and uncompression happening everytime tuples are involved.

If you need to pack some G1/G2 elements or ML results, this is typically where you'd use continuation and backpassing to avoid creating intermediate structures.

[dkaidalov]

Could this be improved on the compiler level? There is no such overhead in Plinth
It might be counter-intuitive for an app developer who isn't deep into Plutus subtleties.
I wouldn't probably even realize that there is such an overhead if not comparing with Plinth side-by-side.

The overhead is huge and it can inhibit some crypto applications. The cost of our SNARK verifier went through the roof, cause we have to deal with lot's of points. We will need to refactor a lot of code now to avoid intermediate structures. But someone else might not even realize that there is such an overhead and give up altogether. So at the very least I would probably document this loudly.

[KtorZ]

Could this be improved on the compiler level?

Not really; because it's core to Aiken's design principles. Plinth currently re-encodes all values using Scott-Encoding, whereas Aiken operates entirely on "serialized data". That's a trade-off which has worked great for a majority of cases, as Aiken doesn't have any initial overhead whereas Plinth typically needs a "warm up" budget to deserialise elements from the script context and Scott-Encode them.

It's usually not an issue for most primitives values as they are already serialisable without much cost; but for G1/G2 elements, those can only be serialised in a compressed fashion.

The work-around in Aiken is to rely on functions and continuations, leveraging the backpassing syntax for readability. For example, if you need to accumulate two values folding over a list of elements; one of these values being a curve point; you can use something like foldl2 to avoid the creation of a tuple or a pair altogether.

So at the very least I would probably document this loudly.

There was a plan to add a compiler warning about this; because I do agree it clearly deserves a warning.

[dkaidalov]

thanks for clarification!
I'm curious wouldn't this inhibit upcoming CIP-133?
Cause it requires a list of points as an input. If that would require compression/decompression then I'm afraid it might make the MSM built-in useless.