Use base32 encoding of long hash of public key plus checksum for address

Dear community,

In this email, I would like to propose a new address system for Lisk. This proposal poses a solution for the roadmap objective “Replace address system”.

A full LIP draft is also in preparation and will be posted soon. Currently, some computations for some checksum alternatives are still ongoing. If the alternatives turn out to perform better than the checksum proposed here, this proposal may change slightly. Therefore, the full LIP draft will not be posted before the computation is finalized.

# Summary

The proposed address format uses a 160-bit hash value of the public key using SHAKE256 and a checksum generated by a 32-bit cyclic redundancy check code. To increase the user-friendliness, the address is encoded in a customized base32 format.

With this proposal, the following gets achieved:

···

*

    the “registration process” (performing at least one transaction per
    account to associate a public key to an address) becomes obsolete

  *

    the collision resistance gets significantly increased

  *

    accidentally sending funds to a wrong address becomes almost impossible

# The Address Computation

The address for an account, given by its public key, is generated as follows:

1.

    Compute SHAKE256(pubkey, 160), where pubkey is the public key of the
    account.

2.

    Compute the checksum CRC-32C of the output of step 1.

3.

    Concatenate the output of step 1 and the output of step 2.

4.

    Encode the output of step 4 into a specified base32 format (see
    below for details).

5.

    Add the prefix “lsk” to the output of step 4.

The output of step 5 yields the address for pubkey.

In the following, some details of the five steps above get clarified.

## Step 2: CRC-32C

The checksum used in step 2 is the 32-bit cyclic redundancy check code by Castagnoli. It is defined by the generator polynomial

x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1.

The hexadecimal representation of this polynomial is 0x11edc6f41.

## Step 3: Concatenation

In step 3, the output of step 2 is appended to the right of the output of step 1. The output of step 3 has a length of 192 bits.

## Step 4: Base32

The base32 encoding in step 4 is a customized version of base32. It uses lower case letters and digits. The alphabet consists of the following characters:

abcdefghjkmnopqrstuvwxyz23456789

The characters “i”, “l” (lowercase L), “0” (zero) and “1” are excluded.

### Encoding

First, the input bit string is filled with zeros on the right until the length is a multiple of five. If the length of the input bit string is a multiple of five, no zeros are appended. Then, the bit string is split into substrings of 5 bits and the substrings are processed from left to right. Each substring is mapped to a character from the alphabet set according to the following mapping f, where each 5-bit string is interpreted as an integer:

x

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

f(x)

z

x

v

c

p

m

b

n

3

4

6

5

o

9

7

8

x

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

f(x)

u

y

r

t

k

q

e

w

2

a

d

s

j

h

f

g

In the specific case of step 4 of the address computation, the input string consisting of 192 bits is filled with three zeros on the right. Then, it is split into 39 substrings consisting of 5 bits. Finally, each substring gets converted to a character by the mapping f.

#### Example of Base32 Encoding

Consider the following 192-bit input string in hexadecimal representation:

0x3fa78efe17a9b1ec05450e156d882c88af6ed63766d19c4a

The bit representation (grouped in 5-bit substrings) is as follows:

00111 11110 10011 11000 11101 11111 10000 10111 10101 00110 11000 11110 11000 00001 01010 00101 00001 11000 01010 10110 11011 00010 00001 01100 10001 00010 10111 10110 11101 10101 10001 10111 01100 11011 01000 11001 11000 10010 10

The string gets appended by three zeros from the right to have a length that is a multiple of five:

00111 11110 10011 11000 11101 11111 10000 10111 10101 00110 11000 11110 11000 00001 01010 00101 00001 11000 01010 10110 11011 00010 00001 01100 10001 00010 10111 10110 11101 10101 10001 10111 01100 11011 01000 11001 11000 10010 10000

If each 5-bit substring is interpreted as an integer, the sequence looks a follows:

7 30 19 24 29 31 16 23 21 6 24 30 24 1 10 5 1 24 10 22 27 2 1 12 17 2 23 22 29 21 17 23 12 27 8 25 24 18 16

Mapping each element to an alphabet element by using the function f defined in the above results in the following base32 string:

nft2hguwqb2f2x6mx26esvxoyvwehqywos3a2ru

### Decoding

For decoding, the decoder needs to know the expected bit length n of the output. Each character of the encoded string gets converted to a 5-bit string by the inverse of the mapping f above. The first n bits from the left of the resulting bit string represent the output.

In our specific case, the decoder has to convert 39 characters into a 195-bit string. The first 192 bits from the left represent the output. If the 3 most right bits are not zero, then the input was not valid.

## Example of an Address Computation

In the following, the address for the public key pubkey = 0x0eb0a6d7b862dc35c856c02c47fde3b4f60f2f3571a888b9a8ca7540c6793243

gets computed.

1.

    Let H := SHAKE256( pubkey, 160 ) =
    0x3fa78efe17a9b1ec05450e156d882c88af6ed637.

2.

    Let CS := CRC-32C( H ) = 0x66d19c4a.

3.

    Let HCS be the concatenation of H and CS, i.e. HCS =
    0x3fa78efe17a9b1ec05450e156d882c88af6ed63766d19c4a.

4.

    Let B be the base32 encoding of HCS, i.e. B =
    nft2hguwqb2f2x6mx26esvxoyvwehqywos3a2ru.

5.

    Adding the prefix “lsk” to B yields the address
    lsknft2hguwqb2f2x6mx26esvxoyvwehqywos3a2ru.

# Justification for this Proposal

## The Hashing Step

We choose a hash output length of 160 bits which provides 160-bit resistance against pre-image attacks, and, therefore, 160-bit resistance against brute-force attacks for finding keys for unregistered addresses.

Besides the strong pre-image resistance, this output length also provides sufficient collision resistance, namely 80-bit resistance. Note that collisions do not provide any value to an attacker. Therefore, the hash function does not need to be resistant against brute force attacks for collisions. However, collisions of addresses could result in “accidental” losses of money: If a user creates a new account by creating a key pair and provides the resulting address to another user in order to receive a payment, and the address is already associated to another public key, then the user will never be able to spend the funds send to this address.

## Checksum

Several checksum options were considered. A very common choice in blockchain projects is to use a truncated hash value, where a length of 32 bits is typically used. However, hash functions do not provide any error detection guarantees and are even slower to compute than a CRC checksum.

Some versions of shortened Reed-Solomon codes were investigated. Although some of them provide higher distances, their overall error detection capabilities were worse than the ones of CRC-32C (we conducted a sampling study introducing random errors and checking for detection success). Therefore, Reed-Solomon codes were disregarded.

BCH codes pose another alternative. They are, for example, used in the Bitcoin improvement proposal 173. BCH codes have, however, many free parameters which results in many possible choices. Finding a suitable choice of parameters requires an extensive computational search. Therefore, they were not considered any further except for the BCH code proposed in BIP 173. Some computations are currently ongoing to compare its error detection capabilities to the ones from CRC-32C (false positives rates for number of errors above the distance of the code).

