Table of Contents

IOHK/ada

  • Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
    • https://eprint.iacr.org/2016/889.pdf
  • Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain
    • https://eprint.iacr.org/2017/573.pdf

白皮书研究

解决PoS的核心问题 : the leader election process.

  • 问题:entropy -> randomized election among stakeholders <- an adversary controlling a set of stakeholders, “grinding” vulnerability, use computational resources to bias the leader election.
  • 方法:
    • 第一:模型
      • persistence 和 liveness
      • P是机制保证Tx变成stable,就会全网finality (常见的思路是more than k blocks deep)
      • L是机制保证合法Tx在某个时间段后一定能stable(也就是说合法交易一定能活下去)
    • 第二:选主协议
      • a coin-flipping protocol ->randomness -> leader election
      • a snapshot of the current set of stakeholders is taken in regular intervals called epochs
      • a secure multiparty computation takes place utilizing the blockchain itself as the broadcast channel
      • in each epoch a set of randomly selected stakeholders form a committee which is then responsible for executing the coin-flipping protocol
      • The outcome of the protocol determines the set of next stakeholders to execute the protocol in the next epoch as well as the outcomes of all leader elections for the epoch.
    • 第三:一组规则
      • protect persistence and liveness.
      • (1) any honest stakeholder is able to communicate with any other stakeholder,
      • (2) a number of stakeholders drawn from the honest majority is available as needed to participate in each epoch,
      • (3) the stakeholders do not remain offline for long periods of time
      • (4) "forkable strings” (???)
    • 第四:经济激励
      • 基于博弈论/纳什均衡设计对抗 block withholding 和 selfish-mining
      • positive payoff --> cannot be stifled by a coalition of parties --> an equilibrium when all players are rational. (问题是玩家理性吗?)
    • 第五:代理机制
      • stake delegation mechanism -> delegate “voting rights”
      • 可以revoke delegation

抗攻击性的考虑

  • double spending attacks
  • transaction denial attacks
  • 51% attacks
  • nothing-at-stake
  • desynchronization attacks

性能

  • transaction confirmation time is from 10 to 16 times faster than that of bitcoin
  • analysis of double-spending attacks relies on our combinatorial analysis of forkable and covertly forkable strings and applies to a much broader class of adversarial behavior than Nakamoto’s more simplified analysis. (???)
  • prototype implementation and report on benchmark experiments run in the Amazon cloud that showcase the power of our proof of stake blockchain protocol in terms of performance.

其他的一些POS协议

Sleepy consensus

  • https://eprint.iacr.org/2016/918.pdf
    • considers a fixed stakeholder distribution (i.e., stake does not evolve over time) and targets a “mixed” corruption setting, where the adversary is allowed to be adaptive as well as perform fail-stop and recover corruptions in addition to Byzantine faults.
    • It is actually straightforward to extend our analysis in this mixed corruption setting, resulting security can be argued only in the “corruptions with delay” setting, and thus is not fully adaptive.

Snow White

  • https://eprint.iacr.org/2016/919.pdf
    • addresses an evolving stakeholder distribution and uses a corruption delay mechanism similar to ours for arguing security.
    • susceptible to a “grinding” type of attack that can bias high probability events in favor of the adversary. While this does not hurt security asymptotically, it prevents a concrete parameterisation that does not take into account adversarial computing power.

Algorand

  • https://arxiv.org/pdf/1607.01341.pdf
    • distributed ledger following a Byzantine agreement per block approach that can withstand adaptive corruptions.
    • Given that agreement needs to be reached for each block, such protocols will produce blocks at a rate substantially slower than a PoS blockchain (where the slow down matches the expected length of the execution of the Byzantine agreement protocol) but they are free of forks.
    • In this respect, despite the existence of forks, blockchain protocols exhibit the flexibility of permitting the clients to set the level of risk that they are willing to undertake, allowing low risk profile clients to enjoy faster processing times in the optimistic sense.

Fruitchain

  • https://eprint.iacr.org/2016/916.pdf
    • reward mechanism and an approximate Nash equilibrium proof for a PoW-based blockchain.
    • We use a similar reward mechanism at the blockchain level, nevertheless our underlying mechanics are different since we have to operate in a PoS setting.
    • The core of the idea is to provide a PoS analogue of “endorsing” inputs in a fair proportion using the same logic as the PoW-based byzantine agreement protocol for honest majority

Cardano SL

  • The core idea of proof of stake is that instead of wasting electricity on cracking computationally heavy problems, a node is selected to mint a new block, with a probability proportional to the amount of coins this node has. If a node has positive (> 0) stake, it is called a stakeholder. If a node eventually becomes chosen to mint a block, it is called a slot leader.
  • Cardano SL is called “Layer” for a reason. It is the first component of the Cardano Platform. Eventually, it will be expanded with a Control Layer, serving as a trusted computation framework to evaluate a special kind of proofs to ensure that a certain computation was carried out correctly. In gaming and gambling, such systems are used for verifying honesty of random number generation and game outcomes. Accompanied with side chains, it will make possible to accomplish such tasks as provably fair distribution of winnings in games. But the application of Control Layer lies well beyond gaming and gambling. Identity management, credit system and more will be a part of Cardano Platform. We are also aiming to evolve Daedalus, the Cardano SL wallet application, into a universal cryptocurrency wallet featuring automated cryptocurrency trading and cryptocurrency-to-fiat transactions.

