Cryptocurrency Privacy Technologies: Zerocoin

January 9, 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.

This article explores the Zerocoin Protocol, the first anonymous cryptocurrency proposal supporting large anonymity sets. Initially suggested as an extension to Bitcoin, it was implemented in various alt-coins over the years. You most likely heard about it as Zcoin (XZC).

The Concept

In 2013 the Zerocoin (opens in a new tab) whitepaper suggested extending the Bitcoin Protocol by introducing a distributed e-cash scheme. Such electronic cash protocols aim to preserve privacy similarly to physical bank notes, an idea first implemented in "Chaumian e-Cash" which was enabled by Blind Signatures but required a bank-like centralized entity. Zerocoin instead, is a distributed e-cash system that intended to use Bitcoin's blockchain as a public "bulletin board", maintaining a list of valid coins for which a coin's membership is proven in zero-knowledge.[23]

This proposal would have effectively extended Bitcoin with a native laundry functionality. Practically, users would have been able to make use of new opcodes added to Bitcoin's scripting language in order to lock funds into the mix and redeem them at a later time without any clear connection between deposit and redemption.

Scheme

Bitcoin, traceable transaction graph example

As you may already know from the previous Confidential Transactions article, Bitcoins are not actually transacted "from one account to another". Rather than that, there exist Unspent Transaction Outputs (UTXOs) that each have a "Locking Script" (ScriptPubKey) associated with them. This script dictates the condition under which a UTXO can be spent. Typically, this condition is that the transaction's signer matches with the address specified in the Locking Script ("Pay-to-Public-Key-Hash"). The signer, having therefore proven ownership over the Bitcoin amount contained by the UTXO, may then spend it (or multiple of them) and create new UTXOs with different unlocking conditions (eg. such that only the new owner of the coins may spend them).

Bitcoin transaction made untraceable with Zerocoin

Zerocoin introduces a new such condition: A user may choose to specify a locking script in their UTXO which "mints" a Zerocoin by publishing a commitment to the coin's unique identifier. This commitment is added to an accumulator containing all legitimately minted Zerocoin commitments. The BTC value within the user's UTXO can be redeemed by anyone who too has minted a Zerocoin of the same denomination. Sometime later, the user may decide to reveal their coin's unique identifier to "spend" the Zerocoin in exchange for the locked value it represents. The crux is, that the user is able to prove that the identifier's commitment is within the accumulator without revealing the commitment itself using a zero-knowledge proof. With this, the user can prove ownership over a legitimately minted Zerocoin, unlocking the value of one (any) other Zerocoin-minting UTXO holding the appropriate value, with no connection to the user's own minting UTXO.

Example

To show how the protocol works, let's imagine Alice is owner over an UTXO holding a value of 2.4 BTC. She'd like to mint two Zerocoins each representing the denomination of 1 BTC. To do so, she locally generates two unique serial numbers Sa{S}_{{a}} and Sb{S}_{{b}} which she will keep secret until she decides to spend the coins. She signs a transaction containing 3 output UTXOs: One sending the change of 0.4 BTC back to herself and the other two each locking one BTC into the e-cash system. The Locking Scripts of these two Zerocoin-minting UTXOs contain commitments Ca{C}_{{a}} and Cb{C}_{{b}} which each commit to the yet-to-be-revealed serial numbers. Bitcoin's blockchain now acts as a public bulletin board containing a set of commitments C1,,CN{C}_{{1}},\ldots,{C}_{{N}} each representing a minted Zerocoin of 1 BTC value. Basically, the protocol is acting as an escrow pool and it's possible to mint different kinds of Zerocoins for various denominations by maintaining multiple sets.

After waiting for a while for other users to participate in the e-cash system, Alice may decide to redeem a Zerocoin in exchange for any other UTXO locking 1 BTC for the Zerocoin protocol (Cx{C}_{{x}}): Alice generates a proof πa\pi_{{a}} that shows she knows Sa{S}_{{a}} for a commitment within the set of all unspent commitments C1,,Ca,Cb,Cx,,CN{C}_{{1}},\ldots,{C}_{{a}},{C}_{{b}},{C}_{{x}},\ldots,{C}_{{N}}, without revealing which of the commitments the associated Ca{C}_{{a}} is. Alice signs a Transaction where she chooses any Zerocoin-minting UTXO as input, "proves her ownership" over it using (Sa,πa){\left({S}_{{a}},\pi_{{a}}\right)}, and sends the unlocked BTC to a fresh address that has no known association with her. The protocol will keep record of all revealed serial numbers S{S} in order to prevent double-spending. Alice was able to hide the origin of her funds within the anonymity set of all other Zerocoin holders.

I've omitted mentioning transaction fees for simplicity, but they'd not require any changes with the introduction of Zerocoin to Bitcoin. It might also be noteworthy that the anonymity set resets once all commitments in the accumulator have been spent, although this seems an unlikely scenario assuming that the system would find continuous use.

💡

"Burning Zerocoins for fun and profit (opens in a new tab)" reveals a fundamental flaw with using plaintext identifiers: An attacker observing transactions may notice a user's intention for spending a legitimate Zerocoin with serial number S{S}. The attacker may quickly mint and redeem a Zerocoin with that very same serial number S{S} and, if they succeeded to do this before the user's spend transaction was included, the user would now be rejected since the specified serial number has already been marked as "spent". The user's Zerocoin is then effectively unspendable and the user will not be able to redeem it for its value.

The paper suggests using a public key as serial number instead and adjusting the protocol to have the spender prove they know the appropriate private key by having them sign the transaction with it.

Accumulators

Proving that an element is part of a list without revealing the element, is a classical membership problem. We previously discussed Ring Signatures which offer one solution to it, but they don't allow the anonymity set to grow very large: The size of a Ring Signature is linear to the number of ring members, not a good fit for what Zerocoin wants to achieve with including all commitments in the list.

