Head2Tail: Cardano stake-based Ledger / Online voting / Privacy features / decentralized software update mechanism / PRIViLEDGE_EU project

https://twitter.com/PRIViLEDGE_EU

Check out the work packages (WP1-4) with some great info about Cardano network and what it can do beyond "just payments"... A lot of docs are co-written by IOHK (https://iohk.io/en/blog/posts/page-1/) and researchers from University of Edinburgh (http://www.ed.ac.uk/) . You'll find info about the side-channels, how Cardano works, the implementations and explanations of all Ouroboros protocols, online voting, EUTXO, privacy features, etc.

Please note that some info might not be 100% docs from end of 2018 and for the latest info on Ouroboros and Hydra go to IOHK blog https://iohk.io/en/blog/posts/page-1/

https://priviledge-project.eu/publications/deliverables

WP1

• section 2.4 "Cardano Stake-based Ledger"

WP2.1

• Chapter 4 gives an overview on privacy-enhancing protocols
• Chapter 6 gives an overview of zero-knowledge techniques. Zero knowledge is an important tool for achieving many cryptographic goals – the ability to prove to another party that everything has been done correctly without revealing any private information is extremely useful for making protocols secure in the malicious set-ting — i.e. in the setting where it is not assumed that the parties behave only as the protocol dictates. Also,blockchain can help with improving zero-knowledge protocols as it can be used as an instantiation of a trusted third party.
• Chapter 7 where a number of open problems are presented. These can be seen as directions of possible research.

WP3.1 (the whole doc is interesting!)

• 4.3 Proof of Stake Ledgers
• Ouroboros: The Ouroboros proof-of-stake protocol [KRDO17] is provably secure in a corruption model that excludes fully adaptive attacks by imposing a corruption delay on the corruption requests of the adversary.
• Ouroboros Praos: In a recent work David et al. propose “Ouroboros Praos” [DGKR18]. In Ouroboros Praos,deciding whether a certain participant of the protocol is eligible to issue a block is decided via a private test that is executed locally using a special verifiable random function (VRF) on the current time-stamp and a nonce that is determined for a period of time known as an “epoch”. A special feature of this VRF primitive is that the VRF must have strong security characteristics even in the setting of malicious key generation: specifically, if provided with an input that has high entropy, the output of the VRF is unpredictable even when an adversary has subverted the key generation procedure. In [DGKR18] such VRF functions is called “VRF with unpredictability under malicious key generation”. In a nutshell, the protocol provided in [DGKR18] represents a “robust transaction ledger”. That is, a ledger that enjoys consistency and liveness (see Sec. 3.3). Moreover this protocol is proved secure in the ∆-semisynchronous setting with full adaptive corruptions.

• Ouroboros Genesis: In a follow-up work, Badertscher et al. [BGK+18] propose “Ouroboros Genesis”. This work provides a blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice (such as check points) or assumptions regarding past availability. Indeed such a blockchain protocol can “bootstrap from genesis”. Moreover the authors prove that the proposed protocol is secure in the Global UC model against a fully adaptive adversary controlling less than half of the total stake. The model considered in [BGK+18] allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. This protocol is effectively independent of both the maximum network delay and the minimum level of availability, both of which are run-time parameters.

  WP4.1 (Sections 2.3, 3 and 5, a must read)

With this document we provide a global picture of the progress of the research done to date in designing a detailed architecture for the Cardano update system (use case 4) and for the toolkit for anonymous authentication.

Sections 2.3

Cardano is a blockchain platform implemented by IOHK and underlying the Ada cryptocurrency. Cardano is running on top of the Ouroboros proof-of-stake protocol. Due to the active development of both the protoco land the whole platform, Cardano would benefit from a safe and secure decentralized software update system. In other words, a system that will ensure that: a) any honest stakeholder will always be able to submit an update proposal to be voted by the stakeholders community, b) it will prevent an update proposal that is not approved by the honest majority to be applied and c) it will provide guarantees for the authenticity of the downloaded software.

Consensus: Ouroboros Family of Proof-of-Stake Protocols

In this section we sketch the proof-of-stake protocols Ouroboros [KRDO17] and Ouroboros Praos [DGKR17]. The former is currently underlying the deployed Cardano blockchain, while the latter is foreseen to ultimately replace it. To avoid confusion, in the following we refer to the Ouroboros protocol [KRDO17] as Ouroboros Classic.

Ouroboros Classic Description.

