Background

In Drivechains, miners are paid for the validity of sidechain blocks, but are supposed to guess the validity of sidechain withdrawals; this mechanism is supposed to ensure that miners do not have to run sidechain nodes, but the guessing game of sidechain withdrawal validity undermines its security, and miners are obligated to run sidechain nodes anyway, increasing the barrier-to-entry of new miners. See this bitcoin-dev message: miners have incentive to run sidechain nodes.

Another proposal (mine, Driveproof, or Sidechain Headers On Mainchain (SHOM)), unifies voting with merge mining, and then lets miners be paid for both validity of sidechain blocks and validity of sidechain withdrawals. This lets the set of sidechain "miners" be completely disjoint from the set of mainchain miners. It has the drawback that in the stable state, sidechain "miners" pay almost all of their sidecoin earnings to mainchain miners, the sidechain's total fees have to approach or exceed the rate limit imposed on side-to-main withdrawals (to prevent theft), and thus sidechain "miners" must use up all the limited side-to-main bandwidth to replenish their maincoin stock to be able to continue paying mainchain miners, vastly weakening the peg.

Hence, I present here proof-of-mainstake.

Introduction

Proof-of-mainstake is a sidechain proposal similar to a federated peg, with the federation membership determined by a stake of coins on the mainchain (i.e. the mainstake). As the name suggests, it is similar to proof-of-stake in that staked coins are used to indicate a controlling interest.

At a glance, the mechanism is:

A maincoin owner dedicates an amount of maincoin as stake to a particular sidechain (note that this is separate from the maincoin that is backing the sidecoin). This stake has a lock time: it cannot be spent "normally" until the lock time has passed.
At each new mainchain block, we run a stake lottery (as is usual for proof-of-stake). The seed of the RNG used for that lottery is the mainchain block header hash of the previous block. The tickets in the lottery are those UTXO's that were staked to the sidechain as of the latest block; the weight of the ticket is based on the value staked, and the remaining lock time.
The winning sidechain staker assembles a candidate sidechain block (with fees paid to himself or herself), signs it, and bribes miners to include the sidechain block header on the next mainchain block.
Miners may only include one sidechain block header from the winning sidechain staker of the previous mainchain block.
Mainchain fullnodes validate mainchain blocks by ensuring that an included sidechain block header is signed by the stake lottery winner (which it determines from the previous block hash in the mainchain header, and the UTXO set as of the previous mainchain block) and that a sidechain block header (if it exists) commits to some previous sidechain block header hash (as in sidechain headers on mainchain).
As in Driveproof/SHOM, side-to-main withdrawals are valid if the withdrawal transaction on the sidechain is on the longest chain of the sidechain, the longest chain dominates in length over all the other chains of the sidechain, and the withdrawal is deep enough. The length of a chain is a vote for the validity of a withdrawal on that chain.

This must be strongly emphasized: The mainchain coins in a mainstake are a separate set of coins from the coins locked into the sidechain. Coins locked to the sidechain are in the sidechain, but coins mainstaked to protect the sidechain remain in the mainchain.

Nothing-at-stake and Stake-grinding

Proof-of-stake is unsafe as a consensus algorithm due to the nothing-at-stake and stake-grinding problems.

Nothing-at-stake is the problem where a stake winner can sign multiple different versions of the block they won, showing different blocks to different peers. A long-range nothing-at-stake is the problem where a stake winner wins a block, spends all the staked coins, then reverses history by signing a different version of the previously-won block and regaining their coins.
Stake-grinding is the problem where the stake winner generates several candidate blocks it can sign. The stake winner does not publish blocks until it gets a block that would cause the stake lottery to go to the stake winner again.

Combining nothing-at-stake and stake-grinding lets a stake owner who wins once create a true chain and a cheating chain. The stake owner publishes the true chain and spends money for off-chain value on the true chain. In the meantime, it continuously grinds stake on an alternate, cheating chain, keeping itself the winner of the lottery on the cheating chain. When it receives the off-chain value, it publishes the cheating chain if it is longer, reversing the spend of its money.

Here is how proof-of-mainstake avoids these classic problems:

A stake winner may sign multiple sidechain blocks, but only one of those will be committed to on the mainchain. In order to perform a long-range nothing-at-stake attack, the sidechain operator needs to have significant mainchain hashpower to reverse the mainchain and build a longer chain.
In order to perform a stake-grinding attack, the stake winner needs to target two desiderata: grind the stake so that it will win again, and grind the proof-of-work on the mainchain. It also cannot grind the stake indefinitely, as other mainchain miners are also grinding with their only target being simply proof-of-work.