Instead, Zerocoin makes use of an "accumulator": An algorithm that allows one to combine a set of values into one short value. For a value within the accumulator, there exists a witness w{w} that proves the inclusion, while at the same time, it is infeasible to find a witness for a value that was not accumulated.

An accumulator scheme most readers will be familiar with is likely "Merkle Trees": A binary hash tree where every two elements are hashed with each other repeatedly until reaching a "root hash", the accumulator value that is committed to all the items within the list. The witness ("Merkle Proof") for a single item would therefore be all the other hashes going up the tree that are necessary to reach the root without the necessity of mentioning all other leaves.[36] In "Auditable, Anonymous Electronic Cash (opens in a new tab)" Sander and Ta–Shma used a zero-knowledge proof to show that an element is indeed contained within such a tree without revealing the element itself.

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

Zerocoin uses an "RSA Accumulator" scheme which, like Merkle Trees allows everyone to reproduce the accumulation of values without the need of knowing any secret trapdoor information. Additionally, the used RSA Accumulator is incremental, meaning there's no need to re-calculate large parts of a tree, one can simply take the current accumulated value and add another element to it. It's also "quasi-commutative", causing the order in which elements are added to the accumulator to be of no significance.

💡

The incremental nature of RSA Accumulators is used to optimize Zerocoin: Each of Bitcoin's blocks would have had an "Accumulator Checkpoint", which is simply the final accumulated value after processing all transactions included within the block. Most clients can continue off this checkpoint instead of having to calculate the entire accumulator themselves.

Creating an empty accumulator Λ\Lambda:

Λ=setup()\Lambda={\mathtt{\text{setup}}}{()}

Incrementally adding a commitment C{C} to the accumulator yields an updated accumulator value:

Λ=add(Λ,C)\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}

The order in which commitments are added is irrelevant:

add(add(Λ,C2),C1)=add(add(Λ,C1),C2){\mathtt{\text{add}}}{\left({\mathtt{\text{add}}}{\left(\Lambda,{C}_{{2}}\right)},{C}_{{1}}\right)}={\mathtt{\text{add}}}{\left({\mathtt{\text{add}}}{\left(\Lambda,{C}_{{1}}\right)},{C}_{{2}}\right)}

A witness to the accumulation of a commitment C{C} is an accumulator state that excludes said commitment:

Λ=add(Λ,C)\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}

