[CLOSED] $20,000 Mini-Blockchain Implementation

[Baldassare]

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

[bitfreak!]

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.

[Cryddit]

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.

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.

[Cryddit]

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. 

[bitfreak!]

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.

Correct.

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.

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

[CasualSam]

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.

[bitfreak!]

Is it at all possible for an attacker to create an account node with the exact same hash as an existing account?

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.

[Cryddit]

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.

[CasualSam]

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.

[bitfreak!]

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.

[bitfreak!]

The major identified functional deficit is that a client requesting an account balance must entirely trust a node to return the correct value.

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?

To a lesser degree this also impacts new nodes that are attempting to acquire the full ledger.

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]

Thanks for taking the time to read all that.

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.

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.

[bitfreak!]

I'm going to have a go at implementing your system (with the merkle tree).

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

[jeremysalwen]

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

[FrictionlessCoin]

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

[bitfreak!]

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.

Check your personal messages.

I was thinking about the issue of an attacker rewriting the entire chain once the mini-blockchain is forgotten

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

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

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.

[jeremysalwen]

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

[bitfreak!]

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

[btc1210]

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.

[CasualSam]

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