Sending Cryptocurrencies Confidentially: Ring Signature, Homomorphic Commitment, and Zero-Knowledge Range Proofs

Introduction: A Platform of Decentralized Privacy Coins ▸

Shielding Cryptocurrencies: Turning Any Cryptocurrency Into a Privacy Coin ▸

Trustless Custodians: A Decentralized Approach to Cryptocurrency Custodianship ▸

Sending Cryptocurrencies Confidentially ▾

Once public coins are shielded, they can be confidentially sent, received, stored and traded as privacy coins. A custodian may keep a record of how many privacy coins have been minted but will have no knowledge of how these privacy coins are used afterward. Every privacy coin transaction is confidential and untraceable, even by custodians and validators. Incognito uses several cryptographic primitives, such as linkable ring signature scheme, homomorphic commitment scheme, and zero-knowledge range proofs, to shield sending addresses, receiving addresses, and transacted amounts.

Fungibility: The Basis of Monetary Privacy

All privacy coins issued in the Incognito network are fungible – one of the basic requirements of money. One unit of currency must be identical and interchangeable with another.

As their history can be traced, most cryptocurrencies, including BTC and ETH, are not fungible. If BTC units become associated with illegal or illicit activities at any point in their history, they could be blacklisted as tainted bitcoins. Anyone could refuse to accept them, and holders might be forced to sell them for less.

A dollar bill, by contrast, is fungible. One is easily interchangeable with another and does not lose value based on how it was previously used. Privacy coins issued on Incognito share this important quality.

Ring Signatures: Shielding Sending Addresses

A ring signature scheme allows a member of a group to sign a message on behalf of the group without revealing the signer’s identity [Chaum and Van Heyst, 1991; Fujisaki and Suzuki, 2007; Van Saberhagen, 2013]. Signer anonymity is preserved by giving each member of the group equal chances of being the true signer. QUEST.

Figure 1. The identity of the signer is obscured. For example, if you encounter a ring signature with the public keys of Annie, Bob, John, and Peter, you will be able to claim that one of these users is the signer, but not be able to pinpoint him or her.

Group formation is spontaneous. There is no group manager to reveal the identity of the true signer. Due to these properties, we call the group an ad hoc group or a ring. The signer can form a group by simply collecting the public keys of other group members. These diversion group members, often called decoys or mixins, are pulled from historical transactions. The unified signature provides anonymity to the signer.

In Incognito, a ring signature is used to authorize the spending of an Unspent Transaction Output [Nakamoto, 2008], or “UTXO” without revealing the spender’s identity. The ring consists of the actual UTXO being spent as well as its decoys, which are various random outputs from historical transactions. The actual UTXO and its decoys collectively make up the inputs of the transaction. To the public, any of these inputs could equally be the actual output being spent.

Figure 2. Visualization of ring signature. The notion of ring signature was first proposed as a way of whistleblowing [Rivest et al., 2001]

Since there is no way to verify which UTXO is being spent, we may have a double-spending problem [Finney, 1993]. To solve this, we implemented a variant of ring signature called Linkable Ring Signature [Liu et al., 2004], in which an additional property is added: linkability. With linkability, any signature issued under the same public key, whether in signing the same message or a different message, has a unique identifier – a serial number. With serial numbers in place, anyone can verify whether two signatures have been issued by the same group member without learning who the signer is. A serial number is derived from each UTXO being spent and is part of every ring signature. A list of all used serial numbers is stored permanently as part of the transaction data so that any new ring signature that attempts to reuse an existing serial number is automatically rejected for double-spending.

Stealth Addresses: Shielding Receiving Addresses

In a typical cryptonetwork like Bitcoin or Ethereum, a public address is all that is needed for anyone to view incoming and outgoing transactions associated with that address [Reid and Harrigan, 2013]. These transactions are public and can be easily linked together to infer total balances and spending patterns.

To avoid transaction linking, Incognito automatically creates multiple one-time public keys – one for each incoming transaction. One-time public keys, also known as stealth addresses, can be thought of as one-time deposit boxes. Only the receiver can open the box to see what is inside and spend it.

Figure 3. Creating multiple unique one-time keys

Stealth addresses are based on the Diffie-Hellman key exchange protocol [Diffie and Hellman, 1976], a cryptographic method that allows two users to create a shared secret even in the presence of an adversary who can observe all communications between them.

An Incognito address consists of a public view key and a public spend key. A public spend key has a corresponding private spend key, which is used to authorize transactions. Similarly, a public view key has a corresponding private view key, which is used to receive payments.

When Alice wants to send privacy coins to Bob, Alice uses Bob’s public view key and public spend key, along with some fresh randomness, to derive a one-time public key for Bob’s new UTXO, in a way such that only Bob can compute the one-time private key corresponding to this one-time public key.

