Anyone here with math background who can help with Reed-Solomon codes problem?
It's needed for the New Address Format: https://forums.nxtcrypto.org/viewtopic.php?f=17&t=524
Original ricot's idea was to use RS codes to auto-correct typos to get superficial, but cool advantage over bitcoin addresses.
But it seems there is a problem. We know that with parity = 4 the algorithm can reliably detect up to 4 errors or correct up to 2.
What isn't mentioned is that those choices seem to be exclusive. You can either detect 4 errors for sure and get general 1/million collision probability (we use 20-bit redundancy) OR you can try to correct errors.
In almost quantum-physics-style weirdness, if you try to correct errors, you cannot use the previous check anymore!
And error correction fails miserably if there are more than 2 errors: it cannot detect that there are more. So it corrects into an incorrect address and there seems to be no way to verify this.
To put it in layman’s terms: you make more than 2 typos and you will almost certainly lose your money. This is unacceptable.
So can anyone either confirm this behavior or tell me what I am missing?
It's needed for the New Address Format: https://forums.nxtcrypto.org/viewtopic.php?f=17&t=524
Original ricot's idea was to use RS codes to auto-correct typos to get superficial, but cool advantage over bitcoin addresses.
But it seems there is a problem. We know that with parity = 4 the algorithm can reliably detect up to 4 errors or correct up to 2.
What isn't mentioned is that those choices seem to be exclusive. You can either detect 4 errors for sure and get general 1/million collision probability (we use 20-bit redundancy) OR you can try to correct errors.
In almost quantum-physics-style weirdness, if you try to correct errors, you cannot use the previous check anymore!
And error correction fails miserably if there are more than 2 errors: it cannot detect that there are more. So it corrects into an incorrect address and there seems to be no way to verify this.
To put it in layman’s terms: you make more than 2 typos and you will almost certainly lose your money. This is unacceptable.
So can anyone either confirm this behavior or tell me what I am missing?
Not an expert in math but one solution I have seen before to this type of problem is to insert a known pattern into the encoded data before encoding, and then check it after decoding.
if the decoder fails the known pattern will fail to be reproduced and then you can trap the error, to my knowledge if the error correcting capability of reed solomon is exceeded then it will always generate an incorrect result but the probability of it maintaining the check data pattern and only corrupting the real data payload should be low - this would need some testing.
e.g. take account number 3323287590575539129
introduce known check pattern for example a progression 3312322837549055765573981299
encode it
NXT-ABCD etc
if you make a mistake decoding
3312422347549065765573981299
You don't know what the account number should be but your algorithm can expect the check pattern to be correct
hope this helps.