Among the set of cyclic redundancy codes, the search was restricted to codes with a 32-bit checksum. One may argue that using a 32-bit checksum is a suboptimal choice since 3 bits of the base32-encoded address (using 195 bits) are not used for the checksum. In fact, one could use a 35-bit CRC code without increasing the overall length of the base32-encoded address. However, 35-bit CRC codes are not well studied in contrast to 32-bit CRC codes (see, for instance, the research of Philip Koopman). Hence, finding a 35-bit CRC code that outperforms CRC-32C for 160-bit inputs would require significant research. Among the set of 32-bit CRC codes, CRC-32C provided the best properties for our setting.

### Details of CRC-32C

For 160-bit inputs, CRC-32C has the distance d=8 which guarantees error detection for up to 7 bit inversions. Moreover, it provides error detection guarantee for any odd number of bit inversions and 32-bit burst error detection. The probability for not detecting an 8-bit error is ~5*10-10.

When using a base32 encoding, this checksum provides error detection guarantee for one mistyped character because one mistyped character can result in up to 5 bit inversions. Due to the burst error detection guarantee, swapping two adjacent characters of an address is guaranteed to be detected as well.

## Base32 Encoding

### Why Base32?

A base32 encoding is clearly preferable over the decimal or hexadecimal system as it is shorter (~20% shorter than hexadecimal). Base64 or any other encodings using a larger alphabet were excluded due to the usage of special characters that can have disadvantages when double-clicking on an address. Any alphabet size that is not a power of 2 was excluded as well, as it disallows to map consecutive strings of bits to characters of the alphabet. Hence, a single mistyped character in an address using such an alphabet could result in many inverted bits which makes it unsuitable for our checksum choice. Base58 is an example of such an alphabet. Hence, a base32 encoding is the preferred choice.

Although there exist already some versions of base32, for instance RFC 4648 and z-base-32, none of them are satisfactory. Therefore, a custom version is defined in this proposal.

### The Alphabet

The alphabet should not contain mixed case letters to ease the communication, for instance, via phone. Lowercase letters are preferred over uppercase letter as they are easier to read. Using an alphabet size of 32 allows to exclude 4 characters from the set of all lowercase letters and all digits. The characters “1”, “i”, “l” (lowercase L), “0” (zero) and “o” are for many fonts the most ambiguous ones. Restricting the alphabet to lowercase letters makes “o” and “i” less ambiguous than the other ones, which led to the decision in keeping one of the two (“o” is part of the alphabet).

### The Encoding Function

The encoding function which maps each 5-bit string to a character of the alphabet was chosen in the way to have few bit inversions for common errors. Consequently, the number of bit inversions introduced by a several common errors may be smaller than the distance of the checksum code in which case the error detection is guaranteed. The common errors considered are

1.

    mistyping a character by a left or right adjacent character on the
    keyboard, and

2.

    mistyping a character by a similar looking character.

Errors of the first kind were given a priority. The 32-bit Gray code was used to ensure that two elements of the alphabet that are in the same row and adjacent on a QWERTY keyboard differ in exactly one bit. In fact, all possible permutations of the contiguous rows of the QWERTY keyboard consisting of elements from the alphabet, i.e. the rows

23456789 qwertyu op asdfghjk zxcvbnm,

fulfil this condition when their concatenation is mapped to the Gray code. Moreover, using the reversed rows and rotations of the concatenations fulfils the same condition. Hence, all these different orderings were considered, and the one that is the best with respect to the second kind of error was chosen. More precisely, the bit representations of any of the pairs

(b, 6) (g, q) (g, 9) (q, 9) (s, 5) (v, u) (z, 2) (q, p) (r, v)

should differ in at most two bits, and the number of pairs differing in two bits should be as small as possible. The lowest number of pairs differing in two bits is 7. In fact, there are 40 different orderings that fulfil this number. The encoding function f defined above is just a random choice from these 40 possibilities.

With this encoding function, it is guaranteed, for example, that introducing seven errors of the first kind (mistyping by an adjacent character) into an address gets detected. Moreover, it is guaranteed to detect up to three errors of the second kind (mistyping by a similar looking character) incorporated in an address.

Best regards

Andreas

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io

This is a response to https://lists.lisk.io/pipermail/lips_lists.lisk.io/2019-March/000049.html
but I cannot get my email into the thread without hacking my email headers.

···

———————————

Hi Andreas, hi Lisk team, hi community,

great to see a proposal regarding the new Lisk address system.

Here you find my feedback and further suggestions:

1. base32 + checksum + network identifier already exists in a standardized
reusable way. It is called bech32 and I suggest using it rather than
reinventing the wheel.
As a bonus, the error correction algorithm of bech32 brings in stronger
guarantees in terms of typo detection than checksumming.
2. Why introduce yet another hashing algorithm that every Lisk tooling
needs to support in order to derive addresses? All Lisk hashing is SHA256,
why not stick with it? Other LIPs try to migrate towards SHA3, why not use
this? However, this point will be obsolete by the next one.
3. An additional requirement for the migration is that version 1 addresses
need to be derived from version 2 addresses. Otherwise one public key will
lead to two different addresses and Lisk core has no way to merge those
accounts. Thus the following derivation is needed:

  public key --> address version 2 --> address version 1
  
This can be archived in two ways:
(a) cut the first 20 bytes from SHA256(pubkey) and use those as address data,
(b) encode the full 32 bytes of the public key into the address.
Encoding the full public key is done in nano-currency and Substrate/Polkadot
and I did not yet find and argument against doing that in a blockchain where
addresses are reused anyway.

Looking forward to hear from you!

Cheers,
  Simon

Hi Simon,

Thanks for your answer.

About 1: As mentioned in my previous mail, the BCH code used in bech32 is still under consideration. The error detection guarantees are indeed better than the ones for CRC-32C. But the error detection capabilities of CRC-32C for more than 4 typos seem to be better. And in combination with our base32 encoding, we have even better error detection guarantees for some specific error types that are expected to be common. I'll post some updates on it soon.

As some details of bech32 had to be adapted anyway (I would remove, for example, the separator because variable input length is not needed), I don't see a big problem to change also the base32 encoding. Implementation wise, using a different encoding should require little effort. And I see advantages in our base32 encoding.

About 2: It does not really make a difference if we use SHAKE256 or SHA3 with truncating. This is almost equivalent as both use the KECCAK function with (almost) the same parameters (security-wise, they are equivalent). I'd expect that any library implementing SHA3 implements also SHAKE256. Therefore, it does not matter. I personally find it cleaner to use the function that provides the output length as a parameter (SHAKE256). But if SHA3 is preferred for some reasons, it's fine for me.

About 3: You are right that this part was missing in my previous email. But I would say that the statement "version 1 addresses
need to be derived from version 2 addresses" is too strong. In fact, it is only required to derive version 1 addresses
from version 2 addresses for known public keys. And both address versions can be derived from the public key. More precisely, the way to deal with the migration could be as follows:

