[$5000 DNAs] Build Idena Ethereum Relay

[midenaio]

Prize Title

• [$5000 DNAs] Idena Ethereum Relay: How the registry of validated cryptoidentities could be relayed from the Idena blockchain to Ethereum

Prize Bounty

• $5k paid in DNAs
• The prize can be split into pieces according to the agreement of the collaborating hackers.
• Hackers receive prizes only if they meet the submission requirements.

Challenge Description

We expect to see two parts of the project that can be implemented by different hackers in collaboration:

• An Idena Ethereum Relay smart contract on the Ethereum blockchain that mirrors the list of cryptoidentities validated on the Idena blockchain
• Idena node improvements to provide data for an Ethereum smart contract (see details below)

Background

Idena is a novel way to formalize people on the blockchain. It does not collect or store personally identifiable information. Idena proves the humanness and uniqueness of its participants by running an AI-hard Turing test at the same time for everyone around the globe. The Idena blockchain is driven by proof-of-person consensus: Every node is linked to a cryptoidentity, one single person with equal voting power.

The Idena validated participants registry is a list of addresses with proven semi-uniqueness of their owners (see examples in the Idena blockchain explorer). Each Idena participant can own one valid cryptoidentity address, it is difficult to have two or more.

The uniqueness of participants is proven by the fact that they provide answers for flip-puzzles synchronously. A single person is not able to validate herself multiple times because of a very limited timeframe for submission of the answers. The bigger the network is, the less frequently the validation sessions happen. The validation status of a participant is not forever. It expires when the next epoch starts. Participants should prolong their validation status for every new epoch. Read more in the Idena website FAQ section.

Possible implementation

The Idena cryptoidentity address is fully compatible with the Ethereum address. In order to use Idena cryptoidentities in the Ethereum blockchain, it is necessary to create a protocol to relay the list of Idena’s cryptoidentities into an Ethereum smart contract without trusted parties.

The relay can be done in two ways:

A. Trusted oracle (not considered)

A special agent/organization authorized to record information to a special smart contract on Ethereum acts as a trusted Oracle. Whenever the cryptoidentity list changes, the trusted Oracle updates the list of valid identities:

• When an identity in Idena is terminated (see Kill identity and Kill invitee methods)
• Upon the end of each validation (see validation results for epoch Change default ceremony time #44)
• The Oracle does not provide any evidence of the changes’ accuracy and is a potential point of failure. We do not consider this approach for the challenge.

B. Trustless Idena Ethereum Relay

A possible alternative solution does not imply a trusted Oracle (or numerous Oracles).

Initially, an Idena Ethereum Relay smart contract has to be created, in which the current list of Idena validated identities’ addresses are included by the contract developer. This initial list of addresses is the genesis of the registry and is manually verified by other participants.

Anyone in the Ethereum network can change the identity list, while providing proof of correctness of the change to this contract:

• When an identity in Idena is terminated, a transaction taken from the Idena blockchain is provided as evidence into the Idena Ethereum Relay smart contract. The smart contract analyzes the signature of this transaction and the type of transaction. If the signature is valid the change is accepted by the contract.
• Upon the end of each validation, along with the list of newly validated participants, signatures of old validated participants confirming correctness of the new list are provided as evidence. These signatures are to be published automatically by Idena nodes.
• The Idena Ethereum Relay smart contract checks the provided list of new participants, calculates the hash of this list. Then it checks the provided signatures of the old participants. Each signature must match the hash of the new participant list. If there are more than 2/3 valid signatures provided to the contract, the contract goes into a new state with a new list of valid addresses.

Availability assumption

The mechanism will work only if a large share of participants of the old registry keep the nodes up and running after the validation and provide their signatures for the new state.

Possible problems: Relay costs

1. When validating 10,000 members in Idena, all the 10,000 entries must be provided to the contract. Relaying such an array of data to Ethereum smart contracts may be expensive.
   Possible optimization: Only the difference between the new and the old lists are relayed to the contract.
2. In order to switch to a new state from the list of participants with 10,000 addresses, 6666 signatures must be relayed. Relaying such an array of data to an Ethereum smart contract and verifying signatures may be expensive.
   Possible optimization:
   As a list of signatories, a committee of a smaller size can be formed in a deterministic manner.
   Using BLS signatures aggregation
3. Due to the high cost of the changes relay, there will be no economically motivated participants to transfer changes to the Idena Ethereum Relay smart contract.
   Possible solution: socialization of transaction costs in the business models of participants paying for the relay of Idena identity registry changes.

Submission Requirements

• All the code must be open source
• Idena Ethereum Relay smart contract requirements:
  • The Idena Ethereum Relay smart contract should be deployed in the Ethereum testnet. A test set of cryptoidentities should be saved in the smart contract.
  • The Idena Ethereum Relay smart contract should provide an up-to-date list of cryptoidentities
  • The Idena Ethereum Relay smart contract should provide secure public methods of updating the list of valid cryptoidentities in case of registry changes on the side of the Idena blockchain
  • The smart contract should consume the lowest possible amount of gas to solve the problem
• Required Idena Node improvements:
  • To calculate the hash of the new list of participants as the Idena Ethereum Relay contract does it
  • To produce a signature for the new set of cryptoidentities required for the Idena Ethereum Relay smart contract

Submission Deadline

• Official end date of the hackathon

Judging Criteria

• The following tests should be available:
  • Test 1: The Idena Ethereum Relay smart contract should be robust and fully-functional. It must be deployed in the Ethereum testnet. Initial test set of cryptoidentities should be saved in the smart contract.
  • Test 2: Pushing a new list of cryptoidentities into the smart contract
  • Test 3: Pushing a set of signatures which is sufficient to change the smart contract state
  • Test 4: Applying the new set of cryptoidentities in the Idena Ethereum Relay smart contract
• The Idena Ethereum Relay smart contract should consume the lowest possible amount of gas to solve the problem.
• The Idena node improved version should produce a signature for the new set of cryptoidentities required for the Idena Ethereum Relay smart contract

Winner Announcement Date

• June 22nd, 2020

Resources

• https://idena.io Idena website
• https://idena.io/?view=faq Idena FAQ
• https://idena.io/?view=download Idena app and Idena node download page
• http://rpc.idena.io Idena node RPC
• https://scan.idena.io Idena blockchain explorer
• https://scan.idena.io/epoch/44 list of validated identities for epoch #0044
• https://github.com/idena-network/idena-go Idena node github repo

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

This issue now has a funding of 0.001 ETH (0.2 USD @ $198.53/ETH) attached to it.

• If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $138,919.87 more funded OSS Work available on the Gitcoin Issue Explorer

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work has been started.

These users each claimed they can complete the work by 1 year, 8 months ago.
Please review their action plans below:

1) henryfour has started work.

