Why is the point (0, 2) mapped to infinity in deserialisation?

[kirk-baird]

Question

As said in the title why is (0, 2) mapped to the point at infinity?

    /*
     * Even though (0,2) is formally a point on E1 curve it's turned to
     * infinity...
     */

[dot-asm]

I have to thank you for reminder! Basically I was going to revisit this prior making the code public, but failed. In essence (0,2) can't participate in meaningful calculations because doubling formula so to say "melts down." But fortunately it may not appear in real-life data, because it's not in the cyclic group. And we expect all legitimate serialized points to be in the group. So that it sounds like it would be appropriate to reject it with BLST_POINT_NOT_IN_GROUP.

[kirk-baird]

Ah so the plan is to do subgroup check on deserialisation?

I ran a small test in rust and it seemed the results were correct for double and add_or_double. (after removing the line check for point (0, 2) in ec1.c::uncompress().

    #[test]
    fn test_double_0_2() {
        let mut bytes = [0u8; 48];
        bytes[0] = 128;
        let mut pk = min_pk::PublicKey::uncompress(&bytes).unwrap();
        let mut p1 = blst_p1::default();
        unsafe {
            blst_p1_from_affine(&mut p1, &pk.point);

            let mut p1_2 = p1.clone();
            let mut double = p1.clone();
            // blst_p1_double(&mut double, &p1);
            blst_p1_add_or_double(&mut double, &p1, &p1_2);
            blst_p1_to_affine(&mut pk.point, &double);
        }

        println!("{:?}", pk.serialize().to_vec());
    }

Both output the point (0, -2) is that not correct?
It just happens to be in a subgroup of size 3 {Inf, (0, 2), (0, -2)}?

[dot-asm]

Ah so the plan is to do subgroup check on deserialisation?

No, absolutely not. Suggestion is to return corresponding error code specifically for (0,2). So that application that does != BLST_SUCCESS would reject it, just like any other nonsensical input, not on curve or otherwise malformed. At the same time an application that would consider (0,2) useful (for whatever crazy reason, most likely just for reference) could check for BLST_POINT_NOT_IN_GROUP out of deserialization to single out the outlier in question.

As for performing operations on it. As mentioned, doubling formula "melts down." It doesn't literally mean that blst_p1_double doesn't produce a result, it's just that whatever it produces is effectively meaningless. Yes, you can note that passing (0,2) to blst_p1_double yields (0,-2), and adding them will result in infinity, and wonder if it's a group... The answer is it's nothing. And if the said point is presented for deserialization it can only mean that somebody is trying to mess with you.

Just in case if one wonders what was the rationale behind "shunting" it to infinity. The original intention was to keep serdes somewhat application-neutral. In other words less dependent on ZCash format. This means that you'd like to have a way of conveying infinite compressed point without the bit denoting the infinity. And line of reasoning went "since (0,2) means nothing, and infinity means non-signature, ..." This arguably needed a revisit...

[kirk-baird]

Just in case if one wonders what was the rationale behind "shunting" it to infinity. The original intention was to keep serdes somewhat application-neutral. In other words less dependent on ZCash format. This means that you'd like to have a way of conveying infinite compressed point without the bit denoting the infinity. And line of reasoning went "since (0,2) means nothing, and infinity means non-signature, ..." This arguably needed a revisit...

Yep, I see that is an more efficient way of representing infinity without using extra bits.

Now that we're using the ZCash format and represent infinity with an extra bit I don't see the need for handling the (0, +-2) case separately. It can be treated the same as any other point that is not in the correct subgroup. That is it will fail the subgroup check when doing some form of verification.

I agree that is a meaningless point as it should never verify as true and would only be used by malicious users. Though I promote it's treatment as the same as any other point not in the correct subgroup for consistency and mainly to match it's treatment in other implementations such as ZCash.

[dot-asm]

I don't see the need for handling the (0, +-2) case separately. It can be treated the same as any other point that is not in the correct subgroup. That is it will fail the subgroup check when doing some form of verification.

Trouble is that group-checking (0,2) is not more meaningful than doubling. Yes, blst_p1_affine_in_g1 says it's not in the group, but it's coincidental. The outcome is actually dependent on algorithm you choose to perform the check. The only sound way to treat it is to single it out. One can argue when it should be singled out, but one can't dispute that it has to be.

[kirk-baird]

The outcome is actually dependent on algorithm you choose to perform the check.

That's interesting, are their certain subgroup checking algorithms for which it's possible (0, +-2) may end up passing the subgroup check?
It looks like it should pass the naive way (albeit coincidentally) which is multiplication by r using double and add, then checking if we have the point infinity or not.

So assuming it may incorrectly pass the subgroup check and so needs to be singled out, I think it would be preferable to single it out at the subgroup check rather than during deserialisation.

[dot-asm]

It looks like it should pass the naive way

That's the thing, depending on algorithm you choose for multiplication by scalar, you'll get varying results.

it would be preferable to single it out at the subgroup check rather than during deserialisation.

I disagree. (0,2) is no different from non-on-curve or any other invalid input. So we need more opinions. But for now fix for #15 keeps it in deserialztion...

[dot-asm]

I've been thinking... (Despite the danger of doing so, I know;-) In essence the group-check is a countermeasure against forgery. And in such case one can wonder if current placement does a disservice. In my mind it boils down to how an application is supposed to react to not-in-group signature more specifically? Well, not when a transaction just enters the network, but later on, when the application handles stuff in larger chunks. Just disregard? Take a note? Just on that signature or whole chunk? Trouble is that as it is now application is effectively encouraged to commit for quite an expensive calculation with integrated group-checks, while feedback about specifics of the failure is quite limited. Most notably Rust or Go application wouldn't know which signature failed the group-check. Is it of interest to application? Pardon my ignorance:-) What I'm trying to hint at is that it might be appropriate to provide an interface to perform group-checks in bulk, parallelized of course, and which would be more specific about failure. Or work on conveying this information from current implementation. Thoughts? Of course if proper action is to disregard the whole chunk (presumably re-fetching it from another source?), then it's all right as it is...

