Decentralized sidechain with Proof of Work inside DER signatures

[stwenhao]

Recently, I shared a puzzle, based on Proof of Work inside Script. It is described in details here: https://bitcointalk.org/index.php?topic=5551080.0

In the shared puzzle, the private key, used to grind solutions, is equal to one. It is done on purpose, to make it easy to recreate by anyone, anywhere. However, Proof of Work can be used in many different places. It can be used to build sidechains, which would be directly pegged into Bitcoin. Then, from the perspective of on-chain node, sidechain transactions will be simplified into one-input-one-output chunks, with attached peg-ins and peg-outs. Any sidechain miner can take any fees out of sidechain users, and pay the rest to the mainchain miners. I think it is a good idea to show some example:

Code:

+-------------------------------------------------+
| Puzzle  0.00050000 BTC -> Miner  0.00053000 BTC |
| Alice   0.01000000 BTC    Bob    0.00999000 BTC |
| Charlie 0.02000000 BTC    Daniel 0.01999000 BTC |
| Elaine  0.03000000 BTC    Frank  0.02999000 BTC |
+-------------------------------------------------+

Here, some unsolved puzzle, with some difficulty, is used as a transaction input. Any sidechain miner can start grinding it, by using SIGHASH_ANYONECANPAY to make sure, that anyone can put more coins in, or bump on-chain fees if needed.

Then, people joining the sidechain will provide their inputs, and people leaving the sidechain will share their outputs. In the example above, the on-chain transaction has zero fee, but it can be higher, if output amounts will be lowered (however, if sidechain miner is also a mainchain miner, then it can decide to prioritize sidechain transactions inside produced Bitcoin blocks). When it comes to sighashes, puzzle solver can use SIGHASH_ANYONECANPAY with SIGHASH_ALL, and other people, who want to join the sidechain, can use SIGHASH_NONE, to sign all inputs, and make sure, that they will be included, only if the Proof of Work puzzle will be solved. Also, they can put any commitment as their r-values inside their signatures, so it could be possible to validate later, if sidechain rules are followed correctly, and if nobody tried to steal any coins.

In this example, we can see the finalization transaction, which is executed every sometimes, depending on picked Proof of Work, which decides, how often new sidechain transactions are broadcasted. It can be done every three months or so, to make it aligned with other sidechain proposals, like BIP-300 or BIP-301, but it depends mainly on users, how much fees they are willing to pay, and how long they want to wait, to get benefits from batching, and pay lower fees, because of that.

In general, the minimal working example, is when every user stays inside sidechain. Then, the whole on-chain representation can be simplified into just this:

Code:

+---------------------------------------------------------------------------+
| SponsorA 0.00010000 BTC -> Puzzle 0.00050000 BTC -> Puzzle 0.00050000 BTC |
| SponsorB 0.00015000 BTC                                                   |
| SponsorC 0.00025000 BTC                                                   |
+---------------------------------------------------------------------------+

In this case, a group of sponsors can start putting their coins in, to transfer them from mainchain to sidechain. The puzzle can be very similar to the original, but committed difficulty and public key can be rotated on-the-fly, depending on things happening inside sidechain mempools. Sidechain users can keep making transactions between themselves, and sponsors can collect this information, and use a merkle root of the next network state, as the private key for grinded signatures (instead of using private key equal to one, like it is in my puzzle). Then, when some sidechain miner will find the solution, it can share a signature, signed with SIGHASH_ANYONECANPAY, and use any coins, to set any fees (or process it for free, if it can also mine mainnet blocks).

Then, during Initial Blockchain Download, Bitcoin nodes don't have to know about sidechain existence at all. From their perspective, there are just some signatures, which are just smaller than usual (which is visible in the Script). However, they don't have to verify the correctness of the sidechain merkle tree, it is treated just like a chunk of bytes, which is only checked from the perspective of ECDSA correctness, and no commitment behind it is ever processed by existing nodes.

