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).