In effect, nothing-at-stake is avoided by publishing checkpoints on the mainchain, and using mainchain consensus to commit to the checkpoints. Stake-grinding is avoided by reusing the mainblock header hash as the lottery seed for the next mainblock; any stake-grinding attempt needs to also target the current difficulty on the mainchain, increasing the effective difficulty a stake-grinder needs to target.

In many ways, proof-of-mainstake is not the same as proof-of-stake.

Building Sidechain Headers

SPV proof publication and merge mining is done via the same mechanism; the stake lottery winner publishes a sidechain block header, paying miners to include the sidechain block header on the mainchain. Hence, mainstake is also a sidechain-headers-on-mainchain system.

Sidechain block headers are reduced down to two core fields:

hashMerkleRoot, 32 bytes that commit to the sideblock's transactions and any extra data the sidechain needs to operate.
hashPrevBlock, 32 bytes that are the hash of the previous sidechain block header.

For each sidechain ID, for each mainchain block, at most one sidechain block header may be published. In addition, the sidechain block header published on the mainchain blocks may only be published by the stake lottery winner from the end of the previous block.

Sidechain block headers are generally expected to continue the sidechain's topmost tip, but they may, at the stake winner's discretion, continue an earlier sidechain block header. This means that the stake winner was either unable to verify the tipmost sidechain block header, or that sidechain block header had invalid transactions.

The mainchain itself is unable to directly confirm that the committed sidechain headers commit to valid blocks; it uses the merge mining process itself as an SPV proof. Since the headers are visible on the mainchain, any mainchain node can judge the validity of any side-to-main withdrawal at SPV security.

Side-to-main Withdrawal

Side-to-main withdrawals are done by publishing a withdrawal transaction on the sidechain, and having some sidechain block header commit to the withdrawal transaction. On the mainchain itself, spends will be done via a variant of OP_WITHDRAWPROOFVERIFY. Spends of the sidechain's lockbox require proof-of-existence that the sidechain-side withdrawal transaction exists, and also that the sidechain-side withdrawal transaction:

is on the longest chain of the sidechain
is at least N sidechain blocks deep
is on all other chains of the sidechain that are at most N sidechain blocks behind the longest chain (i.e. it must exist on every competing chain of the sidechain that is 0 to N sidechain blocks behind the longest chain in height).

Since the sidechain header is published on mainchain, a mainchain fullnode can determine the length of each of the sidechain's split chains, and uses the length as a proxy for validity, on the assumption that rational sidechain mainstakers would rather cooperatively build the sidechain rather than steal the sidechain's backing maincoin.

Obviously the format of the sidechain withdrawal transaction should be something that the mainchain nodes can understand. However, for normal, intra-sidechain transactions, the sidechain may adopt an incompatible transaction format. This can be done by putting the withdrawal transaction in a special branch of the transaction Merkle tree of the sidechain, and putting the actual sidechain transaction Merkle tree in the other branch of that node.

Lockboxes of a sidechain may be created and spent, but may normally only be spent to other lockboxes of the same sidechain. To pay from a sidechain lockbox to some mainchain P2SH addess, then a proof that a side-to-main withdrawal exists on the sidechain at some sidechain block header must be provided. In addition, the mainchain must confirm that this withdrawal has not been used before; the easiest way to implement this is to simply allow one withdrawal per sidechain block and to keep track of sidechain block headers already used in mainchain-side withdrawals in a constantly-growing set. Imposing limits — such as requiring that withdrawals on the mainchain side can only refer to sidechain block headers at most 12,960 mainchain blocks (about 3 months) ago — can be used to allow pruning of this set, at the cost that in case of extremely persistent sidechain chainsplits, withdrawals may become lost (sidechains could keep track of whether withdrawals are unclaimed on mainchain and let the withdrawals be re-spent in the sidechain if this is problematic).

Mainstaking

Let us sketch out the details of mainstake a little. We add a new opcode, OP_STAKEVERIFY, from an existing OP_NOP. Then we allow the scriptPubKey below in the IsStandard check:

 OP_DUP OP_HASH160 <pubkeyhash> OP_EQUALVERIFY OP_CHECKSIGVERIFY
 <stakeLockTime> <sidechainId> OP_STAKEVERIFY

Where sidechainId is a non-zero identifier for a sidechain, and pubkeyhash is the hash of a public key that the staker controls.

