celo-org / celo-bls-snark-rs Goto Github PK

Expected Behavior

We should just instantiate the random oracle with a cryptographic hash function. No need for a key. Also, terminology in the code relating to PRFs should change.

Depends on #55.

Expected Behavior

Use Blake2s in the composite hasher.

Current Behavior

What is the current behavior?

SHA256 is used.

Expected Behavior

Pixel is a forward-secure signature scheme which is attractive: https://eprint.iacr.org/2019/514.pdf.

We should discuss and decide what we want to do about it - should we take, e.g., a two weeks detour to check it out?

Questions that I have at the moment:

1. Is it really 4 exponentiations, without knowing discrete logs of the bases?
2. What are the requirements on the hash function?
3. What needs to be stored and where?
4. What's the effect of the amount of keys we generate on performance? (edited)

Current Behavior

Currently, we're using BLS signatures which are not forward secure.

The current implementation is not compatible with hardware wallet architecture, which using Ledger as a reference can have a little as 4kB volatile memory. A hardware compatible implementation should be made which never exceeds this limit.

Although we are not implementing the SNARK circuit at the moment, we should make sure that we're using a hash function that is SNARK-friendly enough, so that we can batch multiple epochs.

It seems we require around 800 bits of output. They way we achieve it at the moment, when using a 256 bit output, is:

• Hashing the message with a Pedersen hash, which is only collision-resistant.
• Hashing that resulting message 4 times with SHA256 and an incrementing nonce in front of the message, such that we have 1024 random-looking bits.

Some possibilities:

1. What we have now - Pedersen hash over Edwards/SW6 as defined in ZEXE.
2. Rescue/Poseidon - new hash functions from this year, which are very SNARK-friendly.
3. Blake2s/Blake2b/SHA512/SHA3 - SNARK-costly hash functions which mostly vary by their output size and their SNARK cost. We know the cost of Blake2s and SHA256, which output 256 bits. We'll have to evaluate this case-by-case and see if others have done this work in the past.
4. MiMC, which has received some, though still little attention. Very SNARK-friendly.

Currently the repo does not use constant-time signing for BLS. This may make users vulnerable to side-channel attacks. Making signing constant-time will prevent such attacks.

The currently used std::io uses allocation internally. An embedded-friendly implementation not using allocation would build towards hardware wallet compatibility.

Phase 1:

• Validator update logic in circuit (including validator diff encoding and unpacking)
• BLS verification with threshold
• Hash prototype with unoptimized Pedersen hash and Blake2s
• Use GM17 for circuits

Phase 2:

• Decide hash function and implement natively and in circuit
• Hash to group in circuit (TBD whether in BLS12-377 or SW6)
• Groth16 vs Marlin decision and implementation for SW6
• Benchmarks for different amounts of epochs
• Expose C library

Help wishlist:

• Implement Groth16 (either adapt existing code from stefandeml or from scratch)
• Bowe-Hopwood Pedersen hash
• Benchmarks for Marlin
• Benchmarks for amount of epochs
• Relation splitting
• Fancy hash function

Expected Behavior

The direct hasher should use proper Blake2x, rather than the current construction. I believe this would simplify the eventual security proof.

• Think about whether we can reduce 1 compression execution.

Current Behavior

We use a method similar to Blake2x.

We should have a Groth16 implementation natively and in the circuit.

A promising direction is implementing bls12-377 in sapling-crypto.

Expected Behavior

Currently, we only know the performance of a window size of 4 and number of windows around 10k. We should have more benchmarks on different window sizes such that the product remains the same.

@PratyushRT Can you post the image you showed and details on what you benchmarked?

Expected Behavior

Upgrade the Rust toolchain to 1.37 in this repository, in celo-blockchain and celo-monorepo. After doing that, use cargo vendoring.

Current Behavior

We use Rust 1.36.

Validator update logic is as follows:

