Inter-blockchain Communication via Merkle Proofs with EOS.IO

in #eos4 years ago

Merkle trees are used to enable proofs of user actions to light weight clients. Light weight clients are the foundation of inter-blockchain communication where one blockchain acts as a light-client to another blockchain.

Every user action can be viewed as someone writing a check which gets processed by the bank (blockchain) and if accepted logged. Inter Blockchain communication is about generating proofs that a particular check was accepted and the order of its acceptance relative to other checks written by the same sender or receiver.

Chain A can receive messages from Chain B by following Chain B’s block headers and processing action proofs. Each action proof has one or more sequence numbers which Chain A uses to make sure there are no gaps in processing.

Where as other chains generate a merkle tree over state (account balances), EOS.IO generates a merkle tree over sequenced actions. A light client can derive the balance of a single account by processing all sequenced actions for that account without having to process the actions for other accounts.

In many cases it is not necessary to know the balance of an account, instead all the light client needs to do is verify payment. This can be verified with the proof of a single action.

Blockchains are built on top of deterministic state machines; therefore, inter blockchain communication is most effective when guarantees of completeness and order can be provided. The EOS.IO protocol creates a TCP like communication channel between chains. This means that missing or out of order proofs can be detected.

While you can generates proofs to guarantee no actions are skipped, it is not possible to prove that you have all actions up to the present moment. To prove completeness to the present moment one must generate a transaction, have it included, then generate a proof that the most recent transaction was confirmed with the proper sequence number.

Target Audience

This post is for those curious over the cryptographic design of EOS.IO inter-blockchain communication. With this information you can design and build light weight wallets or integrate with your own blockchain. This text was originally drafted for internal documentation, but we are providing it here for community review and inspection by the curious.

Canonical Trees and Proofs

All of the merkle calculations in EOS.IO share a few conventions that disambiguate entries in a proof without requiring additional space. Given two leaves with respective digests of Da and Db. Their shared parent node in a basic merkle tree would be the digest of the concatenation of Da and Db (Da|Db). However, unless the chosen digest calculation is commutative, Da|Db is not the same as Db|Da. This means that a proof, in the form of a “path” from a leaf to the root of a Merkle tree (sometimes referred to as a “log proof”) must indicate whether the entries in the “path” represent left or right concatenation.

To avoid this extra “path” data in the proof, EOS.IO applies a transform to the leaf digests before concatenating them for the new digest. This transform, indicates whether the digest is on the left or right side of the concatenation. The proof “path” then includes pre-transformed digests making the correct concatenation operation easy to infer.

More precisely, EOS.IO enforces that the first bit of the leaf digest is 0 for “left” digests and 1 for “right” digests. When reading a proof path entry (Dp) and applying it to a given digest (Dn) if the first bit of Dp is 0 then the resulting digest is hash(Dp|Dn) otherwise it is hash(Dn|Dp)

    LET canonical_left := CLEAR_FIRST_BIT(left),
    LET canonical_right := SET_FIRST_BIT(right),
    LET data := CONCATENATE(canonical_left,canonical_right),
(pseudocode for generating a hash form a left and right leaf)

In addition, should construction of a merkle tree require hashing a node with an unknown value, for example in a balanced tree of 3 nodes, the resulting digest is the concatenation of the digest with itself.

    /    \ 
  Dab     Dcc  <- Dc concatenates with itself
 /   \    /
Da   Db  Dc

The Block Merkle

For any Block N, its header includes the root of a balanced merkle tree where the leaves are the block ids for all preceding blocks 0..N-1: the Block Root. This serves as a commitment to the contents of the blockchain, from genesis on, by each new block.

Given any block id for a block in the blockchain, and the headers a trusted irreversible block. It is possible to prove that the block is included in the blockchain. This proof takes ceil(log2(N)) digests for its path, where N is the number of blocks in the chain. Given a digest method of SHA256, you can prove the existence of any block in a chain which contains 100 million blocks in 864 bytes.

