MMR PoR: How to do a proof of reserves on a parachain without leaking information?

I’d like subscribers to a social media public (i.e. nostr) channel to prove that they own an account on a parachain with a minimal balance. But I’d like to avoid linkability between the user’s SM account and their wallet.

So, the requirements are:

  • Only owners of a specific parachain token can write in the public channel.
  • No information about the owners’s balances nor transaction activity leaks - beyond proving ownership of a minimal amount

Non-requirements

  • While clearly an improvement, it is not a requirement to prevent a token owner from creating many identities on SM

AFAIU, this could be done with a merkle mountain range proof of reserves (MMR PoR). Such a PoR could have validity for N days after the block used for the proof.

As the fund threshold would be low (could be as low as ED), the use of one time addresses would be an option, if that makes for a simpler solution. However, the problem of generic PoR will have to be solved sooner or later anyway, I guess.

Assuming:

  • the verifier runs a collator of the parachain in question or trusts a remote rpc endpoint

Has anyone worked on this or are at least concepts around?

1 Like

In theory, Yafa-108/146 yield efficient zk proofs of Ed25519/Ristretto arithmetic, but it’ll run stupidly slow with that q=575 bit base field.

You could do a zk proof of the account existing in the chain’s state, do slow non-native arithmetic for one fixed base scalar multiplication that blinds the public key, and then prove knowledge in Ed25519/Ristretto. It’ll have running time similar to the original zcash, so a couple minutes on a sensible desktop computer, which users must rerun every time they post after your app decides it wants more updated balances.

It’s faster if the parachain uses a snark friendly merkle tree, but then other operations become slow, so this makes sense for a zcash like chain, etc.

If you only care about someone being a token holder sometime in the past then they can register on a snark friendly merkle tree using their account transparently, which leaks which accounts participate. After this, they can participate all they like anonymously, although persistent pseduonyms kinda wreck the anonymity here.

Why do you care about balances at all? Is it not enough to know they are a unique person? If so we’ll hopefully deploy something that’ll help eventually.

1 Like

This is an interesting solution indeed

Well, the idea here is actually to provide a public chat for Encointer communities - which are all about unique personhood :wink:

However: The currently deployed personhood protocol is still transparent/pseudonymous. So, if we’d like to only let members of that community write in the public channel, we have basically two choices:

  • minimal balance in the community currency (which includes more people - and businessses too)
  • proof of attendance at regular cycle gatherings along the Encointer PoP protocol (includes less people and strictly no businesses)

Both options carry their linkability risk. Not only for privacy resons, but such linkability could ease collusion attacks on the PoP protocol

@burdges Thinking about your idea, it may be even simpler (or looks simpler given my shallow knowledge of ZKP math): accounts that would like to post in the channel just register to an onchain set. Then the proof would simplify to an (linkable or unlinkable …doesn’t really matter AFAIU) ring signature to prove membership in that set. Proof size should be log(n) and is not so critical because it is validated off-chain in the mobile app (write restriction is applied client-side: messages are just not shown to the readers. This way we can use standard nostr relays)

Of course, the timing of registering to this set and then posting on the channel for the first time leaks information…but we may mask that somehow

Author Scenario:

  1. registers for membership in authors set with an extrinsic to the Encointer parachain
  2. At block XYZ, generates a ring signature for the set state at that block height
  3. posts the signature and block hash to their nostr profile (custom attribute)

Reader Scenario:
For every unkown post author, do:

  1. read proof from profile. If block too old, hide author
  2. fetch entire authors set at this block
  3. verify proof
  4. cache verification result
1 Like

I briefly mentioned doing community moderation with ring VRFs in section 8.3 of Ethical identity, ring VRFs, and zero-knowledge continuations

I’ve largely implemented the “Pedersen VRF” component of the ring VRF in ring-vrf/dleq_vrf at master · w3f/ring-vrf · GitHub and Sergey (W3F) did the “Web3sum” component for Sassafras sized rings in GitHub - w3f/ring-proof: ring-vrf ring proof v2.5 We’ll have some on-going flux among these repos, like maybe one “Web3sum” repo for both the ring-proof and the beefy proof in GitHub - w3f/apk-proofs

We’ll need larger rings though for users, so really we need to implement the “SpecialG” proof from the paper I liked above, which scales better. We’ll land sassafras first though…

2 Likes