# Proposal: Attributable Consensus Solution for DV Clusters **URL:** \ **Category:** Research\ **Created:** [December 12, 2023, 1:07pm UTC](https://community.obol.org/t/proposal-attributable-consensus-solution-for-dv-clusters/104 "2023-12-12T13:07:07Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![albert\_garreta](https://avatars.discourse-cdn.com/v4/letter/a/ecb155/32.png) [@albert\_garreta](https://community.obol.org/u/albert_garreta)\ **Post date:** [December 12, 2023, 1:07pm UTC](https://community.obol.org/t/proposal-attributable-consensus-solution-for-dv-clusters/104/1 "2023-12-12T13:07:07Z")
# Background The performance of validators run by a DV cluster depends on the cluster operators doing their jobs successfully and timely. However, these validators may exhibit good performance metrics even if some operators perform poorly or are always offline altogether. While, in principle, this is in the core ethos of DV technology (i.e. allowing well-meaning operators to have faults while keeping the validators unaffected), it is also susceptible to abuse. Indeed, without a special design around it, an operator may, by maliciousness or carelessness, perform its tasks lousily and yet get the same amount of rewards as the rest of the operators. In this proposal we address this potential pitfall. We want principal providers and any third party to be able to check the performance and availability of the operators verifiably. This is especially important to enable clusters where operators do not know or trust each other. For example, an operator in a cluster where a minority of operators are notoriously offline should be able to attest to this fact, and cut this minority of operators from receiving rewards. Another feature we want to enable is for a minority of online operators to be able to prove they were online, even if the cluster validators could not perform their tasks (due to not enough cluster operators being online, in which case threshold signatures cannot be created). All these allow for a fair reward distribution, where the rewards go to well performing operators. Here, we describe a mechanism that enables the goals above. Due to the length of our solution, we will split our description into 3 posts. The contents of each post are the following: - **Post 1 (this one)**: We describe the problem and its corresponding challenges. We then provide a high level overview of the whole scheme. Finally, we explain how the so-called “Participation Proofs” (see below) are constructed. - **Post 2** : We will explain how participation proofs are used to assign rewards to cluster operators. We will also describe in detail how the correctness of Participation Proofs is ensured via a whistleblower mechanism. - **Post 3** : We will get into low level details of the economics of our solution, as well as the cryptographic details of how certain fraud proofs are verified. **Remark** : Here, we use the term “attributability” more broadly than is sometimes used in the literature. Papers like [BFT forensics](https://arxiv.org/abs/2010.06785) use the term to refer to the ability of detecting nodes that caused a fork in a consensus chain (i.e., detect safety violations). Here, we instead want to identify nodes that were online and nodes that were offline (i.e., detect liveness). ## Problem statement In this post, we aim to design a mechanism that enables the following: - Approximately identifying which operators participated in which duties performed by a DV cluster. - Identifying operators O that were ready to participate in a task, even if the task was ultimately performed without $O$’s collaboration. This should be doable in the following circumstances: - A majority of the cluster operators were offline (and hence, it was impossible to perform the task since the signing threshold could not be met). - A majority of the cluster is colluding against O, preventing O from participating. - O was ready to participate but was not fast enough to do so. For example, a threshold of very fast cluster operators (to which O does not belong) may produce a signature on a block proposal without O 's partial signature. In this scenario, O does not get a chance to participate in the task. However, it is important to still reward O as it fulfills an important DV role: to save the day when one of the slow operators malfunctions. - The participation claims from the previous points should be verifiable on-chain. - The solution should cost at most \approx 1 USD per validator per month. That cost should be split among all operators. Dishonest operators may incur a much higher cost. - Rewards should be fairly assigned to operators, depending on their participation (and readiness to participate) record. ## Challenges - **Malicious exclusion** : Depending on how rewards are distributed, any majority of operators in a DV cluster may be better off ignoring the rest of the operators. This allows the majority to pretend that only the majority participated/was online. - **Minority:** An operator O may be online and ready to participate in DV tasks. However, if a majority of the cluster is offline, O won’t be able to perform any task. Still, we would like O to be able to prove this and get appropriately rewarded for that. - **Latecomers** : An operator in the DV cluster may not participate in performing the cluster duties and even be offline. However, this operator may later go online and pretend that it somehow participated in all tasks. This should not be doable. - **Non-attributability of threshold BLS signatures** : The threshold BLS signature scheme used by Charon DV clusters to perform the validator duties makes it impossible to identify, solely from the aggregated signature, which parties participated or were ready for their corresponding duties. # Overview In this section we provide a high-level overview of our mechanism. The precise details are provided in the subsequent sections. **Fast track** In our solution, clusters normally perform their DV duties through a fast consensus protocol. As usual, the goal of the cluster is to agree on what messages the cluster validators should sign with their respective validator keys. This is done as quickly as possible, and once a quorum (i.e., at least 2/3-rds) of the operators have reached an agreement, the message is signed and sent. This component of the solution is called the **fast track**. **C-slots and optimistic Participation Proofs** After a certain amount of time, which we call **c-slot** (lasting a day on average), the DV cluster runs an additional consensus instance. On this occasion, the cluster seeks to agree on what duties the cluster validators have performed within a certain time window. The consensus produces a piece of data L with this information and a BLS aggregate signature \mathcal{S} of individual operator signatures (this includes a bitfield indicating whose signatures were used). The pair (L,\mathcal{S}) constitutes what we call an **optimistic Participation Proof (PP)**. It is “optimistic” because its reliability depends on optimistic assumptions regarding the behavior of the cluster operators. Once (L,\mathcal{S}) is produced, it is hashed. The hash is signed by the cluster operators via a threshold signature and sent to a smart contract in a Layer 2 network within a time window \Delta\_{update}. The end of a c-slot occurs randomly and unpredictably. This way, operators that want to include their signature in the aggregate \mathcal{S} must remain online and alert. We assume that, at that point, operators will participate in the cluster duties altogether. While this may not always be the case, we believe it achieves an appropriate balance in the tradeoff between reliability and gas costs. **C-epochs and whistleblowers** Every 14 days (a period of time which we call **c-epoch** ), the cluster makes all the optimistic PPs available. Then, **whistleblowers** can check that the contents of these PPs are correct and raise an alarm if this is not the case. To make the Participation Proofs available to the public, the cluster uses EIP-4844 to create a blob transaction on Ethereum, submitting the PPs as a data blob. An L1 (Ethereum) smart contract stores pertinent hashes and commitments to this data, whose components can be checked against the hashes stored in the L2 in the previous steps. Any whistleblower has ample time to review the proofs and raise complaints if needed. If this occurs, the optimistic PPs are verified on-chain. If the verification fails, whistleblowers lose a bond they had deposited, and otherwise, the cluster is penalized. Most on-chain verifications occur on the L2 SC to avoid high gas costs, and any party can act as a whistleblower. To avoid an irrational operator submitting bogus blob data on behalf of an entire cluster, we have the cluster create a threshold signature on the data before this is posted to the L1 SC. Whistleblowers can now raise an alarm if the threshold signature is incorrect. To amortize transaction costs, we also allow clusters to form **coalitions**. A coalition of clusters submits a single blob transaction containing all the participation proofs of all clusters in the coalition. This solution addresses the challenges of “latecomers” and “non-attributability of BLS signatures.” To address “malicious exclusion,” we design our reward mechanism so that operators gain more rewards the more signatures in the lists \mathcal{S} there are. This way, rational operators are incentivized not to exclude other operators. At the same time, operators cannot simply add incorrect signatures to increase their rewards since whistleblowers can then raise a complaint. **Pessimistic or VDF Participation Proofs** It remains for us to address the challenge we call “minority.” We would also like to protect operators against “malicious exclusion” when some operators are irrational (and hence are willing to lose some rewards to exclude others). To this end, we introduce a second type of Participation Proof based on Verifiable Delay Functions (VDF). Any operator may create such proofs and submit them instead of relying on the optimistic PPs. An operator can create The VDF PPs individually without collaborating with anyone else. Hence, they provide resilience against “minority” and “malicious exclusion.” However, VDF PPs are more costly computationally than optimistic PPs, and so we envision a scenario where, as long as things run smoothly, operators rely solely on optimistic PPs, and rarely submit VDF PPs. A VDF PP consists of proofs of correct computation of a Verifiable Delay Function. As part of its input, the VDF function takes certain randomness derived from an L2 (namely, block headers) to avoid operators computing the VDF PP ahead of time. A VDF is a function of relatively high computation cost and hard to parallelize. Additionally, VDFs are built together with a mechanism that allows to quickly and cheaply verify that such function was computed correctly. **Points and rewards** As we mentioned, we want to distribute the rewards earned by the cluster validators fairly. Our idea of fairness is roughly the following: - **Lenience for occasional faults** : Operators who have been mostly online and ready to perform duties should receive almost no penalties, even if they stumble occasionally. - **Heavy penalization for significant faults** : Operators who have not participated —or have not been ready to participate— for a significant amount of time should receive a small share of the rewards. To accomplish these goals, we assign **participation points** to operators for the duties where they participated or were ready to participate (these are computed according to the information in the optimistic PPs and VDF PPs). At the end of a c-epoch, the participation points are converted to a share of rewards. The conversion leverages a logistic points-to-rewards mapping. This mapping has an “S shape”: intuitively peaking, it assigns roughly an even share of rewards if points exceed 3/4ths of the maximum amount of points achievable. Below this threshold, the mapping quickly decays and becomes negligible when the amount of points collected is small. Participation points are not computed on-chain. Instead, an operator in the cluster locally computes and submits the points each operator gained. The points are submitted to the L1 SC at the end of a c-epoch. If the operator were to cheat, a whistleblower could raise an alarm. **Diagrams** ![obol_diag_1](https://europe1.discourse-cdn.com/flex013/uploads/obol/original/1X/d7eab5f2f81465ef54002698fdafca722908695a.png) ![obol_diag_2](https://europe1.discourse-cdn.com/flex013/uploads/obol/original/1X/1002cf6330f4726223fb2ff95d6a669cf50be87a.png) **Costs for honest parties** We next outline the computational and gas costs of our solution. We only describe the costs incurred by honest parties. Malicious actors may end up paying much more since they will be responsible for the costs of on-chain verifications of optimistic and VDF proofs (in case a whistleblower raises an alarm). At the end of a c-epoch (once every 14 days), an operator in each cluster coalition: - Updates an L1 SC with the points each cluster member earned. This means that less than 256 bits are updated. - An L1 SC stores the 256-bit versioned hash to the blob data and the 381-bit KZG commitment. This costs less than 1.5 USD as of November 2023. - Creates a blob transaction with all PPs created during the c-epoch by the clusters in the coalition. - The L1 SC stores the identity of the operator submitting all the previously mentioned data and the gas costs of all these transactions (for reimbursement purposes). This amounts to updating at most 32-byte variable. **L2 costs** In the optimistic path, at the end of each c-slot (on average, a c-slot lasts a day), each cluster: - Submits the following data to an L2 SC: - The threshold signature is verified on the L2 SC (this is cheap since computation in the L2 is cheap). As with the blob transaction gas cost, it is not possible to estimate the cost of these operations reliably at the moment. This is because data storage costs in L2s are bound to change significantly once EIP-4844 starts running. # Terminology, notation, assumptions We begin by describing some assumptions and terminology our solution uses. ### Assumptions - We have a reliable L2 with a L1-L2 messaging service that can send data from an L1 Smart Contract to an L2 SC and vice versa. We don’t require this messaging to be fast or super predictable in execution time. Candidate L2’s are StarkNet and Arbitrum. Docs for L1↔L2 messaging can be found [here](https://docs.starknet.io/documentation/architecture_and_concepts/Network_Architecture/messaging-mechanism/#l2-l1_messages) and [here](https://docs.arbitrum.io/arbos/l1-to-l2-messaging). - Blocks in the L2 are produced at regular, known intervals of time. ### Terminology and notation - C-slot — A collection of consecutive L2 blocks of random length. On average, a c-slot lasts E\_{cslot} time. Currently E\_{cslot}=1 \text{ day}. - C-epoch — A collection of consecutive c-slots. The number of c-slots comprising a c-epoch is variable, but a c-epoch always lasts a number of L2 blocks equivalent to 14-15 days. In expectation, a c-epoch is comprised of 14-15 c-slots. - L1 Smart Contract (SC) — An SC on the L1. - L2 SC — An SC on the L2. - n — Used to denote the number of operators in a cluster. Note, n may be different among different clusters. - Participation Proof (PP) — Verifiable information on the activity of each operator during a c-slot. - Optimistic PP — A PP produced via cluster consensus. It is a pair (L, \mathcal{S}) where: - Verifiable Delay Function (VDF) PP — A PP produced using VDF computations and proofs. - VDF-c-slots (AKA mini-c-slot) — a VDF-c-slot lasts for a random amount of time and for 1 hour in expectation (this is customizable). - \Delta\_{update} — The number of L2 blocks that can be finalized between the end of a c-slot and the moment a cluster submits a commitment to its PP on the L2 SC. - L1 ↔ L2 messaging service — A reliable mechanism that allows L1 Smart Contracts to call functions of L2 Smart Contracts and vice-versa. - Hash\_{L2} — A hash function whose computation gas cost is cheap in the L2. E.g., if the L2 is Starknet, Hash\_{L2} can be the Rescue hash function. - Blob data — A type of data attached to Ethereum transactions that is kept by the consensus nodes for 18 days, and deleted afterward. It will be enabled in [EIP-4844](https://eips.ethereum.org/EIPS/eip-4844). - Hash(Com(\*)), versioned hash — A 256-bit Keccak hash of a BLS12-381-based KZG commitment of blob data. Cf. [EIP-4844](https://eips.ethereum.org/EIPS/eip-4844). - Whistleblower — An agent that locally verifies the correctness of PP (and other data) submitted by cluster operators. If this verification fails, the whistleblower can raise an alarm. - Points — Cluster operators earn points for, roughly, the duties they took part in. Points are later converted to rewards. - \Delta\_{data} — The number of L1 epochs allowed for submitting blob data and points earned to the L1 SC at the end of a c-epoch - \Delta\_{accuse} — The number of L1 epochs during which whistleblowers can raise complaints. - B[C] — Blob data submitted by a cluster C in a given c-epoch (which we omit from the notation). This is a list - Duty types — There are five validator duty types, each encoded by an integer: 1 → Attestation; 2 → Block proposal; 3 → Sync committee duty; 4 → Sync committee aggregation duty; 5 → Attestation aggregation duty. - \Delta\_{L2block} — Time between the finalization of L2 blocks. We assume \Delta\_{L2block} is the same for all blocks, up to a small error modeled via a random variable \varepsilon\_{L2block}, with expectation 0. - Cluster coalition — A set of clusters that submits blob data “together” (to save on transaction costs). - Aggregator — An operator that submits the blob data of a whole cluster coalition. # Participation Proof mechanism ## O **ptimistic** Participation Proofs At the end of a c-slot, the cluster of operators uses a consensus protocol to agree on the following data (the details of this consensus protocol will be described in a further post): - A piece of data L consisting of: - \mathcal{S}, a pair (S, B) consisting of a BLS signature S on the data L and a bitfield B of length n. We expect S to be the aggregated signature of individual operator BLS signatures on L. The bitfield B indicates whose signatures were used for aggregation. **Note** : Verifying the aggregate signature S, which is expensive both in L1 and L2, will only occur when a whistleblower complains. In that case, we will operate on the EVM, assuming a precompile for BLS pairings. The gas cost, in that case, is between 150k and 200k. - The hash Hash\_{L2}(L, \mathcal{S}) of the above data. - A threshold signature on Hash\_{L2}(L, \mathcal{S}), denoted TS(Hash\_{L2}(L,\mathcal{S})). We call (L, \mathcal{S}) an _optimistic Participation Proof_. **What is expected of an optimistic PP** The following requirements are expected to be met by an optimistic PP. If some are not, a whistleblower can raise the alarm, resulting in penalizations for the cluster participants and rewards for the whistleblower. - The signature in \mathcal{S} is valid, and the bitfield contains at least 2n/3 ones (1). - L.start contains correct information. I.e., the L2 block number and header at which the c-slot started are correct. - The amount of attestation missed, as recorded in L.attestations, is coherent. Precisely, - Let i=2,3,4 and let (j\_{i1},\ldots, j\_{in\_i}) be the i-th sequence in L.slots. Let 1\leq t\leq n\_i. **Size of an optimistic PP** - Size of L.attestations. We have - Size of L.slots.2 — Block proposals. - Size of L.slots.3 — Sync committee - Size of L.slots.4 — Sync committee aggregation duty ![obol_table_4](https://europe1.discourse-cdn.com/flex013/uploads/obol/original/1X/caa8d7a00b8a708390591c014d4701eb1e0bdb14.png) - Overall size. ### On attestation aggregation duties Currently, in each attestation committee (128 validators), 16 validators are selected for aggregation duties. Since a validator is added to an attestation committee once per epoch, this means that, in expectation, a validator is in an aggregation committee every eight epochs. Since there are \approx 3100 epochs in a c-epoch (14 days), a cluster with N\_v validators is assigned N\_v\cdot 390 duties of Type 5 in a c-epoch. These are too many to be recorded in the optimistic PP (L,\mathcal{S}): having N\_v=10, would lead to a $\approx 2.5$KB sized list L. For N\_v=1000, in expectation, the cluster performs more than one aggregation duty per slot. Instead, we use the following heuristic: we assume that a validator performs an aggregation duty for every 88 attestation duties. In other words, we assume validators perform exactly the expected number of aggregation duties (restricted to epochs where they performed an attestation duty). Thus, we assume that the number of aggregation duties performed by the cluster in a c-slot is (N\_v\cdot N\_{epochs}- L.attestations)/8 where, as explained previously, N\_{epochs} is the number of L1 epochs spanned during the c-slot. Possible issues with this approach may arise when the actual number of aggregation duties assigned to the validators differs greatly from the expected number. However, we argue next that this occurs very infrequently. Indeed, the actual number of aggregation duties assigned to the cluster’s validators is modeled by a random variable X following a binomial distribution on N\_v\cdot 3100 experiments with success probability 1/8. The expectation of this random variable is \mathbb{E}(X)=N\_v\cdot 3100/ 8 \approx N\_v\cdot 390. And its standard deviation is std(X) = \sqrt{N\_v\cdot 3100 \cdot \frac{1}{8}\cdot\frac{7}{8}}\approx 18.41\cdot \sqrt{N\_v} This is a relatively small standard deviation, and indeed the ratio of \mathbb{E}(X) + \lambda \cdot std(X) and \mathbb{E}(X) is 1+\lambda\cdot\frac{0.05}{\sqrt{N\_v}} ![obol_table_5](https://europe1.discourse-cdn.com/flex013/uploads/obol/original/1X/ec17ff41561852872f2a0dce0c5e8969df74e558.png) We see, therefore, that about once in 25 c-epochs (1 year), the aggregation tasks assigned to a cluster will deviate by more than two standard deviations from the mean. However, even in that scenario, the relative error with respect to the expectation E(X) is very small. Additionally, about once every three c-epochs (1.5 months), the aggregation tasks assigned to the cluster deviate by 1 standard deviations. However, the relative error from the expected number E(X) is very small in this case. ## End of a c-slot The end of a c-slot is triggered when one of the following events occurs: - The following two hold: - The header of the most recent finalized L2 block starts with N\_{cslot} 1 ’s. - The c-slot has lasted so far for at least two hours (or some customizable amount of time). This is to avoid having super short c-slots, which could cause latency issues due to different consensus processes taking place simultaneously. - The end of the current c-epoch has been triggered (see below). Here N\_{cslot} is a parameter that can be used to control how long, in expectation, a c-slot lasts for. It will need to be adjusted so that a c-slot lasts in expectation for E\_{cslot} time (currently set at 1 day). The choice of N\_{cslot} depends on the L2 we work on, so we leave it unspecified. 👉A key point is that the end of a c-slot is “random and unpredictable.” The motivation for having this is that operators cannot plan ahead of time and, for example, log in right before the c-slot ends so as to add their signatures to the participation proofs (in this event, the rest of the operators would want to include the late comer operator, due to how our reward mechanism works —we will explain this in a future post). **Note** : It may be the case that blocks are produced too slowly to be able to properly tune N\_{cslot} so that c-slots last our desired expected amount of time. Then, we can use a hash of the block header. Choosing a hash with a larger digest bit-size then allows to be more granular in choosing N\_{cslot} and the expected duration of c-slots. When any of the above two requirements is met, any actor can trigger the L2 SC, calling a specific function. Any actor can trigger the L2 SC. To incentivize this, we offer a small reward for doing so. Note that we can’t rely on cluster operators to make this trigger since the operators could be interested in extending the duration of the c-slot (for example, if the cluster operators performed poorly during the current c-slot). When the L2 SC is triggered with an “END C-SLOT” call: 1. The L2 SC checks that one of the two conditions above is met. 2. The L2 SC records the corresponding L2 block number, say b. 3. The L2 SC checks if the end of the c-slot marks the end of the c-epoch. The details of this step are described later on. 4. Each cluster has \Delta\_{update} L2 blocks of time to submit Hash\_{L2}(L,\mathcal{S}) and the threshold signature TS(Hash\_{L2}(L,\mathcal{S})) to the L2 SC. 5. The L2 SC checks whether the threshold signature is valid. This can’t be left for the whistleblowers to check: if it was, an irrational operator could send invalid threshold signatures, griefing the cluster for an entire c-epoch. 6. The L2 SC reverts if any of the following happens: ## End of a c-epoch A c-epoch lasts for a variable number of c-slots. More precisely: - When a c-slot ends, the L2 SC checks whether the number N\_B of L2 blocks finalized during the current c-epoch corresponds, in time, to 14-15 days. Precisely, the c-epoch ends when one of the following checks passes in the L2 SC: - If this is the case, the c-epoch number in the L2 SC is updated, and a new “point settlement phase” (which we will describe in a future post) is initiated. - The L2 SC sends the message “END OF C-EPOCH” to the L1 SC, as well as N\_B and the number M of c-slots that comprised the c-epoch. The L1 SC stores this data, it updates its c-epoch number, and begins a new “point settlement phase”. **Note:** We want c-epochs to all last roughly the same time because, as we will see next, c-epochs also control the time clusters, and whistleblowers have to settle the points accumulated in the previous c-epoch. This settlement is a complex process with different subphases, which, for safety, should last a fixed amount of time. ---
**Author:** ![velvetmilkman](https://dub1.discourse-cdn.com/flex013/user_avatar/community.obol.org/velvetmilkman/32/80_2.png) [@velvetmilkman](https://community.obol.org/u/velvetmilkman)\ **Post date:** [January 10, 2024, 4:35pm UTC](https://community.obol.org/t/proposal-attributable-consensus-solution-for-dv-clusters/104/2 "2024-01-10T16:35:02Z")
> [@albert\_garreta](#): > > We have a reliable L2 with a L1-L2 messaging service that can send data from an L1 Smart Contract to an L2 SC and vice versa. > [@albert\_garreta](#): > > Alternatively, at any time, regardless of whether a c-slot has ended or not, anyone can end the c-epoch if NB⋅ΔL2blocks\>15⋅daysN\_B\cdot \Delta\_{L2blocks} \> 15\cdot daysNB​⋅ΔL2blocks​\>15⋅days (and whoever does so earns a small reward). In that case, the c-slot also ends. > > This is to avoid c-epochs lasting much more than 151515 days on rare occasions. Is there any risks associated in situations where an L2 sequencer losing liveness for an extended period of time? It seems that the biggest impact is to submit the HashL2(L,S)Hash\_{L2}(L,\mathcal{S})HashL2​(L,S) and the threshold signature TS(HashL2(L,S))TS(Hash\_{L2}(L,\mathcal{S}))TS(HashL2​(L,S)) to the L2 SC. ---
**Author:** ![albert\_garreta](https://avatars.discourse-cdn.com/v4/letter/a/ecb155/32.png) [@albert\_garreta](https://community.obol.org/u/albert_garreta)\ **Post date:** [January 15, 2024, 1:33pm UTC](https://community.obol.org/t/proposal-attributable-consensus-solution-for-dv-clusters/104/3 "2024-01-15T13:33:37Z")
Hey @velvetmilkman! Thanks for the question. The risk would be that the Hash of the optimistic participation proof doesn’t make it to the L2 SC within the time window Delta\_update. The parameter Delta\_update should be set up so that this it is almost impossible that the hash is delayed by such amount of time while the L2 keeps finalizing blocks. At the same time Delta\_update cannot be too large as this could allow very slow or offline operators to submit hashes of proofs too late in time. I would say that setting Delta\_update = 1,2 hours should work for both goals here.