The stake may be spent in one of two ways. Given the scriptSig below, the stake is spent, i.e. it is removed from being staked to the given sidechain. This scriptSig below is only valid if the nLockTime of the transaction equals th stakeLockTime.

 0 <signature> <pubkey>

The other way is used to publish a sidechain block header specifically for the particular sidechain it is staked for:

 1 <signature> <pubkey>

In the latter case, the transaction spending the stake UTXO has additional restrictions:

It is valid only if the UTXO is the stake winner from the previous block header hash.
It must have exactly one input (the scriptSig 1 <signature> <pubkey>) and exactly one or two outputs.
The transaction's 0-indexed output must be an OP_RETURN output that contains a sidechain block header. The sidechain block header's hashPrevBlock must be either 0, or the hash of a sidechain block header of that sidechain that was already published before.
The transaction's 1-indexed output, if it exists, must be another OP_STAKEVERIFY with exactly the same sidechainId and stakeLockTime.

Since publication of a sidechain block header requires a spend of the stake, this ensures that a mainstaker can only publish a single sidechain block header if it wins the stake lottery.

The transaction needs to pay to mainchain miners in order to be mined; thus mainchain miners are bribed to include the sidechain block header by being offered fees in the transaction. As the only input is the stake itself, the mainchain fees come from the stake.

Lottery Weight

The weight of a mainstaked UTXO in the total stake of a particular sidechain ID is the product of the UTXO value in satoshis, and the remaining time, in mainchan blocks, before the mainstake's locktime.

Basically, the larger the stake value, the more likely to be selected. Also, the longer the stake is committed to the sidechain, the more likely to be selected.

This system means that mainstaker's weight in the lottery (its likelihood of winning the stake lottery) decreases linearly over time, falling to zero at and after the locktime. This reflects the reality that the longer the stake is locked, the greater the incentive for a mainstaker to protect the value of the maincoin by supporting the sidechain and not stealing from the sidechain.

Operating the Lottery

In effect, the sidechain advances "between" mainchain blocks.

Every sidechain fullnode must be a mainchain fullnode. Sidechain mainstakers must also run a sidechain fullnode and also a mainchain fullnode.

After processing a mainchain block, we have the block header hash of the tip, and the UTXO set as of the end of that mainchain block.

From the UTXO set, we extract the UTXOs that happen to be mainstakes. These are the tickets in the lottery. The weight of the ticket is based on the value of the UTXO, times the remaining time until the stake is unlocked (as described in the previous sub-section).

The lottery is then seeded using the block header hash of the tip. If you are the stake winner, you quickly create a sidechain block (paying its fees to yourself) and its header, then sign the sidechain block header and publish it as quickly as possible to all miners, before another mainchain miner gets the next mainchain block.

When the next mainchain block arrives, if it contains your sidechain block header, congratulations, you have advanced the sidechain state and can now publish your sidechain block to other sidechain fullnodes. If it does not contain your sidechain block header, this is sad as you have now "lost your winning ticket" by not responding fast enough.

(If you deliberately do not do anything, then the next mainchain block will not have a sidechain block header, but it is likely to now select a different stake winner unless you control the entire stake of the sidechain.)

Regardless of whether you were able to publish a sidechain block header or not on the mainchain, when the next mainchain block arrives, again the UTXO set is extracted to get the mainstake tickets, then the lottery is run based on the block header hash of the new tip. Thus, all mainchain fullnodes have enough information to verify the correct operation of the sidechain mainstake lottery.

Security

Sidechain security is based on the assumption that no single large maincoin owner can exist that dominates over other maincoin owners.

We can compare mainstaked sidechains to the mined mainchain:

A miner of the mainchain is similar to a mainstaker of the sidechain.
A mainchain miner invests some resources outside of the mainchain to purchase or create mining hardware to build the mainchain. A sidechain mainstaker invests some resources outside of the sidechain (maincoin) to build the sidechain.
A mainchain miner spends electricity, effectively turning it into maincoin. A sidechain mainstaker spends the opportunity cost of the hodling (it could have been invested in JoinMarket or Lightning Network payment node, for example), effectively turning the opportunity cost into sidecoin fees.
In general, the larger the mainchain miner's investment in hashpower, the more likely to mine a block and the greater the reward. In general, the larger the sidechain mainstaker's investment in stake, the more likely to win the stake lottery and the greater the reward.

Similarly, for a given sidechain, if a mainstaker has >50% of the stake, then it would be possible for the mainstaker to attack the sidechain. However, for the sidechain, the consequences of a successful 51% attack is greater: the loss of the entire maincoin backing the sidecoin.

