Bitcoin Forum
August 26, 2024, 02:43:53 AM
Welcome,
Guest
. Please
login
or
register
.
News
: All versions of Windows are affected by a
critical security bug
; make sure you update.
Home
Help
Search
Login
Register
More
Bitcoin Forum
>
Bitcoin
>
Development & Technical Discussion
>
Merkle Trees Mathematical Equation
Pages: [
1
]
« previous topic
next topic »
Print
Author
Topic: Merkle Trees Mathematical Equation (Read 196 times)
bstolzzen
(OP)
Newbie
Offline
Activity: 1
Merit: 0
Merkle Trees Mathematical Equation
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
Evil-Knievel
Legendary
Offline
Activity: 1260
Merit: 1168
Re: Merkle Trees Mathematical Equation
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
Bitcoin Forum
>
Bitcoin
>
Development & Technical Discussion
>
Merkle Trees Mathematical Equation
« previous topic
next topic »
Jump to:
Please select a destination:
-----------------------------
Bitcoin
-----------------------------
=> Bitcoin Discussion
===> Legal
===> Press
===> Meetups
===> Important Announcements
=> Development & Technical Discussion
===> Wallet software
=====> Electrum
=====> Bitcoin Wallet for Android
=====> BitcoinJ
=====> Armory
=====> Mycelium
=====> Hardware wallets
=> Mining
===> Mining support
===> Pools
===> Mining software (miners)
===> Hardware
=====> Group buys
===> Mining speculation
=> Bitcoin Technical Support
=> Project Development
-----------------------------
Economy
-----------------------------
=> Economics
===> Speculation
=> Marketplace
===> Goods
=====> Computer hardware
=====> Digital goods
=======> Invites & Accounts
=====> Collectibles
===> Services
===> Currency exchange
===> Gambling
=====> Games and rounds
=====> Investor-based games
=====> Gambling discussion
===> Lending
=====> Long-term offers
===> Securities
===> Auctions
===> Service Announcements
=====> Micro Earnings
===> Service Discussion
=====> Web Wallets
=====> Exchanges
=> Trading Discussion
===> Scam Accusations
===> Reputation
-----------------------------
Other
-----------------------------
=> Meta
===> New forum software
===> Bitcoin Wiki
=> Politics & Society
=> Beginners & Help
=> Off-topic
=> Serious discussion
===> Ivory Tower
=> Archival
===> Корзина
===> CPU/GPU Bitcoin mining hardware
===> Chinese students
===> Obsolete (buying)
===> Obsolete (selling)
===> MultiBit
-----------------------------
Alternate cryptocurrencies
-----------------------------
=> Altcoin Discussion
=> Announcements (Altcoins)
===> Tokens (Altcoins)
=> Mining (Altcoins)
===> Pools (Altcoins)
=> Marketplace (Altcoins)
===> Service Announcements (Altcoins)
===> Service Discussion (Altcoins)
===> Bounties (Altcoins)
=> Speculation (Altcoins)
-----------------------------
Local
-----------------------------
=> العربية (Arabic)
===> العملات البديلة (Altcoins)
=====> النقاشات
===> إستفسارات و أسئلة المبتدئين
===> التعدين
===> النقاشات الأخرى
===> منصات التبادل
=> Bahasa Indonesia (Indonesian)
===> Marketplace (Bahasa Indonesia)
===> Mining (Bahasa Indonesia)
===> Altcoins (Bahasa Indonesia)
===> Trading dan Spekulasi
===> Ekonomi, Politik, dan Budaya
===> Topik Lainnya
=> Español (Spanish)
===> Mercado y Economía
=====> Servicios
=====> Trading y especulación
===> Hardware y Minería
===> Esquina Libre
===> Mercadillo
=====> Mexico
=====> Argentina
=====> España
=====> Centroamerica y Caribe
===> Primeros pasos y ayuda
===> Altcoins (criptomonedas alternativas)
=====> Minería de altcoins
=====> Servicios
=====> Tokens (Español)
=> 中文 (Chinese)
===> 跳蚤市场
===> 山寨币
===> 媒体
===> 挖矿
===> 离题万里
=> Hrvatski (Croatian)
===> Trgovina
===> Altcoins (Hrvatski)
=====> Announcements (Hrvatski)
===> Off-topic (Hrvatski)
=> Deutsch (German)
===> Anfänger und Hilfe
===> Mining (Deutsch)
===> Trading und Spekulation
===> Projektentwicklung
===> Off-Topic (Deutsch)
===> Treffen
===> Presse
===> Altcoins (Deutsch)
=====> Announcements (Deutsch)
===> Marktplatz
=====> Auktionen
=====> Suche
=====> Biete
=> Ελληνικά (Greek)
===> Αγορά
===> Mining Discussion (Ελληνικά)
===> Altcoins (Ελληνικά)
=====> Altcoin Announcements (Ελληνικά)
=====> Altcoin Mining (Ελληνικά)
=> עברית (Hebrew)
=> Français
===> Actualité et News
===> Débutants
===> Discussions générales et utilisation du Bitcoin
===> Mining et Hardware
===> Économie et spéculation
===> Place de marché
=====> Échanges
=====> Produits et services
=====> Petites annonces
===> Le Bitcoin et la loi
===> Wiki, documentation et traduction
===> Développement et technique
===> Vos sites et projets
===> Hors-sujet
===> Altcoins (Français)
=====> Annonces
=> India
===> Mining (India)
===> Marketplace (India)
===> Regional Languages (India)
===> Press & News from India
===> Alt Coins (India)
===> Buyer/ Seller Reputations (India)
===> Off-Topic (India)
=> Italiano (Italian)
===> Guide (Italiano)
===> Progetti
===> Discussioni avanzate e sviluppo
===> Trading, analisi e speculazione
===> Mercato
=====> Mercato valute
=====> Beni
=====> Servizi
=====> Esercizi commerciali
=====> Hardware/Mining (Italiano)
=====> Gambling (Italiano)
===> Accuse scam/truffe
===> Mining (Italiano)
===> Alt-Currencies (Italiano)
=====> Annunci
===> Raduni/Meeting (Italiano)
===> Crittografia e decentralizzazione
===> Off-Topic (Italiano)
=> 日本語 (Japanese)
===> アルトコイン
=> Nederlands (Dutch)
===> Markt
===> Gokken/lotterijen
===> Mining (Nederlands)
===> Beurzen
===> Alt Coins (Nederlands)
===> Off-topic (Nederlands)
===> Meetings (Nederlands)
=> Nigeria (Naija)
===> Politics and society (Naija)
===> Off-topic (Naija)
=> 한국어 (Korean)
===> 대체코인 Alt Coins (한국어)
=> Pilipinas
===> Altcoins (Pilipinas)
=====> Altcoin Announcements (Pilipinas)
===> Pamilihan
===> Others (Pilipinas)
=> Polski
===> Tablica ogłoszeń
===> Alternatywne kryptowaluty
=====> Nowe kryptowaluty i tokeny
=====> Tablica ogłoszeń (altcoiny)
=> Português (Portuguese)
===> Primeiros Passos (Iniciantes)
===> Economia & Mercado
===> Mineração em Geral
===> Desenvolvimento & Discussões Técnicas
===> Criptomoedas Alternativas
===> Brasil
===> Portugal
=> Русский (Russian)
===> Новички
===> Бизнес
=====> Барахолка
=====> Обменники
===> Идеи
===> Кодеры
===> Майнеры
===> Политика
===> Трейдеры
===> Альтернативные криптовалюты
=====> Токены
=====> Бayнти и aиpдpoпы
===> Хайпы
===> Работа
===> Разное
===> Oбcyждeниe Bitcoin
=====> Новости
=====> Юристы
=> Română (Romanian)
===> Anunturi importante
===> Offtopic
===> Market
=====> Discutii Servicii
===> Minerit
===> Tutoriale
===> Bine ai venit!
===> Presa
===> Altcoins (Monede Alternative)
=====> Anunturi Monede Alternative
=> Skandinavisk
=> Türkçe (Turkish)
===> Bitcoin Haberleri
===> Pazar Alanı
===> Madencilik
===> Ekonomi
===> Servisler
=====> Fonlar
===> Proje Geliştirme
===> Alternatif Kripto-Paralar
=====> Madencilik (Alternatif Kripto-Paralar)
=====> Duyurular (Alternatif Kripto-Paralar)
===> Konu Dışı
===> Yeni Başlayanlar & Yardım
===> Buluşmalar
=> Other languages/locations
Loading...