[kirk-baird]

Yea it's a good point and I guess this is really now just a question about when we should do group check.

If we plan on failing as early as possible for efficiency then it works well for use to do the subgroup checking on deserialisation (whether this is done in batch or singularly). If you think it is better to do this in batch then we could include it as the first step of batch verify aggregate multiple (and then also each of verify, aggregate verify and fast aggregate verify) as then is when we have a list of signatures ready for batching.

Explaining the main use cases might shed some light on this:

1. The main one is processing all of the signatures in a block. In which case we will accumulate a bunch of aggregate signatures and run batch verify aggregate fast.
2. As you mention there are also a some times when we receive a transaction from the network and would need to verify the signature of this transaction before propagating it and/or aggregating it locally.

Note option 1 takes up the majority of the time so we concentrate most of our effort on this, in which as it stands lighthouse receives a block from the network and deserialises the entire block (including all of the signatures and eth2 structs) then searches through a block and extracting all the aggregate signatures. When then batch process all of these signatures.

So If we do subgroup checking at deserialisation then deserialising blocks would be slower but we would fail earlier. But doing this as part of the verify functions allows for it to be done in batch which is also beneficial.

[dot-asm]

if we plan on failing as early as possible for efficiency then it works well for use to do the subgroup checking on deserialisation (whether this is done in batch or singularly)

It should be noted that when I ask "it might be appropriate to add additional interface" it doesn't necessarily mean new interface to Rust (or Go) bindings. I primarily think in terms of C interface. In other words it's not necessarily about actually moving group-check to deserialization. Because as far as higher-level bindings go it might be sufficient to rearrange code in inner loops, and the only difference an application developer would see is that it returns more nuanced error code. But before we can do that we have to agree on these nuances. What makes sense to actual application? That's what we need help with. For example, is it of value to know which signature failed the group-check, by index. Maybe you want to know if there are more than one, maybe also specifically by indices. Or maybe it's actually sufficient to proceed till the first bad one and simply return "a signature didn't pass the group check."

Just in case for reference. Keeping it to lower level is considered beneficial for the following reason. It allows to a) minimize the amount of thread-join points (so that we stay on the right side of the Amdahl's law;-); b) keep more options open for possible vectorization. This is not to say that new interfaces in bindings are not considered, only that consideration process is more convoluted than might initially appear:-) Please, bear with me:-)

[kirk-baird]

Sure, the main use case which is block processing it doesn't matter to us which signature is invalid. If any of the signatures in a block are invalid we will reject the entire block. However, when we are processing blocks in batch, i.e. one or two epochs at a time then if we have one invalid block it would be helpful to know which block is invalid.

However, I expect the case where we receive invalid blocks to be few and far between, unless someone is specifically trying to DoS the network. So if it is significant decrease in speed due to the thread joining I don't think it is worthwhile at this point to spend time returning which is the invalid signature.

If the speed trade off is negligible then it would be helpful to have.

[dot-asm]

However, when we are processing blocks in batch, i.e. one or two epochs at a time then if we have one invalid block it would be helpful to know which block is invalid.

Since it is caller that has knowledge of which signature belongs to which block, I have to draw conclusion that you'd be interested to know the index of failing signature. And since returning just one is easier to implement, shall we settle for just first failing one?

if it is significant decrease in speed due to the thread joining

It won't be any difference in performance in comparison to just returning success or failure.

[kirk-baird]

However, when we are processing blocks in batch, i.e. one or two epochs at a time then if we have one invalid block it would be helpful to know which block is invalid.

Since it is caller that has knowledge of which signature belongs to which block, I have to draw conclusion that you'd be interested to know the index of failing signature. And since returning just one is easier to implement, shall we settle for just first failing one?

Sounds good, first failing index works for me.