Ouroboros POS算法

  • proof : having evidence that blocks of transactions are legitimate.
  • Stake : the relative value held by addresses on the node. “relative value” we mean “all value held by wallets on a particular node divided by total value in the system”.
  • Slot : A small period of time that is significantly larger than the expected difference in clocks on different nodes.
  • slot leaders: generate blocks for the blockchain. Anyone can become a slot leader if the coin selection algorithm would select a coin they own. Nothing except for the network state and network participants being online matters for the sake of proof of stake.
  • Follow the Satoshi (FTS) is an algorithm, that verifiably picks a coin, providing randomness. When your coin gets selected, you become a slot leader and can listen to transactions announced by others, make a block of those transactions, sign it with your secret key and publish it to the network. (随机选择算法)
  • Multi Party Computation approach: select nodes provide the so-called “commitments”, and then those get “revealed”, producing a random value generated independently by participants of the network. (提供算力)

Slot-leader 选择算法

  • Leaders for each slot of the current epoch are computed by FTS in the beginning of the current epoch.
  • So genesis block contains a list of selected slot leaders.
  • The number of selected slot-leaders corresponds to a number of slots in epoch, and this number depends on fundamental security parameter k defined in configuration file.
  • Theoretical aspects of the slot leader selection process is described in paper, page 11.
  • The node sorts all unspent outputs (utxo) in a deterministic way (lexicographically), so result is an ordered sequence of pairs (StakeholderId, Coin), where StakeholderId is an id of stakeholder (its public key hash) and Coin is an amount of coins this stakeholder has. It’s assumed that utxo isn’t empty.
  • Then the node chooses several random is between 1 and amount of Lovelaces in the system. To find owner of i-th coin node finds the lowest x such that sum of all coins in this list up to ‘i’-th is not less than ‘i’ (and then ‘x’-th address is the owner of i-th coin).
  • The result is a non-empty sequence of StakeholderId, ids of selected stakeholders. This sequense of SlotLeaders is storing in the node’s runtime context.
  • With P2SH addresses, node doesn’t know who is going to end up with funds sent to them. Therefore, P2SH addresses can contain destination address which specifies which addresses should count as “owning” funds for the purposes of FTS.

代码

  • https://github.com/input-output-hk/cardano-sl
  • 版本历史

screen shot 2017-10-18 at 3 32 29 pm

FTS (Follow the Satoshi)

  • https://github.com/input-output-hk/cardano-sl/blob/master/lrc/Pos/Lrc/Fts.hs

Blockchain

  • https://github.com/input-output-hk/cardano-sl/blob/master/lib/src/Pos/Block/Core/Genesis/Chain.hs
  • https://github.com/input-output-hk/cardano-sl/tree/master/lib/src/Pos/Block/Logic

参考文档

  • https://cardanodocs.com/introduction/#what-makes-cardano-sl-special
  • https://cardanodocs.com/cardano/proof-of-stake/
  • https://cardanodocs.com/technical/leader-selection/
  • https://cardanodocs.com/cardano/explorer/
  • https://cardanoexplorer.com/
  • https://cardanodocs.com/glossary/
  • https://cardanodocs.com/technical/blocks/

Video

问题

  • Proof of stake with rigorous security guarantees. 严格安全保证在哪里?
  • Proof of Stake protocols and we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium 如果是基于博弈论和纳什均衡的话,那么以太的casper也是这样。区别是什么?

BW怼cardano事件

  • https://steemit.com/cardamon/@dan/peer-review-of-cardano-s-ouroboros
  • BW认为ada抄袭(copy)了他的工作,但是没有提他( Ouroboros is a copy of Delegated Proof of Stake (DPoS) with a few counter-productive modifications. In fact their paper refers to the term “πDPoS” 17 times without mentioning or recognizing any of my prior work.)
  • 结果上,BW认为ada的性能和效率完败
    • 出块 EOS: 0.5 seconds vs. Ouroboros: 20 seconds
    • 稳定 EOS: <= 2 seconds vs. Ouroboros: > 5 hours
  • ada的安全在工程上不可行:400公斤的防弹衣没法穿。(为啥BW没说明)
  • 对dPOS的分析
    • 选人 (Selecting a set of block producers)
    • 排队 (Scheduling the producers into time slots)
  • 选人
    • 时间轮: BTS 1h vs Ouroboros:5 days
    • 参与要求:Steem 没有下限 vs. Ouroboros at least 1% stake
  • 排队
    • 随机性:
      • Steem 从确定一组里面随机抽(uses deterministic scheduling with pseudorandom shuffling)
      • Ouroboros 随机性由随机选定的权益人生成(sampling from a source of provable randomness created by a committee of randomly selected stakeholders)
    • 安全性:
      • Steem / BitShares / EOS 靠投票(人为)select a set of unlikely to collude entities by approval voting then schedule them in a pseudorandom order。 同时EOS要取消shuffle ( EOS will be removing the random shuffle all together.)
      • Ouroboros 随机选择导致时间和延时无法预期 Ouroboros the length of time until 2/3+ of the stake is “randomly selected” is not known. unpredictable latency like bitcoin
  • 分布式安全(Distribution Security Issues)
    • Steem 14 people confirm a block each round.
    • 只有投票才能对抗基于stake权重的中心化 stake-weighted voting creates a very high centralization that can only be countered with approval voting
    • Corruption takes place at the individual level, not the stake level. it is wrong to assume that large stake holders will behave like a group of smaller stakeholders of similar size