w=generateWitness(Λ,C)=Λ\C{w}={\mathtt{\text{generateWitness}}}{\left(\Lambda',{C}\right)}=\Lambda'\backslash{C}

verifyWitness(Λ,C,w)={\mathtt{\text{verifyWitness}}}{\left(\Lambda',{C},{w}\right)}= true\texttt{true}

Toy Example

As a toy example, imagine the accumulator is a composite number while all its elements are prime numbers. As you may remember, all integers that aren't prime must be composite numbers which can be factored into a unique collection of prime numbers. (eg. 15{15} is not prime, therefore, it must be a composite number and can be represented by its prime factors: 35=15{3}\cdot{5}={15})

After initializing the accumulator with Λ=setup()=1\Lambda={s}{e}{t}{u}{p}{()}={1} we can now add a few primes to the set:

Λ=add(Λ,5)=15=5\Lambda={\mathtt{\text{add}}}{\left(\Lambda,{5}\right)}={1}\cdot{5}={5}

Λ=add(Λ,17)=517=85\Lambda={\mathtt{\text{add}}}{\left(\Lambda,{17}\right)}={5}\cdot{17}={85}

Λ=add(Λ,3)=853=255\Lambda={\mathtt{\text{add}}}{\left(\Lambda,{3}\right)}={85}\cdot{3}={255}

The accumulator Λ\Lambda is the composite of all the prime numbers added to the set: 5,17,3{5},{17},{3}.

A witness w{w} can simply be the state of the current accumulator divided through the number whose inclusion we want to prove:

Λ=add(Λ,11)=25511=2805\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{11}\right)}={255}\cdot{11}={2805}

w=generateWitness(Λ,11)=280511{w}={\mathtt{\text{generateWitness}}}{\left(\Lambda',{11}\right)}=\frac{{2805}}{{11}}

verifyWitness(Λ,11,w)=(w11=?Λ)={\mathtt{\text{verifyWitness}}}{\left(\Lambda',{11},{w}\right)}={\left({w}\cdot{11}{\stackrel{{?}}{{=}}}\Lambda'\right)}= true\texttt{true}

Interactive Zero-Knowledge proofs

The zero-knowledge proofs described in the paper can be instantiated using the technique of Schnorr[12]. Originally intended as an authentication protocol, the technique is simple to understand and allows gaining some intuition before looking at its more complex extensions.[11]

⚠️

Conventional DLP is a lot more fragile than ECDLP and requires choosing many of the above parameters very carefully.

Making Interactive Proofs Non-Interactive

The ECC Notation may be more intuitive for some readers, but since we're not dealing with points on curves in this article, further descriptions will make use of the Exponential Notation only.

The Math

Strong RSA Accumulator

Having covered RSA intuition in a previous article, we'll not go into much detail here. The important parts are that RSA relies on prime factorization being hard for two carefully chosen primes n=pq{n}={p}'\cdot{q}', and that going backward from having calculated eme   (mod  n){e}\equiv{m}^{{e}}\ \text{ }\ {\left(\text{mod }\ {n}\right)} is really hard without knowledge of trapdoor information.

With RSA's ability to provide unpredictable one-way permutations, like a conventional hashing function, we can accumulate commitments by modular exponentiation:

Λ=ΛC   (mod  n)\Lambda'=\Lambda^{{C}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}

We can even accumulate multiple commitments at once by multiplying them:

(((ΛC1)C2)...)Cn=ΛC1C2  ...  Cn   (mod  n){\left({\left({\left(\Lambda^{{{C}_{{1}}}}\right)}^{{{C}_{{2}}}}\right)}^{{\text{...}}}\right)}^{{{C}_{{n}}}}=\Lambda^{{{C}_{{1}}\cdot{C}_{{2}}\cdot\ \text{ ... }\ \cdot{C}_{{n}}}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}

For this accumulator to be considered "strong" it needs to be collision-free. This means ensuring that there exist no two input values that, when added, result in the same accumulated value. Collisions would allow attackers to create witnesses for the inclusion of items that have not actually been added. This issue is avoided by ensuring that all commitments are prime.[23]

Trusted Setup

To initialize the accumulator we need two random primes p{p}' and q{q}'. To strengthen against attacks we wouldn't choose these directly, instead we'll randomly generate prime numbers p{p}{''} and q{q}{''} until the following conditions are met:

p=2p+1{p}'={2}\cdot{p}{''}+{1} q=2q+1{q}'={2}\cdot{q}{''}+{1} p,q,p,q  are all odd primes{p}',{q}',{p}{''},{q}{''}\ \text{ are all odd primes}

Parameters p{p}', q{q}' generated like this are considered "safe primes" while p{p}{''} and q{q}{''} are referred to as Sophie Germain primes. This makes n=pq{n}={p}'{q}' a "rigid integer" and very hard to factor.[13]

After calculating n=pq{n}={p}'\cdot{q}' within a trusted environment, p{p}' and q{q}' are no longer needed. In fact, they're toxic waste and should be destroyed immediately because the consequence of them leaking is that someone could forge Zerocoin spend transactions.[21]

💡

In other RSA Accumulator use cases with a trusted centralized party, this trapdoor information is actually useful: It allows removing a value C{C} that is accumulated within Λ\Lambda by calculating Λ=Λ(C1  mod(ϕ(n)))  mod(n)\Lambda'=\Lambda^{{{\left({C}^{{-{1}}}\ \text{ mod(}\phi{\left({n}\right)}\text{)}\right)}}}\ \text{ mod(}{n}\text{}{)} where ϕ(n)=(p1)(q1)\phi{\left({n}\right)}={\left({p}'-{1}\right)}\cdot{\left({q}'-{1}\right)}.

Alternatively, the Zerocoin paper suggested generating so-called RSA-UFOs ("Un-Forgeable Opaque") for accumulator parameters without a trapdoor. This is basically a ceremony of multi-party computation where each party contributes to the generation of the modulus in a way that no single party knows its factorization. The resulting modulus n{n} should, with very high probability, have two large factors.[37]

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

Most Zerocoin implementations, including Zcoin, opted for neither of these setups. Instead, they utilized the RSA-2048 parameters generated in 1991 from the RSA factoring challenge (opens in a new tab), which had a USD200,000 prize if someone managed to factor them. The challenge ended in 2007 with nobody claiming the prize, but this still requires trusting the challenge organizers to truly have destroyed trapdoor information after generation.

Lastly, we need to choose the accumulator's initial value Λ=u\Lambda={u}, with u1{u}\ne{1} and uQRn{u}\in{Q}{R}_{{n}}. To find such a Quadratic Residue we calculate ux2   (mod  n){u}\equiv{x}^{{2}}\ \text{ }\ {\left(\text{mod }\ {n}\text{)}\right.} where x{x} can be a random value or something specific such as a representation of the current date. Although no further explanation on this was given, I assume it is because squaring does not create a permutation of the entire group modulo n{n} as it only maps to quadratic residues and then won't impact the accumulator.[10]

Witness Generation

We've learned how to initialize an Accumulator and how to add commitments to it:

Λ=setup()=ux2   (mod  n)\Lambda={s}{e}{t}{u}{p}{()}={u}\equiv{x}^{{2}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}

Λ=add(Λ,C)=ΛC   (mod  n)\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}=\Lambda^{{C}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}

To generate a witness w{w} that the commitment C{C} was indeed included within Λ\Lambda', we cannot simply use the accumulator's state Λ\Lambda before the commitment was added. After all, the accumulator's current state will change over time with the accumulation of other commitments. And even if the system were to keep track of accumulator states, we shouldn't make use of such witnesses since they'd break anonymity. This is because while the commitment C{C} and witness w{w} are kept secret during the Zero-Knowledge inclusion proof, the resulting accumulator state Λ\Lambda' from Λ=wC\Lambda'={w}^{{C}} will be public. This allows drawing a connection between the Zerocoin minting transaction (when C{C} was publicly added resulting in accumulator state Λ\Lambda') and the Zerocoin spending transaction where inclusion of C{C} is proven.

w=generateWitness(Λ,C)=Λ\C{w}={\mathtt{\text{generateWitness}}}{\left(\Lambda{''},{C}\right)}=\Lambda{''}\backslash{C}

Assuming that the system requires us to prove inclusion within the most current accumulator Λ\Lambda{''} (ie. according to the current block's accumulator checkpoint), we instead generate a witness that is an accumulator state with all of the same commitments contained within Λ\Lambda{''} lest our own C{C}. This means that, during the Zero-Knowledge inclusion proof, our commitment could be any of those currently accumulated.

verifyWitness(Λ,C,w)=(wC=?Λ)={\mathtt{\text{verifyWitness}}}{\left(\Lambda{''},{C},{w}\right)}={\left({w}^{{C}}{\stackrel{{?}}{{=}}}\Lambda{''}\right)}= true/false\texttt{true/false}

In practice, we're unable to remove our included commitment C{C} from the current accumulator state Λ\Lambda{''} to generate a witness, since we lack the necessary accumulator trapdoor information to do so. Instead, we may store the accumulator state Λ\Lambda from before we added our commitment C{C} together with the other secret spending information (S,r){\left({S},{r}\right)} of our coin. Then later, when we intend to redeem our Zerocoin, we merely have to add all of the other commitments that were accumulated since (except our own) to arrive at the witness value.

Pedersen Commitment

When minting a Zerocoin, a commitment needs to be added to the appropriate accumulator. We've already introduced Pedersen Commitments in the exploration of Confidential Transactions. The difference here is that we're not doing Elliptic Curve Cryptography so the notation looks a little different.

C=gShr   (mod  p){C}={g}^{{S}}\cdot{h}^{{r}}\ \text{ }\ {\left(\text{mod }\ {p}\right)}

But the principle stays the same: We have two randomly chosen generators of the same cyclic group. We use the second generator to add a random blinding factor r{r} to ensure that the committed serial number S{S} can not be guessed with brute force. Furthermore, we'll only reveal S{S} to prevent double-spending of Zerocoins, the blinding factor must remain secret as otherwise the commitment can be reconstructed and you'd be able to draw a connection between the minting (reveals commitment C{C}) and the spending (reveals identifier S{S}) transactions, breaking anonymity.

Since Strong RSA Accumulators only allow prime numbers to be added, we may need a few attempts to find a pair (S,r){\left({S},{r}\right)} for which the resulting pedersen commitment is prime.

Note that the modulus p{p} used for the Pedersen Commitment is unrelated to the RSA Accumulator's trapdoor information, though similar in its generation: p=2ωq+1{p}={2}^{{\omega}}\cdot{q}+{1} where both p,q{p},{q} are prime with security parameter ω1\omega\ge{1}. Generators g,hZp{g},{h}\in{\mathbb{Z}_{{p}}^{{\ast}}} are of a subgroup of order q{q} from which the random values for S,r{S},{r} are taken.

Zero-knowledge Proofs

So far, we've learned how to initialize an Accumulator Λ\Lambda, and how to create a prime commitment C{C} to a Zerocoin's serial number S{S}, blinded by a random value r{r}. We generate a witness w{w}, with an accumulator state where C{C} has not been added, that we can use to prove inclusion of the commitment in Λ=wC\Lambda{''}={w}^{{C}}. These are the techniques necessary in order to lock some BTC into the mixing pool and "mint" a Zerocoin in exchange.

To redeem the Zerocoin later, we'd have to prove that (1) our coin's commitment C{C} is indeed included within the Accumulator Λ\Lambda{''}, and (2) that the unspent Serial number S{S} we're revealing was indeed the one that was committed to. But, in order to stay anonymous, we must prove this without revealing C{C}, w{w}, or r{r} since any of these would allow connecting the redemption to the transaction that minted the Zerocoin.

To accomplish this, the paper described the following Zero Knowledge Signature of Knowledge π\pi on transaction data T{\mathbf{\text{T}}}:

π=ZKSoK[T]{(C,w,r):verifyWitness(Λ,C,w)=trueC=gShr}\pi={\mathbf{\text{ZKSoK[T]}}}{\left\lbrace{\left({\color{red}{{C}}},{\color{red}{{w}}},{\color{red}{{r}}}\right)}:{\mathtt{\text{verifyWitness}}}{\left(\Lambda{''},{\color{red}{{C}}},{\color{red}{{w}}}\right)}={\mathtt{\text{true}}}\wedge{\color{red}{{C}}}={g}^{{S}}\cdot{h}^{{\color{red}{{r}}}}\right\rbrace}

Proof of Accumulator Inclusion

For the first part, proving that a committed value is accumulated, the Zerocoin paper and other publications omit detailed explanations and instead refer the reader to the original protocol presented by Camenisch and Lysyanskaya.[8] They summarize that the described proof is then converted into a Non-Interactive Zero-Knowledge Proof of Knowledge via Fiat-Shamir transform:

NIZKPoK{(C,w):verifyWitness(Λ,C,w)=true}{\mathbf{\text{NIZKPoK}}}{\left\lbrace{\left({\color{red}{{C}}},{\color{red}{{w}}}\right)}:{\mathtt{\text{verifyWitness}}}{\left(\Lambda{''},{\color{red}{{C}}},{\color{red}{{w}}}\right)}={\mathtt{\text{true}}}\right\rbrace}
💡

The authors consider the described Zero-Knowledge Proof of Knowledge efficient; although the large proof sizes and the resulting inefficiencies are arguably one of Zerocoin's biggest drawbacks. But still, compared to an inclusion proof that, like Ring Signatures, grows linearly with each member within the group, the used proof is indeed much more efficient (logarithmic).

To construct the proof, we once again need to make use of a pedersen commitment CΛ\mathbb{C}_{\Lambda}, which commits to the commitment C{C} which was added to the accumulator as a value. The proof then works by showing that the value C{C} is contained in both the commitment CΛ\mathbb{C}_{\Lambda} as well as within the accumulator Λ\Lambda without revealing C{C}. Only the new commitment CΛ\mathbb{C}_{\Lambda} has to be revealed as part of this protocol.

CΛ=gChr   (mod  p)\mathbb{C}_{\Lambda}=\overline{{g}}^{{C}}\cdot\overline{{h}}^{{r}}\ \text{ }\ {\left(\text{mod }\ \overline{{p}}\right)}

In addition to being prime, further restrictions on the choice of the C{C} commitment values are necessary to ensure the proof's security: First, commitments must be within a sub-range χA,B\chi_{{{A},{B}}} as 2<ACB<A2{2}<{A}\le{C}\le{B}<{A}^{{2}} to guarantee that the product of any two commitments falls outside of the range.[20] Second, for χA,B\chi_{{{A},{B}}} and the choice of q\overline{{q}} it's required that B2λ+λ+2<A21<q2{B}\cdot{2}^{{\lambda'+\lambda{''}+{2}}}<{A}^{{2}}-{1}<\frac{\overline{{q}}}{{2}} holds, where λ,λ\lambda',\lambda{''} are adjustable security parameters.

Next, we need a few more auxiliary (helper) commitments. While CΛ\mathbb{C}_{\Lambda}'s generators are from a subgroup of order q\overline{{q}} within Zp{\mathbb{Z}_{{\overline{{p}}}}^{{\ast}}}, these auxiliary commitments instead have g~,h~\tilde{{g}},\tilde{{h}} which are two elements from QRn{Q}{R}_{{n}} (quadratic residues within the accumulator's modulo n{n}) for which logg(h){{\log}_{{{g}}}{\left({h}\right)}} is unknown (similarly to how in ECC the relationship H=xG{H}={x}\cdot{G} must remain unknown in order to prevent the prover from tempering with the committed values). The blinding factors r1,r2,r3{r}_{{1}},{r}_{{2}},{r}_{{3}} are chosen randomly from Z[n4]\mathbb{Z}_{{{\left[\frac{{n}}{{4}}\right]}}}.

ProverVerifier
Knows (g,h,n,g~,h~,Λ,CΛ,r,C,w){\left(\overline{{g}},\overline{{h}},{n},\tilde{{g}},\tilde{{h}},\Lambda{''},\mathbb{C}_{\Lambda},{\color{red}{{r}}},{\color{red}{{C}}},{\color{red}{{w}}}\right)}Knows (g,h,n,g~,h~,Λ,CΛ){\left(\overline{{g}},\overline{{h}},{n},\tilde{{g}},\tilde{{h}},\Lambda{''},\mathbb{C}_{\Lambda}\right)}
Chooses random values (r1,r2,r3){\left({\color{red}{{r}_{{1}},{r}_{{2}},{r}_{{3}}}}\right)}
C~C=g~Ch~r1  mod(n)\tilde{\mathbb{C}}_{{C}}=\tilde{{g}}^{{\color{red}{{C}}}}\cdot\tilde{{h}}^{{{\color{red}{{r}_{{1}}}}}}\ \text{ mod(}{n}\text{}{)}
C~w=wh~r2  mod(n)\tilde{\mathbb{C}}_{{{w}}}={\color{red}{{w}}}\cdot\tilde{{h}}^{{{\color{red}{{r}_{{2}}}}}}\ \text{ mod(}{n}\text{}{)}
C~r=g~r2h~r3  mod(n)\tilde{\mathbb{C}}_{{r}}=\tilde{{g}}^{{{\color{red}{{r}_{{2}}}}}}\cdot\tilde{{h}}^{{{\color{red}{{r}_{{3}}}}}}\ \text{ mod(}{n}\text{}{)}
Sends (C~C,C~w,C~r){\left(\tilde{\mathbb{C}}_{{C}},\tilde{\mathbb{C}}_{{{w}}},\tilde{\mathbb{C}}_{{r}}\right)}\RightarrowKnows (g,h,n,g~,h~,Λ,CΛ,C~C,C~w,C~r){\left(\overline{{g}},\overline{{h}},{n},\tilde{{g}},\tilde{{h}},\Lambda{''},\mathbb{C}_{\Lambda},\tilde{\mathbb{C}}_{{C}},\tilde{\mathbb{C}}_{{{w}}},\tilde{\mathbb{C}}_{{r}}\right)}

Like CΛ\mathbb{C}_{\Lambda}, the auxiliary commitment C~C\tilde{\mathbb{C}}_{{C}} commits to C{C}, the value accumulated by Λ\Lambda{''}. Additionally, C~w\tilde{\mathbb{C}}_{{w}} commits to witness w{w} and will be used to prove that it corresponds to the C{C}-th root value Λ\Lambda{''} (Λ=wCΛC=w\Lambda{''}={w}^{{C}}\Leftrightarrow{\sqrt[{{C}}]{{\Lambda{''}}}}={w}).

ProverVerifier
Knows (g,h,n,g~,h~,CΛ,Λ,C~C,C~w,C~r,r,C,w){\left(\overline{{g}},\overline{{h}},{n},\tilde{{g}},\tilde{{h}},\mathbb{C}_{\Lambda},\Lambda{''},\tilde{\mathbb{C}}_{{C}},\tilde{\mathbb{C}}_{{{w}}},\tilde{\mathbb{C}}_{{r}},{\color{red}{{r}}},{\color{red}{{C}}},{\color{red}{{w}}}\right)}Knows (g,h,n,g~,h~,CΛ,Λ,C~C,C~w,C~r){\left(\overline{{g}},\overline{{h}},{n},\tilde{{g}},\tilde{{h}},\mathbb{C}_{\Lambda},\Lambda{''},\tilde{\mathbb{C}}_{{C}},\tilde{\mathbb{C}}_{{{w}}},\tilde{\mathbb{C}}_{{r}}\right)}
Chooses random values (α,β,γ,δ,ϵ,ζ,φ,ψ,η,σ,ξ){\left({\color{red}{\alpha,\beta,\gamma,\delta,\epsilon,\zeta,\varphi,\psi,\eta}},\sigma,\xi\right)}
t1=gαhφ  mod(p){t}_{{1}}=\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ mod(}\overline{{p}}\text{}{)}
t2=(CΛg)γhψ  mod(p){t}_{{2}}={\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ mod(}\overline{{p}}\text{}{)}
t3=(gCΛ)σhξ  mod(p){t}_{{3}}={\left(\overline{{g}}\cdot\mathbb{C}_{\Lambda}\right)}^{\sigma}\cdot\overline{{h}}^{\xi}\ \text{ mod(}\overline{{p}}\text{}{)}
t~1=g~ϵh~ζ  mod(n)\tilde{{t}}_{{1}}=\tilde{{g}}^{{\color{red}{\epsilon}}}\cdot\tilde{{h}}^{{\color{red}{\zeta}}}\ \text{ mod(}{n}\text{}{)}
t~2=g~αh~η  mod(n)\tilde{{t}}_{{2}}=\tilde{{g}}^{{\color{red}{\alpha}}}\cdot\tilde{{h}}^{{\color{red}{\eta}}}\ \text{ mod(}{n}\text{}{)}
t~3=(C~w)αh~β  mod(n)\tilde{{t}}_{{3}}={\left(\tilde{\mathbb{C}}_{{w}}\right)}^{{\color{red}{\alpha}}}\cdot\tilde{{h}}^{{-{{\color{red}{\beta}}}}}\ \text{ mod(}{n}\text{}{)}
t~4=(C~r)αh~δg~β  mod(n)\tilde{{t}}_{{4}}={\left(\tilde{\mathbb{C}}_{{r}}\right)}^{{\color{red}{\alpha}}}\cdot\tilde{{h}}^{{-{{\color{red}{\delta}}}}}\cdot\tilde{{g}}^{{-{{\color{red}{\beta}}}}}\ \text{ mod(}{n}\text{}{)}
Sends (t1,t2,t3,t~1,t~2,t~3,t~4){\left({t}_{{1}},{t}_{{2}},{t}_{{3}},\tilde{{t}}_{{1}},\tilde{{t}}_{{2}},\tilde{{t}}_{{3}},\tilde{{t}}_{{4}}\right)}\RightarrowKnows (,t1,t2,t3,t~1,t~2,t~3,t~4){\left(\ldots,{t}_{{1}},{t}_{{2}},{t}_{{3}},\tilde{{t}}_{{1}},\tilde{{t}}_{{2}},\tilde{{t}}_{{3}},\tilde{{t}}_{{4}}\right)}
Chooses a random challenge e{0,1}λ{e}\in{\left\lbrace{0},{1}\right\rbrace}^{\lambda}
Knows (,e){\left(\ldots,{e}\right)}\Leftarrow Sends e{e}
α=αeC\overline{\alpha}={\color{red}{\alpha}}-{e}\cdot{\color{red}{{C}}}
β=βer2C\overline{\beta}={\color{red}{\beta}}-{e}\cdot{\color{red}{{r}_{{2}}\cdot{C}}}
ζ=ζer3\overline{\zeta}={\color{red}{\zeta}}-{e}\cdot{\color{red}{{r}_{{3}}}}
η=ηer1\overline{\eta}={\color{red}{\eta}}-{e}\cdot{\color{red}{{r}_{{1}}}}
ϵ=ϵer2\overline{\epsilon}={\color{red}{\epsilon}}-{e}\cdot{\color{red}{{r}_{{2}}}}
δ=δer3C\overline{\delta}={\color{red}{\delta}}-{e}\cdot{\color{red}{{r}_{{3}}\cdot{C}}}
φ=φer  mod(q)\overline{\varphi}={\color{red}{\varphi}}-{e}\cdot{\color{red}{{r}}}\ \text{ mod(}\overline{{q}}\text{}{)}
γ=γe(C1)1  mod(q)\overline{\gamma}={\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}\ \text{ mod(}\overline{{q}}\text{}{)}
ψ=ψ+er(C1)1  mod(q)\overline{\psi}={\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}\ \text{ mod(}\overline{{q}}\text{}{)}
σ=σe(C+1)1  mod(q)\overline{\sigma}=\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}\ \text{ mod(}\overline{{q}}\text{}{)}
ξ=ξ+er(C+1)1  mod(q)\overline{\xi}=\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}\ \text{ mod(}\overline{{q}}\text{}{)}
Sends (α,β,γ,δ,ϵ,ζ,φ,ψ,η,σ,ξ){\left(\overline{\alpha},\overline{\beta},\overline{\gamma},\overline{\delta},\overline{\epsilon},\overline{\zeta},\overline{\varphi},\overline{\psi},\overline{\eta},\overline{\sigma},\overline{\xi}\right)}\RightarrowKnows (,α,β,γ,δ,ϵ,ζ,φ,ψ,η,σ,ξ){\left(\ldots,\overline{\alpha},\overline{\beta},\overline{\gamma},\overline{\delta},\overline{\epsilon},\overline{\zeta},\overline{\varphi},\overline{\psi},\overline{\eta},\overline{\sigma},\overline{\xi}\right)}
t1   =?   (CΛ)egαhφ  mod(p){t}_{{1}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\mathbb{C}_{\Lambda}\right)}^{{e}}\cdot\overline{{g}}^{{\overline{\alpha}}}\cdot\overline{{h}}^{{\overline{\varphi}}}\ \text{ mod(}\overline{{p}}\text{}{)}
t2   =?   ge(CΛg)γhψ  mod(p){t}_{{2}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{\overline{\gamma}}}\cdot\overline{{h}}^{{\overline{\psi}}}\ \text{ mod(}\overline{{p}}\text{}{)}
t3   =?   ge(gCΛ)σhξ  mod(p){t}_{{3}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\overline{{g}}\cdot\mathbb{C}_{\Lambda}\right)}^{{\overline{\sigma}}}\cdot\overline{{h}}^{{\overline{\xi}}}\ \text{ mod(}\overline{{p}}\text{}{)}
t~1   =?   (C~r)eg~ϵh~ζ  mod(n)\tilde{{t}}_{{1}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\tilde{\mathbb{C}}_{{r}}\right)}^{{e}}\cdot\tilde{{g}}^{{\overline{\epsilon}}}\cdot\tilde{{h}}^{{\overline{\zeta}}}\ \text{ mod(}{n}\text{}{)}
t~2   =?   (C~C)eg~αh~η  mod(n)\tilde{{t}}_{{2}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\tilde{\mathbb{C}}_{{C}}\right)}^{{e}}\cdot\tilde{{g}}^{{\overline{\alpha}}}\cdot\tilde{{h}}^{{\overline{\eta}}}\ \text{ mod(}{n}\text{}{)}
t~3   =?   (Λ)e(C~w)αh~β  mod(n)\tilde{{t}}_{{3}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\Lambda{''}\right)}^{{e}}\cdot{\left(\tilde{\mathbb{C}}_{{w}}\right)}^{{\overline{\alpha}}}\cdot\tilde{{h}}^{{-\overline{\beta}}}\ \text{ mod(}{n}\text{}{)}
t~4   =?   (C~r)αh~δg~β  mod(n)\tilde{{t}}_{{4}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\tilde{\mathbb{C}}_{{r}}\right)}^{{\overline{\alpha}}}\cdot\tilde{{h}}^{{-\overline{\delta}}}\cdot\tilde{{g}}^{{-\overline{\beta}}}\ \text{ mod(}{n}\text{}{)}
α   ?   [B2λ+λ+1,B2λ+λ+1]\overline{\alpha}\ \text{ }\ {\overset{{?}}{{\in}}}\ \text{ }\ {\left[-{B}\cdot{2}^{{\lambda'+\lambda{''}+{1}}},{B}\cdot{2}^{{\lambda'+\lambda{''}+{1}}}\right]}

