Building the Next Generation of Crypto-Currency (developers required)

[bitfreak!]

The account tree structure and mini-block-chain approach is 100% the way I think things need to go.   I am attempting to implement a new blockchain and started designing something very similar to the white paper.   So on closer look, I have to give this approach strong backing.

We will have a github repo up very soon and it would help if you could contribute to the project. We plan to work with bitcoinj, are you any good with Java?

[1715148507]

1715148507

[1715148507]

1715148507

[bitfreak!]

The challenge here is that in the event of a chain split, this transaction could not be applied upon re-merging of the forked chain.  It also limits transactions to 'one per account per block' where as bitcoin could in theory have many different transaction per address provided they were all based upon different outputs and incoming transactions would not interfere with outgoing transactions.

That's a good observation which I hadn't realized. Although I'm having a bit of trouble seeing how your proposed solution would allow multiple transactions using the same account... my brain isn't working well today.

[aaaxn]

The challenge here is that in the event of a chain split, this transaction could not be applied upon re-merging of the forked chain.  It also limits transactions to 'one per account per block' where as bitcoin could in theory have many different transaction per address provided they were all based upon different outputs and incoming transactions would not interfere with outgoing transactions.

This initial scheme wasn't as bad as you say. You could include any number of tx in same block, because versions changes was applied only during block inclusion.
Anyway I spotted weakness in this approach already and posted refined proposal in wiki few days ago.
http://bitfreak.info/mbc-wiki/index.php?title=Transaction_Signing

[bytemaster]

I have done Java, though c++ is my primary language.    I think that we need to solve some of the design details that are language independent first and if there is a solid java implementation then I could be tempted to go that route.  

I have a strong need for many parallel chains with combined proof-of-work as a means of providing scaling beyond what a single chain could do.   So off of the top of my head some small changes I would make:

1) move the nonce to the proof chain and replace the block-hash with an accumulator (see ZeroCoin), this would allow all mining efforts for all chains using the same 'proof of work' to support as many chains as possible with almost no extra work.   The nonce would only add 8 to 12 bytes per proof header and thus would not really affect the result.

2) Define sector sizes and what goes in each sector.  Assuming you use something like sha224 you incur 28 bytes of overhead for each level in the merkel tree.  If you have a deep tree, then to 'address' a particular change would require 28 bytes per layer.   If you have a 'flat tree' then recalculating the root hash would require hashing your entire data set.    From a purely big-O stand point you want a hash tree that grows in depth as your data set grows.   The only question you have to consider is the 'branching factor' with 2 being the lowest and something on the order of 1 MB of accounts being the 'largest'.   From a network perspective, having each 'sector' of the dataset fit in a single UDP packet may be the right sector size.   Assuming each account is 48 bytes this means about 32 accounts per sector and each node in your merkel tree would in turn contain about 32 hashes 'children'.   The end result would be log32( total accounts size ) * sizeof(sha224) to prove a prove a particular 'account' has membership in the root hash.       Something to consider regarding making the sector size too large is the probability of a random transaction causing a change to a sector.   If 1% of all addresses see changes in every block and your sector size is 128 then chances are *every sector* will change every time and thus you have little savings.  

    To counter this 'random' behavior, free slots should be deterministically selected from the most-frequently changed sector first.   In fact each block should not just update/replace certain sector, but instead should 'sort' the addresses by least-recently accessed.   So, assume 5 addresses change in 5 different sectors resulting in 5*32 addresses that are part of a changed sector.   Users would have to fetch entire sectors at a time anyway so we might as well use the fact that these sectors have 'changed' to re-sort all 5 sectors moving the 5 changes into the same 'new sector' and moving the least recently changed into other sectors.   This will result in a 'hot set' and a 'cold' set and thus minimize the total number of sector fetches that must occur.  

   Ultimately you need all accounts to be accessed via a hash table and to validate that you have the 'entire hash table'.   Moving addresses around within the sectors would cause significant overhead in updating your hash-table index that allows you to find the addresses quickly.  This might be 'unavoidable' if you want to minimize sync overhead as you would be trading CPU time for network time.  

3) Identify how splits / remerges will be handled.  I think the white paper fails to properly handle this issue along with handling multiple transactions from a single account in a single block.

[bytemaster]

The challenge here is that in the event of a chain split, this transaction could not be applied upon re-merging of the forked chain.  It also limits transactions to 'one per account per block' where as bitcoin could in theory have many different transaction per address provided they were all based upon different outputs and incoming transactions would not interfere with outgoing transactions.

