Rootstock (RSK)’s Peg-out efficiency improvement — Segwit (part 3/3)

Co-authors: Ramsès Fernàndez-València and Nicolás Vescovo

In the previous posts (part 1 & part 2) on our RSK’s Peg-out efficiency improvement series, I described the main actors of the architecture, the limitations of the current design and a brief introduction to Segwit versions. I also went more in-depth and described the different proposals studied with their corresponding implementation: Segwit v0 and Segwit v1/Taproot (FROST, ICE-FROST and MuSig2).

In this last post, I will end up with a comparison of the proposals and a conclusion.

Comparison

Summary

PowHSM Complexity

When we refer to the complexity we are talking about code and data structure.

Segwit v0

The complexity here involves only code, as the only change involves the fields that now compose the digest of the signature, and where (in the transaction) to put the resulting signature. We consider that comparing the rest of the protocols is a low-effort change, not to underestimate the complexity but to expose it compared to the rest.

Segwit v1

In both cases, it is easy to see that FROST would be much more complex than MuSig2. In the case of Musig2, it is a “medium” complexity. We can highlight:

• that the Bitcoin transaction parsing by the powHSM changes (we have to account for witness parsing, which is currently not supported).
• that the message to sign computation by the powHSM changes
• that the powHSM does not have to validate the chosen script path and therefore there’s no Merkle proof parsing involved
• that, as opposed to FROST, there is no additional “step” with added complexity in the signing operation

But in the case of FROST, we have much more complex logic to implement:

• Setup process generating a shared secret depending on the “m” of the threshold.
• Random generation for each UTXO to sign.
• Random association for different rounds between the random and a UTXO id. (additional data structure).
• Signing process custom using random generated and pk.

Fees cost

We will consider “fee reduction” only in terms of signature and redeem script, which is the variable data necessary to redeem an output. For calculating the total fee reduction we would have to analyze different scenarios combining a quantity of inputs and outputs, and all the data regarding the transaction (not in the scope of this document).

It became clear that the main fee reduction comes with the upgrade to Segwit v0 (~70% fee reduction) and that Segwit v1 takes advantage of it and makes it even more efficient (~90% fee reduction).

Focusing on Segwit v1, we can say that although both schemas would have better fees than the current one, we could prove that FROST has a constant low fee which is several times (15x approx.) lower than what it is now. While the MuSig2 depends on the size of the threshold (m and n), the reduction percentage is not as significant as FROST.

Notes

1. We calculated the bytes as an approximation. There are more components of the transaction not relevant to this study.
2. An ECDSA signature is usually about 72 bytes in size for a single signature in a transaction. Schnorr signatures clock in at a maximum of 64 bytes per signature.

Example of fee calculation for a threshold 7 of 13:

Current (P2SH) fee calculation

• Script: “M <pk1> <pk2> … <pkN> N OP_CHECKMULTISIG”
• Script vb (M of N) : 1 + 33 * N + 2 = X
• Script vb (7 of 13): 1 + 33 * 13 + 2 = 432
• Signatures vb (M of N) : (72+1) * M = X
• Signatures vb (7 of 13) : (72+1) * 7 = 511
• Total = 432 + 511 = 943 vbytes

Segwit Compatible (P2SH-P2WSH) fee calculation

• Script: “0 <ActualRedeemScriptHash>”
• ActualRedeemScript: “M <pk1> <pk2> … <pkN> N OP_CHECKMULTISIG”
• Script WU (sha256=32b / not in witness -> *4) : (32 + 1 ) * 4 = 132 WU
• ActualRedeemScript WU (M of N) : 1 + 33 * N + 2 = X WU
• ActualRedeemScript WU (7 of 13): 1 + 33 * 13 + 2 = 432 WU
• Signatures WU (M of N) : (72+1) * M = X WU
• Signatures WU (7 of 13) : (72+1) * 7 = 511 WU
• Total = 132 + 432 + 511 = 1075 WU / 4 = 268.75 vbytes

Segwit Native (P2WSH) fee calculation

• Script: “<pk1> OP_CHECKSIG <pk2> OP_CHECKSIGADD … <pkN> OP_CHECKSIGADD M OP_EQUAL”
• Script WU (M of N) : (33+1) * N + 2 = X WU
• Script WU (7 of 13): 34 * 13 + 2 = 444 WU
• Signatures WU (M of N) : (72+1) * M = X WU
• Signatures WU (7 of 13) : (72+1) * 7 = 511 WU
• Total = 444 + 511 = 955 WU / 4 = 238.75 vbytes

FROST (P2TR — key path) fee calculation

• Signatures WU (1 signature only): 64 WU
• Total = 64 WU / 4 = 16 vbytes
• Musig2 (P2TR — script path — MAST) fee calculation
• Script: “<pk> OP_CHECKSIG”
• Script WU: 34 WU
• Inner key of root key: 32 WU
• Hashing partner in tree: 32 WU * Log_2 (Cmn )
• Hashing partner in tree (7 of 13): 32 WU * 11 = 352 WU
• Signatures WU (1 signature only): 64 WU
• Total = 34 WU + 32 WU + 352 WU + 64 WU = 482 / 4 = 120 vbytes