The Action Merkle

For any Block N, the headers include the root of a nearly-balanced merkle tree where the leaves are commitments to data generated while processing actions: the Action Root. This can be used to prove existence and, ordering of actions. Additionally, it can be used to prove completeness of transcripts of actions that affect a given scope.

The data committed to for each action, or Action Commitment, is:

receiver: the account name whose contract received the given action
scope: the scope where this action is defined
name: The name of the action (eg: ‘transfer’)
data: the binary encoded data payload delivered to the contract
data_access: an array of sequence numbers for scopes accessed during the processing of this action

This can be used to prove complete transcripts by providing actions and proofs for the sequence numbers between two given actions

Sequence numbers always increment on write operations and never on reads. There will be exactly one action with a write for a given (sequence, scope, receiver)
region_id: the region this action was processed in
cycle_index: the cycle this action was processed in
This can be used to prove ordering constraints
Shards inside a cycle can execute in parallel; there is no deterministic ordering between actions in the same cycle but different shards.

(Example Action Commitment)

For each shard (a unit of parallelizable execution in a cycle) a balanced merkle tree is constructed of these action commitments to generate a temporary shared merkle root. This is done for speed of parallel computation. The block header contains the root of a balanced merkle tree whose leaves are the roots of these individual shard merkle trees. This means that the resulting merkle tree represented by the Action Root is not guaranteed to be a perfectly balanced merkle tree, however, it should be very close in most cases.

Given an action, somewhere in the blockchain, it is possible to succinctly prove the retirement of that action by first proving that it was committed to by a block’s Action Root, and then that the given block was committed to by a trusted irreversible block header’s Block Root. These two proofs are referred to as the “Action Path” and the “Block Path” respectively.

The Action Path consists of all the data (sibling digests from the merkle tree) necessary to recalculate the root of a merkle tree with respect to a single Action Commitment. That merkle tree’s root should exactly match the Action Root committed to by the header of the block that retired the action.

The Block Path consists of all the data necessary to recalculate the root of a merkle tree with respect to a single Block ID. That merkle tree’s root should exactly match the Block Root committed to by the header of a trusted irreversible block.

For example,

Given the action above, retired in a block with the ID:

Whose Action Root was:


And trusted irreversible block whose Block Root is:


That proof data looks like this:

Action Path:
Block Path:

To verify this proof, first serialize the claimed Action Commitment to EOS.IO’s standard binary format. That results in the following binary representation (in hex):


EOS.IO currently uses SHA256 for its digest method(HASH_FN), so the leaf digest is the SHA256 of the above binary representation:


Using that leaf digest, apply the Block Path, referring to the section on canonical paths and signatures to determine if an entry in the path requires left or right concatenation. After applying the complete path, the resulting root digest should be exactly equal to the Action Root in the header of the block that retired the action:

=> 1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
=> 465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
=> dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab
=> ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996
=> 067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57

Once we have verified that the block has a commitment retiring the action as described, we must also verify that the retiring block is included in the blockchain using the Block Path and the retiring block’s id. After applying the complete path, the resulting root digest should be exactly equal to the Block Root in the header of the trusted irreversible block:

=> da16dd856cbb888545c0ed248f2acbbed57037cf407e258849d4600c8f074739
=> da1a4326c7d83cc86f1154e76000ae94a7579833e75d9378972c6f034e044c11
=> d2d0abf4e6d8b771f8de27413ce7c9ca9e443c89fd10c4d42cb37bcc47cb3598
=> c36045ffee9c98eb419077aa356d65fb6a928914c40ec88aadcf634781e56c23
=> 4432bce7431f676ed704f2d3367cb33407898b70f51fea2dfa014b97ac37a97b
=> 94f5ba720b886515ada9c0f73ab393dffc43beaeac7be6f7f86bce808834dfde
=> 1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6


I would like to thank Bart W. for his help in writing this post and implementing this protocol in the eos-noon branch of our github repository.