Interesting idea, and I used to have a similar idea, the he challenge is mainly at the efficiency (space/time).
I think zkp might be a good choice, but it need more design and time.
So I will try to implement a basic version similar to the one described in 'Possible implementation' first.

Learn more on the Gitcoin Issue Details page.

[uivlis]

Hi guys, I've been working on this.

Though, the functionality is still not ready for the kill scenario (working on it). Also, working on modifying the node.

Waiting for any thoughts!

[uivlis]

Hello, it's me again. I have a bit of a conundrum: in the task's description for the kill functionality, you mentioned:

When an identity in Idena is terminated, a transaction taken from the Idena blockchain is provided as evidence into the Idena Ethereum Relay smart contract. The smart contract analyzes the signature of this transaction and the type of transaction. If the signature is valid the change is accepted by the contract.

Now, my question is: what exactly means "the signature of the transaction" in this context, perhaps the txHash? If so, how can I check that "the signature is valid", since I would need an Eth-Idena oracle to make sure the tx actually exists on Idena? And, if not, then I assume you meant the txHash signed by somebody... but wouldn't that also require 2/3 of the votes?

[busimus]

I would need an Eth-Idena oracle to make sure the tx actually exists on Idena?

@uivlis I don't think this is necessary.
I assume "signature is valid" is to be taken literally: the transaction was signed with the private key of the identity who is authorized to carry out the given transaction.

In the case of KillTx, an identity can only terminate itself and there's no benefit in faking your own termination, so there's no need to verify anything.
In the case of KillInviteeTx, it's trickier. You have to somehow verify that the transaction was signed by someone who is the current inviter of the recipient of the transaction ("current" meaning the inviter link hasn't been erased, which happens after invitee reaches Verified status). Not sure how to do that.

[uivlis]

@busimus Thanks!

Regarding the KillInviteeTx case, I'm thinking it's possible to drop it altogether, since killing an invitee that has not been validated yet has no effect on the state of the relayed verified addresses.

[busimus]

@uivlis Why does it not have an effect? Are you excluding Newbies from the list? They're included in the network size, so they count as "validated". I don't see anything about discrimination by status in the task description.
An inviter can terminate their invitee if they haven't reached Verified status yet, which is based on the amount of flips they solved in short sessions (currently more than 12 flips, so 3 validations to become Verified).

[uivlis]

Initially, an Idena Ethereum Relay smart contract has to be created, in which the current list of Idena validated identities’ addresses are included by the contract developer.

No, no, I didn't mean to exclude anybody, it's just that I thought that "validated" meant Verified, but I see now that it just means "in the network", right?

[busimus]

@uivlis Yes, Newbies are in the list of validated identities in the explorer, so I have no reason to think otherwise.
That being said, I still wasn't able to come up with a good way of verifying KillInviteeTx and the devs suspiciously left no clues about it.

