This paper describes how non-interactive BLS signature aggregation1 can reduce the nothing-at-stake effect in proof-of-stake blockchains. It relies on the assumption that at least 1% of participants are well-behaved. It also describes a simple transaction receipt mechanism that enables faster 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. sign exactly once, and 3. aggregate the signatures produced by these keys instantly and across any distance.
We cannot replicate these properties exactly with proof-of-stake since parties may always sign multiple times (the "nothing-at-stake" problem). However, we can approximate them in the following ways. 1. Introduce an artificial cost. 2. Use a a regular multi-party signature with many signatories who have agreed to destroy their keys. 3. Use BLS signatures to allow aggregation of the result into a single 48 byte signature. Note that we also sacrifice the DMMS property that there is no enrollment process.
Traditional proof-of-stake systems are already an example of this approximation, drawn out over many blocks. In those systems, honest behaviour is considered to be 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. 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, instead destroying their keys as intended.
To register as a signatory, the operator must burn a certain amount of Bitcoin3, described below. The transaction must include the block signing key information.
A primary signatory is selected to sign each block, at random using a decentralized random number generator. The block is then sent out to a committee of 256 other block signatories, also chosen randomly, who each add their own signature to the block.
To provide entropy for the decentralized random number generator, and increase security, signatories 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 signatories are assumed to be honest. Assuming that the network has at most 92% dishonest signatories, 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 signatories who don't provide their signature after a certain amount of time. This incentivizes 100% of signatories 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. 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 (about twice a year). So, whilst the security guarantee for blockchain immutability is close to the cost of owning 90% of the signers, the security guarantee for blockchain reliable progress is much less, only the cost of owning 10% of the signers. However, this attack is not a double spend attack, only a denial of service attack.
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 signatory responsible for creating the upcoming block can broadcast a signed a promise to include a transaction. If the signatory 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:
There is no information that can prove that a witness signature was missing at the time it was required, so instead we take 2/3rd majority of committee signatures stating that the witness signature was missing from the committee 60 blocks later as justification for a ban. This technique can also be used to produce bans for arbitrary reasons.
A malicious actor with 1/6th of the network voting power will be able to produce arbitrary bans about once every six months. Therefore the number of bans each block is limited to 8 to minimize the abuse of this power. Since the production of bans is flexible, the rest of the network may choose to detect this behaviour, and ban the offending nodes.
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 voting power in the network colludes to make it happen, which would again reduce the value of their stake.
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.
To register, a signatory must send any amount of Bitcoin to a burn address, including the registration details in OP_RETURN outputs. If a block contains multiple burns, only the largest counts. The first appearing in the block is selected in the case of ties.
Bans for nodes that have produced a single block after one month of registration are automatically approved in the genesis version of Posmonero. This keeps the registration process tied to Bitcoin's proof-of-work until it is necessary to change it.
This technique was first inspired by the Truthcoin blog4:
I previously argued that:
A: Releasing 50 new Bitcoins per block.
…was equivalent to:
B: Auctioning off 50 Bitcoins to the highest bidder.
Consuming the supply of another cryptocurrency may allow for greater cross-pollination of ideas and code diversity within the network. In particular, it may provide an upgrade path for Bitcoin whilst maintaining the fixed supply by separating value from algorithm. This upgrade path will be decided by the holders of the token, instead of the decisions made by foundations, development teams, or mining pools.
The proposed mechanism does not permit arbitrary decisions about rate of inflation of the Posmonero supply, only the selection of those who are eligible to be signers (e.g. the difference between proof-of-work, proof-of-stake, proof-of-bitcoin-burn, ethereum-burn, etc). Bitcoin's loss-rate is already non-zero and hence the supply will already tend to zero given enough time. Since the Posmonero loss-rate can also be expected not to be zero, the fixed tail-emission will eventually equal the loss-rate and the supply can be said to be fixed.
Given there is a fixed supply of Bitcoin, this leaves bitcoin-based Posmonero registration with a limited timespan. Eventually, Posmonero could switch to a proof-of-posmonero-burn signatory registration process, giving Posmonero token holders an easy mechanism to decide which entities are eligible for new Posmonero emissions. Additionally, (or alternatively), nodes could eventually support registration using burn of alternative foreign cryptocurrencies, such as Peercoin5. This is not a fixed requirement of the protocol, which is deliberately left flexible.
This sets monetary policy into what Blockchains traditionally describe as a hard consensus rule, while allowing selection of signers as a separate tier of flexible consensus rules that can be decided at a later time when there is more information available. This addresses an important need for Blockchain projects, since many projects including Monero often hard-fork. Inspecting the Posmonero blockchain should tell you who was registered or banned, and when, but not why.
Signatory registration and unregistration should be in the block headers so that light clients can verify the chain headers without downloading every transaction. This enables SPV, useful for light clients that can process pseudonymous transactions that have a known viewkey6, for example in an EFTPOS Terminal.
As an experimental improvement for blockchains to decrease space requirements, Posmonero mandates that nodes may only spend and mix with transactions no older than 7 years. 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 be transferred at least once every 7 years.
The voting mechanism described in this construction is only used for transaction history, new signatory registrations, and signatory bans such as expiration, missing witness signatures, and broken promises. However, it can be used for other purposes. For example, it can implement a rewards system for the operation of arbitrary services as described in Loki Network7.
Receipts of promises can also be announced by the committee members to complete the faster confirmation mechanism.
Thank you to all the people upon whom this work depends.
The construction shows how BLS Signatures can reduce the nothing-at-stake effect in proof-of-stake blockchains, describes a simple voting mechanism that can be used for faster confirmations, and a flexible consensus mechanism that permits the reward of arbitrary behaviours.