This initial scheme wasn't as bad as you say. You could include any number of tx in same block, because versions changes was applied only during block inclusion.
Anyway I spotted weakness in this approach already and posted refined proposal in wiki few days ago.
http://bitfreak.info/mbc-wiki/index.php?title=Transaction_Signing

It looks like the solution posted on the wiki is the same solution I came up with, so we are all on the same page!   

[aaaxn]

I have done Java, though c++ is my primary language.    I think that we need to solve some of the design details that are language independent first and if there is a solid java implementation then I could be tempted to go that route.  

I think we should put design together in wiki before touching code.
I already made a page regarding account tree implementation. I think we should just stick with binary tree.
http://bitfreak.info/mbc-wiki/index.php?title=Account_Ledger

EDIT:

1) move the nonce to the proof chain and replace the block-hash with an accumulator (see ZeroCoin), this would allow all mining efforts for all chains using the same 'proof of work' to support as many chains as possible with almost no extra work.   The nonce would only add 8 to 12 bytes per proof header and thus would not really affect the result.

As for merged mining I think it would be nice to include it, but I need to think it over. Do you know any good quality resources where it is described?

Ultimately you need all accounts to be accessed via a hash table and to validate that you have the 'entire hash table'.   Moving addresses around within the sectors would cause significant overhead in updating your hash-table index that allows you to find the addresses quickly.  This might be 'unavoidable' if you want to minimize sync overhead as you would be trading CPU time for network time. 

I think we should treat account ledger as just list of accounts. Account never changes its place on ledger unless it is emptied. This way we can address accounts by just its offset in ledger. This would enable us to make transaction a lot smaller because offset would fit in 5 bytes while public key is 32 bytes.

[bytemaster]

I have done Java, though c++ is my primary language.    I think that we need to solve some of the design details that are language independent first and if there is a solid java implementation then I could be tempted to go that route.  

I think we should put design together in wiki before touching code.
I already made a page regarding account tree implementation. I think we should just stick with binary tree.
http://bitfreak.info/mbc-wiki/index.php?title=Account_Ledger

EDIT:

1) move the nonce to the proof chain and replace the block-hash with an accumulator (see ZeroCoin), this would allow all mining efforts for all chains using the same 'proof of work' to support as many chains as possible with almost no extra work.   The nonce would only add 8 to 12 bytes per proof header and thus would not really affect the result.

As for merged mining I think it would be nice to include it, but I need to think it over. Do you know any good quality resources where it is described?

I recently stumbled across these two papers which show that it is possible to prove a 'hash' exists in a fixed sized accumulator.  This is the basis behind ZeroCoin.

http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf
http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

[lexxus]

I think we should put design together in wiki before touching code.
I already made a page regarding account tree implementation. I think we should just stick with binary tree.
http://bitfreak.info/mbc-wiki/index.php?title=Account_Ledger

We should also choose the "slot" size optimaly for the Account Ledger tree.
We can use the results from http://ecommons.library.cornell.edu/bitstream/1813/5655/1/TR2004-1944.pdf

[lexxus]

I recently stumbled across these two papers which show that it is possible to prove a 'hash' exists in a fixed sized accumulator.  This is the basis behind ZeroCoin.

But why we actually need an accumulator here? Can we just add the transactions to the block and mine it as usual? We can have a separate account ledger for any other currency to store balances.

[aaaxn]

I recently stumbled across these two papers which show that it is possible to prove a 'hash' exists in a fixed sized accumulator.  This is the basis behind ZeroCoin.

http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf
http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

It is just theoretical work. We would need already implemented stable libraries.

[bytemaster]

I think we should treat account ledger as just list of accounts. Account never changes its place on ledger unless it is emptied. This way we can address accounts by just its offset in ledger. This would enable us to make transaction a lot smaller because offset would fit in 5 bytes while public key is 32 bytes.

Great insight, except these slots can be reused if the balance reaches 0.  To safely use just offsets would require that the slot be empty for 24 hours or so before being reused.

[bytemaster]

I recently stumbled across these two papers which show that it is possible to prove a 'hash' exists in a fixed sized accumulator.  This is the basis behind ZeroCoin.

http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf
http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

It is just theoretical work. We would need already implemented stable libraries.

I have contacted the ZeroCoin author attempting to get his implementation for ZeroCoin and creating such a library.   Even without a full implementation, this chain could be designed to potentially work with merged mining by moving the nonce but just use a simple non-merged-mining hash for initial versions.

[bytemaster]

I recently stumbled across these two papers which show that it is possible to prove a 'hash' exists in a fixed sized accumulator.  This is the basis behind ZeroCoin.

