Account Entropy

The following is a report of account entropy as of Saturday February 02, 2019 15:30 UTC.

1497352 XRP ledger accounts were analyzed for character and substring occurences. The results are detailed below.

The justification behind this study is to examing the current XRP Ledger account distribution by public text representation. We hope these results will be of assistance in understanding the ledger as it currently stands and devising new schemes and mechanisms which to robustly and conveniently reference and utilize accounts.

Note: this is an analysis of the Base58 encoding of XRP account addresses, not of the public key which is used as its basis. Due to the encoding process, this study is not used to make statements as to the distribution of generated XRP keys but rather an analysis of patterns found in the human representation, for use in tools and utility systems down the road.

The list of accounts analyzed can be retrieved here (37MB). The code used to analyze accounts is made available here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
    #!/usr/bin/ruby
    # Determine XRP account entropy, takes in a list of XRP accounts and
    # outputs distribution by length, character, positional character,
    # substring, and case-insensitive substring

    require 'workers'

    # Add method to extract all String substrings of a given length
    class String
      def substrings(n)
        (0..size-n).map{|x| self[x..x+n-1] }
      end
    end

    # Read in accounts, populate queue
    accounts = Queue.new
    File.read("accounts.org")
        .split("\n")
        .each { |f|
          accounts << f
        }

    # Output data
    by_len  = {}
    by_char = {}
    by_char_for_pos = Array.new(34) { Hash.new }
    substrings  = {}
    isubstrings = {}

    # Setup worker to monitor progress
    work = Workers::TaskGroup.new
    work.add do
      l = accounts.size
      until accounts.empty?
        puts "#{accounts.size}: #{l-accounts.size}"
        l = accounts.size
        sleep 3
      end
    end

    # Crunch data
    10.times do
      work.add do
        until accounts.empty?
          a = nil
          begin
            a = accounts.pop(true)
          rescue
            next
          end

          by_len[a.size] ||= 0
          by_len[a.size]  += 1

          # slice off the leading 'r'
          a = a[1..-1]

          a.chars.each_with_index { |c, ci|
            by_char[c] ||= 0
            by_char[c]  += 1

            by_char_for_pos[ci][c] ||= 0
            by_char_for_pos[ci][c]  += 1
          }

          [3,5,7].each { |s|
             substrings[s] ||= {}
            isubstrings[s] ||= {}

            a.substrings(s).each { |substr|
              substrings[s][substr] ||= 0
              substrings[s][substr]  += 1

              downcase = substr.downcase
              isubstrings[s][downcase] ||= 0
              isubstrings[s][downcase]  += 1
            }
          }
        end
      end
    end

    work.run

    # Write output
    File.write "output/len", by_len.collect { |l,n|
                               "#{l},#{n}"
                             }.join("\n")

    File.write "output/char", by_char.collect { |c,n|
                                "#{c},#{n}"
                              }.join("\n")

    File.write "output/pos_char", by_char_for_pos.collect { |by_char|
                                    by_char.collect { |c,n|
                                      "#{c} #{n}"
                                    }.join(",")
                                  }.join("\n")

    substrings.keys.each { |l|
      sl = substrings[l].sort_by  { |k,v| v }.reverse.to_h
      File.write "output/substrings#{l}", sl.collect { |s, n|
                                            "#{s},#{n}"
                                          }.join("\n")
    }

    isubstrings.keys.each { |l|
      isl = isubstrings[l].sort_by  { |k,v| v }.reverse.to_h
      File.write "output/isubstrings#{l}", isl.collect { |s, n|
                                             "#{s},#{n}"
                                           }.join("\n")
    }

The following is the xrp alphabet:

For analysis the leading 'r' was removed before analysis was removed as it is uniform accross all account ids.

This is the tally of number the occurances by each character in the complete account set:

Also the percentage each character is represented in the total account id set:

We can look at the distribution of characters for each individual character position in the account ID:


    Account IDs are of a standard 34 character length (including the leading 'r'), though not all accounts are of this length:

      In total, there are 50850633 characters in the account ID set resulting in 48MB of space needed to store it (if using 8bit characters).


      We start analyzing accounts for common substrings, the following are the most/least common 3, 5, and 7 character substrings in the list of ids with the number of occurances in the account set:

      Looking at the complete 3 character set we see 195111 combinations, consistent with the 583 combinations of XRP alphabet characters. Looking at the distribution of these sequences in the data expressed as number of standard deviations () from the mean ():

      With the 5 and 7 character substring analysis, we see approximately 40-42 million unique substrings in the data set, which is significantly less than the corresponding 585 and 587 total combinations. Also we see that the overlap of substring occurance is far less frequent with higher lengths. This can be explained through the greater number of permutations in the longer string length, many combinations of which have not yet been generated in the ledger

      Next we perform the same 3,5,7 character substring analysis but ignoring case. The following is the most/least common case-insensitive substrings with the corresponding number of occurances in the account set:

      Again plotting the distribution of the case-insensitive 3 character combinations in the data expressed as number of standard deviations () from the mean ():

      Conslusion/Next Steps:

      Because of its relative low overlap, the 5 character substring can be seen as a good mechanism to reference account IDs in an informal context (investigations, discussions pertaining to ledger activity, etc). The case-insensitive version of account ids should suffice to provide enough variance, though care should always be taken to ensure the accounts in a set being analyzed/discussed can truley be distinguished by the fixed-length substring set being used. The case-sensitive versions afford additional variance at the expense of additional referential complexity.

      This work can be extended to incorporate a algorthimic generation of "human-friendly" account mnemonics based on ID parsing cross-referenced with a db of substrings rated to be of more significance. Perhaps this could be a community effort driven by a public resource where these substrings can be voted upon and ranked.