Bitcoin Forum
May 13, 2024, 08:01:25 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Merkle Trees Mathematical Equation  (Read 185 times)
bstolzzen (OP)
Newbie
*
Offline Offline

Activity: 1
Merit: 0


View Profile
July 24, 2018, 01:51:04 AM
 #1

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    Total Nodes                  
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
1715630485
Hero Member
*
Offline Offline

Posts: 1715630485

View Profile Personal Message (Offline)

Ignore
1715630485
Reply with quote  #2

1715630485
Report to moderator
1715630485
Hero Member
*
Offline Offline

Posts: 1715630485

View Profile Personal Message (Offline)

Ignore
1715630485
Reply with quote  #2

1715630485
Report to moderator
The forum was founded in 2009 by Satoshi and Sirius. It replaced a SourceForge forum.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1715630485
Hero Member
*
Offline Offline

Posts: 1715630485

View Profile Personal Message (Offline)

Ignore
1715630485
Reply with quote  #2

1715630485
Report to moderator
Evil-Knievel
Legendary
*
Offline Offline

Activity: 1260
Merit: 1168



View Profile
July 24, 2018, 04:44:21 AM
 #2

Quote
 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!

Well, if you assume that exactly one node changed, you should only need to check ceil(LOG(n)/LOG(2)) nodes with ceil() being the "round up" function. Basically, you need one check per tree height level.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!