Cryptocurrency Privacy Technologies: Sigma Protocol(s)

February 10, 2023 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 Zerocoin Scheme in review

  1. A user chooses a random Serial Number and Blinding Factor and creates a commitment that cannot be opened without knowledge of both values.
  2. The user publishes a transaction that locks some amount of value (eg. 1 BTC) and contains the commitment. The chain will keep track of such commitments, effectively "minting" a Zerocoin.
  3. Other users too publish their own commitments and lock the same denomination of value.
  4. Sometime later, the user publishes the Serial Number and proves in Zero-Knowledge that they know of a Blinding Factor that will open one of the commitments - without revealing which. They "redeem" their Zerocoin in exchange for one of the locked values.

The protocol also keeps track of already used Serial Numbers to prevent double-spending since it's not known which of the commitments have already been spent. The Blinding Factor must never leak, since with it anyone could reconstruct the commitment published during the mint-transaction. The scheme is anonymous thanks to the fact that minting and redemption transactions cannot be connected to each other, effectively "mixing" with all other protocol participants.

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{C} which can only be opened with knowledge of a serial number s{s} and a random blinding factor r{r}:

C=sG+rH{C}={s}{G}+{r}{H}

As you can tell by the notation, Sigma makes use of Elliptic Curve Cryptography. This required existing commitments to be re-minted by users after the chain upgrade went live.

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{C} commit to zero, we reveal the serial number s{s} to the validators which allows them to determine the inverse element sG1{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 Ci{C}_{{i}}:

Ci=Ci+sG1{C}'_{{i}}={C}_{{i}}+{s}{G}^{{-{1}}}

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

C=C+sG1=sG+rH+sG1{C}'={C}+{s}{G}^{{-{1}}}=\cancel{{{s}{G}}}+{r}{H}+\cancel{{{s}{G}^{{-{1}}}}}

To a verifier all Ci{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{N} commitments Ci{C}'_{{i}} (C0,C1,,CN1{C}'_{{0}},{C}'_{{1}},\ldots,{C}_{{{N}-{1}}}) the commitment with the Serial Number of 0 is located at the index l{l} (Cl=rH{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 ϕi\phi_{{i}} on the side of the Validator:

i=0N1ϕiCi=ϕ0C0+ϕ1C1++ϕN1CN1{\sum_{{{i}={0}}}^{{{N}-{1}}}}\phi_{{i}}\cdot{C}'_{{i}}=\phi_{{0}}{C}'_{{0}}+\phi_{{1}}{C}'_{{1}}+\ldots+\phi_{{{N}-{1}}}{C}'_{{{N}-{1}}}

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

i=0N1ϕiCii=0N1ψiCi=Cl{\sum_{{{i}={0}}}^{{{N}-{1}}}}\phi_{{i}}\cdot{C}'_{{i}}-{\sum_{{{i}={0}}}^{{{N}-{1}}}}\psi_{{i}}\cdot{C}'_{{i}}={C}'_{{l}} (ϕ0C0+ϕ1C1++ϕlCl++ϕN1CN1)(ψ0C0+ψ1C1++ψlCl++ψN1CN1)=Cl{\left(\phi_{{0}}{C}'_{{0}}+\phi_{{1}}{C}'_{{1}}+\ldots+\phi_{{l}}{C}'_{{l}}+\ldots+\phi_{{{N}-{1}}}{C}'_{{{N}-{1}}}\right)}-{\left(\psi_{{0}}{C}'_{{0}}+\psi_{{1}}{C}'_{{1}}+\ldots+\psi_{{l}}{C}'_{{l}}+\ldots+\psi_{{{N}-{1}}}{C}'_{{{N}-{1}}}\right)}={C}'_{{l}} 0C0+0C1++1Cl++0CN1=Cl{0}{C}'_{{0}}+{0}{C}'_{{1}}+\ldots+{1}{C}'_{{l}}+\ldots+{0}{C}'_{{{N}-{1}}}={C}'_{{l}}

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

i=0N1ϕiCiGenerated by Validator(i=0N1ψiCi+rH)Generated by Prover=Cl\overbrace{{{\sum_{{{i}={0}}}^{{{N}-{1}}}}\phi_{{i}}\cdot{C}'_{{i}}}}^{{\text{Generated by Validator}}}-\underbrace{{{\left({\sum_{{{i}={0}}}^{{{N}-{1}}}}\psi_{{i}}\cdot{C}'_{{i}}+{r}'{H}\right)}}}_{{\text{Generated by Prover}}}={C}{''}_{{l}}

The idea is that the Validator will be none the wiser about which of the commitments Ci{C}'_{{i}} the Prover was able to open since he'll only receive the already calculated sum and no information on the chosen ψi\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{q} with generators G{G} and H{H} where the relationship H=hG{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 C^j\hat{{C}}_{{j}} are proven to commit to messages mj{m}_{{j}} with a value of either 0 or 1.

ZKPoK{(mj,rj):C^j=mjG+rjHmj{0,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}

ProverVerifier
Knows (G,H,C^j,mj,rj){\left({G},{H},\hat{{C}}_{{j}},{\color{red}{{m}_{{j}}}},{\color{red}{{r}_{{j}}}}\right)}Knows (G,H,C^j){\left({G},{H},\hat{{C}}_{{j}}\right)}
Chooses random scalars aj,sj,tj{\color{red}{{a}_{{j}},{s}_{{j}},{t}_{{j}}}}
Aj=ajG+sjH{A}_{{j}}={\color{red}{{a}_{{j}}}}{G}+{\color{red}{{s}_{{j}}}}{H}
Bj=(ajmj)G+tjH{B}_{{j}}={\color{red}{{\left({a}_{{j}}\cdot{m}_{{j}}\right)}}}{G}+{\color{red}{{t}_{{j}}}}{H}
Sends (Aj,Bj){\left({A}_{{j}},{B}_{{j}}\right)}\RightarrowKnows (G,H,C^j,Aj,Bj){\left({G},{H},\hat{{C}}_{{j}},{A}_{{j}},{B}_{{j}}\right)}
Chooses a random challenge scalar x{x}
Knows (G,H,C^j,mj,rj,aj,sj,tj,Aj,Bj,x){\left({G},{H},\hat{{C}}_{{j}},{\color{red}{{m}_{{j}},{r}_{{j}},{a}_{{j}},{s}_{{j}},{t}_{{j}}}},{A}_{{j}},{B}_{{j}},{x}\right)}\Leftarrow Sends x{x}
fj=mjx+aj{f}_{{j}}={\color{red}{{m}_{{j}}}}\cdot{x}+{\color{red}{{a}_{{j}}}}
αj=rjx+sj\alpha_{{j}}={\color{red}{{r}_{{j}}}}\cdot{x}+{\color{red}{{s}_{{j}}}}
βj=rj(xfj)+tj\beta_{{j}}={\color{red}{{r}_{{j}}}}\cdot{\left({x}-{f}_{{j}}\right)}+{\color{red}{{t}_{{j}}}}
Sends (fj,αj,βj){\left({f}_{{j}},\alpha_{{j}},\beta_{{j}}\right)}\RightarrowKnows (G,H,C^j,Aj,Bj,x,fj,αj,βj){\left({G},{H},\hat{{C}}_{{j}},{A}_{{j}},{B}_{{j}},{x},{f}_{{j}},\alpha_{{j}},\beta_{{j}}\right)}
xC^j+Aj   =?   fjG+αjH{x}\cdot\hat{{C}}_{{j}}+{A}_{{j}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {f}_{{j}}{G}+\alpha_{{j}}{H}
(xfj)C^j+Bj   =?   0G+βjH{\left({x}-{f}_{{j}}\right)}\hat{{C}}_{{j}}+{B}_{{j}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {0}{G}+\beta_{{j}}{H}
⚠️

Verifiers should enforce commitments Cj{C}_{{j}}, Aj{A}_{{j}}, and Bj{B}_{{j}} to be valid points on the curve. Scalar values fj{f}_{{j}}, αj\alpha_{{j}}, and βj\beta_{{j}} should be Zq\in\mathbb{Z}_{{q}}. The challenge x{x} should be a binary value {0,1}λ{\left\lbrace{0},{1}\right\rbrace}^{\lambda} where the length λ\lambda is a security parameter.

xC^+A   =?   fG+αH{x}\hat{{C}}+{A}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {f}{G}+\alpha{H}

Substitute C^=mG+rH  ,  A=aG+sH  ,  f=mx+a  ,  α=rx+s\hat{{C}}={\color{red}{{m}}}{G}+{\color{red}{{r}}}{H}\ \text{ , }\ {A}={\color{red}{{a}}}{G}+{\color{red}{{s}}}{H}\ \text{ , }\ {f}={\color{red}{{m}}}{x}+{\color{red}{{a}}}\ \text{ , }\ \alpha={\color{red}{{r}}}{x}+{\color{red}{{s}}}

x(mG+rH)+(aG+sH)   =?   (mx+a)G+(rx+s)H{x}\cdot{\left({\color{red}{{m}}}{G}+{\color{red}{{r}}}{H}\right)}+{\left({\color{red}{{a}}}{G}+{\color{red}{{s}}}{H}\right)}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}{G}+{\left({\color{red}{{r}}}{x}+{\color{red}{{s}}}\right)}{H}

(mx)G+(rx)H+aG+sH   =?   (mx+a)G+(rx+s)H{\left({\color{red}{{m}}}{x}\right)}{G}+{\left({\color{red}{{r}}}{x}\right)}{H}+{\color{red}{{a}}}{G}+{\color{red}{{s}}}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}{G}+{\left({\color{red}{{r}}}{x}+{\color{red}{{s}}}\right)}{H}

(mx+a)G+(rx+s)H   =   (mx+a)G+(rx+s)H{\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}{G}+{\left({\color{red}{{r}}}{x}+{\color{red}{{s}}}\right)}{H}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}{G}+{\left({\color{red}{{r}}}{x}+{\color{red}{{s}}}\right)}{H}

(xf)C^+B   =?   0G+βH{\left({x}-{f}\right)}\hat{{C}}+{B}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {0}{G}+\beta{H}

Substitute f=mx+a  ,  C^=mG+rH  ,  B=amG+tH  ,  β=r(xf)+t  ,  0G=0{f}={\color{red}{{m}}}{x}+{\color{red}{{a}}}\ \text{ , }\ \hat{{C}}={\color{red}{{m}}}{G}+{\color{red}{{r}}}{H}\ \text{ , }\ {B}={\color{red}{{a}{m}}}{G}+{\color{red}{{t}}}{H}\ \text{ , }\ \beta={\color{red}{{r}}}{\left({x}-{f}\right)}+{\color{red}{{t}}}\ \text{ , }\ {0}{G}={0}

(x(mx+a))(mG+rH)+(amG+tH)   =?   0+(r(xf)+t)H{\left({x}-{\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}\right)}{\left({\color{red}{{m}}}{G}+{\color{red}{{r}}}{H}\right)}+{\left({\color{red}{{a}{m}}}{G}+{\color{red}{{t}}}{H}\right)}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {0}+{\left({\color{red}{{r}}}{\left({x}-{f}\right)}+{\color{red}{{t}}}\right)}{H}

(xmxa)(mG+rH)+(amG+tH)   =?   (rxr(mx+a)+t)H{\left({x}-{\color{red}{{m}}}{x}-{\color{red}{{a}}}\right)}{\left({\color{red}{{m}}}{G}+{\color{red}{{r}}}{H}\right)}+{\left({\color{red}{{a}{m}}}{G}+{\color{red}{{t}}}{H}\right)}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\left({\color{red}{{m}}}{x}+{\color{red}{{a}}}\right)}+{\color{red}{{t}}}\right)}{H}

(mxm2xma)G+(rxrmxra)H+amG+tH   =?   (rxrmxra+t)H{\left({\color{red}{{m}}}{x}-{\color{red}{{m}^{{2}}}}{x}-{\color{red}{{m}{a}}}\right)}{G}+{\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}\right)}{H}+{\color{red}{{a}{m}}}{G}+{\color{red}{{t}}}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

