What I learned about private membership in Compact (and 2 problems it created)

Technical Questions
1

Sharing something that changed how I build on Midnight, plus where I got stuck afterwards.

The lesson: I was using a Set to check whether someone was on an approved list. Seemed obvious. It is wrong. A Set reveals which element you tested. Set.member(x) discloses x, so every check leaks exactly who is being checked, and if the same person checks in repeatedly, all their visits become linkable. I would have shipped that without noticing.

The right tool is a HistoricMerkleTree with the membership path supplied as a witness. The person proves they are somewhere in the tree without revealing where. I picked this up from @DR.Ecovery’s thread on ZKP compliance for 42 CFR Part 2 (ZKP compliance for 42 CFR Part 2 — substance use treatment privacy), a check-in app for a drug recovery centre using HistoricMerkleTree plus a path witness plus nullifiers, so nobody can tell which patient checked in. Seeing it applied to something with real stakes made it land far better than reading the rule on its own. The disclosure docs state it plainly too, and it is an easy line to skim past.

Then that lesson created two problems I had not anticipated.

1. Proving membership works. Proving optional membership does not.

I am building a credential where two of three independent issuers have to vouch for you. So I need to ask each tree “is this person in you?” and be able to accept “no”. If they are not in that tree, the witness cannot produce a valid path, and the whole proof dies. A threshold becomes impossible to express.

What worked: when the person is not in a tree, the witness returns a well formed but deliberately invalid path, correct shape with dummy siblings. The recomputed root matches nothing, checkRoot returns false, and the circuit carries on. That lets you write (a && b) || (a && c) || (b && c).

On the TypeScript side the witness is just tree.findPathForLeaf(leaf) ?? dummyPath(leaf), where the dummy is { sibling: { field: 0n }, goes_left: false } repeated to the tree depth.

2. Revocation fights unlinkability.

The obvious way to revoke someone is a blocklist. But checking one means disclosing a stable value about that person on every proof, which undoes the privacy you just bought. (Brave Research flagged this exact tension last November: privacy preserving revocation is underdeveloped and hard to reconcile with unlinkability guarantees.)

What worked: bind each leaf to a time period, and re-attest on a schedule. Revoking someone is then simply not renewing them. They hold no valid leaf for the new period. No blocklist, nothing disclosed. Same idea as the web moving to short lived certificates instead of revocation lists. The cost is that revocation takes effect at the next period rather than instantly.

Small gotcha while wiring up tests: a Compact Counter shows up on the generated TypeScript Ledger type as a plain bigint. It is ledger.myCounter, not ledger.myCounter.read().

Still building this out as a proof of concept. The contract compiles on 0.31.1 and the tests pass. I will share it once it is in a state worth reading. If there is a better way to do either of those two things, I would genuinely like to hear it.

One last thing, said with affection. I am self taught, and somewhere between the failed proofs and the third rewrite I worked out that the part I enjoy most is not making the compiler happy. It is figuring out what the thing should be and who it is actually for. If that is a job in crypto, something in the design thinking and operations direction rather than a pure dev seat, I would love to hear how people ended up in those roles.

2 Likes
2

Welcome @uetto.sec this is a really clear write-up. The Set.member() vs HistoricMerkleTree lesson is one a lot of people learn the hard way; naming the disclosure leak and the linkability over repeated checks is exactly right.

On the two follow-ons:

  1. Optional / threshold membership
    the dummy-path pattern is a solid Compact-shaped workaround when you need checkRoot == false without the witness failing. One privacy footgun to watch: if you disclose(a), disclose(b), disclose(c) individually, you leak which issuers attested even when the final (a&&b)||… stays private. Prefer computing the threshold inside the circuit and disclosing only the final Boolean (or a commitment to the outcome), not the per-issuer bits.

  2. Revocation vs unlinkability: epoch/period-bound leaves (don’t renew = revoke) is the usual unlinkable approach; short-lived certs over CRLs is the right analogy. Tradeoff is grace until the next epoch. If you ever need faster kill, people usually combine short epochs with an issuer “current root” rotation rather than a public blocklist of stable IDs.

Counter → bigint on the TS Ledger type is also a common gotcha thanks for calling it out.

Would love to see the PoC when it’s readable. And on the last point: yes, that “what should this be / who is it for” muscle is a real seat product/protocol design, solutions architecture, DX advocacy, privacy UX.
A lot of the best Compact work starts there and only then goes to circuits. Looking forward to what you ship.

1 Like
3

Thanks for taking the time to look at this… Proper review…

Your first point landed on something real in my code, so I want to name it rather than quietly fix it.

I am not disclosing the per issuer booleans directly. But each of my three membership checks calls checkRoot on a different tree, and checkRoot is a ledger read, so the computed root has to be disclosed. The public transcript ends up carrying three roots, one per agency. For an agency I am actually in, the disclosed root matches a real historic root of that tree. For one I am not in, my witness returns a dummy path and the root matches nothing. So anyone reading the transaction can compare and work out which agencies attested me. The final 2 of 3 boolean stays inside the circuit like I wanted, but the ingredients are sitting in public. Same leak with extra steps.

I believe the fix is stop using one tree per agency. Put every attestation in a single tree with the leaf as hash(identity commitment, period, issuer tag), then prove two memberships against that one tree and assert inside the circuit that the two issuer tags are different and both leaves belong to the same identity. Both disclosed roots are then just valid roots of the same shared tree, and they say nothing about who signed.

That is a rewrite and not a patch, so it goes on the list rather than into today’s build.

Repo is here, still very much a proof of concept: GitHub - tomiin/threshold: Prove you are allowed in without saying who you are. Privacy-preserving age and eligibility verification with 2-of-3 government attestation and user-held self-exclusion, written in Compact on the Midnight network. · GitHub

