0 sats \ 5 replies \ @zuspotirko 7 Dec 2023 \ on: Challenge: encode a permutation via another permutation, with error correction? bitcoin
Ngl I find it a little difficult to understand what you even want.
I would suggest to you for the additional transmission a checksum.
It depends on the size of r. And how frequent those packet losses occur is also relevant. At 13 you can easily use Hash({8D,9C,8H,9S,12D,13C,12H,13S...}) at the end. If one package gets lost, the reciever can loop through and try 13 different values at 13 positions - thus calculating if the hash is correct13*13 different times. That's quite doable.
Another more overhead idea would be to build a merkle tree over all positions with hashes. Then you could more easily find the position were the error occured.
Hash(Hash(Hash(8D,9C),Hash(8H,9S)) ,Hash(Hash(12D,13C),Hash(12H,13S))) E.g. if the error here occured in 13S than you would first find out that the whole hash is incorrect, than find Hash(Hash(8D,9C),Hash(8H,9S)) to be correct, then locate the error in Hash(Hash(12D,13C),Hash(12H,13S)) etc. and go down the tree from there. That's a method that's widely used in many protocols in computer science for transmission.
write
preview
0 sats \ 4 replies \ @VzxPLnHqr OP 7 Dec 2023 freebie
Ngl I find it a little difficult to understand what you even want.
Thanks for your answer and for the feedback regarding clarity. I should have given a more explicit example of the type of transmission I am after:

better example / motivation -- cold storage of entropy

Imagine storing the entropy for a cold wallet in the form of a carefully ordered deck of cards. It is not hard to take a number and represent it as a permutation of N objects. This is what a Lehmer code does, but Lehmer codes alone do not get us all the way there from a redundancy/error-correcting standpoint.
Where I get stumped is how to build error correction into the permutation itself so that you can recover the seed entropy even if your permutation (the message) got a little jumbled up. My thought is that there is probably a way to do it by using an even larger collection of M objects where M > N.
a method that's widely used in many protocols in computer science for transmission.
Regarding your specific solution, I am confused. I want the final encoding of the message (e.g. what is actually transmitted) to be in the form of a permutation of objects, nothing else. Does your method do that? I think your merkle tree idea assumes that the receiver somehow already knows/learns the root hash, but that would be outside of the rules.