Cheap verifiability

[burdges]

There are "verifiable mixnets" that provide additional assurances of correct node behavior, but historically at enormous performance cost, but approaches improve and @FatemeShirazi knows that literature.

We'll use roughly the Sphinx packet format for numerous reasons, which normally looks nothing like a verifiable mixnet. We've some ideas though:

In Sphinx, all outgoing packets have a public key of the form either (1) Q=bP where b=HB(nP) = HB(pN) is a blinding factor with P=pG is an incoming packet's key, N=nG is the nodes key, or else (2) originate from the node giving them the form Q=qG with perhaps q=VRF(n,??) in the proof-of-mixing scheme or at least a limited number of such packets.

We could conceivably produce proofs that "enough" outgoing packets have public keys were reblindings of incoming packets, so part of (1), or perhaps even that all had public keys of form (1) or (2), assuming an [answer to this VRF question](original from the node). We could not exactly prove that no tampered occurs this way, but if tampering occurs then packets die at the next hop. I donno if this improves anything since Sphinx ensures that anyways, but sounds worth discussing further, albeit on the side.

As a rule, verifiable mixnets do their mixing in batches, but we envision using Poisson mixing like Loopix, meaning mix delays should be determined by the packet. We compute the delay by seeding a ChaChaRng with a hash of the key exchange, so HD(nP)=HD(pN), and then sampling the delay from this Rng according to an exponential distribution. An RSA accumulator could likely be used to cheaply prove that outgoing packets correspond to incoming packets, ala zerocoin.

We'd need to prove the delay was sampled correctly by working in the scalars for some elliptic curve and using Pederson commitments. In this vein, we only need approximate correctness, so general sampling methods likely apply, but maybe the quantile function method gives faster proofs, especially with arithmetic-geometric mean method for logarithms, or some method for exponentiation.

Again, I'm unsure anything here actually buys us anything beyond what Sphinx already buys us, but it's worth understanding the differences.

[FatemeShirazi]

I have a question. If we would use source-routing why do we need verifiable shuffling? As you mentioned, in source-routing if a message is deleted and replaced by another it would be dropped at the next hop anyway. I think verifiable shuffle would be used if we need communication/vote integrity (basically making sure a communication is not dropped, maybe it would be called availability)? Or if we have hop-by-hop routing, no? One more reason to use verifiable mixes it to keep the anonymity set constant, basically avoiding n-1 attacks. However, these attacks are not very realistic because they are very expensive and detectable.

[burdges]

We probably do not :) but I never looked into verifiable shuffles much myself, as they were slow in the past, so I likely do not know all the properties they provide. I'll look into the market mixnets paper you sent me later today.

[burdges]

Karaoke nodes publish bloom filters to provide a cheaper proof that servers do not drop cover traffic, thanks @oskarth for mentioning it in #12. I want relays to share commitments to their replay protection filter anyways, for the probabilistic payment scheme, so idea from Karaoke sounds interesting. As noted in #13, we should replace bloom filters with cuckoo filters to efficiently track message bodies too.

In Karaoke, there are rounds so servers may observe exact progression for all their cover messages, which sounds unrealistic. I'm sure doing these checks only sporadically provide far less protection than Karaoke, but presumably it still improves our protections. We expect enough messages that sharing entire replay protection filters sounds expensive, but the Fraud Proofs scheme might help prove that full cuckoo filter exists.

We could also consider applying ideas from their differential privacy and/or optimistic indistinguishability analysis of Karaoke, but it'd presumably become much harder, due to not operating in round and only checking sporadically.

[robertkiel]

closed, ask @burdges