Disclaimer is a software company and is producing the EOS.IO software as free, open source software. This software may enable those who deploy it to launch a blockchain or decentralized applications with the features described above. will not be launching a public blockchain based on the EOS.IO software. It will be the sole responsibility of third parties and the community and those who wish to become block producers to implement the features and/or provide the services described above as they see fit. does not guarantee that anyone will implement such features or provide such services or that the EOS.IO software will be adopted and deployed in any way.

All statements in this document, other than statements of historical facts, including any statements regarding’s business strategy, plans, prospects, developments and objectives are forward looking statements. These statements are only predictions and reflect’s current beliefs and expectations with respect to future events and are based on assumptions and are subject to risk, uncertainties and change at any time. We operate in a rapidly changing environment. New risks emerge from time to time. Given these risks and uncertainties, you are cautioned not to rely on these forward-looking statements. Actual results, performance or events may differ materially from those contained in the forward-looking statements. Some of the factors that could cause actual results, performance or events to differ materially from the forward-looking statements contained herein include, without limitation: market volatility; continued availability of capital, financing and personnel; product acceptance; the commercial success of any new products or technologies; competition; government regulation and laws; and general economic, market or business conditions. Any forward-looking statement made by speaks only as of the date on which it is made and is under no obligation to, and expressly disclaims any obligation to, update or alter its forward-looking statements, whether as a result of new information, subsequent events or otherwise.


@dan thanks for explaining in details how EOS protocol works. I am a fan of EOS, i even plan to buy more with my steemit earning as soon as i earn more. I believe in EOS that it will do amazing things. Though the post is technical, but i still understand few things through this post. Thanks

Dan, I will never understand everything you talk about as you know but I believe in you.

I also named the Dan Larimer Effect as I started calling it --- today in this article about you and the EOS project, thinking only you can rescue Ethereum with the CryptoKitties mess it is causing!!

Loving EOS right now :)

Me too. I don't know a ton about crypto currency yet but invested in EOS and I hit big 😉

@dan it is amazing all you are doing with the big 3 (eos, bitshares and steem). As @stan wrote, big funds will continue flowing from FIAT to Bitcoin first, and when Bitcoin makes processing slow and transactions are pending for a long time, people will realize the blockchains that are capable of delivering are the big 3, and all bitcoin funds will flow to bitshares, eos and steem. Incredible, but the dream is coming, everyday closer. This 3 blockchains can do everything that is needed. It is great you are communicating a lot on EOS and Bitshares gets lots of communication here too. This helps everyone know the progress and the features and benefits this blockchains will receive. You are the visionary of the this new disrupted era. @gold84

@gold84 You just laid it all out about how I feel about @dan and his Vision of EOS. You and I know that logic will bring the masses to EOS, Bitshares and Steem. It is So Good to be here so Early on....................

@stokjockey glad we are on the same page about @dan and this 3 amazing blockchains. For some reason we came here early, and know each of us have the chance to contribute and collaborate with what we are able to. upvoted your comment! @gold84

Wow, @dan, what an incredible sharing you just posted for us to learn from and marvel at too! A big high hat tip to Bart W. for his work on this post too.

Thanks a lot for your unwavering dedication, you are empowering the world and us all first.

All for one and one for all! Namaste :)

It looks like you are quite the inquirer. Very amusing

Is it possible that someone could hack into my page and steal my SBD? I got a message from someone and they said @null is stealing SBD. Anyway, this is way beyond my understanding of how this all works. I think it would be worth taking a look at. I promoted my post because I had been gone from Steemit for about a month and needed a little post boost. I think because I promoted the post it went into @null account. Can you check it out? Anyway, wishing you a beautiful and blessed day. I am back online.


🎀 @theprettysoul 🎀

When you "promote" a post, the sbd goes to null, which means it's "detroyed" and you get a spot on the promoted page :)

