Currently in the decaf377 repository the following should work:

• No default features, using the u32_backend (for hardware wallets)
• Default features, using the u32_backend,r1cs features (for WASM)

However, when r1cs is enabled, arkworks is enabled, which incorrectly forces the use of the u64_backend: https://github.com/penumbra-zone/decaf377/blob/main/src/fields/fp.rs#L16

Discovered in: penumbra-zone/web#1492

Right now a lot of code is duplicated:

• Functions in both u32, u64 backends
• Elligator map and other related logic between arkworks and min_curve backend
  Also, our hacky python script still involves a lot of manual copying, but now we know exactly the constants we need, and can have the script simply generate all of the rust code directly, and have a single constants file.

At some point we should take care of these, on a rainy day with nothing better to do.

We have basic implementations of everything we need for the first MVP, but we should come back to

• Optimizing the algorithm for finding inverse square roots - see TODOs in https://protocol.penumbra.zone/main/crypto/decaf377/invsqrt.html
• Optimizing hash-to-group - e.g. in the description in https://protocol.penumbra.zone/main/crypto/decaf377/group_hash.html we're computing 1 absolute value each time

Followup from #31

Remove Element::map_to_group_cdh and Element::map_to_group_uniform from the public API - this can be done after the release of the next testnet on Monday, August 8th, 2022

Same with the compression/decompression methods without the vartime token

We have a stub implementation of Element::vartime_multiscalar_mul that we should fill in (or remove it?)

In PR #38, we add an optional r1cs feature that lets us add decaf elements to arkworks r1cs constraint systems, and implement a bunch of gadgets that let us do various operations on these decaf elements in R1CS, i.e. decompress/compress, equality checks between decaf points, and elliptic curve arithmetic.

One followup from #38 is to add support for the elligator map in circuit. We need this for computing the asset-specific generators when checking the integrity of balance commitments.

In the CI config (as in the main penumbra repo) being added in #2 we have clippy commented out, at some point we can resolve those clippy warnings and re-enable the CI check in this repo

Today @zbuc discovered that the implementations of Add and AddAssign differ for ElementVar. Commit 1243d07 has a small reproducer.

The problem here is due to the LazyElementVar we added in #42. The goal of this was to simplify circuit programming: previously we had in several places in the circuits for Penumbra defined the same underlying variable both as an ElementVar and as FqVar (when we wanted the encoding - the element in its compressed form), e.g. we'd have both nk_element and nk_fqvar. The LazyElementVar enabled us to:

• define a single variable nk that would lazily store either an ElementVar, an FqVar (compressed form), or both,
• allow the user to call nk.compress() (and nk.decompress()) as many times as is convenient without needing to be concerned about adding constraints for the compression a second time, as the FqVar if it already exists would be returned to the user,

However, in the implementations of the *Assign operations, the inner value on the LazyElementVar was not updated. In this snippet below, self.inner.element() returns a cloned ElementVar, so the original value was not updated:

impl<'a> AddAssign<&'a ElementVar> for ElementVar {
    fn add_assign(&mut self, rhs: &'a ElementVar) {
        self.inner
            .element()
            .expect("element will exist")
            .add_assign(rhs.inner.element().expect("element will exist"));
    }
}

In #34 in commits 41c0d48 and c1db5ad we updated the Rust encoding/decoding of Fq field elements to ensure that the top three bits of the last byte are unset. We should make sure the Sage code is doing the same in the Decaf_1_1_Point class.

Right now we have arkworks compatability for the fields, but users would still need to implement the whole BLS12-377 stack themselves by creating appropriate configs. To avoid repeating this, we want a module doing this in this crate.

We should migrate other crates that depend tightly on decaf377, namely decaf377-rdsa and decaf377-ka into this repository, creating a new workspace.

This would have avoided the need to use git tags recently when shuffling stuff around, and the need to duplicate CI code between the places. These crates will remain tightly coupled for the foreseeable future, so a workspace is sensible.

We should cut a point release for the bug fix we had.

Right now, several decaf377 dependents like decaf377-rdsa, -ka, etc. were upgraded to recent code changes, but used git tags because of instability related to adding the necessary methods they needed at the last minute.

We should finalize adding these, and then make all of them use a new release we tag.

In working on #3675 - making poseidon377 work in a no_std environment without a global allocator, i.e. without arkworks - there is some additional functionality needed in this crate on Fq when the arkworks feature is not enabled. This ticket is to track those items as we find them:

