RS

Reed-Solomon Address Format

Reed-Solomon-Address-Format

The short form of Signum account numbers (addresses) are of the form:  S-XXXX-XXXX-XXXX-XXXXX

This format is referred to as a Reed-Solomon address. It is the default format in the official client, where X is a non-ambiguous number or alphabetic character (the letters I and O and the numbers 1 and 0 are not used).  Addresses are always prefixed with “S-“and hyphens are used to separate the address into 4, 4, 4, and 5 characters. The addresses are NOT case-sensitive.

This form improves reliability by introducing redundancy to detect and correct errors when entering and using Signum account numbers.

Background

The internal format for Signum account numbers is a completely numeric 64-bit identifier derived from the account’s private key. This format is error-prone because a single error when typing a character can result in transactions being unintentionally sent to the wrong account.

Reed-Solomon error-correction codes largely remedy this issue by adding redundancy to addresses.  The Reed-Solomon format was chosen because:

  • the account collision rate is the same as the default address format;
  • the system’s basic error correction can be used to assist users in typing addresses;
  • some programming languages do not have a native MD5 hashing function, and the Reed-Solomon implementation is simpler than MD5.

Benefits of Reed-Solomon addresses

  • The chance of a random address collision, using Signum’s implementation of 4 “check-bits,” is 1 in a million (20-bit redundancy).
  • It allows up to 2 typos in an address to be corrected.
  • It guarantees that up to 4 typographical errors can be detected.
  • The address length is always 17 characters.
  • The “S” prefix makes the addresses easily recognizable as belonging to Signum.

Encoding of Signum Reed-Solomon addresses

  • Case is not enforced in this format, but for unification, all addresses are displayed using the upper case.
  • Dashes split addresses into groups of 4 characters and a final group of 5 characters, but this is not enforced during address input.
  • The old numeric addresses are also recognized and supported for backward compatibility.

Example RS Addresses:

  • S-3DH5-DSAE-4WQ7-3LPSE
  • S-K4G2-FF32-WLL3-QBGEL

Technical details

The first and most important rule is that no error-correction scheme is infallible:  Error correction is a useful tool, but it cannot be relied upon haphazardly.

The problem is somewhat counter-intuitive: either you can do a simple yes/no check of address validity, which will give you one in a million collision, or you can try and correct errors. You cannot do both.

The problem here is that the Reed-Solomon algorithm is only guaranteed to correct up to 2 errors. If more than 2 errors are present in an address entry, it will produce false positives with a probability of around 10%, and transactions will still be sent to incorrect addresses.

Think of the algorithm as error-guessing, instead, to assist users with spotting errors.

Reed-Solomon (RS) addresses for Signum are encoded as follows:

  • Take the original 64-bit account ID, add 1 zero bit to get 65, then split it into thirteen 5-bit “symbols” (65 / 5 = 13).
  • Order the symbols from lowest bit to highest bits, in little-endian order, i.e., bits 0-4, 5-9, 10-14, etc., up to 60-64.
  • Append 4 symbols of parity (20 bits), produced by the Reed-Solomon encoding of our 13 symbols from step one (which are left untouched). This produces a 13 + 4 = 17 symbol codeword.
  • Scramble the codeword symbols in a predefined order and encode them 1-to-1 with an alphabet of 32 characters, splitting them into groups by dashes.

11 + 15 =

Share This