[BitShares] Proof of Minimal Work Concept Feedback Wanted

[bytemaster]

... man in the middle ...

So there's a misunderstanding here. You seem to assume these attacks require me to control all nodes connected to my target. I don't. I need one connection, or possibly a majority of connections (Sybil attack) to the target. Either one is relatively easy to achieve in an anonymous network.
Bitcoin is completely, verifiably secure as long as I have at least one honest node in my connection pool. And then it still has some (weak) ways of warning me that things look wrong if I don't even have that (although it's not something I'd rely on).

The hard problem is when half your connections say one thing, and the other half say another. One half is honest, which is it?
That's what the attacks I outlined above exploit. That's what you need to solve if you want a solid bitcoin competitor.

I'll just reiterate the attack vectors, emphasising the information a node has access to (so you can see that it doesn't rely on isolating it from the network):

1. A node is bootstrapping. It has two connections: the first from an honest node feeding it the actual history, the second feeding it a fake history forked right at the genesis block (or other appropriate checkpoint) where the entire set of addresses is controlled by the same person (since they've mined separately for that time), the fees are zero (because it doesn't matter which actual address has the coins, it's all the same person), and a lot of money moves all the time. What criteria are you using to pick the correct chain?

2. The 10-minute window is closing (whatever criteria you use to decide that). Some nodes have a clock 10 seconds ahead, some clocks 10 seconds behind (probably a bell-shaped curve of some sort). I broadcast a zero-fee valid block directly to nodes at the right time such that half the nodes think "It's too late, not accepting this" and half the nodes think "Still on time, accepting". How do the nodes get back in agreement?

You can see both these attacks assume that honest nodes are present (even possibly majoritary). There's no MITM here. In fact at first glance I don't even need a lot of nodes, just highly connected ones (which is trivial to achieve if everyone connects in an automatic, no trust required fashion).

This is a very thoughtful post, PM me a BTC address.

I think I have figured out something fundamental that solves all of these problems.   Everyone who owns BitShares has financial incentive to mine for free because every block found that pays 100% dividends benefits their holdings.   Anyone who wants to mine for-profit does so because the ROI on their mining effort is greater than the dividends they would receive on their holdings.

How does this work out... someone who has 1% of the hashing power but 2% ownership is better off mining for free. Someone with 2% of the hashing power but only 1% of the money supply is better of mining for profit.

What is the economic outcome of this?   Those who 'own the money supply' set the price paid for mining.  If they want more network security they stop mining for free, if they want more returns they start mining for free.   The result is that the market sets the mining fee and therefore the difficulty level.  

Thoughts?

[bytemaster]

Please help me understand what exactly your proposal is.  As I got it, in the current revision of Bitshares, a miner can decide how much of the fees he wants for himself and how much is going to be paid as dividends.  And the block chosen is that by the miner who takes the least fees?  Is that correct?  Sounds like an interesting idea in principle to me.

It also sounds a little like bidding in an auction - and I think miners have the incentive to bid "just a little less" fees than any of their competitors in order to be awarded the fees.  When do miners publish their blocks - all together after the 10 minutes, or as soon as they have them?  It seems to me that in the latter case (if you are a miner and publish your block with an "offer" right away) you are basically just asking your competitors to bid a little lower in order to get the block, so you wouldn't do that.  Instead, everyone will try to release his/her block as close as possible before the 10 minute time out.  Wouldn't they?

Please let me know what you think about that, and please excuse if I understood something completely wrong.  I also have some more ideas / comments, but want to be sure about my understanding before I make them.

Please clarify this point:  As I see it, miners trying to (honestly) contribute to the network have a tough decision to make from a game-theoretic point of view:  Namely when and with what fees to submit their valid block, so that it has the best chances to be accepted as the one with lowest fees.  If they submit right away, others may use this information about their competitors to submit blocks with just a little less fee - thus it may be a complete waste of efforts to even try mining a block and submitting if there's still too much time left of the 10 minute window.  On the other hand, if every miner waits until the last second, that will directly lead to a very instable condition of the network because of time-differences (in fact, the competition for lowest fees directly amplifies the weakness mentioned in the posts above about time differences).  Furthermore, this model seems much more "unfair" than Bitcoin's with respect to mining - you not only have to try long enough, but also choose the right strategy in determining your fees.  I can imagine that this will turn away a lot of potential miners after they tried a little, so that someone with a particularly good strategy on choosing his offer can become a near-monopolist.

And no, I also don't think that your system will provide for more decentralised mining just for those reasons:  The more hash power someone has, the better chances he has in finding a valid block still in time with lower fees offered after some competitor submitted a block, and thus they have good chances on getting most blocks accepted so that others get no rewards at all for their tries.  This will discourage them, and thus the strongest miner survives (IMHO this tendency is much stronger in your system than in Bitcoin).

What do you think about that?

I think you brought up very good points, please send me an address.

[EmperorBob]

... I think I have figured out something fundamental that solves all of these problems. ....

Unfortunately changing the incentives does not affect the behavior of an attacker that isn't invested in the main chain. The two attacks I've outlined do not require the attacker to actually be invested in BitShares before attacking, so incentives won't work to ward him off.

someone who has 1% of the hashing power but 2% ownership is better off mining for free

Actually the formula is:
  1. 100% of the fees for a block go to the winning miner (lowest fee)
  2. The remainder is shared proportionally to all holdings.

Assume I'm making a block and I own 20% of all bit shares, but only 1% of hashpower. For simplicity assume the average accepted fee is around 50% of the total reward. If I mine successfully for no fee I get 20% of 100% of the total reward. If I mine successfully at the accepted fee (so 50%), I get 100% of 50% (the mining reward) + 20% of the remainder, for a total of 60% of the total. I'll mine successfuly only 1% of the time, the rest of the time I only get my share of the remainder (20% * 50% = 10%)

So my expected return is:
  1. Don't mine: 10% of all block rewards
  2. Mine for free: 10.2% of all block rewards
  3. Mine for average fee: 10.6% of all block rewards

It really doesn't matter what the exact numbers are, you always get more money by charging the fees you can get away with, unless you own 100% of the BitShares (At which point, who's making transactions? It's all one guy). Maybe there's a small incentive to help drive down the average fee if you have large holdings, but I don't see it working out properly.

Also why does it matter how many miners there are? Isn't the point of your proposal to avoid relying on proof-of-work?
I think you need to spell out in very explicit detail what your mechanisms for node agreement are. I'd like to help but you're not giving me much to work with right now.

[bytemaster]

I have determined that proof of work is required and that consensus only works if you have trusted public companies affirming the valid root.   So the choice is between requiring trusted authorities and proof-of-work... so I choose proof-of-work.

Ripple requires trusted nodes... and bitcoin doesn't.    Ripple is faster and confirming state as a result of their design, but requires extra trust. 

Thank you all for helping my work through the design space.