HNHacker News
TopNewBestAskShowJobs

emin-gun-sirer

75 karma · joined November 4, 2013

submissionscomments
emin-gun-sirer··on Bitcoin's mining difficulty has increased by 41.9% over the last 30 days
>The only special power of a 50% miner is to consistently resolve double-spend attempts in its favor.

No, this post, and the handy table inside, explains the various attacks possible at different percentages of the hash rate:

http://hackingdistributed.com/2014/06/16/how-a-mining-monopo...

emin-gun-sirer··on Bitcoin-NG: A Secure, Faster, Better Blockchain
Miner consolidation is a long-standing problem with Bitcoin itself.

When Ittay and I discovered selfish mining [1], we were quite worried about the size of mining pools at the time. Even though we also came up for a fix against selfish mining, the fix only prohibits selfish mining for pools <25%, and we also found that there can never be a fix to prohibit selfish mining for pools >=33%.

Things looked grim for a while, and we played a role in pushing back against GHash when they exceeded 51% around April of '14. The only tool that the community had at the time to break up large miners was just social pressure.

In part as a reaction to GHash crossing of the 51% line, we [2] and Andrew Miller et al [3] came up with techniques based on non-outsourceable puzzles. This is a cool technique that would make it difficult for miners to run large open pools. It does require a potentially disruptive change to Bitcoin, so it's good to have in one's back pocket if the mining situation gets out of hand, but it's not something you want to deploy.

Luckily, Ittay's subsequent work on the Miner's Dilemma [4] discovered an incredibly interesting result: it pays for miners to attack other miners who are running large open pools. This puts natural pressure on miners to not open themselves up to the public and accept people into their pools willy nilly. This in turn is, I think, fantastic news, as it means that the problem may take care of itself, at least when it comes to open pools.

Overall, the distribution of mining power is a point of concern for everyone in the Bitcoin space. The situation looked bleak at first, as it looked like there were few mechanisms to keep open pools from growing ever larger. But now we have a strong technical solution and a natural process that is well-characterized. Large solo miners still remain an ongoing concern.

Hope this is useful.

[1] http://arxiv.org/abs/1311.0243

[2] http://hackingdistributed.com/2014/06/18/how-to-disincentivi...

[3] https://cs.umd.edu/~amiller/nonoutsourceable_full.pdf

[4] http://hackingdistributed.com/2014/12/03/the-miners-dilemma/

emin-gun-sirer··on Bitcoin-NG: A Secure, Faster, Better Blockchain
All good questions, all of which are answered in the white paper. An "elected leader" is essentially the same thing as a miner that mines a block in Bitcoin. Miners can mine empty blocks in Bitcoin. This is OK, as others will step in for such defunct miners. Likewise, in Bitcoin-NG, another miner will step up if the elected leader does not mint microblocks.

Keep in mind also that NG would be layered on top of Bitcoin, so everything that works in Bitcoin will work in NG as well.

emin-gun-sirer··on Using JSON Web Tokens to Authenticate JavaScript Front-Ends on Rails
This sounds like a use case for Macaroons [1]. A primer and a public implementation can be found here [2]. There's also a JavaScript implementation [3].

[1] http://research.google.com/pubs/pub41892.html

[2] http://hackingdistributed.com/2014/05/16/macaroons-are-bette...

[3] https://github.com/nitram509/macaroons.js/tree/master

emin-gun-sirer··on Can't resolve time.nist.gov
Thanks, indeed, there are many alternative NTP servers [1]. But I believe time.nist.gov is the default time server during Ubuntu installation, so there are many hosts that depend entirely on time.nist.gov.

[1] http://www.pool.ntp.org/en/

emin-gun-sirer··on Eventual Consistency and Transactions Working Together
HyperDex provides scalable and high-performance transactions. While it is strongly (not eventually) consistent, the underlying technique we use to achieve atomicity of transactions is reminiscent of this approach.

On a related note, our experience is that a tightly implemented database can be much faster than a typical eventually consistent database. It would be great to see performance comparisons from TreodeDB.

