Cryptocurrency Privacy Technologies: Sigma Protocol(s)

February 10, 2024 by patrickd

Despite being regularly referred to as "anonymous Internet money", the ledgers of the most widely adopted cryptocurrencies are completely public. Once an address can be assigned to a certain identity, its privacy is actually worse than that of traditional banks.

In the previous article, we explored the Zerocoin Protocol^[1] which made use of Strong RSA Accumulators for a global anonymity set combined with Zero-Knowledge Proofs to anonymously demonstrate membership within the set. Unfortunately, there was a cryptographic flaw within an undocumented part of the protocol, leading to many cryptocurrencies implementing it to be vulnerable to inflation attacks. This time we'll explore its successor on Zcoin (now Firo), the "Sigma Protocol" which did not suffer from its predecessor's flaw and also promised significantly reduced proof sizes and the elimination of a trusted setup.

The Concept

In cryptography, the term "Sigma Protocol" ($\Sigma$-Protocol) commonly refers to Proof-of-Knowledge techniques where a statement is proven by a Prover and Verifier communicating in three moves: Commitment, Challenge, and Response. Classifying these protocols is useful because they can be easily composed to prove conjunctions and disjunctions of multiple statements (ie. logical AND / OR conjectures). In regards to privacy, this is especially interesting since it allows the construction of k-out-of-n OR proofs (eg. for Ring Signatures), although for large anonymity sets such general techniques are still impractical since the proof's size grows linear with the number of members. More on this can be found in the Appendix.

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

Zcoin's (somewhat confusingly named) "Sigma Protocol" upgrade instead makes use of a specialized technique introduced by "One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin" (opens in a new tab)^[2] (OOOMP) which allows proving membership in large sets requiring only the transmission of a logarithmic number of commitments. Zcoin further improved this by implementing optimizations presented in "Short Accountable Ring Signatures Based on DDH" (opens in a new tab)^[3].

Scheme

At a high level, Sigma still follows Zerocoin's scheme: Private coins are minted by locking some denomination of public coins and publishing a Pedersen Commitment ${C}$ which can only be opened with knowledge of a serial number ${s}$ and a random blinding factor ${r}$:

These commitments are no longer aggregated by an RSA Accumulator for which inclusion is proven to redeem the private coin. Instead, we prove that we are able to open one out of all published commitments where the serial number is equal to zero. To have our ${C}$ commit to zero, we reveal the serial number ${s}$ to the validators which allows them to determine the inverse element ${s}{G}^{{-{1}}}$. However, to maintain anonymity we may not reveal which of the commitments belongs to us, so the validators will add it to all published commitments ${C}_{{i}}$:

For our own ${C}$, this will have the effect of homomorphically subtracting the serial number, turning it into a commitment to 0:

To a verifier all ${C}'_{{i}}$ look like random points on the curve. There's no way for them to identify which one no longer commits to a serial number.

Inclusion Proof

Zerocoin required 3 Zero-Knowledge Proofs to function:

1. Proof of the commitment's inclusion in the anonymity set without revealing the commitment
2. Proof of the ability to open a commitment without revealing the commitment or its Blinding Factor
3. Proof that both of the previous proofs are referring to the same undisclosed commitment

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

Sigma achieves this within a single proof roughly by relying on both Prover and Verifier having the same ordered list of published commitments. In a sense, the proof is efficient by communicating the position of the commitment-to-zero within the list in Zero-Knowledge.

Assume that within the list of ${N}$ commitments ${C}'_{{i}}$ (${C}'_{{0}},{C}'_{{1}},\ldots,{C}_{{{N}-{1}}}$) the commitment with the Serial Number of 0 is located at the index ${l}$ (${C}'_{{l}}={r}{H}$). Let's say that, based on a seed provided by the Prover and the commitment's place within the list, all commitments are summed up with deterministic random factors $\phi_{{i}}$ on the side of the Validator:

The Prover creates a second sum with factors $\psi_{{i}}$ that were chosen in such a manner that when subtracted from the first, everything will cancel out but for the commitment ${C}'_{{l}}$ that the Prover is able to open (has knowledge of ${r}$ for).

To prevent this from leaking ${C}'_{{l}}$ the Prover adds ${r}'{H}$ to the sum, distorting the Blinding Factor. Knowing both ${r}$ and ${r}'$ the Prover is still able to prove their ability to open the resulting commitment ${C}{''}_{{l}}={\left({r}+{r}'\right)}{H}$.

