Lecture 3 - Merkle Trees

Summary

本视频讨论了银行两个分行间的资金转移问题，提出了一种通过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

00:00

🏦 银行分支间资金转移问题

视频脚本讨论了一个银行两个分支（香港和伦敦）之间的资金转移问题。客户在香港存款，并希望在伦敦取款。银行只能发送一条消息（M）给伦敦分支，这条消息通过不安全的渠道传输，任何人都可以看到，但无法更改。香港分支给每个存款人一个证明（P1, P2, P3, P4），这些证明是二进制字符串。目标是确保每个存款人都能取款，但只能取一次，同时不泄露任何个人信息。

05:02

🔗 使用哈希指针的链表解决方案

提出了一种使用链表和哈希指针的解决方案，通过创建交易并链接它们，每个交易包含付款人信息和金额。通过哈希指针连接交易，形成链表。为了验证交易的存在，客户需要提供从链表末尾到其交易的路径。这种方法的问题是证明太长，且泄露了所有交易信息，不符合隐私要求。

10:03

🔒 隐私保护和短证明的需求

讨论了如何通过使用哈希函数来保护客户隐私，避免泄露个人信息。同时，提出了短证明的需求，即如何减少验证交易存在所需的信息量。

15:04

🌳 利用Merkle树优化证明长度

介绍了Merkle树（奇迹树）的概念，通过构建一个二叉树结构来优化证明长度。每个交易都有一个哈希值，树的根节点是所有交易哈希值的哈希。这样，证明一个交易的存在只需要提供从根节点到该交易的路径上的节点，大大减少了证明的长度。

20:06

🔐 提供交易存在的证明

详细说明了如何使用Merkle树为每个客户提供其交易存在的证明。客户需要提供根哈希值和从根节点到其交易的路径上的节点哈希值，以证明其交易确实存在于树中。

25:10

📈 优化Merkle树以支持实时交易

讨论了如何优化Merkle树以支持实时交易。提出了一个问题，即如何在不知道所有交易的情况下创建Merkle树，这需要在所有存款完成后才能进行。

30:10

🔎 证明特定项不在Merkle树中

探讨了如何证明一个特定项不在Merkle树中，通过使用排序的Merkle树来简化这一过程。通过证明一个特定值前后的值，可以间接证明该值不存在。

35:11

🤼‍♀️ 在线游戏的安全性问题

提出了一个在线游戏（如剪刀石头布）的安全性问题，即如何确保游戏双方不作弊，同时保持游戏的公平性。这个问题与之前的拍卖例子相似，都需要确保双方在不知道对方选择的情况下做出决定。

Keywords

💡银行分支

在视频中，银行分支是指分别位于香港和伦敦的两个银行网点。这两个分支通过一个不安全的通道进行通信，以处理客户存款和取款的业务。香港分支负责收集客户的存款信息，并通过发送一条消息给伦敦分支，使得客户能够在伦敦分支取回他们的资金。

💡不安全通道

不安全通道指的是一个通信路径，虽然消息不能被篡改，但是可以被任何能够访问该通道的人看到。在视频中，香港分支通过这个通道向伦敦分支发送消息，而这条消息可能被黑客拦截并公开，但内容无法被更改。

💡数字签名

数字签名是一种用于验证电子文档真实性的技术，确保消息或文件未被篡改，并确认发送者的身份。在视频中，虽然提到了数字签名，但并未深入讨论其具体实现和作用。数字签名在确保消息M的安全性和验证其来源方面起着关键作用。

💡存款证明

存款证明是银行为客户提供的一种凭证，证明客户在银行存有特定金额的资金。在视频中，香港分支给每个存款人一个证明，这个证明是一串数字，客户可以凭借这个证明在伦敦分支取回他们的钱。

💡双重支付

双重支付是指同一个货币被使用两次或以上的情况，这在数字货币和电子交易中是一个需要解决的问题。在视频中，提到了设计一个系统来防止双重支付的问题，即确保每个存款只能被取款一次。

💡数据泄露

数据泄露是指敏感或私密信息被未经授权的人访问或公开。在视频中，提到了设计系统时的一个要求，即不能通过消息M泄露存款人的个人信息和存款金额。

💡Merkle树

Merkle树，也称为奇迹树，是一种用于验证大量数据的树状数据结构。在视频中，通过构建一个Merkle树，可以有效地证明某个数据项是否存在于整个数据集中，同时保持数据的隐私性。

💡隐私保护

隐私保护是指采取措施保护个人信息不被未经授权的访问或公开。在视频中，设计系统时的一个重要要求是确保客户在验证存款记录时不会泄露其他客户的个人信息。

💡链表与哈希指针

链表是一种线性数据结构，其中的每个元素都指向下一个元素。哈希指针是链表中的一种特殊指针，它通过哈希值而不是直接通过链接指向前一个元素。在视频中，最初的想法是使用链表和哈希指针来构建一个系统，但这种方法最终因为证明太长和隐私问题而被放弃。

💡二叉树

二叉树是一种每个节点最多有两个子节点的树状数据结构，通常用于提高数据检索的效率。在视频中，通过使用二叉树而不是链表，可以减少验证存款记录所需的步骤，从而缩短证明的长度。

💡实时性问题

实时性问题指的是在需要立即响应或处理的情况下，系统可能无法满足时间要求的问题。在视频中，构建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