Cryptocurrency Privacy Technologies: Lelantus Protocol

25. March, 2024 by patrickd

The Concept

Understanding the core concept behind the Lelantus Protocol only requires some basic knowledge on Bitcoin transactions and Elliptic Curve Cryptography.

Zerocoin Scheme in Review

At a high level, the Zerocoin Scheme basically adds a native mixer to a standard transparent ledger blockchain: A fixed denomination of public coins is "burned" in exchange for "minting" a private coin. Or more accurately, some fixed amount of public coins are locked into a pool together with all other coins of the same denomination and for each time a user does this they obtain a secret voucher that they can later redeem in order to re-obtain that same amount of public coins. When the voucher is revealed for redemption, the fact that there's no way to tell which of the public coins were originally burned in exchange for the voucher is how this scheme achieves untraceability.

The Sigma Protocol implements this scheme by using Pedersen Commitments for vouchers, where ${s}$ is a serial number and ${r}$ is a random blinding factor.

When a user mints a voucher, they publish such a commitment ${C}$ as part of the transaction's output and burn the appropriate amount of public coin from some UTXO. Later, the user can redeem those vouchers by generating a Zero-Knowledge One-Out-Of-Many Proof that demonstrates that they have the knowledge necessary (${s}$, ${r}$) to open a commitment within the set of all minted vouchers. The verifier requires the serial number ${s}$ to be revealed as part of this process to prevent users from redeeming the same voucher multiple times. The blinding factor ${r}$ though is kept secret and without it, it's impossible to determine the commitment ${C}$ that belongs to the revealed serial number.

Confidential Transactions in Review

The Confidential Transactions scheme works by hiding transaction amounts within homomorphic commitments. Homomorphism allows the verifier to sum the hidden amounts of both transaction inputs and outputs and compare these sums to ensure that no new coins are being created from nothing. These commitments ${V}$ are Pedersen as well, with the difference that they're hiding the public coin amounts ${v}$ instead of a serial number ${s}$.