Once the new address format is used, a node has to know the new address for every account for which a public key is known. For example, a column for the new address format could be added to the mem_accounts table in Lisk Core, and for each entry with a public key, the new address gets computed. Accounts for which the old address is known but not its public key have to be kept.

As long as there exist accounts for which the old address is known but not its public key, the following steps have to be done during the validation of a transaction tx (after the signature of tx got verified and before the account balance of the sender was verified):
1. Let pubKey be the sender’s public key of tx. Compute the address, addr, of pubkey according to the new format.
2. If no account for addr is known, then:
a. Compute the address, old_addr, of pubkey according to the old format.
b. If an account for old_addr is known, associate pubKey and addr to this account.
c. If no account for old_addr is known, then the transaction is invalid.
3. If an account for addr is known but no public key is associated to addr, then:
a. Associate pubKey to addr.
b. Compute the address, old_addr, of pubkey according to the old format.
c. If an account for old_addr is known, add the account balance of old_addr to addr and delete the account for old_addr.

Best regards
Andreas

···

On 11.03.19 09:33, Simon Warta wrote:

This is a response to https://lists.lisk.io/pipermail/lips_lists.lisk.io/2019-March/000049.html
but I cannot get my email into the thread without hacking my email headers.

———————————

Hi Andreas, hi Lisk team, hi community,

great to see a proposal regarding the new Lisk address system.

Here you find my feedback and further suggestions:

1. base32 + checksum + network identifier already exists in a standardized
reusable way. It is called bech32 and I suggest using it rather than
reinventing the wheel.
As a bonus, the error correction algorithm of bech32 brings in stronger
guarantees in terms of typo detection than checksumming.
2. Why introduce yet another hashing algorithm that every Lisk tooling
needs to support in order to derive addresses? All Lisk hashing is SHA256,
why not stick with it? Other LIPs try to migrate towards SHA3, why not use
this? However, this point will be obsolete by the next one.
3. An additional requirement for the migration is that version 1 addresses
need to be derived from version 2 addresses. Otherwise one public key will
lead to two different addresses and Lisk core has no way to merge those
accounts. Thus the following derivation is needed:

public key --> address version 2 --> address version 1
This can be archived in two ways:
(a) cut the first 20 bytes from SHA256(pubkey) and use those as address data,
(b) encode the full 32 bytes of the public key into the address.
Encoding the full public key is done in nano-currency and Substrate/Polkadot
and I did not yet find and argument against doing that in a blockchain where
addresses are reused anyway.

Looking forward to hear from you!

Cheers,
Simon

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io
www.lightcurve.io

Hi Andreas,

this is why point 3 is important (the other points are less relevant and can follow):

Let A be an existing account on the blockchain that received funds only (i.d. no pub key known),
and A_v1 the old format Lisk address of that account.
Assume the blockchain receives a send transaction to B, addressed by B_v2 (the
new format).
Now the blockchain has no way to know if A and B are the same account and
will create two accounts for the same key pair/user.

If we can compute B_v1 from B_v2, a node can instantly merge those accounts without
ever seeing the pubkey.

Best, Simon

Hi Simon,

You are right that in this situation both addresses could belong to the same public key, but it is not recognised at this stage (before a public key is known). But I don't really see a problem in this. Once there will be a transaction originating from one of the two accounts, one has certainty if they belong together or not. If yes, they get merged.

Best regards
Andreas

···

On 12.03.19 09:50, Simon Warta wrote:

Hi Andreas,

this is why point 3 is important (the other points are less relevant and can follow):

Let A be an existing account on the blockchain that received funds only (i.d. no�pub key known),
and A_v1 the old format Lisk address of that account.
Assume the blockchain receives a send transaction to B, addressed by B_v2 (the
new format).
Now the blockchain has no way to know if A and B are the same account and
will create two accounts for the same key pair/user.

If we can compute B_v1 from B_v2, a node can instantly merge those accounts without
ever seeing the pubkey.

Best, Simon

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io
www.lightcurve.io

You are right that in this situation both addresses could belong to the
same public key, but it is not recognised at this stage (before a public
key is known). But I don't really see a problem in this.

Both ways could indeed work. But this is the point where you can choose
between:

(A) A migration nightmare in a dimension that nobody in the industry
ever dared to do with complicated core code, frustrated community
members, struggling partner companies, crazy wallet UI design and most
of all, users of almost 17 thousand accounts who see inconsistent
account balances � for no reason.

(B) An account equality function for the old and new format like

function isSameAccount(
  left: LiskAddressV1 | LiskAddressV2,
  right: LiskAddressV1 | LiskAddressV2
): boolean {
  if (isFormatV2(left) && isFormatV2(right)) {
    return left === right;
  } else {
    return toFormatV1(left) === toFormatV1(right);
  }
}

Best, Simon

Hi Simon,

About the implications you mentioned for option (A):

  • “complicated core code”: I’m not 100%ly sure which part of the proposal you are referring to. Is it (1) the logic for matching old addresses with new addresses, or (2) using a checksum and a base32 encoding?
    If it’s (1), then I don’t see a big difference in the complexity between yours and my proposal. In both proposals, a node has to go through some logic whenever there is a new public key. In your proposal, you don’t have to do step 3b and 3c from above, but these two steps don’t make the code much more complicated.
    If it’s (2), then the added complexity is worth it. Note that we don’t implement super complicated logic on our own. For the CRC-32C checksum, there exists a library. And for the BCH code, there exists already the implementation from bech32, as you were pointing out.

  • “frustrated community members”: That depends very much on the realisation. It’s pretty easy to let a wallet query the account data for the old and then new address for a given public key for the case that both don’t have an associated public key in the blockchain yet. The wallet can then display the merged account data. I see that the UX is slightly worse when using a tool without providing the key pair/passphrase for checking account states (like Lisk Explorer), because the tool cannot merge them. But I would assume that most users prefer to use a wallet where one provides it’s key.

  • “crazy wallet UI design”: Which part of the proposal exactly make the UI design crazy?

  • “17 thousand accounts who see inconsistent account balances”: See my answer for “frustrated community members”.

About the account equality function isSameAccount in option (B): I guess this one won’t be very helpful. At least I don’t see a use case for it. The function toFormatV1 could be useful for the case where somebody wants to convert a new address to an old one when not knowing the public key. But this will never apply for the account holder since the account holder knows the public key.

Cheers
Andreas

Hi Andreas,

