Recently, I’ve stumbled on this blogpost. It is about recent work of Aayush Gupta and Kobi Gurkan on deterministic signatures.
I’ve thought about similar multi-Schnorr schemes, and the possible features they enable, and here I’d like to present a particular interesting usecase - sybil-resistant compartmentalization.
Imagine a zk-chat (or forum, or social network), in which an account is represented by a keypair.
We want accounts to be able to create “identities”, possibly multiple ones, we call them “sisters” if they originate from the same account.
We want to be able to prove that
X (controlled by you) is sister to identity YX (controlled by you) is NOT sister to identity YIn the second case it must not require cooperation from controller of Y.
This potentially would unlock some very interesting opportunities - for example, right now when we use social networks, we either use real names (which gives good sybil resistance but no privacy), or use pseudonymous handles - which provides no sybil resistance excluding some sort of reputation value.
However, this system would allow to get best of both worlds - the initial accounts can be as sybil resistant as we want them to be, and the identities would be private. However, sybil attacks would be trivially countered (say, by requiring that the previous 100 messages in the particular chat / discussion thread do not originate from the sister identity).
Reputation could also be partially transferred between identities - for example, new pseudonymous identity would potentially be able to prove that her sisters have some threshold reputation value. This is also a sort of soft sybil-resistance mechanic.
My approach to this problem is similar to the deterministic signatures described in the linked blog, but I will try to keep exposition independent.
We assume that account is a keypair (G, pG) on some elliptic curve without pairing. When we want to create an identity, we (somehow) sample the point Z from the system. It is mission critical that this Z is obtained by hash to curve, so no discrete log relations with it are known.
Here, it is important that Z is constructed in a publically verifiable way, because adersarial choice of Z will break the system. Possible ways would be either sampling it from block hash + tx id, or sampling it from account’s private data + nonce and accompanying with zk-proof of well-formedness.
The identity is constructed as (Z, pZ).
Let’s see how we can satisfy the required properties. Given two sister identities, we need to prove that the quadruple (Z, pZ, T, pT) is a Diffie-Hellman quadruple. This can be done using a multi-Schnorr proof.
Now, what is more interesting, the owner of identity (Z, pZ) can prove that they do not control identity (T, qT) for p != q, without knowing q! This is done simply by correctly constructing (T, pT) and checking pT != qT.
This is the place where adversarial choice of T would trivially break the system.
If we are not constrained by initial accounts being Ethereum-compatible, the schema can be modified to be post-quantum.
The identity will be constructed as (z, Hash(z, p)), and accompanied with proof of correctly multiplying by (some) p in the Merkle tree of accounts.
The rest is very similar.
It makes sense to use it even with non-post-quantum secure zk-proof component, because then privacy will still be unconditional.