For each sidechain, a single UTXO is all we need, to keep it running. All inputs and outputs are needed mainly for peg-ins and peg-outs, when people will want to go between sidechain and mainchain, or even jump directly from one sidechain puzzle to another. Nodes can keep signing different versions of on-chain transactions, similar to how Lightning nodes sign them. The final version is broadcasted to the mainchain nodes, when some sidechain miner can find a solution, claim the reward, push the sidechain difficulty a little higher, and commit the state of the whole sidechain, and make it committed on-chain. As long as everyone is staying inside, it is all about changing one 256-bit number to another, so on-chain transaction size is mainly affected by peg-ins and peg-outs, the internal state of the sidechain is transparent to all mainchain nodes, and can execute any rules inside, as creators would pick.

I think producing a new sidechain header could be compared to consuming a single transaction input and producing a single output in that case (everything else is related to peg-ins and peg-outs; if there are none, then one-input-one-output is all that is needed). Mainchain users can then see each sidechain block header, and check Proof of Work behind it, but everything else can stay inside sidechain. I guess it would scale better than Lightning Network, because then, transactions inside sidechain wouldn't require constantly closing and opening new channels, and could be simplified to just replacing one 256-bit number with another 256-bit number, used for the next puzzle.

Edit: Sidechains can be improved with Optional Hourglass. Then, the private key can just represent the state of the whole sidechain (for example its UTXO merkle tree, or something similar), and sidechain miners can try to create stronger and stronger signatures, which could be confirmed at earlier, and earlier block height. Here is an example of a sidechain using Optional Hourglass envelope, and committing to the "Hello World" content:

Code:

SHA-256("Hello World")=d=a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Q=d*G=0298C39AC0D91FF4CEA6E79AE5836E50868C47191BCA0FBFD2A6838D303665F506

And now, we can require at least 13150 ACKs, while also enforcing Optional Hourglass envelope:

Code:

decodescript 210298c39ac0d91ff4cea6e79ae5836e50868c47191bca0fbfd2a6838d303665f506ac
{
  "asm": "0298c39ac0d91ff4cea6e79ae5836e50868c47191bca0fbfd2a6838d303665f506 OP_CHECKSIG",
  "desc": "pk(0298c39ac0d91ff4cea6e79ae5836e50868c47191bca0fbfd2a6838d303665f506)#ryjv7lc4",
  "type": "pubkey",
  "p2sh": "2NEhtT2UPFkvRgMCQ4azmNMEGtVQfmy33vL",
  "segwit": {
    "asm": "0 d35986305ce10537dc781e795e734673035c4160",
    "desc": "addr(tb1q6dvcvvzuuyzn0hrcreu4uu6xwvp4cstqk89zqn)#lgthsn5s",
    "hex": "0014d35986305ce10537dc781e795e734673035c4160",
    "address": "tb1q6dvcvvzuuyzn0hrcreu4uu6xwvp4cstqk89zqn",
    "type": "witness_v0_keyhash",
    "p2sh-segwit": "2N4ZPqUwLBg1FiBuUKyiVckfH63n71KamNG"
  }
}
decodescript 7c8276937693025e3393b2757cab76a914d35986305ce10537dc781e795e734673035c416088ac
{
  "asm": "OP_SWAP OP_SIZE OP_DUP OP_ADD OP_DUP OP_ADD 13150 OP_ADD OP_CHECKSEQUENCEVERIFY OP_DROP OP_SWAP OP_CODESEPARATOR OP_DUP OP_HASH160 d35986305ce10537dc781e795e734673035c4160 OP_EQUALVERIFY OP_CHECKSIG",
  "desc": "raw(7c8276937693025e3393b2757cab76a914d35986305ce10537dc781e795e734673035c416088ac)#mrd0n6f8",
  "type": "nonstandard",
  "p2sh": "2Muhrn2Y5PgHQZRzL9fevf7j34s8aaXwmbg",
  "segwit": {
    "asm": "0 419e580de6345f1ebb6253682f62716098d3ad1bda5b631a752f2484c2342913",
    "desc": "addr(tb1qgx09sr0xx303awmz2d5z7cn3vzvd8tgmmfdkxxn49ujgfs359yfs8fyrcn)#yqw84xvm",
    "hex": "0020419e580de6345f1ebb6253682f62716098d3ad1bda5b631a752f2484c2342913",
    "address": "tb1qgx09sr0xx303awmz2d5z7cn3vzvd8tgmmfdkxxn49ujgfs359yfs8fyrcn",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "2N1tpGp3eEKZgjxXesbk2RFebaLwqY6QWAF"
  }
}

