README.md

Idena ETH Relay

Idena-ETH-Relay is used to make the validated cryptoidentities be relayed from the Idena Blockchain to Ethereum Blockchain.

The idea of this project came from Gitcoin Hackathon: GitxChange, and this solution was based on the "Possible Implementation" advice from idena official.

Solution

This solution uses a relay smart contract to maintain validated cryptoidentities in ethereum blockchain from idena blockchain.

The initial state of the smart contract need to be set after deploying by the owner (probably the idena official team), however, they can only do this once. After the initialization, anyone who can provide the crypto-valid state transition can send an ethereum transaction to change the contract's state.

A crypto-valid state transition requires the previous state, the new validated identities added, the old validated identities deleted, and the signatures of old validated participants confirming correctness of this transition. These data of crypto-valid state transitions will be publicly available in the idena blockchain when the validated identity set changed (new epoch applied, kill identity, kill invitee).

This will make the relay contract maintain the up-to-date set of validated identities from idena blockchain without any trusted oracle(s) or organization(s).

We use the BLS(Barreto Lynn Scott) signature scheme instead of the ECDSA (secp256k1) used by both ETH1 and idena to have smaller inputs and consuming less gas. Because quorum signatures are required for each contract state updating, and the BLS signature have suitable features like key aggregation and multi-signature. Due to the limitation of current evm, it is impractical to use the more secure BLS12-381 algorithm, we adopted the BLS-256 with alt-bn128 curve for now.

The whole solution is mainly composed of two parts:

1. The relay smart contract
2. The improved idena node

The Relay Smart Contract

Relay contract is responsible for maintaining addresses and BLS keys of all validated cryptoidentities from idena blockchain.

A sample relay contract has been deployed to the rinkeby testnet for testing, details can be found in deploy-rinkeby.md.

The smart contract mainly maintains the following states:

• height: the height of the idena blockchain corresponding to the contract state.
• identities: the latest validated identity address list, and the order of the list is the same as that in the idena blockchain (relay state).

  The address represents the validated identity in idena, its format is same as the ethereum address since both idena and ethereum use the same address rule.

• state: a map, records the BLS (G1) public keys corresponding to each address of validated identities.

  The keys are BLS(Barreto Lynn Scott) public keys generated by the improved idena node with alt-bn128 curve. They are derived from the idena nodekey by default (see docs of node below).

• root: the latest state hash of the relay. It is used to ensure that the contract state is consistent with the state of idena blockchain.

Initialize

After deployment, the owner needs to obtain the state data of any chosen height from the idena blockchain to initialize the contract. Because of the limitation of gas in ethereum, the initialization need the following two interfaces to support state with thousands users:

• prepareInit() is used to submit initial identities (addresses and BLS public keys) by owner. The initialization can only be performed once, while this function can be called multiple times before the end of initialization.
• finishInit () is used to finish the initialization. This function can only be successfully called by the owner too, and it can be called only once after deploying and for ever.

Update

After the initialization, anyone can obtain valid data for subsequent state updates from the idena blockchain and publish it to the relay contract. The valid data means the correct state change information with quorum signatures from validated identities. It be obtained from the improved idena node(please refer to the document of improved node below).

Because of the gas limitation again, contract provide two ways to update state:

• When the state change is small (e.g. kill identities, kill invitees before validation ceremony), quickUpdate() can be called to do the update in one transaction.
• When the state change is big (e.g. after validation ceremony), a update flow with the following three steps are needed:
  1. prepareUpdate(): This is used to upload and store address and pubkey (BLS G1) of new identities. It must be called at least once regardless of whether there are new identities for a flow-way update. Anyone can create his own update flow for specific height by calling prepareUpdate(), and it can be called multiple times for one update flow by creator only.
  2. verifyUpdate(): This is used to verify the state to update for the flow. Only the flow creator can call this function to make his update flow verified. If verification passed, the contract will be in updating state to wait the flow being submitted. Any other verification request will be rejected before the submission operation is completed.
  3. submitUpdate(): During updating state, anyone can call this function to submit the verified update flow data. It can be called multiple times by different users to finish the submission. When the submission is completed, the updating state will be cleared.

Interface

The relay contract also provides the following interfaces for contracts (DApps) in ethereum to obtain idena identity state easily.

