Topic: [BitShares] Proof of Minimal Work Concept Feedback Wanted (Read 1968 times)

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. 

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.


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.

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

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?

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?

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

The biggest problem is man in the middle attacks that isolate an individual from all outside information.   If someone can present you a forged chain and convince you to accept payment from them on the forged chain and you ship the goods before learning otherwise they will have stolen from you.    In theory Bitcoin suffers the same problem without checkpoints or knowledge of the expected difficulty.   

So the question becomes are there other means of preventing man-in-the-middle attacks and false chains that are both decentralized and relatively trust-free?  Seems like proof-of-work is both expensive, incomplete, and ultimately relies on outside information to verify you are on the proper chain.   In the March 2013 fork how did the average user know they were on the wrong chain?

There is a difference between 'dividends claimed' and 'dividends paid'.    Dividends paid come from transaction fees and block rewards, this number is defines the dividends per BitShare for all accounts.   This number is accumulated at the block-level until a an output is spent at which point the output can claim the proper percent of dividends earned. 

From a user's perspective, the client can always calculate the dividends due a particular output and thus can factor that value in when generating a transaction.  So a transaction that references a 1 year old output of 100 BTS could 'spend' 110 BTS via an output provided at least 10 BTS of dividends had accumulated since the output was included in a block.

It actually scales better than you think with an intelligent implementation.   Each block I update an accumulation table that will give me constant time lookup of the cumulative dividend percentage by coinage.  This table is only maintained for 1 year (hence the need to move your funds once per year).   The total size of this table is less than 1 MB per BitAsset or about 32 megs total.

So calculation of dividend will require for an unspent output X

0. find the first block with the X
1. for each block up in the blockchain:
1.1 find out which part of block reward was left for dividend payments
1.2 find out which fraction from a total amount of coins at that moment consituted X (i.e. you need to know the state of the network at that moment)
1.3 calculate the dividend payment for that block


I guess it scales, just wonder how well (e.g. assume that on general a user makes 1 transaction per week, with 10min blocks, you need to go through last 1000 blocks to calculate the dividends)

Ok.
Just to make sure I understand you: the total amount of paid dividends per block can be larger than block reward? For example, block reward is 25 but the dividends for all spent transactions in this block is 30 because some accounts accumulated dividends for a long period of time.

Here's a few things you assume nodes can converge to an agreement about without requiring extra consensus mechanisms:

1. Whether a block includes 90% of the expected/broadcast transactions
2. The lowest fee block for a given period

For #1 this could become tricky as hell to verify for any bootstraping node. It'd just have to trust the 'longest' chain, except that making fake long chains is easyish (what is the mechanism for choosing the best chain? You don't have it spelled out explicitly).

#2 is more problematic. Either you have a fixed interval for block acceptance, or you only have a starting point. If it's the latter I can arbitrarily cause reorgs by late publishing of a valid block with a lower fee than anything else (It will also be easy for that block to be valid in all other ways). If it's the former I can cause forks at will by broadcasting a lowest fee block right at the end of the window, and splitting nodes with early clocks from nodes with late clocks.

Dividends are not calculated for an output until the output is spent. The the coinage is used to accumulate all dividends.   This prevents dust and rounding errors.

How dividends transactions are made? If you have 10M accounts with positive balance, you have to make 10M transactions to pay the dividends each block, right?

Sorry for the second post, just another thought (which others already raised above):  How exactly do you prevent a "51% attack" with a malicious chain based on "largest transaction volume"?  As mentioned already, it would be trivial if you just have enough funds to move them around and build up a long chain.  Your response was that you would be paying lots of fees - but are fees mandatory for Bitshares (even if you mine your own transactions) and if so, how large are the minimal fees paid for a transaction?  Will this be large enough to "eat up" your funds quickly?

Did you also think about proof of stake (more than mentioning it in your OP at the end), IMHO that seems like a reasonable idea to prevent such an attack (because by moving the shares for the first time, you give up your claim to the "share-days" you have accumulated).

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.

The difficulty setting would adjust so that there is always on-average N bids per block based upon a X% probability of taking more than 10 minutes per block.   The key is to make sure that the proof-of-work is just difficult enough to prevent everyone having the right to flood the network with solved blocks.

 

If they pick the same dividends then I pick the block that has a hash value closest to the target hash and only one block will qualify and it will be universally agreed upon by everyone.

If I understand correctly, the idea behind this is to erase the "first to publish" reward as you put it and rather have blocks rewarded to those who charge the lowest amount of fees (and consequently the highest % towards dividends).  However, what happens if multiple miners come in at the same bid in terms of mining fees?  How would that be resolved?  Wouldn't you then need to reward the first to publish?  If the node waits 10 minutes before receiving candidates for the next block, will it still know which bid was submitted first in the scenario where fees between two miners come in equal?

I addressed time sync in the prior post.  All I really care about is that the nodes that communicate with me follow the rules and not broadcast more frequently than 10 minutes after they last replaced the head node with a better block.  If they attempt to build off of the prior head node in less than 10 minutes they get disconnected and flagged in my address table... or perhaps challenged with a proof of work. 

I do not think it is considered centralization to trust someone with a public face to merely confirm what you were able to independently arrive at baring any man-in-the-middle attacks.   Particularly if any number of 'known people' could be used and you are not trusting these entities word about anything.   They have too much to lose by lying to you. 

Thanks for your feedback and thoughts, send me an address and keep it coming.