emin-gun-sirer··on ChangeTip must die
>For the record, I appreciate your technical critiques! But you seem to take a perverse delight in being the critic.

Ok, so you enjoy the technical content but disagree with the tone [1]? I can understand that. I genuinely feel sorry I don't have the time to build rapport. Many other bloggers regurgitate things we all agree on and make everyone feel warm and fuzzy inside. I figure that enough people already do this that I only need to chime in when the group-think is headed south.

[1] https://commons.wikimedia.org/wiki/File:Graham's_Hierarchy_o...

emin-gun-sirer··on Neat Algorithms: Paxos
Yes, it's an open-source project from my research group at Cornell.
emin-gun-sirer··on Neat Algorithms: Paxos
This well-illustrated post is technically about the core Synod agreement protocol in Paxos. Building a consistent distributed service on top requires additional scaffolding and infrastructure. Typically, people layer on a system that implements a "replicated state machine (RSM)" on top, which maintains the illusion of a single consistent object, even though it is composed of distributed replicas.

Also keep in mind that Raft, Zab, and View-Stamped replication (in reverse chronological order) are alternatives to the Synod protocol in Paxos. These protocols differ from Paxos by employing a different leader-election mechanism and slightly different way of maintaining their invariants.

There have been many Paxos variants. This site [1] shows the various Paxos variants over a timeline and points out their contributions.

Those of you interested in building replicated state machines using Paxos should take a look at OpenReplica [2]. It is a full Multi-Paxos implementation that takes any Python object and makes it distributed and fault-tolerant, like an RPC package on steroids.

[1] http://paxos.systems/

[2] http://openreplica.org/faq/

emin-gun-sirer··on ChangeTip must die
It's critical to not conflate Bitcoin with ChangeTip. The two are, in effect, separate currencies. One is decentralized and backed by the blockchain, the other is centralized and backed by a company.

A litmus test for centralized currencies is to ask the question "can they create wealth out of the thin air by manipulating a database entry?" The answer is affirmative for ChangeTip. To their credit, they maintain proof-of-reserves online, so while we do not know the amounts held by their users, we have an idea of how much they can pay out. I applaud the transparency they have shown.

I won't respond to the drive-by ad hominem.

emin-gun-sirer··on SuperTCP (outbound TCP accelerator) is going public Beta Sign up here
How does this product actually work, except by violating the standard TCP congestion avoidance algorithm?
emin-gun-sirer··on How to Disincentivize Large Bitcoin Mining Pools
Co-author here. There is a common misconception that consensus of the Bitcoin community is correlated with the hashing power of the miners.

A miner can have 51% of the hashing power, but if the blocks he produces are not accepted by clients (i.e. people with wallets, merchants, and the like), his 51% hash power is completely useless. His blocks need to be recognized by the clients, and if the clients decide that they do not want centralized mining pools, and decide that they only accept blocks with a second cryptopuzzle in them, miners who fail to switch will produce blocks that are unrecognized and therefore useless.

emin-gun-sirer··on It's Time For a Hard Bitcoin Fork
To the contrary, we've been far more respectful and accommodating to the Bitcoin fringe than merited, and certainly far more than the other way around. After all, we took a fair amount of abuse for simply pointing out an objective weakness that is part of the protocol. This, despite the fact that we proposed a fix for it.

Perhaps you've not read our final paper. It doesn't just footnote, but actually cites the prior discussion.

And anyone who reads the previous discussion can see that our paper:

* shows a more extensive attack than the one described there, one that works,

* performs a full analysis of the revenue to be obtained from that attack, and characterizes that revenue as a function of attacking pool size and attacking pool's ability to control information flow in the network,

* shows that Bitcoin is not incentive-compatible,

* shows that, even under the best of circumstances (i.e. the attacker has terrible network connectivity, no Sybils, no control over information propagation and loses to the honest miners every single time), defending against the attacker requires at least 2/3rds of the network to be honest.

