Skip to main content
Bitcoin

Return to Answer

added 1 character in body
Source Link
Pieter Wuille
Pieter Wuille
  • 109.7k
  • 9
  • 202
  • 318

PeterPieter Wuille's comment gives a nice summary:

Peter Wuille's comment gives a nice summary:

Pieter Wuille's comment gives a nice summary:

added 1217 characters in body
Source Link
MCCCS
MCCCS
  • 10.2k
  • 5
  • 28
  • 57

Why? Because a zero byte does not cause any if branch to run in the PolyMod function loop. c was zero, and it stays zero.

You can now skip to the bottom to my more clear explanation

would all be correct, which is worse (even though there are length checks...)

In the CreateChecksum function, you'll see that to create a signature, 6 empty five-bits are appended (because it's how BCH works, checksum is set to empty before being calculated). Because PolyMod has nowno knowledge if the zeros are part of the input or the empty checksum, they're treated the same. Therefore you can:

The quirk described in the link given is when those "arbitrary numbers" in step 3 are zeros. The PolyMod requests a payload with 6 zeros appended to be checksummed (and trailing zeros make a difference in this case as c is nonzero), and the checksum should come just after the payload, if we want the checksum to be correct. You can add zeros to the end, and it'll stay correct. Only the XOR-1 thing has to be done.

Alternative explanation without distracting details

Here's how the BCH checksum works and why it's unique:

If you give the PolyMod function a payload and 6 empty bytes (which is the length of the signature) it'll give you a value.

If you serialize this value in the place of the last 6 empty bytes and call the PolyMod function, it'll return zero. Whenever the checksum is correct, it returns zero. You can then discard the last 6 bytes and use the rest while decoding

Consider the PolyMod function's state after the payload and the checksum is processed. It returns zero, which is the value of the c variable (you can look at the code at the top). Same for c0. Since then, as long as v_i equals zero, c will stay zero. Therefore you can append zeros at the end without breaking the checksum. Or the converse, if you have a valid address, you can remove zeros at the end.

Plus some Xor-ing with 1, as I explained in the middle of the post. In Bech32 alphabet, p ^ 1 = q and q ^ 1 = p.

Why? Because a zero byte does not cause any if branch to run in the PolyMod function loop.

would all be correct, which is worse.

In the CreateChecksum function, you'll see that to create a signature, 6 empty five-bits are appended (because it's how BCH works, checksum is set to empty before being calculated). Because PolyMod has now knowledge if the zeros are part of the input or the empty checksum, they're treated the same. Therefore you can:

The quirk described in the link given is when those "arbitrary numbers" in step 3 are zeros. The PolyMod requests a payload with 6 zeros appended to be checksummed, and the checksum should come just after the payload, if we want the checksum to be correct. You can add zeros to the end, and it'll stay correct. Only the XOR-1 thing has to be done.

Why? Because a zero byte does not cause any if branch to run in the PolyMod function loop. c was zero, and it stays zero.

You can now skip to the bottom to my more clear explanation

would all be correct, which is worse (even though there are length checks...)

In the CreateChecksum function, you'll see that to create a signature, 6 empty five-bits are appended (because it's how BCH works, checksum is set to empty before being calculated). Because PolyMod has no knowledge if the zeros are part of the input or the empty checksum, they're treated the same. Therefore you can:

The quirk described in the link given is when those "arbitrary numbers" in step 3 are zeros. The PolyMod requests a payload with 6 zeros appended to be checksummed (and trailing zeros make a difference in this case as c is nonzero), and the checksum should come just after the payload, if we want the checksum to be correct. You can add zeros to the end, and it'll stay correct. Only the XOR-1 thing has to be done.

Alternative explanation without distracting details

Here's how the BCH checksum works and why it's unique:

If you give the PolyMod function a payload and 6 empty bytes (which is the length of the signature) it'll give you a value.