The difference is that we expect a successful 51% attack to be much more difficult for a sidechain mainstaker to pull off. We point out that while today a very small fraction of Bitcoin users currently operate mining hardware, by definition a Bitcoin user must at some point "own" some bitcoins. This is the basis for our consideration that, with mainstaking, it is less likely that a large amount of maincoin will be controlled by a small number of mainstakers, compared to the likelihood that a large amount of mining hashpower will be operated by a small number of miners.

Level-crossing Attacks

But we should note that while sidechain mainstaking is a virtual mainchain mining, the virtualization itself is dependent on the mainchain operation. We should also consider what mainchain miners can do to attack or otherwise damage the sidechains dependent upon the mainchain, regardless of what reasons we may imagine they have to attack or not attack.

Mainchain miners can't usefully affect who is selected as stake winners or unstake existing mainstakers. However, they can filter out winning mainstakers from publishing sidechain headers. This will work as well as any miner transaction blacklisting policy: if the blacklisting miner has <50% of the mining hashpower, then it is likely some other miner will accept and publish it anyway, with the blacklisting miner unable to impose its will without risk loss of earnings.

It is useful to compare the situation where less than 50% of miners want to somehow attack sidechains, for any reason, under drivechains. Under drivechains, a 26% cartel can block all withdrawals indefinitely (if the proposed parameter X=504, but reducing X will then let a <50% cartel to steal sidechain funds), whereas under mainstake, a 26% cartel can only slow down sidechain operation, with withdrawals still able to get through.

On the other hand, if the attacking miner controls >50% mining hashpower, the attacking miner can impose the policy that any sidechain block header it does not publish itself cannot be published. This allows the attacking miner to steal the entire sidechain coins: it will publish an invalid withdrawal, then push a longer chain sufficient to validate the withdrawal. But we offer a weak mitigation: if the sidechain has sufficient mainstake that is not controlled by the miner, then the miner has low probability of being able to extend its desired invalid chain no matter its hashpower, while still able to stifle extension of the valid chain. This will slow down the miner's attack, hopefully enough that other miners can rescue the ecosystem, or a proof-of-work change can be deployed.

Examining this further, we note that an attacking >50% miner, who has blocked all legitimate sidechain activity and the creation of legitimate mainstakes, can choose a strategy along this spectrum:

It can wait out the mainstake locktimes of legitimate mainstackers, and steal all sidecoins with a 1-satoshi stake locked for a short time (enough to create a long enough SPV proof).
It can lock a large number of its own funds in order to get mainstaking control over the sidechain, and slowly create the necessary SPV proof.

In the first case, the attacking >50% miner will be broadcasting its future intent to steal sidechain funds. Hopefully the existing locktimes will be long enough that the maincoin will have been crashed or other mitigations, such as PoW change, will have been deployed. In the second case, the attacking >50% miner will need to lock up a sizable amount of funds for a sizable length of time; when the theft is committed, it is possible that the fund locktime is still in the future, by which time the price of the coin may have crashed, or other mitigations, such as a softfork to blacklist the fund, may have been deployed.

Centralization Risk

Drivechain has significant incentive for a sidechain protector and a mainchain miner to coalesce, increasing centralization risk.

A mainchain miner needs to know the validity of every withdrawal transaction in order to determine the correct way to vote.
A sidechain protector wants to be reassured that it will be able to withdraw from the sidechain, and will want to have a special relationship with mainchain miners to give them accurate information on how to vote for the sidechain withdrawals.

Drivechain's "blind" merge mining does not help, as it only provides the hash to publish, and not voting information.

Further, while drivechain assumes that miners will always upvote each withdrawal, and only downvote if an invalid withdrawal "slips through", this behavior can be attacked by spamming invalid withdrawals continuously. The only mitigation offered is for miners to "temporarily" upgrade to sidechain fullnodes; but one wonders if there is sufficient incentive to downgrade. This essentially seems to admit of only one true solution: merge sidechain protectors and mainchain miners (in which case "blind" merge mining is pointless), then softfork the sidechain into an extension block (in which case sidechains are pointless).

Mainstaking, on the other hand, limits miner control over sidechains. A sidechain mainstaker wants to be able to publish its transaction to all miners immediately before the next block is found (since its sidechain header is valid only on the block after it wins the stake lottery), but assuming that "fast" mainchain blocks are rare, the normal flooding process will be fast enough for this.

