Bitcoin Forum

This bounty is now closed as per the last update. If you have any questions please send me a PM.

Also, I feel like developers will be much more willing to work on fulfilling these bounties if I can provide some way of ensuring that they will be rewarded the bounty upon completing the task, but I'm not really sure the best way of doing that. So if you have any good ideas relating to that let me know.

You could use an escrow service for that.

Can you expand on how that would work and what services I should take a look at?

An escrow service is basically a middle man. You send them the money in advance and they will hold it until someone completes the job. Then they will transfer the money to that person. If a set date expires without someone completing the job they will transfer the money back to you.

The forum has several trusted escrow members like JohnHamilton (https://bitcointalk.org/index.php?topic=254369.msg2706951#msg2706951) and escrow.ms (https://bitcointalk.org/index.php?topic=235452). Click their names to visit their threads. You can also view their user profiles to see whst feedback they have received from previous transactions.

Hope this helps and good luck with your project. Too bad I can't code :(

There is a bit of problem with the mini-blockchain idea as presented here. 

A blockchain is secured by the work of finding preimages for hashes.  That's what you need to do in order to build a blockchain from least recent to most recent.  However, going the other way, you just need to start with the 'preimage' you want, plug in some arbitrarily chosen nonce, and run the hash function once.   So you could fabricate a supposed 'recent' block and then, with very little effort, construct a fake chain that leads back from it -- to the full length of your mini-blockchain.

So here is the issue.  An attacker can present hundreds of bogus mini-blockchains per second and the client has to figure out which one is real.  In the absence of a way to check things back to the Genesis Block, that's difficult.

I'm not saying the problem isn't solvable.  It's just kinda non-obvious.  One thing you need to do is to make sure it's more computationally expensive to create new blocks backward than it is forward.

I'm not sure that you fully understand the concept, the mini-blockchain is exactly the same as a normal blockchain except that after a certain number of blocks the transactions are pruned from the blocks. The remaining block headers form the proof chain and the proof chain feeds into the mini-blockchain, and that makes it simple to verify the mini-blockchain against the proof chain (meaning the proof chain with the highest cumulative difficulty). You can check the proof chain all the way back the genesis block, you just cannot check the transactions all the way back the genesis block because the transactions are discarded after I certain period of time like I just mentioned. The way that address balances are maintained without a record of every transaction which ever occurred is via the Account Tree. The only attack I know which could get around the security of this design is the Secret Chain Attack documented on the Weaknesses and Attack Vectors page of the wiki.

Thanks for the information, I'll look into the escrow option further.

No problem. Make sure to use a trusted member. $20,000 is a lot of money ;). Escrow.ms is a well known and experienced member.

Yeah that's what worries me, I'm not really sure how safe it would be to trust anyone with $20,000 worth of BTC. And as I mentioned, the final reward will be calculated by the exchange rate at he time the bounty is filled, so I'm not sure how that would work with escrow.