Unfortunately, checking $\sum{v}_{{\text{inputs}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \sum{v}_{{\text{outputs}}}$ on its own is not sufficient since outputs could contain "negative amounts" that would once again allow the creation of new coins. To prevent this, the verifier requires each output to have a range proof (opens in a new tab) demonstrating that all values ${v}_{{{o}{u}{t}{p}{u}{t}{s}}}$ are "positive".

Lelantus' Core Idea

As shown, the cryptographic primitive that both the Zerocoin Scheme and Confidential Transactions have in common are Pedersen Commitments:

Lelantus combines both of these schemes through this commonality, resulting in a protocol that inherits both of their the privacy-enhancing aspects.

Coin commitment ${C}$ now hides both the coin's serial number ${s}$ and the coin amount ${v}$ it is carrying. To maintain the binding properties of this generalized Pedersen commitment (or "double-blinded" commitment), we assume that the logarithmic relationship between all generator points (${G}_{{1}},{G}_{{2}},{H}$) is unknown.

Minting

For a coin commitment to be of value, it has to be "minted" as done in the Zerocoin scheme. To mint, the transaction signer chooses the public coin UTXOs they want to "burn" in exchange. The sum of the input amounts becomes the committed value ${v}$ which is blinded by both the serial ${s}$ and the blinding factor ${r}$. The resulting coin commitment ${C}$ is published by the signer as part of the transaction outputs. Before adding the commitment to the set of valid vouchers, the validators have to ensure that the committed value ${v}$ within ${C}$ is actually equal to $\sum{v}_{{\text{inputs}}}\text{}$.

Despite knowledge of what ${v}$ should be, the verifier can only open the commitment ${C}$ with additional knowledge of ${s}$ and ${r}$. However the serial number should only be revealed as part of the redemption process, and the random blinding factor must never be revealed as this would introduce traceability by reconstructing the commitment during redemption.

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

Instead of revealing information to allow the verifier to open the commitment and check the committed coin amount, a generalized Schnorr Proof is used to convince the verifier of the signer's knowledge of ${s}$ and ${r}$ such that the commitment opens for the correct ${v}$.

SplitJoin

The mint operation is purposefully kept simple with a single private output, which is sufficient to move arbitrary amounts of coins into the "mixer". But if the spending logic would be equally simple (ie. redeeming only a single voucher per transaction), the protocol's privacy would actually be worse than the Zerocoin scheme on its own. That is because before we basically had multiple anonymity sets, one for each fixed denomination. But if redemptions reveal the exact same amount of coins used during minting, each specific public coin amount would become its own anonymity set - and it's unlikely that an amount such as ${1.50284}$ would be minted by multiple people.

This is why, instead of a simple spend operation, we have "SplitJoin" that allows merging multiple coin commitments in a transaction's input and splitting them apart into new commitments as output. Most interestingly, it lets us execute partial spends: If you had minted a single coin commitment with a large sum, you'll be able to anonymously redeem that commitment in exchange for a new commitment and a public coin output that contains a partial amount of the original sum.

Implementing the JoinSplit operation comes with several challenges:

• With the coin commitments now being double-blinded, changes to the One-Out-Of-Many Proof protocol are necessary to demonstrate the ability to open a commitment within the anonymity set with the specified serial number.
• Similar to how it was part of the Confidential Transactions scheme, it's necessary to ensure that the sum of input coin amounts is equal to the sum of output amounts. But since we can't reveal the input commitments without losing untraceability, this needs to be done as part of the OOOMP somehow.
• When a transaction has more than a single output (which is always the case when considering fees as a transparent output), each of the output coin commitments must come with a range proof to prohibit commitments with negative coin amounts being used to create new value out of thin air.

The Math

Generalized Schnorr Proof

We previously discussed the construction of simple Schnorr Proofs in the introduction of the Zerocoin scheme. In short, it allowed us to prove knowledge of a secret witness ${s}$ belonging to a public key ${V}$ such that ${V}={s}{G}$.

A generalized Schnorr Proof allows the prover to demonstrate knowledge of multiple such witnesses ${s}_{{n}}$ belonging to a single commitment ${C}$ without revealing them.

With all ${G}_{{n}}$ being logarithmically independent generators, the following protocol is executed between Prover and Verifier:

During the Lelantus minting process, the verifier already has knowledge of the coin amount ${v}$ from the transparent UTXO inputs and is therefore able to compute ${v}{G}_{{2}}$. After subtracting this from the coin commitment specified as the transaction output (${C}'={C}-{v}{G}_{{2}}$), the above Schnorr protocol demonstrates that the signer is able to open ${C}'={s}{G}_{{1}}+{r}{H}$ without revealing its secret scalars. If this succeeds, the verifier can be sure that the original ${C}$ committed to the expected amount ${v}$ since ${C}={C}'+{v}{G}_{{2}}$.

OOOMP in Review

To briefly recap how One-Out-Of-Many Proofs originally worked, we assume that there are ${N}$ commitments ${C}_{{i}}$ each representing a minted private coin. We say that a Prover has knowledge of serial number ${s}$ and a blinding factor ${r}$ by which one of these commitments at index ${l}$ can be opened, proving ownership and therefore the ability to spend the private coin.

To exchange the private coin for its denomination of locked public coins, the Prover reveals the serial number ${s}$ which the Verifier will remember to prevent the Prover from spending the same commitment more than once. The serial number is "homomorphically subtracted" from all commitments ${C}_{{i}}$ resulting in some other ${C}'_{{i}}$ for all but the commitment at ${l}$ which now commits to 0:

The proof now demonstrates that the Prover is able to open one of the commitments ${C}'_{{i}}$ with his knowledge of ${r}$ without revealing that it was ${C}'_{{l}}$. To do so, it begins with the execution of a 3-move-type proof committing to a valid index ${l}$ in zero-knowledge, during which it responds to the challenge ${x}$ with ${f}_{{j}}$:

Here, the value of ${l}$ is represented by ${n}$ bits ${l}_{{j}}\in{\left\lbrace{0},{1}\right\rbrace}$, while ${a}_{{j}}$ is a random value committed to by the Prover in the first move of the protocol. This is generalized, such that it can be applied to all indices ${i}$ represented by bits ${i}_{{j}}$:

Creating the product ${\prod_{{{j}={1}}}^{{n}}}{f}_{{{j},{i}_{{j}}}}$ for any index ${i}$ results in a polynomial ${\left(\delta_{{{l}_{{1}}{i}_{{1}}}}{x}\pm{a}_{{1}}\right)}\cdot{\left(\delta_{{{l}_{{2}}{i}_{{2}}}}{x}\pm{a}_{{2}}\right)}\cdot\ldots\cdot{\left(\delta_{{{l}_{{n}}{i}_{{n}}}}{x}\pm{a}_{{n}}\right)}$ that can be expanded to the standard form:

The Kronecker Delta $\delta_{l_{j}i_{j}}$ will only be ${1}$ for when the bits of both ${l}$ and ${i}$ at position ${j}$ are equal. This means that all ${x}$ of the product are only multiplied by ${1}$ when the current index ${i}={l}$, resulting in a polynomial of ${n}$-th order. For all other indices ${i}$ some ${x}$ will be multiplied by ${0}$ resulting in lower-order coefficients.

Even without knowing ${x}$ yet, the Prover is able to determine the polynomial's coefficients which are based on his own randomness $\pm{a}_{{j}}$. The lower-order coefficients ${p}_{{{i},{k}}}$ are used to extend the zero-knowledge protocol with additional first-move commitments:

The idea is that the ${D}_{{k}}$ commitments represent the polynomials ${{f}_{{i}}{\left({x}\right)}}$ in a state where they have not been evaluated for a specific ${x}$ yet, with the difference that the commitments lack the highest order coefficient for ${x}^{{n}}$. On the other hand, the products based on the challenge-response values ${f}_{{{j},{i}_{{j}}}}$ represent the polynomials ${{f}_{{i}}{\left({x}\right)}}$ evaluated for challenge ${x}$ with all their coefficients. A subtraction between these two will therefore result in all lower-order coefficients canceling out, leaving ${x}^{{n}}{C}'_{{l}}$.

To prevent revealing the actual ${C}'_{{l}}$, the commitments ${D}_{{k}}$ would additionally have blinding factors ${r}'_{{k}}$ known only to the Prover.

With that, the Prover is able to demonstrate knowledge of blinding factors ${r}$ and ${r}'$ without revealing them, and therefore proving his ability to open the commitment ${C}'_{{l}}$, and ultimately ${C}_{{l}}$.

Generalized OOOMP

As can be seen above, the original One-Out-Of-Many Proof scheme assumed that the commitment, that is being proven to be part of the anonymity set, is required to commit to zero with a single blinding factor:

But this does not apply in Lelantus anymore, where we basically have a commitment that is double-blinded by both the coin amount and a random factor:

The Lelantus paper presents a modification to the OOOMP system that works with double-blinded Pedersen commitments:

The above protocol for ${N}={m}^{{n}}$ anonymity sets was taken from the previous article on the Sigma Protocol. For the purposes of this article, we'll only concentrate on the ${\color{blue}{\text{changes}}}$.

The final check originally looked like this

with ${D}_{{k}}={\sum_{{{i}={0}}}^{{{N}-{1}}}}{p}_{{{i},{k}}}{C}'_{{i}}+{\color{red}{\rho_{{k}}}}{H}$ and $\gamma={\color{red}{{r}}}{x}^{{n}}-{\sum_{{{k}={0}}}^{{{n}-{1}}}}{\color{red}{\rho_{{k}}}}{x}^{{k}}$

As explained in the review, $\text{(1)}$ and $\text{(2)}$ mostly cancel each other out. Specifically, $\text{(1)}$ will leave behind the commitment ${\color{red}{{C}'_{{l}}}}={0}{G}+{\color{red}{{r}}}{H}$ that we were proving inclusion within the anonymity set of, while $\text{(2)}$ leaves the blinding factors ${\color{red}{\rho_{{k}}}}{H}$.

The same principle still applies for the generalized protocol for double-blinded commitments where ${\color{red}{{C}'_{{l}}}}={0}{G}_{{1}}+{\color{red}{{v}}}{G}_{{2}}+{\color{red}{{r}}}{H}$:

Looking at ${\left({2}\right)}$ more closely, we can see that the addition of the new ${\color{blue}{{E}_{{k}}}}$ commitments results in something very similar to the old ${D}_{{k}}$, with the difference that it will leave behind blinding factors for both ${G}_{{2}}$ (for ${v}$) and ${H}$ (for ${r}$).

Therefore, we can see that thanks to these changes the protocol indeed works for double-blinded commitments:

Balance Proof

For Transparent Output

A yet unresolved problem is verifying the sum of coin amounts that each commitment being spent as transaction input is carrying - while not having the actual commitment but only an inclusion proof demonstrating that said commitment was indeed minted and added to the pool of valid vouchers.

Since the inclusion proof carries (blinded) information about the commitment value ${v}$, we can make use of the OOOMP's transcript to extract a commitment ${C}{''}_{{l}}$, which is basically ${C}'_{{l}}$ with a modified blinding factor:

If we now want to verify whether the commitment being redeemed carries the expected coin amount ${v}$, we can subtract ${v}{x}^{{n}}{G}_{{2}}$ from it and have the user prove that he is able to open the resulting commitment ${\left({\color{red}{{r}}}{x}^{{n}}+{\sum_{{{k}={0}}}^{{{n}-{1}}}}{x}^{{k}}{\color{red}{\rho_{{k}}}}\right)}{H}$. The way Lelantus handles this is by treating it as a public key and having the user sign the transaction with ${\color{red}{{r}}}{x}^{{n}}+{\sum_{{{k}={0}}}^{{{n}-{1}}}}{x}^{{k}}{\color{red}{\rho_{{k}}}}$ as the private key.

If we have multiple private coin transaction inputs, and therefore multiple OOOMPs for each, we can simply sum all of the commitments ${C}{''}_{{l}}$ and subtract the overall expected value from it to obtain the "public key":

Doing this requires all One-Out-Of-Many proofs to share a common challenge value ${x}$ (ie. executing them in parallel). Furthermore, in regards to this challenge being derived from committed values (ie. Fiat-Shamir), those values should not only include those of all inclusion proof commitments, but also all of the output coin commitments and their range proofs.

For Private Coin Output

So far we're able to prove that the sum of private inputs is equal to the sum of public outputs. But for a partial spend or split operation we need to check equality against coin commitments that were specified as transaction outputs.

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

The intuitive solution would be to simply sum the output commitments ${C}$ and subtract them from the sum of blinded input commitments ${C}{''}_{{l}}$ derived from the OOOMP transcript.

Let's look at the simplest case where we have a single coin commitment being spent as input and a single new coin commitment being minted as output:

If the values ${v}$ of inputs and outputs are truly equal then they should cancel out leaving a commitment of the form ${a}{G}_{{1}}+{b}{H}$. The balance proof can therefore be a simple generalized Schnorr Proof showing that the user is able to open this commitment without the use of the ${G}_{{2}}$ generator (ie. with ${v}={0}$).

ABDK's Critical Bug

You might have been wondering why the transaction's private output coins should be committed to as part of the inclusion proof for input coins. The reason is a critical issue identified by ABDK Consulting (opens in a new tab) during an audit of the Lelantus Protocol's cryptography.

In the generalized OOOMP, commitments ${E}_{{k}}$ and ${D}_{{k}}$ are summed as part of the proof's verification. The core of the exploit stems from the fact that these commitments are simply assumed to be correctly formed, but they can be arbitrarily modified as long as their sum remains valid.

For example, we can instead commit to ${E}'_{{k}}$ and ${D}'_{{k}}$ which contain a coin amount $\dot{{v}}$:

This is completely legal since ${E}'_{{k}}+{D}'_{{k}}={E}_{{k}}+{D}_{{k}}$ causes the inclusion proof to remain valid. The balance proof however only makes use of ${E}'_{{k}}$ where this modification can now be exploited: Based on the One-Out-Of-Many Proof's transcript the attacker constructs an output coin of the form ${C}={s}{G}_{{1}}+{\left({v}{\color{blue}{+\dot{{v}}\cdot{x}^{{-{n}}}}}\right)}{G}_{{2}}+{r}{H}$ then the Balance Proof will look like

Thanks to knowledge of challenge ${x}$ we can compute the inverse ${x}^{{-{n}}}$ for the output commitment ${C}$'s construction. With that, our injected value $\dot{{v}}$ cancels out and the balance proof remains valid. This allows us to illegally obtain a new voucher worth ${v}{\color{blue}{+\dot{{v}}\cdot{x}^{{-{n}}}}}$ coins. But if we're required to commit to the output coins before we obtain ${x}$ we will no longer be able to exploit this.

Generalized Bulletproofs

In the article about Bulletproof Range Proofs, we saw how we can prove that a value ${v}$ within a Pedersen Commitment of the form ${v}{G}+{r}{H}$ is within a specified range ${\left[{0};{2}^{{\mathbf{{{n}}}}}-{1}\right]}$. Deconstructing the scheme into multiple parts, we ended up with a (1) Zero-Knowledge Inner Product Proof, a (2) Recursive Inner Product Argument, and a (3) Range Constraint Circuit.

The ${\color{blue}{\text{changes}}}$ required for generalizing Bulletproofs to work with double-blinded commitments only affect (1) the Zero-Knowledge Proof. For this, remember that we're trying to show that the inner product of two vectors $<\vec{{\mathbf{{{a}}}}},\vec{{\mathbf{{{b}}}}}>$ results in a value ${v}$ hidden within a commitment ${C}$.

The vectors are separately committed to in

where $\vec{{\mathbf{{{G}}}}}$ and $\vec{{\mathbf{{{H}}}}}$ are vectors of generators ${\mathbf{{{G}}}}_{{i}}$, ${\mathbf{{{H}}}}_{{i}}$ with unknown logarithmic relationship. Assuming a simple case of two-dimensional vectors (${\mathbf{{{n}}}}={2}$) we can expand this to:

To achieve zero knowledge, we further need random vectors $\vec{{\mathbf{{{d}}}}}$ and $\vec{{\mathbf{{{e}}}}}$, chosen and committed by the prover as:

The updated protocol has the following structure:

Under the assumption that the original protocol was correct, we can demonstrate that the protocol remains correct after the changes with a few substitutions and rearrangements:

${\color{blue}{\overbrace{{{\left({s}+{s}_{{{t}{1}}}{x}+{s}_{{{t}{2}}}{x}^{{2}}\right)}}}^{{{r}_{{1}}}}{G}_{{1}}+}}\cancel{{\gamma{G}_{{2}}}}+\cancel{{{r}_{{2}}{H}}}\ \text{ }\ {\overset{{?}}{{=}}}\ \text{ }\ \overbrace{{{\left({\color{blue}{{s}{G}_{{1}}+}}\cancel{{{v}{G}_{{2}}}}+\cancel{{{r}_{{v}}{H}}}\right)}}}^{{{C}}}+{x}\overbrace{{{\left({\color{blue}{{s}_{{{t}{1}}}{G}_{{1}}+}}\cancel{{{\color{red}{{t}_{{1}}}}{G}_{{2}}}}+\cancel{{{\color{red}{{r}_{{{t}{1}}}}}{H}}}\right)}}}^{{{T}_{{1}}}}+{x}^{{2}}\overbrace{{{\left({\color{blue}{{s}_{{{t}{2}}}{G}_{{1}}+}}\cancel{{{\color{red}{{t}_{{2}}}}}}{G}_{{2}}+\cancel{{{\color{red}{{r}_{{{t}{2}}}}}{H}}}\right)}}}^{{{T}_{{2}}}}$

${\color{blue}{{\left({s}+{s}_{{{t}{1}}}{x}+{s}_{{{t}{2}}}{x}^{{2}}\right)}{G}_{{1}}}}\ \text{ }\ {\overset{{✓}}{{=}}}\ \text{ }\ {\left({\color{blue}{{s}{G}_{{1}}}}\right)}+{x}{\left({\color{blue}{{s}_{{{t}{1}}}{G}_{{1}}}}\right)}+{x}^{{2}}{\left({\color{blue}{{s}_{{{t}{2}}}{G}_{{1}}}}\right)}$

The Code

We've seen that the main components of the Lelantus Protocol are One-Out-Of-Many Proofs and Bulletproof Range Proofs. Reviewing how these were implemented in detail would go beyond the scope of this article, instead, we'll be looking at some implementational details that are interesting from a security point of view.

Sliding Anonymity Sets

You might remember the zerocoin_params.h file from previous articles that defined various constants around the Zerocoin and Sigma protocol. Around the time of the Lelantus Upgrade (v0.14.1.2) the Zcoin project renamed itself to Firo, and so did this file.

// Number of coins per id in spend v1/v1.5
#define ZC_SPEND_V1_COINSPERID			10
// Number of coins per id in spend v2.0
#define ZC_SPEND_V2_COINSPERID			10000
// limit of coins number per id in spend v3.0
#define ZC_SPEND_V3_COINSPERID_LIMIT    16000
 
// limit of coins number per id in Lelantus
#define ZC_LELANTUS_MAX_MINT_NUM    65000
#define ZC_LELANTUS_SET_START_SIZE  16000

When Zcoin was first released, RSA Accumulators were used for storing coin commitments. Restrictions were needed on how many coins would be added to the same Accumulator since it would become increasingly easier to forge inclusion proofs with an increasing amount of accumulated commitments. At the beginning, the maximum amount of coins added to an accumulator was restricted to only 10 commitments and was later raised to 10k. With the Sigma Upgrade and OOOMP replacing RSA Accumulators, the maximum anonymity set size was further increased to 16k. The limit was no longer in place for security reasons but simply because the work necessary for generating and verifying OOOMPs increases linearly with the set size. Finally, with the Lelantus release, the limit was increased to 65k.

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

But more interestingly, Lelantus also changed how a new set would be initialized when the current one has reached its limit. Before, the sets would simply start from the beginning, meaning they'd empty and users would do best to wait a while for the anonymity set to grow before they redeem their funds from it. With Lelantus anonymity sets overlap, specifically, once the current set reaches its limit a new set would be started including the last 16k commitments from the current set. So each anonymity set in Firo's Lelantus implementation shares 16k commitments with the previous and the next set.

Whenever a user wants to redeem one of the coin commitments from an anonymity set, they have to provide a groupId (anonymity set identifier) together with the inclusion proof. This means that, if the commitment being redeemed is in a shared region of the anonymity set, the wallet will decide which set it'll prove inclusion for. So for a new set to start with 16k commitments in truth, those wallets must ensure that the identifier of the new set is used, instead of the one that the commitment was actually minted in.

But that wasn't actually the case until Firo's v0.14.11.2 release where the following lines of code were added to the wallet with PR1199 (opens in a new tab):

// Check if the coin is at overlapping parts of sets, use next set for proof creation if it is also in next set.
lelantus::CLelantusState::LelantusCoinGroupInfo nextCoinGroupInfo;
if (state->GetLatestCoinID() > groupId && state->GetCoinGroupInfo(groupId + 1, nextCoinGroupInfo)) {
    if (nextCoinGroupInfo.firstBlock->nHeight <= mintHeight)
        groupId += 1;
}

Trail of Bits' Audit

Firo's Lelantus Upgrade code was audited (ie. security reviewed) by Trail of Bits (opens in a new tab) who found one high (opens in a new tab) and one medium (opens in a new tab) issue that we'll be taking a closer look at here. It's unsurprising that both were found in the implementation of the Range Proof scheme, since this required implementing new and complex additions to the codebase.

Negative Value issue

Output coins come with a Bulletproof Range Proof that proves that their value ${v}$ is within an expected range. Normally, these proofs offer an upper boundary of a power of two (2^n) resulting in a range check of [0, 2^n - 1]. Firo however wants to check a custom range that isn't necessarily bounded by a power of two: [0, nMaxValueLelantusMint].

The intention was to achieve this by adding the difference between 2^n and nMaxValueLelantusMint to the commitment. Therefore, if the commitment's value was larger than nMaxValueLelantusMint it would end up being larger than 2^n - 1.

The problem with this logic is that, since scalars are operating within a field (ie. scalars are modulo the order of the curve), adding the difference can make the commitment's value overflow and therefore appear to be within the range. That would mean that "negative" values (ie. values that will cause wrapping when summed with other values) will pass verification because the verification itself will make it overflow.

A simple solution to this problem is checking both ranges: Checking [0, 2^n] with the unmodified coin commitment to ensure it's not already a negative number. Then adding the difference and checking [0, nMaxValueLelantusMint] to ensure that the value is below Firo's custom upper bound.

Fiat-Shamir issue

At the very beginning of a Bulletproof Range Proof we commit to two input vectors with ${W}$ and to two random vectors with ${S}$. For constructing the range constraint circuit using random linear combination, we need two independent challenges ${y}$ and ${z}$.

The code attempted to achieve this basically like this:

Where assuming ${S}\ne{W}$, this would result in ${y}\ne{z}$. But that assumption is exactly the problem here: When both vector commitments are the same, the resulting hashes (even in alternating order) will also be the same.

The solution was simply adding ${y}$ as parameter to ${z}$'s generation:

The Lelantus Attack

In February 2021 (opens in a new tab) an attacker managed to forge Lelantus proofs. The Firo team noticed abnormal chain activity and emergency-disabled Lelantus with the power of a killswitch that had been temporarily added with the Lelantus Upgrade to handle exact cases like this. A blacklist was implemented to lock the attacker's illicitly created funds.

The exploited issue was described as an implementation error that allowed forging a coin spend, but no technical description was published and the details have mostly been forgotten at this point. The update resolving the issue (PR1012 (opens in a new tab)) was large and came with many changes that intended to additionally harden the protocol. I wasn't able to tell which of these changes specifically ended up fixing the issue that was exploited, though roughly discussing what has changed may be helpful either way.

Most of the changes are related to Fiat-Shamir challenge generation of the Zero-Knowledge proofs. The challenges (ie. a hash based on committed data) are now based on more data (eg. the anonymity set contents now influence the OOOMP's challenge value). In fact, it looks like everything that could possibly be committed to now is. Also, simple domain_separators (ie. string prefixes to comitted data) were added to ensure transcript information can't be reused across proofs or versions.

The challenge hashing itself has also changed: Before a simple sha256 hash was generated, now messages are double-hashed (ie. sha256(sha256(m))). This prevents "length extension" attacks that the sha256 algorithm is vulnerable to. This type of attack exploits the padding space to append more data to the hashed message (ie. you can generate sha256(secret + attacker_controlled) from the result of sha256(secret) alone).

Finally, an additional Schnorr proof was added to the protocol, proving that ${E}_{{k}}$ is well-formed. And the inner product proofs of the Bulletproof Range Proof no longer use separate transcripts.

Conclusion

With the introduction of the Lelantus protocol into Firo, wallets were adjusted and encouraged to move towards a more "private by default" model. Before, Zcoin's privacy features were much more "Opt-In" for the simple reason that the RSA Accumulator inclusion proofs were so large that their use strained the system.

While Lelantus was a great improvement over how Zcoin originally worked, its biggest disadvantage remained its lack of proper stealth addresses. So far, one could anonymize their funds with the protocol, but to actually send them to another person you still had to use the transparant ledger. This is the main reason why Lelantus Spark was created.

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

In Spark users now have both transparent and true stealth addresses. As long as the user only uses their stealth address, "private by default" is basically enforced. With this system in place it would be possible to completely remove transparent address use from Firo, although there are arguments for their usefulness (eg. for centralized exchanges).

Beyond Firo, the work in creating Lelantus revived interest in One-Out-Of-Many Groth-Bootle Proofs inspiring various spin-offs such as Lelantus-MW/CLA (Beam), Anonymous Zether (Bunz et al), Triptych and Arcturus (Monero Research Labs).

Appendix

Direct Anonymous Payments

While the Lelantus Protocol basically adds a native mixer with a large anonymity set and arbitrary amounts, actual transfers between users still happen on the transparent ledger. Users could theoretically exchange secret voucher information with each other, but that requires trusting the person you're receiving it from to not redeem it before you're able to. To improve this, the initial design^[9] of Lelantus proposed to extend the protocol with a simple version of Direct Anonymous Payments.

You might remember how the original Zerocoin Protocol used a random number for the serial ${s}$ of the coin commitment. This turned out to be a protocol flaw^[25] as an attacker could observe a serial number from a pending redemption transaction in the memory pool and frontrun it with their own mint-redeem transactions to mark the serial as used. While this doesn't allow an attacker to steal other users' funds, it did present a potentially dangerous denial of service vector.

To fix this, spending keys were introduced: To mint a voucher, instead of generating the serial directly from randomness, one would create a random witness ${q}$. The actual serial number used for the coin commitment would be derived from the public key ${Q}={q}{G}$ by hashing it: ${s}=\text{hash}{\left({Q}\right)}$. To redeem a voucher with the serial number ${s}$, one now has to additionally sign the transaction with the spending key ${q}$. Since such a valid signature could only have been generated with knowledge of the spending key, it proves that the signer is authenticated to redeem the voucher with the given serial.

Simple Direct Anonymous Payments that don't require any significant changes to the protocol, can be implemented by ensuring the spending key is computed in such a manner that the sender is not able to redeem the voucher before the receiver. In short: Instead of the sender, we have the receiver come up with the spending key ${Q}={q}{G}$ and share ${Q}$ with the sender. To mint a coin commitment, the sender determines a serial number from ${s}=\text{hash}{\left({y}{Q}\right)}$ with ${y}$ being a randomly sampled scalar by the sender. After the sender privately shared ${\left({q},{v},{r}\right)}$ with the recipient, the voucher can be spent with knowledge of ${q}{w}$ which only the receiver has.

While this prevents the sender frontrunning the receiver's redemption, it's still recommended that the receiver should spend this commitment for another because the sender has knowledge of the serial number ${s}$ which allows them to observe when the voucher is being redeemed. The traceability, the necessity of additional transactions, and the possibility of leaking timing information in the process made this approach less than optimal for practical use.

Untraceable Direct Anonymous Payments

A follow-up whitepaper^[24] proposed improved Untraceable Direct Anonymous Payments by introducing one-time shielded layer addresses. Similar to before, the recipient generates a private spending key ${q}$ but this time ${Q}$ will be a blinded commitment ${Q}={q}{G}_{{1}}+{r}_{{q}}{H}$. Additionally, the sender would require a Schnorr proof $\pi_{{Q}}$ on ${Q}$ demonstrating its representation with respect to the fixed public generators ${G}_{{1}}$ and ${H}$ (we can't allow this to include the generator ${G}_{{2}}$ used for the coin value).