Skip to content
The methodOpen data
Back to the collection

Algorand

Jing Chen, Silvio Micali

2016 · arXiv

DatabasesStatistics & probabilityDistributed systems
Read the paper
HN score
0
Mentions
6
Readers
4
Months
4
What’s in a score?

From the abstract

A public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions ---such as titles, sales, and payments--- in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications ---such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not "fork" with overwhelmingly high probability. Algorand is based on (a novel and super fast) message-passing Byzantine agreement. For concreteness, we shall describe Algorand only as a money platform.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

josh2600
Neutral mention · rule
I mean you can just read Silvio’s paper: https://arxiv.org/abs/1607.01341 My understanding on how the accounts are chosen is that they have a global list of users that have opted in to validate and they pick one person at random to create the block and then 1000 people at random to validate it. If you get 501 validations back, then you have a block. The attack I always thought about but never got an answer to was: what if you pay for the lottery winners to collude? Certainly if you offer some amount of money for the block producers only on the condition that you get 501+the block creator in a given block you could probably sign a bad block, right? It’s unclear what the…
Read the full comment
consequences of that would be if the block’s signatures still have to be valid but you could maybe craft something bad. I don’t know, all of this thinking is from when I first talked to Silvio at IACR so it’s been a long time. It’s possible all of my knowledge is way out of date or wrong. Anyways, I wish them luck, they’ve certainly got a big thing going.
Original comment Algorand Consensus Protocol
alistproducer2
Neutral mention · rule
In distributed ledgers, it doesn't matter who the leader is. The system only has to ensure that leadership is distributed in such a way that it is statistically infeasible or economically unprofitable to rewrite history. PoW distributes the leadership (block creation) via crypto puzzles. PoS tries to use economic incentives to make bad behavior more expensive than good. There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). The basis of such a system is going to be the creation of non-biasable pseudo-random number generation. Along these lines one of the…
Read the full comment
more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS. Edit: for clarity A lottery-based system works because the "winning numbers" (imagine a winner being a node whose public key when XOR'd with the winning number is below a certain value) are known to all (a protocol like randhound ensures that all nodes know the winning number). A winner's bundle of transactions are validated as his/her's by cryptograpic signature (which can be verified using the same public key that is used to confirm this person is truly a winner). Those are the broad strokes. Obviously there's a lot more to getting it to work. I've been working on it for months and still haven't gotten around to putting it down on paper. [0]: https://arxiv.org/abs/1607.01341 [1]: https://eprint.iacr.org/2016/1067.pdf
Original comment Stellar Protocol: A Federated Model for Internet-Level Consensus (2016) [pdf]
peercoin
Neutral mention · rule
>An honest mining majority is a hard requirement of Bitcoin. But proof-of-stake doesn't solve the problem of collusion -- it's even more susceptible to it since it's so easy to recreate valid-looking chains. With Bitcoin, two or more competing chains will at least be visible (two distinct chains with a lot of work), whereas they're everywhere in PoS and the main chain is qualitatively no different from any other valid chain (of which we can create thousands quickly). I'm not sure what math you are using to base this assumption on. A formal argument by algorand is that the probability of a fork would be the age of the universe. It is NOT straightforward or cheap to recreate valid looking chains and generate the next block creating a fork. https://arxiv.org/pdf/1607.01341.pdf
Original comment Photos: Life inside of China’s massive and remote Bitcoin mines
jude-
Neutral mention · rule
> This is usually considered too expensive in the context of non-coin/-blockchain p2p networks because you want nodes to be able to run on embedded and other resource-constrained devices. The O(log n) node state and bootstrap cost limits are quite important. Otherwise it would be akin to asking every mobile phone to keep up to date with the full BGP route set. Funny you should mention BGP. We have been approached by researchers at Princeton who are interested in doing something like that, using Blockstack (but to be fair, they're more interested in giving each home router a copy of the global BGP state). I totally hear you regarding the costly bootstrapping. In…
Read the full comment
Blockstack, for example, we expect most nodes to sync up using a recent signed snapshot of the node state and then use SPV headers to download the most recent transactions. It's a difference between minutes and days for booting up. > Of course, but for some applications that is more than good enough. If your adversary can bring enough resources to bear to take over 1/3rd of your network he might as well DoS any target he wants. So you would be facing massive disruption anyway. Yes. The reason I brought this up is that in the context of public DHTs, it's feasible for someone to run many Sybil nodes. There's some very recent work out of MIT for achieving BFT consensus in open-membership systems, if you're interested: https://arxiv.org/pdf/1607.01341.pdf > I mean blockchains lose some of their security guarantees too once someone manages to dominate 1/2 of the mining capacity. Same order of magnitude. It's basically the design domain "secure, up to point X". In Bitcoin specifically, the threshold for tolerating Byzantine miners is 25% hash power. This was one of the more subtle findings from Eyal and Sirer's selfish mining paper. > The things you list don't really replace the purpose of a DHT. A dht is a key-value store for many keys and a routing algorithm to find them in a distributed environment. What you listed just gives you a bunch of nodes, but no data lookup capabilities. Essentially you're listing things that could be used to bootstrap into a DHT, not replacing the next layer services provided by a DHT. If the p2p application's steady-state behavior is to run its own overlay network and use the DHT only for bootstrapping, then DHT dependency can be removed simply by using the systems that bootstrap the DHT in order to bootstrap the application. Why use a middle-man when you don't have to?
Original comment An off-grid social network
peercoin
Neutral mention · rule
> Why not move to proof of stake? >> Because it doesn't make sense. If a chain, on which a token exists, needs securing, you can't use that chain's token to secure itself. I mean I'm not entirely sure what this argument is based on? In addition to existing proof of stake systems which have been running for years now, there exist several papers with rigorous formal proofs. Including Turing Award winner Silvio Micali's algorand. Refute his paper. You will became very famous overnight. https://arxiv.org/abs/1607.01341 > Mining has huge energy requirements as shown by the article. >> Mining has no requirements at all. People just follow the best chain, and miners can sell the bitcoins they earn by extending the best chain. It's entirely voluntary. I assume this is trolling or extreme nitpicking. Securing the network in proof of work requires that the majority of computing power is held by honest miners.
Original comment Photos: Life inside of China’s massive and remote Bitcoin mines
peercoin
Neutral mention · rule
Why not move to proof of stake? Proof of Work mining used in bitcon to secure the network as originally proposed in Nakomoto's paper has huge energy requirements. The result is large energy hungry mines as shown by the article. In addition, there is a centralization of governance by the miners. One such example of a long running proof of stake is Peercoin. Peercoin is a legit energy-efficient contender to Bitcoin. It's one of the first publicly known implementations of proof of stake has been around for close to 5 years now. Peercoin is energy-efficient and runs on raspberry pis. It's been running successfully for years now. https://peercoin.net/ There are also academic proof of stake chains which virtually eliminate the chance of forks, such as algorand. https://arxiv.org/abs/1607.01341
Original comment Photos: Life inside of China’s massive and remote Bitcoin mines

Keep following the thread.

More in Databases

More from the same topics.

2017arXiv

The Case for Learned Index Structures

Tim Kraska, Alex Beutel, Ed H. Chi +2

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.

Databases
19 mentions14 months
5HN score