• Removed validators must be replaced with new added validators
• Hash to group must be done on the same validator diff message
• The BLS signature must be verified

In #63 support was added for the PoP from section 4.4 of https://cseweb.ucsd.edu/~syilek/pkreg.pdf. Compared to the B-Pop protocol in section 4.1, the one in section 4.4 has several weakness. First, PoP4.4 requires sampling a random challenge value, and we'll have to figure out how to do this in a distributed system. Second, PoP4.4 makes honest parties vulnerable to MitM attacks during key registration. Section 4.4 indeed explains how this attack can be carried out with a signing oracle, but by changing the hash function the problem is just moved to needing a registration oracle. In the real world you might obtain a registration oracle via a MitM on an honest party trying to register a key. Unless some sort of at-most-once-per-key registration semantics are implemented (which seems more fraught than switching to B-Pop), this attack becomes practical.

B-Pop may be seen as applying Fiat-shamir to PoP4.4 and gaining non-malleability.

Once_cell

For about a year now the Rust constant-evaluation pipeline has been robust enough that lazy_static is entirely replaceable by the once_cell crate, which provides a macro-free way of doing what lazy_static once did.

rust-lang-nursery/lazy-static.rs#111
rust-lang/rfcs#2788

Currently, the blake2s circuit code doesn't support all the parameter block operations needed.

Expected Behavior

The BLS public key should be tied to the Ethereum address (and maybe other details).

Current Behavior

Currently, the BLS public key and the Ethereum address are independent, opening the validator registration process, opening it to possible attacks.

Celotool currently depends on the Geth repository and Rust toolchain to create proofs of possession. It would be much better to have a pure JS implementation of that part. There's a WIP TypeScript implementation.

Expected Behavior

Celotool should generate a genesis object with BLS public keys and generate proofs of possession.

The validators contract should store BLS public keys and verify proofs of possession.

Current Behavior

Only uses ECDSA keys.

Currently Geth aggregates the public keys directly. With subtraction, it can be faster. The method already exists in the bls-zexe codebase.

Expected Behavior

We should have a hardware wallet compatible implementation. Promising directions seem to be:

• bls12_381 create from Zcash
• RELIC

Current Behavior

We don't have one.

The method should implement the HashToG2 trait.

Some possibilities:

1. Fouque-Tibouchi - https://www.di.ens.fr/~fouque/pub/latincrypt12.pdf.
2. Boneh et al. - https://eprint.iacr.org/2019/403. Method 6 looks particularly relevant and simple to implement. It's similar to Fouque-Tibouchi and well specified for BLS12-381.
3. Continue with try-and-increment, and require as a consensus rule that the "diff header" will hash to a point on the first try.

Currently we have 1 .go file per architecture, due to the celo-blockchain toolchain being rigid for compiling with various CGO flags.

It'd be nice if we could get rid of these files, fix celo-blockchain and specify explicit instructions on how to cross-compile / link this library in various architectures.

An approach for this can be seen in #122 (which we partially reverted due to geth's inflexibility)

We need to implement an API that can be consumed by Go.
Rust allows exposing an "unsafe" C interface, which is suitable for this goal. The Go side should have a memory-safe abstraction over this API.

A successful example is how it's done in librustzcash (although the consumer is C++, I've successfully used a similar method with Go in the past):
https://github.com/zcash/librustzcash/blob/master/librustzcash/src/rustzcash.rs

Some questions to answer:

1. Static vs dynamic library - I'm in favor of static, which goes well with the Go model of a single binary. Might impact licensing considerations.
2. Bridge methods vs specific functions. Instead of implementing multiple C interfaces, it's possible to implement just one and pass serialized messages over it. This method potentially limits the memory-unsafe parts of the code, at the cost of performance, and a possible false sense of security.
3. Are validators running geth? Is there another process they run? It's something I'm not familiar with yet.

Let's use this issue to track any potential optimizations which can be done to reduce the size of our circuits

Expected Behavior

