Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
The Bech32 BIP declares that Bech32 is "based on BCH codes". But if you look at the wikipedia page on BCH codes, you see a lot of mathematical equations, but none of those equations seems to be similar to the code that calculates a bech32 checksum.
Can someone explain what parts of BCH codes that bech32 is based on?
The math in the wikipedia article is primarily concerned with generating a BCH code-- which is something that was done for the design of Bech32 but obviously isn't part of the implementation itself-- and with correcting errors which isn't done with Bech32. The article's section on encoding is blank, which is too bad because that is the one thing that's done in the Bech32 code. Even bech32 validation just works by re-encoding and checking if the new encoding matches.
Bech32 is a BCH code constructed with a characteristic-2 field. This allows its symbols to be an integer number of bit's long (5 in the case of bech32). In this kind of field the numbers are treated as coefficients of a binary polynomial, addition is accomplished via xor, and multiplication is accomplished by shifted xors reduced mod a polynomial. As a result the workings look pretty different from what you'd expect from an algebraic description.
A fancy bech32 decoder that finds the error positions also ends up not looking too much like the algebraic decoder in wikipedia, because bech32 has performance better than guaranteed by the fact that it is a BCH code but to exploit that you must go beyond the plain algebraic decoder. When we designed bech32 we also found a non-BCH cyclic code that had somewhat better error detection-- and would have used the same encode/validation code with different constants-- but preferred to stick with the BCH code since proving a lower bound on its performance is much simpler and there are more options for constructing fancy decoders since BCH codes can be decoded algebraically (as described in Wikipedia).
The implementation in the Bitcoin code of bech32 has an extensive description of the mathematics of it and how the mathematics relates to the implementation.
My understanding is that some research went into picking an optimal generator polynomial for the BCH code and then it was hardcoded into the bech32 standard.
More info in this talk by Pieter Wuille