my last two mails are both about the feature of bering able to derive v1 addresses from v2 addresses. Let’s call it downgradability (from a v2 address to a v1 address). This requirement needs to be decided before talking about the encoding.

  • “complicated core code” refers to (1) “matching old addresses with new addresses”. The big difference is that with downgradability every incoming transaction (no matter if recipient expressed as v1 or v2) can be assicated with one account in the core database. I.e. no migration step is needed. Without downgradability two recipient addresses (one v1 and one v2) of the same keypair will lead to two different accounts that exist in the node. Those accounts need to be merged at a later point in time and you never get all pairs of accounts merged together, so this migration will never come to and end.
  • You should not take the existence of the pubkey for granted. There are many applications where the pubkey is not always available. Most interaction with the Lisk ecosystem happen outside of the wallet. Some examples are: the explorer, the Testnet faucet, the Mobile Hub for Lisk by Elevate, cash flow analysis.
  • “crazy wallet UI design”: the UI needs to explain the user that they have two distict accounts on the blockchain. Two different addresses with two different balances. Since blockchain node is the single source of truth there is no way of avoiding this explicit distiction. Even if you can access both accounts with the same keypair, it is two distict accounts until merged. This two account logic must be present in every Lisk wallet for the rest of the blockchain’s life since you can never guarantee that all user’s accounts are merged on-chain.

The isSameAccount can be used by the core to associate incoming transactions with an account in the database. It can also be used for querying an account state via the API no matter if the old or the new address format is given. It can be used by the faucet to determine if an account already received funds.

Best, Simon

Hi Simon,

Ok, I agree that for the users that did not register their account and received balance transfers to the old and the new address it could be too confusing. I don’t know for how many accounts that will apply (I fear that most of the 17k unregistered accounts will never be used again), but you are right that we should use the available options to avoid potential UX issues for these users if there are no big drawbacks. Also, this makes the registration step obsolete for these specific accounts (accounts that received balance transfers to the old AND the new address), which my proposal didn’t. I will adapt the proposal to use SHA-256 truncated to 160 bits. Thanks for stressing this point.

I would prefer to have a consistent usage of a new address format in the future and to not allow to send to the old addresses anymore.

About the checksum:
The error detection capabilities of the BCH code from bech32 for arbitrary errors are 4 times worse than for CRC-32C. But this is expected due to 2 bits less for the checksum. The much better error detection guarantees for few errors (BCH guarantees detection of 4 errors and CRC-32C only one error in base32 encoding) should, however, be valued more than the overall detection capabilities. Moreover, the overall length of the address decreases by one character when using the BCH code. Therefore, I will change the proposal also in this regard.
There is however one modification I would like to do: If the input sequence of 5-bit integers gets appended by some zeros to the left, then bech32 yields different checksums. I.e., the two input sequences
[5, 21, 31] and [0, 0, 5, 21, 31]
yield different checksum in bech32. Since we have fixed input length (160 bits, or a sequence of 5-bit integers of length 32), this property is rather error prone and I’ll remove it.

Andreas

Hi Andreas,

Very good, you’re welcome

I’d also prefer that but I don’t think it is realistic. There should be a window for migrating existing thirt party software at least.

[5, 21, 31] and [0, 0, 5, 21, 31] are different byte arrays and must lead to different checksum in any sensible algorithm. There is no point in adding an additional data normalization step at this abstraction layer.

address = network identifier + data + checksum and each of those incrediants should be checked one by one. When data.length != 20 the address is invalid, no matter what the checksum is.

Cheers, Simon

We could think about such a transition phase. But what would be the exact purpose? Is it to allow the creation of valid balance transfer transaction without adopting the new format, or for something else?
I’m afraid that the implementation of software that needs to be able to validate balance transfer transactions will be slightly more complicated if we allow both address formats at the same time. But the added complexity might be acceptable.

Consider the 160-bit hash value 0x079b88baa787e83b5a06bbfee95002ac5a9925de. The 5 most left bits are zero. So, it gets converted to the following sequence of 5-bit integers:
S = [0 30 13 24 17 14 21 7 16 31 20 3 22 22 16 6 23 15 31 14 18 20 0 2 21 17 13 9 18 9 14 30]
Then, this sequence defines a polynomial with coefficients over the finite field with 32 elements, i.e. the polynomial

0x^{31} + 30x^{30} + 13x^{29} + ... + 9x^2 + 14x + 30,

and it is used to compute the checksum (multiplying by x^6 and dividing by the generator polynomial). At this point, I see the risk that some implementations may use the sequence
S’ = [30 13 24 17 14 21 7 16 31 20 3 22 22 16 6 23 15 31 14 18 20 0 2 21 17 13 9 18 9 14 30]
for the checksum computation as it defines formally the same polynomial (one may also arrive at this sequence due to other pitfalls). The total length of the address is still the same if the leading zero is not ignored when converting into base32. Just the checksum value could be different, depending on the way we chose.

You are right that for general purpose checksum, one should have different checksums for S and S’. Also for bech32, where variable input lengths are used, it makes sense. But in our case, I see no advantage in computing different checksums for S and S’ and there is a small risk for pitfalls. Hence, I see a small advantage.

We found an issue with the “downgrade-ability”, i.e., the ability to derive the current address format from the new one:
Let old_addr be an address in the current format for which no public is known but that has some funds. Although we do not know the public key, we can compute the first 8 bytes of the SHA-256 hash of the public key from old_addr. If we append 24 arbitrary bytes to these 8 bytes and treat the resulting 32 bytes as a hash value used for the computation of the new address, then we get an address, new_addr, from which one would derive old_addr. If one sends a balance transfer transaction to new_addr, all nodes would associate new_addr to old_addr, but the account holder of old_addr does not posses a key pair that yields old_addr and new_addr. Hence, the account holder of old_addr were not able to spend the funds anymore.

So, nodes should not associate old addresses to new addresses if no common public is known.

3 Likes

I agree, this is a very valid point I was not aware of. Good job!

Even encoding the full 32 bytes pubkey into the address would not help since it is easy to bruteforce a random 32 byte input p with sha256(p).slice(0, 8) === old_addr. In order to merge, you need to ensure that

  1. there is a public key to derives to the old address,
  2. the owner of the old address has a private key for that public key.

Then this migration is going to be a horrible mess when it comes to development and user experience (for all the reasons I stated above).

We have an updated and finally complete version of the LIP. We made, however, two changes:

  • We removed the modification of the BCH code (see here), as already requested by @Simon_Warta. The main reason to do so is to be compatible with the checksum implementation of bech32 which kind of widely used and exists in several languages. Note, however, that only the checksum is compatible with bech32. The base32 encoding is still different.
  • The merging of account data of old addresses and new addresses for the case that the old address was never “registered” will not be done automatically. Instead, the user has to issue an explicit transaction, which we call reclaim transaction. Note that this holds only for accounts that never had an outgoing transaction before this change is implemented. The reason to do so is the SDK: this way, it much easier to extract the logic related to the current address system into custom logic for Lisk Core for the main chain and the SDK does eventually not need to implement the old address system.

The LIP follows in the next post.

LIP: <LIP number>
Title: Use base32 encoding of long hash of pubkey plus checksum for address
Author: Andrea Kendziorra <andreas.kendziorra@lightcurve.io>
Discussions-To: https://research.lisk.io/t/use-base32-encoding-of-long-hash-of-public-key-plus-checksum-for-address/
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>