Thanks for the insight I really do appreciate it. Wonderful. Hope everything is going well in your cyber world. :)


Very interesting description of Merkle trees in connection with blockchain technology. Never read this before.

THx again... Ohh can't wait for 2018 and the time eos will be the number 2 coin... I only have 100 but I will keep them for such a long time.... I hope these can help me make some dreams come true

Where is the best place to buy EOS? Do you recommend a certain Wallet ? all you need is chrome and metamask

I understood about a tenth of that and it was still fascinating to read.

Shards sound especially interesting. If I understand correctly (it's unlikely) each shard represents a unit of information processed by a node in parallel?

@dan is the reason I came back to cryptocurrency. I'm pulling for every project he has been a part of.

It is good to get an inspirational individual to motivate the spirit of crypto

Thank you!

Very interesting .... I will need to read this a few times

Can you explain why Steem hasn't seem the same recent gains as EOS has. In October EOS was .50 now it is almost $4.00. You would think with that the price of steem would be closer to 5 or 6 dollars

Suppose it comes down to supply and demand, EOS has a lot of hype and excitement about what might be possible once it's built and therefore it generates a lot more FOMO than something like STEEM

I guess they are working on it

EOS has an all time high of $5 and the blockchain doesn't even exist yet. Wait till June next year. Steemit won't move significantly until it gets migrated to EOS.

Is that likely to happen?

LOL goodluck with that... @ned and @dan don't see eye to eye on some things.

Steem has systemic problems. It is gamed and manipulated and the whales wont have it any way because they have all the power. Look out for a STEEM clone on EOS share dropped on all EOS holders.

Hi Dan! Thank you for continuing to turn up and share information about EOS! I'm happy to be getting my hands on a few tokens here and there!

For those of us without a broad technical background, what can we do to be a part of this? Other than collecting tokens and telling people that we are excited about EOS.... is there something we should be doing to participate in this phase of things? Or is it still too early for those without a lot of technical know how?


EOS the game changer!

My grandchildren are going to do projects about you at school.

how old are they now???

I don't have any yet. My oldest child is 7, so his kids are still a ways off :)

So YOUR kids might be reading about Dan in high school then!

They'll be learning about him, but at home. School's always at least a generation behind.

ha ha, fair enough. At LEAST a generation behind is right, if they ever get there at all!

schools out for summer

I did not understand a single thing, but happy that I am up 500%.....

I'm in same boat, except unhappy that it's up so much because I wanted to get as much as possible at a cheap price

If you really really really believe in this project like I do, put in some more every week.. Say $20 a week, depends on you. The thing with this project is that it's still on its ICO stage. I don't know how the price it will be after. Uncertainties are the walls for opportunities. It's up to you to take those risks or minimize those by dollar averaging on your fav token.

Yeh that's what I have been doing, just would have been nice to have a bit longer to accumulate at that lower price!

Wouldn't we all. This price hike though is remarkable. Within days it happened and still gaining. Like you I was waiting for the traders to start selling but it never happened. Majority is probably waiting for $10 and cash out. That's my speculation anyway. Anything can happen.

It's possible although I'm sure a lot of EOS holders are holding long term. I know I won't be selling at $10!

Sell at 1000.. possible.. when the kitty craze has broken ethereum network. Still a long way though, keep forgetting we are still in the ico stage lol.

Read again and again, and want to know how EOS protocol works. Thanks @dan

Given a digest method of SHA256, you can prove the existence of any block in a chain which contains 100 million blocks in 864 bytes.
only 3 years back if we have 1 block per second?

Great post I need to study alot

Dan, I aspire to be as brilliant as you one day. ...

Nice information @dan...
may I translate your post to indonesia..?

Good sum-up to all things EOS!

Congratulations @dan, this post is the most rewarded post (based on pending payouts) in the last 12 hours written by a Superhero or Legend account holder (accounts hold greater than 100 Mega Vests). The total number of posts by Superhero and Legend account holders during this period was 27 and the total pending payments to posts in these categories was $1769.31. To see the full list of highest paid posts across all accounts categories, click here.

If you do not wish to receive these messages in future, please reply stop to this comment.

Wow, even the Disclaimer is proportional to the article size. Great job sir, you have all my respect for this!

Es fantástico!! No comprendo mucho, pero tener acceso a la información es lo altamente valioso. Muchas gracias y felicitaciones.

Congratulations @dan!
Your post was mentioned in the hit parade in the following category:

  • Pending payout - Ranked 2 with $ 283,98

I Know you are talking about your Eos project, but I need to say welcome back to steemit @dan

have to save this one for later, looks like a very good & usefull reading materal! Thank you for that #upvote !!

Can this phenomenon be seen between two forks of an original blockchain ? thank you for your answer :)