And then, people can try to mine addresses like tb1qgx09sr0xx303awmz2d5z7cn3vzvd8tgmmfdkxxn49ujgfs359yfs8fyrcn constantly, while sharing their ACKs between themselves. The final winner is the miner, who will produce the smallest signature during three months.

[d5000]

I wanted to react to this thread for a long time, but I have difficulties understanding the post. So I hoped for some other knowledgeable people to get a discussion going but that never happened ...

Okay, then I'll go step by step, starting with a very simple question:

What is the exact purpose of the puzzle to secure the sidechain? It looks to me like it the "puzzle transaction" is located on-chain (on the Bitcoin chain, not the sidechain), and that it is created to order the peg-in and peg-out transactions, to prevent double spends. It looks like a simple form of merged mining.

But in BIP300/301 (hashrate escrow) the miners mine the peg-ins and peg-outs validating the sidechain rules, but without an additional puzzle as far as I know (only the "puzzle" to find the block).

My uneducated guess is that the puzzle is to ensure that a sidechain miner validates the sidechain rules, without a mainchain miner having to interfere. The mainchain miner thus only checks if the peg-ins and peg-outs are correct, but not "where they go/where they come from on the sidechain". But what if a miner validates the sidechain state incorrectly? How does the puzzle help to prevent that?

[stwenhao]

What is the exact purpose of the puzzle to secure the sidechain?

If you can apply Proof of Work inside Script, then Proof of Work is enforced by the mainchain, and on top of that, sidechain can enforce any rules.

In theory, miners can steal all sidechain funds, by making a transaction, which will be valid for Bitcoin, but invalid for sidechain. However, in practice, BIP-300 and BIP-301 has similar assumptions (that some sidechains can be killed in this way), and also, all Script conditions have to be fulfilled. Which means, that if a given sidechain will use for example Proof of Work and locktime, then you also meet that locktime. The same with multisigs, and everything else, which can be added to the Proof of Work alone. But of course, the simplest use case, is to use just Proof of Work, and solve all conflicts in that way.

It looks to me like it the "puzzle transaction" is located on-chain (on the Bitcoin chain, not the sidechain), and that it is created to order the peg-in and peg-out transactions, to prevent double spends.

Exactly. The main chain has to understand some basic things, which means, that Proof of Work is enforced on-chain. But everything else is only enforced by sidechain rules, if it is not expressed in the Bitcoin Script (some things like locktime and multisig can be expressed, but many other things are left to the sidechain).

It looks like a simple form of merged mining.

As long as mined transactions are strictly separated from mined block headers, there is no Merged Mining. However, it could be added, for example if Bitcoin will start counting Proof of Work inside transactions, or if opcodes like OP_CAT would be activated. But for now, by mining sidechains, you don't make Bitcoin stronger directly (however, double-spending a sidechain transaction, and stealing funds, require re-mining that transaction, so it is hard, if enough Proof of Work is spent to make the first transaction; moving coins somewhere else is not trivial, even if the private key for grinding is known, which my puzzle also shows, because nobody solved all of that yet, which means, that OP_CHECKSIG is still strong).

but without an additional puzzle as far as I know (only the "puzzle" to find the block).

The "puzzle" in BIP-300 or BIP-301 is expressed as 13150 "votes", broadcasted by miners. Here, a similar thing can be achieved, by locking things on Proof of Work, which could be completed for example in around three months, and sending "shares" in some P2P network, to report the status of "voting". Or: a huge multisig can be done, but it is costly, and a simple "13150 OP_CHECKSEQUENCEVERIFY" is much better, if someone needs something like that.

But what if a miner validates the sidechain state incorrectly?

