<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Roman Kashitsyn on Medium]]></title>
        <description><![CDATA[Stories by Roman Kashitsyn on Medium]]></description>
        <link>https://medium.com/@roman-kashitsyn?source=rss-23896498b45e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*3tCRt4Z7bYXjsDYG569j9A.jpeg</url>
            <title>Stories by Roman Kashitsyn on Medium</title>
            <link>https://medium.com/@roman-kashitsyn?source=rss-23896498b45e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 07:37:21 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@roman-kashitsyn/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Building Effective Rust Canister Smart Contracts: Useful Patterns]]></title>
            <link>https://medium.com/dfinity/building-effective-rust-canister-smart-contracts-patterns-and-pitfalls-d019221061b2?source=rss-23896498b45e------2</link>
            <guid isPermaLink="false">https://medium.com/p/d019221061b2</guid>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[rust-programming-language]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Roman Kashitsyn]]></dc:creator>
            <pubDate>Mon, 10 Oct 2022 14:30:13 GMT</pubDate>
            <atom:updated>2022-10-20T18:44:22.424Z</atom:updated>
            <content:encoded><![CDATA[<h4>Technical considerations for creating and deploying Rust canisters on the Internet Computer blockchain.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rkHNr8qpEy6SbVwcxMVUbQ.png" /></figure><h3>How to read this document</h3><p>This document is a compilation of useful patterns and typical pitfalls I observed in the Rust code running on the <a href="https://internetcomputer.org/">Internet Computer</a> (IC). Take everything in this document with a grain of salt: solutions that worked well for my problems might be suboptimal for yours. Every piece of advice comes with explanations to help you reach your own judgment.</p><p>Some recommendations might change if I discover better patterns or if the state of the ecosystem improves. I will try to keep this document up to date.</p><p><a href="https://internetcomputer.org/docs/current/developer-docs/build/cdks/cdk-rs-dfinity/rust-quickstart">Internet Computer Home | Internet Computer Home</a></p><h3>Code organization</h3><h4>Canister state</h4><p>The way IC canisters are structured forces developers to use a global mutable state. Rust, on the other hand, intentionally makes it hard to use global mutable variables, giving you a few options to choose from. Which option is the best?</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#use-threadlocal"><strong>☛</strong></a><strong> <em>Use </em></strong><strong><em>thread_local! with </em></strong><strong><em>Cell/</em></strong><strong><em>RefCell for state variables.</em></strong></p><p>This option is the safest one. It will help you avoid memory corruption and issues with asynchrony.</p><pre>thread_local! {<br>    static NEXT_USER_ID: Cell&lt;u64&gt; = Cell::new(0);<br>    static ACTIVE_USERS: RefCell&lt;UserMap&gt; = RefCell::new(UserMap::new());<br>}</pre><p>Let us look at some other options you might find in the wild and see what is wrong with them.</p><ol><li>let state = ic_cdk::storage::get_mut&lt;MyState&gt;;<br>The Rust CDK provides <a href="https://docs.rs/ic-cdk/0.3.2/ic_cdk/storage/index.html">storage</a> abstraction that allows you to get a mutable reference indexed by a type. In my opinion, introducing this abstraction was not a good design choice. <a href="https://docs.rs/ic-cdk/0.3.2/ic_cdk/storage/fn.get_mut.html">get-mut</a> allows you to obtain multiple non-exclusive mutable references to the same object, which breaks language guarantees. You can easily shoot yourself in a foot with this, I will show you how in a minute.</li><li>static mut STATE: Option&lt;State&gt; = None;<br>Plain old global variables. This approach forces you to write some boilerplate to access the global state and suffers from the same safety issues as the previous one.</li><li>lazy_static! { static STATE: RwLock&lt;MyState&gt; = RwLock::new(MyState::new()); } <br>This approach is memory-safe, but I find it confusing. Threading is not available in canisters, so it is not obvious what happens if you try to obtain a lock for an already locked object. A canister cannot block, so it traps if it fails to obtain a lock. Which means that the meaning of your program changes depending on the compilation target (wasm32-unknown-unknown vs native code). <strong>We do not want that.</strong> <em>[See “Make most of the canister code target-independent” below.]</em></li></ol><p>Let us see how non-exclusive mutable references can lead to bugs that are hard to track down. At first it might seem that if you do not have concurrency involved, there should be no harm. Unfortunately, that is not true. Let us look at an example.</p><pre>#[update]<br>fn register_friend(uid: UserId, friend: User) -&gt; Result&lt;UserId, Error&gt; {<br>    let mut_user_ref = storage::get_mut&lt;Users&gt;() ①<br>                           .find_mut(uid)<br>                           .ok_or(Error::NotFound)?;</pre><pre>let friend_id = storage::get_mut&lt;Users&gt;().add_user(&amp;friend); ②</pre><pre>mut_user_ref.friends.insert(friend_id); ③</pre><pre>Ok(friend_id)<br>}</pre><p>Here we have a function that uses the storage abstraction, but plain old mutable globals have the same issue.</p><ol><li>We get a mutable reference pointing into our data structure.</li><li>We call a function that modifies the data structure. This call might have invalidated the reference we obtained in step ①, so now the reference could be pointing to garbage or into the middle of another valid object.</li><li>We use the original mutable reference to modify the object. This might lead to heap corruption.</li></ol><p>Real code might be much more complicated, the mutation might happen in a function called from a function called from the canister method, etc. The issue might have stayed undetected until your canister is in active use and stores (and corrupts) important user data. If we used a RefCell, we would get a panic before this code is shipped (assuming you ran the code at least once before shipping).</p><p>It should be now clear <em>how</em> to declare global variables. Let us discuss <em>where</em> to put them.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#clear-state"><strong>☛</strong></a><strong> <em>Put all your globals in one basket.</em></strong></p><p>Consider making all the global variables private and placing them in a single file, the canister main file. This approach has a few benefits:</p><ul><li>Testing is easier because most of your code doesn’t touch the globals directly.</li><li>It is easier to understand how the global state is used. For example, checking that all the stable data is properly persisted across upgrades is trivial.</li></ul><p>Consider also adding comments clarifying which variables are stable, like in example below:</p><pre>thread_local! {<br>    /* <strong>stable</strong>   ① */ static USERS: RefCell&lt;Users&gt; = ... ;<br>    /* <strong>flexible</strong> ② */ static LAST_ACTIVE: Cell&lt;UserId&gt; = ...;<br>}</pre><p>I borrowed <a href="https://sdk.dfinity.org/docs/language-guide/upgrades.html#_declaring_stable_variables">Motoko terminology</a> here:</p><ol><li><em>stable</em> variables are globals that the system preserves across upgrades. For example, a user database should probably be stable.</li><li><em>flexible</em> variables are globals that the system discards on code upgrade. For example, it is reasonable to make a cache flexible if keeping this cache hot is not critical for your product.</li></ol><p>If you ever tried to test canister code, you probably noticed that this part of the development workflow is not polished yet. A quick way to make your life easier is to piggyback on the existing Rust infrastructure. This is possible only if we can compile the canister both to native target and to WebAssembly.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#target-independent"><strong>☛</strong></a><strong> <em>Make most of the canister code target-independent.</em></strong></p><p>It pays off to factor most of the canister code into loosely coupled modules and packages and to test them independently. Most of the code that depends on the System API should go into the main file.</p><p>It is also possible to create a thin abstractions for the System API and test your code with a fake but faithful implementation. For example, we could use the following trait to abstract the <a href="https://sdk.dfinity.org/docs/interface-spec/index.html#system-api-stable-memory">stable memory API</a>:</p><pre>pub trait Memory {<br>    fn size(&amp;self) -&gt; WasmPages;<br>    fn grow(&amp;self, pages: WasmPages) -&gt; WasmPages;<br>    fn read(&amp;self, offset: u32, dst: &amp;mut [u8]);<br>    fn write(&amp;self, offset: u32, src: &amp;[u8]);<br>}</pre><h4>Asynchrony</h4><p>panics and traps in canisters are somewhat special. If your code traps or panics, the system rolls back the state of the canister to the latest working snapshot. Unfortunately, this means that if your canister made a call and then panicked in the callback, the canister might never release the resources it allocated for the call.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#panic-await"><strong>☛</strong></a><strong> <em>Don’t panic after </em></strong><strong><em>await</em></strong></p><p>Let us look at an example.</p><pre>#[update]<br>async fn update_avatar(user_id: UserId, <strong>pic: ByteBuf</strong> ① ) {<br>    let key = store_async(user_id, &amp;pic)<br>                  <strong>.await</strong>      ②<br>                  <strong>.unwrap()</strong>;  ③<br>    USERS.with(|users| set_avatar_key(user_id, key));<br>}</pre><ol><li>The method receives a byte buffer with an avatar picture.</li><li>The method issues a call to the storage canister. The byte buffer is captured in a Rust future allocated on the heap.</li><li>If the call fails, the canister panics. The system rolls back the canister state to the snapshot created right before the callback invocation. From the canister’s point of view, it still waits for the reply and keeps the future and the buffer on the heap.</li></ol><p>Note that there is no corruption, the canister is still in a valid state, but some resources, like memory, will never be released until the next upgrade.</p><p>The System API was recently extended to deal with that problem (see ic0.call_on_cleanup in the <a href="https://sdk.dfinity.org/docs/interface-spec/index.html">Internet Computer Interface Specification</a>). This issue is likely to be fixed in future versions of the Rust CDK.</p><p>Another problem that you might experience with asynchrony and miss in tests is a future that obtains exclusive access to some resource for a long period of time.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#dont-lock"><strong>☛</strong></a><strong><em> Don’t lock shared resources across await boundaries.</em></strong></p><pre>#[update]<br>async fn refresh_profile_bad(user_id: UserId) {<br>   let users = <strong>USERS_LOCK.write().unwrap()</strong>; ①<br>   if let Some(user) = users.find_mut(user_id) {<br>       if let Ok(profile) = async_get_profile(user_id)<strong>.await</strong> { ②<br>           user.profile = profile;<br>       }<br>   }<br>}</pre><pre>#[update]<br>fn add_user(user: User) {<br>    let users = <strong>USERS_LOCK.write().unwrap()</strong>; ③<br>    // ...<br>}</pre><ol><li>We obtain exclusive access to the users map and make an async call.</li><li>The canister state is committed right after the call suspends. The user map stays locked.</li><li>Other methods trying to access the map will panic until the call issued in step ② completes.</li></ol><p>This issue becomes quite nasty when combined with panics: if you lock an important resource and then panic after await, the resource stays locked forever.</p><p>We’re now ready to appreciate another benefit of <a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#use-threadlocal">using </a><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#use-threadlocal">thread_local! for global variables</a>. The code above wouldn&#39;t have compiled if we used thread_local!. One simply cannot await an async function from a closure that accesses thread-local variables:</p><pre>#[update]<br>async fn refresh_profile(user_id: UserId) {<br>    <strong>USERS.with</strong>(|users| {<br>        if let Some(user) = users.borrow_mut().find_mut(user_id) {<br>            if let Ok(profile) = async_get_profile(user_id)<strong>.await</strong> {<br>                <strong>// The closure is synchronous, cannot await ^^^</strong><br>                // ...<br>            }<br>        }<br>    });<br>}</pre><p>The compiler nudges you to write the code correctly (though, admittedly, less elegantly):</p><pre>#[update]<br>async fn refresh_profile(user_id: UserId) {<br>    if !USERS.with(|users| users.borrow().has_user(user_id)) {<br>        return;<br>    }<br>    if let Ok(profile) = async_get_profile(user_id).await {<br>        USERS.with(|users| {<br>            if let Ok(user) = users.borrow_mut().find_user(user_id) {<br>                user.profile = profile;<br>            }<br>        })<br>    }<br>}</pre><h4>Canister interfaces</h4><p>Many people enjoy the code-first approach supported by the Motoko compiler: you write an actor with some public functions, and the compiler automatically generates the corresponding Candid file. That is indeed a useful feature, especially in the early stages of development.</p><p>I’ll try to persuade you that it should be the other way around for canisters that have clients: the Candid file should be the source of truth, not the implementation.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#candid-file"><strong>☛</strong></a><strong> <em>Make your .did file the source of truth.</em></strong></p><p>Your Candid file is the main source of documentation for people who want to interact with your canister (including your own team members who work on the front end). The interface should be stable, easy to find, and well documented. Which is not something you can get automatically.</p><pre>type TransferError = variant {<br>  // The debit account didn&#39;t have enough funds<br>  // for completing the transaction.<br>  InsufficientFunds : Balance;<br>  // ...<br>};</pre><pre>type TransferResult =<br>  variant { Ok : BlockHeight; Err : TransferError; };</pre><pre>service {<br>  // Transfer funds between accounts.<br>  transfer : (TransferArgs) -&gt; (TransferResult);<br>}</pre><p>You might ask, “How do I make sure that my .did file and my implementation are in sync”? And that is a great question. The answer is, “Use the Candid tooling”:</p><ul><li>There are macros in the Rust CDK that allow you to annotate your Canister methods and extract the .did file.</li><li>The latest versions of the candid package have functions to check that one interface is a subtype of another interface, which is a Candid term for “backward compatible”.</li></ul><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#errors-variant"><strong>☛</strong></a><strong> <em>Use variant types to indicate error cases.</em></strong></p><p>Just as Rust error types make it easy for API consumers to recover from errors correctly, Candid variants can help your clients handle edge cases gracefully. Using variant types is also the <a href="https://sdk.dfinity.org/docs/language-guide/errors.html#_prefer_optionresult_over_exceptions_where_possible">preferred way of handling errors in Motoko</a>.</p><pre>type CreateEntityResult = variant {<br>  Ok  : record { entity_id : EntityId; };<br>  Err : opt variant {<br>    EntityAlreadyExists : null;<br>    NoSpaceLeftInThisShard : null;<br>  }<br>};</pre><pre>service : {<br>  create_entity : (EntityParams) -&gt; (CreateEntityResult);<br>}</pre><p>Note, however, that even if a service method returns a result type, it can still reject the call. There is probably not much benefit from adding error variants like InvalidArgument or Unauthorized. There is no meaningful way to recover from such errors programmatically. So rejecting malformed, invalid, or unauthorized requests is probably the right thing to do in most cases.</p><p>So you decided to follow the advice and represented your errors as a variant. How do you add more error constructors as your interface evolves?</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#candid-variant-extensibility"><strong>☛</strong></a><strong> <em>Make your variant types extensible.</em></strong></p><p>Candid variant types are tricky to evolve in a backward-compatible manner. One approach is to make the variant field optional:</p><pre>type CreateEntityResult = variant {<br>  Ok : record { /* */ };<br>  Err : <strong>opt</strong> variant { /* * /}<br>};</pre><p>If some clients of your canister use an outdated version of your interface, the Candid decoder could replace unknown constructors with a null. This approach has two main issues:</p><ul><li>The Candid decoder does not yet implement this magic (see <a href="https://github.com/dfinity/candid/issues/295">dfinity/candid#295</a>).</li><li>Diagnosing a problem if all you see is a null might be a daunting task.</li></ul><p>An alternative is to make your error type immutable and rely on a loosely typed catch-all case (and documentation) for extensibility.</p><pre>type CreateEntityResult = variant {<br>  Ok : record { /* */ };<br>  Err : variant {<br>    EntityAlreadyExists : null;<br>    NoSpaceLeftInThisShard : null;<br>    // Currently defined errors<br>    // ========================<br>    // error_code = 401 : Unauthorized.<br>    // error_code = 429 : Too many requests.<br>    // error_code = 503 : Canister overloaded.<br>    Other : record { error_code : nat; error_message : text }<br>  }<br>};</pre><p>If you follow this approach, your clients will see a nice textual description if they experience a newly introduced error. Unfortunately, handing generic errors programmatically is more cumbersome and error-prone compared to well-typed extensible variants.</p><h3>Optimization</h3><h4>Reducing cycle consumption</h4><p>The first step towards an optimized system is profiling.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#instruction-counter"><strong>☛</strong></a><strong> <em>Measure the number of instructions your endpoints consume.</em></strong></p><p>The <a href="https://docs.rs/ic-cdk/0.5.3/ic_cdk/api/fn.instruction_counter.html">instruction_counter</a> API will tell you the number of <em>instructions</em> your code consumed since the last <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/#entry-points">entry point</a>. Instructions are the internal currency of the IC runtime. One IC instruction is the <a href="https://en.wikipedia.org/wiki/Quantum">quantum</a> of work that the system can do, such as loading a 32-bit integer from a memory address. The system assigns an instruction cost equivalent to each <a href="https://sourcegraph.com/github.com/dfinity/ic@cfdbbf5fb5fdbc8f483dfd3a5f7f627b752d3156/-/blob/rs/embedders/src/wasm_utils/instrumentation.rs?L155-177">webassembly instruction</a> and <a href="https://sourcegraph.com/github.com/dfinity/ic@cfdbbf5/-/blob/rs/embedders/src/wasmtime_embedder/system_api_complexity.rs?L40-107">system call</a>. It also defines all its limits in terms of instructions. As of July 2022, these limits are:</p><ul><li>One message execution: <a href="https://github.com/dfinity/ic/blob/7d3fb4ef01416241205818450156aabd21c24b34/rs/config/src/subnet_config.rs#L19">5 billion</a> instructions.</li><li>One round: <a href="https://github.com/dfinity/ic/blob/7d3fb4ef01416241205818450156aabd21c24b34/rs/config/src/subnet_config.rs#L46">7 billion</a> instructions. (<em>Each block produced by consensus initiates a round of execution.</em>)</li><li>Canister upgrade: <a href="https://github.com/dfinity/ic/blob/7d3fb4ef01416241205818450156aabd21c24b34/rs/config/src/subnet_config.rs#L56">200 billion</a> instructions.</li></ul><p>Instructions are not cycles, but there is a <a href="https://github.com/dfinity/ic/blob/c01d7d1b2e18490a2f70d2fdf5b6aceccab5860c/rs/cycles_account_manager/src/lib.rs#L730-L738">simple linear function</a> that converts instructions to cycles. As of July 2022, ten instructions are equivalent to four cycles on an <a href="https://github.com/dfinity/ic/blob/7d3fb4ef01416241205818450156aabd21c24b34/rs/config/src/subnet_config.rs#L288-L289">application</a> subnet.</p><p>Note that the value that performance_counter returns has meaning only within a single execution. You should not compare values of the instruction counter measured across async boundaries.</p><pre>#[update]<br>async fn transfer(from: Account, to: Account, amount: Nat) -&gt; Result&lt;TxId, Error&gt; {<br>  let start = ic_cdk::api::instruction_counter();</pre><pre>let tx = apply_transfer(from, to, amount)?;<br>  let tx_id = archive_transaction(tx).<strong>await</strong>?;</pre><pre><em>// </em><strong><em>BAD</em></strong><em>: the await point above resets the instruction counter.</em><br>  let end = ic_cdk::api::instruction_counter();<br>  record_measurement(end - start);</pre><pre>Ok(tx_id)<br>}</pre><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#serde-bytes"><strong>☛</strong></a><strong> <em>Encode byte arrays using the </em></strong><a href="https://crates.io/crates/serde_bytes"><strong><em>serde_bytes</em></strong></a><strong><em> package.</em></strong></p><p><a href="https://github.com/dfinity/candid">Candid</a> is the standard interface definition language on the IC. The Rust implementation of Candid relies on a popular <a href="https://serde.rs/">serde</a> framework and inherits all of serde’s quirks. One such quirk is the inefficient encoding of byte arrays (Vec&lt;u8&gt; and [u8]) in most serialization formats. Due to Rust <a href="https://rust-lang.github.io/rfcs/1210-impl-specialization.html">limitations</a>, serde cannot treat byte arrays specially and encodes each byte as a separate element in a generic array, increasing the number of instructions required to encode or decode the message (often by a factor of ten or more).</p><p>The HttpResponse from the canister HTTP protocol is a good example.</p><pre>#[derive(CandidType, Deserialize)]<br>struct HttpResponse {<br>    status_code: u16,<br>    headers: Vec&lt;(String, String)&gt;,<br>    <em>// </em><strong><em>BAD</em></strong><em>: inefficient</em><br>    body: Vec&lt;u8&gt;,<br>}</pre><p>The body field can be large; let us tell serde to encode this field more efficiently using the <a href="https://serde.rs/field-attrs.html#with">with</a> attribute.</p><pre>#[derive(CandidType, Deserialize)]<br>struct HttpResponse {<br>    status_code: u16,<br>    headers: Vec&lt;(String, String)&gt;,<br>    <em>// </em><strong><em>OK</em></strong><em>: encoded efficiently</em><br>    #[serde(with = &quot;serde_bytes&quot;)]<br>    body: Vec&lt;u8&gt;,<br>}</pre><p>Alternatively, we can use the <a href="https://docs.serde.rs/serde_bytes/struct.ByteBuf.html">ByteBuf</a> type for this field.</p><pre>#[derive(CandidType, Deserialize)]<br>struct HttpResponse {<br>    status_code: u16,<br>    headers: Vec&lt;(String, String)&gt;,<br>    <em>// </em><strong><em>OK</em></strong><em>: also efficient</em><br>    body: serde_bytes::ByteBuf,<br>}</pre><p>I wrote a tiny canister to measure the savings.</p><pre>#[query(manual_reply = true)] <br>fn http_response() -&gt; ManualReply&lt;HttpResponse&gt; {     <br>    let start = ic_cdk::api::instruction_counter();     <br>    let reply = ManualReply::one(HttpResponse {         <br>        status_code: 200,         <br>        headers: vec![(&quot;Content-Length&quot;.to_string(), &quot;1000000&quot;.to_string())],         <br>        body: vec![0; 1_000_000],     <br>    });     <br>    let end = ic_cdk::api::instruction_counter();         <br>    ic_cdk::api::print(format!(&quot;Consumed {} instructions&quot;, end - start));     <br>    reply }</pre><p><em>(A canister endpoint measuring the number of instructions required to encode an HTTP response. We have to use a </em><a href="https://docs.rs/ic-cdk/latest/ic_cdk/api/call/struct.ManualReply.html"><em>ManualReply</em></a><em> to measure the encoding time.)</em></p><p>The unoptimized version consumes 130 million instructions to encode one megabyte, and the version with serde_bytes needs only 12 million instructions.</p><p>In the case of the <a href="https://github.com/dfinity/internet-identity/">Internet Identity</a> canister, this change alone reduced the instruction consumption in HTTP queries by <a href="https://github.com/dfinity/internet-identity/pull/184">order of magnitude</a>. You should apply the same technique for all types deriving serde’s Serialize and Deserialize traits, not just for types you encode as Candid. A <a href="https://github.com/dfinity/ic/commit/1b98a5d984176b1c948d0cb92227d88ad5ee8044">similar change</a> boosted the ICP ledger archive upgrades (the canister uses <a href="https://cbor.io/">cbor</a> for state serialization).</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#avoid-copies"><strong>☛</strong></a><strong> <em>Avoid copying large values.</em></strong></p><p>Experience shows that canisters spend a lot of their instructions copying bytes. (Spending a lot of time in memcpy and memset is a common trait of many WebAssembly programs. That observation led to the <a href="https://github.com/WebAssembly/bulk-memory-operations/blob/dcaa1b6791401c29b67e8cd7929ec80949f1f849/proposals/bulk-memory-operations/Overview.md">bulk memory operations</a> proposal included in the <a href="https://webassembly.github.io/spec/core/appendix/changes.html?highlight=proposals#bulk-memory-and-table-instructions">WebAssembly 2.0 release</a>.) Reducing the number of unnecessary copies often affects cycle consumption.</p><p>Let us imagine that we work on a canister that serves a single dynamic asset.</p><pre>thread_local!{<br>    static ASSET: RefCell&lt;Vec&lt;u8&gt;&gt; = RefCell::new(init_asset());<br>}</pre><pre>#[derive(CandidType, Deserialize)]<br>struct HttpResponse {<br>    status_code: u16,<br>    headers: Vec&lt;(String, String)&gt;,<br>    #[serde(with = &quot;serde_bytes&quot;)]<br>    body: Vec&lt;u8&gt;,<br>}</pre><pre>#[query]<br>fn http_request(_request: HttpRequest) -&gt; HttpResponse {<br>    <em>// </em><strong><em>NOTE</em></strong><em>: we are making a full copy of the asset.</em><br>    let body = ASSET.with(|cell| cell.borrow().clone());</pre><pre>HttpResponse {<br>        status_code: 200,<br>        headers: vec![(&quot;Content-Length&quot;.to_string(), body.len().to_string())],<br>        body<br>    }<br>}</pre><p>The http_request endpoint makes a deep copy of the asset for every request. This copy is unnecessary because the CDK encodes the response into the reply buffer as soon as the endpoint returns. There is no need for the encoder to own the body. Unfortunately, the current macro API makes it unnecessarily hard to eliminate copies: the type of reply must have &#39;static lifetime. There are a few ways to work around this issue.</p><p>One solution is to wrap the asset body into a <a href="https://doc.rust-lang.org/std/sync/struct.Arc.html">reference-counting smart pointer</a>.</p><pre>thread_local!{<br>        static ASSET: RefCell&lt;RcBytes&gt; = RefCell::new(init_asset()); }</pre><pre>struct RcBytes(Arc&lt;serde_bytes::ByteBuf&gt;);</pre><pre>impl CandidType for RcBytes { /* */ } <br>impl Deserialize for RcBytes { /* */ }</pre><pre>#[derive(CandidType, Deserialize)] <br>struct HttpResponse {     <br>    status_code: u16,     <br>    headers: Vec&lt;(String, String)&gt;,     <br>    body: RcBytes, }<br>}</pre><p><em>(Using a reference-counting pointer for large values. Note that the type of the </em><em>ASSET variable has to change: all copies of the data must be behind the smart pointer.)</em></p><p>This approach enables you to save on copies without changing the overall structure of your code. A <a href="https://github.com/dfinity/certified-assets/commit/47804eb70f44d2e5c73da26f0009540330293eb2">similar change</a> cut instruction consumption by 30% in the certified assets canister.</p><p>Another solution is to enrich your types with lifetimes and use the <a href="https://docs.rs/ic-cdk/latest/ic_cdk/api/call/struct.ManualReply.html">ManualReply</a> API.</p><pre>use std::borrow::Cow;<br>use serde_bytes::Bytes;</pre><pre>#[derive(CandidType, Deserialize)]<br>struct HttpResponse&lt;&#39;a&gt; {<br>    status_code: u16,<br>    headers: Vec&lt;(Cow&lt;&#39;a, str&gt;, Cow&lt;&#39;a, str&gt;)&gt;,<br>    body: Cow&lt;&#39;a, serde_bytes::Bytes&gt;,<br>}</pre><pre>#[query(manual_reply = true)]<br>fn http_response(_request: HttpRequest) -&gt; ManualReply&lt;HttpResponse&lt;&#39;static&gt;&gt; {<br>    ASSET.with(|asset| {<br>        let asset = &amp;*asset.borrow();<br>        ic_cdk::api::call::reply((&amp;HttpResponse {<br>            status_code: 200,<br>            headers: vec![(<br>                Cow::Borrowed(&quot;Content-Length&quot;),<br>                Cow::Owned(asset.len().to_string()),<br>            )],<br>            body: Cow::Borrowed(Bytes::new(asset)),<br>        },));<br>    });<br>    ManualReply::empty()<br>}</pre><p>This approach allows you to get rid of all the unnecessary copies, but it complicates the code significantly. You should prefer the reference-counting approach unless you have to work with data structures that already have explicit lifetimes (<a href="https://docs.rs/ic-certified-map/0.3.0/ic_certified_map/enum.HashTree.html">HashTree</a> from the <a href="https://crates.io/crates/ic-certified-map">ic-certified-map</a> package is a good example).</p><p>I experimented with a one-megabyte asset and measured that the original code relying on a deep copy consumed 16 million instructions. At the same time, versions with reference counting and explicit lifetimes needed only 12 million instructions. (The 25% improvement shows that our code does little but copy bytes. The code did at least <em>three</em> copies: ① from a thread_local to an HttpResponse, ② from the HttpResponse to candid&#39;s <a href="https://sourcegraph.com/github.com/dfinity/candid@8b742c9701640ca220c356c23c5f834d13150cc4/-/blob/rust/candid/src/ser.rs?L28">value buffer</a>, and ③ from candid&#39;s <a href="https://sourcegraph.com/github.com/dfinity/candid@8b742c9701640ca220c356c23c5f834d13150cc4/-/blob/rust/candid/src/ser.rs?L61">value buffer</a> to the call&#39;s <a href="https://sourcegraph.com/github.com/dfinity/cdk-rs@39cd49a3b2ca6736d7c3d3bf3605e567302825b7/-/blob/src/ic-cdk/src/api/call.rs?L481-500">argument buffer</a>. We removed ⅓ of copies and got ¼ improvement in instruction consumption. So only ¼ of our instructions contributed to work not related to copying the asset&#39;s byte array.)</p><h4>Reducing module size</h4><p>By default, cargo spits out huge WebAssembly modules. Even the tiny <a href="https://github.com/dfinity/cdk-rs/tree/58d276340c2592aa9dcbc4a3e79ef4ac4fca023b/examples/counter/src/counter_rs">counter</a> canister compiles to a whopping 2.2MiB monster under the default cargo release profile. In this section, we shall explore simple techniques for reducing canister sizes.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#compile-size"><strong>☛</strong></a><strong> <em>Compile canister modules with size and link-time optimizations.</em></strong></p><p>The code that the Rust compiler considers fast is not always the most compact code. We can ask the compiler to optimize our code for size with the opt-level = &#39;z&#39; <a href="https://doc.rust-lang.org/cargo/reference/profiles.html#opt-level">option</a>. Unfortunately, that option alone does not affect the counter canister module size.</p><p><a href="https://doc.rust-lang.org/cargo/reference/profiles.html#lto">Link-time optimization</a> is a more aggressive option that asks the compiler to apply optimizations across module boundaries. This optimization slows down the compilation but its ability to prune unnecessary code is crucial for obtaining compact canister modules. Adding lto = true to the build profile shrinks the counter canister module from 2.2MiB to 820KiB. Add the following section to the Cargo.toml file at the root of your Rust project to enable size optimizations:</p><pre>[profile.release]<br>lto = true<br>opt-level = &#39;z&#39;</pre><p>Another option you can play with is <a href="https://doc.rust-lang.org/cargo/reference/profiles.html#codegen-units">codegen-units</a>. Decreasing this option reduces the parallelism in the code generation pipeline but enables the compiler to optimize even harder. Setting codegen-units = 1 in the cargo release profile shrinks the counter module size from 820KiB to 777KiB.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#size-optimizer"><strong>☛</strong></a><strong> <em>Strip off unused custom sections.</em></strong></p><p>By default, the Rust compiler emits debugging information allowing tools to link back WebAssembly instructions to source-level constructs such as function names. This information spans several <a href="https://webassembly.github.io/spec/core/binary/modules.html#custom-section">custom WebAssembly sections</a> that the Rust compiler attaches to the module. Currently, there is no use for debugging information on the IC. You can safely remove unused sections using the <a href="https://github.com/dfinity/ic-wasm">ic-wasm</a> tool.</p><pre>$ cargo install ic-wasm<br>$ ic-wasm -o counter_optimized.wasm counter.wasm shrink</pre><p>The ic-admin shrink step shrinks the counter canister size from 820KiB to 340KiB. ic-wasm is clever enough to preserve custom sections that the <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/#state-tree-canister-information">ic understands</a>.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#twiggy"><strong>☛</strong></a><strong> <em>Use the </em></strong><a href="https://rustwasm.github.io/twiggy/"><strong><em>twiggy</em></strong></a><strong><em> tool to find the source of code bloat.</em></strong></p><p>Some Rust language design choices (for example, <a href="https://rustc-dev-guide.rust-lang.org/backend/monomorph.html">monomorphization</a>) trade execution speed for binary size. Sometimes changing the design of your code or switching a library can significantly reduce of the module size. As with any optimization process, you need a profiler to guide your experiments. The <a href="https://rustwasm.github.io/twiggy/">twiggy</a> tool is excellent for finding the largest functions in your WebAssembly modules. (twiggy needs debug info to display function names. Run it <em>before</em> you shrink your module with ic-wasm.)</p><p>Top contributors to the size of the WebAssembly module of the <a href="https://github.com/dfinity/cdk-rs/tree/58d276340c2592aa9dcbc4a3e79ef4ac4fca023b/examples/counter/src/counter_rs">counter</a> canister. Custom sections with debugging information dominate the output, but we have to keep these sections to see function names in twiggy’s output. Serde-based candid deserializer is the worst offender when it comes to code size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8xFlOHum2ammBfGVVWcNig.png" /></figure><p>Once you have identified the library that contributes to the code bloat the most, you can try to find a less bulky alternative. For example, we shrank the ICP ledger canister module by 600KiB by <a href="https://github.com/dfinity/ic/commit/6f79736085f85dfd01493319816c9a3c9a563b73">switching</a> from <a href="https://crates.io/crates/serde_cbor">serde_cbor</a> to <a href="https://crates.io/crates/ciborium">ciborium</a> for <a href="https://cbor.io/">CBOR</a> deserialization.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#compress-modules"><strong>☛</strong></a><strong> <em>GZip-compress canister modules.</em></strong></p><p>The IC has the concept of a <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/#ic-install_code">canister module</a>, the equivalent of an executable file in operating systems. Starting from <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/#0_18_4">version 0.18.4</a> of the IC specification, canister modules can be not only binary-encoded WebAssembly files but also GZip-compressed WebAssembly files.</p><p>For typical WebAssembly files that do not embed compressed assets, GZip-compression can often cut the module size in half. Compressing the counter canister shrinks the module size from 340KiB to 115KiB (about 5% of the 2.2MiB module we started with!).</p><h3>Infrastructure</h3><h4>Builds</h4><p>People using your canister might want to verify that the canister does what it claims to do (especially if it moves their tokens around). The Internet Computer allows anyone to inspect the SHA256 hash sum of the canister WebAssembly module. However, there are no good tools yet to inspect the source code that the module was built from. It is the developer’s responsibility to provide a reproducible way of building a WebAssembly module from the published sources.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#reproducible-builds"><strong>☛</strong></a><strong> <em>Make canister builds reproducible.</em></strong></p><p>Getting a reproducible build by chance is about as likely as constructing a living organism by throwing random molecules together. There are at least two popular technologies that can help you make your builds more reproducible: <a href="https://linuxcontainers.org/">Linux containers</a> and <a href="https://nixos.org/">Nix</a>. Containers are a more mainstream technology and are usually easier to set up, but Nix also has its share of fans. In my experience, Nix builds also tend to be more reproducible. Use whatever technology you are comfortable with. It is the end result that matters.</p><p>It also helps if you build your module using a public Continuous Integration system so that it is easy to follow the steps that produced your module and download the final artifact.</p><p>Finally, if your code is still evolving, make it easy for people to correlate module hashes with versions of the source code. For example, if you use GitHub releases, mention the module hash in release notes.</p><p>Read the <a href="https://smartcontracts.org/docs/developers-guide/tutorials/reproducible-builds.html">reproducible canister builds</a> article for more advice on reproducible builds.</p><h4>Upgrades</h4><p>Let me remind you how upgrades work:</p><ol><li>The system calls pre_upgrade hook if your canister defines it.</li><li>The system discards canister memory and instantiates the new version of your module. The system does preserve the stable memory, which is now available to the new version.</li><li>The system calls post_upgrade hook on the newly created instance if your canister defines it. The init function is not executed.</li></ol><p>If the canister traps in any of the steps above, the system reverts the canister to the pre-upgrade state.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#plan-for-upgrades"><strong>☛</strong></a><strong> <em>Plan for upgrades from day one.</em></strong></p><p>You can live without upgrades during the initial development cycle, but even then losing state on each deployment quickly becomes annoying. As soon as you deploy your canister to the mainnet, the only way to ship new versions of the code is to carefully plan the upgrades.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#version-stable-memory"><strong>☛</strong></a><strong> <em>Version your stable memory.</em></strong></p><p>You can view stable memory as a communication channel between the old and the new versions of your canister. All good communication protocols are versioned, and yours should be as well. For example, you might want to radically change the stable data layout or serialization format in the future. If the stable memory decoding code needs to <em>guess</em> the data format, it tends to become quite messy and brittle.</p><p>Save your nerve cells, think about versioning in advance. It is as easy as declaring “the first byte of my stable memory is version number”.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#test-upgrades"><strong>☛</strong></a><strong> <em>Always test your upgrade hooks.</em></strong></p><p>Testing upgrades is crucial. If they go wrong, you lose your data irrevocably. Make sure that upgrade tests are an integral part of your infrastructure.</p><p>I’ll describe one approach to testing upgrades that you can use in your integration tests. The idea is that you add an extra optional upgrade step before you execute the state validation part of your test. The pseudo-code below is in Rust, but shell scripts will work just as well.</p><pre>let canister_id = install_canister(WASM);<br>populate_data(canister_id);<br><strong>if should_upgrade { upgrade_canister(canister_id, WASM); }</strong><br>let data = query_canister(canister_id);<br>assert_eq!(data, expected_value);</pre><p>You then run your tests twice in different modes:</p><ol><li>In “no upgrades” mode your tests run normally without executing any upgrades.</li><li>In “upgrade” mode your tests “self-upgrade” the canister under the test.</li></ol><p>This should give you some confidence that if you upgrade your canister, the state is preserved, and the users cannot tell if there was an upgrade or not. Of course, it is also a good idea to test that your canister can be safely upgraded from the previous version.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#upgrade-hook-panics"><strong>☛</strong></a><strong> <em>Do not trap in the </em></strong><strong><em>pre_upgrade hook.</em></strong></p><p>The pre_upgrade and post_upgrade hooks appear to be symmetrical. If either of these hooks traps, the canister goes back to the pre-upgrade state. However, this symmetry is deceptive.</p><p>If your pre_upgrade hook succeeds, but the post_upgrade hook traps, the hope is not lost. You can figure out what went wrong and build another version of your canister that will not fail on the upgrade. You might need to devise a complex multi-stage upgrade procedure, but at least there is a way out.</p><p>On the other hand, if your pre_upgrade hook traps, there is not much you can do about it. Changing canister behavior needs an upgrade, but that is what a broken pre_upgrade hook prevents you from doing.</p><p>The pre_upgrade hook will not let you down if you do not have one. The following advice will help you to get rid of that hook.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#stable-memory-main"><strong>☛</strong></a><strong> <em>Consider using stable memory as your main storage.</em></strong></p><p>There is a cap on how many cycles a canister can burn during an upgrade. If your canister goes over that limit, the system cancels the upgrade and reverts the canister state. This means that if you serialize your whole state to stable memory in the pre_upgrade hook and your state grows huge, you might not be able to upgrade your canister ever again.</p><p>One way of dealing with this issue is to avoid the serialization step in the first place. You can use stable memory as your “disk store”, updating it a little in every update call. This way you might not need the pre_upgrade hook at all, and your post_upgrade hook will need to burn few cycles.</p><p>There are quite a few downsides to this approach, however:</p><ul><li>Organizing the flat address space of stable storage into a data structure is a challenge. This is especially true for complex states consisting of multiple interlinked data structures. As far as I know, there are no good libraries for that yet, but there are a few people working on addressing this issue.</li><li>Changing the layout of your data might be infeasible. It will simply be too much work for a canister to complete the data migration in one go. This might be as hard as writing a program that reformats an eight-gigabyte disk from FAT32 to NTFS without losing any data. By the way, that program must complete in under 5 seconds.</li><li>You need to think carefully about the backward compatibility of your data structures. The latest version of your canister might need to be able to read data written by the version installed a few months ago.</li></ul><p>Overall, it is a tough trade-off between service scalability and code simplicity. If you plan to store gigabytes of state and upgrade the code, using stable memory as the main storage is a good option to consider.</p><h4>Observability</h4><p>At <a href="https://dfinity.org/">DFINITY</a>, we use metrics extensively and record a lot of data about our production services. This is indispensable when you are trying to understand the behavior of a complex distributed system. Canisters are not special in this regard.</p><p><a href="https://mmapped.blog/posts/01-effective-rust-canisters.html#expose-metrics"><strong>☛</strong></a><strong> <em>Expose metrics from your canister.</em></strong></p><p>Let us look at two specific approaches you can take.</p><ol><li>The first approach is to expose a query call that returns a data structure with your metrics. If you do not want to expose this data to everybody for some reason, you can reject queries based on the caller’s principal. One of the main benefits of this approach is that the response is highly structured and easy to parse. I often use this approach in integration tests.</li></ol><pre>pub struct MyMetrics {   <br>  pub stable_memory_size: u32,   <br>  pub allocated_bytes: u32,   <br>  pub my_user_map_size: u64,   <br>  pub last_upgraded_ts: u64, <br>}</pre><pre>#[query] <br>fn metrics() -&gt; MyMetrics {   <br>  check_acl();   <br>  MyMetrics {     <br>    // ...   <br>  } <br>}</pre><p>2. The second approach is to expose the metrics in a format that your monitoring system can slurp directly through the canister HTTP gateway. For example, we use Prometheus for monitoring, so our canisters dump metrics in <a href="https://prometheus.io/docs/instrumenting/exposition_formats/#text-based-format">Prometheus text-based exposition format</a>.</p><pre>fn http_request(req: HttpRequest) -&gt; HttpResponse {   <br>  match path(&amp;req) {     <br>    &quot;/metrics&quot; =&gt; HttpResponse {         <br>        status_code: 200,         <br>        body: format!(r#&quot;<strong>stable_memory_bytes {}<br></strong>                         <strong>allocated_bytes {}</strong>  <br>                         <strong>registered_users_total {}</strong>&quot;#, <br>                      stable_memory_bytes, allocated_bytes, num_users),         <br>        // ...     <br>    }   <br>  } <br>}</pre><p>As you can see, you do not have to link any fancy libraries, the format is simplicity itself. If you need only simple counters and gauges, the format macro will do. Histograms and labels require a bit more work, but you can get quite far with basic tools.</p><p><strong>Some things you might want to keep an eye on:</strong></p><ul><li>The size of the stable memory.</li><li>The size of the objects allocated on the heap (this size is quite easy to get by defining a <a href="https://doc.rust-lang.org/1.50.0/std/alloc/struct.System.html">custom allocator</a>).</li><li>Sizes of internal data structures.</li><li>Last time the canister was upgraded.</li></ul><h3>References</h3><p>Below are a few examples of heavily used Rust canisters you might draw inspiration from.</p><ul><li><a href="https://github.com/dfinity/internet-identity/tree/main/src/internet_identity">Internet Identity backend</a> is a good example of a canister that uses stable memory as the main storage, obtains secure randomness from the system, and exposes Prometheus metrics.</li><li><a href="https://github.com/dfinity/certified-assets">Certified assets canister</a> is a good example of a canister that produces certified HTTP responses.</li></ul><p><strong>____</strong></p><h4>Start building at <a href="https://internetcomputer.org/">internetcomputer.org</a> and join the developer community at <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d019221061b2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/building-effective-rust-canister-smart-contracts-patterns-and-pitfalls-d019221061b2">Building Effective Rust Canister Smart Contracts: Useful Patterns</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Design and Evolution of the ICRC-1 Fungible Token Standard]]></title>
            <link>https://medium.com/dfinity/the-design-and-evolution-of-the-icrc-1-fungible-token-standard-f7f303a33300?source=rss-23896498b45e------2</link>
            <guid isPermaLink="false">https://medium.com/p/f7f303a33300</guid>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[icp]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[crypto]]></category>
            <dc:creator><![CDATA[Roman Kashitsyn]]></dc:creator>
            <pubDate>Mon, 22 Aug 2022 17:01:41 GMT</pubDate>
            <atom:updated>2022-08-23T16:09:26.289Z</atom:updated>
            <content:encoded><![CDATA[<h4>A review of the principles and features behind the Internet Computer’s fungible token standard.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mdd4VOUy4LLr-2Ko6ZXXyA.jpeg" /></figure><p>On August 14th, the overwhelming majority of NNS voters accepted <a href="https://dashboard.internetcomputer.org/proposal/74740">the ICRC-1 Fungible Token Standard</a> proposal for the <a href="https://internetcomputer.org/">Internet Computer</a>. As a member of the <a href="https://forum.dfinity.org/t/announcing-token-standard-as-topic-of-the-first-meeting-of-the-ledger-tokenization-working-group/11925/1">Ledger &amp; Tokenization Working Group</a>, I feel humbled by the community’s trust and support.</p><p>Many people contacted me after the vote to learn more about the standard, motivating me to write this article. I will explain the reasoning behind the Working Group decisions, highlight interesting features of the accepted standard, and outline future work.</p><h3>Design principles</h3><p>If you were to ask five different programmers to each design an application programming interface, the diversity of their solutions might surprise you. People make decisions and design software based on their values and priorities.</p><p>Knowing the principles that the Working Group followed when designing the standard will help you better understand the final product.</p><h4>Interoperability</h4><p>The compatibility of the new standard with the existing infrastructure was the primary concern of the Working Group.</p><p>Hundreds of millions of dollars worth of tokens are locked in existing ledgers hosted on the Internet Computer. Producing a specification incompatible with the storage model of those ledgers would require <a href="https://www.coindesk.com/learn/what-are-wrapped-tokens/">wrapping</a> those tokens. Wrapped tokens are a reasonable compromise for interoperability <em>between</em> blockchains, but applying this solution to ledgers already hosted on the Internet Computer has many disadvantages:</p><ul><li><strong>Fractured ecosystem.</strong> Some actors will continue to use the original ledger; some will move to the wrapped tokens for convenience. These two groups will have to use and support incompatible tools and interfaces.</li><li><strong>User frustration.</strong> Every user must decide which token version (wrapped or unwrapped) they need to use. This mental strain is unnecessary and avoidable.</li><li><strong>Operational costs.</strong> Wrapping tokens will require setting up and maintaining new infrastructure.</li><li><strong>Security issues.</strong> Bridges and token wrappers are usual sources of costly security bugs.</li></ul><h4>Safety</h4><p>The standard should expose only features amenable to efficient and safe implementations.</p><p>For example, the Working Group considered a payment flow requiring the ledger to send notifications to the payee. Unfortunately, this flow can compromise the ledger upgrade safety, so the Working Group focused on a less convenient but safer (at least from the implementation point of view) flow.</p><h4>Pragmatism</h4><p>The standard should not depend on experimental or new platform features.</p><p>The Working Group members suggested many brilliant ideas that didn’t make the cut. Continuing the payment notifications example: adding new platform features (e.g., <a href="https://github.com/dfinity/interface-spec/pull/51">named callbacks</a>) can enable upgrade-safe implementations of notifications. Nevertheless, we decided to postpone the notification feature because having a good standard now is more important than having a perfect one in a year.</p><h4>Simplicity</h4><p>The standard should be easy to understand and implement.</p><p>Unnecessary complexity is the scourge of software systems. Some of the features discussed in the Working Group, such as the two-step transfer interface, were safe and pragmatic but notoriously hard to implement correctly. Given that there is no immediate need for these mechanisms, we agreed to develop advanced payment flows as future extensions.</p><p><a href="https://medium.com/dfinity/infinityswap-proudly-supporting-the-icrc-1-token-standard-on-the-internet-computer-cc1f87e17a6b">InfinitySwap: Proudly Supporting the ICRC-1 Token Standard on the Internet Computer</a></p><h3>Feature highlights</h3><h4>Embedding</h4><p>The ICRC-1 token standard is embeddable into existing ledger implementations. For example, the ICP ledger and any <a href="https://github.com/Psychedelic/DIP20">DIP20</a>-compatible ledger can integrate ICRC-1 safely. Several decisions made such embeddings easy:</p><ul><li>ICRC-1 accounts give ledgers a lot of flexibility in choosing internal representation. For example, the ICP ledger can convert ICRC-1 addresses into <a href="https://internetcomputer.org/docs/current/references/ledger#_accounts">account identifiers</a>.</li><li>All methods in the ICRC-1 interface have the icrc1_ prefix. Name conflicts will not stop developers from adding ICRC-1 methods to their interfaces.</li><li>The ICRC-1 interface does not specify access to the transaction log, giving existing ledgers the freedom to use their (incompatible) representations. Sometimes <em>not having</em> something is a feature!</li></ul><h4>Improving the ICP ledger technology</h4><p>The <a href="https://dashboard.internetcomputer.org/transactions">ICP ledger</a> is the biggest token ledger deployed on the Internet Computer. It is stable and robust: there haven’t been any significant incidents or unplanned outages since its launch in early May 2021.</p><p>The standard draws heavily on the experience of developing and operating the ICP ledger and inherits many of its beneficial traits:</p><ul><li>ICRC-1 allows users to have multiple <a href="https://medium.com/dfinity/fungible-tokens-101-cfd6849899e2#204a">subaccounts</a>, encouraging additional transparency and enabling a simple and safe payment flow. The <a href="https://internetcomputer.org/how-it-works/network-nervous-system-nns/">NNS Governance</a> is a heavy user of this feature.</li><li>ICRC-1 inherits and improves the <a href="https://github.com/dfinity/ICRC-1#transaction-deduplication-">transaction deduplication</a> feature crucial for implementing safe transfers over an unreliable network.</li></ul><p>At the same time, the standard brings some quality-of-life improvements, such as more transparent account addresses and extended memo sizes.</p><h4>Layered design</h4><p>The <a href="#e977">design goals</a> of the standard precluded the inclusion of many practical features. The Working Group understood the importance of these features and decided to follow the principles of <a href="https://www.leanproduction.com/">Lean Production</a> practices and deliver results in <a href="https://queue.acm.org/detail.cfm?id=2945077">small batches</a>. The ICRC-1 standard provides the <a href="https://github.com/dfinity/ICRC-1#icrc1_supported_standards">icrc1_supported_standards endpoint</a> to query the ledger capabilities.</p><p>As we already discussed, the standard does not specify the interface for fetching transactions. The lack of this interface makes it impossible to build many valuable features. For example, token wallets have no portable way of displaying all past transactions.</p><p>The Working Group chose to produce a separate optional extension for accessing the transaction log. Once this specification is ready, some ledgers will implement the new spec and advertise it through the supported standards endpoint. The wallets will be able to query ledgers for extensions and use the new interface when it’s available to provide a better user experience.</p><p>The layered design is also great for platform evolution. Plenty of exciting features are coming to the Internet Computer platform, and the extensions mechanism will allow the DeFi ecosystem to evolve in lockstep with the platform.</p><h4>Extensible metadata</h4><p>Many token standards follow the <a href="https://eips.ethereum.org/EIPS/eip-20#methods">ERC-20 example</a> and allow the ledger client to query information about the token, such as the token name and symbol. However, modern applications usually demand more information to provide a good user experience. Wouldn’t it be nice to display the token icon? How about different icons for dark and light color themes? Or maybe a link pointing to the description of the token? The solution proposed by the Working Group is to provide <a href="https://github.com/dfinity/ICRC-1#metadata">uniform access to metadata</a> enabling application builders to experiment without changing the ledger interface.</p><p><a href="https://medium.com/dfinity/fungible-tokens-101-cfd6849899e2">Fungible Tokens 101</a></p><h3>Next steps</h3><p>The ICRC-1 token standard is an important milestone, but it’s just a beginning of a long journey. The Ledger &amp; Tokenization Working Group has plenty of work to do:</p><ul><li>We need to agree on the <a href="https://forum.dfinity.org/t/icrc-1-account-human-readable-format/14682">textual representation for the ICRC-1 accounts</a>.</li><li>Inspired by the <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec">Internet Computer Interface Specification</a>, we want to introduce an acceptance test suite allowing developers to test their ledger implementations.</li><li>We are looking forward to developing further specifications enabling new types of applications, such as transaction log access and advanced payment flows.</li></ul><p>Stay tuned!<br><strong>____</strong></p><h4><strong>Start building at </strong><a href="https://internetcomputer.org/"><strong>internetcomputer.org</strong></a><strong> and join the developer community at </strong><a href="https://forum.dfinity.org/"><strong>forum.dfinity.org</strong></a><strong>.</strong></h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f7f303a33300" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/the-design-and-evolution-of-the-icrc-1-fungible-token-standard-f7f303a33300">The Design and Evolution of the ICRC-1 Fungible Token Standard</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fungible Tokens 101]]></title>
            <link>https://medium.com/dfinity/fungible-tokens-101-cfd6849899e2?source=rss-23896498b45e------2</link>
            <guid isPermaLink="false">https://medium.com/p/cfd6849899e2</guid>
            <category><![CDATA[token]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[icp]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Roman Kashitsyn]]></dc:creator>
            <pubDate>Thu, 11 Aug 2022 14:13:58 GMT</pubDate>
            <atom:updated>2022-08-11T17:58:55.762Z</atom:updated>
            <content:encoded><![CDATA[<h4>An introduction to fungible tokens and ledgers, along with features like mints, subaccounts, approvals, and transfer fees.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VmIj0WS3oKcveqm53HYTiQ.png" /></figure><h3>Introduction</h3><p>I am currently involved in the effort to deliver the <a href="https://github.com/dfinity/ICRC-1">ICRC-1</a> fungible token standard for the <a href="https://internetcomputer.org/">Internet Computer</a>. (<a href="https://dashboard.internetcomputer.org/proposal/74740"><strong><em>Voting is currently open on a motion proposal for the ICRC-1 standard</em></strong></a><strong><em>.</em></strong>) The two most heated discussions in the working group centered on using <a href="#204a">subaccounts</a> and the core payment flow for smart contracts (in particular, the approve/transferFrom flow popularized by the <a href="https://eips.ethereum.org/EIPS/eip-20">ERC-20</a> token standard). At first glance, these issues seemed unrelated, but surprising connections revealed themselves under closer scrutiny, begging for analysis and exploration.</p><p>This article is a gentle introduction to fungible tokens and ledgers. We shall frame the concept of the ledger and design choices in designing a practical accounting system, laying the ground for more subtle technical topics that will come in future articles.</p><h3>Fungible Tokens</h3><blockquote>“Gold is gold everywhere, fungible and indifferent. But when a disk of gold is stamped by a coiner with certain pompous words and the picture of a King, it takes on added value — seigneurage. It has that value only in that people believe that it does — it is a shared phant’sy.”<br><strong>— Neal Stephenson, The Confusion</strong></blockquote><p>The concept of <a href="https://www.investopedia.com/terms/f/fungibility.asp">fungible</a> tokens is ancient and intimately familiar to us, though we rarely use this learned term of <a href="https://en.wiktionary.org/wiki/fungible">Latin origin</a> in everyday life. Fungible tokens are interchangeable items you can trade, such as coins of equal value or gold pieces of identical form, weight, and purity.</p><p>When you bought ice cream as a kid, you traded one fungible token (<a href="https://www.investopedia.com/terms/f/fiatmoney.asp">fiat money</a>) for another (ice cream). The salesperson at the store <a href="https://en.wikipedia.org/wiki/Pecunia_non_olet">did not care</a> where your coins came from. Maybe your aunt gave you some to buy a treat, or perhaps you saved some from your lunch money. You did not care which instance of the desired sort of ice cream you would get. (My absolute favorite is <a href="https://en.wikipedia.org/wiki/Plombi%C3%A8res-les-Bains#Plombir_ice_cream">plombières</a>.)</p><h4>Asset Ledgers</h4><p>The most prominent examples of fungible tokens in the digital world are digital assets such as <a href="https://bitcoin.org/">bitcoin</a>, <a href="https://ethereum.org/en/eth/">ether</a>, and <a href="https://wiki.internetcomputer.org/wiki/ICP_token">ICP</a> utility tokens. An <a href="https://www.investopedia.com/terms/a/asset-ledger.asp">asset ledger</a> is a concept lying at the heart of these systems. Ledgers are journals of transactions the system executed; they keep track of fund movements between accounts. Each purchase you make using bitcoin becomes a record in the Bitcoin ledger packed into a block in the blockchain.</p><p>My nerdy ex-colleagues from <a href="https://ya.ru/">Yandex</a> used to use a simple ledger to keep track of tip money. I will use and evolve their scheme to demonstrate the concept of a ledger and its variations.</p><p>Geneviève works in a small accounting firm. One day she goes into a small restaurant with two of her colleagues, Allen and Meriam. They get a fantastic meal and decide to tip $20. Unfortunately, Allen and Meriam do not have $6.66 to share the burden equally. So they get a notebook, write “Ledger” on the cover, and split the first page into three columns. Then Allen and Meriam transfer Geneviève imaginary money on that ledger.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uXmbxUq5vX1pwJ6owh2LLg.png" /></figure><p>Now Allen and Meriam have -$6.66 on their “accounts”, and Geneviève has $13.32. The next day, they go to a coffee shop and tip $15. This time Allen pays for everyone, and Geneviève and Meriam add new entries to the ledger.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PvRX9pPdPpOVzMoFH-_9LQ.png" /></figure><p>Now Allen has $3.34 on his account, Geneviève has $8.32, and Meriam has -$11.66. (To compute a person’s balance, go over all the records in the log from top to bottom. If the person appears in the <em>from</em> column, subtract the <em>amount</em> from their balance; if the person appears in the <em>to</em> column, add the <em>amount</em> to their balance.) This ledger has an interesting property: the sum of all balances is always zero because we started with no funds, and each record only moves funds.</p><p>This simple scheme describes a fully functional and practical ledger that helps balance the financial burden of tipping. The person with the lowest balance on the ledger pays for the whole company when they go out.</p><p>The tip ledger is unusual because it allows negative balances like credit cards. This setup works well when all the participants know and trust one another. Digital ledgers such as Bitcoin are like debit cards: you must have enough tokens on your account before transferring them. But how do the first tokens get into the system?</p><h4>Minting and Burning</h4><p>All ledgers have a way to produce, or <em>mint</em>, tokens out of thin air. Bitcoin network mints tokens as a reward for participants that help the ledger grow. The IC mints ICP utility tokens to reward participants in the network governance and node providers.</p><p>Another popular scheme is <em>wrapped tokens</em>, where the ledger mints tokens as proxies for other assets. Let us extend the tip ledger example to make it operate on wrapped dollars.</p><p>Imagine now that Geneviève does not trust the folks she hangs out with, but she wants to continue enjoying the convenience of virtual money. Whenever someone transfers her virtual tokens on a piece of paper, she wants to be sure she can claim her buck back.</p><p>One way to approach the issue is to set up a piggy bank at the office. Anyone who puts $1 into the bank gets a <em>wrapped</em> $1 on the ledger. The transaction converting a physical bill into a virtual token is a <em>mint</em> transaction.</p><p>One day Geneviève, Allen, and Meriam put $10 each into the piggy and mint their wrapped money on the ledger.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-aTWjE0LFMlR-u0AD-2mnQ.png" /></figure><p>Then they all go to a coffee shop where Geneviève tips $6 for the group. Allen and Meriam transfer their shares to Geneviève on the ledger.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f9Bd8KJ9c5OhrOmMiQyXdw.png" /></figure><p>The main difference with the original scheme is that now Geneviève can exit the group and get her money back at any point. All she needs is to open the piggy under a supervision of a trusted party, get her $14, and record a <em>burn</em> transaction on the ledger by sending her tokens to the void (sometimes called the <em>minting account</em>). The sum of all balances on the ledger is always equal to the amount of money in the piggy bank.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1FyDhZDrU9ygHW_cDn9xSA.png" /></figure><p>Wrapped tokens are not a recent invention: the U.S. dollar <a href="https://en.wikipedia.org/wiki/Gold_standard">was</a> a wrapped token for 1.50463 grams of gold in <a href="https://en.wikipedia.org/wiki/Coinage_Act_of_1873">1873</a>.</p><h4>Subaccounts</h4><p>Geneviève and her colleagues have a tradition: when someone has a birthday, other colleagues raise funds to buy a little present. Next week Allen turns thirty-three, so the department asked Geneviève to buy something nice for him. This time they decided to use the piggy bank ledger discussed in the previous section to transfer funds for the present. However, there is one little issue: if everyone transfers gift money to Geneviève directly, how will she separate her money from the gift money?</p><p>Our clever office folks decided to add a new feature to the ledger to address the fund separation problem. Everyone can hold multiple disjoint accounts on the ledger and move funds from any of those accounts. A <a href="https://www.investopedia.com/terms/s/sub-account.asp">subaccount</a> will be a label demarcating independent accounts belonging to the same person.</p><p>Geneviève asks colleagues to transfer funds to her NYYRA OVEGUQNL subaccount until the end of the day. (Geneviève applied advanced cryptography to hide the purpose of the subaccount from Allen.) She burns the tokens on her NYYRA OVEGUQNL subaccount and withdraws $42.00 from the piggy bank right before leaving the office.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u5hBtrzZWBed3pzOkwxivQ.png" /></figure><p>Geneviève heads to the book store and buys the latest edition of <a href="https://www.amazon.com/-/en/dp/0884271951">the goal</a> by Eliyahu M. Goldratt. What a great birthday present!</p><p>Overall, subaccounts are a helpful feature allowing you not to put all your tokens in a single basket. Your bank likely opened more than one account for you, such as a salary and a savings account.</p><h4>Approvals</h4><p>One day Geneviève’s nephew, Alex, comes to visit her at work. Geneviève has an important call with a customer and could not take Alex out for lunch. Her colleagues were happy to go out with Alex, but there was a little problem: Alex did not have money.</p><p>Luckily, Geneviève accumulated quite some balance on the ledger, so someone could pay for Alex and get her ledger money back in exchange. All that was left is to formalize this arrangement on the ledger.</p><p>Geneviève could transfer some budget to Alex before he goes out, and he could transfer her the leftover when he is back. That solves the problem, but Geneviève cannot use the locked funds herself during that time because, technically, they belong to Alex.</p><p>Another approach popularized by the Ethereum community is to introduce the notion of <em>approvals</em>. The ledger could have another table with spending allowances between two people.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*K-NhMiu_xj06faWWkR8PlQ.png" /></figure><p>With this record, Alex can transfer money on behalf of Geneviève up to the allowance.</p><p>Alex had a lot of fun with Geneviève’s colleagues and spent $16.00 at a coffee shop. Allen paid for Alex, and Alex transferred some of Geneviève’s tokens to Allen in return. This arrangement resulted in two updates to the ledger. The first update is the new transaction in the log. Note that we need a new column in the table, “On Behalf Of,” to indicate that Alex initiated the transaction, but Geneviève is the effective payer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zJTTt8Q6t92dNC-TK7Jw0w.png" /></figure><p>The second update lowers the allowance in the approval table by the amount Alex spent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CiLtxo0f_FrLTnDI1iO6_A.png" /></figure><h4>Fees</h4><p>Peppy was a lovely five-year-old girl who came to the office space to see how her mother, Meriam, spends her days. Peppy loved numbers, could write her name, and was unusually rational for her age. Her favorite game was finding holes in ad-hoc rules that grown-ups invent all day. Her eyes caught a little devilish fire when she saw how her mother used the ledger notebook.</p><p>“How much can I send you, Mom?” asked Peppy.</p><p>“No more than you have on your account,” replied Meriam.</p><p>“I don’t have anything yet. Can I send <em>nothing</em>?”</p><p>“Ahm… Well, there are no rules prohibiting <em>that</em>, I suppose.”</p><p>Peppy grabbed a pen and started filling the lines with blocky letters.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PyQbMnVhMKDOdgzHM2w5dw.png" /></figure><p>“OK, Peppy, stop. There is a new rule: you cannot transfer <em>nothing</em>. Only a positive amount.”</p><p>Peppy stopped. A few wrinkles appeared on her forehead, and then her lips curled into a smile. She opened her little backpack with tiger stripes and fetched a nickel she found on the street a few days ago. She put the nickel into the piggy bank and recorded a mint. She did not stop there, however.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q-ZFeU6TaUnw1siEHFn1Pw.png" /></figure><p>“OK, Peppy, a new rule: you can’t transfer to yourself. There is no reason to do that!”</p><p>Peppy knit her brows, struggling to come up with a counter-action. Ten seconds later, she was scribbling again. She was so focused that the tip of her tongue stuck from her mouth.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8TYy7QfmWfSmzz14L7_HIA.png" /></figure><p>“It’s not funny, Peppy. From now on, every record will cost the sender a penny.”</p><p>Peppy pursed her lips, wrote four more records to the notebook, and visited Mrs. Geneviève, who had a chocolate bar in her upper drawer.</p><p>Fees are an essential instrument in ledger design. The bitcoin network uses fees to protect the system against spam transactions and incentivize the nodes to include transactions into blocks. The higher the fee the transaction sender is willing to pay, the more likely the nodes to process the transaction. The ICP ledger also uses fees as a mechanism for spam prevention.</p><h3>Summary</h3><p>We have seen that fungible tokens are an essential part of our daily life. We learned that <a href="#7200">ledger</a> is a robust accounting mechanism that we can adapt to the task at hand by adopting various features: <a href="#801f">mints</a>, <a href="#204a">subaccounts</a>, <a href="#103c">approvals</a>, and <a href="#8ab5">transfer fees</a>. In the following article, we will discuss protocols allowing clients to exchange tokens for service, known as <em>payment flows</em>.</p><p><strong>____</strong></p><h4>Start building at <a href="https://internetcomputer.org/">internetcomputer.org</a> and join the developer community at <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cfd6849899e2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/fungible-tokens-101-cfd6849899e2">Fungible Tokens 101</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[IC Internals: The XNet Protocol for Subnets]]></title>
            <link>https://medium.com/dfinity/ic-internals-the-xnet-protocol-for-subnets-c4035dac7d2c?source=rss-23896498b45e------2</link>
            <guid isPermaLink="false">https://medium.com/p/c4035dac7d2c</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[protocol]]></category>
            <category><![CDATA[blockchain-technology]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[subnet]]></category>
            <dc:creator><![CDATA[Roman Kashitsyn]]></dc:creator>
            <pubDate>Mon, 08 Aug 2022 19:30:16 GMT</pubDate>
            <atom:updated>2022-08-11T06:13:34.023Z</atom:updated>
            <content:encoded><![CDATA[<h4>A detailed summary of the Internet Computer’s subnet communication protocol — a feat of research and engineering.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0Q7SKRV8UeBqf4Q4eBEdnQ.jpeg" /></figure><h3>Introduction</h3><p>This article continues the previous post on state machine replication in the Internet Computer (IC), <a href="https://mmapped.blog/posts/02-ic-state-machine-replication.html">a swarm of replicated state machines</a>. This time, we shall examine the protocol over which independent state machines (also known as <em>subnets</em>) communicate, the <em>XNet protocol</em>.</p><p><a href="https://medium.com/dfinity/ic-internals-orthogonal-persistence-9e0c094aac1a">IC Internals: Orthogonal Persistence</a></p><h3>Subnets</h3><p>A <em>subnet</em> is a collection of nodes participating in a single instance of the <a href="https://dfinity.org/howitworks/consensus">consensus protocol</a>. All the nodes in a subnet have the same state and apply the same blocks.</p><p>It might be tempting to think that nodes of a subnet are physically collocated. However, the opposite is usually true: subnet nodes are often geographically distributed across independent data centers. (There are still good reasons to assign multiple nodes in a data center to the same subnet, such as increasing query call capacity and speeding up recovery in case of a replica restart.) The goal is to improve availability: a disaster in a single data center cannot take down the entire subnet. The <em>registry</em> canister maintains the assignment of nodes to physical machines, and the <a href="https://dfinity.org/howitworks/network-nervous-system-nns">Network Nervous System</a> governs all the changes to the registry.</p><p>Nodes from different subnets can live in the same data center. This setup might be counter-intuitive: nodes from different subnets might sometimes have better network connectivity than nodes in the same subnet.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wG_JpZTwd4so09ySAXSsZw.png" /><figcaption>Two three-node subnets located in three data centers. Solid lines represent peer-to-peer communication within a subnet; dotted lines — cross-subnet communication. Not all XNet connections are present in the picture.</figcaption></figure><p>XNet protocol is not limited to the same-datacenter communication; any node from one subnet can talk to any other node from another subnet. However, the replica prefers contacting close peers to reduce the message delivery latency. (The replica uses network latency as the proximity measure. It randomly contacts nodes from other subnets, assigning higher weights to nodes with lower latency.)</p><h3>Message Streams</h3><p>Messages start their journey in the output queues of canisters hosted on the source subnet. The subnet sorts these messages based on the destination subnet and interleaves them into flat message streams (one stream per destination subnet). Each message in the stream gets a unique monotonically increasing index.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cXiK5IJkrTYmEndgo_qZDg.png" /><figcaption>The flow of messages within a subnet. Canisters push messages into their output queues; the stream builder picks up these messages and constructs a flat outgoing message stream for each subnet.</figcaption></figure><p>The component merging the queues (aptly called <em>stream builder</em>) should satisfy a few constraints:</p><ul><li><strong><em>Determinism</em></strong><br>All nodes in the subnet must agree on the exact contents of the stream. To do its job, the stream builder needs the mapping from canister identifiers to subnet identifiers, the <em>routing table</em>. The routing table comes from the registry and changes over time. To ensure determinism, each block pins the registry version that the state machine is using for message processing.</li><li><strong><em>Ordering</em></strong><br>If canister A sends two requests to canister B, R1, and R2, then R1 should appear before R2 in the stream.</li><li><strong><em>Fairness</em></strong><br>We do not want messages from a single chatty canister to dominate the stream. The stream builder tries to interleave messages so that each canister has the same bandwidth.</li></ul><p>When a node from subnet X decides to get new messages from subnet Y, it picks a node from Y (the registry stores the entire network topology) and calls Y’s XNet endpoint with the index of the first unseen message and the number of messages to fetch.</p><h3>Block Payloads</h3><p>The job of the consensus protocol is to aggregate messages from the outside world and pack them into a neat block. Consensus includes several types of messages into blocks, such as user ingress messages, Bitcoin transactions (for subnets with enabled <a href="https://medium.com/dfinity/btc-icp-integration-beta-release-the-bitcoin-testnet-api-is-now-available-bab84c378c1e">Bitcoin integration</a>), and inter-canister messages from other subnets. We call messages paired with the data required for their validation a <em>payload</em>. We call components that pull payloads from the network <em>payload builders</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PIngKJ_vKZXspV1QUsuAtg.png" /><figcaption>The consensus algorithm aggregates messages from the outside world into blocks.</figcaption></figure><p>XNet payload builder pulls messages from nodes assigned to other subnets using a simple HTTP protocol. <em>XNet endpoint</em> is a component that serves messages destined for other subnets over secure TLS connections, accepting connections only from other nodes. (This measure does not imply privacy because malicious nodes can access the data; but ensures that network providers cannot read the messages.) XNet endpoint fetches the complete list of nodes, their subnet assignment, IP addresses, and public keys (required to establish a TLS connection) from the registry.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0gdyMKP-zOIgWiv1VDqr8A.png" /><figcaption>The data flow in the XNet protocol. Subnet Y produces a signed stream of messages for subnet X and exposes this stream via an HTTP endpoint. Subnet X pulls messages from one of the nodes on subnet Y.</figcaption></figure><h3>Garbage Collection</h3><p>We now know how one subnet accumulates messages destined for another subnet. This knowledge begs another question: how do replicas remove messages that the destination subnet has already consumed? We need a feedback mechanism allowing the consumer subnet to tell the producer subnet that it does not need some stream prefix anymore. We call this mechanism <em>signals</em>.</p><p>Signals are a part of the XNet payload specifying the prefix of the <em>reverse</em> stream that the sending subnet can drop. When a node from subnet X fetches XNet payload from a node from subnet Y, in addition to actual messages, the Y node includes the <em>stream header</em>. The stream header describes the state of the X ↔ Y communication:</p><ul><li>The full range of message indices in the forward stream X → Y.</li><li>The signals for the <em>reverse</em> stream (Y → X): for each message index in the reverse stream, Y tells whether X can garbage collect the message (an ACK signal) or should reroute the message (a REJECT signal). A REJECT signal indicates that the destination canister moved, so X should route the message into another stream.</li></ul><p>Signals solve the issue of collecting obsolete messages, but they introduce another problem now we also need to garbage-collect signals! Luckily, we already have all the information we need: we keep signals only for messages that are still present in the reverse stream. Once we notice (by looking at the range of message indices) that the remote subnet dropped messages from its stream, we can remove the corresponding signals from our header.</p><p>From my experience, the interplay of message indices and signals is notoriously hard to grasp, so let us look at an example. The diagram below depicts two subnets, X and Y, caught in the middle of communication. Subnet X gets a prefix of Y’s stream and the header, allowing X to induct new messages and garbage-collect its messages and signals. X also publishes signals for the newly received messages and updates its indices accordingly so that Y could garbage-collect its messages and signals in the next round of communication.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n5Wo1GiamyEft5hsomt_pg.png" /><figcaption>Two subnets, X and Y, communicating over the XNet protocol. In previous communications, subnet Y consumed messages [0,10) from X’s stream and has recently received messages 10 and 11. Now, subnet X receives a prefix of Y’s stream and the matching header and removes messages 10 and 11 from its stream because Y will not need them anymore. X also includes signals for the newly received messages into the X → Y stream header and removes an obsolete signal for message Y1 it consumed before.</figcaption></figure><p>Signals and stream messages are like snakes eating each other’s tails on the <a href="https://theneverendingstory.fandom.com/wiki/Auryn">Auryn</a>: the sender drops messages when it sees signals, and the receiver drops signals when it sees stream bounds advancing.</p><h3>Stream Certification</h3><p>Since no two nodes in the network can blindly trust each other, we need a mechanism to validate the contents of XNet payloads. More specifically, we want proof that the stream prefix in the payload is the same on all honest nodes in the subnet that produced the stream. In the previous article, we have seen how nodes use threshold signatures on <a href="https://pr-12--infallible-khorana-f0cacc.netlify.app/posts/02-ic-state-machine-replication.html#state-trees">state trees</a> as authenticity proofs for call replies. The XNet protocol relies on the same trick: nodes include streams destined for other subnets into their state trees and use threshold signatures as proofs of authenticity for nodes from other subnets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/926/1*Is1iwqaepw5WoFgJp4jOTA.png" /><figcaption>The encoding of subnet message streams in the <a href="https://pr-12--infallible-khorana-f0cacc.netlify.app/posts/02-ic-state-machine-replication.html#state-trees">state tree</a>.</figcaption></figure><p>Conceptually, a node requesting messages from a subnet is not different from a client requesting a response. This similarity allows us to use the same authentication mechanism in both cases. (Currently, there is a minor difference in how we represent certificates in the XNet protocol and the <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/#_certificate">IC HTTP</a> interface. The HTTP interface certificates combine the data and the hashes required to check the authenticity in a single data structure, the <em>hash tree</em>. The XNet protocol separates the raw message data and the hashes (called the <em>witness</em>) into separate data structures. The reason for that distinction is purely historical. We implemented the XNet protocol significantly earlier than the response authentication, so we could not benefit from <a href="https://www.joachim-breitner.de/blog">Joachim Breitner’s</a> brilliance. Joachim took the XNet authentication scheme as the starting point and simplified it for the <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec/">IC Interface Specification</a>.)</p><p>The tree structure of the certificate comes in handy for buffering messages on the receiver: the receiver can maintain a slightly larger pool of messages than a single block can fit, asynchronously fetching new messages and appending them to the pool, merging the certificates appropriately. This optimization allows us to use the subnet’s narrow XNet channel more efficiently and improve fairness when we include messages from multiple subnets into a single block.</p><h3>Limitations</h3><p>The XNet protocol is a marvelous feat of engineering, but it has a few inherent limitations:</p><ul><li>All XNet messages have to go through consensus blocks. This constraint bounds the theoretical throughput of the protocol by the block rate and size. For example, if a subnet produces one block every second and the block size is 2MiB, the XNet throughput on this subnet can be at most 2MiB/sec.</li><li>Delivering a message requires two rounds of consensus (one round on the sender, one round on the receiver). This constraint bounds the latency of the protocol by the block rate. If both the receiving and the sending subnet need a second to produce a block, a request will need at least two seconds to reach the destination. Delivering the response will need another two rounds, so the call round-trip time is at least four seconds.</li></ul><h3>Code References</h3><p>A few pointers to the code implementing designs from this article:</p><ul><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/registry/routing_table/src/lib.rs#L213">routing table</a>.</li><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/messaging/src/routing/stream_builder.rs#L237">stream builder</a>.</li><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/xnet/payload_builder/src/lib.rs#L665">payload builder</a> and the <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/xnet/payload_builder/src/certified_slice_pool.rs#L1042">XNet message buffer</a>.</li><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/xnet/endpoint/src/lib.rs#L93">XNet endpoint</a> and the <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/xnet/payload_builder/src/proximity.rs#L118">node proximity metric</a> computation.</li><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/messaging/src/routing/stream_handler.rs#L557">induction of messages</a> into the state machine state.</li><li>The garbage collection of <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/messaging/src/routing/stream_handler.rs#L391-L426">messages</a> and <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/messaging/src/routing/stream_handler.rs#L428-L465">signals</a>.</li><li>The <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/canonical_state/src/lazy_tree/conversion.rs#L254-L284">mapping of streams</a> to the tree structure, <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/state_manager/src/stream_encoding.rs#L40">tree encoding</a>, and <a href="https://github.com/dfinity/ic/blob/226faa85b945aabf0fc22a18b4c2e1b9f0f4c8ee/rs/state_manager/src/lib.rs#L2912-L2972">validation</a>.</li></ul><h3>Credits</h3><p>Finally, I shall give due credit to people who played an essential role in the protocol development.</p><ul><li><a href="https://www.linkedin.com/in/allen-clement-b73a4652/">Allen Clement</a> is the mastermind behind most of the features of the XNet protocol.</li><li><a href="https://www.linkedin.com/in/david-derler-08630495/">David Derler</a> refined many of Allen’s ideas and wrote a formal mathematical specification for the protocol.</li><li><a href="https://www.linkedin.com/in/alin-sinpalean-8451b8139/">Alin Sinpalean</a> implemented the protocol in the <a href="https://github.com/dfinity/ic/tree/3fe4137c86ab0521c39089954c03d7fb29e2c3d2/rs/xnet">ic replica</a> and developed many optimizations.</li></ul><p>My main contributions are stream certification and TLS integration.</p><p><strong>____</strong></p><h4>Start building at <a href="http://smartcontracts.org/">smartcontracts.org</a> and join the developer community at <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c4035dac7d2c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/ic-internals-the-xnet-protocol-for-subnets-c4035dac7d2c">IC Internals: The XNet Protocol for Subnets</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[IC Internals: Orthogonal Persistence]]></title>
            <link>https://medium.com/dfinity/ic-internals-orthogonal-persistence-9e0c094aac1a?source=rss-23896498b45e------2</link>
            <guid isPermaLink="false">https://medium.com/p/9e0c094aac1a</guid>
            <category><![CDATA[crypto]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <dc:creator><![CDATA[Roman Kashitsyn]]></dc:creator>
            <pubDate>Thu, 28 Apr 2022 13:53:45 GMT</pubDate>
            <atom:updated>2022-05-10T02:25:44.784Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>With orthogonal persistence, a program doesn’t need to persist its state in files explicitly: the runtime handles persistence transparently.</em></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BmU7M_XI95TKU2eIdFqb9Q.jpeg" /></figure><h3>Orthogonal persistence</h3><p>I often describe the <a href="https://smartcontracts.org/">Internet Computer</a> (IC) as a distributed operating system that hosts <a href="https://webassembly.org/">WebAssembly</a> programs. One of my favorite features of the IC is <a href="https://en.wikipedia.org/wiki/Persistence_(computer_science)#Orthogonal_or_transparent_persistence">orthogonal (or “transparent”) persistence</a>. Orthogonal persistence creates an illusion that a program runs forever without crashing or losing state. There is no need for the program to persist the state in files explicitly: the runtime handles persistence transparently.</p><p>In the early research on orthogonal persistence, state modifications looked like database transactions. Programmers had to mark transaction boundaries so that the system could identify safe snapshot points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qlDAdrRlJBIv4DPiQrWlGw.png" /><figcaption>A slightly modified snippet of code in <a href="https://en.wikipedia.org/wiki/PS-algol">ps-algol</a> from the paper “An Approach to Persistent Programming” by Atkinson et al. Note explicit calls to commit and abort procedures.</figcaption></figure><p>Why can’t we take a snapshot after every instruction? This granularity is not only inefficient but also does not help us recover from failures. If the program crashes because of a faulty input, rolling back the instruction right before the crash is pointless. (<em>Obligatory </em><a href="https://en.wikipedia.org/wiki/Meanwhile_(Futurama)"><em>Futurama</em></a><em> reference: the program will behave like </em><a href="https://www.youtube.com/watch?v=yHr283GT24U&amp;t=163s"><em>Fry time-traveling to the moment right after the jump from the Vampire State Building</em></a><em>.</em>)</p><p>Persistent programming improved over manual serialization, but it does not feel “orthogonal” enough. We can do better.</p><p><a href="https://medium.com/dfinity/internet-computer-basics-part-1-principals-and-identities-215e8f239da4">Internet Computer Basics — Part 1: Principals and Identities</a></p><h3>Actors</h3><p><a href="https://en.wikipedia.org/wiki/Actor_model">Actors</a> are a model of concurrent computation that treats systems as interactions of state machines. All the programs running on the IC are actors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*L_k0kZROL3vKticT4EQAHQ.png" /><figcaption>Pseudocode of an actor.</figcaption></figure><p>The actor model and orthogonal persistence are a match made in heaven. Actors have a natural persistence boundary: the system can grab a snapshot of the actor’s state at the moment when it is ready to process the next message. The programmer does not need to call commit explicitly to mark execution points where the system should persist the state.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QWrC6b_LHEA-R21wNQK1Yg.png" /><figcaption>Pseudocode of an IC actor with orthogonal persistence.</figcaption></figure><p>The bulkiest component of an actor state on the IC is the WebAssembly (Wasm) <a href="https://webassembly.github.io/spec/core/exec/runtime.html#module-instances">instance state</a>. A naive approach to snapshotting is to make a deep copy of all the data structures representing the state before each message execution. Most of the state data structures are cheap to clone; mutable globals are a good example. However, snapshotting and restoring Wasm memories pose a challenge: each memory can hold gigabytes of data. Copying the memory in full before each message execution is prohibitively expensive.</p><p>Let us see how the IC implementation responds to this challenge.</p><h3>Snapshots and deltas</h3><p>The implementation divides the contents of each memory into 4096-byte chunks called <em>pages</em>. When the actor executes a message, the system automatically detects the memory pages that the actor modifies, or <em>dirties</em>. The system uses low-level UNIX APIs to detect page modifications. Since most operating systems operate on 4096-byte memory pages, using the same page size in the replica is the most natural choice.</p><p>The memory snapshot of an actor is a map from a page index to the page contents. We call this data structure a <em>page map</em>. There are many ways to implement this data structure. The primary assumption that guided the current implementation is that each message execution modifies only a small number of pages. This assumption holds in practice: as of April 2022, 95% of message executions change at most seven memory pages.</p><p>If the expected number of dirtied pages is small, it is natural to apply some delta-encoding scheme. Thus we chose to represent page maps as a combination of on-disk <em>checkpoint files</em> and in-memory <em>page deltas</em>. A checkpoint file is a flat binary file with a full copy of the actor memory that the system creates at the end of some execution rounds. Once created, checkpoint files are immutable. A page delta is a <a href="https://en.wikipedia.org/wiki/Persistent_data_structure">persistent</a> map that contains pages dirtied by the actor since the last checkpoint.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x54VrNMgC1cwi5SXtd_k7w.png" /><figcaption>Snapshots of an actor memory over several execution rounds. Dotted pages represent pages inherited from the checkpoint, dotted vertical lines — message execution boundaries, bold shapes — page deltas. Note that the system shares the contents of dirtied page among snapshots.</figcaption></figure><p>The runtime uses page maps in the following way:</p><ol><li>The system creates a “scratchpad” memory by constructing a patchwork from the checkpoint file and the running page deltas.</li><li>The system executes a message on the actor state and detects the pages that the actor dirtied on the scratchpad.</li><li>If the message execution succeeds, the system copies the contents of the dirty pages into the running delta.</li><li>Otherwise, the system throws away the scratchpad.</li></ol><p>Once in a while, the system creates a new checkpoint by cloning the original checkpoint file and flushing dirty pages to the new file. This procedure speeds up scratchpad construction and reduces memory pressure.</p><h3>Detecting memory writes</h3><p>Detecting touched and dirtied memory pages is another challenging aspect of orthogonal persistence. The system compiles actor’s WebAssembly modules to native code. How do you know which pages arbitrary code touched? There are multiple approaches to this problem:</p><ul><li>Compare the full memory before and after execution. This approach is easy to implement and works on all platforms, but it performs poorly on sizable memories and does not give us accessed pages.</li><li>Instrument the WebAssembly module before compiling it to native code. For example, we could add a system call before all load and store instructions to mark the corresponding pages as accessed or dirtied. This approach works on all platforms but can slow down execution by an order of magnitude.</li><li>Use memory protection and signal handlers to detect memory reads and writes at runtime. This approach works well on UNIX platforms and is reasonably efficient. We shall discuss this approach in more detail shortly.</li><li>Implement a custom filesystem backend as a <a href="https://en.wikipedia.org/wiki/Filesystem_in_Userspace">FUSE</a> library, then <a href="https://man7.org/linux/man-pages/man2/mmap.2.html">memory-map</a> actor memory as a virtual file. The operating system will call into our library when the actor code reads from or writes to the memory-mapped file, allowing us to perform the required bookkeeping. This approach works great on platforms that support FUSE (Linux and macOS), but it has some administrative disadvantages. For example, the replica will need privileged access to be able to mount a virtual filesystem.</li><li>Use Linux <a href="https://man7.org/linux/man-pages/man1/pmap.1.html">pmap</a> utility to extract <a href="https://techtalk.intersec.com/2013/07/memory-part-2-understanding-process-memory/#pmap-detailed-mapping">memory access statistics</a> right after the message execution. This approach is very efficient, but it does not always produce deterministic results.</li></ul><h3>The signal handler</h3><p>The <a href="https://man7.org/linux/man-pages/man2/mprotect.2.html">memory protection API</a> allows us to set read and write permissions on page ranges. If the process violates the permissions by reading a read-protected region or writing to a write-protected region, the operating system sends a signal (usually SIGSEGV) to the thread that triggered the violation. The <a href="https://man7.org/linux/man-pages/man7/signal.7.html">signal handling API</a> allows us to intercept these signals and inspect the address that caused them. We can build a robust and efficient memory access detection mechanism by combining these APIs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jOKGxJVGw-rlm6oXZlhbfA.png" /><figcaption>Pseudocode of the memory access detection state machine.</figcaption></figure><p>Let us see the state machine in action on a simple example: an actor stores an array of integers; it needs to find a specific integer in the array and replace it with another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uygftT2grW9acq958j3diA.png" /><figcaption>An example of a function triggering the memory access mechanism.</figcaption></figure><p>To keep the example simple, let us assume that the array starts at page zero, and the integer to replace is at position 2000 in the array. Before the execution begins, the entire memory has protection flags PROT_NONE. As the actor executes the replace function, the following events occur:</p><ol><li>The actor accesses array[0]. Since the corresponding memory page is read-protected, the load instruction generates a SIGSEGV signal. The system invokes the signal handler that marks the page as touched and sets the memory protection to PROT_READ. The context switches back to the actor code, which can now repeat the read operation successfully.</li><li>The actor accesses array elements array[1] through array[1023] without interruption. (<em>A 4096-byte memory page can fit 1024 32-bit integers.</em>)</li><li>The actor accesses array[1024]. This element lives on the next page, which is still read-protected. The system behaves just as in step 1.</li><li>The actor accesses elements array[1025] through array[2000] without interruption.</li><li>The actor writes to array[2000]. The corresponding memory page is write-protected, so the store instruction generates a SIGSEGV signal. The context switches to the signal handler. The signal handler marks the page as dirty and removes the write protection by settings the protection flags to PROT_READ | PROT_WRITE. The actor code resumes and repeats the write, this time without interruption.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aqSMSwWDDsv7-Cd9MMjFHw.png" /><figcaption>States of the memory mapping during `replace` function execution. Rectangles represent memory pages, hollow arrows — reads, solid arrows — writes.</figcaption></figure><p>The signal handler approach is quite efficient in practice, and we can optimize it further:</p><ul><li>Instead of constructing the full actor memory in advance, we can populate it lazily when the actor first touches it. This optimization works best for fragmented memories with lots of page deltas.</li><li>Sequential memory access is a pervasive pattern worth optimizing. We can remove read protection from multiple consequent pages at once, removing the need to switch the execution context to the signal handler for each page. This optimization makes the mechanism less precise but can significantly improve execution speed.</li><li>We can speculatively remove write protection from multiple consequent pages to speed up sequential writes. We can later compare the contents of dirtied pages with the snapshot to validate our speculation.</li></ul><h3>Surviving upgrades</h3><p>Orthogonal persistence creates an illusion that the program runs forever without interruption. But what if we want to fix a bug in that program or add a new feature? Can we do the upgrade without losing the program state?</p><p>At first sight, it might seem safe to swap the WebAssembly module of an actor without changing the contents of its memory. Unfortunately, this seldom works in practice.</p><ul><li>The actor code expects a specific memory layout; changing data type definitions affects the layout. The new version of the code will not be able to make sense of the old memory.</li><li>The memory might contain pointers to functions. Changing the code might invalidate these pointers.</li><li>The code might have other expectations about the data besides the memory layout. For example, the new version of the code might use a different hash function for hash tables. Hash table lookups might start returning invalid results after the code swap.</li></ul><p>The only known way to solve this issue is to rely on stable data representations. There is a <a href="https://github.com/WebAssembly/multi-memory">proposal</a> that enables WebAssembly programs to access multiple disjoint memories. <a href="https://medium.com/@rossberg">Andreas Rossberg</a> suggested using the multi-memory feature to refine the persistence model with memory lifetimes. For example, an actor could use the default memory (the memory with index zero) as mid-term storage that depends on the compiler’s memory representation. The actor could use other memories as long-term storage with a stable (ideally, language-independent) data layout. The system would wipe out the transient memory during the upgrade but persist the long-term storage. (<em>Andreas also proposed short-term memories with a lifetime of a single message execution. Such memories open up attractive optimization opportunities, but we did not have enough pressure to implement them.</em>)</p><p>Since the IC needed to support upgrades before the multi-memory proposal was implemented, the runtime emulates one extra memory via the <a href="https://smartcontracts.org/docs/interface-spec/index.html#system-api-stable-memory">stable memory API</a>. This API intentionally mimics WebAssembly <a href="https://webassembly.github.io/bulk-memory-operations/core/exec/instructions.html#memory-instructions">memory instructions</a> to facilitate future migration to multi-memory modules. Internally, the main memory and the stable memory share the <a href="#580e">representation</a>.</p><p>Currently, most actors serialize their entire state to stable memory in the pre-upgrade hook and read it back in the post-upgrade hook. There is an ongoing effort to build tools that make it easier to use stable memory as the primary data storage.</p><h3>Conclusion</h3><p>We examined the classical approach to orthogonal persistence and its <a href="#214f">synergy</a> with the actor model. We learned about the <a href="#580e">page map</a>, the data structure that IC replicas use to store multiple versions of an actor’s memory efficiently, and the <a href="#1b20">SIGSEGV-based memory access detection system</a>. Lastly, we saw that orthogonal persistence is not the final solution to state persistence and why we need better tools to handle <a href="#5ba3">program upgrades</a>.</p><h3>References</h3><p>The <a href="https://github.com/dfinity/ic">IC replica code</a> is open source. In case you want to read the code that implements ideas from this article, here are a few pointers:</p><ul><li>The <a href="https://github.com/dfinity/ic/blob/3633026472367a413912bf797490c9336ba762f5/rs/execution_environment/src/hypervisor.rs#L1136">function executing a single message</a>.</li><li>The <a href="https://github.com/dfinity/ic/blob/3633026472367a413912bf797490c9336ba762f5/rs/replicated_state/src/page_map.rs">page map</a> module.</li><li>The <a href="https://github.com/dfinity/ic/blob/3633026472367a413912bf797490c9336ba762f5/rs/memory_tracker/src/lib.rs#L358">naive</a> and the <a href="https://github.com/dfinity/ic/blob/3633026472367a413912bf797490c9336ba762f5/rs/memory_tracker/src/lib.rs#L499">optimized</a> signal handlers.</li></ul><p><strong>____</strong></p><h4>Start building at <a href="http://smartcontracts.org/">smartcontracts.org</a> and join the developer community at <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9e0c094aac1a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/ic-internals-orthogonal-persistence-9e0c094aac1a">IC Internals: Orthogonal Persistence</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>