To authenticate a validator owns the private key behind a claimed public key, bls-zexe should provide a proof of possession API.

Current Behavior

There isn't any.

Currently Vec and Box are used in the code as dynamically allocated data structures, which is problematic in an embedded context. Using fixed-size statically allocated equivalents would build towards hardware wallet compatibility.

Expected Behavior

Blocks have the EpochData structure, which is meant to be filled with the SNARK-friendly signed data. We should have a proper encoded struct for that. This issue tracks the encoding of that set to bits.

Current Behavior

Currently, we don't have that.

Meta-issue: #71

Meta-issue: #71

Expected Behavior

We should have another hash implementation that uses the Zcash Pedersen hash described here: https://github.com/zcash/zips/blob/master/protocol/protocol.pdf.

It should have many benefits:

1. More efficient memory-wise.
2. More efficient over-all, when using the Montgomery curve birational equivalence.
3. Much more efficient in a SNARK (might be around 2x).

Current Behavior

We use the Zexe variant from here: https://eprint.iacr.org/2018/962.pdf

Expected Behavior

• Having an independent Sage implementation of the different components of hash-to-group:
  • Pedersen hashes
  • Blake2s hashes
  • Try-and-increment
  • The way we combine them to create the hash-to-group

Current Behavior

We don't have test vectors from an independent implementation.

The currently used std::error::Error uses allocation internally. An embedded-friendly implementation not using allocation would build towards hardware wallet compatibility.

Currently we have weird BE/LE encoding in various places. We must make sure that this is consistent across all necessary codebases, because it's a giant footgun otherwise.

1. geth
2. native hasher
3. snark hasher

Expected Behavior

Geth should use an infrastructure that supports bls-zexe keys, which have a different size and properties than the ECDSA keys used in Geth.

Current Behavior

Geth uses the crypto.Account infrastructure.

Currently errors are "boxed" using Box<dyn Error>. This is problematic in embedded contexts because Box uses allocation. Using stack-based error messages would build towards hardware wallet compatibility.

Expected Behavior

Geth compilation should only build the bls_zexe package.

Current Behavior

#56 introduces separation into algebra and snark packages. Geth doesn't need the snark crate for now.

Once #100 is merged, the Zexe subdirectory won't be needed anymore. That means we can pull the bls crate to the root directory. It'd be also nice to rename the repo to something like bls-rs-snark or similar. Crates can probably be renamed to bls-crypto and bls-snark

Expected Behavior

The validation code will use the bls-zexe code for BLS signatures signing, verification and aggregation.

Current Behavior

Geth uses normal ECDSA signatures.

Depends on #13.

WIP - celo-org/celo-blockchain#326

Expected Behavior

The SNARK-friendly hasher is slow. Sometimes we only need to sign a hash to gain the aggregation benefits.

Current Behavior

There is only the slow SNARK-friendly hasher.

The spec should specify the ultralight sync protocol. This is a bit task, so this issue is to track the initial draft sections and structure of the spec.

Some of the topics to include:

1. Curve choices, together with relevant parameters, such as G1/G2 generators.
2. Diff structure - a list of public keys to remove/add, a signature, etc.
3. BLS signature specification.
4. The algorithms which the validators use to sign and light-clients use to verify.
5. Specific "bits-and-bytes" encodings of relevant elements.
6. What else?

It doesn't have to include at the moment a security analysis.

Expected Behavior

Should have a LICENSE. After a discussion with @timmoreton, it seems the best would be:

• Keep it dual licensed as Zexe is
• Copy the AUTHORS, LICENSE-* files
• Include the section on contributions from the readme License

Current Behavior

What is the current behavior?

There's no license.

Currently the embedded-friendly no-std library is being developed as a separate branch of bls-zexe. Clients should be able to conditionally compile the repo depending on whether they want to use the no-std version or the original version using heap allocation and fine-grained error codes.

Implements the first part of #14.