Perhaps the biggest giveaway that we did something differently is that THE BITCOIN TALK FORUMS CONCLUDED THAT THEIR ATTACK WOULD NOT WORK, WHEREAS WE SHOWED THAT OURS WOULD.

You're making things up when you imply that we're claiming that 51% is an "unsurvivable crisis." To the contrary, the article very clearly says that the Bitcoin economy remains unaffected, and that the Bitcoin price is also unaffected.

We have been trying to improve the Bitcoin system since day 1. I realize that you're part of the original brigade, and that also explains your ad hominems here. I urge you to elevate the discussion.

emin-gun-sirer··on It's Time For a Hard Bitcoin Fork
The counterpoint from my colleague Ed Felten is based on a flawed understanding of how mining pools work and how pool participants are rewarded.

Explained here: http://hackingdistributed.com/2013/11/08/fairweather-mining/

emin-gun-sirer··on It's Time For a Hard Bitcoin Fork
Nice ad hominems you've got there.

>In fact, the paper just formalized some concerns discussed in the mining community for years.

This is false. Discussed here: http://hackingdistributed.com/2013/11/09/no-you-dint/

>the "Bitcoin lunatic fringe" this author mocks has been right about the pool(s) having such power refraining from destructive (and self-bankrupting) next steps.

No. The Bitcoin lunatic fringe was adamant that no pool would willingly cross the 50% boundary.

That just happened. Models and reasoning based on "no rational miner would do X" are clearly flawed, partly because the miners may not be rational, or partly because they are rational within a time-frame not modeled. In any case, people who reasoned like you have now been shown conclusively to have the model wrong.

This is an opportunity to fix the protocol, not shill for the price, and certainly not to engage in ad hominems.

Cheers.