Bob uses his private view key to recognize the UTXO being sent to him by scanning all incoming transactions. Once the UTXO is found, Bob is able to compute the one-time private key that corresponds to the one-time public key. Bob can spend the UTXO with his private spend key.

Figure 4. Stealth addresses

The transaction data is on the Incognito public ledger. Anyone can see that a new transaction has occurred, but cannot link the one-time public key in the transaction to Bob. If Bob were a merchant, for example, no one would be able to determine that he and Alice are doing business together.

Confidential Transactions: Shielding Transacted Amounts

Confidential Transactions shield the transacted amounts [Maxwell, 2015]. Anyone can see that privacy coins are transacted on the Incognito public ledger, but cannot see the exact amounts.

Figure 5. Confidential transaction amount

The basic idea is to commit the input and output amounts of a transaction as Pedersen commitments [Pedersen, 1991]. A commitment is formed by the value itself and a randomness called a blinding factor, which prevents others from guessing the value. The value and the blinding factor can later be revealed by the committer so that everyone can use them to verify that the commitment was well-formed.

Figure 6. Commitments are equipped with zero-knowledge range proofs to prove their validity

The first problem with this approach is that validators can no longer verify the transaction, specifically the sum of inputs against outputs.

To solve this, we included a zero-knowledge proof of the validity of the confidential transaction in every transaction. Zero-knowledge proofs [Goldreich et al., 1991] enable the prover to demonstrate his knowledge of the truth of a particular statement without revealing anything beyond the fact that it is true.

Due to a cryptographic property called homomorphic [Gentry and Boneh, 2009], or malleable, all input commitments of a transaction can be added up to a single input commitment. Similarly, all output commitments can be added up to a single output commitment. The sum of commitments is a commitment to the sum of underlying values, with the blinding factor as the sum of blinding factors in individual commitments.

It turns out that a commitment to zero is a valid public key, of which the corresponding private key is the blinding factor. A sender now signs the difference between these two commitments, which is a commitment to zero, to prove that the balance is preserved. By including this commitment as a ring member in the ring signature, the sender can prove the claim by signing the transaction with this blinding factor as one of the private spend keys.

The second problem with this approach is that an attacker could create money out of thin air and inflate a privacy coin supply by committing to negative amounts.

To solve this, we associated each output commitment with a range proof [Boudot, 2000; Morais et al., 2019]. A range proof proves that the output amounts are positive, in the interval [0, 264), without revealing the actual amounts. Validators now can verify that the transaction is legitimate without knowing the actual amounts being transferred.

To implement range proofs, we employed Bulletproofs [Bunz et al., 2018]. Bulletproofs are short non-interactive zero-knowledge proofs designed to enable efficient confidential transactions, with no trusted setup required. Bulletproofs reduce the size of the old range proof from ~5KB to only 700 bytes. Bulletproofs also supports aggregation; combining several range proofs would only increase the size by several hundred bytes.

Privacy at Scale with Dynamic Sharding ▸

Consensus: A Combination of iPoS, Multiview-pBFT, and BLS ▸

Multiview PBFT ▸

Incognito Software Stack: Navigating the Incognito Source Code ▸

Incognito Performance ▸

Network Incentive: Privacy (PRV) ▸

User-Created Privacy Coins ▸

Use Cases: Privacy Stablecoins, Privacy DEX, Confidential Crypto Payroll, and more ▸

Future Work: Smart Contracts, Confidential Assets, Confidential IP, and more ▸

Conclusions, Acknowledgments, and References ▸

28 Likes

I suppose the public view key of Bob would be Q that Bob sends to Alice (and d would be Bob’s private view key), and the one time public key for Bob would be P that Alice sends to Bob. Using P, Q and d, Bob can compute c and 1{Q+(cA)}, thus identifying the respective transaction.

What is the assumption of the communication channel between Alice and Bob?
It seems that the solution is circular, if you can avoid the man-in-the-middle attack of the DH protocol, e.g. using a strong authenticated channel between Alice and Bob, even if it is unencrypted, can’t you just use it to communicate directly the transaction id to Bob?

2 Likes

Because Alice wants to send PRV to Bob, she must know the payment address of Bob.

Bob can publish his payment address somewhere.

Alice just needs to directly communicate with Bob via public channels such as chat, video call to confirm with Bob before she makes a transaction.

1 Like

So it means that there is a public record (e.g. if Bob is a merchant, there would be a website) that links Bob to the “stealth” payment address?

Yeah, that is a public record. However, Alice only knows the payment address, not stealth address. From payment address, Alice will generate a stealth address (one-time address) and then send PRV or pToken to this address. :slight_smile:

In other words, amounts transacted in individual transactions on Incognito are not identifiable unless you are the sender/receiver, but the total amounts transacted in each ringed transaction would be publicly identifiable.

Am I understanding it correctly?

3 Likes

Hey @Globallager,

