The future of Mulitsigs & cryptography on HIVE

Greetings HIVE community! In this post we'd like to go into detail about the underlying technology of HIVE, specifically multisigs, and what changes we need for the L1. As many of you already know, HIVE lacks L1 smart contracts. Not only is this a problem for the community in general, but also creates major pain points for L2s. Luckily, HIVE has always had native multisigs for it's accounting. A native function that can be hit or miss on other blockchains. However, while this is a useful tool for in general use, it has major limitations for L2s like VSC. In this blog I will go into depth about the problem space, and the suggested changes the VSC project is proposing to the HIVE core team.

Counterparty risk on HIVE

Many of you have already heard of this term one way or another. Almost universally, this carries a negative connotation and rightfully so. With many bridge hacks, insecure L2s, it's easy to lose trust in a system, especially when lots of money is at stake. But, what is counterparty risk? And how does it affect HIVE? For starters, counterparty risk is essentially the assumed risk when a user entrusts their funds into another entity out of their control. This can take the form of DEXs, bridges, and even smart contracts. Luckily for us, a good smart contract with no admin keys, securely audited, and on a safe L1 network has almost zero counterparty risk.

On the otherhand, for L2s this is a lot more complicated to answer, while L2s might have perfect security within themselves, to interact with the L1 (i.e own funds), someone or something (a smart contract) MUST own the L1 funds, and thus create the potential for counterparty risk. Typically L2s employ a trusted entity to hold funds for network. This might be a centralized party or a small mulitsig with a few trusted members depending on the L2. Unfortunately, the reality is most of the top Ethereum L2s solely employ centralized custody or mulitsigs that are not under the control of the community. The controlling entity has complete authority and ability to steal users funds. How can anyone say these so called L2s are secure and decentralized? You can't.

On HIVE, we have native multisig capabilities, which is great! Using this technology in combination with a consensus system, we can help reduce counterparty risk for VSC. Making VSC more decentralized and secure than top Ethereum L2s. VSC node operators are actually in control of L1 funds, and not a single centralized entity. With all this in mind, there are limitations. We have a maximum of 40 signers on any multisig, which boils down to approximately 30 signers with full control (for a 3/4 consensus). This is still better than an Eth L2 with only two or 3 signers for entire network of thousands of nodes and billions of dollars. However, it's still not enough to address modern concerns around L2 security.

While this point is not directly relevant to security, the data cost of operating a multisig on HIVE is not practical. As more signers are added to the multisig, the larger the minimum transaction size becomes. Each transaction for a multisig of 30 signer is a minimum of 2kb, which might not sound like a lot, but it's 30x bigger than regular transactions and larger than the average size of 99% of transactions on HIVE. As a result, the large transaction size imposes significant costs to a L2 and adds significant chain bloat with heavy usage.

Cryptography to the rescue!

Given everything above, it's clear that the current approach to multisigs is not optimal for L2 networks. To solve this HIVE must implement Boneh–Lynn–Shacham (BLS) signatures into the L1 network. BLS is very similar to the current signature algorithms implemented on HIVE, except it allows for very efficient signature and public key aggregation. Signature aggregation allows for combining all of the signatures from hundreds of even thousands of public keys into a single one while proving the exact same information. The result is a massive storage space savings for mulitsig operations and allows for a significant expansion of the maximum allowed signers. Mulitsigs on HIVE could easily have hundreds of even thousands of signers inside nearly the same data footprint as a single signature. For VSC, this makes a significant difference in the security of on chain custody.

Technical details

this section goes more into the technical details while still keeping fairly high level. Feel free to comment any further questions below.

BLS properties:

Private Keys: 32 Bytes.
Public Keys: 48 Bytes.
Signatures: 96 Bytes.

Above, are the sizes of BLS private keys, public keys, and signatures. If you are familiar with ECC cryptography, you will notice the public key and signatures are larger than regular secp256k1 or ECDSA algorithms. However, despite the larger data footprint of a single signature, the aggregation of signatures results in siginficant size decrease at scale.

To do this process, the following concepts must be noted:

A Bitvector - a series of pointers that indicate which public keys signed a transaction. The bitvector is the only part of a transaction that increases in size as more signers are added.
Key identifier - identifies the entire signing group for a multisig. All signing parties and their associated weights.
Aggregated signature - signature created from combining all signatures from each party.

Steps:

The multisig registers all the public keys and their associated weights. This produces a key identifier unique for that particular group. Note: the public keys are sorted in a deterministic order.
From this point HIVE nodes have enough information coupled with the transaction can verify any signature from any combination of signers
A transaction is then constructed and signed by several signers in the multisig.
The aggregate signature is created as a result
A bitvector is created from the list of public keys involved in the transaction against the entire signer group. This creates a compressed representation of each public involved and scales on the basis of 1 bit per public key.
HIVE nodes will then use the key identifier & bitvector to compute the combined public key for the signers involved in a transaction
The aggregated public key can then be used to verify the signature of the newly created transaction.

The result is a transaction with a constant aggregated signature size and a highly space efficient bitvector
Using this approach, it allows us to scale to hundreds of even thousands of signers participating in a multisig with significantly less overhead.
This technique becomes more efficient as more signers are added. For 3 signers, there is only a storage reduction of 1.4x, where as for 500 signers, the size reduction becomes 170x smaller and continues to scale to a theoretical maximum of 520x (1/8 byte per signer vs 65b per signer)

Legend:

Y Axis: total transaction size in bytes
X Axis: total number of signers
Red line: traditional multisig on HIVE
Blue line: mulitisig using BLS signatures w/aggregation on HIVE.

The graph above shows you how the storage usage of a traditional multisig scales vs multisig using BLS signatures. You can clearly see how a traditional approach quickly skyrockets in size, where as BLS signatures only marginally increase the transaction size as bitvector increases in size. This does NOT take into account gross storage usage of key identifier, registered public keys, or computational costs and only looks at individual transaction size.

Call to Action!

We urge the HIVE core team to implement BLS signatures & aggregation technology into the HIVE L1. We strongly believe implementing this technology would be easier and safer than L1 smart contracts and opens major possibilities for VSC & Other L2s alike. By HIVE implementing this technology, it would join the ranks of Polkadot, Ethereum, and other chains using attempting to build similar technology. We could be one of the first to fully implement this technology and make it directly available to end users.

We also acknowledge there is even more that can be done to further decrease transaction overhead regarding multisig, such as zero knowledge proofs and signed merkle trees. We aim to make this only a fraction of a compressive set of improvements to the L1 for supporting VSC and future projects on HIVE. This is only the beginning

I intend to meet with the core team to present this information directly and start the process of building into the next hard fork.