Then, funds can be sent anywhere, just like in BIP-300 and BIP-301.

How does the puzzle help to prevent that?

To move funds anywhere else, you have to overwrite the whole Proof of Work, which is done by all sidechain miners. Which means, that you have to be stronger, than the whole sidechain network. And that is hard to achieve, because if that would be the case, then no altcoins using double SHA-256 could work in practice.

Also, you have to do that in 10 minutes. Sidechain miners can prepare something for three months, and then broadcast it. And beating in 10 minutes something, than they did in three months, is possible, but unlikely.

Another thing is the mining key doesn't have to be public. People can use homomorphic encryption, and then, they are vulnerable only to short exposure attacks.

So I hoped for some other knowledgeable people to get a discussion going but that never happened ...

It probably won't happen, because many people think, that sidechains are stupid, or they are against them. So, don't expect serious discussions, until something will be really deployed. Only then people will pay attention. And if coins will be protected by Proof of Work, then they will move less times than usual, so it also has some anti-spam features, if sidechains will be widely used. Maybe this will be the only way to have some spam resistance, if the main chain will be flooded with every use case, that people would want to deploy.

[flapduck]

You've got per-tx merged mining: grind a sig so its hash meets a target; commit the sidechain header in that signed message. Miners include the tx for fees; the sidechain uses the "work in the sig" for fork choice.

Key things to nail:
What the sig commits to: bind {sc_header, sc_prev, mainchain height, outputs} with strict SIGHASH_ALL; do fee-bumps via CPFP/RBF.
Use Schnorr/Taproot, not ECDSA DER, safer grinding, fixed encoding, fewer edge cases. Fork choice math, define target and cumulative score unambiguously; publish a reference is_work_valid.
Liveness/censorship: make fee bumping trivial; include mainchain height to avoid replay across reorgs.

Work proves effort, not correctness, consider fraud-proofs/delayed finality to deter invalid headers.

[stwenhao]

strict SIGHASH_ALL

It is risky to mine puzzles with SIGHASH_ALL, because then, you can never modify it later. Which means, that if you find a valid solution, and any of your inputs will be moved earlier by any participant, then you are left with invalid signature, even if it has required Proof of Work. I think miners should use at least SIGHASH_ANYONECANPAY, just to make sure, that on-chain fees can be bumped with any coins, without re-mining the solution.

do fee-bumps via CPFP/RBF

Using CPFP is hard, when you have to wait three months, and solve the next puzzle, to use it. Of course, other people doing peg-outs can potentially do CPFP, even unintentionally, but it is just a side-effect of being in the same transaction, and they may prefer to wait, instead of immediately moving their coins anywhere else.

Use Schnorr/Taproot

OP_SIZE does not work there.

Work proves effort, not correctness

Exactly like in the mainchain. You can have "Alice -> Bob" transaction, included by one miner, and "Alice -> Charlie" transaction, included by another miner, in another block. Then, only Proof of Work can decide, which one is valid.

consider fraud-proofs/delayed finality to deter invalid headers

It is delayed. Things like "<time> 13150 OP_ADD OP_CHECKSEQUENCEVERIFY" simply means, that each sidechain coin can be moved after 13150 blocks (around three months). Also note, that Lightning Network can be connected with such sidechains, and then, it is just about forming the closing channel transaction. Even in LN, funds can be stolen, if you successfully confirm some old channel state. Here, assumptions are not weaker, but stronger, because you can have exactly the same things like you already have in LN, and add Proof of Work just on top of that.

Also, when it comes to fraud proofs, there is a limit of what mainchain can do. Because, similarly to LN, the mainchain should not know, what is inside LN, and the same is true here. It is up to users, to set up penalty transactions, to invalidate all old transactions, if they will ever be broadcasted. The mainchain can only accept a given transaction, and make sure, that it will be confirmed, and that it won't be easily altered in 10 minutes, if the whole network spent three months on grinding it.

[flapduck]

It is risky to mine puzzles with SIGHASH_ALL… I think miners should use at least SIGHASH_ANYONECANPAY, just to make sure that on-chain fees can be bumped with any coins, without re-mining the solution.

