# Improved algorithm for Koinos Nicknames!

in #koinos5 months ago

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:

# 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).
Send a donation in https://koinosbox.com/nicknames

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!