MAYA is a shuffle argument with O(log n) proof size and transparent setup, built for verifiable elections. It allows a mix-server to prove — succinctly and without any trusted setup — that a shuffled list of ciphertexts is a correct re-encryption and permutation of the original list, without revealing the permutation itself.
Performance
| n | Mode | Prover (s) | Verifier (s) | Proof size |
|---|---|---|---|---|
| 1,000 | ST | 0.24 | 0.05 | 3.78 KB |
| MT | 0.10 | 0.03 | ||
| 10,000 | ST | 1.95 | 0.45 | 4.91 KB |
| MT | 0.72 | 0.17 | ||
| 100,000 | ST | 19.52 | 4.60 | 6.03 KB |
| MT | 6.90 | 1.57 | ||
| 1,000,000 | ST | 193.72 | 45.43 | 6.59 KB |
| MT | 71.91 | 13.81 |
Table 1. MAYA (Ristretto curve) for a shuffle of n ciphertexts. Timings are measured end-to-end, including disk I/O, in seconds, for single-threaded (ST) and multi-threaded (MT) execution. Proof size is independent of the threading model.
All benchmarks were conducted on a laptop equipped with an Intel Core i5-1245U
processor (2 Performance-cores and 8 Efficient-cores for a total of 12 threads,
with a max turbo frequency of 4.4 GHz), 16 GB of RAM, and running Ubuntu 22.04
LTS, with rustc 1.88.0. MAYA uses the Ristretto255 curve
(curve25519-dalek) with folding factor k=4.
These figures improve on the ones reported in the paper. They were measured with the implementation in maya_extensions, run as a single block, which is the plain shuffle. The protocol is unchanged. See the Changelog for how the two versions differ, and the Paper for the full evaluation.
Learn more
- Paper — the full research paper describing MAYA
- Specification — the verifier specification
- MAYAsk — extensions for blocks, multiple keys, and decryption mixnets
- Getting Started — run MAYA yourself
- Code — source code and repositories