• function isUpdating() public view returns (bool): Returns whether the contract is in updating state or not.
• function identities() public view returns (address[] memory, bool): Get the list of all encrypted users validated in idena (along with the updating state).
• function identityByIndex(uint256 i) public view returns (address, bool): Query identity address by index along with the updating state (along with the updating state)..
• function isIdentity(address addr) public view returns (bool, bool): Check if the specific identity is validated in idena (along with the updating state).
• More interfaces can be found in the contract source code

Tests

Below is an example of test case output, which simulates a state initialization with 2468 identities (same as epoch47) and different update cases. Gas costs of all operations are printed for reference.

More test outputs can be found in test-results.md

The Improved Idena Node

You can find the improved node implementation here.

Following are the design and implementation instructions of the idena node modification:

• BLS keys used to generate multiple signatures will be derived from the idena nodekey(which is a secp256k1 ecc private key). The derivation algorithm can be found in secstore.

• To bind BLS keys to idena identities, nodes will publish the BLS public keys during the validation ceremony by sending a BlsKeysTx transaction to the blockchain.

  • In order to ensure that the published BLS keys are correct and valid, identities need to publish both the BLS public keys and a BLS signature of the binding address.
  • The published BLS public keys will be save to stateIdentity in StateDB first, and after the validation ceremony the keys of validated identities will be saved to stateApprovedIdentity in IdentityStateDB too.

  Although it was said that BLS key is derived by the specific algorithm, it is only a default implementation of this improved node. In fact, identities are not forced to use this method to generate a matching BLS key, they can publish any bls key generated by themselves as long as keeping the generated private key secret and safe.

• The IdentityStateDB will record the whole relay state matching the relay contract in ethereum, including all validated identities, their orders and BLS public keys. We will use order indexes to indicate the identities to save gas. This relay state in IdentityStateDB will change when new identities are added or any old identity is deleted. Those will happen in the follow cases:

  • After the validation ceremony.
  • KillTx is found.
  • KillInviteeTx is found.

• When relay state is changed, node will need to do following works:

  1. Generate the difference between current state and previous state. It will be sent to the relay contract in ethereum for state synchronization.
  2. Calculate a state root for the new relay state used for signature verification. state root is generated by height, previous state root, new identities, order indexes of deleted identities, the algorithm is exactly same as the relay contract. This implementation can be found in relay.go.
  3. Collect enough signatures for this state change, and aggregate the signature into one for sending to the relay contract later.

• Idena node will collect signatures for each state change through gossip messages. The main collecting algorithm can be found in relay's StateManager

  Other solutions have been considered, for example, collect signatures through onchain transactions, or modify block structure, or modify consensus voting, etc. But it feels that these methods are too invasive to the idena blockchain, improper modification may cause serious problems, like reducing the performance of the blockchain, causing the consensus to lose liveness, etc. So, the current implementation version adopts a loosely coupled and safer way, which has smaller impact on the idena blockchain and consensus. In the future, it is necessary to consider these deeper implementation solutions.

• There will be a RelayState contains the state root and multi-signature info of each block. RelayStates will be saved to database repo with relayStatePrefix = []byte("relay"), find it here.

• Three new APIs are added to provide people or bots with the data needed to send transactions to relay contract.

Improvements

• Make the relay contract to consume lower amount of gas.
• Synchronize more state data of idena blockchain to the contract, like identity status(newbie, verified, human).
• The BLS signatures collection algorithm need to be improved.
• Adopt the BLS12-381 instead of bls with alt-bn128 after the hard-fork of ethereum blockchain with BLS12-381 support.
  • EIP 2537: Precompile for BLS12-381 curve operations
  • EIP 1962: EC arithmetic and pairings with runtime definitions

Other Solutions

Idena ethereum relay is a wonderful idea, and the solution adopted now is not perfect.

For example, the following directions are worthy of consideration and attention:

• Use Zero-Knowledge Proofs like zk-snarks or others to prove the correctness of transition.
• Adopt the BLS threshold signature (subgroup multi-signature scheme, m-of-n multisig), which will make the verification more concise and efficient.

Any other solutions, ideas and suggestions are welcome.

Tools and Apps

bls-256-go implements the initial version of bls-256 signature used by the relay.

relay-tools implements some tools of idena ethereum relay. Currently it can be used to generate test data for relay contract.

More tools and apps are expected to be developed to make the relay work better and easier. Such as the following tools (not limited to)

• A robot like program to monitor the idena blockchain and call relay contract to synchronous state.
• A frontend of the relay contract to show contract state more intuitively.
• DApps on the ethereum blockchain to integrated the validated cryptoidentities from idena.