Bitcoin Forum

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 (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 (https://drive.google.com/file/d/0B21vncLoIlIyUldiZTRxSTYyNGc/view?usp=sharing)

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://bitcointalk.org/index.php?topic=713538.0

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

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.

Very nice! Have any plans of implementing this?

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 (http://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.

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. :)

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 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).

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 128-bit security with Paillier you need 3kbit keys and 6kbit ciphertexts.

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 (http://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.

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

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?

You're referring to another scheme committed transactions http://www.mail-archive.com/bitcoin-development@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 selfish-mining 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

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.

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 (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.

When will your paper be updated with your new findings?

[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

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.

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 (non-decryptable) 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 schnorr-related 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

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.

Well presuming we're talking compressed points, thats 256-bits per point or value, then I think doing what I said should be 1x 256-bit point homomorphic value, 2x 256-bit elgamal encryption, a proof of discrete log equivalence signature (2x 256-bit) so 4 values.  4 vs 6, net saving?  Maybe I missed a point not sure without writing out the protcool.  And the CRT scheme while interesting is kind of shiny and new and slowish to decrypt.  It looks ok to me, in terms of crypto-conservatism; but I think this elgamal equivalence proof etc is even more conservative.  (And so is the schoenmaker's range proof IMO).

Adam

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.

What happened to this? Has it been proved to be impossible? 

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.

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

Very nice.. I hope to have Adam Back and Gregory Maxwell's opinion about this new one as well. Meanwhile I will try to digest the content by myself!

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

I am still getting around it, but sure, I will pm you if I find some part of it questionable. Yet it may take me a lot of time and courage to come up with a critique of your model, since I am not a cryptographer, but rather a number theorist. Therefore I hope Adam come on board sooner than later :)
About a lighter version, I guess no. You may need a more accessible and lighter presentation of your model for general audience later, when and if your technicalities get approved by the mentioned experts and is ready to be implemented.

Very nice work once again. I like the idea of using temporary addresses for every transaction, it seems to be a powerful way of increasing privacy. If I'm understanding your proposal correctly, the temporary addresses created by transactions are essentially what you store in the account tree, or you could also say that the account tree essentially contains all the unspent outputs from transactions (aka the receipts). What you have proposed is more similar to Bitcoin than the MBC scheme because it revolves around unspent outputs and brings back concepts like change and coin minting without inputs.

At some point in the future Bitcoin developers may figure out a way to compress all the unspent outputs into a compact structure which can be shared among peers much like in your scheme. At the end of the day your scheme might not end up being much more scalable than Bitcoin. But since your scheme, like the MBC scheme, doesn't use tx scripting, that allows you to implement all these clever mathematical tricks to produce a high level of anonymity and privacy while still remaining much more scalable than Bitcoin in its current state and all current anon coins.

Obviously it wont be more scalable than the MBC scheme but the original scheme doesn't provide the remarkably high level of anonymity that your scheme does and anonymity always comes at a cost. I also noticed that your new solution to preventing small value outputs (aka dust) is to enforce a minimum value output. Micro-transactions are much more costly in your scheme compared to the MBC scheme so I can see why you would gravitate towards that solution but it still seems like a rather poor solution to me, especially if the minimum value were to remain static over time.

A better solution might be to simply have miners enforce a minimum transaction fee. I've never really been a fan of the Proof-of-Stake mechanism but one reason I think PoS can be truly useful is for allowing stakeholders to vote on the minimum transaction fee and other important values such as the maximum block size. The problem of pruning dust really is one of the hardest things to solve I think. Sacrificing micro-transactions for more scalability is probably the best solution for your scheme but there are definitely better solutions for the MBC scheme.

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.

Well there are no unspent outputs in the MBC scheme which is why I think your scheme is closer to Bitcoin. If I were to send 1000 micro-transactions to the same address using Cryptonite the account tree would only grow larger on the first transaction, but if the address was already in the account tree before I sent the first tx then the tree wouldn't grow at all. In your scheme the tree would grow for each of those 1000 transactions because you're recording unspent outputs rather than a balance sheet like Cryptonite. And that is the main reason why Bitcoin will never achieve the level of scalability that Cryptonite has, despite what some other people might claim.

Yeah I've thought about it but it's obviously not going to be the easiest thing in the world. It's also very hard to decide when and how the maintenance fees should be subtracted from address balances even if you know what the maintenance fee should be. There always seem to be serious difficulties involved regardless of how the problem is approached.

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.

Is there any plan or desire to implement this anytime soon?
Of course after a final review of the scheme by the experts.

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.

One way is to get more publicity after a final review by some experts, to attract talented coders take a part.
Another way is to place a presale of let say 5% to 10% of the total supply and use the collected (btc) fund to shape a group of professional coders for implementing it asap.

If this concept goes 1/1 into a coin with fair distribution algo, low inflation and no premine or other ripoff crap, its definitely a buy.

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 agree, just mentioned both possible ways, to clear it out.
Also imitating btc stats including total supply, distribution curve or even lowering the inflation is most advisable. But the time between blocks should be much shorter, 1 or 2 minutes would be ideal.
The only thing I don't like about cryptonite is its 10 years flat high inflation rate. Unless a coin has an existent market to support and use its supply from the day 1, high flat inflation would scare people off. Moderate speculative atmosphere (I don't mean pump and dump) is healthy for any growing economy.

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 (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%.

Agreed, you detailed the points precisely.

It goes live at block 445,000, in about 9 hours. (Check the countdown here>  http://jnxt.org/countdown/?block=445000)

You can vote by stake, asset, mscurrency and you have options weight these votes too. It is pretty powerful. Here is a teaser video, starting at the time Alex talks about this > https://www.youtube.com/watch?v=dhJgz6hpHXg&feature=youtu.be&t=68

Comments, once it is live, would be welcomed.

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

I am wondering why not consider your scheme as one of the earliest candidates for the sidechains to be embedded with the bitcoin blockchain. Adam Back and Gregory Maxwell both have had a glance at your scheme and they are the very founders of the sidechain proposal. I say this because two of bitcoin foremost problematic issues are scalability and anonymity. Having the total supply of this coin less than the total supply bitcoin has and setting the 1:1 pegging proportion makes this coin economy more precious and dynamic and also guarantees that the bitcoins still in circulation never cut to zero, as they can not all become pegged in the new chain.

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.

@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.

Good news: http://www.coindesk.com/blockstream-open-source-code-sidechains/
We would all know much more soon, by their code release.

Hi, All-- 

By an interesting coincident of timing bffranca asked me two days ago to comment on his latest document.   I pointed out some problems with the variable selection in the description of the range-proofs that was making it hard for me to follow what he was describing, and that the particular discussion didn't appear secure (the hashes only occurred once in the verification equation so the proof appeared to be vacuous), this may just be a misunderstanding on my part caused by the equation markup mistake; I'd elaborate further but the document is down. I certainly don't blame Bffanca there-- Adam's post that described these proofs was dense and not easy to decode. My own approach was to first reinvent them from scratch, along the way I came up with a new ring signature generalization and a construction that is highly efficient.

At the same time, I've been working for some time on a similar system for Bitcoin which I've posted about here: https://bitcointalk.org/index.php?topic=1085273.msg11572844#msg11572844 which may be of some interest to some.

I had no idea that Bffanca was continuing this work after the first pass where Adam and I pointed out the need for range proofs until his recent contact.  Had I know about it previously I would have shared my progress earlier!  In any case, all my work is public now, along with a reasonably high performance implementation of the crypto and an integration into a testnet sidechain.

I'm not convinced that I've extract all the efficiency possible from this scheme yet; I was still exploring the use of balanced signed digit encoding (e.g NAF) to try to get the a further decrease... but wanted to get a working system out for people to play with and that meant I couldn't just keep optimizing forever.

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 (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 (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 (https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf) describes the use of BLS signatures for  multi, threshold and blind signing.

@Maxwell: I was hoping to see a modified version of mini- blockchain scheme amongst your sidechains candidates or to say elements. Did you consider it at all?
And if you didn't, why? Is it because the mini-blockchain is not a secure ledger cryptographically? Or because it is not feasible to attach such a mini-sidechain to bitcoin?

I don't think it's all that interesting: It requires that you trust the miners implicitly for the history, and if you're willing to do that you can use SPV which is much more efficient. And, I say this as the person who originally proposed state commitments in 2011: https://bitcointalk.org/index.php?topic=21995.0

If, for whatever reason, one really is interested in an in-between mode: a side effect of elements alpha witness segregation is that you can sync the chain while skipping 2/3 (to 95% with CT) of the data, but still have perfect security for the utxo set.

The txout commitment schemes have a non-trivial cost for full nodes as the txout set becomes large, e.g. requiring on the order of 20 times the amount of I/O--  so a one time miner trusting init takes less bandwidth but then you have much higher IO and CPU ongoing; so it's not actually clear to me that they're a win; even ignoring the security trade-off... which is part of the reason that they haven't moved forward in the Bitcoin space.

Some of the other things in the miniblockchain stuff are just incorrect. Like it claims to not have transaction malleability; but it does due to the inherent DSA malleability. I don't recall other features you might have been looking for.