Note that the random exponents have to be selected as follows: α(B2λ+λ,,B2λ+λ),γ,φ,ψ,σ,ξZq,ϵ,η,ζ(n42λ+λ,,n42λ+λ),andβ,δ(n4q2λ+λ,,n4q2λ+λ)\alpha\in{\left(-{B}\cdot{2}^{{\lambda'+\lambda{''}}},\ldots,{B}\cdot{2}^{{\lambda'+\lambda{''}}}\right)},\gamma,\varphi,\psi,\sigma,\xi\in\mathbb{Z}_{{q}},\epsilon,\eta,\zeta\in{\left(-\lfloor\frac{{n}}{{4}}\rfloor\cdot{2}^{{\lambda'+\lambda{''}}},\ldots,\lfloor\frac{{n}}{{4}}\rfloor\cdot{2}^{{\lambda'+\lambda{''}}}\right)},{\quad\text{and}\quad}\beta,\delta\in{\left(-\lfloor\frac{{n}}{{4}}\rfloor\cdot{q}{2}^{{\lambda'+\lambda{''}}},\ldots,\lfloor\frac{{n}}{{4}}\rfloor\cdot{q}{2}^{{\lambda'+\lambda{''}}}\right)}.

Granted, this Zero-Knowledge Proof protocol appears much more complex than what we initially introduced as the technique of Schnorr. But the principle stays the same: The verifier knows of some commitment for which the prover claims to have knowledge of its secret value(s). Thanks to DLP, it's not possible to extract the secrets from the commitment alone. The prover chooses randomness (α,\alpha,\ldots) and uses it to calculate temporary commitments t{t} which are sent to the verifier. The verifier too generates randomness and sends it to the prover as the challenge e{e}. The prover mixes (α,\overline{\alpha},\ldots) its own randomness with the challenge and the secrets in a manner that will allow for things to cancel each other out for the verifier, resulting in a value matching that of the temporary commitments t{t}. The verifier knows that the prover wouldn't have been able to generate the appropriate exponents (α,\overline{\alpha},\ldots) without knowledge of the secret values, for things to match at the end.