De nada. Estamos para apoyar. Leer y entender que nos estas mostrando . cual es su utilidad y en que beneficia . Normalmente elegimos lo que es necesario o nos beneficia de uno manera u otra

I don't understand, why the flags?

@dan, Sorry about this comment is a little of topic, but I want to find a way to address Steemit users proposals to enhance Steemit environment.

I just read a post about creating channels in our blogs and I think that this will be a great improvement.

Also I miss more sophisticated peer to peer (user to user) instant messaging.

Can you help me and direct me to someone who can do something about
this issues.

Greetings from Slovenia, one of the most crypto friendly countries!

I'm also programmer and could be of some use.

Follow me for more football updates

Have you heard about cryptocurrency,if yes then you have to wake up now and make investment.lets look at this thing for instance,five years ago,bitcoins was just $100.yes!
Those who invested at that time and bought more bitcoins are the millionaires we see bitcoin sells more than $16,000.yes! See the massive change.imagine you had bought just 10bitcoins at that time,for just $ will be selling one for $16000 by now.woow.bitcoin is the new generation now.stand up now or regret later.
The best place to invest your money is
Visit this site and invest as minimum as $10 and gain profit your entire life.follow me for more updates on crypto


You can find Russian version of this post HERE

Русская версия тут

What about communication offline? IOTA is looking to do something like that with bluetooth and other protocols. Will EOS have some kind of offline communication @Dan

Dear dan
This comment has nothing to do with this article, I just wanted to let you know that you are absolutely awesome.

Hi @dan really following EOS project. I want to ask you something
let's say i want to develop a steemit like app on eos with different characteristics, having advertising and some other stuffs and be compliant with the law of two specific countries for instance. I would design that app with 2 different blockchains(both based on EOS) and use interblockchain communications where users from one blockchain could comunicate with users of the other one(transfers, messages...), would be this a posible solution having good time responses of near real time apps ? or it would be a better solution use the regions(have the blockchain separated by regions where each country could be one ) for that? are regions on EOS designed with that purpose ?

Sorry for resurrecting this old post. I'll pull down the source in a bit, but hoping for some clarity on 1 thing.

You said: Using that leaf digest, apply the Block Path. Should that not be the action path? I'm not sure if I understand your terminology incorrectly, or if the paragraph is wrong. Thanks in advance.

Spamming comments is frowned upon by the community.

Comment spam is currently defined by @steemcleaners as:

  • 10 or more generic comments per day that are not in response to a question posed by the post or comment. “Thanks”, “Great Post!”, “Great Photo!”, “Good”, “Like”, “Nice”, “Wow”, “Cute”, “Follow me”, etc.

  • Commenting on old posts to hide self up-votes or a voting trail.

  • Copy/Paste comments that serve no purpose or the purpose is self promotion.

  • Comments that inform the contributor that they have been up upvoted, resteemed, or flagged when the curator does not actually upvote, resteem, or flag the post.

  • Unsolicited and off topic referral links.

Continued comment spamming may result in action from the cheetah bot.

More Info: Abuse Guide - 2017.

Please don't SPAM... take a look in this before hurting your reputation.