Topic: Confidential Transactions, Content privacy for Bitcoin transactions - page 3. (Read 14708 times)

No matter how good this gets, the split over block size has caused a rift in BTC users and developers alike, some will be against this just as others fought the raise in block size. This will never get into core, likely we'll have another person threatening a hardfork.

It's unfortunate how things turned out. only way this makes it in  is if a ton of concessions are made or they branch off.

Summing it up, it really does demonstrably add confidentiality right now, and it can be done at this time.  I'm curious to know only what sort of process would be logical to see this evolve into an option for Core (and ultimately other wallets) - I think someone else asked this in the context of the sidechain question as well (bitcoin core development track or be on sidechain)?

(Edit:  I think you answered my question in response to someone else asking the  same thing while I was typing this, basically it sounds like it's unlikely to make it into core in the near term if I understand it properly... it would need some further development and refinement and maybe, more acceptance from core developers?)

Inputs do not have an exponent.  The exponent is a property of the range proof, not of the values themselves. They work by scaling the basis the proof operates over.

Right now elements alpha wallet only lets the exponent be changed by a config file setting.   

This exactly?  No-- but some optimized, mature, and superior version... sometime in the future? I certainly plan to work towards that end. There are other people who work on software in this space which wouldn't support it, however.

Aside, as TierNolan pointed out-- this composes perfectly with coinjoin and coinswap, and the interface is setup to facilitate coinjoin already; in coinjoin the participants need not learn each others values.  And in the case of coinswaps the swap transactions can be made indistinguishable from ordinary payments to a single key due to the switch to schnorr signatures.

Fair enough, but it still works then.  Inputs don't need range proofs.  The coinjoin system can be used to scramble the inputs (as long as they have the right sighash). 

The outputs (plus public fee) can be summed and proved to be equal to the sum of the inputs.  There is an additional proof required that all outputs are positive.  This prevents people spending 1BTC and getting -5BTC and 6 BTC, and then just ignoring the -5BTC output.

I don't understand how that works. CoinJoin works by rearranging input such that the output values remains the same. If the inputs values are unknown, how could that be calculated?


Edit: You can ignore me, it's going to take me a while to wrap my head around this, if I ever manage it. If this protocol does what it says it does, then this is probably the biggest innovation to Bitcoin since.. well.. Ever.

Edit2: Speaking of which, is this going to make it to Bitcoin core or is this expected to remain on a sidechain?

The output "values" are random looking curve points and proofs that they are within range.

You can move them around just like normal coinjoin outputs.  You just have to keep the output value and proof as a single unit.

Two sets of fees can be added together too to give one fee output.

This means that you can do coinjoin without having to have all the outputs the same amount.

Since this hides transaction amounts doesn't this make CoinJoin impossible at the same time?
Attaching transactions between two people or businesses can be a serious breach of privacy even if the actual amounts are unknown.

Since the vast majority of transactions will be <42.94967295 BTC, almost all transactions will have exponent zero. So, transactions with exponent >0 will stand out and be much less anonymous. And the inputs and outputs to coinjoins will need to have the same exponent.
Nothing against it, the space saved is worth the loss of anonymity for very large transactions. But it is probably best to warn people about it so that no one uses confidential transactions incorrectly.
Also, if I have several inputs with different exponents (let's say 0,1 and 2) and I want join them into a single ouput, will the protocol force me to have two outputs (with exp 0 and 2) or will it round down the amount?

No, because it doesn't show up on the network; though sure it's not ideal-- it was just an implementation expedient: that has no impact on the consensus behavior, and it can be fixed to have one blinding key per scriptpubkey.

No-- it could be, but the overhead of that is quite considerable.  The exponent is public (note how it's shown on the getrawtransaction view), and just a property of the range proof, not the value itself-- so there is no complication in combining. It's set to whatever value the user wants, using it doesn't restrict the values you can send, though if your exponent is >0 your least significant digits are non-private.

So, addresses are

0x19: Alpha testnet blinded key
0x6F: Public key flag

<20 byte hash>


The 20 byte hash is for pay to public key hash. 

It seems the public/blinding key operates on a per-wallet basis.  Doesn't that basically kill privacy?

There is nothing much to see.

You just have an address. You send coins to it.  The fact that the world can't see the values is basically invisible to the user.  Looks just like testnet. From the CLI you can see more.

Here is an example where I send 0.25 testnet to myself.


$ ./alpha-cli getnewaddress
22E8QKHaTijFemPDwKvAk9qoTgagPfp8nBQiry87MMU1h2gQbF9xzLoyG8oWnakxEcPqQmhDtd2Wrut Cy
$ ./alpha-cli sendtoaddress 22E8QKHaTijFemPDwKvAk9qoTgagPfp8nBQiry87MMU1h2gQbF9xzLoyG8oWnakxEcPqQmhDtd2Wrut Cy 0.25
ab4201ee651c1396d35d799e68d59f3bb75581cc7fff1deed5efaf670973fbc9
$ ./alpha-cli listtransactions "*" 2
[
    {
        "account" : "",
        "address" : "22E8QKHaTijFemPDwKvAk9qoTgagPfp8nBQiry87MMU1h2gQbF9xzLoyG8oWnakxEcPqQmhDtd2Wrut Cy",
        "category" : "receive",
        "amount" : 0.25000000,
        "vout" : 0,
        "confirmations" : 0,
        "txid" : "ab4201ee651c1396d35d799e68d59f3bb75581cc7fff1deed5efaf670973fbc9",
        "walletconflicts" : [
        ],
        "time" : 1433908060,
        "timereceived" : 1433908060
    },
    {
        "account" : "",
        "address" : "22E8QKHaTijFemPDwKvAk9qoTgagPfp8nBQiry87MMU1h2gQbF9xzLoyG8oWnakxEcPqQmhDtd2Wrut Cy",
        "category" : "send",
        "amount" : -0.25000000,
        "vout" : 0,
        "fee" : -0.00005479,
        "confirmations" : 0,
        "txid" : "ab4201ee651c1396d35d799e68d59f3bb75581cc7fff1deed5efaf670973fbc9",
        "walletconflicts" : [
        ],
        "time" : 1433908060,
        "timereceived" : 1433908060
    }
]
#then we can see how the world sees it.
$ ./alpha-cli getrawtransaction ab4201ee651c1396d35d799e68d59f3bb75581cc7fff1deed5efaf670973fbc9 1
{
    "txid" : "ab4201ee651c1396d35d799e68d59f3bb75581cc7fff1deed5efaf670973fbc9",
    "version" : 1,
    "locktime" : 0,
    "fee" : 0.00005479,
    "vin" : [
        {
            "txid" : "76c4b906eaebdfc7685d1870aa3c4d57c8dce2fe7b924a7147c410ebffa8bee2",
            "vout" : 0,
            "scriptSig" : {
                "asm" : "0c0315abc52bced031a61ef1d8987470794540e46890b25b1f0f2b73b39d85ca37056e60fbf9a33 70c11ef7229575d937fd2935c9024ed2b1bc4a6fd473d3a9e01 0359134c3055c290a7a0499f0dfb78742ce964c1c4c8e17407898d5d05956c894e",
            },
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value-minimum" : 0.00000000,
            "value-maximum" : 42.94967295,
            "ct-exponent" : 0,
            "ct-bits" : 32,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "OP_DUP OP_HASH160 fd23ecdd4fb918bd88a319294b1f0ede5f701165 OP_EQUALVERIFY OP_CHECKSIG",
                "reqSigs" : 1,
                "type" : "pubkeyhash",
                "addresses" : [
                    "n4bSHiZXaApHquce1KEB8tfCZH7ZpDnUYe"
                ]
            }
        },
        {
            "value-minimum" : 0.00000000,
            "value-maximum" : 42.94967295,
            "ct-exponent" : 0,
            "ct-bits" : 32,
            "n" : 1,
            "scriptPubKey" : {
                "asm" : "OP_DUP OP_HASH160 fd5eff1963631488f624513719e866d92eae83e5 OP_EQUALVERIFY OP_CHECKSIG",
                "hex" : "76a914fd5eff1963631488f624513719e866d92eae83e588ac",
                "reqSigs" : 1,
                "type" : "pubkeyhash",
                "addresses" : [
                    "n4cf44LWhzi5KtbTaA1YHFBLWtgn89TF4K"
                ]
            }
        }
    ]
}

Interesting ~ this probably sounds anti-privacy a bit for me to ask perhaps at this stage :-) but do you have a screencap of what it looks like (GUI) when this process (confidential transactions as described thus far in your post) is being done?  
(Note:  I haven't dug into Elements... yet. :-) )

Is the exponent also encrypted? And if so, could you give some more detail on how you deal with amounts with different exponents?

Perhaps you've not caught on that this makes coinjoins and coinswaps tremendously more private and useful; since joining with anyone at any time improves your privacy, with no need to coordinate values.

You can think of it in these terms:  CoinJoin and CoinSwap are efficient metadata privacy protection systems, but their effectiveness is undermined by the content not being private.  CT is a content privacy system. The two compose very nicely. (And the RPCs in elements should be all setup to integrate with external coinjoin.).


Uh. Interesting position, (checks posting history), ah. Thanks for taking the time to step away from your ordinary posting in Dash/Darkcoin threads to chime in here.   I reject your premise: A bitcoin system where fungibility had failed enough to produce the situation you described would have already failed as a money. as that outcome would be untenable.  It's also not a theory that is well supported by current practices as there seems to be little such effect for coins moved through a variety of altcoin exchanges which are rumored to be primarily frequented for (inept) money laundering purposes.

Well, I'm impressed. Why you went to the trouble to implement your ring signature scheme makes a lot more sense now.

Taint tracking is inherently against the fungibility property of money. 

Moving money into the side chain and back doesn't really do much mixing, since you can still follow the transactions.

If this materializes, will we see two kinds of Bitcoins traded in exchanges, standard Bitcoins that trade at $x, and tainted Bitcoins that have been in the privacy sidechain trading at $x/2 or so?

OP, would you feel comfortable putting all your BTC through that sidechain?

Sounds like a credible idea for a side-chain for sure. I particularly like how CT could impose a more appropriate data visibility model for bitcoin overall; public transaction information that is required to assure system integrity is still available to all users, and private transaction information that only the involved parties require is now rendered private, yet still provable in a way that anyone can verify if they are provided with the data and the blinding factor. And all without much (arguably none) chain bloat.

Off topic  (): when can we expect to see code available that allows a chain like this to be mined?

This should be in the alt-coin section.   

Haha, but i am taking a look and it seems very interesting, some of the stuff is above my head but definitely worth studying. I'm glad you branched out and tried something new unburdening yourself of the self-imposed shackles BTC is suffering from.

I mentioned that I was using the new Borromean ringsig as a building block for a larger cryptosystem, Here it is:

Confidential Transactions

One of the most powerful new features being explored in the Elements sidechain is Confidential Transactions, a cryptographic tool to improve the privacy and security of Bitcoin. This feature keeps the amounts transferred visible only to participants in the transaction (and those they designate).

The security of the Bitcoin ledger is made possible by universal verification: each participant individually and autonomously verifies that each transaction is valid, without trusting any third party.  An unfortunate side effect is that all the transaction data must be conspicuously public so it can be verified, which is at odds with the normal expectation of privacy for traditional monetary instruments.

Insufficient financial privacy can have serious security and privacy implications for both commercial and personal transactions. Without adequate protection, thieves and scammers can focus their efforts on known high-value targets, competitors can learn business details, and negotiating positions can be undermined. Since publishing often requires spending money, lack of privacy can chill free speech.  Insufficient privacy can also result in a loss of fungibility--where some coins are treated as more acceptable than others--which would further undermine Bitcoin's utility as money.

Bitcoin partially addresses the privacy problem by using pseudonymous addresses. If someone does not know which users own which addresses, the privacy impact is reduced. But any time you transact with someone you learn at least one of their addresses. From there, you can trace out other connected addresses and estimate the values of their transactions and holdings. For example, suppose your employer pays you with Bitcoin and you later spend those coins on your rent and groceries. Your landlord and the supermarket will both learn your income, and could charge you higher prices as your income changes or target you for theft.

There are existing deployed techniques that further improve privacy in Bitcoin (such as CoinJoin, which merges the transaction history of users by making joint payments), but the utility of these techniques is reduced by the fact that it's possible to track amounts.

There have been proposed cryptographic techniques to improve privacy in Bitcoin-like systems, but so far all of them result in breaking "pruning" (section 7 of Bitcoin.pdf) and result in participants needing a perpetually growing database to verify new transactions, because these systems prevent learning which coins have been spent. Most proposed cryptographic privacy systems also have poor performance, high overhead, and/or require new and very strong (and less well understood) cryptographic assumptions.

Confidential Transactions improves the situation by making the transaction amounts private, while preserving the ability of the public network to verify that the ledger entries still add up. It does this without adding any new basic cryptographic assumptions to the Bitcoin system, and with a manageable level of overhead.

CT is possible due to the cryptographic technique of additively homomorphic commitments. As a side-effect of its design, CT also enables the additional exchange of private "memo" data (such as invoice numbers or refund addresses) without any further increase in transaction size, by reclaiming most of the overhead of the CT cryptographic proofs.


The technology behind Confidential Transactions
A high level technical primer

---

This work was originally proposed by Adam Back on Bitcointalk in his 2013 thread "bitcoins with homomorphic value". To build CT I had to implement several new cryptosystems which work in concert, and invented a generalization of ring signatures and several novel optimizations to make the result reasonably efficient.

The basic tool that CT is based on is a Pedersen commitment.

A commitment scheme lets you keep a piece of data secret but commit to it so that you cannot change it later. A simple commitment scheme can be constructed using a cryptographic hash:

  commitment = SHA256( blinding_factor || data )

If you tell someone only the commitment then they cannot determine what data you are committing to (given certain assumptions about the properties of the hash), but you can later reveal both the data and the blinding factor and they can run the hash and verify that the data you committed to matches. The blinding factor is present because without one, someone could try guessing at the data; if your data is small and simple, it might be easy to just guess it and compare the guess to the commitment.

A Pedersen commitment works like the above but with an additional property: commitments can be added, and the sum of a set of commitments is the same as a commitment to the sum of the data (with a blinding key set as the sum of the blinding keys):

  C(BF1, data1) + C(BF2, data2) == C(BF1 + BF2, data1 + data2) C(BF1, data1) - C(BF1, data1) == 0

In other words, the commitment preserves addition and the commutative property applies.

If data_n = {1,1,2} and BF_n = {5,10,15} then:

  C(BF1, data1) + C(BF2, data2) - C(BF3, data3) == 0

and so on.

Our specific Pedersen commitments are constructed using elliptic curve points. [The reader need not understand elliptic curve cryptography, beyond accepting the black box behaviors I describe here.]

Normally an ECC pubkey is created by multiplying a generator for the group (G) with the secret key (x):
  Pub = xG

The result is usually serialized as a 33-byte array.

ECC public keys obey the additively homomorphic property mentioned before:

   Pub1 + Pub2 = (x1 + x2 (mod n))G.

(This fact is used by the BIP32 HD wallet scheme to allow third parties to generate fresh Bitcoin addresses for people.)

The Pedersen commitment is created by picking an additional generator for the group (which we'll call H) such that no one knows the discrete log for H with respect to G (or vice versa), meaning no one knows an x such that xG = H. We can accomplish this by using the cryptographic hash of G to pick H:

    H = to_point(SHA256(ENCODE(G)))

Given our two generators we can build a commitment scheme like this:

   commitment = xG + aH

Here x is our secret blinding factor, and a is the amount that we're committing to.  You can verify just using the commutative property of addition that all the relationships given for an additively homomorphic commitment scheme hold.

The Pedersen commitments are information-theoretically private: for any commitment you see, there exists some blinding factor which would make any amount match the commitment. Even an attacker with infinite computing power could not tell what amount you committed to, if your blinding factor was truly random. They are computationally secure against fake commitment, in that you can't actually compute that arbitrary mapping; if you can it means you can find the discrete log of the generators with respect to each other, which means that the security of the group is compromised.

With this tool in hand we can go and replace the normal 8-byte integer amounts in Bitcoin transactions with 33-byte Pedersen commitments.

If the author of a transaction takes care in picking their blinding factors so that they add up correctly, then the network can still verify the transaction by checking that its commitments add up to zero:

    (In1 + In2 + In3 + plaintext_input_amount*H...) -
     (Out1 + Out2 + Out3 + ... fees*H) == 0.

This requires making the fees in a transaction explicit, but that's generally desirable.

The commitment and its checking are quite simple. Unfortunately, without additional measures this scheme is insecure.

The problem is that the group is cyclic, and addition is mod P (a 256-bit prime number that defines the order of the group). As a result, addition of large values can 'overflow' and behave like negative amounts. This means that a sums-to-zero behavior still holds when some outputs are negative, effectively allowing the creation of 5 coins from nothing:

 (1 + 1) - (-5 + 7) == 0

This would be interpreted as "someone spends two bitcoins, gets a '-5' bitcoin out that they discard out, and a 7 bitcoin output".

In order to prevent this, when there are multiple outputs we must prove that each committed output is within a range which cannot overflow (e.g. [0, 2^64)).

We could just disclose the amounts and blinding factors so that the network could check, but this would lose all of the privacy. So, instead, we need to prove that a committed amount is within the range but reveal nothing else about it: we need an additional cryptosystem to prove the range of a Pedersen commitment. We use a scheme similar to Schoenmakers’ binary decomposition but with many optimizations (including not using binary).

To build this we start with a basic EC signature. If a signature is constructed so that the 'message' is the hash of the pubkey, the signature proves that the signer knew the private key, which is the discrete log of the pubkey with respect to some generator.

For a 'pubkey' like P = xG + aH, no one knows the discrete log of P with respect to G because of the addition of H, because no one knows an x for xG = H----_unless_ a is 0. If a is zero then P = xG and the discrete log is just x; someone could sign for that pubkey.

A pedersen commitment can be proven to be a commitment to a zero by just signing a hash of the commitment with the commitment as the public key. Using the public key in the signature is required to prevent setting the signature to arbitrary values and solving for the commitment. The private key used for the signature is just the blinding factor.

Going further, let’s say I want to prove C is a commitment to 1 without telling you the blinding factor. All you do is compute

   C' = C - 1H

and ask me to provide a signature (with respect to G) with pubkey C'. If I can do that, the C must be a commitment to 1 (or else I've broken the EC discrete log security).

To avoid giving away the amount we need yet another cryptographic construct: a ring signature.  A ring signature is a signature scheme where there are two (or more) pubkeys and the signature proves that the signer knows the discrete log of at least one of the pubkeys.

So with that we can construct a scheme where I prove a commitment that C is either 0 or 1--we call this an "OR proof".

First, I give you C, and you compute C':

    C' = C - 1H

Then I provide a ring signature over {C, C'}.

If C was a commitment to 1 then I do not know its discrete log, but C' becomes a commitment to 0 and I do know its discrete log (just the blinding factor). If C was a commitment to 0 I know its discrete log, and I don't for C'.  If it was a commitment to any other amount, none of the result will be zero and I won't be able to sign.

This works for any pair of numbers, just by suitably pre-processing the amounts that are put into the ring... or even for more than two numbers.

Say I want to prove to you that C is in the range [0, 32). Now that we have an OR proof, imagine I send you a collection of commitments and OR proofs for each of them:

C1 is 0 or 1 C2 is 0 or 2 C3 is 0 or 4 C4 is 0 or 8 C5 is 0 or 16.

If I pick the blinding factors for C1..5 correctly then I can arrange it so that C1 + C2 + C3 + C4 + C5 == C.  Effectively I have built up the number in binary, and a 5-bit number can only be in the range [0,32).

Numerous optimizations are required to make this more efficient:

First, I propose a new ring signature formulation, a Borromean ring signature

• , which is especially efficient: it requires only 32 bytes per pubkey, plus 32 bytes which can be shared by many separate rings. This is has twice the asymptotic efficiency of previously proposed constructions for this application.
• https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf

Instead of expressing the amount directly, CT amounts are expressed using a decimal floating point where the digits are multiplied by a base 10 exponent.  This means that you can prove large amounts with small proofs, so long as they have few significant digits in base 10: e.g., 11.2345 and .0112345 can have the same size proof, even though one number is a thousand times larger.

There is also a non-private "minimum amount" sent, which allows a smaller proof to cover a larger range if the user doesn't mind leaking some information about the minimum amount (which might already be public for external reasons); this also allows the least significant digits to be non-zero when an exponent is used. Minimum amounts are supported by first subtracting the minimum, then proving that the result is non-negative.

The mantissa of the floating point is encoded using rings of size 4 (base 4) rather than binary, because this minimizes the number of commitments sent while not using any more signature data than base 2.

The final mantissa digit commitment can be skipped, backwards constructing it from the value being proven and the other digits, etc.

Finally, by careful use of derandomized signing in the prover, it's possible for the receiver of the coins--who shares a secret with the sender, due to ECDH key agreement with the receivers pubkey--to 'rewind' the proof and use it to extract a message sent by the sender which is 80% of the size of the proof.  We use this to signal the value and blinding factor to the receiver, but it could also be used to carry things like reference numbers or refund addresses.

The result is that a proof for a 32-bit value is 2564 bytes, and simultaneously may convey 2048 bytes of message. A 32-bit proof can cover a range of 42.94967296 BTC with 1e-8 precision, or 429.4967296 BTC with 1e-7 precision, and so on. My implementation is able to verify over 1300 32-bit range proofs per second on an i7-4770R, and there are many performance optimizations still possible.

The implementation supports proofs of any mantissa size or exponent, with the parameters controlled by the sender. Performance and size are linear in the number of mantissa bits, and odd numbers of bits are supported (by switching to radix-2 for the last digit).

In Elements, the range proofs are only required in cases where there are multiple confidential value outputs (including fees).  Transactions that merge multiple confidential amounts into a single output do not need range proofs since the fact that all the inputs were in range is sufficient.

By sharing the scanning key used to establish the shared secret used by the rewindable range proofs, this approach is completely compatible with watching wallets; users can share these keys with auditors to enable them to view their transaction amounts.

Future work may use the fact that proofs can support a minimum value to also allow skipping the range proofs when there is a single confidential output even when fees are being paid, or allow nodes to skip or delay verifying most range proofs by using fraud proofs.

The system presented here depends on no new fundamental cryptographic assumptions, only the hardness of the discrete log problem in the secp256k1 group and a random oracle assumption, just like the normal signatures in Bitcoin.

While the size of the range proofs are non-trivial, they are still an order of magnitude smaller and faster to verify than some alternatives (like Zerocoin), and most of their space can be reclaimed to communicate additional data between users, a feature which is often requested but hard to justify in a public broadcast network. Similar to signatures, the range proofs can be placed on separate tree branches in blocks to allow clients that don’t care about (e.g. historical ones) to skip receiving them.

Most importantly, this scheme is compatible with pruning and does not make the verification state for Bitcoin grow forever. It is also 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).

Unlike some other proposals, this system is not just speculation or pure cryptography without integration with the Bitcoin system.

Confidential Transactions is enabled in Elements and used by default by all ordinary transactions.

The source code for the just the underlying cryptosystem is also available.