• Fq::pow() - used in poseidon-parameters for the computation of the cofactor matrix here as well as for the computation of the SubWords layer in poseidon-permutation here. This was previously provided via arkwork's ark_ff::Field trait (ref).
• TK

Followup from #38. When we witness a decaf element, we do some expensive checks in R1CS to certify it is a valid point. This is done in the implementation of AllocVar::new_variable for ElementVar. I think it would be good to add another benchmark to this repository for our awareness benchmarking that function during proof creation. This benchmark should set mode to AllocationMode::Witness.

After #42 we should add another type in the R1CS feature that represents the encoding of a decaf377 Element in circuit. This type will be called EncodingVar.

Internally, EncodingVar will hold a LazyElementVar created using LazyElementVar::new_from_encoding.

EncodingVar should be public, and used anywhere in the ElementVar API where the encoding is returned or taken as an argument, i.e. compression/decompression.

As part of penumbra-zone/penumbra#3526, we added fiat-crypto formally verified field arithmetic implementations to decaf377, moving away from using the Arkworks field arithmetic imlpementation. This unblocked development of Penumbra's ledger app, since the Arkworks field arithmetic allocated.

However, @TalDerei did some very helpful benchmarking here and found that we have a significant performance regression.

This performance regression is blocking migrating downstream crates to the latest stable release (0.9.0, see #93). To move forward without introducing a performance regression we should switch back to Arkworks field arithmetic for the 64-bit backend only. Embedded environments like Ledger development will use the 32-bit backend which will continue to use the formally verified fiat-crypto field arithmetic.

See suggestions in: https://research.nccgroup.com/2022/09/12/public-report-penumbra-labs-decaf377-implementation-and-poseidon-parameter-selection-review/

Note that arkworks isn't currently constant time, so this is on hold for now

The wrapper types added in #64 don't include inversion. The fiat-generated code has methods that seem to be intended to be used to implement inversion (divstep etc, as seen in cargo doc --open). We'll need to figure out how to use these:

• Figure out how to wrap the raw fiat methods into our wrapper types. This could either be Fq::inv(&self) -> Option<Fq> (returning None if self == 0) or Fq::inv(&self) -> Fq (returning 0 if self == 0), whichever is convenient to implement.
• Add property tests that inversion works.
• Copy wrappers across all six field impls {u32, u64}::{Fp, Fq, Fr}.

Currently, the conventional basepoint is created using the Element::basepoint() method. But Element is already designed to be used with the crate prefix as decaf377::Element, so decaf377::Element::basepoint() is a bit unwieldy and redundant.

Reported in Discord:

pcli panicked with the following when I tried to generate a wallet: thread 'main' panicked at 'no entry found for key', /home/.../.cargo/git/checkouts/decaf377-759be7b9e0a7e297/d777a1b/src/invsqrt.rs:151:18

This is an error from when the computed alpha for i=5 (the last iteration) in the Sarkar algorithm is looked up in the s table, so there must be a bug somewhere

https://eprint.iacr.org/2021/1152 proposes a new curve defined over the BLS12-381 scalar field called Bandersnatch. This curve has an endomorphism that allows use of the GLV method, making it faster in the software context (outside of a circuit).

Currently, decaf377 is defined in terms of the Edwards-on-BLS12-377 curve created as part of the Zexe paper. But there's no really compelling reason to use that curve in particular — unlike the scenario for ristretto255, there is not a large deployment base already using that curve.

So, instead, it might be better to try to apply the same techniques in the Bandersnatch paper to create a GLV-compatible Edwards curve defined over the BLS12-377 scalar field, and then define decaf377 in terms of that curve.

From #3526

This is a ticket for adding support for decaf377::Element in jf-plonk ark-groth16:

Note: The below is deprecated and applied to when we were going to use plonk but something similar will be done for Groth16

• Add an optional proofs feature for all the below logic that requires jf-plonk (see: 8689d27)
• Add an extension trait on PlonkCircuit<Fq>
• Possibly add a newtype wrapper like EncodingVariable(pub Variable) (to represent an encoded decaf point)
• Create a ElementVariable wrapper around jf-plonk's PointVariable: this type will only be created by decoding an EncodingVariable or by operating on ElementVariables. This ensures that we are always working with a valid decaf point.
• Implement encoding and decoding functions (btwn Fq field elements and decaf points)

We need to add new CI jobs that:

• Test with the u32_backend: #72
• Build in a no alloc environment: #76

Not super high priority but someday it would be nice to run the sage files in CI also since we do have tests in there. Currently I'm running the tests whenever I change the file before merging something.