toposware / winterfell Goto Github PK

This should be useful for checking the validity of the computation
https://github.com/ToposWare/winterfell/blob/e9826fae63adc3557089c5008c90ce5618422af4/examples/src/schnorr/ecc.rs#L63

Related to #4

In the Schnorr signature verification, we need to hash a message of a certain number of BaseElements, which may not fit in the hash capacity. It is currently adding, at the end of each hash cycle, two new chunks of messages in the last two registers of the hash state, corresponding to the hash rate.
Is it acceptable? Does it have any drawback?

Once the design of the state transition function AIR program is completed and tested, we should export the whole AIR in a separate crate, or directly in Substrate in the "Certificate" pallet (or whatever it's called).

Needed for Substrate. May be a desired feature upstream, will contact the author.

In the Schnorr signature scheme, we are using only the first output of the Rescue hash (the output size is 2), for computing the scalar multiplication with the public key of the signer.

Does it involve any security issues?
If using a small field, how is it worsening? (we would still be limited in field size by the DLog if using Schnorr signatures but in the case where we would be using a different signature scheme not relying on large fields, how would that behave?)

We rely on our private repo stark-curve for f252 which won't be made public unlike winterfell.
As decided on the dev roadmap of 11/29, for the OSS release, it should be removed as not being currently used nor planned to be used in the near future.

The original implementation of f252::BaseElement and the associated curve was done (in branch https://github.com/ToposWare/winterfell/tree/f252) inside the math crate. But this requires heavy machinery, and there are considerations (Zeroization, Constant time implementation, Serde support), that are not required by this library but would be on the substrate side.

It would be better to export them in an external crate and define f252::BaseElement as a simple wrapper around the field element implementation.

Migration has been started there and the corresponding (lighter) winterfell update has been done here.

Our State Transition Function could be similar to whats's being prover in the rollup tutorial for R1CS in https://github.com/arkworks-rs/r1cs-tutorial but with extra checks to prevent double spendings (for instance nonce check)

The library is currently using SHA3 and BLAKE3 for public randomness and Merkle tree commitments.
We may want to change this. Implementing algebraic hash functions for recursion? Blake2s if Blake3 is judged not battlefield tested enough?

We currently rely by default on blake3 of sha3 for the out-of-circuit Merkle tree commitments.
Integrating recursion would require the verifier to have an efficiently computable hash function inside the AIR program over the primefield f63 that we use. Hence the need to integrate a hasher instantiation over this field, as a first step towards recursion.

Other instantiations of Rescue-Prime over f62 / f64 are defining a hash state of 12 and a rate width of 8. We'd need to investigate if that is the best ratio also for f63.

We are currently using two versions of Rescue, one for Schnorr that targets small rate but longer cycle, and one in the Merkle tree authentication (modulo wrong field for now) targetting larger rate for shorter cycle length. Once we agree on which to use for the final complete transition_function AIR, it would be necessary to have a proper, clean and secure implementation of Rescue outside of this library, to be reused on the Substrate side for asset transfers.

We may want for the POC to go with something simple, then dealing with a large prime field which is already part of the rest of our software. This would lead to (much?) slower performances, due to the field size and the type of the prime used (for efficient FFTs for instance), but maybe (probably?) ok for the low activity in the POC.

Should we use the field of StarkWare? (i.e. 252bits with very-high 2-adicity of 192)

From the original Table comparison of the Vision/Rescue paper (p40), it seems that for λ = 128 with a prime-field of size ~64bits, GMiMC_erf would outperform Rescue (while being extremely more efficient outside the circuit). It may be worth considering using a different hash function, including also Poseidon.

Note that we can get an extended set of constants for MDS matrices (Poseidon and Rescue) and Round constants (all the above) and make the chosen hash function a customizable parameter.

Some upgrades / new features could be nice but not necessary for the POC itself. They mostly deal with performance improvement on the prover side and/or proof size reduction. Most of them are already on the pipeline of the upstream repo:

Proof size reduction:

• facebook/winterfell#40
• facebook/winterfell#39
• facebook/winterfell#38
• facebook/winterfell#35

Prover speed-up:

• facebook/winterfell#36 (a MUST if we want to go for recursion)
• facebook/winterfell#13

Additional:

• facebook/winterfell#12 (for 128bit security with a small prime field of ~64bits)
• facebook/winterfell#9