We are not going to show the demonstration, but in an example of a threshold of 17 of 34 (this is the maximum we can represent due to a limitation of MAST being 32 the maximum height of the tree), the difference between the options becomes notable in favor of FROST which is constant. But we have an acceptable difference in favor of Segwit (both scenarios).

• Current (P2SH): 2396 vbytes
• Segwit Compatible: 620.25 vbytes
• Segwit Native: 599.25 vbytes
• FROST: 16 vbytes
• Musig2: 288.5 vbytes

Real world example

Peg-out transaction:

https://www.blockchain.com/btc/tx/cdbae904e8465fe42cadf61e584a948a40a8a1852f0a444c9d8c4c3aa0fa65d6

• Fee: 0.00016305 BTC
• Fee ~$: 6

Fee reduction:

P2WSH (Segwit v0):

• Fee: 0.000048915 BTC
• Fee ~$: 1,85

Musig2:

• Fee: 0.00003261 BTC
• Fee ~$: 1,20

FROST:

• Fee: 0.0000179355 BTC
• Fee ~$: 0,70

Verification complexity

Here we want to compare how hard it is to verify that, for security reasons, the possible ways to spend the UTXO are completely transparent and there is no hidden condition that someone could exploit.

In the case of FROST, the shared keys should be easily computable, checking that the aggregation of the same corresponds to a valid threshold of m of n. Which should require a short computation time and effort.

But in the case of Musig, it depends on the size of the threshold. If it increments in size, the combination of possible scripts becomes higher, and we would need much computation time and effort. For instance, if we take a threshold of 17 of 34, we have approximately 2.333 Millions possible scripts. To validate the tree, we should rebuild it by combining all possible groups of 17, hashing all intermediate keys (another 2.333 Million hashes) to reach the Merkle root, and reconstructing the main Taproot key. It is possible but confusing and adds complexity to its use and trust.

Robustness

Let’s define robustness as the ability of the schema to resume in case of failure or malicious actors without needing the whole process to restart from the beginning.

We could say that FROST and MuSig2 have the worst robustness because they need to restart the process. But, in the case of FROST, it has its variant ICE-FROST, which improves some scenarios, making it a more robust solution. Neither of them reaches the current working solution, which has better robustness, not being possible to abort the process if one of the actors acts maliciously.

It is good to mention that we didn’t explore the possibility of improving Musig2 robustness. Still, we believe that it should be possible to get a better result by analyzing different scenarios with the Federation team, once they understand the implementation aspects of this schema.

Implementation time

This is only an estimated subjective opinion since we still don’t have any valid PoC of these schemas. But, supported by the analysis, we could say that Segwit could be the easiest solution to implement in the short term, followed by FROST in the medium/large term, due to complexity and the need to develop new features involving more than 1 team (Federation, Core and HSM).

Short-term would be estimated in a couple of months, while long-term we would require an estimate of 1 year development time.

Threshold N Limit

Segwit has a limitation of a threshold of “m of 67” due to the limit on the script size (3600 bytes) and the 201 script ops limit, where we publish all the public keys of the pegnatories.

MuSig2 has a limit of a threshold of 17 of 34 (this is the maximum we can represent due to a limitation of MAST being 32 the maximum height of the tree), whereas FROST has no limit in terms of how many participants can generate an aggregate signature. But we believe that FROST has a limit in terms of the complexity of communication of signatures and Bridge coordination between them. So this “unlimited” feature related to FROST is just theoretical.

Furthermore, in practice, we have another constraint, which is memory consumption. The Bridge runs into a node of limited memory. In the case of FROST that constraint doesn’t matter at all since we only need to recover some signatures and do some small computations. But in the case of Musig2, we need to compute the tree, which can have millions of elements and hashes in memory.

An estimative table has been made with the following formula:

• Being X = # of elements
• Size of script (leaf) = 34 bytes
• Size of the hash (intermediate leaf) = 32 bytes
• Total size of the tree (in megabytes) = (X * 34 + X * 32 * 2) / 1.000.000

The next table is estimated in MegaBytes (MB), combining thresholds of M of N:

For the purpose of this analysis, we suggest taking ~500MB as a limit of what a node can use to represent this tree. So the maximum possible N is 25.

Conclusion

After the analysis, we can take some takeaways.

• Comparing all the proposals with the current method (P2SH), we can see that Segwit improves several aspects, especially those related to fees and, in particular, when it comes to the threshold limit, which allows Segwit to provide more flexibility. Even with just Segwit v0, the improvement is considerable.
• When comparing Segwit v1 proposals (FROST, ICE-FROST and MuSig2), we can observe that FROST is the most efficient scheme. It has a fixed fee cost, a no-limited threshold and an improvement in a fee reduction of around 98%. However, the scheme is hard to implement and requires a big effort. We could consider this schema for the long term in the future.

To put it all together, although Segwit v0 does not provide the best overall performance compared to the other mechanisms, it emerges as the most robust option with promising results in terms of efficiency and greatly improves the economic aspects of P2SH.

As a first step considering the benefits, we are going to propose an upgrade to Segwit v0 (RSKIP-305) in the short term and the plan for a long-term FROST (TBD) scheme implementation, which will lead to outstanding performance and more security for the RSK PowPeg.