I want to know how I can express a phenomenon found in Merkle Trees mathematically. If I want to figure out which leaf node in a Merkle Tree has changed I can look at the authentication path to figure it out. Let's say there is one leaf node and one root node. If the root node changes you don't have to look at any other nodes (0) to determine which leaf node must have changed. In Figure 2 there is a 0 across from 1. If there are 2 leaf nodes and the Merkle Root changes you only have to look at 1 node to determine which leaf node must have changed. As we increase the number of leaf nodes there is a relationship that exists with the total number of nodes you need to look at. I was wondering if there was a way I could express this mathematically in a clean way. Thanks!
Figure 1.
2*0 = 0 (1 zero)
2^0 = 1 (1 one)
2^1 = 2 (2 twos)
2^2 = 4 (4 threes)
2^3 = 8 (8 fours)
2^4 = 16 (16 fives)
2^5 = 32 (32 sixes)
2^6 = 64 (64 sevens)
Figure 2.
Leaf (Left Column) & Total Nodes (Right Column)
1 0
2 1
3 2
4 2
5 3
6 3
7 3
8 3
9 4
10 4
11 4
12 4
13 4
14 4
15 4
16 4
17 5
18 5
19 5
20 5
21 5
22 5
23 5
24 5
25 5
26 5
27 5
28 5
29 5
30 5
31 5
32 5
33 6
34 6
35 6
36 6
37 6
38 6
39 6
40 6
41 6
42 6
43 6
44 6
45 6
46 6
47 6
48 6
49 6
50 6
51 6
52 6
53 6
54 6
55 6
56 6
57 6
58 6
59 6
60 6
61 6
62 6
63 6
64 6
65 7
66 7
67 7
68 7
69 7
70 7
71 7
72 7
73 7
74 7
75 7
76 7
77 7
78 7
79 7
80 7
81 7
82 7
83 7
84 7
85 7
86 7
87 7
88 7
89 7
90 7
91 7
92 7
93 7
94 7
95 7
96 7
97 7
98 7
99 7
100 7
101 7
102 7
103 7
104 7
105 7
106 7
107 7
108 7
109 7
110 7
111 7
112 7
113 7
114 7
115 7
116 7
117 7
118 7
119 7
120 7
121 7
122 7
123 7
124 7
125 7
126 7
127 7
128 7
