Topic: [BitShares] Proof of Minimal Work Concept Feedback Wanted (Read 2021 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.

   I have been thinking about this particular problem and I believe the key isn't in agreeing to a universal time, but elapsed time.  I know exactly how much time has elapsed in the past 10 minutes with very little drift.   Every node sending me messages also knows exactly how much time has passed.   Furthermore, almost every node has access to NTP so has a reasonable estimate of what to expect.    Every node would only build off of blocks that had relatively accurate times (in their opinion) and every node could validate that every other node waits at least 10 minutes before sending them candidates for the next block.   So there is no need to agree on universal time, only to vet that other nodes only broadcast at the proper intervals.   Nodes violating this social behavior would be disconnected.    The network would develop a rhythm.  So lets define a simple heuristic that a node could use with near zero knowledge... it will only forward new blocks it receives 10 minutes after receiving the last block it accepted.   The node knows who informed it of that last block and thus could instantly detect other nodes 'cheating' and sending too soon.   

   This approach should be entirely resistant to Sybil because all information I rely upon is given to me directly.   I am still at risk of someone entirely controlling all of my connections and sending me bogus blocks.  But this is only really an issue for 'first time connections that are boot strapping'.    Once you have a large local database you can reconnect to enough nodes to be confident you are not getting a bogus block.   

A node could be particularly picky, but this does not work like Ripple in a very critical way.  There is still a Proof of Work (how ever minimal) that is used to elect someone to choose which transactions are included in the block.  There is also profit made for having your block accepted by others that you would lose by including an invalid transaction.   As a result, POW is used to solve the mempool selection problem, and 'consensus' / desire to win the next block will provide profit motives to accept any reasonable block.    An unreasonable block would be any block that failed to include many valid transactions.  These blocks would not be broadcast across the network even with their proof of work.


Chain volume is easy to fake, but not volume-by-coinage.   Furthermore, all of these fake transactions would have to be broadcast to the entire network and the vast majority of the fees would be paid as dividends to everyone else and thus not go to the attacker.   This attack relies upon isolating an individual and all of their connections to the valid chain.   I suspect that if someone were able to isolate a user on the bitcoin chain, they would also be subject to the same attack...  *except* that they wouldn't be able to maintain the difficultly level. 

With BitShares all users are required to move their funds once per year to prove ownership of the private key.  These expected transactions could not be faked and in the time it took to synchronize with the network one would quickly notice a pattern of these 'about to expire accounts' failing to move.   

Bitcoin has everyone comparing notes off chain on what the expected difficultly should be.  If we didn't check the expected difficulty & gensis block then anyone with an ASIC could generate 4 years of history in no time and then trick anyone who connected to their bogus nodes.   

The one benefit of a proof-of-work system is it makes it harder to pull a man-in-the-middle attack.   So the question becomes how difficult is it for a large entity to pull a man-in-the-middle attack?   Second, if every single BitShare business with a public face was publishing their view of the consensus block via a SSL connection, then you are still decentralized and not trusting any one entity.   What are the chances that Mt. Gox, BitStamp, BitInstant, and Google are all going to lie about their view of the network?    Every merchant has a vested interest in both their name and the value of the ecosystem to prevent man-in-the-middle attacks and therefore the opinion of major players is the consensus opinion because these are the guys everyone is trading with.  We are not trusting them for the balance and we should be able to independently come to the same conclusion they came to.  We only check their 'opinion' to detect a man-in-the-middle attack.   

Your feedback took some time and is worthy a tip, send me an address.

Warning, I'm being a devil's advocate here...

I think the whole point of the Proof of Work (POW) is a solution to the " Byzantine Generals' Problem".  What that means is that a consensus is achieved to determine which block will be added to the correct and longest blockchain.  Once added everyone works on the newest and longest blockchain.

Imagine that Proof of Minimal Work (POMW) is used.  I think the hardest problem you mentioned is, "Implement a time sync protocol for the network that keeps all nodes within a couple of seconds of each other."  I think this is a very difficult problem to solve in a p2p manner.  Satoshi developed a distributed timestamp server on a p2p basis using POW.  Using POMW how would it be possible to sync 100,000 clients on the Internet?  Clients turn on and off, the Internet can slow down due to DDoS attacks, sharks gnaw Internet cables in the ocean, etc...  You said, "50% of the time there will be multiple candidates found in that 10 minute period".  I suppose these multiple candidates were mining using POW.  Then the candidate with the lowest fee is used, right?  That means all 100,000 clients need to be aware of each other to determine the lowest fee.  If they are not aware of each other, one client in the eastern hemisphere  would be awarded the block while another client in the western hemisphere would also be awarded the block, which would cause a chain fork.  Note that it is possible for bitcoin miners to mine a block at the same time.  If such a case arose then the block that is included will be determined by the 51% higher majority.  That is why Satoshi used the timestamp server in combination with POW to fully determine which block to use and ultimately which blockchain to extend.

You said, "Chain forks would be easily identified and the minority fork could be identified by transaction volume."  I am not sure what you mean by this.  Transaction volume of the previously mined block of the longest chain?  What if there were 10 different chains?  Can transaction volume truly determine the correct chain to use?

You said, "Everyone could easily compare notes off-chain to make sure that they are working on the global consensus and not some fake chain."  I think this is possible for comparing the older blocks in the blockchain.  I do know that in the bitcoin client Gavin sets blockchain markers to make sure the blockchain is correct to a certain point.  While not 100% secure it does make it more difficult to attack the bitcoin blockchain.

You said, "Many trusted companies would periodically publish transactions confirming they are using the current chain, perhaps by signing blocks they happen to mine."  Using trusted companies means some sort of centralization is involved to make POMW work.

EDITED

Ok, some picking apart, since you asked nicely:

1. Trying to keep a large network with a sync of a few seconds at most:
    a. Is rather difficult, especially in non-controlled decentralized environments (How do you get people to agree on a clock time without falling prey to a Sybil attack at that level? Bitcoin cheats by simply copying the time it gets from the system clock, and hoping that it's less than 2 hours away from the rest of the nodes).
    b. Only decreases the likelyhood of an accidental fork. Shenanigans can still occur. If I know the exact cut-off time, I can arrange to send a last-second block to about half the network. What happens? They wait a little longer? Then I can DOS by continuing to send them these (easyish to mine) blocks?

2. Counting on clients using mempool to decide which blocks are best, and avoiding forks while doing that, means agreement on what transaction are in the mempool.

3. Chain volume to resolve forks is trivial to fake for any semi-competent attacker. Send money in circles and bam!, you're the main chain.

4. Comparaison of notes off-chain and what not essentially pushes the trust and verification problem to another layer. It's a nice to have but fundamentally doesn't solve anything.

Broadly speaking your proposal sounds like Ripple's, where significant effort (validation-wise and synchronisation-wise, not proof-of-work) is spent syncing all nodes' mempools (making that the consensus mechanism). It's still vulnerable to Sybill attack, so they require a UNL (Unique Node List) to avoid it. It basically solves the problem by forcing quasi-permanent forks on any disagreement, and hoping that most of nodes in the UNL for a client are non-colluding/honest. You may want to read up on that.

I'll post a defense of POW as an agreement mechanism in a bit.

* EDIT*  Thanks to everyone who participated in this discussion, the feedback has been invaluable.    New new tips will be paid, but discussion is still desired.  


  I am starting a tip-bounty for those who can help analise and provide the most insightful and helpful comments.  Project Invictus (Charles & I) have a proven track record of paying tips for good feedback.  Hopefully the discussion will be worth while on its own, but I recognize that this tip-bounty infers no obligation on me to pay any particular poster.  

   Premise:  

-  Proof of Work is a lottery / voting system that can always be bought by the highest bidder.  
-  Real security in the Bitcoin chain comes from consensus and public records and not from mining.
-  The lottery system is required to select who gets to submit blocks to the network as decentralized 'decision' making system.  It also helps facilitate the initial distribution of a currency.
-  A determined adversary (say a government) could attempt a DOS on some or all addresses by regulating mining pools or purchasing a large number of ASICS.   The solution to this DOS is also the proof that mining is irrelevant from a security perspective.  
-  Fees are required to ration bandwidth and storage, these fees shouldn't be waisted on electricity and power consumption because this makes the network 0-sum and potentially operating at a slight loss.  
-  To keep fees down, miners must centralize and the blockchain bandwidth must grow beyond what the average individual can handle.

  Solution:
   Have miners compete to work for the least fees in a network where fees not paid to the miners are paid as dividends to those who hold the currency.    
   Mining will only be used to decide who gets to submit a block and rate-limit block production, but acceptance of the block is based entirely upon maximizing dividends, minimizing mining fees, and including 90% of the expected/broadcast transactions among many other factors (coin age, transaction volume, etc).  
   Bitcoin already operates on consensus (see March 2013 fork) and mining power is just a horrible waste.  

  Details:
   Implement a time sync protocol for the network that keeps all nodes within a couple of seconds of each other.
   No blocks will be relayed until 10 minutes after the prior block.
   50% of the time there will be multiple candidates found in that 10 minute period, the candidate that mined at the lowest fee is selected rather than the 'first to publish' because the lowest mining fee pays the highest dividends.
   Chain forks would be easily identified and the minority fork could be identified by transaction volume.  The cause of chain forks will always be because two different clients are following different rules and never because of a mining dispute or race.
   Everyone could easily compare notes off-chain to make sure that they are working on the global consensus and not some fake chain.  Many trusted companies would periodically publish transactions confirming they are using the current chain, perhaps by signing blocks they happen to mine.  

   I believe the economics of this system will cause miners to compete to use the least-resources possible per mining fee paid to the miner.  Mining would not completely stop because the difficulty would adjust toward 0 until someone steps up to broadcast a block every 10 minutes.

   Because there is no potential for chain-reorgs, confirmation times be reduced to 2 blocks and block rates could be increased dramatically.  

Proof of Minimal Work would prevent centralization and ASIC development entirely because their business model depends upon doing the most work the most efficiently.   Proof of Minimal Work is based upon accepting the minimim fee possible for the service you are providing to the network putting together and broadcasting blocks approved by all other nodes every couple of minutes.  

I am looking for attacks on this system as well as clear reasons why such a network would be secure.   Would an alt-coin based upon such a Proof of Minimal Work have value over say something like Litecoin or Proof of Stake?  Can you convince me that Proof-of-Work is actually providing security and not just a back door?