Lecture 3 - Merkle Trees
Summary
TLDR本视频讨论了银行两个分行间的资金转移问题,提出了一种通过Merkle树结构来确保交易记录的安全性和隐私性的方法。通过构建一个由交易哈希值组成的二叉树,并仅通过树的根哈希值来提交所有交易的承诺,同时允许用户通过短证明验证其交易的存在。此外,视频还探讨了如何使用排序Merkle树来证明某个值不存在于树中,而不会泄露其他信息。最后,视频提出了一个关于如何在网络上安全地玩剪刀石头布的问题,作为观众思考的挑战。
Takeaways
- 🏦 问题描述:银行有两个分行,分别位于香港和伦敦,客户在香港存款后希望在伦敦取款。
- 🔒 安全性要求:香港分行发送给伦敦分行的消息M通过不安全的通道传输,可以被任何人查看,但无法篡改。
- 📜 消息M的构成:消息M包含所有存款交易的哈希值,每个存款人获得一个证明P,用于在伦敦分行取款。
- 💡 解决方案初探:使用链表或账本,每个交易包含交易ID、付款人信息和金额,以及指向前一个交易的哈希指针。
- 🔏 隐私保护:通过在交易中包含个人信息的哈希值而非实际信息,保护客户隐私。
- 🌳 梅克尔树(Merkle Tree):使用梅克尔树结构来优化证明长度,提高效率。
- 🔄 梅克尔树的证明:通过提供从根节点到特定交易节点的路径上的节点及其兄弟节点的哈希值,验证交易的存在。
- 📈 梅克尔树的优势:提供了较短的证明长度(O(log n)),同时保持了隐私性,因为只包含哈希值而非实际交易信息。
- ⏱️ 实时性问题:创建梅克尔树需要知道所有交易,因此在所有存款完成后才能生成证明,存在延迟。
- 🔄 排序梅克尔树:通过排序交易值(或其哈希值),可以更高效地证明某个值不存在,同时减少信息泄露。
- 🤼♀️ 应用场景:梅克尔树可以用于多种场景,如在线游戏(如剪刀石头布)和拍卖,确保公平性和不可篡改性。
Q & A
如何确保香港分行和伦敦分行之间的信息传递既安全又高效?
-通过使用Merkle树结构,香港分行可以将所有交易的哈希值发送给伦敦分行,这样伦敦分行可以通过较短的证明来验证每个存款者的资金是否真实存在。
在不安全的通道上发送信息时,如何防止信息被篡改?
-通过在信息上附加数字签名,可以确保信息在传输过程中不被篡改。虽然在这个脚本中还没有详细讨论数字签名,但它是一种常见的安全措施。
什么是Merkle树,它是如何工作的?
-Merkle树是一种树状数据结构,其中每个叶节点包含一个数据块的哈希值,而非叶节点包含其子节点哈希值的哈希。这种结构允许有效的验证,因为可以通过比较根哈希值和叶节点的哈希值来验证数据的完整性。
为什么需要使用随机数(nonce)?
-随机数(nonce)用于增加交易的唯一性,防止重放攻击,并隐藏数据模式,从而提高安全性。
如何确保存款者在伦敦分行取款时,他们的个人信息不被泄露?
-通过在Merkle树中存储个人信息的哈希值而不是实际信息,可以确保即使哈希值被公开,个人隐私也不会泄露。
如果存款者想要证明他们的交易确实存在于列表中,他们需要提供哪些信息?
-存款者需要提供从根节点到其交易所在的叶节点的路径上的节点值。这些值包括每个节点的哈希值,以及在必要时,其兄弟节点的哈希值。
Merkle树如何帮助防止双重支付问题?
-伦敦分行可以通过跟踪已经支付的交易的哈希值来防止双重支付。一旦交易被验证并支付,它的哈希值就会被记录下来,从而防止同一笔交易被重复提取。
在Merkle树中,如何证明某个特定的值不存在于树中?
-通过提供该值前后的两个值的哈希值,可以证明中间的值不存在于树中。这是因为Merkle树的结构保证了值的顺序,所以如果两个相邻的值都知道,那么中间的值也就知道了。
为什么在创建Merkle树时需要知道所有的交易?
-创建Merkle树需要将所有交易的哈希值按照一定的顺序排列,然后逐层计算父节点的哈希值,直到得到根节点的哈希值。因此,必须先知道所有的交易才能构建完整的Merkle树。
在网络环境中如何安全地玩剪刀石头布游戏?
-可以通过设计一种机制,要求Alice和Bob同时提交他们的选择,并且这个提交是不可更改的。例如,可以使用区块链技术,让他们的选择被记录在区块链上,这样就没有人能够在知道对方选择后更改自己的选择。
Outlines
🏦 银行分支间资金转移问题
视频脚本讨论了一个银行两个分支(香港和伦敦)之间的资金转移问题。客户在香港存款,并希望在伦敦取款。银行只能发送一条消息(M)给伦敦分支,这条消息通过不安全的渠道传输,任何人都可以看到,但无法更改。香港分支给每个存款人一个证明(P1, P2, P3, P4),这些证明是二进制字符串。目标是确保每个存款人都能取款,但只能取一次,同时不泄露任何个人信息。
🔗 使用哈希指针的链表解决方案
提出了一种使用链表和哈希指针的解决方案,通过创建交易并链接它们,每个交易包含付款人信息和金额。通过哈希指针连接交易,形成链表。为了验证交易的存在,客户需要提供从链表末尾到其交易的路径。这种方法的问题是证明太长,且泄露了所有交易信息,不符合隐私要求。
🔒 隐私保护和短证明的需求
讨论了如何通过使用哈希函数来保护客户隐私,避免泄露个人信息。同时,提出了短证明的需求,即如何减少验证交易存在所需的信息量。
🌳 利用Merkle树优化证明长度
介绍了Merkle树(奇迹树)的概念,通过构建一个二叉树结构来优化证明长度。每个交易都有一个哈希值,树的根节点是所有交易哈希值的哈希。这样,证明一个交易的存在只需要提供从根节点到该交易的路径上的节点,大大减少了证明的长度。
🔐 提供交易存在的证明
详细说明了如何使用Merkle树为每个客户提供其交易存在的证明。客户需要提供根哈希值和从根节点到其交易的路径上的节点哈希值,以证明其交易确实存在于树中。
📈 优化Merkle树以支持实时交易
讨论了如何优化Merkle树以支持实时交易。提出了一个问题,即如何在不知道所有交易的情况下创建Merkle树,这需要在所有存款完成后才能进行。
🔎 证明特定项不在Merkle树中
探讨了如何证明一个特定项不在Merkle树中,通过使用排序的Merkle树来简化这一过程。通过证明一个特定值前后的值,可以间接证明该值不存在。
🤼♀️ 在线游戏的安全性问题
提出了一个在线游戏(如剪刀石头布)的安全性问题,即如何确保游戏双方不作弊,同时保持游戏的公平性。这个问题与之前的拍卖例子相似,都需要确保双方在不知道对方选择的情况下做出决定。
Mindmap
Keywords
💡银行分支
💡不安全通道
💡数字签名
💡存款证明
💡双重支付
💡数据泄露
💡Merkle树
💡隐私保护
💡链表与哈希指针
💡二叉树
💡实时性问题
Highlights
讨论了银行两个分行间的资金转移问题,其中一个分行在 Hong Kong,另一个在 London。
Hong Kong 分行通过不安全的渠道发送一条消息 M 给 London 分行,这条消息可以被任何人看到,但无法被篡改。
Hong Kong 分行给每个存款人一个证明 P1、P2、P3 和 P4,这些证明是二进制字符串。
存款人 Alice、Bob、Carol 和 Dave 分别存入不同金额,希望以后能在另一个分行取回。
设计要求确保每个人都能取回自己的钱,并且每笔存款只能取回一次,防止双重支付问题。
消息 M 不能泄露任何关于存款人的个人信息和存款金额。
提出了使用链表或带有哈希指针的账本来记录交易,但这种方法存在问题。
为了解决链表方法的问题,提出了使用哈希树(Merkle tree)来提高效率。
哈希树的每个节点都是其子节点哈希值的哈希,根节点的哈希值作为整个交易历史的承诺。
哈希树的证明长度是 log(n),比链表方法的 n 要短得多。
哈希树方法解决了隐私问题,因为树中的节点只包含数据的哈希值,而不包含实际的个人信息。
每个存款人需要证明其交易存在的路径,以及该路径在哈希树中的位置。
通过哈希树,可以有效地证明某个特定值是否存在于树中,同时保持证明的长度较短。
提出了排序哈希树(sorted Merkle tree)的概念,通过排序数据来简化证明特定值不存在的过程。
即使在排序哈希树中,也可以通过证明前后哈希值来证明某个值不存在,而不会泄露其他数据信息。
讨论了如何在互联网上安全地玩剪刀石头布游戏,确保双方无法作弊。
将拍卖视为一种游戏,其中参与者需要在不知道对手动作的情况下进行出价。
提出了使用区块链技术来解决分布式系统中的共识问题,确保数据的一致性和安全性。
通过这个银行分支间资金转移的例子,展示了区块链技术在金融领域的应用潜力。
Transcripts
at the end of the last session we talked
about this problem of a bank with two
branches and let's just revisit that so
let's say that I have one branch here in
Hong Kong and let's say there is another
branch in
London and we said that people can
deposit money in Hong Kong and they want
to get their money back in London later
now the idea was that the Hong Kong
Branch can send only one message to the
London branch and this message we called
it
m we said that this is sent over an
unsecure channel so my assumption is
that this message M can be seen by
anyone maybe a hacker sees it and then
publishes it to everyone but no one can
change it okay and we will talk about
digital signatures later on but for now
just imagine that this message somehow
has a signature from Hong Kong and it's
impossible to forge that okay so this is
what we have and then we have a bunch of
people who are depositing money so let's
say again we have Alice
Bob maybe
Carol and let's say
Dave and each of them is depositing some
amounts maybe
50 100 200 and maybe
10 right and then later on they want to
be able to go to the other branch and
get their money back and we said that
the Hong Kong Branch should give each
one of these people uh a proof so let's
call it P1 P2 P3 and
P4 and generally whenever I don't say
what the type of something is you should
just assume that it's a string of zeros
and ones so the message M that's I'm
sending from Hong Kong to London is just
a string of zeros and ones the proofs
that I'm giving to each one of the
depositors these are also just strings
of zeros s ons and then the idea was
that let's say this happens on day one
so on day
one everyone does the deposit and then
the Hong Kong Branch gives them the
proofs and then let's say the next day
on day
two each one of them go to the London
Branch the London branch has already
received the message M but now each of
them should be able to give the proofs
that they have received from Hong Kong
to the London branch and get their money
now if we want to write our requirements
more
specifically these are the requirements
that I
have I have to make sure that everyone
can get their money back and I have to
make sure that they can get their money
back only once so you shouldn't be able
to deposit once and then withdraw twice
so uh let's say the first one is that
every
depositor can
withdraw but the second constraint is
that each deposit can be withdrawn at
most
once
okay and we will later on see that this
is actually one of the most problematic
issues when we're designing a
cryptocurrency so this is the problem of
double spending maybe someone has just
one coin and they're trying to use it
twice or something like that here we
will have someone who has deposited once
let's say Alice has deposited $50 and
maybe she goes to the London branch and
then she tries to withdraw $50 twice we
have to make sure this cannot
happen and the other constraints that we
want to
have is basically I don't want to leak
any data based on M so m is public
everyone can see M no one should be able
to find any of the personal information
on of the depositors and the amounts
that they deposited based on M so
M does not
leak any personal
data
okay and then we also talked about this
idea that maybe this channel is really
expensive maybe I want my message M to
be as short as possible so this is
another requirement I just want to say
that the message m is really small so
let's say m has constant lengths
has1 this is another thing that I would
like to
have because otherwise if M could be
large well the Hong Kong Branch could
just take the hash of every transaction
the hash of every deposit and send all
of these has hases to the London ranch
right that would make the problem
trivial but at the same time we have a
really
huge now we saw a solution last time and
the solution was to just use a linked
list or a ledger with hash pointers so
the idea was very simple this was our
initial
idea so uh maybe I can call it nons
solution one because we know that it
will not work in the end
was that I'll just create some
transactions and let's say every
transaction has some ID and a let's say
this is transaction number one and let's
say it also has a pointer to the
previous transaction now in this case
because there is no previous transaction
this pointer is just null there's
nothing in there but then in this
transaction I say who paid the money and
how much so maybe I just say this is
Alice and
50 then I I create another
transaction it's really hard
to this so this was transaction one this
is my transaction two it has a serial
number two it should also have a pointer
to the previous transaction so it will
have a
pointer to this transaction and
basically the way that works is that I
have a hash of the previous transaction
so the pointer is just a hash of
transaction one and then in transaction
two I'm saying that Bob paid 100 so I
would just write Bob
100 and I just repeat this for the other
two transactions as well so I have
transaction
three and this one was Carol plus d 200
and then
10 okay so 200 and it also includes the
hash of the previous
transaction and then finally I have this
last transaction transaction
4 it has the hash of transaction
three and it says that they've paid
much
okay now the question was what is the
proof that we can give uh to each of the
depositors and what is the message M
that we're going to send to the other
Branch so for the message m
we said we just take the hash of the
very last transaction so I just take
this whole transaction I hash it I get
hash of transaction for and I say this
is my message
M and I send this to the other
Branch now let's say that you're one of
these depositors and you need to go to
the London branch and prove that one of
these transactions actually exists it's
actually in this list now let's say
you're Dave if you're Dave you can just
go to the other uh branch and you can
just show your
transaction and they can just calculate
the hash they see that it's the same as
M that they received from the other
Branch so they know that you didn't fake
this
transaction so they would give you the
money but now imagine your Carol if
you're Carol you can't just give your
own transaction you have to also provide
Dave's
transaction because that's the only way
you can verify Carol's transaction here
see uh as the London Branch You Know M
you know the hash of this last
transaction so if Carol wants to prove
that this transaction transaction three
actually I forgot to write the
transaction name so this was transaction
three this is transaction
4 if Carol wants to prove that this
transaction is actually in the list she
has to start from the end of the list
she has to First say here's transaction
four which has the the correct hash and
the bank can check that and then she has
to say okay now in transaction four as
you see there is a hash pointer to
transaction three and here's transaction
three and now you can check that it has
the correct hash so that's how Carol can
prove that her transaction is in there
so in order for Carol to prove the
existence of her transaction in this
list she has to actually know her own
transaction but also Dave's
transaction now the problem because
comes even worse for Bob because you can
just continue with this Bob has to know
his own transaction Carol's transaction
and Dave's transaction in general each
person who wants to prove the existence
of their transaction has to also prove
every transaction that comes after it
right so in general the proof that I'm
going to have if I have end
transactions
[Music]
uh I don't know why this writing is not
working okay so assuming that I have n
transactions this is what happens the
proof of transaction I is going to
include transaction I itself but also
transaction I + one transaction I plus 2
all the way to transaction
n right so this is the proof that I'm
giving to each one of my
depositors so Alice here is going to
have the longest proof because she
actually needs to have all all of the
transactions in order to prove the
existence of
a now two problems and these were the
problems that I mentioned at the end of
the previous session the first problem
is that now our proofs are too
long and the second problem is privacy
if Alice needs to know all of the
transactions that come after hers in
order to prove the existence of her
transaction that means that Alice has to
know that Bob deposited 100 and Carol
deposited 200 and so on so Alice knows
everyone's name and amount that they
transacted and that's not something that
we would be happy with so let's add some
extra requirements
here I can apparently only write towards
the top of the page for some
reason okay
so my extra
requirements are going to be short
proofs and privacy
see so short proofs is fine
privacy by privacy at this point I mean
that no one should be able to see other
people's transactions so no one should
be able to see other people's names and
no one should be able to also see the
amounts that they
deposited so uh no
client
sees
other people's
information but are these the only
requirements that are not satisfied can
we just check that these previous
requirements are already all
satisfied
so every depositor can withdraw yes
because every depositor can prove that
their uh transaction was actually in the
linked list in The Ledger so we have
this one each deposit can be withdrawn
at most once well this one is something
that we can enforce on the side of the
London Branch because the London Branch
can just remember which transactions uh
have been paid out and just don't pay
out the same transaction more than once
right and every transaction has a serial
number so they can just keep track of
the serial numbers that are paid out so
this is
easy now here's the interesting part we
already had the requirement that M the
message that is sent from Hong Kong to
London does not leak any information any
of the personal information of the
people and actually we satisfied that
because m is just the hash of this
transaction right and hopefully the hash
of the transaction doesn't really leak
any information but in the last session
we saw that if you don't have nones in
your hash it can actually leak
information right but here I don't need
to add an extra NS because this hash is
pretty much like an ANS
itself right so the hash of transaction
three is already included in transaction
four and that's something that uh really
makes our domain large so no one can
really do uh any kind of uh butterfly
attack or uh just trying every
possibility root forcing things like
that but if you don't trust your hash
function you can also add a non here
that's fine so this makes sure that M
does not leak any information and of
course M's length was fixed because the
output of a hash function always has a
fixed length let's say
256 so this is also F now the thing that
is interesting here is that I didn't
want M to leak any personal data and
basically I used the hiding property of
the hash function here I said that
because m is just the hash of something
and because my uh hash function is
hiding this m is not going to leak any
information
right so now here for privacy I need
something very similar it's just that I
want to make sure that none of the
clients can see anyone else's
information so maybe I can again use
hashes so the idea here is to use
hash to hide
data
okay so what was our problem here why
were we leaking any personal
information basically the problem was
that when Carol wanted to prove that her
transaction is in there she had to also
provide the transaction for Dave but
then the transaction of Dave actually
included his name and his amount right
so if I just Define my transactions in a
different way so that my transactions
don't have this personal information in
them but they only have let's say the
hash of the personal
information then no information will be
leaked so let's do this let's say that
uh first of all I need a bunch of
nonsense for my hashes so let's say
whenever someone is depositing money
they're also giving a random nons to the
branch so Alice when she deposits the
money she chooses some nons n one and
also gives this nons uh to the Hong Kong
branch and let's say this N1 is just a
random string of 1,24
bits and let's say Bob does the same
thing Carol does the same thing and Dave
also does this now I'm going to change
the structure of my
transactions so this is nons solution
two it's going to solve our privacy
issue but it's not going to solve the
problem problem with really long
proofs now again look here transaction
one used to include the personal
information of Alice instead I'm just
going to say this transaction will only
have the hash of the personal
information so I'm going to create a new
transaction
one and again just as before it has a
serial number it has a pointer to the
previous transaction but there is no
previous previous transaction so this
one is null so when I say null you can
just imagine a string of all zeros right
and then here instead of actually
putting Alice 50 I put the hash of the
string that contains her name and then
concatenated with the amount and then
concatenated with the nons that she
chose okay so this is now my new
structure for my transactions and of
course I do the same thing for the other
trans transaction so
uh this is my transaction
two and let's say transaction three and
transaction four and each one of them
will have a serial number it will have a
pointer to the previous transaction
which is basically just the hash of the
previous
transaction and instead of the
information it will just have the hash
of the information so Bob
100 and the nons of Bob
two okay and so on I'm just too lazy to
draw this you
know okay now first of all why do we
need the nones we need the nonsense
because otherwise uh again someone can
do a Brute Force attack If someone knows
the names of all of our clients they can
just try every possible name and they
can also try every possible value if the
values are small so we need the nonsense
here to really hide the
data but now actually my laziness is
backfiring I have to actually put them
here I guess so I have this hash of
whatever here hash of the personal
information I have a pointer to the
previous one I have a serial number and
here again I have the hash I have a
serial number and I have a pointer to
the prev
okay
now just as
before we have to talk about what kind
of proof we have to give to each one of
the
depositors so the last depositor again
just uh brings the transaction so I just
say that my m is the hash of this last
transaction so that's the value that the
Hong Kong branch is sending to the
London branch
and if the last depositor wants to prove
that their transaction is in the this
they can just bring their transaction
and when they bring their
transaction the Hong Kong Branch can
check that it has the right
hash and then when they see that it has
the right hash what is it that uh I'm
providing I'm basically providing this
pointer this serial number and this
other
hash but now the Hong Kong the London
branch is convinced about this
hash right but this hash is the hash of
my personal information so it's the hash
of my name and the amounts that I put in
and the nons that I chose but I know all
of those things so I can give those
things to the London Branch as well and
they can verify it and they can know
that this was the amount that I put
in so the proofs actually work just like
before so now let's consider
Alice let's say that Alice wants to
prove that transaction one was in there
so she has to start with the last
transaction she has to give the hash of
the last
transaction right uh so sorry she has to
give the last transaction transaction 4
and then the branch checks that it has
the right hash but after it checks that
transaction 4 has the right hash it can
see the pointer here to transaction
three and then Alice can give
transaction three and then we can just
Traverse all the pointers back until we
get to transaction one so everything is
just like before Alice knows all of
these transactions the difference is
that these transactions now don't
include any personal information of
anyone they just include these hashes so
even though Alice knows this hash that
appears in transaction two she doesn't
know that transaction two actually
belongs to Bob and it was for $100 and
so on that information is Now hidden
she knows that information only for her
own transaction so now the proof is
exactly like before she just proves that
this transaction transaction one is in
the linked list but after she does this
she also knows the values that created
this hash so so she can actually open
this hash and say okay now this hash
says that I'm Alice I deposited 50 and
this is my NS so she can know only about
her own personal data and she can prove
the existence of the transaction to the
other branch and everything else goes
through because well of course she can
withdraw now because she can prove her
own
transaction uh every deposit can be
withdrawn at most once because again
let's say the London Branch just keeps
track of the serial numbers that are
withdrawn and it's really important that
these serial numbers and the hash
pointers they're outside of this hash so
the design is quite important here and M
does not leak personal data for the same
reason as before it's a hash it has
constant lengths for the same reason as
before but now we also have this
privacy now we have this as well no
client can see any other clients
information they can only see the hashes
and the hashes don't
leak but we still don't have short
proofs the lengths of our proofs are
still as bad as before so my proof is
still the same as before if I want to
prove transaction I I have to provide
all the transactions from transaction I
forward so if I want to prove the first
transaction I have to give all of the
transactions so in the worst case my
proofs have a length of basically Theta
n
okay
so how do we make this better let's
forget about the hashes and let's just
look at the data structure what are we
doing this message M that I'm giving to
the London branch
it's basically a pointer to the last
transaction right because we talked
about this hashes are
Pointers now I'm giving a pointer to
this last transaction and whenever
someone wants to prove that their
transaction is in the list they have to
basically help the London Branch
Traverse this whole list until it
reaches their
transaction so that's the problem the
problem is that I have a link list and
basically I have to Traverse this link
list until I get the transaction I was
looking for and doing
that uh in the worst case takes n steps
or n minus one steps
okay now from your basic data structures
coures what is a data structure that
would allow you to Traverse it
faster you can just use something like a
binary tree right so this is the
intuition that I want you to have
imagine that instead of having a linked
list I just use a binary
tree so let's say I have a root in my
tree and each node has two children it's
a binary
tree so it's a tree that looks like
this okay now if I have a tree like this
and if I have n elements in the tree so
let's say n nodes or n
elements what is the height of this
tree it's logarithmic in N right so my
height is just going to be o of
log now let's say that I
somehow can give the London Branch a
pointer to the root of this tree and
let's say that every node also has two
pointers it has a pointer to the left
side and a pointer to the right side so
a pointer to the left child and another
one to the right
child if this is the case then you can
see that my proofs will be shorter so if
I want to prove that this node for
example let's say I want to prove that
this is in my tree let's say this is the
transaction where I've deposited some
money in Hong Kong I want to prove that
this is in the tree and let's say that
the pointer that Hong Kong sent to
London was a pointer to the rout all I
have to do is that I have to prove that
the root is there so I have to give the
root to the London Branch then I have to
show that the root has a pointer to this
left child and give this left child to
the London Branch then I have to show
that this left child has a pointer to a
right child and give this
one so now as you see I'm basically
providing only one of the nodes at each
level of the tree so I'm providing a
proof that has a length of login but I
didn't tell you how to create this tree
yet this is just the intuition the
intuition is that instead of
traversing a whole link list which takes
linear time I just want to be able to
Traverse a binary tree which takes login
time okay now how how do we actually
make this kind of tree this is what we
call a miracle
tree
okay now here's how this works let's say
that I have a bunch of transactions
transaction one to transaction four now
in my transactions I'm just going to put
the uh personal data so
basically I have um let's say I don't
personal data let's show with d so I
have D1 D2
D3 and D4 and basically D1 is the
personal data of Alice it's basically
the string that says Alice deposited 50
and her nons was N1 so that's what
d1s right and similarly for all the
other ones so for example D4 is just
Dave 10
N4 okay so
D4 it's just going to be Dave deposited
10
and is non for N4 okay I want to create
a binary tree that contains all of these
uh pieces of information D1 to
D4 uh kind of as its leaves but not
exactly so here's what I'm going to do
I'm going to create a leaf for each one
of
these so I'm going to create a node in
my tree and in this one I'm going to put
the hash of
D1 in this node I'm going to put the
hash of
D2 similarly I'll just put the hash of
D3 the hash of
D4
okay now I want to create a binary tree
so there should be a node that is the
parent of both of
these and let's give this a name let's
call this one L1 so L1 is just the hash
of D1 L2 is just the hash of D2 I have
L3 here and L4
here now I create a parent that
basically has the hash of L1 and L2 so I
do this hash of L1 concatenated with
L2 and I make it the parent of both of
these
and here I do the same thing I have to
scroll up in order to be able to write
so hash of
L3 oops concatenated with
L4 okay let's give this some other name
so I don't know let's call this one B1
and let's call this one B2 I will
finally have a root which basically has
the hash of B1 concatenated with
B2 and this is my root let call it
R
okay let me just clarify something here
so I have a bunch of pieces of data and
all of these are strings D1 D2 D3 D4
right so I'm taking the hash of D1 I'm
calling that L1 so L1 is also a string
it's just the hash of D1 L2 is just the
hash of D2 so I then take these two
strings I concatenate them and I take
their hash and I call that B1 so if I
want to expand this B1 is basically the
hash of the hash of D1 concatenated with
the hash of
D2 that's what B1
is okay and similarly B2 is the hash of
the hash of D3 concatenated with the
hash of
D3 now finally I'm going to use my root
hash uh which is called also the miracle
root so this whole tree is called the
miracle tree after its inventor and The
Roots we always call it the miracle rout
I'm going to use this route as my
message M so this is what the Hong Kong
branch is sending to the London
Branch now the first thing I want you to
see is that when send this message m to
the other Branch I'm basically
committing to everything in this tree
I'm committing to all of the data points
D1 to D4 because if I later want to
change any of them let's say I want to
change D2 this would also change L2
because it's just the hash of T2 but if
it changes L2 it will also change
B1 and generally whenever any node in
this three changes it also changes its
parents because you you have to
recalculate the hashes so this means
that when I'm giving the hash of the
root I'm committing to everything in
this tree I cannot change any of the
entries in this
tree
okay so that's good because it means
that uh I can just send this root hash
to the other branch and I have sent a a
very short message a message of constant
length but I'm now sure that that
message has enough information to commit
me to every one of the transactions
now let's say that someone wants to
prove that their transaction is actually
in the list so what kind of proof should
I give to Alice so that Alice can prove
that D1 is actually in this
stream so Alice should be able to go to
the London branch and she should be able
to basically let the r London Branch
start from here and then go to B1 and
then go to L1 so that they're convinced
that D1 is there so the information that
Alice needs to know is going to be what
well she needs to know the root
hash needs to basically Know M or let's
say
this right but let's say that she knows
M and the London Branch also knows M but
now Alice wants to prove that B1 is the
left child of
M okay how can you do that well you
actually also o need to know
B2 right because the only way I can
prove that B1 is the left child is by
providing both B1 and B2 and saying just
take the hash of B1 V2 and that gives
you the hash that you already have here
it gives you
R right so Alice needs to know this note
Alice needs to know R she needs to know
B1 but she also needs to know
B2 and the role of B2 is to just prove
that B1 is the left child of
R okay so now that she has provided this
information the London branch has
verified that B1 is the left child of R
but B1 is just the hash at this point
right now Alice wants to prove that L1
is the left child of B1 but in order to
do that she also needs to know the right
child she also needs to know L2 so if
she provides both L1 and L2 then uh the
branch can just compute the hash of L1
and L2 and verify that it was correct
which means that L1 is the left child
and L2 is the right child so she needs
to know L2 and she needs to also know
L1 and at this point when she gives all
of this information to the London Branch
the London Branch knows that L1 is in
the tree now L1 was just the hash of the
personal data of Alice and Alice knows
her own personal data she knows that uh
d one was basically Alis 50 and N1 so
she can just provide this and then at
this point it's proven to the bank that
this deposit was actually in the list
and it was actually in this
tree
so now let's do it for someone
else let's say
that uh Carol wants to prove it so I
want to prove this third transaction
again I have to prove the root
I have to prove that B2 is the right
child of the root but in order to do
that I have to also know B1 so she
should also know
B1 and B2 but at this point B2 is proven
to the bank so she wants to prove that
L3 is the left child of B2 but to do
that she needs to also know L4 so she
needs to know L3 and
L so this is the proof that I'm going to
give
to Carol to the person who's done the
third deposit and so now in general this
might not look great when I have only
four deposits because the proofs seem to
be
long but in general if I have a Long
Tree basically my intuition holds I can
start at the top of the tree and I just
have to provide the path that goes to my
particular Leaf but the difference is
that whenever I'm providing some node I
have to also provide it
sibling so I'm not going to just give
proofs of lengths login the lengths of
the proofs are actually two times login
but that's fine I don't care about just
the constant factor it's all login
anyway so I can now have proofs whose
lengths are just all Lin so every
Pi
now if I take any proof Pi the lengths
of this
proof is in O of login more specifically
it's twice the logarithm plus one plus
two whatever
okay nice so this is what we call a
mirle tree and it finally now satisfies
all of our requirements so first of all
it has short proofs short in the sense
that the length of the proof is all in
we will later on see how we can actually
decrease this to even constant time
when we talk about digital signatures
and other things but for now this is
short enough for
us it also protects the privacy because
you
see any one of my clients would just see
some of the hashes this tree but these
hashes they don't contain any personal
information so in my tree I'm not
putting any of the actual personal data
I'm only ever putting the hashes and all
of my hashes have nonsense in them
so it also satisfies the Privacy
requirement and these previous
requirements it's also kind of easy to
verify so the message that is sent from
one branch to the other branch is just
the hash of the root that's constant
size of course it doesn't leak any
information none of our hashes leak any
information and every depositor can
prove that their deposit exists by just
proving the path from the route to their
deposit so that's fine and when we say
each deposit can be withdrawn at most
once that's also easy because uh
the the London Branch can basically keep
track of the hashes of all the deposits
that have already been paid out and you
don't pay out for the same hash more
than once or you can keep track of the
paths that have been paid out and you
don't pay for the same paths more than
once in any case it's easy to keep track
of these
things okay
but we still have another problem and
this is a problem that we will solve in
future sessions and the problem is that
this is not in real time right so in
order to create this whole tree I need
to know all of my transactions so the
way this actually works is that on day
one in the morning everyone goes to the
Hong Kong branch and deposits their
money and gives their nonsense and
everything and then after all the
deposits are done only then the Hong
Kong Branch can create that tree the
miracle tree so they create the Merle
tree they send the hash of the root to
the London Branch but again only after
they have created the Merle tree they
can give the proofs to the
clients so when the client makes a
deposit they're not going to get a proof
immediately they're going to have to
wait until everyone else does their
deposits too and then only at the end of
the the day they each get their
proof okay so we have this problem
here
now let's forget about our use case and
let's just focus on Miracle
trees so we saw how we can prove that a
particular item is in the leaf of a
miracle tree I can just start at the
root prove the
pass what if I want to prove that the
particular item is not in the Merle
tree can I give those kinds of
BS so right now it seems
impossible right because I mean how can
you prove that something is not there
unless you know everything unless you
can prove every single element that is
there if you know all of the hashes uh
at every level and if you know D1 D2 D3
and D4 you can prove everything that is
in there and then you can say nothing
else is there right but in general if I
give you some other number D5 and I ask
you is D5 in this tree or not there is
no way you can give a short proof that
D5 is not in the tree but we can solve
that by a very nice trick and this is
what we call ass sorted mle
tree so the idea in a sorted tree is
that I'm just going to create a miracle
tree but when it comes to the leaves
when it comes to the data Le I'm going
to sort
those okay so I'm going to have the
exact same thing as
here let me see if I can just copy
this I'm going to have the exact same
thing now it's going to be
sorted so it means that D1 is going to
be less than D2 less than D3 less than
D4 and in general I can do this with n
of
course now why does this sorting
actually help
me well first of all how do I sort
strings I can just sort them in lexical
graphic order so even if you think of
these not as numbers but as just
sequences of zeros and ones you can sort
them anyway so we have an
order and
now let's think of them as numbers for a
second because for this example it's
easier to do with numbers let's say D1
is two D2 is five D3 is 8 and this one
D4 is 10
let's and suppose that I want to prove
that's there is no six in
here how can I prove it well I can just
prove the existence of D2 and D3 I can
just prove the existence of five and
eight because when I prove the existence
of five and eight I'm not just proving
that they exist in the tree I'm also
proving their location in the tree so if
I prove that five is here which I can do
and I can give a proof of uh length
login and then if I can also prove that
8 is
here because I've also proven the
location I've proven that 8 comes
exactly after five which means that
there is no six there is no
seven right so this is how we can prove
that a particular value does not exist
in a miricle tree if I just sort all of
my values and if I just prove the
previous value and the next
value
okay but now of course
the next problem and what I want you to
think about is that suppose I want to
prove that a particular value is not in
my tree but I also don't want to leak
information right because here I have a
problem and the problem I have is that I
wanted to prove that six is not in my
tree but then in order to do that I had
to prove that five and eight are
actually in my tree but that's leaking
five and eight that's leaking some
information uh and maybe I don't want to
do that maybe I just want to prove that
a particular number is not in the tree
but I don't want to leak any information
about the numbers or the datas that are
actually in the tree can I do
that yeah so the idea
is yes exactly so instead of sorting
based on the D's let's just sort the
L's let's just sort based on the
hashes right and then when I want to
prove that a particular item is not
there I just take its hash and then I
prove the previous hash and the next
hash and that proves that this
particular hash is not there and when
the hash of this item is not there that
item is also not right so that's pretty
easy uh yeah but in general this is like
a factor of
two well not a factor of two ex it's a
little bit worse than just proving the
existence of something because now I
have to prove the existence of two
things so if I just wanted to prove the
existence of eight I have to provide R
B2 B1 L3 and L4 but now for five I have
to prove R V1 V2 L1 and L so actually in
this particular case again because my is
really shallow in order to prove that
500 I have to
Pro
okay now here's a problem that I want
you to think
about suppose that I want to play Rock
Paper
Scissors but I want to play it over the
Internet so this is just something to
think about rock paper scissors this was
actually the homework in the last uh
offering of this course but I'm not
going to use the same homework again so
I'm just going to give it to you let's
say that I have two players Alice and
Bob and let's say they have access to
the
internet so let's say they're on a group
chat and everyone else can also see what
messages they're
sending uh so they cannot fake messages
and they cannot also hide the messages
that they have already sent but let's
say they want to play Rock Paper
Scissors now in the real world the way
we do this is by forcing them to move at
the same
time right but if I just have a group
chat on let's say WhatsApp I can't do
that because even if I give them a very
particular time if I say you have to
write rock or paper or scissors exactly
at
1250 it might be that Bob is cheating
and he just has a script that Waits For
Alice to write the answer and as soon as
she writes the answer Bob takes that
answer calculates what would make him
win and immediately outputs that so if
Alice is playing Rock Bob would
immediately play paper and you cannot
tell the difference between this kind of
cheating and just basic Network
lag right so the question now is how can
we play Rock Paper Scissors in a secure
way in the sense that we want to make
sure neither side can
cheat okay and actually I want you to
think how this relates to the example of
the auction that we saw before because
in some sense you can also think of an
auction as a game and the idea there was
that you should also move before knowing
your opponent's
move and here it's exactly the same
problem so I have to make sure that
Alice moves before knowing what Bob
wants to do and I have to also make sure
that Bob moves before knowing alysis
move okay so I'll see you
tomorrow
関連動画をさらに表示
Blockchain Expert Explains One Concept in 5 Levels of Difficulty | WIRED
ICT Forex Scout Sniper Basic Field Guide - Vol. 6
How to use Popover modifier in SwiftUI | Bootcamp #69
Python Advanced AI Agent Tutorial - LlamaIndex, Ollama and Multi-LLM!
5 Steps to Finding Today's Trades
Ultimate Day Trading Strategy Guide 📚🍏for Beginners (Working in 2024!)
5.0 / 5 (0 votes)