Totally hear you on fee flexibility. One way to get both properties is to split responsibilities:

Anchor input (strict) - one signature with SIGHASH_ALL that binds the sidechain header commit, prev pointer, and the exact payout template.

Fee input (flexible) - a second signature (your "puzzle/work" sig) using ANYONECANPAY so anyone can RBF in extra inputs right before broadcast.

This keeps the "work" valid while letting fee-payers add coin at the last minute without you re-grinding. It also prevents a relayer from reshaping the payout you intended.

Using CPFP is hard, when you have to wait three months, and solve the next puzzle, to use it.

Agree CPFP isn't the right tool for a CSV-locked input across months. With the split above, you don't CPFP the locked input. You simply wait until near maturity, assemble a fresh replacement with extra fee inputs (thanks to ANYONECANPAY on the fee side), and RBF it in. Mempools won't keep a txn for months anyway, so "fee planning" happens at broadcast time.

OP_SIZE does not work there.

For the PoW check: we don't need to enforce it in script at all (tapscript doesn't give us clean 256-bit comparisons). Let the script only enforce spendability (key path + CSV/CLTV). Sidechain nodes verify the "work in the signature" off-chain for fork choice. If you do want to grind safely, Schnorr/keypath is still preferable to ECDSA: you can vary the nonce point safely and avoid RNG/nonce-bias pitfalls that grinding ECDSA tends to invite.

Exactly like in the mainchain… "Alice->Bob" vs "Alice->Charlie"… Then, only Proof of Work can decide, which one is valid.

Right, fork choice by cumulative work. To reduce the "grind on invalid body" risk, I'd at least bind a body Merkle root (and maybe body length) into the message you sign and publish a compact "invalidity witness" format off-chain. Nodes that see a body-level contradiction can deterministically orphan descendants of that header; no L1 involvement, but you still deter obviously invalid histories.

Things like "<time> 13150 OP_ADD OP_CHECKSEQUENCEVERIFY" … each sidechain coin can be moved after ~3 months.

Makes sense for delayed finality. In the split-input layout above, put the CSV on the anchor input so no one can front-run settle-outs, while fee inputs remain free to change via RBF right before maturity.

[d5000]

- snip -

Thanks for your explanations! The concept is now a bit clearer for me. Also thanks to @flapduck for chiming in!

I guess my main problem was that in BIP 300/301 the security is achieved by the fact that 1) the peg-in/out validators are also mainchain miners (high barrier of entry) and 2) several months of "votes" by the miners. You have already addressed point 2 with your idea to send some "shares" into the sidechain P2P network. However I still struggle with argument 1), i.e. the sidechains could have much less hashrate/security budget/attack cost than the main chain, and that would make an attack easier in this case. Which can be a problem if the sidechains are becoming a relevant part of the Bitcoin ecosystem.

Initially I thought the following:

- in the Drivechain model, you have almost "Bitcoin-security" for the sidechain peg-in/outs because almost all Bitcoin miners participate;
- while in this model, the peg-in/out protection has the security of a typical altcoin, because smaller miners often get the puzzle solved.

However after thinking again: there may be enough incentives for most, if not all mainchain miners, like with merged mining of Namecoin when it was still a "respected" altcoin, to participate in the sidechain validation and puzzle solving, so perhaps the difference in terms of hashrate between mainchain mining and the puzzles isn't that big.

One could of course assume that all miners that mine a Bitcoin block with a sidechain transaction inside, would like to solve the puzzle too and add the transactions that transfers the sidechain reward to their own wallet into the same block. That is however not guaranteed, because you may find the block without halving solved the puzzle earlier, and so the miner would have to allocate resources to both the "block puzzle" and the "sidechain puzzle". If he allocates too much to the sidechain puzzle he risks being outcompeted by a miner who doesn't solve the sidechain puzzle.

Is my understanding correct?

[stwenhao]

the sidechains could have much less hashrate/security budget/attack cost than the main chain, and that would make an attack easier in this case

