[Cryptography] More efficient block-chain ledger: Micali's "Algorand" ?

[Henry Baker]

At 01:32 PM 2/26/2017, Natanael wrote:
>Den 26 feb. 2017 20:39 skrev "Henry Baker" <hbaker1 at pipeline.com>:
>This approach cryptographically selects ---in a way that is provably immune from manipulations, unpredictable until the last minute, but ultimately universally clear--- a set of verifiers in charge of constructing a block of valid transactions.  This approach applies to any way of implementing a shared ledger via a tamper-proof sequence of blocks, including traditional blockchains. 
>
>This isn't the first attempt to do this.  The arguments against it are old.
>
>Here's a good article on why everything that isn't centralized degrades to proof of work when there's an incentive to influence the globally shared output;
>
>http://www.truthcoin.info/blog/pow-cheapest/
>
>Some examples of why this is flawed;
>
>1: Sybil attacks.  We could just stop here, but...
>
>2: NSA (or any other entity with similar technical capabilities) can just hack the current leader nodes.  They're just a bunch of random nodes in the first place, so they're unlikely to be highly secure.
>
>Then they can try a million inputs until all further blocks appoints themselves only as future leaders.  This is a huge weakness with using elected central master nodes in networks without any central gatekeeper.  This system is just a distributed gatekeeper that you can hijack.  A full takeover is unrecoverable with technological measures and needs a social effort to revert.
>
>If there actually existed any automated method capable of restoring normal trusted behavior after a takeover, then this method would by itself be able to replace the standard concensus system.
>
>3: There's no way their proof will be meaningful in any way, because it implicitly assumes that all nodes are secure and it assumes a perfect network.  "Unpredictable until the last minute" means nothing even if they're doing their randomized node selection with hash commitments.
>
>This is both because of the above mentioned Sybil attack, and because if you've got a large number of nodes participating then you can always delay publishing commitments until everybody else has published theirs, and opt to publish OR not publish committed values as desired to influence selection (giving you as many "bits worth" of effective bruteforce as you've got participating nodes) - and of course also because of the following problem;
>
>4: Netsplits. Or worse, induced netsplits and direct network level censorship by somebody capable of spying directly on the internet connections of the individual nodes.
>
>Since a protocol like this must be tolerant to node failures, NSA can just delay the responses of everybody and chose the set to allow through that gives their own nodes more control (amplifying the effect of the selective publishing attack in #3).
>
>5: The classical nothing-at-stake problem. There was a valid block A at time B (in the past) from set of leaders C.
>
>Then network troubles happened and most nodes fell away, and a new leaders were appointed from the candidates.
>
>Except not, the "real" chain is a different one, but your fresh node doesn't know that.  And it has no way to know.
>
>Nothing enforces that this blockchain truly is append-only for anybody not well connected.  What's worse is that if your node later finds the real chain, your node has no object way to know which is real, while it does have internal state that is incompatible with the current chain (the set of appointed leader nodes).
>
>There's not even any useful heuristics to detect an attack, because any sign of a forgery attack in the blockchain is indistinguishable from an actual real world event (and can be induced in the real chain).  And any strong heuristics would lead to a looks-least-fake fork competition with ugly play = another modified proof of work scheme.

Here's Micali's Spring 2017 course on Github -- perhaps protected by SHA1? :-)

https://github.com/mit-dci/6.892-public

Unfortunately, this version of 6.892 is not listed as part of MIT's Open Courseware, and so there is no video (that I could find) of the lectures.