reply on: Challenge: encode a permutation via another permutation, with error correction? \ stacker news ~bitcoin

pull down to refresh

0 sats \ 3 replies \ @zuspotirko 7 Dec 2023 \ parent \ on: Challenge: encode a permutation via another permutation, with error correction? bitcoin

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?

With a merkle tree you would transmit the the permutation of objects and in addition to that the tree.

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.

The idea is that the whole data is large and transmitted first. Then the tree is used to find errors. You send the tree root, the recipient acknowledges the tree root. And then answers if his calculated tree root is equal to the senders tree root. If yes, great, the most minimal transmission for checksum verification. If no, then the underlying tree offers a super fast way to find where the error was.

0 sats \ 2 replies \ @VzxPLnHqr OP 7 Dec 2023

Thanks. I understand what you mean now. However, it does not quite capture what I am seeking. I want it to be a single message which is comprised of data (e.g. entropy for a cold wallet, which itself may include some of its own checksums, etc), and I want the whole thing to be represented as a permutation of {1,2,3,4,5...,M}. So what I want is definitions for encode and decode such that:

encode(data) = f
decode(g) = data

where f and g are not equal, but f and g are permutations of {1,2,3,4,...,M}.

Continuing with the cold storage example: the sender "sends" f by putting the cards in the order determined by f and then destroying the underlying original entropy (the secret) since it is now represented by f. Maybe Sender then buries this deck of cards in a hole in the ground or something :-).

Then, some time later, the Receiver (which could be the Sender itself) digs up the deck of cards and writes down their order. Unfortunately the order the cards are now in, for whatever reason, turns out to be g which is not equal to f. In other words, there was an error in the transmission. However, all hope should not be lost.

So, the question is: can we endow f with enough error correction capabilities that even if the receiver receives g, the receiver can still find the underlying original secret data from g?

10k sats \ 1 reply \ @zuspotirko 8 Dec 2023

encode(data) = f decode(g) = data

where f and g are not equal, but f and g are permutations of {1,2,3,4,...,M}.

What this makes me think of as someone specialized in security in CS is "second preimage" from hash functions. Let's do a quick transformation:

decode(g) = data
<=>
encode(decode(g)) = encode(data)
<=>
g = encode(data)
=>
encode(data) = f
encode(data) = g
with f !=g

Functions that fulfill this property are insecure hashfunctions. Especially compressing hashfunction for which two preimages can easily be found (google "second preimage resistance"). I know this doesn't help you directly but maybe ths cryptographic perspective helps you searching

0 sats \ 0 replies \ @VzxPLnHqr OP 8 Dec 2023

Right, that is actually why I am trying to focus more on the error-correction aspect of this. Using a secure hash function for checksum calculation (as in the bip39 spec) helps determine that there is an error but it does not identify where the error is nor help correct it.

Reed-Solomon error correcting codes are more what I am seeking, but it is non-trivial to make those work for permutations.

Anyway, there seems to be less interest/activity in this bounty thread than I was anticipating, so I went ahead and awarded the bounty to you!