shortname: [18/TEP]
name: Transactional Election Process
type: standard
status: draft
editor: Alberto Granzotto <[email protected]>
contributors: Vanshdeep Singh <[email protected]>, Lev Berman <[email protected]>
This specification introduces the new concept of Election. An Election is an asynchronous process that when successful triggers Network wide changes synchronously (i.e. at the same block height). An Election is started by any Validator in the Network, called Initiatior. The Election itself and all cast Votes are transactions, hence stored in the blockchain. This enables new Validators to replay Network changes incrementally, while syncing.
Changing the shape of a BigchainDB Network at runtime is an important requirement. While this BEP does not address this issue directly, it wants to solve the limitations we had with Upsert Validators (BEP-3) by giving a tool that can be used this and other situations. BEP-3 addresses a really interesting use case: adding a Member to a running Network. Since changes in the Validator Set are not themselves expressed as transactions but are included into the metadata of an arbitrary block, all the nodes have to add a Validator simultaneously—if less than the majority of the nodes attempt to include a Validator, the block fails and the whole Network can stuck. Since those changes are not stored in the blockchain itself, a new Node that needs to sync with the Network will fail in validating blocks from a specific height on. The height will match the one of the first block voted by a new Validator that was not included in the genesis.json file (and Tendermint will fail with Invalid commit (last Validator set size) vs (number of precommits)).
The abstract version of the problem is "make Network wide decisions". We need a way for Members to vote on proposals, and implement them as soon as the quorum of ⅔ is reached. In this BEP, a proposal is named Election, a vote is a fungible token formalized with the capitalized name Vote Token. Elections and Vote Tokens are stored in the blockchain, so a new Node that syncs with the Network will be able to replay them locally, and reach the same state of all other Members.
The basic idea is to formalize the concept of an Election storing its data in a BigchainDB Transaction Spec v2 (BEP-13). Implementations of this BEP might introduce new operations for a BigchainDB Transaction Spec v2, and new validation rules for the Election transaction and the Vote transaction. By storing it in a BigchainDB Network, it allows Members to vote asynchronously, and Validators to apply changes synchronously.
At any point in time, a Member of a BigchainDB Network can start a new Election.This Member is called Initiator.
An Election is a transaction representing the matter of change, and some Vote tokens. The Initiator issues a CREATE transaction with the amount set to the total power of the Validators. The transaction has multiple outputs, one per Validator. Each output is populated with the public key of the Validator, and an amount equal to the power of the Validator.
At this point the Election starts. Independently, and asynchronously, each Validator can spend its Vote Tokens to an Election Address to show agreement on the matter of change. The Election Address is the id of the first CREATE transaction. Once the Vote tokens has been transferred to that address, it is not possible to transfer it again, because their private key is not known.
During the end_block call, all transactions about to be committed are checked. Every transfer of a vote token triggers a functions that counts the number of positive votes of Election over the number of voters. If the ratio is greater than ⅔, then the current Validator commits the change. Given the BFT nature of the system, all non-Byzantine Validator will commit the change at the same block height.
Each Validator checks every new transaction that is about to be committed in a block. The process is roughly the following:
- If the transaction is not a valid Vote, return.
- If the Vote is for a not valid Election, return.
- If the Election including the current Vote has less than ⅔ of positive votes, return.
- If the Election excluding the current Vote has more than ⅔ of positive votes, return. (It has been concluded already.)
- If the Election excluding the current Vote has less than ⅔ of positive votes and including the current Vote has more than ⅔ of positive votes, execute the logic to implement the Election.
A Validator must be able to discern valid Votes from invalid ones. A valid vote is a transaction that spends one or more Vote Tokens to the Election Address.
A Validator must be able to discern valid Elections from invalid ones. A valid Election is a transaction where all the following conditions are true.
operationisCREATE, or equivalent.- Each public key listed in
inputs.owners_beforebelongs to one of the Validators. outputs.amountis the total power of the Validators.outputshas as many entries as the total number of Validators.- Each Validator is represented in
outputs. - Each entry in
outputscan be spent by only one Validator, and the amount attached to it is equal to the power of that Validator.
Note: any change in the Validator Set will make old Elections invalid. Check approach 2 for a process that can tolerate a certain degree of change to the Validator Set.
Vote delegation is trivial. Let's consider a Network of three Members: Alice, Bob, and Carly. Alice is the Initiator, and starts a new Election. Alice generates a CREATE transaction with three outputs, one per each Member. Bob wants to delegate his vote to Carly, so he transfers his output to Carly, granting her more votes she can spend in the way she wants.
Let the Validator Set be denoted by at time
, a member of a BigchainDB Network can start a new Election. This member is called Initiator (
s.t.
) .
An Election proposal is a transaction representing the matter of change. The Initiator , issues a create election transaction
. The election MUST contain outputs such that each output is populated with the public key of the Validator
s.t.
, and an amount equal to the current power
of the Validator.
Once is committed in a block, the election starts. Independently and asynchronously, each Validator may spend its vote tokens (referred as
) to the election address
to show agreement on the matter of change. The Election Address
is the
id of the transaction .
NOTE: Once the vote tokens have been transferred to the election address
it is not possible to transfer it again, because the private key is not known.
At time let,
- Validator set be denoted by
s.t.
, where
denotes the set of public keys who voted for election
be the newly received vote token
In the constrained approach any change to the Validator Set invalidates all the elections which were initiated with a different Validator Set.
If below conditions hold true then the election is concluded and the proposed change is applied,
where
and
denotes the vote tokens received at
prior the the current token
The generalized constraints can tolerate a certain degree of change to the Validator Set.
If below conditions hold then the election is concluded and the proposed change is applied,
The above constraints state that if the Validators with which an election was initiated still hold super-majority then the election can be concluded.
Approach 1 is easier to comprehend and explain because of how constrained it is.
Approach 2 has two benefits over the Approach 1.
- Elections can have intersections. In other words, the following is possible:
election 1 creation height < election 2 creation height < election 1 conclusion height < election 2 conclusion height
- Elections can survive network updates. For example, each Validator in the network can move to a new address and delegate his vote to the new address. Elections created prior to such migrations can still be concluded.
For a start, we plan to implement Approach 1 because of its simplicity. We are able to switch to Approach 2 in the future by the means of a soft fork with additional support for the new type of elections described in Approach 2.
During the end_block call, all transactions about to be committed are checked. Every vote token triggers a function (which implements Approch 1 or Approach 2) that checks the necessary conditions. If the function returns True then the current Validator applies the suggested change in . Given the BFT nature of the system, all non-Byzantine Validator will commit the change at the same block height.
A blockchain is a Byzantine fault tolerant, replicated state machine. BigchainDB is a permissioned one, this means that the nodes that validate transactions and create blocks know about each other: their identity is not anonymous. This is not true for networks like Bitcoin or Ethereum: in those permissionless blockchains the Validator set changes over time and the identity is anonymous.
The reasoning behind this BEP exploits the permissioned nature of a BigchainDB Network, and the instant finality of the blocks.
In this context, a Member of a BigchainDB Network can start an election on a specific matter by calling out all Members. The election is successful when the supermajority (⅔ of the Network) agree on the matter.
The matter is domain specific, and can be something like adding a new Validator to the Network, adding support for a new transaction model, and so on. Each matter has some specific logic (code) that is triggered when the election is successful. All non byzantine nodes reach the same conclusion on the election at the same block height, and they all trigger the same logic if the election is successful (even if they voted against).
We had some discussions around the finality of an election. In the original design, the current Validator Set is used to decide the outcome of an election. Any change to the Validator Set would make all existing elections invalid. To overcome this issue, another approach has been proposed and documented. This new approach can tolerate a certain degree of change to the Validator Set.
This BEP is fully backwards compatible.
This BEP proposes a framework to handle Elections. An implementation of this BEP is another BEP that defines the scope of the Election and all the details related to it.
By now, this BEP has been implemented in:
To the extent possible under law, the person who associated CC0 with this work has waived all copyright and related or neighboring rights to this work.