To hide the identity of the sender in a transaction, we use ring signature scheme. Roughly, in each transaction we have a ring (or multiple rings if multiple inputs are used), only one input is the sender’s input and the rest are decoys.

You can read more from Monero’s document here.

Thanks for your question :slight_smile: .

2 Likes

Thanks for the reply as well!

So all amounts transacted in all transactions should be shielded, yet why aren’t amounts in pDEX transactions confidential as well?

3 Likes

Hi @Globallager,

Sorry for the late reply! Actually, Incognito uses a decentralized protocol for automated liquidity provision on pDEX (that is similar to UniSwap on Ethereum). In this protocol, the amount in all trade transactions must public, so we cannot hide it.

In privacy version 2, we will hide the sender. Therefore, the real identity of the user (i.e., payment address) will be protected as well.

3 Likes

Hey @Globallager check these two works as well Privacy Version 2 & Confidential asset. We plan to deploy them on mainnet in Q1 next year.

btw, @Globallager are you interesting in contributing in any direction :thinking:?

1 Like

First of all let me thank you guys from incognito for your ground-breaking work to save us all from Big Brother in a possibly cashless society in the future!

However, if you want to reach a wider audience you’ll probably need to improve your communication :wink: Even after having watched most of your Youtube videos it’s still not 100% clear to me how private the Incognito Wallet actually is and what specific steps need to be taken by your users in order to enjoy best possible privacy.

Have I — after investing over an hour or two in your educational material — correctly understood the following:

  1. Just transferring BTC to my Incognito wallet’s BTC address, shielding it to pBTC and unshielding it to BTC back again doesn’t gain me any privacy. For extra privacy I’d need to trade BTC for another crypto currency on pDex or send my pBTC to ANOTHER Incognito wallet user?
  2. Even if I use your Incognito wallet correctly and thus reach maximum possible privacy, my cryptos will still not be 100% anonymous because — unlike e.g. the Samourai wallet — the Incognito wallet doesn’t use IP obfuscation and e.g. connect over Tor, so the real-world cryptos which I’ll eventually get from Incognito wallet will immediate be tied (or can at least be traced back) to my smartphone’s IP address on which the Incognito wallet runs?
  3. Which user data (IP address etc.?) do you collect? Do we still need to trust Incognito to some extent to keep us private like we do need to trust our VPN provider?
  4. How safe are my cryptos in my Incognito wallet? Who has the private keys of my Incognito addresses (shielded and unshielded)? Can hackers or Incognito themselves (theoretically, I do trust you guys) gain access to your users’ funds?

It’s not meant as a criticism, much to the contrary. It’s just open questions which in my view prevent wide adoption of an otherwise brilliant product before they have been addressed, so please address them here :slight_smile:

6 Likes

So incognito uses both ring ct and zk proofs?

Currently, we use the sigma protocol and bulletproofs. In privacy version 2, we will upgrade from sigma protocol to ring ct.

1 Like

Interesting, so that would be scrapping the zk proofs all together or using them together with ringct? I’m a big fan of zero knowledge proofs

Dear Incognito team, regarding “Currently, however, IP addresses are exposed…but work is in progress to hide IP addresses and further improve the privacy of the Incognito network”: can you already tell when this will be implemented and whether using a VPN App on the smartphone that runs your incognito wallet fixes the problem for your users till then, please?

1 Like

Running tor or a VPN fix it on your phone

2 Likes

hey @petr, thanks for the thoughtful questions. These are exactly what we’re trying to solve here. From the protocol perspective, let me answer questions number (1) and (4) first.

(1) - yes, with the current version of both the privacy and interoperability layers, it’s possible to map between an address from a public chain (e.g. Bitcoin) and an Incognito address from a shield. But once the privacy v2 with One-time address support releases, the problem would be gone. And a shield in the Incognito network will be completely anonymous. Also, it’ll also help pDEX a lot in terms of privacy as well as speed.

(4) - No one can have your private keys unless your wallet gets hacked. The transactions are created from the client-side (e.g., Incognito wallet) and it does not need to send a private key to any servers/nodes so Incognito would not be able to access your funds.

For questions number (2) & (3), I guess @binh is the best person for you to discuss with. He’s lead of the Incognito wallet team so I’m pretty sure he did think of the problems sometimes.

4 Likes

hi @petr
thanks for your question.

for question 2,3

As for IP information, when your wallet is connected to the internet, your public ip can be seen on the server. however, the Incognito system doesn’t keep and doesn’t use user’s IP.

you can see more information here: https://incognito.org/t/incognito-wallet-apps-tracking-and-permissions/1915

mostly, these are due to the node device setup. if you don’t utilize this, you can forego most of it. we are working steadily to reduce these.

in the meantime, if you want to conceal your IP, please use VPN or Tor app to connect your phone to the internet.

4 Likes