Topic: Anonymity in the Mini-Blockchain scheme - page 3. (Read 5461 times)

Please correct me if I am mistaken (and I haven't read the paper), but if I remember correctly from when afair Adam first proposed homomorphic encryption at some presentation in Israel, the tx is not untraceable for the recipient and his fan-out of recipients downstream?

I think Adam had argued one of the benefits could be the inability of miners to block txs based on the history trail.

Any other summary of the benefits and tradeoffs compared to other anonymity schemes?

public key encryption can do that fine, and the user has key(s) to control coins or balances.


As far as I can see this is all (including the matrix proofs) modulo n the order of the curve (or p the field).  Consider if I prove balance a == a'+b+t where t is the transaction fee, a is alice's initial balance, a' alice's revised balance and b bob's additional balance.  

Alice and Bob can collude to create instead a' > a eg say n = 13 then the honest version is t=1, a=6, a'=3, b=2 (6=3+2+1)
but a dishonest version is t=1, a=6, a'=11,b=7 and 6=11+7+1 mod 13 = 19 mod 13 = 6.  So Alice and Bob can add n to their balance and the ZKP still passes.

Adam

gmaxwell: Sorry, I thought you were talking about regular Elgamal, not the exponential variant. My bad.  
The problem with exponential Elgamal (as you've said) is that you need to brute-force the decryption. As the balances of the accounts are also encrypted, users only have two options:
1) Store a copy of the balance in theirs computers using a different encryption. Since the mini-blockchain only stores transactions for a limited time, they would need to connect to the network periodically (7 days in the case of cryptonite).
2) Brute-force the decryption. Which requires solving the discrete logarithm problem in a search space equal to the total number of coins. For bitcoin that would be 2^50. I don't how much time it would take in a regular PC, but if it is more than a few seconds it becomes problematic (people don't like to wait).
Other than that, I agree with you. Elgamal is better studied, faster and has better libraries. As I have said, any additively homomorphic encryption would do. The choice of Paillier was arbitrary.

gmaxwell, adam3us: I don't need to prove that the values don't wrap around. That isn't a problem with the linear algebra zero-knowledge arguments that I'm using. You should probably read the original paper by Groth:
www0.cs.ucl.ac.uk/staff/J.Groth/MatrixZK.pdf
It is a great read. The most revelant sections are 3.3 (about the Schwartz-Zippel Lemma) and 5.1 (it explains the proof that I'm using). Sorry that I didn't include the proof for these zero-knowledge arguments, but the paper was already very long and I did not want to make it even longer.

I agree, the values seem to wrap rendering the scheme insecure unless I'm missing something about the ZK matrix additions - those are also modulo one of the fields right?

What Greg said re Elgamal is how I did it in this homomorphic value scheme https://bitcointalksearch.org/topic/m.3294618 note use of Berry Schoemakers ZK range proof to prove the values dont wrap.  It ends up being basically a pedersen commitment because you dont need to be able to encrypt, just verify.  The sender can send the Pedersen nonce to the recipient so the recipient can see how much he received and be in a position to respend it.

I would personally prefer to avoid adding the Paillier security assumptions, while they seem fairly conservative and reasonable, unless it was necessary.

The hard part is the ZK range proof (aka ZK less than) - that is where the largest part of the verification cost and worse, the coin size comes from.  As you see on the above link it comes to 1KB per value.  I am not sure that would actually be worse than this scheme because for 128-bit security with Paillier you need 3kbit keys and 6kbit ciphertexts.

Adam

I don't see what you're saying that. ElGamal can do addition fine, as long as you don't need decryption (or can brute-force the decryption), you can just tell the recipients the values (e.g. just separately in the transaction or out of band).  ElGamal is much older and well studied, and you're already taking the same security assumption for the commitments. So it's just a _ton_ more code for the paillier, new cryptographic assumptions, and a lot of overhead.

Having looked a bit more at it, I don't see how you're proving the values don't wrap around. E.g. that I don't give someone a negative amount (a huge amount) of coins, which yet still adds up because of the wrap. I thought there was something in there before, but I I'd stopped before getting that far with confusion on the paillier ... because it seemed very strange to invoke a new very inefficient cryptosystem (and I wasn't sure if the rest was going to be worth reading).

You're right, any additively homomorphic encryption would do. I chose Paillier because it is was reviewed extensively and has a ton of libraries written for it. Unfortunately ElGamal is multiplicatively homomorphic so it can't be used.

It's not clear to me why it's using the paillier encryption.  The commitment agreement proof looks like it would work fine with any additively homomorphic encryption, e.g.  ElGamal over the same prime group used for the commitments, which would make things much simpler and more efficient.

What am I missing here?


The paper appears to be missing citations on the agreement proof approach and only cites the basic underlying cryptosystem; which might answer my question there.

BootstrapCoinDev: I advise you to read J. D. Bruce's paper. He explains in detail how new nodes decide which blockchain is the correct one. www.cryptonite.info/files/mbc-scheme-rev2.pdf.

mistercoin: Thank you! I haven't really thought about it, but it would be nice to see a coin using this scheme. Although it probably can be improved.

Very nice! Have any plans of implementing this?

I was wondering how a new node can bootstrap and be sure it has a valid set of balances, when all the other nodes have discarded the transaction history. Just having proof of work doesn't tell you that all the transactions in those blocks are valid to you, just that they were valid to whoever mined them. But it sounds like that issue is addressed fairly well at the bottom of the "Proof Chain" section.

Maybe Cryptonite could be hard-forked but it would be difficult. It is easier to create a new coin.

I took a look at the paper and most of it is over my head. Could this be implemented into Bitfreak's mini blockchain coin - Cryptonite? https://bitcointalksearch.org/topic/annxcn-cryptonite-1st-mini-blockchain-coin-m7-pow-no-premine-713538

This paper attempts to improve the mini-blockchain scheme and make it private and even more scalable. This is achieved by encrypting transaction amounts and accounts balances with homomorphic encryption, allowing it to perform addition and subtraction on encrypted values without revealing the plaintexts. Another aspect of this paper are ”expiration dates” on accounts so that users need to pay fees periodically to maintain their accounts. This way abandoned accounts are automatically pruned from the mini-blockchain.

https://drive.google.com/file/d/0B21vncLoIlIyaVpGVFN5c1VFdmM/view?usp=sharing

Edit (24/04/2015): After receiving some constructive criticism, I redesigned the scheme and rewrote the paper. The objective is still the same, to make a more private version of the mini-blockchain scheme. It can be found at the following link,

https://drive.google.com/file/d/0B21vncLoIlIyUldiZTRxSTYyNGc/view?usp=sharing