You would be welcome to create a project on CIYAM Open for this (https://ciyam.org/open) - it has a workflow process that locks in a chosen dev for a period of time (so no-one is wasting their efforts rushing to get a bounty) and for this project I would not charge any fee.

If the dev fails to deliver by the date and time that they had promised to then the task can be re-opened.

This is being used for the Moneychanger project as well as for the CIYAM project itself.

Also if you need an escrow then for a small fee I'd be happy to do this (check my trust rating).

I think escrow.ms is a good choice. Here is his trust record: https://bitcointalk.org/index.php?action=trust;u=76380

He recently escrowed a 18 BTC deal, so he's experienced with larger amounts of BTC. You could send him a PM and try to figure out how you are planning on doing it.

Thanks for the offer, but the problem is finding developers skilled enough to work on a project like this. That's why I created a bounty in the first place, because I found it very difficult to put together a team of developers skilled enough to work on this project. If there is a team of developers out there who think they can get the job done then I am more than willing to that route. And I will also keep your escrow offer in mind, because you strike me as some one I can trust to get the job done.

I'm working on a similar idea, but with only two components: account tree and proof chain. Also writing in python. Project is progressing, should be done in a few month.
Not really interested in the bounty.

I know how to code HTML, CSS..., but not professional. If you can tell me a way to learn them quick and thoroughly I am more than happy to do that.

Good luck on your request :D

p.s. USE ESCROW!!!

Well it does not necessarily have to be written in one of the languages I specified. If you can get the basic concept implemented without the extra components you will still be eligible for the first bounty.

Cool, I will be watching this thread and will report if I've made any progress.
Good luck by the way. This is the right direction for altcoins to take.

Great... moved to the alt-coin section. Now this thread has every chance in the world of being noticed by decent developers...  :-\

Don't worry too much - it's happened to other projects that have still ended up getting devs - I think that the "idea" more than where it is categorized will determine the result.

Thanks for the encouragement, I'm just not very optimistic anymore because I've been trying to find developers for this project for many months now. And this thread was already on the 5th page of the alt-coin section before I even noticed it was moved, which is extremely discouraging. Gaaahhh I guess I'll just have to suck it up and hope for the best.

Without a doubt "getting devs" is the hardest thing to do (and the major problem I've found in starting CIYAM Open).

Unfortunately they are very hard to come by - I might take some time to look into your project myself and see if I could take on some tasks but I can't promise much as I'm very busy working on my own project (like so many others are).

I was just looking at the Nxt coins and I noticed that it has removed scripts from the system.


Anyone looking to implement this idea should take a look at Nxt because the mini-blockchain wont use script either (scripts are impossible due to the way the Account Tree works).

Keep hope brother. You have a good idea here, someone will come along and make it a reality. :)

Ok after some thinking I am willing put some of the project funds under the control CIYAM Open (I'm thinking 10 BTC), but I will maintain control of the rest of the funds. I know I don't have any trust feedback but I have been a part of this forum since early 2011 and have been offering bitcoin related tools and information on my website for many years, so I think I have earned some trust in any case.

Perhaps a multi-sig solution might be even better (so the trust is spread).

BTW I don't think that many members would have a trust problem with you as I know you have been around longer than I have been.

I was thinking about that too, but multisig transactions require all parties to agree before the funds can be released, and I really don't want any more than 2 parties involved, so I'm not really sure there's a point. If we both hold a portion of the funds then the winner of the bounty can at least be fairly certain they will receive a partial reward from one of us.

Okay - I get that - so if I hold any funds I will GPG sign an agreement about the release of them to make sure that all is above board.

Trust is a hard thing to come by on this forum - and I very much value the trust that I have established so far.

Sounds like a plan, we can discuss the details further when I return, for now I need to get some shut eye. I'll be back to check on this thread later.

reserved

False, you can have m of n transactions so 2 out of 3 have to agree or whatever ration you set. https://github.com/spesmilo/sx is your friend there (look for Multisig)

@Bitfreak!

I'm going to take a run at this, but I want to be sure I've got the requirements right first.

When you say on the wiki page describing the Account Tree that it should be easy to reference an account by "offset and address" I'm guessing that by "address" you mean the key needed to spend to that account, but what do you mean by "offset?"

It wouldn't be hard at all to make it easy to reference an account by address alone.  That would make it equally simple to just ignore some extra data called an "offset" as being something I don't really need to find the account -- unless you mean that you also want to be able to look it up by offset alone, without needing the address for this other kind of search?

"Re-Mining of Lost Coins" Why stop there? While we're at it why don't we just increase the number of coins from 21 million to 42 million?

@Bitfreak!

Another requirements question.  When you say you'd like "recovery of lost coins" do you mean "recovery of coins sent to addresses/keys whose corresponding private keys have not been used in X time"?  Or do you mean "recovery of coins in addresses/keys that have not been used in *ANY* transaction (ie, neither the private key nor the public key has been used) in X time"?

I ask because it's possible that Alice lost the private key to one of her addresses many years ago, but Bob just sent coins to that address using the public key just last week.  Are the  coins Bob sent to be considered "lost" because the only key that could possibly spend them hasn't been used for many years, or are those coins (and all other coins in Alice's old account) to be considered "live" because the public key to that account was used only last week?

If we go with the first option, then once Alice's old account has been "recovered", as long as she doesn't reactivate it by using the private key that we assumed was lost, any coins sent to that address may be recovered immediately, even in the very same block as the tx that sends them.  

The first option seems more sensible to me, because the only idea that causes "recovery" to make any sense is the presumption that the private key to the address has been lost. Coins recently sent to that address do not indicate that it has been found.  

But the second option is more sensible in terms of orderly data structures.  If it's the private key only then we need to keep track of the last time each account was decremented, but we may never completely delete an account from our account lookup because if the account is "dead" it remains "dead" until the private key is used, and any amounts sent to it may be recovered immediately.  If it's both private *and* public key, then we must remember the last time the balance changed in either direction, but we can delete accounts completely when they reach zero, because the effect is the same if a new spend "creates a new account" as if a new spend is directed to an account that has been "recovered".

I have very similar concerns about this re-mining. Is there already a thread covering this tipic only. Just imagine I do not redeem my casascius coin for 50 years. Will it become worthles? Maybe I want to treasure some "paper wallets" in a time capsule. Please elaborate or link to relevant thread. THX.

Then casascuis won't make coins for blockchains that mine lost coins.

Not a problem for Bitcoin.  This is for altcoins.

The best way of doing this is dropping this "bounty" system and just hiring developers?

Is it really that mysterious?


Never mind that it seems grossly inefficient and a waste of resources to have "competition jobs" where people are developing in parallel, racing for the bounty prize.


Also, you might want to discuss this with developers to find out the timeframe and compensation for developing what you're talking about.


I get it that you have a budget, we all do, but realize that your budget dictates the quality, speed and interest you'll find in developing these products. In my estimate what you're looking for versus how much you're willing to pay for it is wildly off base. For reference, I've been a part of small HTML websites that were more expensive than what you're offering.

Someone stated "Devs are hard to find" in the thread. This is absurd. Devs that are willing to work under customer dictated terms that attempt to bypass the marketplace norms, maybe. I don't know too many development houses that would think these terms are fair.

Feel free to seek it out, of course, but all of this nonsense regarding how to find devs and how to make them feel like they'll get the bounty are easily solvable via contracts and directly hiring firms that develop software. The institution I work for never has a shortage of vendors who are willing to accept our money in return for software.

I didn't write that part of the wiki, but I think you're correct, we should only need to reference an account by the address.

Yes exactly, you are right about this as well. If it was done the other way then anyone could send coins to an address to ensure that the coins are never considered to be lost, which would defeat the purpose of the re-mining system.

Probably, I think there is a difference between hiring developers (where whatever they produce belongs to you) and this open source bounty system. Nothing prevents someone from following the requirements here, creating own altcoin, and after the release claim the bounty. Thus it is lower than market development rates. Plz correct me if I'm wrong, bitfreak.

In that case your coins would get re-mined under the assumption they were lost. You would have to transfer a portion or all of your coins to another address to prove that you still have control of the coins.

Developers are typically not hard to find, but when you require developers skilled enough to work on cutting edge crypto-currency technology which has never been built before, it is very hard to find developers. In the many months I've been advertising this bounty, Cryddit is actually the only person who has told me directly that he is going to try to implement this concept in order to claim the bounty.

EDIT: and if developers don't want to waste their time attempting to claim this bounty, then they should try to team up with other developers in this thread who have already said they are working in it.

I'm going to try to as well. But will use it for my altcoin.

I would highly recommend that you try to team up with Cryddit. There will be less wasted effort and things will get done quicker if you guys team up instead of working independently. 'Probably' does have a point about that.

This is exactly the case.  I'm implementing an altcoin myself, and the major requirements of this bounty (length limited blockchain, recovery of lost coins, reasonably trustable zero-confirm transactions)  closely resemble some of the novel features I had already intended to do anyway.   So I was already planning to write some very similar code.  If someone else is willing to pay a bounty for this particular set of requirements, and afterwards I still have rights to open-source, modify, and use the code produced, then doing this gets me about 80% of the way to the versions of these features I want to implement for my own system. 

It's earlier in my dev plan than I had intended to do it, but the set of requirements here apply to a transaction model much simpler than mine (I'm going to be using pay-to-script-hash and several different families of addresses with different properties) so it can exist independently of the complications I'll need to integrate it with.  Implementing this version will be easier and cleaner than what's going to eventually wind up in my code, but it'll still be a very good starting point for me.

FWIW, I think having the miner detect double spends is far too late for zero-confirm transactions.   It ought to be possible to repudiate a doubly-spent transaction within ten seconds, or the capability becomes one that won't be practical to use (in situations like checkout lines with people waiting behind you, or vending machines where you're just grabbing something on your way somewhere and don't have extra minutes, etc).  It doesn't matter if the double spend is "punished" or not; the merchant is still left holding the bag and that's _not_ okay!  I say ten seconds because that's roughly the amount of time it takes for a transaction to propagate across the Bitcoin network to 90% or more of the nodes and it'll only take a couple of seconds for an online merchant to check with ten or so clients at least a few of which are likely to have heard of the other transaction.

I am presuming that the proof chain needs to go back at least as far as the most recent "hard checkpoint" known to the client.  IE, the client can occasionally trim the oldest blocks from the proof chain, but only after a software update that gives it a later checkpoint to work from.

I'm also presuming that a "hard checkpoint" will be added to the client only when no blockchain reorg that reaches previous to that checkpoint is still acceptable or possible. 

Correct.

The "hard checkpoint" will hardly ever be updated because the proof chain will remain tiny for very for long periods of time.

Is it at all possible for an attacker to create an account node with the exact same hash as an existing account? The lack of a nonce field should make this much more difficult as you'd have to generate a new public key for every hash attempt.

I've got an idea for a much lighter account structure than a merkle tree but there are worse implications if the above attack is possible.

It would be possible but highly unlikely. I'm guessing it would be like trying to find a private key which already holds some BTC. I'm not really sure though, it will depend on the design of the account tree.

With RSA encryption at least, it would be exactly as hard as the effort spent trying to find the private key for an existing txout -- problem being that in order to accomplish either task you have to factor the modulus. 

With ECC, I'm not familiar enough to say for sure; but I think there are underlying geometric problems similar in scope for both tasks.

OK here is my attempt at a lighter-weight alternative to the account structure. I think it is interesting enough to post but I'm not suggesting it is better than the current method.

No merkle tree is involved. The ledger is just a loose collection of account objects and the master hash is the result of XORing all the account hash values together.

To update a specific account it is first 'checked-out'. This involves XORing the account's hash with the master hash (Master = Master XOR OriginalAccountHash).

After modifying and rehashing the account it is then 'checked-back-in'. This is the same XOR process (Master = Master XOR UpdatedAccountHash).

New accounts just need to be 'checked-in' and removed accounts are left 'checked-out'.

The check-in/check-out process ensures that the master hash is always equal to the combined XOR result of the acount hashes.

New blocks are submitted with the new master hash in the header. Every node that downloads a new block confirms the new master hash by performing the same XOR operations against the previous block's master hash. The master hash can also be verified at any time by rehashing every account and XORing the hash results together. This would rarely be necessary though.

To mitigate against various security issues the number of accounts should be stored in the block header. The total number of coins should also be known but this is derivable from the length of the proof chain.

The major identified functional deficit is that a client requesting an account balance must entirely trust a node to return the correct value. Some sort of consensus system would be needed to overcome this problem. To a lesser degree this also impacts new nodes that are attempting to acquire the full ledger.

CasualSam, that's a very interesting idea... using the check-in/check-out process you describe seems to be a very clever way of removing the need for a hash tree and at the same time it still allows modification of separate accounts without requiring the client to re-process the master hash from every single account hash. It seems like it would be a bit less secure than a hash tree design but putting the number of accounts in the block headers like you suggest seems like a decent way to recover some of that lost security.

I like your way of thinking.

I'm not sure I understand what you mean here. Why would a client need to request account balances from other clients? I assume you are talking about a situation where the node has no ledger information to look at? Wouldn't the same thing apply to bitcoin if one client was to ask another client for the balance of the address? Why would it have any reason to trust the other client?

This could actually be a problem imo. The hash tree design will allow nodes to acquire small portions of the account tree and validate that portion without requiring the full account tree. However in your proposed structure it would require all the account hashes before it could validate them against the master hash.

EDIT: removed unnecessary explanation.

Thanks for taking the time to read all that.


Yeah this is definitely the major failing of the system.

I'm going to have a go at implementing your system (with the merkle tree). I am new to bitcoin and this is a great opportunity to learn more. It's unlikely I will get any bounties, but I am happy to share whatever code I write.

Good to hear, but don't give up on your idea so quickly, it has potential imo.

Hey Bitfreak,

I very much like your mini-blockchain idea.  I'd like to implement it, but as it stands, I feel like it would benefit from further specification before I start writing the code.  If you could give me an account on the wiki so I could start outlining the data structures, protocols, and algorithms my implementation will use, that would be great.  I was planning on implementing the idea before I found out about the prize, but I'm really happy to have someone to bounce ideas off of.

Here's what I've fleshed out so far:

Account DB structure:  Merkle tree
While the "XOR of all accounts" structure is nice from the perspective of a thin client, as you pointed out, it makes things rather difficult to bootstrap, and corrupt or malicious information sent from your peers hard to detect (how do you know which block is bad?).

Merkle trees solve this distribution problem, and you can run a thin client almost as efficiently.  If you only want to track a single account, you only have to fetch a single "path" down the merkle tree.  If you're running a full client, the XOR system isn't better either, because if you want to actually verify that the transactions match up to the account balances,  you need to store all the account balances anyway, and need to have a fast way of indexing the accounts.  This is going to have basically the same overhead as a Merkle tree.  Rather than trying to retrofit the XOR system with additional data structures, we can just use the merkle tree which serves as a p2p distribution/thin client support/fast read-write data structure all in one. 

Mini-blockchain Security:

I was thinking about the issue of an attacker rewriting the entire chain once the mini-blockchain is forgotten might be remedied by attaching signatures to all the accounts, or some other scheme, but after I thought about it a bit, it's essentially a problem in communication complexity which is provably impossible.  /Someone/ needs to keep track of the old blocks in order for chain-rewriting to be detected.  But it's only necessary for a single person to have a copy of the old blocks to prove that a chain rewrite is invalid.  The way I think about it, the actual length of the mini-blockchain that is stored can vary as much as the user wants between clients, and a few clients can store the whole blockchain.  Of course, the issue of who is guarding against mini-blockchain rewrites, how that information is communicated and accepted by the network, and how to make sure there are incentives to catch this sort of attack still needs to be figured out (an idea which just occurred to me is that catching a block rewrite could be worth some percentage of the fake chain's proof of work, but we need to be careful that it can't be gamed in either direction.).

Compressing the mini-blockchain:

Assuming that you have validated your transaction history and account trees, you don't actually need to store the entire mini-blockchain on disk, just the initial account tree, the current tree, and then the transactions, which can be used to recreate any intermediate tree.

-Jeremy

Extremely interesting.  I will spend some effort reading your specifications.

Check your personal messages.

That's not an issue, that is what the proof chain is for. The only way to overcome the security provided by the proof chain is a secret chain attack (check the link supplied by CasualSam).

It is designed in such a way that no one is required to store anything except the mini-blockchain, and it wouldn't particularly matter if that's what everybody did (clients can however store as much of the mini-blockchain as they desire). It would only matter during an event such as a secret chain attack, but even then it's not entirely necessary to prevent the attack. Read more about the proof chain and the secret chain attack.

I wasn't able to find the link posted by CasualSam.  Could you repost the link please?

It looks like he deleted his post or I'm going crazy. Here's the link: Weaknesses and attack vectors (http://bitfreak.info/mbc-wiki/index.php?title=Weaknesses_and_attack_vectors)

I didn't even know there were interesting topics like this here.

This forum is crammed with a hundred copy-paste and ponzi-style coins.

Bitfreak:

The bounty for 'Re-Mining' is set at $3000. This is a lot to pay for a feature that won't be utilized for at least 50 years. Even as a selling point it is only marketable to those extremely confident in the longevity of your coin.

Is there any possibility you would consider withdrawing the bounty and adding it to the basic implementation? I think this would offer much better business value for your money.

Actually what I'd really like to see is the non-integral features moved into a new bounty leaving just the block-chain/proof-chain/address-tree in the basic implementation. This would still give you a demonstrable representation of the fundamental system concepts.

Basic Implementation Stage 1 - Bounty $10K (or more)
* Block-Chain
* Proof-Chain
* Address-Tree

Basic Implementation Stage 2 - Bounty $3K (or less)
* Should prevent reuse of signed transactions
* Should have guards against secret chain attack
* Should have improved ASIC resistance (check out ProtoShares and Quark)

Just an idea :)

interesting concepts.

Yeah I was thinking about removing that bounty anyway because there are some downfalls with coin re-mining I want to keep this implementation as close to bitcoin as possible.

Dear existing/prospective developers,

With the bounty system on offer there are a number of reasons why a team approach is better value than attempting to complete this individually.

* Higher chance of receiving the bounty. A team is more likely to beat an individual.
* The effort/reward ratio is maintained.  Bounty would be split fairly by a predetermined method (e.g. Tasks completed/hours worked/value added/etc.)
* Peer discussion and review. Strategies and difficulties can be discussed and worked through as a team.
* Flexible commitment. Work as much or as little as you want. If you have specialist knowledge but limited time perhaps you could act as a consultant and receive a split of the bounty based on the value you add.

If anyone would like to join a dev-team, please PM (or post here). If there is a positive response I’ll set up somewhere private to discuss further (ideas?).

I think that the offset is actually necessary. Consider the scenario where a new peer is trying to obtain a full copy of the account tree. The peer needs to be able to request parts of the account structure to build the complete tree. I can't see how you'd do it without the following functions:

GetBranch(AccountIndex)
GetSubTree(AccountStartIndex,AccountEndIndex)

Edit:
It seems that it is an attribute of the merkle tree that every account does have an immutable index which is an entirely valid unique key. If this is true then it would be more efficient (storage-wise) to reference accounts by index wherever possible (transactions, etc.). In fact this opens up the possibility of having multiple accounts for a single key sig (not saying this is desirable).

Merkle trees. I need a way to store them. The btc method means lots of inserts. I wasted a fair bit of time on this issue especially considering it is entirely client side. Just wanted to say I am going to use the btc method unless there is objection.

Any additional devs please contact me as I'm sure you'll be able to add something to the team.

What language is the code written in?

OP I would like to try a pathetic attempt to disprove the concept and advise you to change the design.

0-confirmation with punishment sounds nice but won't work in my opinion.

Scenario:
I'm Bob a malicious person. This coin has a big distributed network after it has become popular.
I spend a coin with the minimal fee so miners put me low on the queue this way it will take some time before I'm processed.
I not only spend once or double but a million fold in a fraction of a second through my modified client.
Since the blockchain is distibuted chances are that many clients will process these transactions parallel and not see the double spending for a while until quite a few transactions have come through.
My money arrives at a good part of the million accounts and my client send it on to another million account without double spending making the last transaction legal.
Since you only need 0-confirmations you can ofcourse instantaniously spend.
My first account will get the penalty million-fold and goes negative but who cares I will discard that account. My other accounts at the receiving end will have done a legal transaction so they will not be penalized.
The blockchain has no way of getting back the money from the end user since it was a legal transaction. If it could you could scam the end user by sending money which will be retracted by the network.
I now have atleast doubled my money and flooded the blockchain with bad transactions.


You can send my $2000 in BTC to 1Ff5jhoHxBFksJhpcwnuKHLvWWPA99kcts :D

For now I'm prototyping some of the trickier features in C# which is most productive for me. It will probably be in implemented C++ and based on an existing open-source coin. It is hard to tell how complete bitcoinJ is and whether it would be suitable base. I am less rusty in java but have a good few years C++ (low level copy-protection stuff).

Overall I have good technical and analytical skills and but very little experience with bitcoin or distributed systems. I'm attempting this project mostly as a way to learn more and can devote up to 40h/week for the next couple of months.

While I'm willing to work alone I think a team approach is much more practical. I'd love to hear from anyone interested in getting involved. Most useful right now would be someone with better knowledge of bitcoin implementation details who can discuss implementation strategies,  help break it into tasks and work out some sort of development schedule with me.

Is there any chance the mods could move this back to "Project Development"? It is much more suited to the audience there.

It would be impossible for your account to go into the negative range. Every block which is added onto the blockchain cannot contain any transactions which make an account go negative. The wiki page about 0-confirmation transactions (http://bitfreak.info/mbc-wiki/index.php?title=Secure_0-confirmation_transactions) covers your scenario.

Ok, I have removed the extra bounty concerning the re-mining of lost coins, but instead of adding the funds to the main bounty I have created another bonus bounty which requires the implementation of a "Quantum-Safe Signature Scheme". That is something I meant to include from the very beginning because I feel it's important to build quantum-resistance into the system as early as possible.

For the Account Tree,  does the master hash reference all the accounts that have been created or just the accounts that have changed in the block?

For transactions that are created,  it would require a reference hash to something to prevent double spending.   What would that reference be if there the previous transaction was discarded?

I'm not sure I understand your question. A new block will cause changes in multiple accounts in the account tree, so the master hash would be recalculated just like any other merkle hash tree where the base data blocks are changed. The same process would be used in bitcoin when miners add or change transactions in their block (the transactions are structured as a merkle tree and the root hash is the equivalent of the master hash).

http://bitfreak.info/mbc-wiki/index.php?title=Transaction_Signing

The account tree is made of accounts.  Are these only the accounts that have changed during the block, or is it all the accounts for the entire block chain?

The merkel root for a block is calculated only for the transactions in the block.   

So I would gather,  the accounts in the master hash are just the accounts that have changed for this block?

Will a version of this using the GHOST protocol work?

That is, a block may have multiple parents?

The account tree holds all non-empty accounts that exist (that's why it's possible to have a mini-blockchain instead of a full blockchain).

I don't see why not.

Correct. Since it's structured as a merkle tree you only need to work on specific branches of the tree when something changes, but changing just one account will change the master hash.

When you talk about an Account tree... you mean an Address tree in Bitcoin terminology?

The account tree is a totally new concept, there is nothing like it in the bitcoin design. The account tree is basically just a database of all the non-empty addresses. It's structured as a merkle tree so that the network can easily keep track of changes and maintain the integrity of the data held in the database.

So one Account has multiple addresses?   Are these Accounts broadcast to the network?  How does an Address know that it is associated to an account?

With Bitcoin, the only two object that are broadcast are Blocks and Transactions.

Are you saying that in your system,  there Proofs,  Blocks, Accounts and Transactions that are broadcast?   Are there transactions?

Sorry I misunderstood your earlier question. Yes I suppose you could call the account tree an address tree because it holds information about all the non-empty addresses. The account tree is simply a hash tree where the data blocks represents individual accounts. The reason we call them "accounts" is because they hold more than just the address, each data block will also hold the balance of that address and some other information about the address. Each account will hold information about a single address only. All nodes will have a copy of the account tree just like the blockchain. The mini-blockchain works just like a normal blockchain and it holds transactions just like a normal blockchain, the only difference is that it gets trimmed after a certain period of time. When a new block is generated and propagated to all the nodes in the network, those nodes will use the transactions in that block to update their copy of the account tree and then they will recalculate the master hash of the account tree and make sure it matches the master hash specified in the block header, if it doesn't match then the block is considered invalid. I suggest that you read the mini-blockchain wiki properly, it explains everything in detail.

EDIT: it's also important to keep in mind that the transactions wont use scripts:

Clearly there is something missing here.   In Bitcoin,  Blocks and Transactions are what are broadcast in the the network.

What is broadcast here?  

I would think that transactions are broadcast.

So they are collected in Blocks.  So blocks contain transactions.

Or.... not in this case...  how are transactions consumed?

I am missing something here.

Also, I don't understand how you can update the global account when a peer doesn't see all the transactions.

It's the same thing here... what is so hard to understand about what I said. Miners will collect the transactions into blocks and then when a miner solves their block they will release it to the network. Then the other nodes will add that block onto their mini-blockchain just like they would for a normal blockchain. In Bitcoin that would be the end of it, and you'd need the entire blockchain to calculate the balance of any address because the blockchain has no concept of address balances, it's a continual ledger which keeps track of where coins are sent to work out the balances. However in the mini-blockchain design the balances are saved into the account tree, and when a new block is accepted onto the mini-blockchain the nodes will use the transactions contained in that block to recalculate the balances of the addresses in the account tree. A transaction will contain a simple command like "send X number of coins from address A to address B". So the nodes will simply carry out those commands by altering the balances in their account tree, if an account doesn't exist then it is added to the tree, and then when the changes have been made they will recalculate the hashes in the account tree.

Ok.  

Bitcoin is a P2P network,  so I have to understand what messages are sent.

(1) When are transactions no longer relayed by a node?   In other words,  when are they baked into an account such that they no longer are relayed?  What determines when a transaction is not relayed anymore?

(2) When the account tree is created.   Are accounts relayed through the network for other nodes to store and reconstruct?

(3) Which version of an account should a node accept?   Is there a block height embedded in the account? Is there a hash that relates the same account to a previous version of it?

(4) I need to understand the interplay of when transactions are sent and when addresses are sent.  I also need to understand what happens when a transaction is in conflict with an address and how to determine if there is a conflict.

Like I said, transactions are collected into blocks in the same way as Bitcoin transactions, so nodes would stop relying transactions in the same way as they do with Bitcoin. To be honest I'm not exactly sure how a Bitcoin node decides to stop relaying transactions.

Yes obviously the accounts are relayed through the network for other nodes to reconstruct the account tree. The account tree will be created after the first genesis block is created. Nodes will reconstruct the account tree when they are synchronizing with the network.

In order to determine which version of the account tree is the correct one, a node must first obtain the full proof chain and the mini-blockchain with the highest cumulative difficulty. The master hash of the account tree is contained in every block header so that when the node has reconstructed the account tree they can make sure it contains the right data. The block height can be calculated from the number of block headers in the proof chain and mini-blockchain so it doesn't necessarily need to be stored in the account tree, but it would probably add a bit of extra security to do so.

I'm not sure what you mean. I get the feeling you still aren't fully understanding the concept of how the mini-blockchain and account tree are supposed to work. What do you mean "when addresses are sent"? Do you mean when are portions of the account tree propagated across the network? Like I said, that should only happen when a node is synchronizing with the network. The mini-blockchain wiki has the answer to all of these questions, please read it properly.

It is pull based,  so any node can request older transactions.  So in this implementation,  a node may request a transaction that does not exist in any node.   So therefore,  there is some criteria when to throw away transactions.  What is that criteria?



Yes obviously the accounts are relayed through the network for other nodes to reconstruct the account tree. The account tree will be created after the first genesis block is created. Nodes will reconstruct the account tree when they are synchronizing with the network.
[/quote]
Does an account have an identifier or hash that will distinguish it from other version of itself in the network?




In order to determine which version of the account tree is the correct one, a node must first obtain the full proof chain and the mini-blockchain with the highest cumulative difficulty. The master hash of the account tree is contained in every block header so that when the node has reconstructed the account tree they can make sure it contains the right data. The block height can be calculated from the number of block headers in the proof chain and mini-blockchain so it doesn't necessarily need to be stored in the account tree, but it would probably add a bit of extra security to do so.
[/quote]
How is the account information requested from a node?  Do I ask the node, "give me account for block height 13?"   If the block height is already at 15, do I return an error?



I'm not sure what you mean. I get the feeling you still aren't fully understanding the concept of how the mini-blockchain and account tree are supposed to work. What do you mean "when addresses are sent"? Do you mean when are portions of the account tree propagated across the network? Like I said, that should only happen when a node is synchronizing with the network. The mini-blockchain wiki has the answer to all of these questions, please read it properly.
[/quote]
So are you saying that, once a transaction is included in a block it is never accessible or propagated through the network?   The problem is,  the P2P network is never certain until a number of blocks whether a transaction is in the block chain or not.   So you can't start transmitting account information until you have the requisite number of confirmations.

I'll be honest,  unless there is a specification of the network protocol, then this specification is incomplete.

Why would a node want to request an older transaction that is not being relayed? Oh... you mean transactions that have been previously included into blocks and not orphaned transactions? So what you're asking is what determines when the the transactions in old blocks are discarded? The answer to that depends on the length of the mini-blockchain cycle. If the cycle is set to a week then transactions will be kept by nodes for a week before they are discarded. Then the remaining block header becomes part of the proof chain.

Since the account tree is structured as a hash tree, yes, every single account in the tree has a corresponding hash obviously.

http://bitfreak.info/mbc-wiki/index.php?title=Network_synchronization

I believe my first answer should answer this too.

What happens when the block chain is forked?   Would there not be two sets of competing account trees?

In the case that an account tree becomes the losing tree,  I gather the protocol needs to go out in the network to refresh its info?

Yes in that case there would be two competing blockchains and two account tree corresponding to each chain.

Yes that is correct. If the losing chain is just a couple of orphaned blocks then there should be enough of a backup stored in memory to undo the orphaned changes. But then the nodes would need to query the network to catch up to the correct chain. In the case where the nodes cannot undo the changes then they will have to go through the resynchronization process.

So it may make sense for an implementation to have a LRU cache of transactions in the case of forks?

Because transactions are removed,  won't users lose the ability to have a record of their transaction?  Would it make better sense to hold like a year's worth of transactions and the Account tree is really just there for a check point mechanism?

Not necessarily a cache of transactions, a cache of the changes made to the account tree would make more sense.

Yes, without a blockchain which saves every transaction that ever happened it wont be possible to go back and examine old transactions. This may offer a little bit of extra anonymity however it's likely that some people will choose to store every transaction for historical purposes. Each node will have the ability to change how long they want to store transactions, but it cannot be any shorter than the cycle time of the mini-blockhain.

If you're going to save so many transactions you may as well just go back to using a full blockchain. The whole point of the mini-blockchain is to make the blockchain as small as possible so that the network becomes extremely scalable. The account tree is just a way to keep track of the address balances without requiring all transactions to be recorded forever.

Is a SPV client feasible with this kind of setup?

If you discard the transactions (and likely the merkle roots in the blocks) you aren't able to do a Simple Payment Verification that a transaction exists in a block.   Is there something similar where you can have a lightweight client?

I haven't really thought much about this but I believe it would be possible to do something similar. You could get the proof chain and all the headers from the mini-blockchain and then to check the balance of any given address you could just request a specific branch of the account tree which corresponds to the account you are interested in. The advantage of using a merkle tree is that you can acquire small pieces of the whole tree and confirm them against the master hash without needing the whole tree.

What about a solution that has both a Transaction Block and an Account Tree?

Not sure what you mean. Please elaborate.

What I mean is that instead of just the master hash on the block, there is also a merkle root that points back to the transactions in the block just like bitcoin.

Clients then may query for all the transactions or only the transactions up to a certain block.

That way you get the best of both worlds,  if you want the entire block chain you query all transactions,  if you want on only with a years worth of transactions, you query until the account tree of a year previous.   

Transactions are stored in the blocks the same way as in Bitcoin, so there will be a merkle root in every block just like Bitcoin.

It probably wouldn't be possible to get transactions from the previous year because the cycle time of the mini-blockchain wouldn't be anywhere near that long.

I still get the feeling you aren't really grasping the concept properly...

Actually I look at is as if the Account tree is a tradeoff.  

You need to keep transaction up to a certain period.  That is just how it works for any payment system.  and that is what users will expect.

However, for a duration say greater than 1 year or 3 years,  you want to archive those transactions.  To do so needs what you call the account tree that servers just as a snapshot of the transactions at a certain point in time.  

I think your proposal is interesting,  however I don't think you can discard transactions.

The whole purpose of the mini-blockchain scheme is to increase scalability. Just imagine if Bitcoin were to reach the level of traffic that Visa must handle on a daily basis, there is no feasible way that all those transactions can be stored within a blockchain which records every transaction forever. The transactions are the bulkiest part of the whole bitcoin scheme, so what the mini-blockchain scheme aims to do is limit the number of transactions which are required to be stored by every node down to only a week or less of transaction history.

There isn't really any trade off involved because users can save the transactions which correspond to their addresses if they want to keep a record of the transactions they have made, but there's no need for them to store any of the other transactions longer than the cycle time of the blockchain. But any node that wishes to save a year or more worth of transactions can do so if they are willing to give up the disk space required; the key thing is that no node is required to store any transactions longer than the cycle time of the mini-blockchain, and that enables anyone to quickly synchronize with the network instead of having do download gigabytes worth of transaction history.

Yes you can discard transactions after a period of time so long as you have a method of maintaining a secure ledger which records the exact balance of each address. That is what the account tree does. It is a compact snapshot of the entire system in a sense, but it's a snapshot which gets updated with every new block. The transactions in each block don't link back to other transactions like they do in Bitcoin, they simply issue commands which say "take X number of coins from the balance of address A and give them to the balance of address B". So long as the balance recorded in the account tree for address A holds at least X number of coins and so long as the transaction is signed with the private key of address A then the transaction will be accepted by the network. There is no need to look back at historical transactions, so they can be safely discarded when they fall outside the mini-blockchain.

Ok.   I  see your point.  Transactions can be saved by parties interested in saving the transactions, but these don't need to be globally broadcast.   

UPDATE: I am going to close this bounty within the next week because I've had this bounty open for a very long time and it looks like no one is currently working on it and I have several people interested in working for me directly in return for a weekly wage. I feel that this project will get done quicker if I pay a team of developers to work for a weekly wage, so unless there are any objections I will close this bounty within a week. If you are interested in joining the team and working for a weekly wage please send me a PM.