Topic: [CLOSED] $20,000 Mini-Blockchain Implementation - page 3. (Read 10068 times)

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

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.

interesting concepts.

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

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.

It looks like he deleted his post or I'm going crazy. Here's the link: Weaknesses and attack vectors

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

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.

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

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

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

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.

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.

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.

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.

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.

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.

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.

Correct.

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

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.