Abstract

This LIP proposes a new format for addresses (also referred to as Lisk ID) to replace the current format in the Lisk protocol. The proposed address format uses 160 bits of the SHA-256 hash of the public key and a 30-bit checksum generated by the BCH code proposed in BIP 173. To increase the user-friendliness, the address is encoded in a customized base32 format.

The new address format makes the “registration process” (performing at least one transaction per account to associate a public key to an address) obsolete. Moreover, the collision resistance gets significantly increased, and accidentally sending funds to a wrong address becomes almost impossible due to the checksum.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

The current address system was designed with the aim to be convenient for users when reading, typing, inserting or communicating an address. This was done by choosing a short length. In fact, the addresses are generated by taking the first 64 bits of the SHA-256 hash of the public key (plus a few small modifications). Despite the advantages, the address system has at least three significant shortcomings. First, an account holder is currently strongly advised to perform at least one transaction from an account to associate a public key with the address. Otherwise, an adversary could find another key pair that yields the same address and use this one to spend funds from this account.

Secondly, the addresses do not have a checksum or any other error detection mechanism. Hence, mistyping a single character of the address for a balance transaction results in sending funds to a different account (with very high probability, no user has a corresponding key pair for this account).

The third disadvantage is the low resistance against collisions of addresses. If the number of created Lisk accounts will rise significantly in the future, the probability for a collision could become non-negligible.

Therefore, a new address system is proposed that eliminates the mentioned issues. The first and the third issue get resolved by using a 160-bit hash of the public key. The second one by using a checksum. Since the overall bit length of the hash value plus checksum is rather large, a base32 encoding is used. This results in shorter addresses than in hexadecimal representation while still being human-friendly.

Specification

Address Computation

The address for an account, given by its public key, is generated as follows:

  1. Compute SHA-256(pubkey), where pubkey is the public key of the account, and truncate the output to its first 160 bits.
  2. Compute the checksum of the output of step 1 using the BCH code described below.
  3. Concatenate the output of step 1 and the output of step 2.
  4. Encode the output of step 3 into a specified base32 format (see below for details).
  5. Add the prefix “lsk” to the output of step 4.

The output of step 5 is the address for the given account. An example of an address computation can be found in the appendix. In the following subsections, some details of the steps above get clarified.

Step 2: BCH checksum

The checksum is computed using the BCH code proposed in BIP 173. In this section, we only provide example Javascript code that computes and validates the checksum correctly (based on the code from bech32). For a more formal description, see the appendix.

Creating checksum

The checksum can be computed by the function createChecksum below. For this, the output of step 1 has to be split into 5-bit strings, and each bit string has to be converted into an integer. Hence, the input for createChecksum is a list of 32 integers between 0 and 31. The output of createChecksum is a sequence of 6 integers between 0 and 31, where each integer represents a 5-bit string. Thus, the checksum consists of 30 bits.

function polymod (values) {
  var GENERATOR = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3];
  var chk = 1;
  for (var p = 0; p < values.length; ++p) {
    var top = chk >> 25;
    chk = (chk & 0x1ffffff) << 5 ^ values[p];
    for (var i = 0; i < 5; ++i) {
      if ((top >> i) & 1) {
        chk ^= GENERATOR[i];
      }
    }
  }
  return chk;
}

function createChecksum (data) {
  var values = data.concat([0, 0, 0, 0, 0, 0]);
  var mod = polymod(values) ^ 1;
  var ret = [];
  for (var p = 0; p < 6; ++p) {
    ret.push((mod >> 5 * (5 - p)) & 31);
  }
  return ret;
}
Validating checksum

To verify if a code word has a correct checksum, the function verifyChecksum below can be used.

function verifyChecksum (codeword) {
  return polymod(codeword) === 1;
}

As for the checksum creation, the input for verifyChecksummust be a sequence of integers between 0 and 31. The 6 most right integers of the codeword represent the checksum.

Step 3: Concatenation

The output of step 1 is a 160-bit string, and the output of step 2 a 30-bit string. In step 3, the output of step 2 is appended to the right of the output of step 1. The output of step 3 has a length of 190 bits.

Step 4: Base32

The base32 encoding in step 4 is a customized version of base32. It uses lower case letters and digits. The alphabet consists of the following characters:

abcdefghjkmnopqrstuvwxyz23456789

The characters “i”, “l” (lowercase L), “0” (zero) and “1” are excluded.

In the following subsections, the encoding and decoding for bit lengths that are multiples of 5 are described. Note that the encoding and decoding could easily be extended to arbitrary bit lengths.

Encoding

First, the bit string is split into substrings of 5 bits and the substrings are processed from left to right. Each substring is mapped to a character from the alphabet set according to the following mapping f, where each 5-bit string is interpreted as an integer:

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(x) z x v c p m b n 3 4 6 5 o 9 7 8
x 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
f(x) u y r t k q e w 2 a d s j h f g

In the case of step 4 of the address computation, the input string consisting of 190 bits is split into 38 substrings consisting of 5 bits, and each substring gets converted to a character by the mapping f .

Decoding

Each character of the encoded string gets converted to a 5-bit string by the inverse of the mapping f above. The resulting bit string represents the output. In our specific case, the decoder has to convert 38 characters into a sequence of 38 integers between 0 and 31.

Step 5: Prefix

The output of step 4 is a string of length 38. It is appended by the prefix “lsk” from the left, yielding a string of length 41.

Usage of the Addresses in the Protocol

Addresses have to be used for the recipientID property of balance transactions. Further usages are optional.

Address Format Validation

The following steps have to be done to validate if a given address addr satisfies the proposed address format. Note that these steps validate only the format. It does not guarantee that any user or even a specific user is in possession of a key pair that corresponds to this address. The validation consists of:

  1. Verify that addr is a string of length 41.
  2. Verify that the substring of the first 3 characters of addr equals “lsk”.
  3. Let substr be the substring of the last 38 characters of addr. Verify that every character in substr is an element of the used base32 alphabet. Uppercase letters are not allowed.
  4. Decode substr into sequence of 38 integers between 0 and 31, denoted by intseq, by using the inverse of the mapping f above. Verify that verifyChecksum(intseq) returns True.

If any of these validation steps fails, then the address does not have a valid format.

Address Format Validation in Transaction Validation

When a transaction object contains an address, the address format has to be validated during the transaction validation. If the format validation fails, the transaction has to be rejected. The procedure described above can be used for the format validation. Of course, a node may also keep track of all validated addresses and may validate the format of an address by a lookup.

Address Format Validation in User Interfaces

This subsection does not contain rules for the protocol, but recommendations for the design of user interfaces to make use of all capabilities of the new address format. The recommendations are:

  • When entering an address into an input field, letters should be automatically converted to lowercase letters.
  • Before sending out a transaction that contains an address data field, the address format should be verified. If the validation fails, the transaction should not be sent out.

