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 Hive account@fu1 and Hive account@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!
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 Hive account@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 Hive account@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, Hive account@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:
Remove conflicting names.
Rebuild patterns for all names and write them in the state of the contract.
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.
Add an image, short bio, etc (optional fields) and click register.
In the popup click "advanced".
Tick "use free mana" and set max. mana to 10.
Go down, click check events and send.
Enjoy your name 😎
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:
