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?

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

The timing couldn't have been better.

gmaxwell, the paper is up at the following link https://drive.google.com/file/d/0B21vncLoIlIyUldiZTRxSTYyNGc/view?usp=sharing. Whenever I change the paper I have to change the link so that's why you weren't able to see it. But I always keep the up-to-date link in the first post of the thread.

I have just watched your video introducing the Elements sidechain (https://www.youtube.com/watch?v=9pyVvq-vrrM) and I was very impressed. I didn't expect that new features would be introduced in the first test sidechain, especially all these features. I actually read your draft about Borromean signatures before but thought that you were going use them in the same way as Cryptonite, using ring signatures as an OR proof is an innovative idea. In summation, I'm very envious.  

Since my scheme offers no more privacy than using Confidential transactions + Stealth addresses, I see no reason to try to implement it. The only information that may be useful to you is that I use Boneh-Lynn-Shacham signatures which are shorter and also require less rounds of communication for threshold and blind signing than Schnorr signatures. If you're interested, the following paper https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf describes the use of BLS signatures for  multi, threshold and blind signing.

@bybitcoin: Ok, I cannot say if this scheme can be a sidechain to Bitcoin since the paper does not provide a detailed description of a SPV proof. Without knowing that I would just be speculating. When Blockstream launches their "demo version" of a sidechain, the federated peg, there will be more information. But I wouldn't mind if the scheme became a sidechain instead of a altcoin.

I still haven't read their whitepaper about sidechains. I downloaded it a few weeks ago but just forgot about it. But AFAIK it could be implemented as a sidechain easily.
I will read the paper and give you a more informed answer after.

Now that I saw what the Nxt's voting system is, I am disappointed. It appears that all votes are recorded in the blockchain in plaintext so that anyone can see who voted on what. https://wiki.nxtcrypto.org/wiki/Voting_System "On the bottom of the pane, the votes cast in the poll are displayed while they are still available. For each voting account the account ID is shown along with the integer range value associated with each option voted for."

Most (if not all) cryptographic voting schemes are private (no one can see my vote) and receipt-free (I can't prove that I voted on a given option), this is done to avoid coercion and vote buying. Nxt's voting system is neither so it can't be used for any serious election. Despite that, there are articles saying it could be used in shareholder's elections, corporate governance (http://cointelegraph.com/news/113414/nxt-teases-voting-system-two-phase-transactions-and-a-foundation) and even government elections (https://www.cryptocoinsnews.com/nxt-decentralized-voting-system-twitter/). This is very misleading and it appears that a lot of people think that Nxt's voting system is secure when it is not.

There is an advantage in having a smaller total supply, the range proofs get smaller (513 bits for each bit of the total coin supply). Since Bitcoin's supply is ~2^50.9, a total supply between 2^40 and 2^50 is desirable.
The distribution curve is difficult to decide. If it is too short, the supply gets concentrated in a small number of people and the coin gets accused of being a pump and dump. If it is too long and the price does not rise accordingly, no one wants to hold onto the coin because it devalues too fast. Normally if a (fiat) currency exceeds 4% inflation it starts to be a problem. I don't like Bitcoin's distribution curve (see http://www.mattwhitlock.com/Bitcoin%20Inflation%20logarithmic.pdf) because it takes a long time (12 years) to reach a good inflation rate (2%) and then only spends 4 years at that rate. I would prefer to have a initial period of very high inflation to distribute coins (like the first 4 years of Bitcoin) but then have a longer period where the inflation is kept at a constant rate between 2% and 4%.

Presales (and premines and instamines) have a negative connotation regardless of what the money is used for. It would be a shame to turn people away from a good cryptocurrency just because there was a presale. IMO, voluntary coders and fair distribution is the way to go.

I would like to see this come to life but I can't do it alone because I don't know how to code (except some simple scrypts in Python). Having said that, I am willing to work in any way I can.

Yes, I was talking about the advantage relative to Bitcoin. I know the account tree in my scheme will be at least an order of magnitude bigger than in the MBC, probably more. I tried to maintain the accounts in the scheme, but it was simply not possible to have a high degree of privacy with reusable accounts.

You understood it perfectly, the account tree has the unspent outputs of all transactions. The advantage for me of separating the unspent outputs from the transactions is that the transactions are much larger in size (in this scheme) than the unspent outputs, so there is a considerable saving. The minimum output value was borrowed from Bitcoin and it seems to be working well for them. An interesting variation could be forcing the minimum output value to be a multiple of the transaction fee, for example, if you include a transaction fee of X then all outputs must be at least 3X.
I remember that you wanted to have maintenance fees in Cryptonite to control dust but you were having problems with the actual mechanism of deciding the value, but having the stakeholders voting on it seems to be a good solution. Nxt is going to implement (or has already implemented?) voting by stakeholders. It is probably worth seeing how they do it, maybe it is applicable to Cryptonite.

Thank you. I would also like to have their opinion, especially Adam Back since I borrowed a lot from his homomorphic value scheme (https://bitcointalk.org/index.php?topic=305791.msg3294618#msg3294618). But every opinion is welcomed, I just want the paper to be reviewed.
Bybitcoin, if you have any doubt you can PM me and will respond ASAP. I know the paper ended up being too "dense". Maybe I should write a "lighter" version?

As promised, the new paper. https://drive.google.com/file/d/0B21vncLoIlIydUVGcjdDak1pRGc/view?usp=sharing

No, I apologize for the long absence. I was occupied during January and February. Also, I was not satisfied with the scheme so I spent the last month rewriting it. I will publish it here next week.

You would need to prove plaintext and random value equivalence between EC pedersen (additively homomorphic) and regular Elgamal (multiplicatively homomorphic). I don't think you can do it with discrete log equivalence protocol. Especially with only 2 points/values.

I haven't thought of that. But it's going to be more expensive than the CRT Elgamal scheme. A CRT Elgamal cyphertext would be 6 EC points. Your idea would be 3 EC points (1 from the commitment + 2 from Elgamal) plus the size of the ZK proof (probably going to be 3 EC points + 3 256-bit integers?). And it still would have the problem of requiring that users connect every 7 days to the network.

Digicoin: I'm going to wait a bit more because I'm trying to find a range proof more efficient than Schoenmaker's bit-by-bit proof. Also, I would like to see if I could introduce multi-input 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 mini-blockchain 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 mini-blockchain 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.

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 brute-forces 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;p-1]. 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;p-1]. 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 17-bit 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.

Adam, I reviewed the proof and you are absolutely right. For some reason I thought that wrap-around 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 256-bit 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.


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.

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.