Serialization

Whenever an address value has to be serialized, the 20 bytes of the public key hash are taken, i.e. the bytes which are used as the input for the checksum computation. This applies for the serialization of the recipientID property of balance transfer transaction and for any other property of a transaction (or block) that contains and address.

Converting Existing Accounts

We distinguish between accounts with and without associated public key. Note that an account has an associated key if and only if an outgoing transaction from this account is included in the blockchain.

Accounts with Public Key

For accounts with an associated public key, the new address has to be computed and stored such that the account is accessible via the new address.

Accounts without Public Key

Funds that were sent to an address of the current format and for which no public key was associated before the implementation of the new address system are not automatically accessible. To make them accessible, a special transaction, called reclaim transaction, has to be included in the blockchain. The set of addresses of the current format without associated public key and for which no reclaim transaction was included in the blockchain have to be persisted along with their balances. In the following, we denote this set of addresses by unregisteredAddresses.

Reclaim Transaction
Type

The type of the reclaim transaction is the lowest positive integer that is not used for any other transaction type on the Lisk blockchain (8 at the time of writing).

Schema

The asset property of a reclaim transaction needs to contain the amount property which is of type string. The value of asset.amount must represent a decimal number and this number must be equal to the balance associated to the address of the current format in Beddows.

A reclaim transaction is of the following form:

{
  "type": <type>, // at the time of writing, the value must be 8
  "senderPublicKey": <Public key of the sender>,
  ...
  "asset" : {
    "amount" : <amount in Beddows>
  }
}
Validity

A reclaim transaction, tx, must fulfil the following points to be valid:

  • Let old_addr be the address according to the old format for tx.senderPublicKey. Then, old_addr must be contained in unregisteredAddresses.
  • Let old_balance be the sum of all funds send to old_addr in Beddows. Then tx.asset must contain the property amount, and the number represented by tx.asset.amount must be equal to old_balance.
  • Let new_addr be the address of the new format for tx.senderPublicKey and let new_balance be the balance of new_addr. If there exists no account for new_addr, then new_balance is 0. Then tx.fee must be smaller or equal than old_balance + new_balance.
State Changes

We use the same notation as in the Validity section. If the transaction tx is included in the blockchain, the following state changes apply:

  • old_addr is removed from unregisteredAddresses.
  • If no account for new_addr exists, the account is created.
  • If no public key is associated to new_addr, the public key tx.senderPublicKey is associated to new_addr.
  • The balance for new_addr is set to old_balance + new_balance - tx.fee.
Serialization

The asset property of a reclaim transaction tx needs to be serialized to an array of 8 bytes containing the big endian encoding of tx.asset.amount interpreted as a 64-bit signed integer.

Rationale

Hashing Step

To keep the length of the addresses at a reasonable level, a hash of the public key with a length smaller than 256 bits is used instead of the public key itself. When choosing the hash length, one crucial requirement has to be kept in mind: For a given address, it should be computationally infeasible to find a key pair (public key and private key) that yields this address. This requirement prevents that an attacker can find a key pair for an address for which no public key is yet associated to (a public key gets associated to an address the first time a transaction outgoing from this account is included in a block). If an attacker were able to find such a key pair, they could transfer the funds from this account. In the current Lisk protocol, it is computationally very expensive to find a key pair for a given address, but it is not infeasible. For an account with no associated public key, such an attack may be economically profitable if there are enough funds in the account. Therefore, it is currently recommended to do at least one transaction per account such that the address is associated to the account holder’s public key. This process is sometimes referred to as the “address registration” process. However, the address registration process is an additional step required from the user, and it is highly desired to make it obsolete.

The length of the hash output determines the resistance against the mentioned attack. Although a security level of 128 bits is considered to be sufficient for the next years (see the security recommendations from ECRYPT [1, Chapter 2] and NIST [2, Section 5.6.2]), we choose a hash output length of 160 bits which provides 160-bit resistance against such attacks. Besides the strong pre-image resistance, this output length also provides sufficient collision resistance, namely 80-bit resistance. Note that collisions do not provide any value to an attacker. Therefore, the hash function does not need to be resistant against brute force attacks for collisions. However, collisions of addresses could result in “accidental” losses of money: If a user creates a new account by creating a key pair and provides the resulting address to another user in order to receive a payment, and the address is already associated to another public key, then the user will never be able to spend the funds send to this address. Only the key pair associated with the address can be used to spend the funds. With the chosen hash length, the probability for an address collision becomes negligible, even for very large numbers of addresses. For example, the probability of having an address collision after 1015 addresses is smaller than 10-18.

Why SHA-256?

SHA-256 is the currently used hash function in the Lisk protocol. To keep the protocol simple, we propose to not introduce a new hash function and to use SHA-256 here as well.

Checksum

Several checksum options were considered and are discussed in the following.

Hash Functions

A very common choice in blockchain projects is to use a truncated hash value, where a length of 32 bits is typically used. However, hash functions do not provide any error detection guarantees and were discarded for this reason.

Reed-Solomon Codes

Some versions of shortened Reed-Solomon codes were investigated.

The first one uses the alphabet size 32, which is very suitable for using a base32 encoding. That means, each character of an address (represented by 5 bits) corresponds to one symbol of a codeword. Since a Reed-Solomon code with alphabet size q allows only a maximum block length of q-1, the maximum block length for q=32 is 31. Hence, a codeword would consist of maximum 31*5 = 165 bits. Since this is too short for a 160-bit input plus an adequate checksum, the input has to be split into parts which results in two checksums. More precisely, the input (the 160-bit hash value) is split into two inputs of 80 bits, and both inputs are encoded with a [31, 28, 4]32 Reed-Solomon code, where the output is shortened. Hence, there is a 3 symbol (15 bits) checksum for each input. The distance of the code, d=4, guarantees error detection for up to 3 errors in the address, which is less than for the chosen BCH code. Moreover, the error detection capabilities are very poor for more than 3 errors. For example, the false positive rate (false positive means to not detect errors) for 4 errors in an address is ~3*10-6.

The second considered Reed-Solomon code is the one with the parameters [1023, 1020, 3]1024. The checksum consists of 3 symbols with 10 bits each. One symbol of a codeword always represents 2 characters in the base32-encoded address. The distance of the code, d=4, guarantees detection of up to 3 errors in the base32-encoded address. This is again worse than for the chose BCH code. Moreover, the error detection capabilities for more errors are worse than the ones for the BCH code.

Other alphabet size were disregarded due to the worse error detection guarantees in the base32 encoding (unless one uses more than 32 bits for the checksum).

Cyclic Redundancy Check Codes

