bffranca
Newbie
Offline
Activity: 24
Merit: 0


November 25, 2014, 04:42:49 AM Last edit: June 07, 2015, 11:58:08 PM by bffranca 

This paper attempts to improve the miniblockchain 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 miniblockchain. https://drive.google.com/file/d/0B21vncLoIlIyaVpGVFN5c1VFdmM/view?usp=sharingEdit (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 miniblockchain scheme. It can be found at the following link, https://drive.google.com/file/d/0B21vncLoIlIyUldiZTRxSTYyNGc/view?usp=sharing






Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




MisO69
Legendary
Offline
Activity: 1946
Merit: 1005
My mule don't like people laughing


November 25, 2014, 02:02:49 PM 

This paper attempts to improve the miniblockchain 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 miniblockchain. https://drive.google.com/file/d/0B21vncLoIlIyaVpGVFN5c1VFdmM/view?usp=sharingI 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://bitcointalk.org/index.php?topic=713538.0




bffranca
Newbie
Offline
Activity: 24
Merit: 0


November 25, 2014, 05:52:07 PM 

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




BootstrapCoinDev


November 26, 2014, 02:25:49 PM 

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.




mistercoin
Legendary
Offline
Activity: 1018
Merit: 1000
gemini.com/share/88dpzrmh9


November 26, 2014, 03:01:57 PM 

Very nice! Have any plans of implementing this?




bffranca
Newbie
Offline
Activity: 24
Merit: 0


November 27, 2014, 02:59:20 AM 

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/mbcschemerev2.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.




gmaxwell
Staff
Legendary
Offline
Activity: 3640
Merit: 5983


November 27, 2014, 06:02:05 AM 

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.




bffranca
Newbie
Offline
Activity: 24
Merit: 0


November 27, 2014, 06:20:03 AM 

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.




gmaxwell
Staff
Legendary
Offline
Activity: 3640
Merit: 5983


November 27, 2014, 09:29:32 AM 

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.
I don't see what you're saying that. ElGamal can do addition fine, as long as you don't need decryption (or can bruteforce 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).




adam3us


November 27, 2014, 09:42:44 AM Last edit: November 27, 2014, 10:43:30 AM by adam3us 

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.
I don't see what you're saying that. ElGamal can do addition fine, as long as you don't need decryption (or can bruteforce 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). 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://bitcointalk.org/index.php?topic=305791.msg3294618#msg3294618 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 128bit security with Paillier you need 3kbit keys and 6kbit ciphertexts. Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



bffranca
Newbie
Offline
Activity: 24
Merit: 0


November 27, 2014, 06:15:16 PM 

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 bruteforce 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 miniblockchain only stores transactions for a limited time, they would need to connect to the network periodically (7 days in the case of cryptonite). 2) Bruteforce 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 zeroknowledge arguments that I'm using. You should probably read the original paper by Groth: www0.cs.ucl.ac.uk/staff/J.Groth/MatrixZK.pdfIt is a great read. The most revelant sections are 3.3 (about the SchwartzZippel Lemma) and 5.1 (it explains the proof that I'm using). Sorry that I didn't include the proof for these zeroknowledge arguments, but the paper was already very long and I did not want to make it even longer.




adam3us


November 27, 2014, 09:54:28 PM 

