Add the circom compatible Baby Jubjub curve

[Shigoto-dev19]

Description

• Added a Circom compatible Baby Jubjub elliptic curve according to ERC-2494.

  • The literature test cases are verified(not explicitly added in order to respect the architecture!).
  • The architecture is kept the same as the other Twisted Edwards curves by arkworks-rs/curves.
  • The package ark-jubjub is already used locally and verified to be running equivalently to circomlibjs babyjub but with much better performance.

• Note: I highly appreciate the optimized impementations of EC Cryptography by arkworks-rs and thanks to the flexible API, I hope that this PR would be beneficial to the community regarding the fact that, I personally could not find any circom-compatible and efficient Baby Jubjub implementation as this one.

---

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [x] Targeted PR against correct branch (master)
• [x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [x] Wrote unit tests
• [x] Updated relevant documentation in the code
• [x] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [x] Re-reviewed Files changed in the Github PR explorer

[Pratyush]

Hi @Shigoto-dev19, Thank you for the PR! I believe we already have an implementation of Baby Jubjub in the repo, it's under the name ed_on_bn254; is your implementation different from the existing one? Put another way, is the existing implementation incompatible with the circom one?

[Shigoto-dev19]

Hi @Shigoto-dev19, Thank you for the PR! I believe we already have an implementation of Baby Jubjub in the repo, it's under the name ed_on_bn254; is your implementation different from the existing one? Put another way, is the existing implementation incompatible with the circom one?

Hi @Pratyush, yes; I tried ed_on_bn254 myself and I can confirm that it is not the same as the Baby Jubjub curve; Hence not compliant with the circomlibjs or babyjub circuit. For this reason, I added it myself to the arkworks-rs curves.

Please let me know if you need a detailed report on references and marking differences in my implementation.

[burdges]

Just fyi, jubjub is an existing curve: https://github.com/arkworks-rs/curves/tree/master/ed_on_bls12_381 the crate name & dir are wrong here.

Anyways the Fr agrees with ed_on_bn254, so this curve should be isogenious.

[Shigoto-dev19]

Just fyi, jubjub is an existing curve: https://github.com/arkworks-rs/curves/tree/master/ed_on_bls12_381 the crate name & dir are wrong here.

Anyways the Fr agrees with ed_on_bn254, so this curve should be isogenious.

• That's true indeed.
• I run the following code in zkrepl for instance, and compare to either ed_on_bls12_381 or ed_on_bn254 but I got no compliant results.

include "circomlib/escalarmulfix.circom"; include "circomlib/bitify.circom";

template BabyJub() { signal input e; signal output out[2];

var base[2] = [5299619240641551281634865583518297030282874472190772894086521144482721001553,
               16950150798460657717958625567821834550301663161624707787222815936182638968203];

component n2b = Num2Bits(253);
component escalarMul = EscalarMulFix(253, base);

var i;

e ==> n2b.in;

for  (i=0; i<253; i++) {
    n2b.out[i] ==> escalarMul.e[i];
}

escalarMul.out[0] ==> out[0];
escalarMul.out[1] ==> out[1];

}

component main = BabyJub();

/ INPUT = { "e": "2" } /

- Also, if you add the following literature tests from [ERC-2494](https://eips.ethereum.org/EIPS/eip-2494) the tests will fail for both  ```ed_on_bls12_381``` or ```ed_on_bn254``` 
```rust
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    pub fn test_jubjub_addition() {
        let x1 = MontFp!("17777552123799933955779906779655732241715742912184938656739573121738514868268");
        let y1 = MontFp!("2626589144620713026669568689430873010625803728049924121243784502389097019475");
        let p1 = EdwardsAffine::new_unchecked(x1, y1);

        let x2 = MontFp!("16540640123574156134436876038791482806971768689494387082833631921987005038935");
        let y2 = MontFp!("20819045374670962167435360035096875258406992893633759881276124905556507972311");
        let p2 = EdwardsAffine::new_unchecked(x2, y2);

        let p3 = (p1 + p2).into_affine();

        let x3_expected = MontFp!("7916061937171219682591368294088513039687205273691143098332585753343424131937");
        let y3_expected = MontFp!("14035240266687799601661095864649209771790948434046947201833777492504781204499");

        assert_eq!(p3.x, x3_expected);
        assert_eq!(p3.y, y3_expected);
    }

    #[test]
    pub fn test_jubjub_doubling() {
        let x = MontFp!("17777552123799933955779906779655732241715742912184938656739573121738514868268");
        let y = MontFp!("2626589144620713026669568689430873010625803728049924121243784502389097019475");
        let p = EdwardsAffine::new_unchecked(x, y);

        let p_doubled = (p * F::from(2)).into_affine();

        let x_expected = MontFp!("6890855772600357754907169075114257697580319025794532037257385534741338397365");
        let y_expected = MontFp!("4338620300185947561074059802482547481416142213883829469920100239455078257889");

        assert_eq!(p_doubled.x, x_expected);
        assert_eq!(p_doubled.y, y_expected);
    }

    #[test]
    pub fn test_jubjub_doubling_identity() {
        let x = MontFp!("0");
        let y = MontFp!("1");
        let p = EdwardsAffine::new_unchecked(x, y);

        let p_doubled = (p * F::from(2)).into_affine();

        assert_eq!(p_doubled.x, x);
        assert_eq!(p_doubled.y, y);
    }

    #[test]
    pub fn test_jubjub_membership() {
        let x = MontFp!("0");
        let y = MontFp!("1");

        let p1 = EdwardsAffine::new_unchecked(x, y);
        let p2 = EdwardsAffine::new_unchecked(y, x);

        assert_eq!(p1.is_on_curve(), true);
        assert_eq!(p2.is_on_curve(), false);
    }

    #[test]
    pub fn test_jubjub_base_point_choice() {
        let Gx = MontFp!("995203441582195749578291179787384436505546430278305826713579947235728471134");
        let Gy = MontFp!("5472060717959818805561601436314318772137091100104008585924551046643952123905");
        let generator = EdwardsAffine::new_unchecked(Gx, Gy);

        let base = (generator * F::from(8)).into_affine();

        let Bx = MontFp!("5299619240641551281634865583518297030282874472190772894086521144482721001553");
        let By = MontFp!("16950150798460657717958625567821834550301663161624707787222815936182638968203");

        assert_eq!(base.x, Bx);
        assert_eq!(base.y, By);
    }

    #[test]
    pub fn test_jubjub_base_point_order() {
        let Bx = MontFp!("5299619240641551281634865583518297030282874472190772894086521144482721001553");
        let By = MontFp!("16950150798460657717958625567821834550301663161624707787222815936182638968203");
        let base = EdwardsAffine::new_unchecked(Bx, By);

        let order = MontFp!("2736030358979909402780800718157159386076813972158567259200215660948447373041");
        let p = (base * order).into_affine();

        assert_eq!(p, EdwardsAffine::zero());
    }
}

• I also used the Baby Jubub curve API from circomlibjs and it is unfortunately not compliant with any of the arkworks curves.

• I am not trying to put my name as a contributor in arkworks, not also that I am an expert in Cryptography or Rust, I barely started learning rust one month ago, I struggled a lot to use rust for the Baby Jubjub circom-compatible curve. I might have overlooked sth here, but all I know that I extensively tried everything but nothing worked.

• I don't care if you merge my PR or not, all I wanted from the beginning is to put traces to my efforts so if someone one day follow the same approach for the same reason, I don't want them to get frustrated like I did.

• Thank you for your attention and considerate replies :)

[Pratyush]

Hi @Shigoto-dev19 ,

It seems that the curve equation used by circom is different from the one that we've implemented (but the curves are otherwise isomorphic).

So I think a good way to proceed would be for you to add your new parameters (from jubjub/src/curves/mod.rs) in the ark-ed-on-bn254 crate (e.g., in https://github.com/arkworks-rs/curves/blob/master/ed_on_bn254/src/curves/mod.rs)

This should save a bunch of duplication (e.g., you would not need to reimplement the fields), and would make the relation between the two curves clear.

[Shigoto-dev19]

Hi @Shigoto-dev19 ,

It seems that the curve equation used by circom is different from the one that we've implemented (but the curves are otherwise isomorphic).

So I think a good way to proceed would be for you to add your new parameters (from jubjub/src/curves/mod.rs) in the ark-ed-on-bn254 crate (e.g., in https://github.com/arkworks-rs/curves/blob/master/ed_on_bn254/src/curves/mod.rs)

This should save a bunch of duplication (e.g., you would not need to reimplement the fields), and would make the relation between the two curves clear.

Hi @Pratyush I agree, I also made sure that they are different curves by using a new base point from the literature and doing EC operations instead of ark-curves generator(regarding that arkworks generators are different). Still, no result was satisfying as well. I got the desired curve from the fork I did and that's why I tried to show it in this PR. Thanks for the recommendation but I still don't fully get the context :thinking:

[rsinha]

I ran into similar issues when working with noir and arkworks, where the default implementations of babyjubjub seem to be incompatible -- for example, the generator specified in eip-2494 does not lie on the curve defined in ed_on_bn254.

Is there a plan to merge this PR? Or, create a new PR as suggested above to avoid duplication?

[Pratyush]

Sorry for the trouble, but we've migrated all activity in this repo over to arkworks-rs/algebra. We're going to archive this repository, so I encourage re-opening this PR against that repo.