Several cyclic redundancy check (CRC) codes were considered, mainly 32-bit CRCs. The best performing CRC code is the one by Castagnoli (also referred to as CRC-32/4 in [3]). It’s error detection capabilities for more than 4 errors in the base32-encoded addresses are better than for the chosen BCH code. However, the error detection guarantee is worse. The code guarantees detection of up to 7 bit inversions which results in an error detection guarantee of up to one character in base32 encoding. Moreover, the overall length of the address increases by one with a 32-bit checksum. Therefore, this CRC code was not selected.

BCH Codes

BCH codes have many free parameters which results in many possible choices. Finding a suitable choice of parameters requires an extensive computational search. We simply use the result presented in BIP 173 without performing the search ourselves. This code is well suited for a base32 encoding. It provides detection guarantee of up to 4 characters in base32 encoding for the input length of 38 characters, has good error detection capabilities for more than 4 errors and is relatively efficient. Moreover, the authors of BIP 173 claim that it was optimized for detecting low numbers of bit inversions which fits well together with the base32 encoding proposed here (see
below for the reasoning of the specific encoding function).

Base32 Encoding

Why Base32?

A base32 encoding is clearly preferable over the decimal or hexadecimal system as it is shorter (~20% shorter than hexadecimal). Base64 or any other encodings using a larger alphabet were excluded due to the usage of special characters that can have disadvantages when double-clicking on an address. Any alphabet size that is not a power of 2 was excluded as well, as it disallows to map consecutive strings of bits to characters of the alphabet. Hence, a single mistyped character in an address using such an alphabet could result in many inverted bits which makes it unsuitable for our checksum choice. Base58 is an example of such an alphabet. Hence, a base32 encoding is the preferred choice.

Although there exist already some versions of base32, for instance RFC 4648 and z-base-32, none of them are satisfactory. This is in most cases due to the selection of the alphabet. The base32 encoding that matches our requirements the most (but not sufficiently) is the one proposed in BIP 173. Due to the unsatisfactory design of the existing base32 versions, a custom version is defined in this protocol.

The Alphabet

The alphabet should not contain mixed case letters to ease the communication, for instance, via phone. Lowercase letters are preferred over uppercase letter as they are easier to read. Using an alphabet size of 32 allows to exclude 4 characters from the set of all lowercase letters and all digits. The characters “1”, “i”, “l” (lowercase L), “0” (zero) and “o” are for many fonts the most ambiguous ones. Restricting the alphabet to lowercase letters makes “o” and “i” less ambiguous than the other ones, which led to the decision in keeping one of the two (“o” is part of the alphabet).

The Encoding Function

The encoding function which maps each 5-bit string to a character of the alphabet was chosen in the way to have few bit inversions for some error types that are expected to be common. As the checksum is optimized for detecting low numbers of bit inversions, the probability of detecting more than 4 errors of these types increases. The types of error considered are

  1. mistyping a character by a left or right adjacent character on the keyboard, and
  2. mistyping a character by a similar looking character.

Errors of the first kind were given a priority. The 32-bit Gray code was used to ensure that two elements of the alphabet that are in the same row and adjacent on a QWERTY keyboard differ in exactly one bit. In fact, all possible permutations of the contiguous rows of the QWERTY keyboard consisting of elements from the alphabet, i.e. the rows

23456789, qwertyu, op, asdfghjk, zxcvbnm

fulfil this condition when their concatenation is mapped to the Gray code. Moreover, using the reversed rows and rotations of the concatenations fulfils the same condition. Hence, all these different orderings were considered, and the one that is the best with respect to the second kind of error was chosen. More precisely, the bit representations of any of the pairs

(b, 6), (g, q), (g, 9), (q, 9), (s, 5), (v, u), (z, 2), (q, p), (r, v)

should differ in at most two bits, and the number of pairs differing in two bits should be as small as possible. The lowest number of pairs differing in two bits is 7. In fact, there are 40 different orderings that fulfil this number. The encoding function f defined in the
specification is just a random choice from these 40 possibilities.

Prefix

A prefix is added to the address to minimize the risk that a Lisk address gets confused with an address of another blockchain project. This can be helpful, for instance, when users use applications/clients that handle several cryptocurrencies including Lisk.

Converting Existing Accounts

The usage of a reclaim transaction for accessing funds send to “unregistered” addresses was preferred over solutions that automatically merge account information of old and new addresses (e.g., as in this post) for the following architectural reason: It allows that the SDK does eventually not need to implement the current address format. In contrast, an automatic merge solution that is part of the transaction verification is hard to extract from general transaction verification logic, and therefore hard to remove from the SDK. Moreover, an automatic merge solution requires additional computational steps whenever a transaction contains a public key that was not contained in the database before.

Amount Property in Reclaim Transactions

One may argue that the amount property of a reclaim transaction is not required to process the transaction. This is true. However, the undo step in case of reverting a block would be very expensive because one could not easily distinguish between the following two cases:

  1. The account received balance transfers only to the old address.
  2. The account received balance transfers to the old and the new address.

Backwards Compatibility

This change introduces a hard fork because

  • balance transactions using the current address format get rejected by nodes following the proposed rules, and vice versa, and
  • reclaim transactions get rejected by nodes following the current protocol.

References

[1] M. Abdalla et. al, “Algorithms, Key Size and Protocols Report (2018)”, ECRYPT-CSA, Feb. 2018, http://www.ecrypt.eu.org/csa/documents/D5.4-FinalAlgKeySizeProt.pdf

[2] E. Barker, “Recommendation for key management”, NIST Special Publication 800-57 Part 1 Rev. 4, Jan. 2016, https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf

[3] G. Castagnoli, S. Brauer, M. Herrmann, “Optimization of cyclic redundancy-check codes with 24 and 32 parity bits”, IEEE Transactions on Communications, Vol. 41 (6), pp. 883 - 892, Jun. 1993

Appendix

Examples

Address Computation

In the following, the address for the public key

pubkey = 0x0eb0a6d7b862dc35c856c02c47fde3b4f60f2f3571a888b9a8ca7540c6793243

gets computed.

  1. Let
H' = SHA-256(pubkey) = 0xc247a42e09e6aafd818821f75b2f5b0de47c8235b580881bd7750c9365993d25

and let Hbe the first 160 bits of H', i.e.,

H = 0xc247a42e09e6aafd818821f75b2f5b0de47c8235.

The representation of H as a sequence of 5-bit integers is

H_5bit = [24 9 3 26 8 11 16 9 28 26 21 15 27 0 12 8 4 7 27 21 22 11 26 27 1 23 18 7 25 0 17 21].
  1. Let CS be the checksum of H, i.e.,
CS = createChecksum(H_5bit) = [21 21 31 11 22 16].
  1. Let HCS be the concatenation of H and CS in 5-bit representation, i.e.
HCS = [24 9 3 26 8 11 16 9 28 26 21 15 27 0 12 8 4 7 27 21 22 11 26 27 1 23 18 7 25 0 17 21 21 21 31 11 22 16]
  1. Let B be the base32 encoding of HCS, i.e.
B = 24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu.
  1. Adding the prefix “lsk” to B yields the address
lsk24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu.