If you serialize this value in the place of the last 6 empty bytes and call the PolyMod function, it'll return zero. Whenever the checksum is correct, it returns zero. You can then discard the last 6 bytes and use the rest while decoding

Consider the PolyMod function's state after the payload and the checksum is processed. It returns zero, which is the value of the c variable (you can look at the code at the top). Same for c0. Since then, as long as v_i equals zero, c will stay zero. Therefore you can append zeros at the end without breaking the checksum. Or the converse, if you have a valid address, you can remove zeros at the end.

Plus some Xor-ing with 1, as I explained in the middle of the post. In Bech32 alphabet, p ^ 1 = q and q ^ 1 = p.

Source Link
MCCCS
MCCCS
  • 10.2k
  • 5
  • 28
  • 57

Peter Wuille's comment gives a nice summary:

basically: take a bech32 string, xor a 1 into the last character, then push or pop as many 'q's as you like, and then xor a 1 into the last character again... should always give you a valid new bech32 string

Checksum code taken from Bitcoin Core is:

uint32_t PolyMod(const data& v)
{
    uint32_t c = 1;
    for (const auto v_i : v) {
        uint8_t c0 = c >> 25;

        c = ((c & 0x1ffffff) << 5) ^ v_i;

        if (c0 & 1)  c ^= 0x3b6a57b2;
        if (c0 & 2)  c ^= 0x26508e6d;
        if (c0 & 4)  c ^= 0x1ea119fa;
        if (c0 & 8)  c ^= 0x3d4233dd;
        if (c0 & 16) c ^= 0x2a1462b3;
    }
    return c;
}

Basically, the checksum function has an internal variable that is modified with every 5-bit character, similar to SHA without padding and different sizes. What you should notice is that it both this and SHA are prone to length extension attacks, which means someone who doesn't know x but knows H(x) can calculate H(x || A), where A is any data sequence and || is the concat operator.

Called from:

data CreateChecksum(const std::string& hrp, const data& values)
{
    data enc = Cat(ExpandHRP(hrp), values);
    enc.resize(enc.size() + 6); // Append 6 zeroes
    uint32_t mod = PolyMod(enc) ^ 1; // Determine what to XOR into those 6 zeroes.
    data ret(6);
    for (size_t i = 0; i < 6; ++i) {
        // Convert the 5-bit groups in mod to checksum values.
        ret[i] = (mod >> (5 * (5 - i))) & 31;
    }
    return ret;
}

In this function, simply the result of PolyMod is serialized, but the checksum's least significant bit is XOR'ed with 1. If you undo that, you can extend the checksum by feeding the PolyMod function (or the Initialize-Update-Finalize version of it) a number of five-bit zeros more, and if you XOR the least significant bit with 1 again, you'll get a valid checksum.

Why? Because a zero byte does not cause any if branch to run in the PolyMod function loop.

The reason XOR-1 was a part of the specification is (from my understanding) was to prevent adding an additional character at the end in a way that the checksum is still correct. Otherwise,

  • ii2134hk2xmat79tqq
  • ii2134hk2xmat79tqqq
  • ii2134hk2xmat79tqqqq

would all be correct, which is worse.

In the CreateChecksum function, you'll see that to create a signature, 6 empty five-bits are appended (because it's how BCH works, checksum is set to empty before being calculated). Because PolyMod has now knowledge if the zeros are part of the input or the empty checksum, they're treated the same. Therefore you can:

  1. Take any Bech32 address as a five-bit byte sequence

  2. Xor the last byte with 1

  3. Append arbitrary numbers

  4. Add 6 empty bytes

  5. Calculate PolyMod result

  6. Xor the last byte with 1

  7. Encode

The quirk described in the link given is when those "arbitrary numbers" in step 3 are zeros. The PolyMod requests a payload with 6 zeros appended to be checksummed, and the checksum should come just after the payload, if we want the checksum to be correct. You can add zeros to the end, and it'll stay correct. Only the XOR-1 thing has to be done.