(mxm2xma)G+(rxrmxra+t)H+amG   =?   (rxrmxra+t)H{\left({\color{red}{{m}}}{x}-{\color{red}{{m}^{{2}}}}{x}\cancel{{-{\color{red}{{m}{a}}}}}\right)}{G}+{\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}+\cancel{{{\color{red}{{a}{m}}}{G}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

(mxm2x)G+(rxrmxra+t)H   =?   (rxrmxra+t)H{\left({\color{red}{{m}}}{x}-{\color{red}{{m}^{{2}}}}{x}\right)}{G}+{\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{m}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

if  m=1\text{if }\ {m}={1}\text{}

(1x12x)G+(rxr1xra+t)H   =?   (rxr1xra+t)H{\left({\color{red}{{1}}}{x}-{\color{red}{{1}^{{2}}}}{x}\right)}{G}+{\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{1}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\cancel{{{\color{red}{{r}}}{x}}}\cancel{{-{\color{red}{{r}}}{\color{red}{{1}}}{x}}}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

(1x12x)G+(ra+t)H   =   (ra+t)H\cancel{{{\left({\color{red}{{1}}}{x}-{\color{red}{{1}^{{2}}}}{x}\right)}{G}}}+{\left(-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {\left(-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

if  m=0\text{if }\ {m}={0}\text{}

(0x02x)G+(rxr0xra+t)H   =?   (rxr0xra+t)H{\left({\color{red}{{0}}}{x}-{\color{red}{{0}^{{2}}}}{x}\right)}{G}+{\left({\color{red}{{r}}}{x}-\cancel{{{\color{red}{{r}}}{\color{red}{{0}}}{x}}}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{0}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

(0x02x)G+(rxra+t)H   =   (rxra+t)H\cancel{{{\left({\color{red}{{0}}}{x}-{\color{red}{{0}^{{2}}}}{x}\right)}{G}}}+{\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {\left({\color{red}{{r}}}{x}-{\color{red}{{r}}}{\color{red}{{a}}}+{\color{red}{{t}}}\right)}{H}

Invalid for any  m>1\text{Invalid for any }\ {m}>{1}

Remember that all statements can be verified in parallel within 3 moves with the same challenge x{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{1} (when α=β\alpha=\beta) or 0{0} (when αβ\alpha\ne\beta). The parameters are usually written as indices of the greek letter δ\delta (delta):

δαβ={0if αβ,1if α=β.\delta_{\alpha\beta} = \begin{cases} 0 &\text{if } \alpha \neq \beta, \\ 1 &\text{if } \alpha=\beta. \end{cases}

One Out Of Many Proof Intuition

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

C0,C1,,Cl,,CN1{C}'_{{0}},{C}'_{{1}},\ldots,{C}'_{{l}},\ldots,{C}'_{{{N}-{1}}}

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

i=0N1δilCi=Cl{\sum_{{{i}={0}}}^{{{N}-{1}}}}\delta_{{{i}{l}}}{C}'_{{i}}={C}'_{{l}} δ0,lC0+δ1,lC1++δl,lCl++δN1,lCN1=0G+rH\delta_{{{0},{l}}}{C}'_{{0}}+\delta_{{{1},{l}}}{C}'_{{1}}+\ldots+\delta_{{{l},{l}}}{C}'_{{l}}+\ldots+\delta_{{{N}-{1},{l}}}{C}'_{{{N}-{1}}}={0}{G}+{r}{H} 0C0+0C1++1Cl++0CN1=rH{0}\cdot{C}'_{{0}}+{0}\cdot{C}'_{{1}}+\ldots+{1}\cdot{C}'_{{l}}+\ldots+{0}\cdot{C}'_{{{N}-{1}}}={r}{H}

As described, the Kronecker delta δil\delta_{{{i}{l}}} will be 1 only when the current index i{i} is equal to the index l{l} of the commitment Cl{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=i1,,in{i}={i}_{{1}},\ldots,{i}_{{n}} and l=l1,,ln{l}={l}_{{1}},\ldots,{l}_{{n}} where ij,lj{0,1}{i}_{{j}},{l}_{{j}}\in{\left\lbrace{0},{1}\right\rbrace}. Using this, we can substitute δil\delta_{{{i}{l}}} with the product j=1nδijlj{\prod_{{{j}={1}}}^{{n}}}\delta_{{{i}_{{j}}{l}_{{j}}}}:

i=0N1(j=1nδijlj)Ci=1Cl{\sum_{{{i}={0}}}^{{{N}-{1}}}}{\left({\prod_{{{j}={1}}}^{{n}}}\delta_{{{i}_{{j}}{l}_{{j}}}}\right)}{C}'_{{i}}={1}{C}'_{{l}} i=0N1(δi1l1δi2l2δinln)Ci=(111)Cl{\sum_{{{i}={0}}}^{{{N}-{1}}}}{\left(\delta_{{{i}_{{1}}{l}_{{1}}}}\cdot\delta_{{{i}_{{2}}{l}_{{2}}}}\cdot\ldots\cdot\delta_{{{i}_{{{n}}}{l}_{{{n}}}}}\right)}{C}'_{{i}}={\left({1}\cdot{1}\cdot\ldots\cdot{1}\right)}{C}'_{{l}}
⚠️

This technique assumes N=2n{N}={2}^{{n}}, which will rarely be exactly the case in practice. It's recommended to simply pad the commitments by reusing the last Ci{C}'_{{i}} until a valid length has been reached.

Zcoin's OOOMP implementation erroneously omitted doing this until version v0.13.8.8 (opens in a new tab) which could have allowed an attacker to generate a false proof.

Example

Assume n=3{n}={3}, therefore N=23=8{N}={2}^{{3}}={8} with C0,C1,C3,C4,C5,C6,C7{C}'_{{0}},{C}'_{{1}},{C}'_{{3}},{C}'_{{4}},{C}'_{{5}},{C}'_{{6}},{C}'_{{7}} and the commitment Cl{C}_{{l}} for which we want to prove set membership of at l=5{l}={5} (ie. Cl=C5{C}_{{l}}={C}_{{5}}).

i{i} / j{j}1 (20{2}^{{0}})2 (21{2}^{{1}})3 (22{2}^{{2}})
0000
1100
2010
3110
4001
l{l} = 5101
6011
7111

According to the above (big-endian) binary table the values of lj{l}_{{j}} would be l1=1{l}_{{1}}={1}, l2=0{l}_{{2}}={0}, and l3=1{l}_{{3}}={1}:

l=j=1nlj2j1=l120+l221+l322=11+02+14=5{l}={\sum_{{{j}={1}}}^{{{n}}}}{l}_{{j}}{2}^{{{j}-{1}}}={l}_{{{1}}}{2}^{{0}}+{l}_{{{2}}}{2}^{{1}}+{l}_{{{3}}}{2}^{{2}}={1}\cdot{1}+{0}\cdot{2}+{1}\cdot{4}={5}

We'll now unroll the introduced equation using the example's assumptions:

i=07(j=13δijlj)Ci=C5{\sum_{{{i}={0}}}^{{{7}}}}{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{i}_{{j}}{l}_{{j}}}}\right)}{C}'_{{i}}={\color{blue}{{C}'_{{5}}}}(j=13δ0jlj)C0+(j=13δ1jlj)C1+(j=13δ2jlj)C2+(j=13δ3jlj)C3+(j=13δ4jlj)C4+(j=13δlj)C5+(j=13δ6jlj)C6+(j=13δ7jlj)C7=C5{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{0}_{{j}}{l}_{{j}}}}\right)}{C}'_{{0}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{1}_{{j}}{l}_{{j}}}}\right)}{C}'_{{1}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{2}_{{j}}{l}_{{j}}}}\right)}{C}'_{{2}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{3}_{{j}}{l}_{{j}}}}\right)}{C}'_{{3}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{4}_{{j}}{l}_{{j}}}}\right)}{C}'_{{4}}+{\color{blue}{{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{l}_{{j}}}}\right)}{C}'_{{5}}}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{6}_{{j}}{l}_{{j}}}}\right)}{C}'_{{6}}+{\left({\prod_{{{j}={1}}}^{{3}}}\delta_{{{7}_{{j}}{l}_{{j}}}}\right)}{C}'_{{7}}={\color{blue}{{C}'_{{5}}}}(δ0151δ0252δ0353)C0+(δ1151δ1252δ1353)C1+(δ2151δ2252δ2353)C2+(δ3151δ3252δ3353)C3+(δ4151δ4252δ4353)C4+(δ5151δ5252δ5353)C5+(δ6151δ6252δ6353)C6+(δ7151δ7252δ7353)C7=C5{\left(\delta_{{{0}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{0}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{0}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{0}}+{\left(\delta_{{{1}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{1}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{1}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{1}}+{\left(\delta_{{{2}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{2}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{2}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{2}}+{\left(\delta_{{{3}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{3}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{3}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{3}}+{\left(\delta_{{{4}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{4}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{4}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{4}}+{\color{blue}{{\left(\delta_{{{5}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{5}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{5}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{5}}}}+{\left(\delta_{{{6}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{6}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{6}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{6}}+{\left(\delta_{{{7}_{{{1}}}{5}_{{{1}}}}}\cdot\delta_{{{7}_{{{2}}}{5}_{{{2}}}}}\cdot\delta_{{{7}_{{{3}}}{5}_{{{3}}}}}\right)}{C}'_{{7}}={\color{blue}{{C}'_{{5}}}}(δ0,1δ0,0δ0,1)C0+(δ1,1δ0,0δ0,1)C1+(δ0,1δ1,0δ0,1)C2+(δ1,1δ1,0δ0,1)C3+(δ0,1δ0,0δ1,1)C4+(δ1,1δ0,0δ1,1)C5+(δ0,1δ1,0δ1,1)C6+(δ1,1δ1,0δ1,1)C7=C5{\left(\delta_{{{0},{1}}}\cdot\delta_{{{0},{0}}}\cdot\delta_{{{0},{1}}}\right)}{C}'_{{0}}+{\left(\delta_{{{1},{1}}}\cdot\delta_{{{0},{0}}}\cdot\delta_{{{0},{1}}}\right)}{C}'_{{1}}+{\left(\delta_{{{0},{1}}}\cdot\delta_{{{1},{0}}}\cdot\delta_{{{0},{1}}}\right)}{C}'_{{2}}+{\left(\delta_{{{1},{1}}}\cdot\delta_{{{1},{0}}}\cdot\delta_{{{0},{1}}}\right)}{C}'_{{3}}+{\left(\delta_{{{0},{1}}}\cdot\delta_{{{0},{0}}}\cdot\delta_{{{1},{1}}}\right)}{C}'_{{4}}+{\color{blue}{{\left(\delta_{{{1},{1}}}\cdot\delta_{{{0},{0}}}\cdot\delta_{{{1},{1}}}\right)}{C}'_{{5}}}}+{\left(\delta_{{{0},{1}}}\cdot\delta_{{{1},{0}}}\cdot\delta_{{{1},{1}}}\right)}{C}'_{{6}}+{\left(\delta_{{{1},{1}}}\cdot\delta_{{{1},{0}}}\cdot\delta_{{{1},{1}}}\right)}{C}'_{{7}}={\color{blue}{{C}'_{{5}}}}(010)C0+(110)C1+(000)C2+(100)C3+(011)C4+(111)C5+(001)C6+(101)C7=C5{\left({0}\cdot{1}\cdot{0}\right)}{C}'_{{0}}+{\left({1}\cdot{1}\cdot{0}\right)}{C}'_{{1}}+{\left({0}\cdot{0}\cdot{0}\right)}{C}'_{{2}}+{\left({1}\cdot{0}\cdot{0}\right)}{C}'_{{3}}+{\left({0}\cdot{1}\cdot{1}\right)}{C}'_{{4}}+{\color{blue}{{\left({1}\cdot{1}\cdot{1}\right)}{C}'_{{5}}}}+{\left({0}\cdot{0}\cdot{1}\right)}{C}'_{{6}}+{\left({1}\cdot{0}\cdot{1}\right)}{C}'_{{7}}={\color{blue}{{C}'_{{5}}}}0C0+0C1+0C2+0C3+0C4+1C5+0C6+0C7=C5{0}\cdot{C}'_{{0}}+{0}\cdot{C}'_{{1}}+{0}\cdot{C}'_{{2}}+{0}\cdot{C}'_{{3}}+{0}\cdot{C}'_{{4}}+{\color{blue}{{1}\cdot{C}'_{{5}}}}+{0}\cdot{C}'_{{6}}+{0}\cdot{C}'_{{7}}={\color{blue}{{C}'_{{5}}}}C5=C5{\color{blue}{{C}'_{{5}}}}={\color{blue}{{C}'_{{5}}}}

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

fj=ljx+aj{f}_{{j}}={l}_{{j}}{x}+{a}_{{j}}

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

fj,1=fj=ljx+aj=δ1ljx+aj{f}_{{{j},{1}}}={f}_{{j}}={l}_{{j}}{x}+{a}_{{j}}=\delta_{{{1}{l}_{{j}}}}{x}+{a}_{{j}} fj,0=xfj=(1lj)xaj=δ0ljxaj{f}_{{{j},{0}}}={x}-{f}_{{j}}={\left({1}-{l}_{{j}}\right)}{x}-{a}_{{j}}=\delta_{{{0}{l}_{{j}}}}{x}-{a}_{{j}}

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

pi(x)=j=1n(δijljx)+k=0n1pi,kxk=δilxn+k=0n1pi,kxk{p}_{{i}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{n}}}{\left(\delta_{{{i}_{{j}}{l}_{{j}}}}{x}\right)}+{\sum_{{{k}={0}}}^{{{n}-{1}}}}{p}_{{{i},{k}}}{x}^{{k}}=\delta_{{{i}{l}}}{x}^{{n}}+{\sum_{{{k}={0}}}^{{{n}-{1}}}}{p}_{{{i},{k}}}{x}^{{k}}

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

Example

Continuing based on the assumptions made in the previous example, we determine the polynomial pi(x){p}_{{i}}{\left({x}\right)} for each commitment Ci{C}'_{{i}}:

p0(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,0f2,0f3,0=(δ0l1xa1)(δ0l2xa2)(δ0l3xa3)=(δ0,0xa1)(δ0,1xa2)(δ0,1xa3)=(1xa1)(0xa2)(0xa3)=(xa1)(a2)(a3)=a2a3xa1a2a3{p}_{{0}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{0}}}\cdot{f}_{{{2},{0}}}\cdot{f}_{{{3},{0}}}={\left(\delta_{{{0}{l}_{{1}}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{0}{l}_{{2}}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{0}{l}_{{3}}}}{x}-{a}_{{3}}\right)}={\left(\delta_{{{0},{0}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{0},{1}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{0},{1}}}{x}-{a}_{{3}}\right)}={\left({1}{x}-{a}_{{1}}\right)}{\left({0}{x}-{a}_{{2}}\right)}{\left({0}{x}-{a}_{{3}}\right)}={\left({x}-{a}_{{1}}\right)}{\left(-{a}_{{2}}\right)}{\left(-{a}_{{3}}\right)}={a}_{{2}}{a}_{{3}}{x}-{a}_{{1}}{a}_{{2}}{a}_{{3}}p1(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,1f2,0f3,0=(δ1l1x+a1)(δ0l2xa2)(δ0l3xa3)=(δ1,1x+a1)(δ0,0xa2)(δ0,1xa3)=(1x+a1)(1xa2)(0xa3)=(x+a1)(xa2)(a3)=a3x2a1a3x+a2a3x+a1a2a3{p}_{{1}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{1}}}\cdot{f}_{{{2},{0}}}\cdot{f}_{{{3},{0}}}={\left(\delta_{{{1}{l}_{{1}}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{0}{l}_{{2}}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{0}{l}_{{3}}}}{x}-{a}_{{3}}\right)}={\left(\delta_{{{1},{1}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{0},{0}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{0},{1}}}{x}-{a}_{{3}}\right)}={\left({1}{x}+{a}_{{1}}\right)}{\left({1}{x}-{a}_{{2}}\right)}{\left({0}{x}-{a}_{{3}}\right)}={\left({x}+{a}_{{1}}\right)}{\left({x}-{a}_{{2}}\right)}{\left(-{a}_{{3}}\right)}=-{a}_{{3}}{x}^{{2}}-{a}_{{1}}{a}_{{3}}{x}+{a}_{{2}}{a}_{{3}}{x}+{a}_{{1}}{a}_{{2}}{a}_{{3}}p2(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,0f2,1f3,0=(δ0l1xa1)(δ1l2x+a2)(δ0l3xa3)=(δ0,1xa1)(δ1,0x+a2)(δ0,1xa3)=(0xa1)(0x+a2)(0xa3)=(a1)(a2)(a3)=a1a2a3{p}_{{2}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{0}}}\cdot{f}_{{{2},{1}}}\cdot{f}_{{{3},{0}}}={\left(\delta_{{{0}{l}_{{1}}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{1}{l}_{{2}}}}{x}+{a}_{{2}}\right)}{\left(\delta_{{{0}{l}_{{3}}}}{x}-{a}_{{3}}\right)}={\left(\delta_{{{0},{1}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{1},{0}}}{x}+{a}_{{2}}\right)}{\left(\delta_{{{0},{1}}}{x}-{a}_{{3}}\right)}={\left({0}{x}-{a}_{{1}}\right)}{\left({0}{x}+{a}_{{2}}\right)}{\left({0}{x}-{a}_{{3}}\right)}={\left(-{a}_{{1}}\right)}{\left({a}_{{2}}\right)}{\left(-{a}_{{3}}\right)}={a}_{{1}}{a}_{{2}}{a}_{{3}}p3(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,1f2,1f3,0=(δ1l1x+a1)(δ1l2x+a2)(δ0l3xa3)=(δ1,1x+a1)(δ1,0x+a2)(δ0,1xa3)=(1x+a1)(0x+a2)(0xa3)=(x+a1)(a2)(a3)=a2a3xa1a2a3{p}_{{3}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{1}}}\cdot{f}_{{{2},{1}}}\cdot{f}_{{{3},{0}}}={\left(\delta_{{{1}{l}_{{1}}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{1}{l}_{{2}}}}{x}+{a}_{{2}}\right)}{\left(\delta_{{{0}{l}_{{3}}}}{x}-{a}_{{3}}\right)}={\left(\delta_{{{1},{1}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{1},{0}}}{x}+{a}_{{2}}\right)}{\left(\delta_{{{0},{1}}}{x}-{a}_{{3}}\right)}={\left({1}{x}+{a}_{{1}}\right)}{\left({0}{x}+{a}_{{2}}\right)}{\left({0}{x}-{a}_{{3}}\right)}={\left({x}+{a}_{{1}}\right)}{\left({a}_{{2}}\right)}{\left(-{a}_{{3}}\right)}=-{a}_{{2}}{a}_{{3}}{x}-{a}_{{1}}{a}_{{2}}{a}_{{3}}p4(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,0f2,0f3,1=(δ0l1xa1)(δ0l2xa2)(δ1l3x+a3)=(δ0,1xa1)(δ0,0xa2)(δ1,1x+a3)=(0xa1)(1xa2)(1x+a3)=(a1)(xa2)(x+a3)=a1x2+a1a2xa1a3x+a1a2a3{p}_{{4}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{0}}}\cdot{f}_{{{2},{0}}}\cdot{f}_{{{3},{1}}}={\left(\delta_{{{0}{l}_{{1}}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{0}{l}_{{2}}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{1}{l}_{{3}}}}{x}+{a}_{{3}}\right)}={\left(\delta_{{{0},{1}}}{x}-{a}_{{1}}\right)}{\left(\delta_{{{0},{0}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{1},{1}}}{x}+{a}_{{3}}\right)}={\left({0}{x}-{a}_{{1}}\right)}{\left({1}{x}-{a}_{{2}}\right)}{\left({1}{x}+{a}_{{3}}\right)}={\left(-{a}_{{1}}\right)}{\left({x}-{a}_{{2}}\right)}{\left({x}+{a}_{{3}}\right)}=-{a}_{{1}}{x}^{{2}}+{a}_{{1}}{a}_{{2}}{x}-{a}_{{1}}{a}_{{3}}{x}+{a}_{{1}}{a}_{{2}}{a}_{{3}}p5(x)=j=13fj,ij=f1,i1f2,i2f3,i3=f1,1f2,0f3,1=(δ1l1x+a1)(δ0l2xa2)(δ1l3x+a3)=(δ1,1x+a1)(δ0,0xa2)(δ1,1x+a3)=(1x+a1)(1xa2)(1x+a3)=(x+a1)(xa2)(x+a3)=x3+a1x2a2x2+a3x2a1a2x+a1a3xa2a3xa1a2a3{\color{blue}{{p}_{{5}}{\left({x}\right)}={\prod_{{{j}={1}}}^{{3}}}{f}_{{{j},{i}_{{j}}}}={f}_{{{1},{i}_{{1}}}}\cdot{f}_{{{2},{i}_{{2}}}}\cdot{f}_{{{3},{i}_{{3}}}}={f}_{{{1},{1}}}\cdot{f}_{{{2},{0}}}\cdot{f}_{{{3},{1}}}={\left(\delta_{{{1}{l}_{{1}}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{0}{l}_{{2}}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{1}{l}_{{3}}}}{x}+{a}_{{3}}\right)}={\left(\delta_{{{1},{1}}}{x}+{a}_{{1}}\right)}{\left(\delta_{{{0},{0}}}{x}-{a}_{{2}}\right)}{\left(\delta_{{{1},{1}}}{x}+{a}_{{3}}\right)}={\left({1}{x}+{a}_{{1}}\right)}{\left({1}{x}-{a}_{{2}}\right)}{\left({1}{x}+{a}_{{3}}\right)}={\left({x}+{a}_{{1}}\right)}{\left({x}-{a}_{{2}}\right)}{\left({x}+{a}_{{3}}\right)}={x}^{{3}}+{a}_{{1}}{x}^{{2}}-{a}_{{2}}{x}^{{2}}+{a}_{{3}}{x}^{{2}}-{a}_{{1}}{a}_{{2}}{x}+{a}_{{1}}{a}_{{3}}{x}-{a}_{{2}}{a}_{{3}}{x}-{a}_{{1}}{a}_{{2}}{a}_{{3}}}}