Valid Addresses

We list some example addresses for a given public key. Note that the provided public keys are not necessarily valid public keys (curve points for which there exists a private key).

pubkey  = 0x0000000000000000000000000000000000000000000000000000000000000000
address = lskoaknq582o6fw7sp82bm2hnj7pzp47mpmbmux2g

pubkey  = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
address = lskqf5xbhu874yqg89k449zk2fctj46fona9bafgr

pubkey  = 0x00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
address = lskamc9kfzenupkgexyxsf4qz9fv8mo9432of9p5j

pubkey  = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00
address = lsk6xevdsz3dpqfsx2u6mg3jx9zk8xqdozvn7x5ur

pubkey  = 0x749b88baa787e83b5a06bbfee95002ac5a9925dcaeea28262e683498147b8fce
address = lskxwnb4ubt93gz49w3of855yy9uzntddyndahm6s

pubkey  = 0xe877c250d725ac7ca6c5d9d83b39645de7eebe6c4ae6e076da7163434d297c7d
address = lskzkfw7ofgp3uusknbetemrey4aeatgf2ntbhcds

Invalid Addresses

In the following, we list some invalid addresses and for each address at least one reason for the invalidity.

24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu      # missing prefix

lsk24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5e    # incorrect length (length 40 instead of 41)

lsk24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5euu  # incorrect length (length 42 instead of 41)

LSK24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu   # incorrect prefix

tsk24cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu   # incorrect prefix

lsk24cd35u4jdq8sz03pnsqe5dsxwrnazyqqqg5eu   # invalid character (contains a zero)

lsk24Cd35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu   # invalid character (contains an upper case 'C' instead of lower case 'c')

LSK24CD35U4JDQ8SZO3PNSQE5DSXWRNAZYQQQG5EU   # invalid characters (all letters in upper case)

lsk24dc35u4jdq8szo3pnsqe5dsxwrnazyqqqg5eu   # invalid checksum due to character swap

Formal Description of the BCH Code

The specification section provides example code for creating and validating the checksum, but not a formal description. This shall be done here (see also the documentation of the Bitcoin implementation of bech32 for some details; for example, the representation of the generator polynomial as an array of 32 bit numbers is explained there) .

Let F32 be the finite field with 32 elements. We use the representation F2[x]/(x5+x3+1) for F32, i.e., every element in F32 is interpreted as a polynomial with coefficients in F2 modulo x5+x3+1. Each polynomial is identified by the decimal number whose bit representation matches with the polynomial. For example, the decimal number 23 represents the polynomial x4+x2+x+1 because the bit representation of 23 equals 10111. Let g(x) be the polynomial with coefficients in F32 of the following form:

g(x) = x6 + 29x5 + 22x4 + 20x3 + 21x2 + 29x + 18.

g(x) is the generator polynomial of the BCH code. Every input for the checksum is interpreted as a polynomial with coefficients in F32 too. For example, the input

d = 0xc247a42e09e6aafd818821f75b2f5b0de47c8235

is interpreted as the polynomial

d(x) = 24x31 + 9x30 + 3x29 + … + 25x3 + 0x2 + 17x + 21

where each coefficient represents 5 bits of d (see the
example above for all coefficients). To achieve that a codeword can be represented as the concatenation of the input and the checksum, systematic encoding is used. In this specific case, the checksum polynomial, chk(x), can be computed by

chk(x) = - (d(x) * x6 mod g(x))

for an input polynomial d(x). Then, the whole codeword, represented as a polynomial c(x), has the form

c(x) = d(x) * x6 + chk(x).

A polynomial p(x) with coefficients in F32 is then a valid codeword if and only if

0 = p(x) mod g(x)

holds. However, two more tweaks were used for the design of the bech32 checksum. Both are discussed in the following subsections.

Adding a Leading Term to the Input Polynomial

A leading term is added to the input polynomial in bech32. More precisely, if k is the length of the input sequence of 5-bit integers, then let

d’(x) = xk + d(x).

The polynomial d’(x) is then used for the checksum computation instead of d(x). This ensures that the checksum differs if some zeros are added to the left of the input sequence of 5-bit integers. E.g., the inputs

[5, 21, 31] and [0, 0, 5, 21, 31]

yield different checksums in bech32. Here, this property is not needed due the fixed length input, but was kept to be compatible with bech32. Since the input sequence has always length 32, we always have

d’(x) = x32 + d(x)

in our case.

Codewords Are not Multiples of Generator Polynomial

The second tweak is to add 1 to d’(x) * x6 when computing the checksum, i.e., the checksum is computed as

chk’(x) = - (d’(x) * x6 + 1 mod g(x)).

Then, a polynomial p(x) with coefficients in F32 is a valid codeword if and only if

-1 = p(x) mod g(x)

holds (note that 1=-1 holds in F32). This avoids that appending some zeros to the right of a codeword yields again a valid codeword. If the checksum were computed by

chk(x) = - (d(x) * x6 mod g(x)),

then appending n zeros to the right of a valid codeword would yield again a valid codeword. This is because

0 = c(x) mod g(x)   implies   0 = c(x) * xn mod g(x).

This property is not strictly required for this proposal due to the fixed length of codewords, but was kept to be compatible with bech32.

Notes

[]:
Note that this list of pairs of similar looking characters is based on subjective perception since no scientific result is known to the author.

Nice update!

There is one thing I still don’t understand. In

The base32 encoding that matches our requirements the most (but not sufficiently) is the one proposed in BIP 173.

you speak of requirements not being met. What are those requirements? Did those requirements exist before the custom solution? Are those requirements worth sacrificing compatibility with dozens of external software components? There are even C libraries for the Ledger that give you bech32 for free.

At IOV we integrate Lisk and could just do Bech32.encode("lsk", sha256(pubkey).slice(0,20)) and everyone is happy. But for the sake of changing 2 characters and the alphabet and saving a 1 character you really want to be incompatible?

Also having a configurable prefix can be handy to differentiate mainnet and testnet addresses.

The requirements are mentioned in the subsection “The Alphabet” and “The Encoding Function”:

  • We want to exclude the most ambiguous characters, which is not the case in bech32 to our mind.
  • We wanted to optimize the mapping from 5-bit integers to characters w.r.t. our error model, which includes similar looking characters and adjacent keys on a keyboard, which is a small improvement over bech32 to our mind.

We don’t see a reason to differentiate between testnet and mainnet addresses in Lisk, and not distinguishing keeps the implementation simpler. It also makes it unnecessary to include the prefix into the checksum input and to use a separator symbol in the address, as you mentioned it.

I see that we are not compatible enough to use existing libraries like this. But it requires only minor changes to existing code to compute our addresses (removing the human readable part from the checksum input and replacing the mapping from 5-bit integers to characters), and we see some improvements due these changes, as mentioned above.

I created a pull request for this LIP: https://github.com/LiskHQ/lips/pull/24

The pull request was merged. The new LIP has the number 0018.