Improved algorithm for Koinos Nicknames!

in #koinos5 months ago

ogi_or_twitter_post.png

Last week when I announced that the contract was fixed in order to prevent similar names, some members contacted with me to show me some examples where the algorithm was not working properly, like @fu1 and @fm1... again, I had to take a pen and paper to determine what was wrong with the algorithm and come up with new ideas to improve the design.

I found that the problem with the algorithm to detect similar names is that I was ordering the names alphabetically, and making comparisons with the closest names in the list... which is not enough!

For instance, let's say the contract already has this list o names: @alice, @alimento, @alitas, and @alligator. And then we try to create the new name @aliwe. If we look closely, @alice and @aliwe are very similar, so ideally these 2 words should be compared in order to detect that they are similar. However, the contract was comparing this new word just with @alitas and @alligator, because @aliwe is in the middle of these 2 words if we order them alphabetically. Since @aliwe is very different to these words then it was accepted.

After thinking about it a lot, I found a solution to the problem.

Unique Patterns

This new approach doesn't order the names alphabetically. Instead of that, from each name we extract a list of patterns, and we make sure that these patterns are unique.

Let's come back to the example of @alice. When alice is created, the contract saves this list of patterns: lice, aice, alce, alie, alic. These patterns are the result of removing 1 letter from the original name alice. If we remove the first letter we get "lice". If we remove the second letter we get "aice". Alice without the third letter is "alce". Without the fourth letter is "alie". And without the last one is "alic".

The algorithm consists in verify that these patterns are unique for each name in the contract. For instance, if @aliwe is created, it will be rejected because "alie" is one of its patterns, and this pattern is already saved for alice. Apart from that this verification is done by removing up to 2 letters. For instance, @alicce will be rejected as well because if we remove 2 letters we get again the pattern "alie", which is already taken by alice.

In conclusion, we just have to extract and compare if the patterns already exist. No need to order them alphabetically, or compute the levenshtein distance. Which not only solves the problem we faced with similar names, but also improves the performance of the contract 💪 Koinos Nicknames continues with its mission of SAFE TRANSFERS.

Contract patched

This change represented a complete refactor of the contract. But apart from that, I had to create a plan to rewrite the existing data in the contract in order to apply the new algorithm:

  1. Remove conflicting names.
  2. Rebuild patterns for all names and write them in the state of the contract.
  3. Remove the previous lists dedicated to save the names alphabetically.

I successfully managed to apply the patch. During this process I consumed around 260 MANA! (splitted in several transactions) It's the first time I consume this big amount of mana. As a reference, today a transfer of koin consumes around 0.2 mana. So, this patch consumed the mana of making 1300 koin transfers.

Names removed
As I said, I had to remove some conflicting names after applying the new rules. Sorry for the incovenience. Here is the list of names removed:
@ggg, @bill, @buick, @open, @toys, @free, @burn, @bull, @tim, @mary, @bren, @olga, @taco, @best, @fm1, @kk11, @snoop, @bts, @poe, @koins, @teing, @ford, @maria, @jenny, @lol, @zero, @axa, @bitforex, @cmc, @ordi, @diana, @pop, @nbc, @play, @france, @sha, @jeff, @lily, @star, @xoom, @coingate, @space, @sell, @koinos, @my-wallet, @block, @xin, @may, @miner, @mac.

Transaction - a801bad2

Reminder for Hive Users

I put here some reminder for Hive users (more details in the previous post):

The reception at the moment is very good. Now, we have more than 1000 names in the contract.

We are close to the end in order to give 100% control to Koinos Governance. I hope that with this patch we will have a more robust system. If you detect new bugs please let me know.

Support

Please support this development. There are several ways you can contribute:

Join the JGA Mining Pool (very good APY).
Buy a Kondor NFT
Send a donation in https://koinosbox.com/nicknames
Become a sponsor in https://github.com/sponsors/joticajulian

Sort:  

Please check DM on Mattermost. Thx

@klye due to the new rules your name is not in conflict with @ply anymore. Then I claimed @klye and sent it to you 😎 https://koinosbox.com/nicknames/@klye

THANK YOU!

That is awesome that you remembered me when the shift of rules occurred.

You are the man. Thank you again. Made my morning!

But what is this about?

Nicknames is a name service on Koinos Blockchain (to have human readable accounts). See more details here https://peakd.com/koinos/@jga/nicknames

Thanks for reserving. ❤️

you're welcome. Please install Kondor Wallet and create an account. Then send me your address and I will asign the name to that address.

Left you a comment in MM but we can't claim without Hive Keychain connected as a wallet.

Good point. Right now, the support is only for Koinos Wallets. In the long term it would be possible to support other wallets like Hive Keychain by creating smart contract wallets trained to interact with other protocols.
But for the moment I don't see viable this support in the short term. I will ping you if something like this happens in the future.