emin-gun-sirer··on It's Time For a Hard Bitcoin Fork
That's not the kind of restriction that stops pool mining. The trick is to enable the pool members to steal the blocks they discover. Andrew Miller, a grad student at UMD, has an ingenious scheme for doing this. I am pretty sure I put the link in the article, under the first bullet in the "What to Do Now" section.
emin-gun-sirer··on Is learning MongoDB worth it?
There are next-generation NoSQL data stores out there that are better than MongoDB on many axis (performance, consistency, fault-tolerance, API, backup speeds, etc). One of these (full disclosure: it's from my group) is HyperDex (http://hyperdex.org).
emin-gun-sirer··on Zuckerberg Says Obama Steps on NSA Spying Not Enough
Just curious: of the data that Zuckerberg could collect, what does he not collect?

It should be pretty clear that this is not an endorsement of NSA's broad data collection activities. But credible leadership in this area requires that Zuckerberg willfully constrain and limit the activities of his own company first.

emin-gun-sirer··on The Face Behind Bitcoin?
No culture deserves to have its creation myths exposed or destroyed. Ironically, Newsweek's behavior makes a strong case for anonymous communication and payment systems.
emin-gun-sirer··on What Did Not Happen At Mt. Gox
Author here. I think there is some subtlety around the technical point that may be getting lost.

Ittay Eyal and I were the ones who discovered an attack against Bitcoin called selfish mining, where we showed how a miner could earn more than his fair share. This attack did not require, but could benefit from, the attacker racing against honest participants on the peer-to-peer network. Some members of the Bitcoin community claimed that the attacker would reliably lose these races because they start behind.

In the article, I point out that there is indeed a transaction race in this case, that people have demonstrated an ability to outrun transactions, and that this has ramifications for selfish mining. I do not claim that there is a technical impossibility -- quite the contrary! The tricks used to make that succeed are identical to what an aggressive selfish miner would use.

To be fair, malleability attacks require a modified client and some network positioning, so there is nevertheless a technical obstacle. Not one that is impossible to surmount, but one that requires some effort.

I did not know that Mt. Gox performed automatic reissues -- thank you for bringing that up. Would you happen to have a pointer that establishes this?

On the whole, I do not believe that malleability accounts for Gox's collapse at all. Even automatic reissues would put at most the hot wallet at risk. Studies of malleable transactions do not show anywhere near the volume required to account for Gox's collapse. And something I did not mention in the post is that the timing of the observed malleable transactions doesn't match the story from Mt. Gox at all. There is undoubtedly more to this story.

emin-gun-sirer··on OkTurtles + DNSNMC: Surveillance-free communication on your favorite websites
>The implications of my comment were not simply that gamma is reduced to zero, but that the whole problem is thrown out the window because the entire pool would be banned from the network (blacklisted).

Ah, but even if detection worked perfectly (and did have a false positive rate of 0), who precisely do you blacklist? The Bitcoin wallet? It's trivial to generate more. The IP address? Which precise IP address? Even if you could locate the IP address of the submitting node accurately, a pool has many, and it's possible to get more.

emin-gun-sirer··on OkTurtles + DNSNMC: Surveillance-free communication on your favorite websites
The math seems to be correct and borne out by simulations, even independent simulations devised by people who did not believe that the selfish mining attack would work [1].

So Stephen's point is that there may be operational procedures that might allow one to detect selfish mining. This is great, as this is what we want is for Bitcoin to deploy in-protocol incentives to break up selfish miners. But there are two issues: (1) I'm not sure that his suggested tactic of judging by the latest timestamp would actually work well for established pools. I suspect that some pools are less eager to update their xaction sets, and therefore might lose to selfish miners, and (2) even if these operational measures worked perfectly, they would succeed in lowering gamma. But even with gamma at 0, selfish mining is still a win for groups of size 33% and above.

Hope this is useful.

[1] http://hackingdistributed.com/2013/11/17/selfish-mining-simu...

emin-gun-sirer··on OkTurtles + DNSNMC: Surveillance-free communication on your favorite websites
I'm one of the two authors of the selfish mining paper. Let me chime in on the selfish mining aspect of this generally insightful comment:

>The interesting question remains: what happens when some pools start to implement this strategy?

>I do not know for sure, but I suspect that the result will be a wash, so to speak, and most likely will end poorly for the cheaters (when they are caught). Their entire paper is based on the absurd claim that a single selfish pool will grow, like some sort of cancer, until it reaches 51% proportions (and then it's game over). While this is a possibility, at the moment it seems like an exceedingly remote one. In fact, the more cheating pools there are that use this strategy, the less likely their vision of a BTC doomsday becomes. Which group of bandits should one join, and is it worth the risk?

The revenue dynamics of selfish mining (SM) are such that two SM pools working independently are better off joining forces. The excess revenue for SM is super-linear in pool size. So, with X% of the mining power working selfishly, you make (X(1+eps))%, with Y% mining selfishly, I make (Y(1+iota))%, but if we combine forces, we make (X+Y)*(1+delta)%, where delta>eps+iota. So we not only get our normal winnings, but we win an additional reward for joining forces. And since there is nothing at the protocol level to break up large mining pools, there is an incentive for SM pools to get large and grow until the 50% point.

We deliberately deferred a game-theoretic analysis of selfish mining to a future paper, because such analyses tend to be highly dependent on modeling assumptions. E.g. would an attacker view reaching the >50% point as a complete failure event when all coin value drops down to 0, or as a complete success event? The answers on how to model this apocalypse depend on too many assumptions about the attacker, his motivation, and what others can detect about his power. A thorough job of modeling the game-theoretic dynamics of Bitcoin (with selfish mining) would indeed make an exciting follow-on paper.

emin-gun-sirer··on Sent $10,701.03 to Coinbase. Still missing bitcoins.
You mean "ACID transactions" and not SQL databases. Some NoSQL databases, such as HyperDex, provide ACID transactions.
emin-gun-sirer··on Why Bitcoin is a significant breakthrough, but perhaps not as a currency
Let me use this opportunity to point out http://virtual-notary.org, an online witness to facts that can be checked online, where these facts are recorded in the Bitcoin blockchain. These go beyond the types of document proof of existence cited in the article, and can cover facts such as exchange rates, DNS address ownership, WHOIS info, weather conditions, housing prices, employment status, etc.

This article describes the usage scenarios in detail: http://hackingdistributed.com/2013/06/20/virtual-notary-intr...

emin-gun-sirer··on Broken by Design: MongoDB Fault Tolerance
That blog post met with a lot of responses of the form "tl;dr but mongo was broken and it's fixed now, nothing to see here." Wasn't fixed then, doesn't seem to be fixed now [1]. And it's quite difficult to have a conversation with people who can write but not read.

TL;DR Not surprised that a brogrammer response to all this would be "you jelly."

[1] http://aphyr.com/posts/284-call-me-maybe-mongodb

emin-gun-sirer··on Broken by Design: MongoDB Fault Tolerance
I'm the author of the blog post, and just saw this resubmission on HN. Just wanted to quickly touch upon some of these points:

* "It lies." Mongo lied at the time I wrote the post, and while the default has been changed, the "this entire point is no longer a concern" seems overly optimistic. See here for further details where successful writes are lost: http://aphyr.com/posts/284-call-me-maybe-mongodb

* "It's slow." We have indeed benchmarked Mongo's behavior, and, even though developers give up on consistency and fault-tolerance by using MongoDB, they don't get high performance in return for their tradeoff: http://hyperdex.org/performance/

* "It doesn't work pipelined / it doesn't work multithreaded." I don't quite see a correctness argument here. I read through the sources of the Java driver at the time I wrote the blog post. If you follow the pattern described in the link you provided (java-concurrency), you will find that thread A can issue getLastError and receive results for thread B's operations. That is broken. The word "thread-safe" does not mean what you think it means. "People use it without ill effects" isn't as strong an argument as "I read through the code and it looks broken." Further, when 10gen responded to this blog post, they were unable to refute the technical point: http://hackingdistributed.com/2013/02/07/10gen-response/

* "WriteConcerns are broken." Check out the Jepsen test, the last subsection: http://aphyr.com/posts/284-call-me-maybe-mongodb

Agreed that Mongo's simplicity is a big draw for many developers new to NoSQL. Sadly, the system provides very weak properties, and applications built on top end up having even weaker properties still.

emin-gun-sirer··on Thoughts on Bitcoin
The post assumes that Bitcoins will fail if they are not suitable as a store of value. It overlooks the fact that a currency can succeed as a medium of exchange, even if it is not suitable as a store of value.
emin-gun-sirer··on Proof of Existence: Storing Hashed Files in the Bitcoin Block Chain
Timestamping services are not novel and date way back before 2012. The earliest work I know of is from AT&T back in the 80's, where they proposed to publish the hash in the NYT. The idea was so well established that there is even an RFC [1] from 2001. And by the way, virtual-notary.org was online for several months or perhaps even a year before the blog post.

But the important differences are actually technical. Virtual Notary is a much more general service, offering to attest to any kind of online factoid. Let's elevate the discussion here -- it doesn't matter who was there first (because the AT&T folks were there two decades before both services), what matters is who offers the most useful service [3].

As for the previous work on selfish mining, see here [2].

[1] http://www.ietf.org/rfc/rfc3161.txt

[2] http://hackingdistributed.com/2013/11/09/no-you-dint/

[3] https://news.ycombinator.com/item?id=6819835

emin-gun-sirer··on Proof of Existence: Storing Hashed Files in the Bitcoin Block Chain
Virtual Notary offers a superset of the document verification service offered by proofofexistence.com.

It's best to think of Virtual Notary as a impartial online witness to factoids that can be checked online. Besides documents, it can attest to the content of web pages, tweets, weather conditions, stock prices, exchange rates, employment status (for those institutions where we know how to check employment status), house features and prices, etc.

It can also issue official, certified random numbers.

Virtual Notary also allows the users to download an independently-verifiable X509 certificate of attestation.

Page 1 of 2Next →