New BSIP 0052: Untraceability solutions for Stealth transactions

[christophersanborn]

(From: https://github.com/Agorise/bsips/blob/master/bsip-1202.md)

BSIP: 1202 (unassigned)
Title: Untraceability solutions for Stealth transactions
Authors: Christopher J. Sanborn
Status: Draft
Type: Protocol
Created: 2018-01-29
Discussion: <url>

Abstract

Confidential Transactions (CT) [1], (as implemented by Phase I of Stealth development), solves the linkability and value-hiding problems, but not the traceability problem. CT transfers are traceable on the blockchain, meaning that for any given transaction, a history of prior transactions can be determined. If the set of antecedents is large, then there is a great degree of plausible-deniability regarding the origins of the hidden assets. However, if the set is small, it is possible to determine with increasing probability where the assets originated from. A solution to this is to “mix” transaction inputs with unrelated users so as to increase the traceability set. Some privacy blockchains rely on a mechanical mixing or “tumbling” process to increase the traceability set, however this approach has drawbacks. Monero has a very clever scheme of using ring signatures to automatically and randomly mix in unrelated inputs on every transaction, guaranteeing that even newly blinded funds are mixed with with inputs having a rich history. It is proposed, as a component of Stealth development Phase II, to implement a similar mechanism for BitShares.

Motivation

Stealth can be thought of as a constellation of privacy-preserving features implemented on (or planned for) the BitShares blockchain. "Privacy" here is a set of specific goals:

• Untraceability
• Unlinkability
• Value/Asset hiding
• Anonymity

Although Confidential Transactions (CT) provides good solutions to unlinkability and value hiding, (which together help but do not fully solve anonymity), the transactions currently supported on the network are fully traceable. This means it is possible generate a history all prior transactions leading up to a particular transaction output, including a set of originating transactions wherein public balances were blinded. For outputs which are "close" to their originating transactions, it may be possible possible to identify a small set of non-anonymous originating actors, and to make estimates of the possible maximum value amount of an output (by assuming it can be no larger than the sum of all originating transactions in its history).

What we seek is a method to make it unknowable which prior transaction outputs were consumed in the generation of a new transaction output. Although it seems a tall order (how can a node validate that a sum of inputs balances a set of outputs when it is unknown which inputs are involved?), a solution actually comes in the form of a ring signature protocol developed for the Monero project.

The ring signature strategy in Monero has gone through two major developmental stages. In the first stage, transaction amounts were not blinded (although pseudo-blinding was achieved by composing value transfers from an aggregate of round-number individual transactions). In the second stage, the ring signature authorization protocol was combined with Confidential Transactions to form the RingCT protocol [2], in which transfers are both value-blinded and untraceable. Since BitShares already implements CT, the adoption of RingCT into BitShares Stealth operations can be seen as an improvement upon an existing feature.

Rationale

Although BitShares is an account-based blockchain, in which value-transfer operations are a simple transfer of balance from one account to another, Stealth operations on the BitShares blockchain instead follow a UTXO model. Stealth transactions produce "transaction outputs" (TXOs) which represent individual balance amounts under the control of someone possessing the appropriate secret key. These TXOs are "unspent" (UTXOs) until they are involved in a downstream transaction, at which point they are considered destroyed and no longer spendable. (To partially spend a UTXO, a transaction consuming it would need to produce two outputs: one to the intended recipient, and one back to the sender as "change.")

A transaction in a UTXO-based blockchain is simply a list of inputs (UTXOs which will be destroyed) and a list of outputs (newly-generated UTXOs). Validating such a transaction involves confirming that the value sum of inputs equals the value sum of outputs plus fees, and that appropriate authorization is provided for all inputs.

Because the list of inputs is part of the transaction, all UTXOs have a traceable history.

Ring signatures are a signature scheme in which, for a given set of credentials, a signature is provided proving that at least one of the credentials authorized the transaction, but it cannot be determined by a third party which credential it was that signed it. Thus ring signatures provide plausible deniability. All involved credentialed parties can mutually point fingers at each other, saying, "it wasn't me."

Ring signatures can provide untraceability in Stealth transactions in the following way: For a given transaction, a set of inputs is collected which is larger than the set needed to cover the the intended transaction outputs. The additional inputs should include inputs for which the spender does not have authorizaton to spend. A signature is provided proving that at minimum enough inputs are authorized to cover the outputs, however an external observer cannot determine which inputs are thereby consumed. Double-spending of inputs is prevented by the provision of a "key image" for each actually-spent input. A key image is a piece of data that uniquly derives from the consumed input, but which cannot be matched to it. A subsequent spend of the same input would produce the same key image, alerting the network to the attempt at a double spend. Now, the set of inputs to any transaction includes not only the actually-consumed inputs, but also a large set of "red herring" inputs, which achieve two important aims for untraceability:

1. A degree of plausible-deniability for the authorizer of any individual transaction, and
2. An enormously larger set of prior transactions that form the "history" of the transaction, implicating a much larger set of originating transactions than is actually involved in the true history of the transaction.

It should be noted that one drowback of this scheme is that it is no longer possible to determine which UTXOs are spent vs. unspent, and this has implications for database pruning. However, the Monero chain has been functioning with this limitation for several years now without hitting a performance bottleneck. Additionally, the Monero team has projected that performance growth will keep pace with database size, even absent pruning of spent TXOs. (CITE). (A review of this projection and discussion of its implication for the BitShares chain is in the Discussion section.)

Specifications

(Detailed description of RingCT with annotations for how it would be adapted to BitShares Stealth transactions.) [2]

Discussion

Overview of alternative untraceability solutions

(Compare/contrast with other schemes for providing untraceability, including ZeroCoin accumulators, master-node facilitated tumbling, MimbleWimble, etc.)

Mimblewimble

• PRO: Supports a sort of automated, non-interactive aggregate signature scheme (end result similar to CoinJoin), facilitating untraceability at the blockchain level (although not necessarily at the network-snooping level).
• CON: Requires communication between sender and recipient.
• [Jed2016], [PoelMW]

CoinJoin, CoinSwap, etc.

• In [1], Maxwell states "[CT is] compatible with CoinJoin and CoinSwap, allowing for transaction graph privacy as well while simultaneously fixing the most severe limitation of these approaches to privacy (that transaction amounts compromise their privacy)."

  • ((This still needs to be researched by this author but I believe these protocols involve mixing with contemporaneous participants, many of whom may be nefarious actors. RingCT allows mixing with historical transactions, and reuse of historical transactions, greatly broadening the set of available mix-in transactions. TODO: confirm this disadvantage.))

• Dash (http://dash.org) uses a system of "master nodes" to coordinate an opt-in mechanism of "pre-washing" coins via several rounds of mixing with other participants where each round of washing is a CoinJoin-like process. (https://dashpay.atlassian.net/wiki/spaces/DOC/pages/1146924/PrivateSend)

Accumulator Schemes, e.g. ZeroCoin

• Spending a coin into the accumulator produces receipt that can be used to withdraw a coin from the accumulator later. The withdraw operation cannot be linked to the orignal deposit operation. Untraceability os provided by the fact that the "plausible deniability set" of users who might be responsible for the coin is the set of all users who have deposited coins into the accumulators. This can be a very large set.
  • Pros:
    • Large deniability set
    • Conceptully simple mechanism
    • Possible to audit supply
  • Cons:
    • Depends on a trusted setup, which, if compromised, could allow theft or counterfeit of coins
      • (NOTE: Announcement by ZCoin team of an upgrade that eliminates need for trusted setup) (CITE)
      • [Yap2017], [GrothSigma]
    • Mechanism to transfer coins between users while the coins are inside the accumulator is unclear/unknown (to this author) or impossible. Thus an accumulator may be a good way to wash or hide your own funds, but is not a good solution for creating a balance that one easily use in cash-like user-to-user transactions.

Scaling challenges in a Ring-Sig scheme

(Discussion of the implications of not pruning spent TXOs.)

Summary for Shareholders

Copyright

This document is placed in the public domain.

See Also

[1] Confidential Transactions (Greg Maxwell) - https://people.xiph.org/~greg/confidential_values.txt

[2] Ring Confidential Transactions (Shen Noether) - https://eprint.iacr.org/2015/1098

[Jed2016] Mimblewimble (Tom Elvis Jedusor) - https://scalingbitcoin.org/papers/mimblewimble.txt

[Poel2016MW] Mimblewimble (Andrew Poelstra) - https://download.wpsoftware.net/bitcoin/wizardry/mimblewimble.pdf

[Yap2017] Zcoin moving beyond trusted setup in Zerocoin (Reuben Yap) - https://zcoin.io/zcoin-moving-beyond-trusted-setup-in-zerocoin/

[GrothSigma] - One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin (Jens Groth and Markulf Kohlweiss) - https://eprint.iacr.org/2014/764.pdf

[pmconrad]

IMO the inability to prune TXOs makes this a no-go. Curious to see the Discussion.

[christophersanborn]

IMO the inability to prune TXOs makes this a no-go. Curious to see the Discussion.

It’s not an insignificant drawback. Although imho, the cost incurred vs. the privacy provided is not out of proportion. I say this considering that Monero has been operating with this same drawback and despite plenty of on-chain activity is not anticipating any scaling problems due to it.

API nodes won’t want to prune this data anyway, as it’ll be needed to provide wallet history to users. Witness-only nodes, of course, would benefit from being able to prune.

Also, the community will of course want to ensure that the fee structure is appropriate for transactions that will incur an en-perpetuity storage burden. I think a reasonable balance is achievable there.

All this notwithstanding, though, I do think that MimbleWimble needs to be kept on the table as a contending untraceability solution. If the communication problem can be solved, then MW offers some significant advantages over RingCT/CA, not the least of which is prunability.

[abitmore]

Draft merged.