t1   =?   (CΛ)egαhφ{t}_{{1}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\mathbb{C}_{\Lambda}\right)}^{{e}}\cdot\overline{{g}}^{{\overline{\alpha}}}\cdot\overline{{h}}^{{\overline{\varphi}}}

Substitute t1=gαhφ  ,  CΛ=gChr  ,  α=αeC  ,  φ=φer{t}_{{1}}=\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ , }\ \mathbb{C}_{\Lambda}=\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\ \text{ , }\ \overline{\alpha}={\color{red}{\alpha}}-{e}\cdot{\color{red}{{C}}}\ \text{ , }\ \overline{\varphi}={\color{red}{\varphi}}-{e}\cdot{\color{red}{{r}}}

gαhφ   =?   (gChr)egαeChφer\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ {\left(\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}^{{e}}\cdot\overline{{g}}^{{{\color{red}{\alpha}}-{e}\cdot{\color{red}{{C}}}}}\cdot\overline{{h}}^{{{\color{red}{\varphi}}-{e}\cdot{\color{red}{{r}}}}}

gαhφ   =?   geChergαeChφer\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{{e}\cdot{\color{red}{{C}}}}}\cdot\overline{{h}}^{{{e}\cdot{\color{red}{{r}}}}}\cdot\overline{{g}}^{{{\color{red}{\alpha}}-{e}\cdot{\color{red}{{C}}}}}\cdot\overline{{h}}^{{{\color{red}{\varphi}}-{e}\cdot{\color{red}{{r}}}}}

