Topic: [BitShares] Proof of Minimal Work Concept Feedback Wanted - page 2. (Read 2010 times)

   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?