The protocol operates (and was analyzed) in a synchronous model that splits the time continuum into a sequence of consecutive, non-overlapping intervals called slots(in Cardano, each slot is20seconds long).It is assumed that all parties are equipped with synchronized clocks that tell them the index of the current slot,and all messages are delivered within the next slot.In each slot, each of the parties can determine whether it qualifies as a so-called slot leader for this slot.The event of a particular party becoming a slot leader occurs with a probability proportional to the stake controlled by that party, is independent for two different slots, and is determined by a public, deterministic computation from the stake distribution and so-called epoch randomness(we will discuss shortly where this randomness comes from) in such a way that for each slot, exactly one leader is elected.If a party is elected to act as a slot leader for the current slot, it is allowed to create, sign, and broadcast a block (containing transactions that move stake among stakeholders). Parties participating in the protocol are collecting such valid blocks and always update their current state to reflect the longest chain they have seen so far that did not deviate from their previous state by too many blocks. As in the case of Bitcoin [Nak08], if there are multiple candidate chains, the slot leader will always choose the longest one to attach a new block.Multiple slots are collected into epochs, each of which contains R∈N slots (in Cardano, R= 21600). Each epoch is indexed by an index j∈N. During an epoch j, the stake distribution that is used for slot leader election corresponds to the distribution recorded in the ledger up to a particular slot of epoch j−1, chosen in a way that guarantees that by the end of epoch j−1, there is consensus on the chain up to this slot. Additionally, the epoch randomness for epoch j is derived during the epoch j−1 via a guaranteed-output delivery coin tossing protocol SCRAPE [CD17] that is executed by the stakeholders.

Security. Ouroboros Classic was shown by Kiayias et al. [KRDO17] to achieve the common prefix, chain growth, and chain quality properties, proposed as security desiderata for blockchain protocols by Garay et al.[GKL15]. It is well-known that these properties imply both persistence and liveness of the resulting ledger.These properties are achieved by Ouroboros under the following assumptions:

• 1. synchronous communication (as outlined above);
• 2. majority of the stake is always controlled by honest parties (i.e., parties following the protocol);
• 3. parties cannot be corrupted immediately, there is a corruption delay in place;
• 4. the stake shift per epoch is limited.

Ouroboros Praos

The Ouroboros Praos protocol [DGKR17], despite sharing the basic structure with Ouroboros Classic, differs from it in several significant points; we now outline these differences.The slot leaders are elected differently in Praos: Namely, each party for each slot evaluates a verifiable random function (VRF, [DY05]) using the secret key associated with their stake, and providing as inputs to the VRF both the slot index and the epoch randomness. If the VRF output is below a certain threshold that depends on the party’s stake, then the party is an eligible slot leader for that slot, with the same consequences as in Ouroboros Classic. Each leader then includes into the block it creates also the VRF output and a proof of its validity to certify its eligibility to act as a slot leader. The probability of becoming a slot leader is again roughly proportional to the amount of stake the party controls, however now it is independent for each slot and each party,as it is evaluated locally by each stakeholder for itself. This local nature of the leader election implies that there will inevitably be some slots with no, or several, slot leaders.In each epoch j, the stake distribution that is used in Praos for slot leader election corresponds to the distribution recorded in the ledger up to the last block of epoch j−2. Additionally, the epoch randomness for epoch j is derived as a hash of additional VRF-values that were included into blocks from the first two thirds of epoch j−1 for this purpose by the respective slot leaders.8Stake shift is a change in the stake distribution among the participants of the protocol. Finally, the protocol uses key-evolving signatures for block signing, and in each slot the honest parties are mandated to update their private key, making the system resilient to even adaptive corruptions.Security.

Ouroboros Praos was shown by David et al. [DGKR17] to achieve both persistence and liveness under weaker assumptions than Ouroboros Classic, namely:

• 1. semi-synchronous communication, where messages can be adversarially delayed for up to∆slots (where∆affects the security bounds but is unknown to the protocol);
• 2. majority of the stake is always controlled by honest parties (i.e., parties following the protocol);
• 3. the stake shift per epoch is limited.In particular, Ouroboros Praos is secure in face of fully adaptive corruptions without any corruption delay.

Sections 3

Cardano is an actively developed system, and as such will clearly need updates and improvements when new requirements arise, bugs are discovered, standards or protocols change, or new technologies become relevant. Traditionally, such software updates have been handled in an ad-hoc, centralized manner: Somebody, often a trusted authority, or the original author of the software, provides a new version of the software, and users download and install it from that authority’s website. However, this approach is clearly not decentralized, and hence jeopardizes the decentralized nature of the whole system: In a decentralized software update mechanism,proposed updates can be submitted by anyone (just like anyone can potentially create a transaction in blockchain).The decision of which update proposal will be applied and which won’t, is taken collectively by the community and not centrally. Thus, the road-map of the system is decided jointly. Moreover, there is no central code repository, nor there is some main software maintainer, who decides on the code. All versions of the code are distributed and only local copies exist, in the same manner that the ledger of transactions is distributed in blockchain. The decentralized software update system must reach a consensus, as to what version is the curren tone (main branch) and which code branch will be merged into main. Finally, the decentralized software update system guarantees the authenticity of the downloaded software, without the need to have some central authority to sign the code, in order to be trusted.At present, there is no standard way to propose updates, reach consensus on such proposals and then—once consensus has been reached—distribute updates securely to all participants. There is no way to guard against malicious proposals on the one hand, while on the other hand enabling critical security updates or bug-fixes to be distributed in swiftly.