---
CIP: ?
Title: Votes & Certificates on Cardano
Category: ?
Status:
Authors:
- Pyrros Chaidos <[email protected]>
- Raphaël Toledo <[email protected]>
- Arnaud Bailly <[email protected]>
Implementors:
- Cardano Scaling team <https://github.com/cardano-scaling/alba>
Discussions: []
Created: 2024-08-01
License: CC-BY-4.0
---
This proposal specifies a cryptographic protocol for distributed and decentralised stake-based votes and compact certificates, based on the Approximate Lower Bounds Arguments research paper.
Several existing or proposed extensions to Cardano protocol and network depend on a decentralised stake-based voting and certificates production mechanism:
- Mithril is already in production and provides certificates using a centralised aggregator, but work is underway to decentralise signatures diffusion and aggregation,
- Peras is an extension to Ouroboros Praos that depends on votes and certificates to provide boosts to some blocks of the chain, in order to reach faster settlement certainty,
- Leios is another proposed extension to Praos that depends on votes and certificates to endorse blocks and increase overall throughput of the network.
In general, having a decentralised protocol in place to build some small proof that a large enough quorum of the network's stake-holders have "seen" some piece of information has a lot of potential use cases: checkpointing and snapshotting state come to mind, but any kind of knowledge that's shared by all SPOs could potentially be voted for and "proven" through a cryptographically secure certificate.
Those protocols shares a lot when it comes to the overall process they follow to build a certificate:
- SPOs can cast their vote independently on some known piece of information according to the amount of stake they represent,
- Votes are diffused across the network,
- Any party (the prover) can independently aggregate a large number of individual votes into a much smaller certificate,
- A certificate can be verified independently, guaranteeing the prover actually witnessed some quorum of votes.
TODO, see https://alba.cardano-scaling.org ?
Warning
This should be rewritten and is copied verbatim from Peras Tech report #2
Voting in Peras is mimicked after the sortition algorithm used in Praos, e.g it is based on the use of a Verifiable Random Function (VRF) by each stake-pool operator guaranteeing the following properties:
- The probability for each voter to cast their vote in a given round is correlated to their share of total stake,
- It should be computationally impossible to predict a given SPO's schedule without access to their secret key VRF key,
- Verification of a voter's right to vote in a round should be efficiently computable,
- A vote should be unique and non-malleable. (This is a requirement for the use of efficient certificates aggregation, see below.)
Additionally we would like the following property to be provided by our voting scheme:
- Voting should require minimal additional configuration (i.e., key management) for SPOs,
- Voting and certificates construction should be fast in order to ensure we do not interfere with other operations happening in the node.
We have experimented with two different algorithms for voting, which we detail below.
We have used an identical structure for single Votes, for both algorithms. We define this structure as a CDDL grammar, inspired by the block header definition from cardano-ledger:
vote =
[ voter_id : hash32
, voting_round : round_no
, block_hash : hash32
, voting_proof : vrf_cert
, voting_weight : voting_weight
, kes_period : kes_period
, kes_vkey : kes_vkey
, kes_signature : kes_signature
]
This definition relies on the following primitive types (drawn from Ledger definitions in crypto.cddl)
round_no = uint .size 8
voting_weight = uint .size 8
vrf_cert = [bytes, bytes .size 80]
hash32 = bytes .size 32
kes_vkey = bytes .size 32
kes_signature = bytes .size 448
kes_period = uint .size 8
As already mentioned, Vote mimicks the block header's structure which allows Cardano nodes to reuse their existing VRF and KES keys. Some additional notes:
- Total vote size is 710 bytes with the above definition,
- Unless explicitly mentioned,
hashfunction exclusively uses 32-bytes Blake2b-256 hashes, - The
voter_idis it's pool identifier, ie. the hash of the node's cold key.
A vote is cast by a node using the following process which paraphrases the actual code
- Define nonce as the hash of the epoch nonce concatenated to the
perasstring and the round number voted for encoded as 64-bits big endian value, - Generate a VRF Certificate using the node's VRF key from this
nonce, - Use the node's KES key with current KES period to sign the VRF certificate concatenated to the block hash the node is voting for,
- Compute voting weight from the VRF certificate using sortition algorithm (see details below).
Vote verification requires access to the current epoch's stake distribution and stake pool registration information.
- Lookup the
voter_idin the stake distribution and registration map to retrieve their current stake and VRF verification key, - Compute the nonce (see above),
- Verify VRF certificate matches nonce and verification key,
- Verify KES signature,
- Verify provided KES verification key based on stake pool's registered cold verification key and KES period,
- Verify provided voting weight according to voting algorithm.
The first algorithm is basically identical to the one used for Mithril signatures, and is also the one envisioned for Leios (see Appendix D of the recent Leios paper). It is based on the following principles:
- The goal of the algorithm is to produce a number of votes targeting a certain threshold such that each voter receives a number of vote proportionate to
$\sigma$ , their fraction of total stake, according to the basic probability function$\phi(\sigma) = 1 - (1 - f)^\sigma$ , - There are various parameters to the algorithm:
-
$f$ is the fraction of slots that are "active" for voting -
$m$ is the number of lotteries each voter should try to get a vote for, -
$k$ is the target total number of votes for each round (e.g., quorum)$k$ should be chosen such that$k = m \cdot \phi(0.5)$ to reach a majority quorum,
-
- When its turn to vote comes, each node run iterates over an index
$i \in [1 \dots m]$ , computes a hash from the nonce and the index$i$ , and compares this hash with$f(\sigma)$ : if it is lower than or equal, then the node has one vote.- Note the computation
$f(\sigma)$ is exactly identical to the one used for leader election.
- Note the computation
We prototyped this approach in Haskell.
The second algorithm is based on the sortition process initially invented by Algorand and implemented in their node. It is based on the same idea, namely that a node should have a number of votes proportional to their fraction of total stake, given a target "committee size" expressed as a fraction of total stake
The process for voting is thus:
- Compute the individual probability of each "coin" to win a single vote
$p$ as the ratio of expected committee size over total stake. - Compute the binomial distribution
$B(n,p)$ where$n$ is the node's stake. - Compute a random number between 0 and 1 using nonce as the denominator over maximum possible value (e.g., all bits set to 1) for the nonce as denominator.
- Use bisection method to find the value corresponding to this probability in the CDF for the aforementioned distribution.
This yields a vote with some weight attached to it "randomly" computed so that the overall sum of weights should be around expected committee size.
This method has also been prototyped in Haskell.
The peras-vote package provides some benchmarks comparing the two approaches, which gives us:
- Single Voting (Binomial): 139.5 μs
- Single Verification (binomial): 160.9 μs
- Single Voting (Taylor): 47.02 ms
:::note
The implementation takes some liberty with the necessary rigor suitable for cryptographic code, but the timings provided should be consistent with real-world production grade code. In particular, when using nonce as a random value, we only use the low order 64 bits of the nonce, not the full 256 bits.
:::
Mithril certificates' construction is described in details in the Mithril paper and is implemented in the mithril network. It's also described in the Leios paper, in the appendix, as a potential voting scheme for Leios, and implicitly Peras.
Mithril certificates have the following features:
- They depend on BLS-curve signatures aggregation to produce a so-called State based Threshold Multi-Signature that's easy to verify,
- Each node relies on a random lottery as described in the previous section to produce a vote weighted by their share of total stake,
- The use of BLS signatures implies nodes will need to generate and exchange specialized keys for the purpose of voting, something we know from Mithril is somewhat tricky as it requires some form of consensus to guarantee all nodes have the exact same view of the key set.
Approximate Lower Bound Arguments or ALBAs in short, are a novel cryptographic algorithm based on a telescope construction providing a fast way to build compact certificates out of a large number of unique items. A lot more details are provided in the paper, on the website and the GitHub repository where implementation is being developed, we only provide here some key information relevant to the use of ALBAs in Peras.
ALBA's expected proving time is benchmarked in the following picture which shows mean execution time for generating a proof depending on: The total number of votes, the actual number of votes (
The following diagram is an excerpt from the ALBA benchmarks highlighting verification. Note these numbers do not take into account the time for verifying individual votes. As one can observe directly from these graphs, verification time is independent from the number of items and only depends on the 
In practice, as the number of votes is expected to be in the 1000-2000 range, and there is ample time in a round to guarantee those votes are properly delivered to all potential voting nodes (see below), we can safely assume proving time of about 5 ms, and verification time under a millisecond.
For a given set of parameters, namely fixed values for
Varying the security parameter and the honest votes ratio for a fixed set of 1000 votes of size 200 yields the following diagram, showing the critical factor in proof size increase is the
In the following tables we compare some relevant metrics between the two different kind of certificates we studied, Mithril certificates (using BLS signatures) and ALBA certificates (using KES signatures): Size of certificate in bytes, proving time (e.g., the time to construct a single vote), aggregation time (the time to build a certificate), and verification time.
For Mithril certificates, assuming parameters similar to mainnet's (
| Feature | Metric |
|---|---|
| Certificate size | 56 kB |
| Proving time (per vote) | ~70 ms |
| Aggregation time | 1.2 s |
| Verification time (certificate) | 17 ms |
For ALBA certificates, assuming 1000 votes, a honest to faulty ratio of 80/20, and security parameter
| Feature | Metric |
|---|---|
| Certificate size | 47 kB |
| Proving time (per vote) | ~133 us |
| Aggregation time | ~5 ms |
| Verification time (certificate) | 15 ms |
Warning
Don't know what to put in there, we'll need several rounds of back and forth
The proposed scheme (votes structure and ALBAs) fills in all the requirements of a generic voting and certificate system that can be applied to any kind of data that's shared by all SPOs, or a sufficiently large fraction of them.
Warning
Not sure what to put here
ALBAs voting and certificate production is available to all block-producing nodes through an API.
- Complete high-performance Rust library features & APIs
- Audit library for security
- Integrate library in cardano-node
- Approximate Lower Bound Arguments, Pyrros Chaidos, Prof Aggelos Kiayias, Leonid Reyzin, Anatoliy Zinovyev, May 2024, Eurocrypt'24
This CIP is licensed under CC-BY-4.0.