The expected default behavior of mainstaking is that miners will, as usual, get as many high-value valid transactions into blocks, without attempting to censor or block certain transactions. In this case, mainstakers can operate the sidechain continuously without requiring special relationships with mainchain miners, unlike drivechain, which requires that a sidechain protector have special trusted channels to transmit voting information to mainchain miners.

Stake Locktime limit

For various reasons, it may be best to consider disallowing stake locktimes too far into the future. For example, the stake locktime may not be further than about a year from the time it is first staked. Mainstakers must renew their stakes by doing a "normal" spend using 0 <signature> <pubkey> and spending it again on a new stake scriptPubKey.

In case the private keys of a mainstake are lost or destroyed (for example, physical destruction of the hardware executing the sidechain mainstaker code), if that particular mainstake wins the stake lottery, then the sidechain cannot advance for that mainchain block. However, after enough time has passed, the mainstake is removed from the stake lottery and will no longer encumber the sidechain.
Relatedly, an attack where a small amount of coin is staked to a very far future date (1000 years from now, for example), in order to overpower more moderate stakes to steal the entire sidechain funds, is limited by this policy.
It allows the sidechain to be upgraded from a mainstaked sidechain to a miner-controlled, mainchain fullnode-verified extension block (see next section).

Against those, however, we must caution the below:

Our weak mitigation against a mainchain miner >50% attack is weakened further; now the mainchain miner with 51% hashpower need only block the creation of sidechain mainstake UTXOs except its own, and eventually the other mainstake UTXOs will time out and the miner can outright steal costlessly. The miner can even just wait out the timeout period and steal all sidechain coins as soon as all the timeouts end. Hopefully such dire straits will allow a PoW change to be deployed before the timeouts of all sidechain mainstakes end.

Upgrading Mainstaked Sidechains to Miner-Controlled Extension Blocks

One of the reasons for implementing a sidechain is to prototype improvements to Bitcoin before being implemented on the mainchain. (One may consider as an example, the Elements Alpha sidechain, where OP_CHECKSEQUENCEVERIFY and SegWit were prototyped)

If a sidechain transaction and block format is "near enough" to the mainchain, then it may be possible to simply softfork the sidechain rules onto mainchain if there is significant evidence that the prototype on the sidechain is beneficial. Then the sidechain users can simply move their sidecoins back to maincoin, and mainstakers let their stakes lapse and transfer them elswhere, and the sidechain itself can simply be defunct, as its rules are now in the mainchain (or the sidechain can explore even further with even newer features to prototype). However, there may be sidechains — MimbleWimble, for instance — whose transaction format or block format is very different, or which have significant changes in transaction validation, and which cannot be usefully applied to the mainchain, or would require a hardfork. For such sidechains to be "upgraded" to mainchain status, they need to be extension blocks.

As mainstakes will eventually lose their weight at the end of the stake locktime, the below upgrade path from mainstaked sidechain to extension block can be used. Note that below is a softfork.

The developer selects a public-private keypair and publishes both private and public keys in the code. This will be the miner-controlled keypair.
At ACTIVATE, mainchain fullnodes will now verify the sidechain blocks and reject invalid sidechain blocks — the sidechain is now an extension block. Legacy nodes will be unaware of the sidechain blocks.
After ACTIVATE, the developer creates a single UTXO with 1 satoshi, staked to the sidechain (now an extension block) with the published public key. This is the current miner-controlled stake. Spends of this stake is only allowed if it is publishing a sidechain block header, or if it will spend itself entirely on a new miner-controlled stake (i.e. when it times out).
After ACTIVATE, new mainstaking UTXOs are disallowed, other than the miner-controlled stake.
After ACTIVATE, existing mainstake UTXOs will still participate in the lottery, for back compatibility with legacy nodes. However, when the mainstake UTXO times out, it cannot be re-staked again to the same sidechain.
When all other mainstake UTXOs have timed out, only the miner-controlled stake will be selected in the stake lottery, even at 1 satoshi. The sidechain is now completely a miner-controlled extension block.

A Vision For Future Bitcoin Upgrades

The example of Elements Alpha suggests a new way of proposing upgrades to Bitcoin.

Design and develop the upgrade as a sidechain.
Deploy the sidechain and fight off attackers successfully.
Show the world that the improvements on the sidechain are beneficial, and that people are using the sidechain significantly.
Convince the other developers of Bitcoin to upgrade the sidechain to mainchain status, citing the evidence gathered from being a sidechain.
If it can be done as a softfork on the mainchain, then re-deploy as a softfork on the mainchain. If not, and it is acceptable as an extension block, then upgrade the sidechain to an extension block, as above.