Financial Privacy and Verifiable Transactions

[Cryddit]

One property of the Bitcoin system (and so far, of all altcoins) is that there is a public record of all transactions, including the amount and derivation of all "coins" ie, unspent txouts. 

In the presence of datamining, this effectively de-anonymizes vast parts of the entire system.  And that's a problem. 

It would be good if we could verify the transactions conformance to protocol rules with respect to amounts (ie, verify that the outputs are equal to or less than the inputs) without revealing the amounts themselves.  Zerocoin was one solution to this, but I would rather attack it at the level of individual transactions.

Proof of "less than" is very hard, probabilistic, and would add huge bulk to the blockchain.  But proof of "equal" is possible and compact, and requires only one adjustment to protocol rules: We must explicitly represent the coin intended as the transaction fee, so that proof of equality is applicable to all transactions.

In the Benaloh homomorphic cryptosystem,  the public key is a modulus M and a base B.  For a plaintext P, a blocksize L, and some shared number N greater than 0 and less than M, the encryption of P is:

(B raised to the Pth power, multiplied by N raised to the L power) modulo M. 

This is interesting because for any two integers X and Y whose sum is less than B, the product of Encrypt(X) and Encrypt(Y) equals Encrypt( (X + Y) mod B).  And because addition and multiplication are both associative, this is true of any set of more than two integers as well. 

That is to say, for any given set of plaintext numbers, the product of the encrypted numbers equals the encryption of the sum of the numbers.   Since we want to test that the inputs and outputs add to the same sum, we can do so by testing that the encrypted inputs and the encrypted outputs have the same modular product, even when we don't know what the numbers are. 

Key management is a somewhat complex problem; to verify that the output coins add up to the same amount as the input coins, you need all the coins to be encoded using the same Benaloh key.  Therefore having the Benaloh key used for any output coin of a transaction enables you to learn the amounts for all input coins and output coins of that transaction.   That means that all the participants know what's going on in the transaction, which is, IMO, as it should be. 

But I need to figure out a good way for blockchain checkers to verify that the presented input coins shown in the current transaction  encrypted with the common key of the current transaction, are in fact the same amounts as the identified output coins of their previous transactions, which of course show in the blockchain encrypted using the keys of previous transactions.