If you require correctly signed InviteTx and ActivationTx along with KillInviteeTx as proof of the fact the given identity is actually the inviter of an invitee, you don't get any more information from that than "this identity successfully invited this other identity at some point" (i.e. you can't prove they're the current inviter).
If you try to check the Epoch of those transactions and compare it with the current epoch to see if more than 3 epochs have passed since the invitation, you have to rely on devs never changing the number of flips required to become Verified.
And then there's also an edge-case of a malicious inviter. They can invite someone and cancel their invitation after invitee accepts, which would give them enough proof to remove the invited identity from the list in the future (if that invitee finds another inviter quickly and validates).

I may be missing some important piece of the puzzle.

EDIT: I love thinking about something for hours, posting about it, and then minutes later realizing that I'm wrong.

[bingbinglee]

@midenaio ^

[midenaio]

@uivlis There are two possible solutions for the KillInviteeTx verification:

Solution 1 (additional data is required for the smartcontract)

1. There are two attributes could be provided to the smartcontract in addition to the list of validated addresses (signed by 2/3 of the network):

• Cryptoidentity status (Newbie, Verified, Human)
• Inviting address (for Newbies only)

2. The KillInviteeTx is valid if the transaction hash is signed by the inviting address which is known by the smartcontract

Solution 2 (Merkle proof)

1. The dataset of pairs (inviting address, newbie address) is represented as a Merkle tree. The Merkle root is signed by 2/3 of Idena nodes together with the hash of cryptoidentities registry. The Merkle root has to be provided to the smartcontract.
2. In order to verify KillInviteeTx the proof of relationship between invitee and inviting address has to be provided in form of the Merkle path

[uivlis]

Thanks, clear sailing now! However, would you also please point me to some Idena docs (others than the FAQ on the Idena website)? I'm not sure if there are such docs, but I haven't been able to find info about the data structure of a tx.

[busimus]

There aren't any docs, hardly any comments in the code as well.
Thankfully the code isn't too hard to read, but it takes a bit of time to get familiar with the general layout to know where to look for the things you're interested in. Here's the Transaction struct.

[uivlis]

Got it. Thanks, again!

[uivlis]

Alright, here's another one. I really wanted to go with Solution 2, but isn't it a bit cumbersome for the user to provide the Merkle proof to the contract? I presume he would have to rebuild the entire tree structure (made of all inviters and invitees) in order to get the nodes of the path, perhaps you were thinking of a more streamlined approach?

[henryfour]

In my ongoing implementation, the init() tx of the contract can only be called along with ~100 identities because of the gas limit. It cost about 7433545 to init 100 identities:

Gas used: 7433545, tx: 0xc20c8c700554bf002d621f9430be9bea7cb2148bea83e6957b011fa808a289e9 │
✓ init with 100 identities (1622ms)

So, my implementation of the relay contract need to change to support multi-init() transactions. i.e. Abount 10-20 transactions are needed to init the contract if the epoch have 1000-2000 identities.
Is it acceptable?

I estimate the amount of gas for each new identity when update states is nearly.
But the good news is that the later updates will mainly care about the changed identities.
I will try best to save gas limit (not gas cost), because gas limit is more important to our relay.

[uivlis]

Hey guys, I just finished implementing the Kill and KillInvitee functionality, using Merkle trees (I got my answer to my last question above).

You can check the complete implementation (and tests) of the relay here.

Moving to implement the node changes!

[henryfour]

I have finished the 1st version of the eth-relay contract along with a short description of the solution.
The idena-go node modification is still under developing, and will be open sourced some days later when the basic viable functions are finished.

[uivlis]

Coming back with some gas cost tests for the batched initialization of the relay:

• 100 addresses:
  7826119 gas
• 1000 addresses:
  43508747 gas
• 10000 addresses:
  403343955 gas

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work for 0.001 ETH (0.24 USD @ $236.1/ETH) has been submitted by:

1. @uivlis
2. @henryfour

@midenaio please take a look at the submitted work:

• PR by @henryfour
• PR by @uivlis

---

• Learn more on the Gitcoin Issue Details page
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Chat
• $144,694.30 more funded OSS Work available on the Gitcoin Issue Explorer

[henryfour]

idena node improvement was basically completed, advises and fixes are welcome.
https://github.com/idena-lab/idena-go/tree/eth-relay

[henryfour]

Detailed documentation has been updated.
Also, a sample relay contract for testing has been deployed to the rinkeby testnet, please refer to this document

[henryfour]

The smart contract has been improved to support thousands of identities in both initialization and updating operations. It has been deployed to the rinkeby testnet (0x323ebbe7f8df0560707fdf7b503bab68a6e1b0a3), and initialized with 2468 identities (same as epoch47).
In addition, a state change with 20 identities killed and 120 new identities added has been updated to the relay contract.

Please refer to the main document and deploy document for more information.