But why we actually need an accumulator here? Can we just add the transactions to the block and mine it as usual? We can have a separate account ledger for any other currency to store balances.

THis would be for the proof chain and would allow people to search for proof of work on multiple chains at once without requiring any chain to be overly bloated. 

[aaaxn]

I think we should treat account ledger as just list of accounts. Account never changes its place on ledger unless it is emptied. This way we can address accounts by just its offset in ledger. This would enable us to make transaction a lot smaller because offset would fit in 5 bytes while public key is 32 bytes.

Great insight, except these slots can be reused if the balance reaches 0.  To safely use just offsets would require that the slot be empty for 24 hours or so before being reused.

One problem I see with instant pruning is when receiver account is emptied while there is pending tx which sends funds to it. I think we should add tx validity rule. Tx has block number under which they were created. I think we could just drop transaction which has this block earlier than last slot pruning. Introducing delay is still good idea and it should be done too.

[lexxus]

THis would be for the proof chain and would allow people to search for proof of work on multiple chains at once without requiring any chain to be overly bloated. 

But accumulator can only check if it contains an element but not how they are linked, right? I mean for "proof chain" you need to have a linked list and accumulator cannot reproduce it.

[bytemaster]

If I was mining for Namecoin and Bitcoin I would create an accumulator that included the hash of the block-header for both.  The block-header for each chain would contain the previous node in that chain.

Then when I found the work, I could submit  accumulator + namecoin header hash + key  as the proof of work for the namecoin chain and accumulator + bitcoin header hash + bckey to the bitcoin network.  Thus I solved 2 blocks at once, but each block still has a unique previous hash.

Of couse if the two chains have different difficulties it may only work for namecoin and not for bitcoin unless the resulting hash was good enough for both.

[aaaxn]

Assuming each account is 48 bytes this means about 32 accounts per sector and each node in your merkel tree would in turn contain about 32 hashes 'children'.   The end result would be log32( total accounts size ) * sizeof(sha224) to prove a prove a particular 'account' has membership in the root hash.      

You mean 32-branches at every level of tree or just joining accounts in 32 blocks and construct binary tree over such blocks?
If you mean former then to prove membership you need to include all siblings on your path to leaf which means 32 * log32(accounts number) * (size of hash)
If you mean latter you get 2 * log2(accounts / 32) * (size of hash)

[aaaxn]

If I was mining for Namecoin and Bitcoin I would create an accumulator that included the hash of the block-header for both.  The block-header for each chain would contain the previous node in that chain.

Then when I found the work, I could submit  accumulator + namecoin header hash + key  as the proof of work for the namecoin chain and accumulator + bitcoin header hash + bckey to the bitcoin network.  Thus I solved 2 blocks at once, but each block still has a unique previous hash.

Of couse if the two chains have different difficulties it may only work for namecoin and not for bitcoin unless the resulting hash was good enough for both.

You could do it with simple hash tree. You include root hash of merge mined blockchains headers and every single chain can prove its inclusion with 2 * logN hashes. I think its affordable and does not need inclusion of new untested and potentially complicated algorithms.

[BitcoinAshley]

Instead of another "******Coin", it's better to take a good ISO currency code from the beginning, like Ripple did with XRP. It must start with X then. Something like XCC, i.e. CC for Crypto Currency.

I understand, but your statement is somewhat of a non-sequitur. The naming convention "****coin" is not at all incompatible with an ISO currency code starting with X. The USD could be called "DollarCoin" and the ISO code would still be USD. So this currency could be called "FailCoin" and the code would still be XFL or XFC or something like that.
However, it was suggested to stay away from the _____Coin convention, and I think that's probably a good idea provided we can think of a non-stupid name - but I just wanted to point out that this convention is not inherently incompatible with an ISO convention. It is just the Bitcoin community's resistance that prevents XBT from being adopted; not that the name "bitcoin" itself prevents this code from being used.

[bitfreak!]

Ok after some discussion with other members, the name has been decided and a github repo has been created.

The name we are going with is Peercash and the repo can be found here (it's still empty right now):
https://github.com/peercash/peercash

Currency code: XPC

The name probably isn't as awesome as it could have been but it was hard to come up with something unique and with the domain name still available. Still I think it's a pretty good name and describes what the project is about so I'm not unhappy with the decision.

The concept is still being fully developed in the project wiki and aaaxn probably wont be around for a little while, so the real development still hasn't started yet. However if anyone wants to start contributing to the project repository that is fine.