Isn't it more sensible to anonymize on-chain voting without touching web2 space?

If I understand, there is no notion of identity here beyond anonymized token ownership, right?

I like that because (a) token ownership can be de-sibeling but (b) does not go beyond de-sibeling into de-anonymizing. Almost any identity schemes proposed winds up de-anonymizing. There are many limitations of using only token ownership for de-sibeling users of course, but they are preferable to all the de-anonymizing junk one normally sees.

Why should B send any transactions? As B is a pseudonym, I'd think B merely needs a certificate in the form of a zero-knowledge proof saying some A exists. What am I missing?

I suppose threshold assumptions suffice for this, which gives rise to simpler schemes, but maybe the bellman tooling is easier at this point.

Anyways I think token ownership as identity might provide a sane step that helps us then ignore must worse proposals. And de-sibeling web2 stuff using this makes sense too.

I'd love to get comments from Philipp Jovanovic @Daeinar and later Bryan Ford

Burdges, glad you think our current thoughts are at least somewhat sensible! @drewstone has also worked on this and can provide more context.

@burdges it should be updated! If you're available for a call, I'd love to talk through some of your questions.

Updated again!

You currently need a chain so that A can register B somewhere, but..

Why should B send any transactions? I'd think B needs A's public key so they can generate some Merkle path in a zk proof, which acts as their identification token.

A group is a Merkle tree with leaves H(H(B || nonce) || A). An identity message has the form (b H_1(id_rept), pi) where B = b G and pi is a SNARK that B exists in the group and id_rept is the identity of the party to whom identity is being proven and H_1 is a hash-to-curve function. B is never revealed anyplace and never possesses funds. We've no nullifiers to reveal either.

As an aside, we could take H(B || A) for the leaf and either do a zk proof that A is inside when creating group leaves, or else reveal B only at registration time, as B is never revealed in redemption. We can avoid B and the group entirely if you do not mind A being online. I'm not suggesting either, but..

If A is a jubjub public key, then we might find some trick for b to be a one-way function of A, so that A need not register B on chain at all, and your group can be defined entirely in the circuit for pi, but A also need not be online. I suppose this requires a Blake2b zkSNARK circuit too, so yes this sounds like a more complex system.

Why should the Merkle tree be sparse?

We're now building a zkSNARK based ring VRF to replace the schnorrkel VRF for polkadot relay chain block production: https://github.com/w3f/research/blob/master/docs/polkadot/BABE/sortition/index.md#ring-vrfs

Our ring VRF will work with a Merkle tree whose leaves are Jubjub keys B_i = b_i G and its public inputs will be a Merkle root and two curve points X and Y, and the zk circuit will prove that Y = b_i X for some leave B_i = b_i G. If X = H_1(msg) then Y = b_i H_1(msg) is a VRF output.

We'd then have an identity scheme if msg is the party to whom identity is being proven. We could make B non-value bearing by constructing the Merkle tree like you envision here.

Anyways, yes we should do a call about this stuff, sorry i missed that part earlier. I'm on vacation next week, but maybe this week, or definitely the week after.

We've some fancier tricks for the ring VRF which i'll try to implement in March.

Would love to chat if you're ever free @burdges. Sounds interesting.

Re-closing since w3f/Grants-Program#216 was accepted and it looks like it does indeed supersede this ;) Sorry for the confusion.