The idea is that the Validator will be none the wiser about which of the commitments ${C}'_{{i}}$ the Prover was able to open since he'll only receive the already calculated sum and no information on the chosen $\psi_{{i}}$ factors. While this was a gross oversimplification of the actual technique behind OOOMP, it should still have transported the concept at a high level.

The Math

As you might have guessed, we assume the Elliptic Curve Discrete Log Problem (ECDLP) to be hard for a group of prime order ${q}$ with generators ${G}$ and ${H}$ where the relationship ${H}={h}{G}$ is unknown. It could be argued that the selection of these parameters may leave an opportunity to introduce trapdoors, similar to how a trusted setup could have allowed the system to be backdoored. However by using well-established elliptic curve parameters and the use of hash functions for selecting generators, this risk should be insignificant.

Sigma Protocol for commitment to 0 or 1

The One-Out-Of-Many technique extends a $\Sigma$-Protocol where multiple commitments $\hat{{C}}_{{j}}$ are proven to commit to messages ${m}_{{j}}$ with a value of either 0 or 1.

${\mathbf{\text{ZKPoK}}}{\left\lbrace{\left({\color{red}{{m}_{{j}}}},{\color{red}{{r}_{{j}}}}\right)}:\hat{{C}}_{{j}}={\color{red}{{m}_{{j}}}}{G}+{\color{red}{{r}_{{j}}}}{H}\wedge{\color{red}{{m}_{{j}}}}\in{\left\lbrace{0},{1}\right\rbrace}\right\rbrace}$

Remember that all statements can be verified in parallel within 3 moves with the same challenge ${x}$, effectively resulting in a logical AND conjecture. Like all $\Sigma$-Protocols, this one too may be transformed to be non-interactive using the Fiat-Shamir heuristic.^[7]

Kronecker Delta

In what follows, a function called the "Kronecker delta" will be useful for conciseness. The function takes two parameters ($\alpha,\beta$) and returns either ${1}$ (when $\alpha=\beta$) or ${0}$ (when $\alpha\ne\beta$). The parameters are usually written as indices of the greek letter $\delta$ (delta):

One Out Of Many Proof Intuition

Assuming there are ${N}$ commitments ${C}'_{{i}}={C}_{{i}}+{s}{G}^{{-{1}}}$, where ${l}$ is the index at which our coin-commitment ${C}'_{{l}}={C}_{{l}}+{s}{G}^{{-{1}}}={0}{G}+{r}{H}$ is located, the anonymity set known by both the Prover and Verifiers is:

We want to construct a proof where, when each commitment is multiplied with a Kronecker delta $\delta_{{{i}{l}}}$, the sum results in a commitment to zero which we are able to open (thanks to our knowledge of ${r}$):

As described, the Kronecker delta $\delta_{{{i}{l}}}$ will be 1 only when the current index ${i}$ is equal to the index ${l}$ of the commitment ${C}'_{{l}}$ for which we want to prove that we are able to open it.

We'll then further break the indices down into their binary representations ${i}={i}_{{1}},\ldots,{i}_{{n}}$ and ${l}={l}_{{1}},\ldots,{l}_{{n}}$ where ${i}_{{j}},{l}_{{j}}\in{\left\lbrace{0},{1}\right\rbrace}$. Using this, we can substitute $\delta_{{{i}{l}}}$ with the product ${\prod_{{{j}={1}}}^{{n}}}\delta_{{{i}_{{j}}{l}_{{j}}}}$:

If we engage in ${n}$ parallel $\Sigma$-protocols (described above) to demonstrate that all values ${l}_{{j}}\in{\left\lbrace{0},{1}\right\rbrace}$ by making commitments $\hat{{C}}_{{j}}={l}_{{j}}{G}+{r}_{{j}}{H}$ (with ${m}_{{j}}={l}_{{j}}$ and randomly chosen ${r}_{{j}}$), the Prover would reveal values of ${f}_{{j}}$ in the form

as part of the final move. Based on that we define

which gives us for each ${i}$ that the product ${\prod_{{{j}={1}}}^{{n}}}{f}_{{{j},{i}_{{j}}}}$ is a polynomial of the form

where the polynomial's low order coefficients (corresponding to ${x}^{{0}},\ldots,{x}^{{{n}-{1}}}$) are ${p}_{{{i},{k}}}$ and can be determined before receiving the challenge value ${x}$.