This paper describes how non-interactive BLS signature aggregation1 can reduce the nothing-at-stake effect in proof-of-stake blockchains. It relies on two assumptions: that nodes' clocks are set to the same time and that at least 1% of participants are well-behaved. It also describes a simple transaction receipt mechanism that enables near instant confirmation times.
Blockstream's sidechains paper2 provides a good context to introduce the concept:
We observe that Bitcoin's blockheaders can be regarded as an example of a dynamic membership multi-party signature (or DMMS), which we consider to be of independent interest as a new type of group signature. Bitcoin provides the first embodiment of such a signature, although this has not appeared in the literature until now. A DMMS is a digital signature formed by a set of signers which has no fixed size. Bitcoin's blockheaders are DMMSes because their proof-of-work has the property that anyone can contribute with no enrolment process.
Inspired by this observation, we can simulate the process using regular EC multi-party digital signatures. This is equivalent to a proof-of-work DMMS if we assume a mechanism that allows participants to 1. expend resources to produce signing keys that 2. can sign exactly once, and 3. participants have a way to aggregate the signatures produced by these keys instantly and across any distance.
Of course, we can't assume these things and this contrived hypothetical is impossible, but we can simulate the three ideal properties with proof-of-stake in the following ways. 1. Introduce an artificial cost. 2. Use a a regular multi-party signature with many signers who have agreed to destroy their keys. 3. Use BLS signatures to allow aggregation of the result into a single 48 byte signature.
Traditional proof-of-stake systems are an example of this, drawn out over many blocks. In those systems, honest behaviour is simply not reusing a key. In this construction, it also includes destroying the key once the network confirms their block.
Usually with proof-of-stake systems, the arguments against parties behaving dishonestly are 1. it would require a large amount of funding or coordination and 2. it would decrease the value of their stake. These claims are far from formalized and may not be true, but analysis is beyond the scope of this paper. For our purposes we make the assumptions 1. that at least 50% of participants will be online to sign blocks, 2. that most of the time 100% will sign within the allocated time-frame to avoid the network banning them, and 3. that at least 1% will not sign multiple blocks for the same height.
To enroll as a notarizing party ("signer"), the operator must send a fixed deposit to an unspendable address. The transaction must include the block signing key information. The owner receives the deposit back when they unenroll.
A primary signer, randomly selected using a decentralized random number generator, signs each block. It is then sent out to a committee of 256 other block signers, also chosen randomly, who each add their own signature to the block.
To provide entropy for the decentralized random number generator, and increase security, signers are requested to rotate their signing key every time they create a block. Each block's 64 bit random seed is the previous block's seed xored with 64 bits of the newly revealed signing key. Keys are committed to prior to disclosure to prevent attacks on the RNG.
A threshold number of signers are assumed to be "honest" signers. Assuming that the network has at most 92% dishonest signers, the probability that every member of a committee is dishonest is less than 1e-9.
However, we cannot halt blockchain progress if one member decides not to sign or is temporarily offline, so we consider any block with at least 2/3rd of signatures to be valid. This 2/3rd majority threshold is the midpoint in a trade-off between the number of dishonest parties required to halt the blockchain, and the number of dishonest parties required to create a fork.
BLS signatures allow the group block signatures ("witness signatures") to continue collecting new signatures well after the network confirms the block. The network can ban signers who don't provide their signature after a certain amount of time. This incentivizes 100% of signers to provide their signatures, despite if they are occasionally offline.
To achieve consensus before providing witness signatures, the committee members cast rounds of voting about whether the required block was late. Every vote after the first round of voting should be cast to reflect the maximum tally result. This is so that near even splits or low-turnout votes will snowball into a 2/3rd majority as quickly as possible. For ties, signers should favour a candidate with the greatest timestamp. Once a round with 2/3rds majority happens, the network confirms or rejects the candidate block.
The consensus votes are ephemeral and not used for the witness signatures on the chain. This is so the network can penalize nodes that send contradicting votes, whilst permitting nodes who voted against the consensus to add their witness signature after they observe the confirmed block.
If more than 1/3rd of the committee stops participating in multi-party signature generation then the blockchain will halt. 1/6th of the participants can expect to appear in 1/3rd of the committee about once every 111 thousand blocks. To mitigate this issue, progression after a timeout is possible with at least 50% of all the network's signers. This brings the minimum cost of halting the network 50% of the network stake.
In the unlikely event of a reorganization, nodes should select the branch with the most witness signatures. If they are the same, the network compares the following block, then the one after that, and so on.
The signer responsible for creating the upcoming block can broadcast a signed a promise to include a transaction. If the signer then creates a block without the transaction, the committee will reject it. It is possible for blocks with broken promises to appear in the chain, as promises may be unknown to the committee at the time when they confirm the block. Proof of broken promise can result in a ban.
Bans are validated with proofs of any of the following, up to 120 blocks after the event:
I chose the constants arbitrarily.
The is no information that can prove that a witness signature was missing at the time it was required, so instead we take unanimously committee signatures stating that the witness signature was missing from the committee 60 blocks later as justification for a ban.
A malicious actor would need 90% ownership of the network to produce arbitrary bans, or 50% if we assume 4/5 of nodes will participate in selfish banning without collaboration. Even with those conditions, a committee capable of producing an arbitrary ban will only form about once every 4000 years.
100% of the nodes should broadcast their witness signatures eventually due to the ban that results from a missing signature. Therefore, their decision about honest participation is whether they choose to delay their broadcast. Game theory says it is more rewarding for them to broadcast it immediately due to their stake in the network.
The network transaction history is immutable, assuming at most 90% of nodes are colluding to secretly break chain immutability at some later date. A 95% majority would control 100% of two committees in a row about once in a million years. A 99% majority would control 6 blocks in a row about once every 20 years. So, large reorganizations can only occur if nearly all the stakeholders collude to make it happen.
The network can tolerate up to 99.95% dishonest nodes, requiring every witness signature and 256 blocks for a block to achieve negligible probability of dropping from the main chain due to a chain reorganization.
During usual network operation the security properties of this protocol should cater for the relatively weak security requirements of everyday transactions and also strong security requirements of very large transactions.
If only 2/3rd of signatures are found in every block, the maximum threshold for dishonesty becomes much less, with 50% dishonest miners achieving the 2/3rd threshold in the committee about once every 33 years.
Signer enrollment and unenrollment should be in the block headers so that light clients can verify the chain headers without downloading every transaction. This enables some SPV, useful for light clients that can process pseudonymous transactions that have a known viewkey5, for example in an EFTPOS Terminal.
As a general improvement concept for blockchains to decrease space requirements, we mandates that nodes may only spend and mix with transactions no older than 7 years old. This means space requirements for the blockchain will increase linearly with usage and only the size of the headers will increase linearly with time. To remain active, funds must transferred at least once every 7 years. In June 2019, 20% of the Bitcoin UTXO set was older than 5 years6.
The voting mechanism described in this construction is only used for transaction history, observing missing witness signatures, and observing broken promises. However, it can make any network decision. For example, it could implement a rewards system for the operation of arbitrary services in a decentralized network7, or establish unique human membership to the group (for example, by humans authenticating identification documents offline).
The construction shows how BLS Signatures can reduce the nothing-at-stake effect in proof-of-stake blockchains.