gαhφ   =?   geC+αeCher+φer\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{{e}\cdot{\color{red}{{C}}}+{\color{red}{\alpha}}-{e}\cdot{\color{red}{{C}}}}}\cdot\overline{{h}}^{{{e}\cdot{\color{red}{{r}}}+{\color{red}{\varphi}}-{e}\cdot{\color{red}{{r}}}}}

gαhφ   =?   geC+αeCher+φer\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{\cancel{{{e}\cdot{\color{red}{{C}}}}}+{\color{red}{\alpha}}-\cancel{{{e}\cdot{\color{red}{{C}}}}}}}\cdot\overline{{h}}^{{\cancel{{{e}\cdot{\color{red}{{r}}}}}+{\color{red}{\varphi}}-\cancel{{{e}\cdot{\color{red}{{r}}}}}}}

gαhφ   =   gαhφ\overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ \overline{{g}}^{{\color{red}{\alpha}}}\cdot\overline{{h}}^{{\color{red}{\varphi}}}

t2   =?   ge(CΛg)γhψ{t}_{{2}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{\overline{\gamma}}}\cdot\overline{{h}}^{{\overline{\psi}}}

Substitute t2=(CΛg)γhψ  ,  CΛ=gChr  ,  γ=γe(C1)1  ,  ψ=ψ+er(C1)1{t}_{{2}}={\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ , }\ \mathbb{C}_{\Lambda}=\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\ \text{ , }\ \overline{\gamma}={\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}\ \text{ , }\ \overline{\psi}={\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}