You can pick any difficulty you want. It can be much harder, than overwriting the whole mainchain. For example: bc1qss67lljllhph4wnmzn7f8qpc3wh6q48hlpfpznt9sz2lntw963nssn6kzm

When there is no Merged Mining, then this is how far you can get. You can pick a fixed difficulty, or adjust it with OP_CHECKLOCKTIMEVERIFY or OP_CHECKSEQUENCEVERIFY. Also, some people argue, that a coin without Merged Mining is better. In that case, they can just use it now in that form. And Merged Mining won't be there, as long as the community won't officially support sidechains, or activate them as a side-effect, by activating OP_CAT or other features, which would bring them indirectly. Or: if someone will come up with a better model, and deploy it, without any soft-fork.

However, even if the sidechain is much weaker, than the mainchain, then still: you have to attack Bitcoin, to attack the sidechain. You have to make a real double-spend, get it confirmed on Bitcoin, and spend a lot of Proof of Work, by actively trying to make that double-spend. Which means, that it is similar, as if you would attack Lightning Network, by confirming the old state of the channel. Because that model can be built on top of other things, like LN. It doesn't have to use only Proof of Work: it can use Proof of Work, and any conditions you would pick.

the peg-in/out protection has the security of a typical altcoin, because smaller miners often get the puzzle solved

It has that security, when the transaction is already broadcasted to the mainchain. However, as long as it is relayed only inside the sidechain, then mainchain miners don't know the keys. They don't know the conditions. They don't even know, that some sidechain is there. They can see just a regular P2WSH, with unknown Script.

Which means, that mainchain miners would have to join the sidechain, to actually know, which UTXO is in use (because public key can dynamically commit to the current state of sidechain mempools, so the address can change every time). Also, they would have an incentive, to broadcast their shares, and get sidechain coins. Which also means, that the most dangerous attack would happen, if some attacker would secretly grind the solution, and share it before all sidechain miners will collectively get there. But that can be also solved, if knowing the mining key would require knowing all sidechain keys. Which means, that the shared key can remain secret, as long as enough miners are online, and they are computing things under Homomorphic Encryption. Then, it is known, only when the sidechain block solver broadcasts it, and it gets decrypted by sidechain nodes, and shared on-chain. Which means, that it is then vulnerable only to short exposure attacks.

But note that the amount of coins often make it not worth attacking. For example: you have this puzzle: bc1qn9vp8l5rs7huyl237s4q9lhrzcs0mzaajt528ysq3wgnzvlkay5sdfz6am. It requires grinding around 2^64 hashes, as long as half of the generator has the smallest x-coordinate, where the private key is known. And if you count the profitability, then it is more profitable, to mine the regular mainchain block, than to solve this puzzle (at least for now).

So, instead of adjusting the difficulty, sidechains can just adjust the amounts. Then, if you want to send a huge transaction, you can use the mainchain. And if you want to buy a coffee, then you can use a sidechain. It is unlikely, that big mining pools will want to destroy their reputation, just to steal a bunch of satoshis. And the best thing is: there is no altcoin. Everything is covered by real BTCs. It is not the same as attacking some altcoin, because now, you are attacking real Bitcoin users. And also, even if Proof of Work fails, and gets attacked, then you can still fallback to LN, or other Script conditions, then it has comparable security assumptions, than alternative solutions, like pure LN without mining. Because you can attach Proof of Work to any Script you want, including doing that in some LN channel.

Is my understanding correct?

I think so. But we will know for sure, if people will start using such things, and building something on top of that. Now, it is still in testing stage. As always: it is recommended to first try doing all of that in test networks, and going to mainnet, when you will be comfortable with all of that. And even if mainnet puzzles were solved, testnet4 puzzles are still waiting there, so you can still get some of them even on CPUs, if you just understand, how the Segwit transaction is signed.

Edit: Try to move these coins, to get started: tb1qzsjnew5qcn75e4cqdsc6r9v8fjy5ensancqmv2l2n82p0q5f5tls758l9d. And when testnet4 coins will be claimed by someone else, then you can repeat the same experiment in regtest.