I have solutions for limited cases where coins are not subdivided or combined.  (ie, input coins can change ownership in a transaction becoming output coins, in a way that's verifiable, without having their value revealed).   But when these coins are eventually subdivided or combined, their value is revealed as soon as one of the resulting coins is spent.  If at least one of the participants in a transaction does not value (or negatively values) privacy, this can happen as soon as that participant comes into possession of a coin.

Does anybody have a better solution for the last part of this problem?

[jl2012]

One property of the Bitcoin system (and so far, of all altcoins) is that there is a public record of all transactions, including the amount and derivation of all "coins" ie, unspent txouts. 

In the presence of datamining, this effectively de-anonymizes vast parts of the entire system.  And that's a problem. 

It would be good if we could verify the transactions conformance to protocol rules with respect to amounts (ie, verify that the outputs are equal to or less than the inputs) without revealing the amounts themselves.  Zerocoin was one solution to this, but I would rather attack it at the level of individual transactions.

Proof of "less than" is very hard, probabilistic, and would add huge bulk to the blockchain.  But proof of "equal" is possible and compact, and requires only one adjustment to protocol rules: We must explicitly represent the coin intended as the transaction fee, so that proof of equality is applicable to all transactions.

In the Benaloh homomorphic cryptosystem,  the public key is a modulus M and a base B.  For a plaintext P, a blocksize L, and some shared number N greater than 0 and less than M, the encryption of P is:

(B raised to the Pth power, multiplied by N raised to the L power) modulo M. 

This is interesting because for any two integers X and Y whose sum is less than B, the product of Encrypt(X) and Encrypt(Y) equals Encrypt( (X + Y) mod B).  And because addition and multiplication are both associative, this is true of any set of more than two integers as well. 

That is to say, for any given set of plaintext numbers, the product of the encrypted numbers equals the encryption of the sum of the numbers.   Since we want to test that the inputs and outputs add to the same sum, we can do so by testing that the encrypted inputs and the encrypted outputs have the same modular product, even when we don't know what the numbers are. 

Key management is a somewhat complex problem; to verify that the output coins add up to the same amount as the input coins, you need all the coins to be encoded using the same Benaloh key.  Therefore having the Benaloh key used for any output coin of a transaction enables you to learn the amounts for all input coins and output coins of that transaction.   That means that all the participants know what's going on in the transaction, which is, IMO, as it should be. 

But I need to figure out a good way for blockchain checkers to verify that the presented input coins shown in the current transaction  encrypted with the common key of the current transaction, are in fact the same amounts as the identified output coins of their previous transactions, which of course show in the blockchain encrypted using the keys of previous transactions.

I have solutions for limited cases where coins are not subdivided or combined.  (ie, input coins can change ownership in a transaction becoming output coins, in a way that's verifiable, without having their value revealed).   But when these coins are eventually subdivided or combined, their value is revealed as soon as one of the resulting coins is spent.  If at least one of the participants in a transaction does not value (or negatively values) privacy, this can happen as soon as that participant comes into possession of a coin.

Does anybody have a better solution for the last part of this problem?

I don't understand the maths. But as you said the value will eventually be revealed so I don't think it works.

[Cryddit]

I dunno.  We get along fine in physical space with cash that's non-divisible and non-joinable.  If there are standard coin sizes, and people are willing to make change, divisibility isn't really necessary.  (although TX fees and so on would need to be in whole-coin increments, like sales tax).

[gmaxwell]

We get along fine in physical space with cash that's non-divisible and non-joinable.

In the centeralized world we have central banks that regulate inflation to keep prices stable.

Encrypting values sounds interesting, if the overhead is very low.  But perhaps of limited value, since disclosing an amount must disclose the whole transaction history.  I also don't see how you can pay a transaction fee (which requires making one output a public value, so the miner knows how much fee he got!) without disclosing the encryption key for the whole transaction.

If you traverse the history of a random transaction on the network you'll find that many of them are rapidly internlinked with hundreds of thousands of transactions. Even using a penny from one graph would end up disclosing the whole history's values. This would make the privacy very brittle. It can be argued that brittle privacy is worse for people than none.

If the scheme supported a way to 'emerge' a coin and make its value public without disclosing the history, even if this mechanism were fairly costly (e.g. a moderately big zero knoweldge proof) then that would be a way to infrequently break up the history without disclosing it, and this would perhaps be more useful. E.g. every once in a while you'd perform a transaction that makes the values public and provides a proof that the values are correct, but doesn't disclose the history.

[adam3us]

With Benaloh it true that B can be smaller (than the order of the group of a secure EC DL instance) and actually it has to be smaller if you use decryption, because decryption takes time sqrt(B).  But I dont think mod B solves the inherent problem with less than, because as a generic thought experiment consider B=251 (or n=251 in an EC group of order n using EC discrete log instead of Benaloh), now you have an input 4, you can make the homorphic addition still work while defrauding the network:

E(4) = E(127)+E(127)+1

where 1 is the clear text fee (ie the recipent encrypts 1 and checks E(4) =? E(127)+E(127)+E(1)) which is true mod 251 because 127+127+1=255-251=4, and now you have created forged value of n=B=251 coins.

Did you see the range proof on this thread? 

https://bitcointalk.org/index.php?topic=305791.msg3294618#msg3294618

I optimized the application of the Schoenmakers range proof and comes to 1kB-2kB per value (proof size depends on the precision of the coin value, not on the size of n).

I avoided Benaloh because its less well used, not EC; and you still need the range proof I argue above, and being mod B anyway restricts your coin value precision to B, and the range proof will be no smaller in Benaloh than normal EC discrete log as a result.

But I need to figure out a good way for blockchain checkers to verify that the presented input coins shown in the current transaction  encrypted with the common key of the current transaction, are in fact the same amounts as the identified output coins of their previous transactions, which of course show in the blockchain encrypted using the keys of previous transactions.

Using the Pederson commitment as shown on the other thread allows validation of adding up without revealing the transaction details because there is also an undisclosed x (value private key), ie c1=g^v1*h^x1 and x1 is never disclosed, and yet addition can be checked.


Also about your idea there is a way to prove two discrete logs are equal that may allow what you want (havent checked how that works out with Benaloh).

Adam

One property of the Bitcoin system (and so far, of all altcoins) is that there is a public record of all transactions, including the amount and derivation of all "coins" ie, unspent txouts. 

In the presence of datamining, this effectively de-anonymizes vast parts of the entire system.  And that's a problem. 

It would be good if we could verify the transactions conformance to protocol rules with respect to amounts (ie, verify that the outputs are equal to or less than the inputs) without revealing the amounts themselves.  Zerocoin was one solution to this, but I would rather attack it at the level of individual transactions.

Proof of "less than" is very hard, probabilistic, and would add huge bulk to the blockchain.  But proof of "equal" is possible and compact, and requires only one adjustment to protocol rules: We must explicitly represent the coin intended as the transaction fee, so that proof of equality is applicable to all transactions.

In the Benaloh homomorphic cryptosystem,  the public key is a modulus M and a base B.  For a plaintext P, a blocksize L, and some shared number N greater than 0 and less than M, the encryption of P is:

(B raised to the Pth power, multiplied by N raised to the L power) modulo M. 

This is interesting because for any two integers X and Y whose sum is less than B, the product of Encrypt(X) and Encrypt(Y) equals Encrypt( (X + Y) mod B).  And because addition and multiplication are both associative, this is true of any set of more than two integers as well. 

That is to say, for any given set of plaintext numbers, the product of the encrypted numbers equals the encryption of the sum of the numbers.   Since we want to test that the inputs and outputs add to the same sum, we can do so by testing that the encrypted inputs and the encrypted outputs have the same modular product, even when we don't know what the numbers are. 

Key management is a somewhat complex problem; to verify that the output coins add up to the same amount as the input coins, you need all the coins to be encoded using the same Benaloh key.  Therefore having the Benaloh key used for any output coin of a transaction enables you to learn the amounts for all input coins and output coins of that transaction.   That means that all the participants know what's going on in the transaction, which is, IMO, as it should be. 

But I need to figure out a good way for blockchain checkers to verify that the presented input coins shown in the current transaction  encrypted with the common key of the current transaction, are in fact the same amounts as the identified output coins of their previous transactions, which of course show in the blockchain encrypted using the keys of previous transactions.

I have solutions for limited cases where coins are not subdivided or combined.  (ie, input coins can change ownership in a transaction becoming output coins, in a way that's verifiable, without having their value revealed).   But when these coins are eventually subdivided or combined, their value is revealed as soon as one of the resulting coins is spent.  If at least one of the participants in a transaction does not value (or negatively values) privacy, this can happen as soon as that participant comes into possession of a coin.

Does anybody have a better solution for the last part of this problem?

[Cryddit]

I think that I have a solution for the homomorphic encryption problem that I started this thread with.

The solution lies in choice of exponent for the Benaloh system.  In order to convert coins from previous to subsequent exponent, it is necessary to know all the factors of the exponent.   To verify that it has been done correctly requires only one.

Given X = A * B * C, the coin holder (who knows all these values) can easily convert JX to KY where Y = A * B * D  =  D * (X / C).  He can reveal C and D allowing others to verify that it has been done correctly, even though others don't know A and B.  However, in order to derive J or K, any others would have to first *know* whichever one they weren't trying to derive, and second would have to be able to factor the residue AB.

In practical application, a coin that was created with the exponent X in the original transaction can be converted to the exponent Y, where the previous transaction has revealed C and the current transaction reveals D.

This requires the exponents to be uncomfortably large, making each coin a minimum of 1/2 kilobyte to represent.  But it's reasonably practical I think.  I will have to scribble and do proofs for a day or two in order to figure this out in detail.

I have to admit that I can understand more readily the difficulty of modular factoring than the difficulty of reversing ECC.  ECC is easiest for me to think of as sort of a modular discrete geometry problem, although usually presented and explained as a Groups problem.  If I can show rigorously that this idea works via modular factoring, I will look at ECC and see if I can find the appropriate analogue in its structure.  If so that should reduce the required representation space by about an order of magnitude.

[marcus_of_augustus]

Ok ... gonna dig into this a bit more now I think.