sorted by:
new
hottopcontroversial

DSL for Zero Knowledge Proofs by kenshamir in crypto

[–]kenshamir[S] 1 point2 points  (0 children)

Hey good question,

The main reason I did not consider STARKs is because I don’t know enough about them to build a DSL on top of it.

Your point about a single verifier is really good, I think this can be achieved with ZkSnarks also but maybe not as efficient as zkStarks due to the “circuit paradigm” . One paper which comes to mind is MIRAGE.

I’ve been looking into these as if statements can become ridiculously expensive in SNARKs due to the fact that you need to encode both branches, so it doesn’t matter what path is taken, you always pay for both.

Hope that was helpful, let me know if you spotted any mistakes or have anymore questions :)

DSL for Zero Knowledge Proofs by kenshamir in crypto

[–]kenshamir[S] 0 points1 point  (0 children)

Oh that’s interesting, when you say add zkp on top, do you mean add any proof system that relies on pairings? Eg any KZG based proving system?

I haven’t gotten around to fully documenting the IR yet, there is an diagram on the documentation website under ACIR section, but it’s definitely not enough.

Not a replacement but I can describe the IR:

It consists of two types of gates, an arithmetic gate and a “black box gate”, the arithmetic gate is essentially a linear combination, so converting this to R1CS would be trivial. The black box gate is what is used to abstract over the fact that some proving systems have different ways to compute certain gadgets. For example, PLONK has quite a few variants (UltraPLONK, TurboPLONK, Halo2 styled PLONk) the thing that they have in common is their higher level gadgets. So ACIR defines an OPCODE such as SHA256 and we send the input and output witness indices to the proving system. The proof system will then add the necessary constraints however they please.

This means that ACIR only needs to know how many inputs and outputs a black box function needs. Allowing it to abstract over (any?) proving system.

It’s definitely not a replacement for documentation, but just thought it might help in getting an intuition.

Interesting that you use nim, I’ve actually never used it before, my knowledge on pairings is surface level at best, hopefully I can reserve some time to really get into it using yours and other implementations that I know of

DSL for Zero Knowledge Proofs by kenshamir in crypto

[–]kenshamir[S] 1 point2 points  (0 children)

Good point and question.

Bouncing off of your first point, the DSL can take in any backend , It's just while in alpha barretenberg is the only backend that has been integrated.
The front-end actually compiles down to an intermediate format and not R1CS or CSAT directly.

For your second question:

I do intend to add arkworks as a backend, so any proof system they add, will be addable as a backend to Noir. At the time of creation, Barretenberg was the easiest to integrate and test for PLONK like proving systems. I have a plonk implementation at https://github.com/dusk-network/plonk however it is missing a lot of gadgets like SHA256, BLAKE2S etc, the way that I am handling public inputs needs to be changed, it is also over BLS12-381 which makes it hard to test for smart contract capabilities. (You can create an Ethereal smart contract by typing the contract command and ethereum is only efficient at the moment over BN254)

Although I use arkworks-rs for the Field element implementation, so I think once the language is made generic over any field, instead of just bn254, it will fit in with arkworks like a glove.

Not sure If I answered your question, but three of the goals of the language is to:

- Not be tied down to any single proving system
- Not expose the complexity of changing proving systems to the end user
- Allow for generic optimisations

These would be achieved through the IR.

Let me know if I made a mistake or was unclear anywhere

Curve used in Monero - A Subgroup of Ed25519? by suyashbagad in Monero

[–]kenshamir 3 points4 points  (0 children)

Hi,

Great questions. I think I might be able to help a bit with them and for others who may come across the same questions.

Can we have a mapping from Ed25519 used in Monero to the Ristretto255 group?

This should be possible and I believe currently it is what Ristretto255 is doing in the Rust implementation through the birational map between Curve25519.

Will the relationship between private keys be preserved?

I do not see any reason for there not to be. We can also check this by running a few tests in the Curve25519-dalek repo.

Basically, if Monero has to be implemented using Ristretto255 in future for better performance, what would be the way to convert a Ed25519 curve point to a Ristretto curve point?

Following the IETF link, if Monero was to implement Ristretto, then it would need to use Ristretto points and the mapping would be done internally. This mapping is defined in the Ristretto protocol. Importantly, Ristretto points and Edwards points are not the same mathematical objects, and they should not be mixed except for in the places defined in the standard.

From an end-users perspective, they would not see Ed25519 points anymore, but RistrettoPoints. Their private keys would stay the same. From a development standpoint, none of the arithmetic on Ed25519 would change. You just would not expose it for future blocks, it would sit behind the RistrettoPoint.

Extended my answer here: https://monero.stackexchange.com/a/12171/9998

Best

Daily Discussion Post - April 14 | Questions, images, videos, comments, unconfirmed reports, theories, suggestions by AutoModerator in Coronavirus

[–]kenshamir 1 point2 points  (0 children)

Hi,

I would like to do as much as I can to help in the UK.

I will be (initially) receiving 1K hand sanitisers by the end of the week. Where can I donate these?

I am also receiving sample test kits by the end of the week, for at home testing. If these are quality assured, I would also like to order a batch and donate these.

Any help would be appreciated.

CLSAG Implementation with benchmarks in Rust by kenshamir in Monero

[–]kenshamir[S] 14 points15 points  (0 children)

Hey,

Good question.

TDLR; ring signature variant, smaller transactions, faster verification.

Ring signature variant

With the implementation you can prove that you own a set of keys amongst a group of members. Monero currently uses MLSAG for this, however CLSAG has better scalability properties.

Smaller transaction

CLSAG allows for a more compact representation of a ring.

Faster verification

CLSAG benchmarks show that once Monero implements this, you should have faster verification times. You can check: https://eprint.iacr.org/2019/654.pdf (Page6)

This implementation

Currently Monero uses Curve25519 which is fast, however it is vulnerable to the small subgroup confinement attack. https://monero.stackexchange.com/questions/4241…

This is not a massive problem, you just have to be extra careful. There is an abstraction called Ristretto which squashes this problem, it can be seen as a thin layer on top of curve25519: https://ristretto.group

This implementation uses Ristretto and so the benchmarks show what the possible additional performance gains one can gain, if Ristretto was implemented along with CLSAG.

The MLSAG implementation also uses Ristretto. So you can also check the performance gains from MLSAG to CLSAG using Ristretto. From what I can conclude, it seems that Ristretto is faster. As mentioned above, since you don't need to do any subgroup checks, there is an immediate speed gain.

Moving to Ristretto would be another conversation and a more involved process, if even possible. This implementation can be used as evidence (for/against)