It is a 2 of 3 agency eligibility check with user held self exclusion, aimed at gambling and adult sites rather than banking. I started it pointed at banks and backed out of that. KYC rules are prescriptive about collection and not just about outcome, so the bank still has to obtain and keep name, date of birth, address and an ID number for years, and travel rule and suspicious activity reports both need a named subject. A yes or no proof does not remove a single one of those obligations, it just sits on top of the file they have to keep anyway. Age gating goes the other way. The law tells the operator to verify age, and some of the newer ones make holding a copy of the ID a liability in itself, so the operator has a real reason to prefer not knowing. That felt like the only place this gets bought instead of just admired.

The README has a limits section with ten things I already know are wrong or unproven, and this root disclosure goes in as number eleven.

And thanks for the last paragraph. That is the seat I am aiming at.

1 Like
4

@uetto.sec that’s exactly the deeper version of the footgun. checkRoot is a ledger read, so the path-root you pass in has to be disclosed; with one tree per agency, “matches a historic root vs matches nothing” is enough to reconstruct the attestation pattern even if the final 2-of-3 Boolean never leaves the circuit. Same leak, extra steps well caught.

The single-tree redesign is the right direction: leaf = hash(identity commitment, period, issuer tag), prove two memberships against the same HistoricMerkleTree, assert different issuer tags + same identity inside the circuit. Then both disclosed roots are just valid roots of one shared tree and don’t encode which agencies signed. Worth the rewrite.

Also the product pivot (age/gambling over bank KYC) is sharp. “The law requires an outcome the operator would rather not hold the documents for” is a much better buyer than bolting a ZK yes/no onto a file they still have to keep for Travel Rule / SAR.

i looked at the repo README limits section is doing real work (especially naming the agency-pattern leak as #3 before this thread). Looking forward to #11 landing as the single-tree rewrite. Nice PoC.

1 Like
5

Following up because I did not want to leave this at “I believe the fix is”. I built a small harness and ran it instead.

Two things came out, and one of them means I described the leak too generously in my own post above.

The result of each check is published directly.

I said an observer compares my disclosed root against the tree’s known historic roots to work out which agencies matched. That is true, but it is far more work than anyone needs to do. checkRoot compiles to a member operation followed by popeq, and popeq writes the answer straight into the public transcript, tagged with the ledger field index it ran against.

Reading proofData.publicTranscript for two callers of the same circuit, Alice enrolled in tree A only and Bob in tree B only:

caller check vs treeA check vs treeB
Alice popeq [1] popeq []
Bob popeq [] popeq [1]

No comparison, no inference. The answer is just written down.

The compiler had been telling me the whole time.

Take disclose() off a checkRoot argument and the error names three separate channels:

ledger operation might disclose a hash of the witness value
ledger operation might disclose a hash of the boolean value of the witness value
ledger operation might disclose a hash of a modulus of a hash of the witness value

The middle one is the result of the check. A single disclose() consents to all three, and the message reads like it is only complaining about the root, so you wrap it and move on. That is exactly what I did, and I never read the second line properly.

The fix holds, and for a reason I did not expect.

Single tree, leaf as hash(domain, identity commitment, issuer tag), prove two memberships, assert the tags differ inside the circuit. A caller attested by (A, B) and one attested by (B, C) produce byte identical transcripts. Same pushed roots, same popeq values.

But it is not hiding the boolean. It cannot. It makes the boolean constant, because the circuit requires both checks to pass. So the rule is harsher than “use one tree”:

Every checkRoot call in a circuit has to return the same value for every honest caller. If a call can legitimately return false for some people, that false is public.

Which means the dummy path advice in my original post is not safe.

I recommended it above as the way to express a threshold, and I posted the TypeScript for it. It works in the sense that the proof still generates. It also guarantees a varying boolean, which is the leak. Optional membership and unlinkability are not both available this way. If anyone copied that snippet, that is the catch.

Harness, four commands, reproduces all of the above: GitHub - tomiin/checkroot-transcript-probe: Reproduction harness showing that HistoricMerkleTree.checkRoot publishes its result to the public transcript in Compact, and how to restructure so it does not. · GitHub

Also written up as a docs page with a PR open: docs(compact): document what checkRoot discloses to the public transcript by tomiin · Pull Request #1170 · midnightntwrk/midnight-docs · GitHub

@nasihudeenJ thank you for confirming the direction. The rewrite is queued, and I will post when #11 actually lands rather than when I have planned it.

8

The single-tree rewrite is in, and it’s the design you described. Leaf is hash(identityCommitment, period, agencyTag), two memberships against one shared HistoricMerkleTree, tags asserted distinct in-circuit. The “same identity” half is structural: both leaves derive from one idc computed inside the circuit. attest tags with the caller’s own derived id, so no agency can insert under another’s name.

Both checks are asserted rather than combined into a Boolean, so every proof that lands publishes true twice against roots of the same tree.

The rewrite also surfaced something worse in that circuit. merkleTreePathRoot hashes the path’s own leaf, and the witness runs on the prover’s machine. The old code derived a leaf from the caller’s key, passed it to the witness as a hint, then used only the returned path. A prover could return any attested person’s path and be admitted having never been attested. Soundness, not privacy. Both proofs now assert path.leaf == leaf.

Cost: proveEligibility goes 20,066 to 25,745 rows and stays at k=15, so it’s free to prove. The binding alone is 8 rows.

One thing worth flagging for anyone doing membership proofs: there was already a test called “fails for someone never attested” and it passed the whole time the contract was broken, because it used an honest witness. A test suite that only exercises honest witnesses can’t catch a witness-trust bug.