The problem with exponential Elgamal (as you've said) is that you need to bruteforce 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 miniblockchain only stores transactions for a limited time, they would need to connect to the network periodically (7 days in the case of cryptonite).
public key encryption can do that fine, and the user has key(s) to control coins or balances. I don't need to prove that the values don't wrap around. That isn't a problem with the linear algebra zeroknowledge arguments that I'm using. You should probably read the original paper by Groth: www0.cs.ucl.ac.uk/staff/J.Groth/MatrixZK.pdfAs 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

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



UnunoctiumTesticles


November 28, 2014, 12:15:11 PM 

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 fanout 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?




adam3us


November 29, 2014, 10:13:55 PM 

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 fanout 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?
You're referring to another scheme committed transactions http://www.mailarchive.com/bitcoindevelopment@lists.sourceforge.net/msg02184.html and detail on https://bitcointalk.org/index.php?topic=206303.msg2157994#msg2157994, your description is correct. There is an unsolved problem with it though  how to prevent hostile miners censoring the keys instead (by pretending they never saw them)... there needs to be a second stage validation to say ok, this is the disclosed key and the signatures are good & values add up. You cant directly impose consensus on not disclosing that because it creates a DoS risk  that someone really doesnt reveal the key at all, or keeps it to themselves, like a selfishmining type of attack. The homomorphic encrypted transaction values is different, just encrypting the value. So the payments are still as traceable as without them, just the values are hidden from the miners and from the ledger. Miners and anyone else can still verify that the amounts add up, just they cant tell how much they actually are. Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



bffranca
Newbie
Offline
Activity: 24
Merit: 0


December 01, 2014, 02:57:37 AM Last edit: December 01, 2014, 04:33:10 AM by bffranca 

Adam, I reviewed the proof and you are absolutely right. For some reason I thought that wraparound wasn't a problem and that I could prove y=x_1+...+x_n over the integers. The thing is that Groth's proof can prove that a vector is the Hadamard product of two other vectors over the integers or prove that a value is the inner product of two vectors but only over the integers modulo n. Strangely he treats both cases as interchangeable and never mentions this critical difference. Anyway, I need to add range proofs for all input/output amounts and then it's enough to check if Com(y)/(Com(x_1)*...*Com(x_n))=Com(0). I will probably use Berry Schoenmaker's range proof with your improvements. Also, I have been thinking of ways to substitute the Paillier's encryption for another encryption scheme. First, I can't trust the sender of a transaction to send the value and the nonce of the transaction (how you did in your homomorphic value scheme) because if he sends the wrong value the receiver no longer can use his account. Worse, a malicious user could do that on purpose to ask for ransom or to disrupt the network. The other suggestion (from gmaxwell) was to use elliptic curve Elgamal. I did some research and found that a 3 GHz Pentium 4 processor can do an EC addition on a NIST 256bit prime field curve in 8.3*10^8 seconds. Extrapolating from that, it can crack a 24 bit EC discrete log on average in 0.7 seconds. So, if I reduce the maximum amount per transaction to 2^24 units, I could use EC Elgamal instead of Paillier. As a bonus, the range proof size would be cut in half. So it may be a viable idea. The problem with exponential Elgamal (as you've said) is that you need to bruteforce 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 miniblockchain only stores transactions for a limited time, they would need to connect to the network periodically (7 days in the case of cryptonite).
public key encryption can do that fine, and the user has key(s) to control coins or balances. My issue wasn't with storing the balance. The problem is if a transaction is deleted before the receiver connects to the network. Then the receiver has no way of finding the transaction amount.




bffranca
Newbie
Offline
Activity: 24
Merit: 0


December 03, 2014, 08:12:15 PM Last edit: December 16, 2014, 12:06:00 AM by bffranca 

Ok, found a good elliptic curve additively homomorphic encryption scheme. Here's the paper, http://ecewp.ece.wpi.edu/wordpress/crypto/files/2012/10/main.pdf. What the authors did was using regular elliptic curve Elgamal to encrypt several times the same message modulo different (small) pairwise coprime numbers. To decrypt one simply bruteforces the decryption of each plaintext (which should be easy since the moduli are small) and then, using the chinese remainder theorem, one can recover the original message. In more detail: Setup> Choose a elliptic curve prime field F_p, a base point P in F_p and a random integer x in [1;p1]. Calculate point Q=x*P. Assume that the message space is Z_s and that s<p. Then choose integers d_1,...,d_t in N such that s<d<p (d=d_1*...*d_t) and that they are pairwise coprime (for all i!=j, gcd(d_i,d_j)=1). The public key is the tuple (P,Q,d_1,...,d_t) and the secret key is x. Encryption> Choose random integers r_1,...,r_t in [1;p1]. Calculate m_i= m mod d_i for all i in {1,..,t}. The ciphertext is the t tuples {(A_i,B_i)=(r_i*P, r_i*Q+m_i*P), for all i in {1,...,t}}. Decryption> Calculate C_i= B_i  x*A_i=m_i*P for all i. Then calculate m_i= log_P(C_i) for all i. Finally use the extended Euclidean algorithm to solve the system of congruences {m=m_1 mod d_1,...,m=m_t mod d_t}. Assuming the message space is 2^51 (like bitcoin), we would need three 17bit moduli. The public key would be a bit longer than regular Elgamal and the ciphertexts would have 3x the size but it would be fast to decrypt and more efficient than Paillier encryption.




digicoin
Legendary
Offline
Activity: 1106
Merit: 1000


December 15, 2014, 06:43:27 AM 

When will your paper be updated with your new findings?




adam3us


December 15, 2014, 02:49:49 PM 

[The url is b0rken for the additively homomorphic Elgamal variant you mentioned. Should be http://ecewp.ece.wpi.edu/wordpress/crypto/files/2012/10/main.pdf] Their additive Elgamal variant seems interesting, but I am not sure why you need it to be simultaneously decryptable and additive: instead you can have additive simply with vG+xH for two EC bases G and G, value v, and random value x, and presuming the owner knows his own decryption, he can do the addition, and communicate the value & new x value to the recipient using ECIES or normal Elgamal? Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



bffranca
Newbie
Offline
Activity: 24
Merit: 0


December 16, 2014, 12:05:08 AM 

Digicoin: I'm going to wait a bit more because I'm trying to find a range proof more efficient than Schoenmaker's bitbybit proof. Also, I would like to see if I could introduce multiinput transactions (as proposed in Adam's "Ringcoin" homomorphic scheme) into this scheme.
Adam: The url is working fine in my browser but I will change it. I need it to be decryptable because you don't know if the sender of the transaction will send the right value and random value. In your homomorphic scheme this isn't a problem because you could simply ignore the transaction but this scheme runs on top of the miniblockchain which actually has accounts. Suppose you have an account with balance x and corresponding Pedersen commitment xG+vH. Then I send you a transaction with value y (it can even be zero) and random value r,so yG+rH, but I send to you encrypted any other values (let's say y' and r'). The two commitments will be added and your balance will be (x+y)G+(v+r)H. Now you can't open the commitment of your own balance so, you can't make transactions because you won't be able to produce the required ZK proofs. Finally I can send a message telling you to pay me z bitcoins or I won't tell you the real values. Also, the miniblockchain only stores transactions for a limited time (in cryptonite's case it's 7 days) so if someone receives a transaction and doesn't connect to the network in 7 days, he won't see the transaction and will no longer know its own balance.




adam3us


December 16, 2014, 10:17:39 AM 

There are variants of schnorr proof of knowledge (DSA is a variant of schnorr) where you can prove that encrypted values are the same by combining with Elgamal. So I think you should be able to prove that the sender sent the recipient in a way decryptable by their advertised public key, an encrypted value which matches the (nondecryptable) second encryption. eg if you look at Brands is a more complicate version but there are a few survey papers showing all the common things you can easily prove using schnorr variants. ie so prove that the plaintext under the encryption would result in the recipient knowing a value that would allow it to spend the coin. in your labelling make a schnorrrelated proof that y=y' and r=r'. I did think of this going back a few weeks in my comments on your original scheme but maybe neglected to say it. Adam Adam: The url is working fine in my browser but I will change it. I need it to be decryptable because you don't know if the sender of the transaction will send the right value and random value. In your homomorphic scheme this isn't a problem because you could simply ignore the transaction but this scheme runs on top of the miniblockchain which actually has accounts. Suppose you have an account with balance x and corresponding Pedersen commitment xG+vH. Then I send you a transaction with value y (it can even be zero) and random value r,so yG+rH, but I send to you encrypted any other values (let's say y' and r'). The two commitments will be added and your balance will be (x+y)G+(v+r)H. Now you can't open the commitment of your own balance so, you can't make transactions because you won't be able to produce the required ZK proofs. Finally I can send a message telling you to pay me z bitcoins or I won't tell you the real values. Also, the miniblockchain only stores transactions for a limited time (in cryptonite's case it's 7 days) so if someone receives a transaction and doesn't connect to the network in 7 days, he won't see the transaction and will no longer know its own balance.

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



