WIP: WIP-0006
Layer: Consensus (hard fork)
Title: Coexistence of BLS and Secp256k1 keys
Author: Gorka Irazoqui
Discussions-To: `#dev-general` channel on Witnet Community's Discord server
Status: Proposed
Type: Standards Track
Created: 2020-04-24
License: BSD-2-Clause
This proposal discusses different options to handle both BLS and Secp256K1 keys in the Witnet network. This is a key feature for the interoperability with Ethereum, in particular to achieve highly efficient signature verifications by leveraging the curves that the EVM subsidizes.
The co-existence of different curve keys will be crucial in Witnet in order to develop bridges with other chains. For the purpose of the document, we will only discuss the co-existence between Secp256k1 and BN256, being the latter subsidized in the EVM. However, this WIP can serve as a proposal for adding new curves to Witnet.
Implementing one-way decentralized bridges between two chains becomes a task that highly depends on the consensus protocol implemented by the chain whose transactions need to be verified. We will call this chain the source chain (i.e. the Witnet chain), while the chain in which the transactions are verified will be referred as the target chain.
Assuming the availability of the source chain's block headers on the target chain, one can easily verify that a transaction occurred in the source chain. Typically, transactions are grouped in a merkle tree whose root is inserted into the block header. Thus, to prove the existence of a transaction you just need to provide a valid merkle path that evinces that the hash of the transaction was undeniably inserted into the merkle tree at the time the block hash was appended to the source chain..
However, ensuring the availability of the block headers in the target chain is not that straightforward, specially for non-PoW chains. PoW achieves probabilistic finality thanks to the difficulty of reverting a chain with sufficient work on it, a difficulty that is publicly verifiable. In order to validate new block headers from chains whose consensus relies on a BFT algorithm that is based on an intra-chain metric (stake, reputation) the target chain needs to know the previous state of such metrics in the source chain. In the particular case of Witnet, it is yet not decided which metric to use, but under BFT assumptions we can expect 2/3 of such metric holders to be honest, and therefore a block header validity will likely depend on the ability to demonstrate that those 2/3 agree on a specific value. This can become truly challenging in terms of efficiency.
BLS signatures allow us to aggregate signatures provided by a set of group members. In the case of Witnet, those members will be the ARS, as the consensus of the Witnet chain is highly dependant on the reputation of each of the peers. The overall aggregated signature can be validated in the target chain in a single verification. However, a BLS verification is approximately 10 times more costly than a regular ECDSA verification. Thus, BLS gives us a big advantage for bridging with other chains, but little advantage when using it to sign transactions internally in the Witnet network.
In consequence, we need to derive a way to make both BLS and ECDSA algorithms co-exist in Witnet. This proposal introduces different solutions to such problem.
As already said before, we need to maintain a state about the ARS in the block headers that future blocks can be validated upon. Such information will be stored as a merkle root of all the identities and their position in the ARS.
Note that reputation score is currently associated to the hash of the Secp256K1 public key. However, ARS members in the ARS merkle root should be identifiable by their BLS public key, as this will be used to verify their aggregated signature.
Additionally, addresses and transaction outputs are also associated with the hash of the Secp256k1 public key. Given the clear overhead of implementing a BLS verification compared to a ECDSA verification, transaction outputs should keep being spendable by secp256k1 private key holders.
Our first proposal is to make every node store a mapping with the relationship between a Secp256k1 and the BN256 key.
secp256k1bn256Map mapping. A new mapping to be stored in memory that is updated every time a new key is proposed. This mapping does not need to be stored on-chain, but can be constructed by information that is on-chain. This can be implemented as an additional mapping to be stored in the chain manager.
type secp256k1bn256Map = HashMap<PublicKeyHash, Bn256PublicKey>;The Bn256PublicKey will initially be the one in G2, making the equation to satisfy in the block relay:
e(S, G2) = e(H1(M), P)
However, in order to improve the efficiency of the block relay calculations this can be subject to change.
bn256_public_key field. One new field in the commitment transaction body (CommitTransactionBody) data structure bn256_public_key is defined:
message CommitTransactionBody {
Hash dr_pointer = 1;
Hash commitment = 2;
DataRequestEligibilityClaim proof = 3;
repeated Input inputs = 4;
repeated ValueTransferOutput outputs = 5;
Option<Bn256PublicKey> bn256_public_key = 6;
}This new field will be optional, but by default nodes should include their public key in the commitment only if they are not members of the ARS. This way we avoid including for every single commit.
bn256_public_key field. One new field in the Block Header (BlockHeader) data structure bn256_public_key is defined:
message BlockHeader {
message BlockMerkleRoots {
Hash mint_hash = 1;
Hash vt_hash_merkle_root = 2;
Hash dr_hash_merkle_root = 3;
Hash commit_hash_merkle_root = 4;
Hash reveal_hash_merkle_root = 5;
Hash tally_hash_merkle_root = 6;
}
uint32 version = 1;
CheckpointBeacon beacon = 2;
BlockMerkleRoots merkle_roots = 3;
BlockEligibilityClaim proof = 4;
Option<Bn256PublicKey> bn256_public_key = 5;
}This new field will be optional, but by default nodes should include their public key in the block header only if they are not members of the ARS. This way we avoid including for every single block proposal.
Every time a commitment transaction associated with a pkh introduces a new bls_key, the mapping is updated. In this case we can foresee 3 scenarios:
-
Nodes do not change their BLS key: If nodes behave honestly, we can expect that they always specify the same bls_key in their commitment transactions.
-
Nodes introduce a new BLS key: There should be no problem on specifying a new bls_key as this will be updated in the mapping.
-
Nodes specify someone elses BLS key: We can suspect here that there is an attack going on. However such an attack would be identical to convincing a BLS key holder to vote for some specific value. Therefore, preventing this behavior does not close any attack vector.
With this information, a block producer can insert a merkle root of those BLS keys in the block header. This allows a smart contract to verify a potential membership to such set.
UTXOs and reputation points are still linked to a pkh, which is generated by a hash of the Secp256k1 public key. Therefore, no further change should be necessary to be compatible with previous features.
Extending such functionality to be able to associate a secp256k1 public key to an additional curve key should be as simple as creating declaring an struct with all curves we want to store the public key for.
struct AltPublicKeys {
Bn256PublicKey: bn256_public_key,
BLS12381PublicKey: bls12381_public_key
}and update the mapping us:
type secp256kAltPublicKeys = HashMap<PublicKeyHash, AltPublicKeys>;This proposal is a draft submitted for evaluation and eventual approval from the Witnet community.
No reference implementation exists or is provided. More details on this can be found in the Adoption Plan below.
Due to the undeniable impact on consensus of this proposal, it becomes apparent that these protocol changes need to be introduced through a coordinated upgrade of the whole network.
No special provision in this proposal mandates the application of distinct validation rules for transactions and blocks that predate its eventual activation. In consequence, the protocol changes proposed herein are expected to be applied on a newly bootstrapped block chain in which the updated protocol must be applied starting from the genesis block itself. It is also expected that the protocol changes that this WIP implies are tested in cojunction with those that implement the necessary BLS features to achieve a decentralized block relay.
This proposal has been cooperatively devised by many individuals from the Witnet development community.