(CΛg)γhψ   =?   ge(CΛg)γe(C1)1hψ+er(C1)1{\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\frac{\mathbb{C}_{\Lambda}}{\overline{{g}}}\right)}^{{{\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

(gChrg)γhψ   =?   ge(gChrg)γe(C1)1hψ+er(C1)1{\left(\frac{{\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}}}{\overline{{g}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\frac{{\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}}}{\overline{{g}}}\right)}^{{{\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

((gChr)g1)γhψ   =?   ge((gChr)g1)γe(C1)1hψ+er(C1)1{\left({\left(\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}\cdot\overline{{g}}^{{-{{1}}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left({\left(\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}\cdot\overline{{g}}^{{-{{1}}}}\right)}^{{{\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

(g(C1)hr)γhψ   =?   ge(g(C1)hr)γe(C1)1hψ+er(C1)1{\left(\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}^{{\color{red}{\gamma}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}^{{{\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

g(C1)γhrγhψ   =?   geg(C1)(γe(C1)1)hr(γe(C1)1)hψ+er(C1)1\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{\color{red}{\psi}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\left({\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}\right)}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\left({\color{red}{\gamma}}-{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}\right)}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

g(C1)γhrγ+ψ   =?   geg(C1)γ(C1)e(C1)1hrγre(C1)1hψ+er(C1)1\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}-{\left({\color{red}{{C}}}-{1}\right)}\cdot{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}-{\color{red}{{r}}}\cdot{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

Since we're in an abelian group, the following holds true: (C1)(C1)1=1  mod(p){\left({C}-{1}\right)}\cdot{\left({C}-{1}\right)}^{{-{{1}}}}={1}\ \text{ mod(}\overline{{p}}\text{)}

g(C1)γhrγ+ψ   =?   geg(C1)γ(C1)e(C1)1hrγre(C1)1+ψ+er(C1)1\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}-{\left(\cancel{{{\color{red}{{C}}}-{1}}}\right)}\cdot{e}\cdot\cancel{{{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}-{\color{red}{{r}}}\cdot{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}+{\color{red}{\psi}}+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}

g(C1)γhrγ+ψ   =?   ge+(C1)γehrγre(C1)1+ψ+er(C1)1\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{{e}+{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}-{e}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}-\cancel{{{\color{red}{{r}}}\cdot{e}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}+{\color{red}{\psi}}+\cancel{{{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}-{1}\right)}^{{-{{1}}}}}}}}

g(C1)γhrγ+ψ   =?   ge+(C1)γehrγ+ψ\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{\cancel{{{e}}}+{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}\cancel{{-{e}}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}

g(C1)γhrγ+ψ   =   g(C1)γhrγ+ψ\overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ \overline{{g}}^{{{\left({\color{red}{{C}}}-{1}\right)}\cdot{\color{red}{\gamma}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\color{red}{\gamma}}+{\color{red}{\psi}}}}

t3   =?   ge(gCΛ)σhξ{t}_{{3}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\overline{{g}}\cdot\mathbb{C}_{\Lambda}\right)}^{{\overline{\sigma}}}\cdot\overline{{h}}^{{\overline{\xi}}}

Substitute t3=(gCΛ)σhξ,  CΛ=gChr  ,  σ=σe(C+1)1  ,  ξ=ξ+er(C+1)1{t}_{{3}}={\left(\overline{{g}}\cdot\mathbb{C}_{\Lambda}\right)}^{\sigma}\cdot\overline{{h}}^{\xi}\text{, }\ \mathbb{C}_{\Lambda}=\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\ \text{ , }\ \overline{\sigma}=\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}\ \text{ , }\ \overline{\xi}=\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}

(g(gChr))σhξ   =?   ge(g(gChr))σe(C+1)1hξ+er(C+1)1{\left(\overline{{g}}\cdot{\left(\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}\right)}^{\sigma}\cdot\overline{{h}}^{\xi}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\overline{{g}}\cdot{\left(\overline{{g}}^{{\color{red}{{C}}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}\right)}^{{\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}

(g(C+1)hr)σhξ   =?   ge(g(C+1)hr)σe(C+1)1hξ+er(C+1)1{\left(\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}^{\sigma}\cdot\overline{{h}}^{\xi}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot{\left(\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}}}\cdot\overline{{h}}^{{\color{red}{{r}}}}\right)}^{{\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}

g(C+1)σhrσhξ   =?   geg(C+1)(σe(C+1)1)hr(σe(C+1)1)hξ+er(C+1)1\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot\sigma}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot\sigma}}\cdot\overline{{h}}^{\xi}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot{\left(\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}\right)}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot{\left(\sigma-{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}\right)}}}\cdot\overline{{h}}^{{\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}

g(C+1)σhrσ+ξ   =?   geg(C+1)σ(C+1)e(C+1)1hrσre(C+1)1hξ+er(C+1)1\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot\sigma}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot\sigma+\xi}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot\sigma-{\left({\color{red}{{C}}}+{1}\right)}\cdot{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot\sigma-{\color{red}{{r}}}\cdot{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}

Since we're in an abelian group, the following holds true: (C+1)(C+1)1=1  mod(p){\left({C}+{1}\right)}\cdot{\left({C}+{1}\right)}^{{-{{1}}}}={1}\ \text{ mod(}\overline{{p}}\text{)}

g(C+1)σhrσ+ξ   =?   geg(C+1)σ(C+1)e(C+1)1hrσre(C+1)1hξ+er(C+1)1\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot\sigma}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot\sigma+\xi}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overline{{g}}^{{e}}\cdot\overline{{g}}^{{{\left({\color{red}{{C}}}+{1}\right)}\cdot\sigma-\cancel{{{\left({\color{red}{{C}}}+{1}\right)}}}\cdot{e}\cdot\cancel{{{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}}}\cdot\overline{{h}}^{{{\color{red}{{r}}}\cdot\sigma-{\color{red}{{r}}}\cdot{e}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}\cdot\overline{{h}}^{{\xi+{e}\cdot{\color{red}{{r}}}\cdot{\left({\color{red}{{C}}}+{1}\right)}^{{-{{1}}}}}}