Differences Between Paper and Implementation
The goal of this document is to enumerate all ways in which
implementation differs from the specifications presented in the paper and
to clarify everything that may be obscure after reading the paper.
This document is divided into four parts:
- Clarifications part clarifies some details which are not specified in the paper, but are important for practical implementation.
- Modifications part outlines things which are specified in the paper, but are implemented differently in Cardano SL.
- Added features part briefly mentions new features which are not described in paper, but have been implemented in Cardano SL.
- Omissions part lists topics described in paper but not implemented into Cardano SL.
Time, Slots, and Synchrony
In a basic model of Ouroboros time is divided into discrete units called slots. However, there are no details on how to obtain current time securely and with enough precision.
cardano-sl, current time is obtained by querying a predefined set of NTP
servers. Specifically, each node periodically queries NTP servers and calculates
mean of results. A node stores last margin (the difference between local time and
global time) and last obtained global time. А node also stores last slot to ensure
that slots are monotonic. Please read about Time in Cardano SL
for implementation details.
Coin Tossing and Verifiable Secret Sharing
As Ouroboros paper suggests, PVSS scheme by Schoenmakers is used in
cardano-sl. One of the challenges while using a VSS scheme is associating the
public key used for signing with the public key used for VSS scheme
VssPublicKey). This is solved by introducing
certificate is a signature given by a signing key for a pair consisting of
VssPublicKey and the epoch until which this certificate is valid. Initially,
all stakeholders with stake enough for participation in randomness generation
have certificates. When a new stakeholder with enough stake appears or when an
existing certificate expires, a new certificate should be generated and
submitted to the network.
VssCertificates are stored in blocks.
PVSS scheme by Schoenmakers uses share verification information which also includes a commitment to the secret. It is also used as a commitment in Ouroboros protocol. The PVSS scheme has been implemented over the elliptic curve secp256r1. Please read about PVSS implementation in Cardano SL for more details.
Block Generation Time
In Ouroboros paper, they do not state explicitly when a slot leader should
generate a new block and send it to the network: it can be done at the beginning
of a slot, at the end of a slot, in the middle of a slot, etc. In
there is a special constant called “network diameter” which approximates maximal time
necessary to broadcast a block to all nodes in the network. For example, if network
diameter is 3, then block is generated and announced 3 seconds before the end of a slot.
Delegation scheme, as described in the paper, does not explicitly state whether proxy signing certificates should be stored within the blockchain (though there is a suggestion to store the revocation list in the blockchain). Without storing proxy signing certificates in the blockchain it is barely possible to consider delegated stake in checking eligibility threshold. On the other hand, if all certificates are stored in the blockchain, it may lead to a blockchain bloat when a big portion of blocks will be occupied by proxy certificates. Submitting a certificate is free, so adversaries can generate as many certificates as they want.
There are two types of delegation in
cardano-sl: heavyweight and lightweight.
There is a threshold on stake that one has to posses in order to participate in
heavyweight delegation. Proxy signing certificates from heavyweight delegation
are stored within the blockchain. On the contrary, lightweight delegation is
available for everybody, but certificates are not stored within the blockchain
and are not considered when checking eligibility threshold. As the paper suggests,
delegation-by-proxy scheme is used.
Please read about Stake Delegation in Cardano SL for implementation details.
Leader Selection Process
In Ouroboros, Leader Selection Process is described as flipping a
(1 - p₁) … (1 - pⱼ₋₁) pⱼ-biased coin to see whether the
j-th stakeholder is
selected as the leader of the given slot. Here
pⱼ is probability of selecting the
cardano-sl, it is implemented in a slightly different way.
numbers in a range
[0 .. totalCoins] are generated, where
R is a number of
slots in an epoch. Stakeholders occupy different subsegments on this range,
proportional to their stakes. This way, each random number maps into stakeholder.
Also, as the paper suggests, a short (32-bits) seed is used for initializing PRG
instead of using
n ⌈log λ⌉ random bits.
Please read about Leader Selection in Cardano SL for implementation details.
Commitments, openings, shares sending
Time of sending is randomized within a small interval. It is done to avoid network overload when all coin-tossing participants send their data at the same time. This interval is chosen to be small enough for protocol to remain secure. If this data is sent too late and there are many adversaries leading last few slots of a certain phase, it can happen that data will not be included into the block.
In Ouroboros, each stakeholder is presented as exactly one participant of the underlying VSS scheme. However, it is natural that a stakeholder with more stake is more important than a stakeholder with less stake with regards to secret sharing. For instance, if three honest stakeholders control 60% of stake in total (each of them controls 20%) and there are 40 adversary stakeholders each having 1% of stake, then the adversary has full control over secret sharing.
To overcome this problem, a number of shares for each stakeholder proportional
to their stake is generated in
Randomness Generation Failure
Ouroboros does not cover the situation when commitments cannot be recovered.
However, a practical implementation should account for such scenarios.
cardano-sl implementation uses a seed consisting of all zeroes if there are no
commitments that could be recovered.
See the article on update system.
Security of P2P
See the article on P2P implementation and hardening.
The sections on Input Endorsers and Incentive Structure are not implemented yet. Those sections are to be implemented together with the pending research on Side-chains and released within the Side-chains release.