<?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 Igor Mandrigin on Medium]]></title>
        <description><![CDATA[Stories by Igor Mandrigin on Medium]]></description>
        <link>https://medium.com/@mandrigin?source=rss-b63376527faf------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*n8g47XO5rVwNUShgx6iokQ.jpeg</url>
            <title>Stories by Igor Mandrigin on Medium</title>
            <link>https://medium.com/@mandrigin?source=rss-b63376527faf------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 23:19:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mandrigin/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[“Work Is Work” by Coda Hale]]></title>
            <link>https://medium.com/@mandrigin/work-is-work-by-coda-hale-237e6f744a5d?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/237e6f744a5d</guid>
            <category><![CDATA[leadership]]></category>
            <category><![CDATA[management]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Wed, 12 Aug 2020 09:18:16 GMT</pubDate>
            <atom:updated>2020-08-12T09:18:16.474Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1hwAUhB5ijdHjaE7ox_7jw.jpeg" /><figcaption>image by <a href="https://www.flickr.com/photos/paulspace/">Paul Albertella</a></figcaption></figure><p>“<a href="https://codahale.com/work-is-work/">Work Is Work (in Which Results Diminish)</a>” is an article from <a href="https://codahale.com/about/">Coda Hale</a>.</p><p>Its main topic is that <strong><em>scaling teams is hard</em></strong>.</p><blockquote>Internal tooling, training, and services must be developed and fielded to ensure that all members are able to work on problems of continuously increasing impact. The ceaseless pursuit of force multipliers is the only possible route to superlinear productivity improvements as an organization grows.</blockquote><p>I absolutely agree. When adding more people to the organization, the best thing you can do is to make them work on something that improves productivity of everyone else. Being it a good CI system, internal frameworks, documentation, etc.</p><p>Code is smartly using <a href="https://en.wikipedia.org/wiki/Queueing_theory">queueing theory</a> to explain managerial issues:</p><blockquote>As with writing highly-concurrent applications, building high-performing organizations requires a careful and continuous search for shared resources, and developing explicit strategies for mitigating their impact on performance.</blockquote><blockquote>At some point, adding new members can cause the organization’s overall productivity to decrease instead of increase, as the increase in wait time due to contention is greater than the increase in work capacity. (This is the organizational version of the latency spikes we see as servers become overloaded.)</blockquote><blockquote>While the consultants can indeed move quickly in a low-contention environment, integrating their work product back into the contended resources often has the effect of ballooning […] how long a critical section is held. This produces a quadratic spike in wait times which increases utilization which in turn produces a superlinear spike in wait times.</blockquote><blockquote>The more distance between those designing the organization and the work being done, the greater the risk of unmanaged points of contention. Top-down organizational methods can lead to subdivisions which seem like parallel efforts when listed on a slide but which are, in actuality, highly interdependent and interlocking.</blockquote><blockquote>Staffing highly sequential efforts as if they were entirely parallel leads to catastrophe.</blockquote><blockquote>[…] the total time spent communicating will grow quadratically as the work capacity of the organization grows linearly.</blockquote><blockquote>[…] pair-wise communications don’t need to be formal, planned, or even well-known in order to have costs. <strong>Neither your employee handbook nor your calendar are accurate depictions of how work in the organization is done.</strong></blockquote><p>Informal communication is often forgotten about.</p><p>Of course, one of the tools that can help with this is applying microservices. I personally think that <strong><em>microservices architecture solves leadership problems, not technical</em></strong>. Though, it also should be done right.</p><blockquote>The key word there is <strong>independent</strong>. Slicing your shit up into a hundred microservices will not help you if everyone needs to change ten of them to get anything done.</blockquote><p>There are solutions, with some of those I do agree wholeheartedly.</p><blockquote>To avoid that, organization leaders should keep the development of a product portfolio as an explicit goal. Feature or product ideas which are complimentary to the organization’s overall business strategy but don’t naturally coexist with the main product can be developed as separate products by independent teams.</blockquote><blockquote>… tooling, libraries, and frameworks can be developed by force multiplier teams to reduce both time-to-market of new products…</blockquote><p>This is the one point that I disagree with. Trying to do the whole portfolio on a unified “framework”, makes this framework and the team behind it the bottleneck of the organization. You can and likely will end up with “<em>having to change ten of them</em>”, just like the author pointed out earlier.</p><p>If you are building everything in the same way, you are missing out on some innovation that new approaches and new technologies can bring to your other products.</p><blockquote>removing a feature from a product involves the same contention and coherence costs as adding a feature</blockquote><p>100% that! A lot of people for some reason think that adding a feature is harder than removing it. <strong>For non-trivial features it is not true</strong>. You can break half of the product by trying to remove the traces of a feature.</p><p><strong>Remainders of old features will haunt the codebase forever</strong>, making it is less secure, harder to change and harder to onboard new people on.</p><blockquote>Synchronous meetings should be reserved for low-latency collaboration on complex issues; likewise, collaboration should be reserved for synchronous meetings.</blockquote><p>In the ideal world, yes.</p><blockquote>Companies are groups of people being compensated for having to spend some of their finite lifetimes not being with their partners, children, pets, or super weird hobbies.</blockquote><p>One more important view point there.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=237e6f744a5d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[KV-Witness]]></title>
            <link>https://medium.com/@mandrigin/kv-witness-8985168537f9?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/8985168537f9</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[stateless]]></category>
            <category><![CDATA[proof]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Tue, 14 Jul 2020 16:12:29 GMT</pubDate>
            <atom:updated>2020-07-17T10:02:10.348Z</atom:updated>
            <content:encoded><![CDATA[<h4>an alternative approach to block witnesses</h4><p>There is currently a proposed format for block witnesses in <a href="https://blog.ethereum.org/2019/12/30/eth1x-files-state-of-stateless-ethereum/">Stateless Ethereum</a>, that has a spec <a href="https://github.com/ethereum/stateless-ethereum-specs/blob/master/witness.md">in a GitHub repo</a>. It is based on opcodes. You can imagine a tiny programming language with just a few commands that generate a <a href="https://medium.com/@jgm.orinoco/understanding-sparse-merkle-multiproofs-9b9f049e8f08">Merkle Mupltiproof</a>.</p><p>This post researches an alternative approach to block witness construction. It is based on a list of keys and values and has a simpler semantics.</p><p>In this post I will try to answer the following questions:</p><ul><li>What is the KV witness format and how it is different from currently proposed (opcode-based) Witness format?</li><li>What are the pros and cons of the KV comparing to OP?</li><li>How efficient is this format is in terms of network bandwidth?</li></ul><h3>Requirements</h3><p>Any block witness must satisfy the following requirements:</p><ul><li><em>Correctness.</em> We should be able to run any block from Ethereum mainnet using this format.</li><li><em>Efficiency.</em> We should use the minimum network footprint to transfer this witness.</li><li><em>Merkelization.</em> The witness format must support <a href="https://medium.com/ewasm/evm-bytecode-merklization-2a8366ab0c90">Code Merkelization</a>.</li><li><em>Arity-agnostic</em>. The witness format must support both <a href="https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768">hexary and binary Merkle Tries</a>.</li></ul><h3>Semantics</h3><p>Witness format I describe in this part of the post is <a href="https://stackoverflow.com/questions/17930267/what-is-the-difference-between-syntax-and-semantics-in-programming-languages">semantics</a>. I’m not talking about the exact byte layout here.</p><p>Later on, I will touch more on the exact binary format of the witness that was used for testing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/1*UfdyOFiGHaeldq_Rj7ovVw.png" /><figcaption>KV-Witness</figcaption></figure><pre>witness ::= header, body, proofs  <br>header ::= version : byte, trie_arity : byte  <br>body ::= array of [ { type: byte key : []byte, value : []byte } ]  <br>proofs ::= map { &lt;type&gt;: [ { prefix : []byte, hash : []byte } ] }</pre><h4>Witness body</h4><p>Witness body conists of 2 elements:</p><ol><li>Data. <br>The key can be: an account address, a storage key or a code key and the value is an account, a storage item or a code chunk respectively. <strong><em>This part of the witness body is completely agnostic to the arity of a Merkle Trie that is used to validate its correctness. Moreover, if we use something else for correctness check this part won’t change.</em></strong></li><li>Proof(s). <br>The key is the Merkle path and the value is a hash. The proof is dependent on the trie arity and will be different for hex and bin tries. <strong><em>This semantics allows including multiple proofs with different types in the same witness. So, we can theoretically make a witness that supports both hex and bin tries.</em></strong></li></ol><p>body is sorted lexicographically by key, making sure that:</p><ul><li>shorter keys are earlier in the list (so we are rebuilding a trie from top to bottom);</li><li>when keys are equal (that could happen for account and code) <em>account</em> always goes first.</li></ul><h4>Parsing Algorithm</h4><ol><li>Validate witness version and the proof arity (make sure that the witness proof arity matches the trie arity that that block requires).</li><li>Validate the witness hash (if canonical witness is there).</li><li>Create an empty trie of the right arity.</li><li>Go though the data, just insert data into this trie in the order it comes (witness should be lexicographically sorted).</li><li>Insert proofs into the trie.</li><li>Validate root hash (should match the root hash of the <strong><em>previous</em></strong> block).</li></ol><h3>Pros &amp; Cons</h3><p>Here is the list of pros and cons comparing KV-Witness vs <a href="https://github.com/ethereum/stateless-ethereum-specs/blob/master/witness.md">the current opcode-based witness format</a>.</p><h4><strong>Pros</strong></h4><ul><li>It matches the flat DB structure, can be inserted immediately if the canonical witness hash is valid (no need to verify Merkle Root).</li><li>It can be used for snapshot sync.</li><li>The witness data is independent from the validity proof method we choose: Merkle Tries or Polynomial Commitments or something else.</li></ul><h4><strong>Cons</strong></h4><ul><li>Potentially higher network footprint on binary tries due to byte alignment (e.g. the proof key 0b01, that is 2 bits will take a byte of storage space).</li><li>Potentially slower witness parsing.</li></ul><h3>Network Efficiency Research</h3><h4>KV Witness Example Implementation</h4><p>We need to be able to prove the correctness of the format. It should be able to run on all blocks of Ethereum Mainnet.</p><p>To do that, I have implemented this witness format in a branch of turbo-geth repository: <a href="https://github.com/ledgerwatch/turbo-geth/tree/kv-witness-research">kv-witness-research</a>.</p><p>This implementation was tested in Google Cloud on Ethereum mainnet blocks from 5.000.000–8.000.000.</p><h4>How to repeat the experiment?</h4><p>You need at least 200GB of free space and least 32gbs of RAM (the code is a PoC and isn’t optimized much).</p><p>1) clone kv-witness-research branch of turbo-geth (commit aa6b4dc609b3d871c778597a71ac08601f17de53</p><p>2) (took 1 day in my case) sync block headers and bodies for mainnet: go run ./cmd/geth --syncmode staged --datadir ~/stateless-chaindata/</p><p>3) (took 17 days in my case) run stateless prototype on this data</p><pre>go run ./cmd/state stateless --blockSource ~/stateless-chaindata/geth/chaindata --statefile ~/kv_witness_statefile --witnessInterval 5000000 --statsfile ~/stats_kv_witness.csv 2&gt;&amp;1 | tee debug.log</pre><p>That way, in stats_kv_witness.csv you should obtain the same stats as I have in this document.</p><h4>Witness binary format</h4><p>The witness starts with a single-byte header that contains version: header.</p><p>Then, there is a witness body that consists of the size (1-4 bytes dependent on the number of witness elements) and the elements themselves.</p><p>Each element starts with a single-byte type, followed by key field that is a byte array of arbitrary size prefixed by the size byte (just like body itself) followed by the actual data.</p><p>Data depends on what type of element is there:</p><ul><li>for storage leafs it is a byte array of arbitrary size refixed by the size bytes;</li><li>for code leafs it is a byte array of arbitrary size prefixed by the size bytes too;</li><li>for proofs it is a fixed-size 32 byte hash value w/o any size prefix;</li></ul><p>For accounts it is more complicated, but basically it is</p><ul><li>flags byte (mask that tells if account elements don’t have their default values)</li><li>nonce, 8 bytes (if nonce != 0)</li><li>balance (if balance != 0), byte array of arbitrary size, prefixed by its size;</li><li>storage root hash (if not empty root hash), 32 bytes, byte array of fixed size;</li><li>code hash (if code not empty), 32 bytes, byte array of fixed size.</li></ul><p>In the end we get something like this: this: [&lt;header&gt; &lt;witness_elements_count&gt; &lt;element1_type&gt; &lt;element1_key_size&gt; &lt;element1_key_byte1&gt; ... &lt;element1_value_size&gt; ... &lt;element2_type&gt; ...]</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/721/1*y2Qvb5ttuYa6jUT-gLP77A.png" /><figcaption>KV-Witness</figcaption></figure><p><strong>Optimization: Key prefix deduplication</strong></p><p>Key is a Merkle Path that consists of nibbles, not bytes. A single nibble size is 4 bits for a hex trie and 1 bit for a binary trie. That way, we can see that sometimes a key can be a non-integer amount <strong><em>bytes</em></strong>: (for example 12 bits is 8,5 bytes).</p><p>The key is encoded as []byte, where it is aligned by byte (so a key with a len between 4 and 5 bytes will always be 5 bytes). Also, an additional &quot;mask&quot; byte is added to the beginning that shows which bits are &quot;active&quot; in the last byte.</p><ul><li>a key 0xFF (1 byte): [00001000 11111111] &lt;== 8 significant bits</li><li>a key 0b11(2 bits): [00000010 11000000] &lt;== 2 significant bits</li><li>a key 0b10(2 bits): [00000010 10000000] &lt;== 2 significant bits</li><li>a key 0b_10101010_01010101_1101(2 bytes 4 bits): [11110000 10101010 01010101 11010000]</li></ul><p>Then, we can add a simple optimization that allows us to mitigate repeating prefixes in both data and proofs.</p><p><strong><em>To increase compression efficiency, we will intermix both data and proof in the same ordered map.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/709/1*8BiVp3Gj7k6O51047s9svg.png" /><figcaption>Data and proof are together sorted lexicographically</figcaption></figure><p>The highest 4 bits of a header byte mean a byte offset of a previous key.</p><p>Since in our semantics the keys are sorted, we can use the first 4 bytes describe the followng cases:</p><ul><li>the key is the same as the previous one, the whole key can then be reduced to 1 byte: [10000000]</li><li>the key doesn’t share any bytes with the previous one ([0000xxxx xxxxxxxx ...])</li><li>the key shares up to 14 prefix bytes with the previous one ([????xxxx xxxxxxxx ...]): ??? is big-endian encoded number 1 (001) to 14 (1110).</li><li>the key shares 15 or more bytes with the previous one ([1111xxxx ???????? xxxxxxxx ...]): where ???????? is an addition to 15.</li><li>for 15 bytes it will be [1111xxxx 00000000 ... ] (15 + 0)</li><li>for 16 bytes it will be [1111xxxx 00000001 ... ] (15 + 1)</li><li>for 32 byte it will be [1111xxxx 00010001 ... ] (15 + 17)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/709/1*EWoJyKYvmcYHbycJYBxiQQ.png" /><figcaption>KV-Witness Compression. The number in parenthesis tells how many bits to reuse from the previous key.</figcaption></figure><h4>Network Efficienty Research Results</h4><p><em>Raw data for the results is available in this GitHub repo: </em><a href="https://github.com/mandrigin/ethereum-mainnet-kv-witness-data"><em>https://github.com/mandrigin/ethereum-mainnet-kv-witness-data</em></a></p><p>To give a comprehensive image in terms of network efficiency, we compare 3 types of witnesses, all of them are running on hexary tries:</p><p>1) <strong>Opcode witness</strong>, the <a href="https://github.com/ethereum/stateless-ethereum-specs/blob/master/witness.md">existing one</a>. (Data is from <a href="https://github.com/mandrigin/ethereum-mainnet-bin-tries-data">my previous experiments</a>).</p><p>2) <strong>KV Witness(uncompressed)</strong>: no key prefix deduplication.</p><p>3) <strong>KV Witness(compressed)</strong>: key prefix deduplication is included.</p><p>Tests were conducted on blocks <strong>5.000.000–8.000.000.</strong></p><p><strong>Absolute size comparison</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tTU-r9uWqL6rfEc9B6kwoQ.png" /><figcaption>Absolute size comparison. Compressed KV witness behaves pretty much like the opcode witness.</figcaption></figure><p><strong>Quantile analysis</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iP0QawRnb_fB5w8fE6UPgg.png" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/645924819fd67bb929a1031f86e3e36f/href">https://medium.com/media/645924819fd67bb929a1031f86e3e36f/href</a></iframe><h3>Conclusion</h3><p>Key prefix deduplication does provide significant improvements to the KV witness. With it enabled, we have almost the same numbers between these two formats.</p><p>The KV Witness has a couple of advantages.</p><p>The main one is its simplicity. It is much easier to make a spec for a data format, essentially a dictionary, then a more complicated almost-programming-language approach.</p><p>The second advantage is that proof is semantically separate from the data, so when we want to change trie arity (from hexary to binary) or when we want to change the proof mechanics completely, it is will require less changes with the KV-Witness approach.</p><p>I think it is definitely a worthy contender for the witness spec standard.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8985168537f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ReGenesis Explained.]]></title>
            <link>https://medium.com/@mandrigin/regenesis-explained-97540f457807?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/97540f457807</guid>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[decentralization]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Sun, 28 Jun 2020 17:00:21 GMT</pubDate>
            <atom:updated>2020-06-28T17:00:21.669Z</atom:updated>
            <content:encoded><![CDATA[<p>The amount of money locked in DeFi apps surpassed $1.500.000.000; DApps are beign announced almost every day. At that rate, Ethereum can become a victim of its own success. One of the struggles on the infrastructure layer is boundless state growth.</p><p>A couple of days ago <a href="https://twitter.com/realLedgerwatch">Alexey</a> published an an <a href="https://ethresear.ch/t/regenesis-resetting-ethereum-to-reduce-the-burden-of-large-blockchain-and-state/7582">article at EthResearch forums</a> with an interesting idea on how to help with exactly that. He called it <strong><em>ReGenesis</em></strong>.</p><p>The idea is relatively simple and might look very radical at the first sight: <strong><em>let’s nuke all the state we have locally at deterministic schedule (say, every 1.000.000 blocks), keep the root hash of the latest block and then begin rebuilding the state from scratch until the next 1.000.000 blocks passes and next state extinction event happens</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gEy7w62hVTREJH2pnjO7GA.png" /><figcaption>ReGenesis: Reseting state every N blocks. State grows, witnesses shrink. Until the next ReGenesis.</figcaption></figure><p>To understand, why this idea might work and is worth researching, one needs some context and explanation.</p><p>This is what this post is exactly about.</p><h3>Current State of Affairs</h3><ol><li><strong>Centralisation of state storage.</strong> <br>It is very easy to send a transaction in Ethereum, to do that you don’t really need much state or anything. Transaction senders aren’t motivated to keep any state whatsoever.<br>If you are running an infrastructure node (a miner, or an exchange), at the other hand, you need to make sure that you have all the state possible to be able to validate the transaction and to propagate it further. Even more so if you are a miner.<br>That way, we have incentivies to centralize storage of the current state in infrastructure nodes who usually are being runned by bigger entities: Infura, big miners, exchanges, etc.</li><li><strong>Stage Growth Continues Unbounded.<br></strong>That is it, “current state” bucket in <a href="https://github.com/ledgerwatch/turbo-geth">Turbo-Geth</a> is about 40 GB at the time of writing and keeps growing. <br>The problem here is not the state size itself, but it uncapped growth. Sure, we might try to hope that fast SSD drives capacity is growing faster than the blockchain state. <br>We were lucky here so far, but being lucky isn’t a viable long-term strategy.</li><li><strong>Stateless Ethereum Gas Repricing is hard.<br></strong><a href="https://blog.ethereum.org/2020/01/28/eth1x-files-the-stateless-ethereum-tech-tree/">Stateless Ethereum</a> initiative has a very tricky job to price block witnesses. Those witnesses are produced by miners and it is difficult to predict when sending a transaction how big the block witness would be. <br>That way, it requires to somehow infere the witness price from smart contract behaviour without breaking existing smart contracts. <br>There were a couple of proposals there, notably <a href="https://ethresear.ch/t/oil-adding-a-second-fuel-source-to-the-evm-pre-eip/7394">Oil</a>, but it is a hard problem to solve.</li></ol><h3>Running transactions post-ReGenesis</h3><p>Okay, we all got the idea, you nuke all the current state except the root hash. Disk size goes 40GB → 32 bytes.</p><p>Amazing, disk space saved.</p><p>But how do I send transactions?</p><p>Stateless Ethereum comes to the rescue. To be able to run your transaction, you need to provide a witness. The witness consists of the state of used accounts, code and storage as well as Merkle proofs to be able to validate the root hash (more on witnesses and Stateless Ethereum <a href="https://github.com/ethereum/stateless-ethereum-specs">here</a>).</p><p>There is one difference between ReGenesis and Stateless Ethereum though. To explain that I would like to introduce 2 pieces of terminology: <strong><em>explicit</em></strong> state and <strong><em>implicit</em></strong> state.</p><p>Say, you are running a geth node now. Whenever you peer sends you a new block N, it assumes that you already have all the state needed to validate all transactions in this block, that you have synced to the block N-1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CulRHD7j638uDbQYBO-7ZA.png" /><figcaption>Today’s Ethereum: We imply that both nodes have all the state needed.</figcaption></figure><p>That is <strong><em>100% implicit state</em></strong>. Your peer implied that you already have the state and didn’t add to the block anything.</p><p>In Stateless Ethereum, when you run a node, and your peers send you a new block N, they assume that you have no implicit state whatsoever. They just include everything you can possibly need to run this block in the block itself. It is a Block Witness.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XDRamQg57ZurGY6-6b6O9g.png" /><figcaption>Stateless Ethereum: We provide all state as explicitly.</figcaption></figure><p>Your peer is sending you <strong><em>explicit state</em></strong>.</p><p>ReGenesis does something in between.</p><p>Let’s imagine ReGenesis has happened at the block 10.000.000. Right now the chain head is at the block 10.001.000. We can assume that any ReGenesis node has implicit state for everything between blocks 10m and 10,001m. Every account, every storage entry and every contract that was used in these blocks already exist on every node and don’t require a witness. That can reduce witness size substantially, as we saw in the <a href="https://medium.com/@mandrigin/semi-stateless-initial-sync-experiment-897cc9c330cb">semi-stateless sync experiment</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dxlo0fecsgySvMrWpOuDEg.png" /><figcaption>ReGenesis: Block 1 provides some information that does not exist on the Node1.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KAA-bFEpn287XYawDMSgNQ.png" /><figcaption>ReGenesis: the state from Block 1 is merged to Node 1’s implicit state.</figcaption></figure><p>If you, as a transaction senders need to send a new transaction to the network that is currently at the block 10.001.000, you need to follow these steps:</p><ul><li>create a transaction that you want;</li><li>take a look at the implicit state that was generated since the last ReGenesis;</li><li>create explicit state for the entries that are NOT inlcluded in implicit state, package it as a transacton witness (we will discuss what it is a bit later on);</li><li>send the transaction with the witness to the network;</li></ul><h3>Wait. That will require Transaction Senders to have some state even after ReGenesis!</h3><p>Yes.</p><p>If you want to send a transaction after ReGenesis, you might need some pre-ReGenesis state information to be able to generate a witness.</p><p>Though, for most DApps, that means that they need to store state of a minor subset of contracts and accounts they actually use (plus a Merkle Proof of course).</p><p>That makes this optimization a bit less dramatic to them. On the bright side, potentially shifts incentives to decentralise the data storage.</p><h3>Transaction Witnesses</h3><p>As you have probably noticed, I’ve mentioned transaction witnesses before.</p><h4>Transactional Witnesses vs. Block Witnesses</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hbpKhaChSSpHRPoNluYAkQ.png" /><figcaption>A single combined block witness.</figcaption></figure><p>Instead of having a witness for the whole block (a block witness), we have a witness per transaction.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ov1lw76iJ05LZfBsIj7_YA.png" /><figcaption>Transaction Witnesses</figcaption></figure><p>Transaction witnesses contain explicit state for all accounts, storage entries and code used in this transaction. They also contain a <a href="https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/">Merkle Proof</a> to ensure we can verify the state.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8CyTUiCoEWBcby81snTyIQ.png" /><figcaption>Block Witnesses are generated by a miner. We need a tricky gas pricing to compensate them.</figcaption></figure><p>Transaction witnesses have one important benefit. They are generated on the sender and are sent with the transaction. Hence, we know their size immediately and it is obvious how to price them. We don’t need EVM repricing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kOQqoWXOXKn9yNAmEo7VvA.png" /><figcaption>Transaction Witnesses are generated by senders create witnesses, much easier to compensate.</figcaption></figure><p>One potential downside of using transaction witnesses is the data duplication. If say, all transactions in the block will be between same accounts, transaction witnesses will contain duplicate data.</p><p>Another downside is a bit more complicated algorithm of applying those witnesses.</p><p>Block witnesses are generated on a miner. The miner knows the exact ordering of transactions to include, so the witness always contains up-to-date data.</p><p>Transaction witnesses that are sent from a sender. There should be an intelligent “merging” of the witness with implicit state generated by previous transactions in the block.</p><p>But the whole idea of ReGenesis would need it, so it isn’t that big of a deal.</p><h4>Why can’t we use transactional witnesses right now?</h4><p>A short answer a mix of Dynamic State Access and potential front-running transactions by malicious agents.</p><p>A longer answer is as follows.</p><p>In Stateless Ethereum you need to provide the full state for this transaction, we assume that the recipient has no state whatsoever. If your transaction uses Dynamic State Access, that means that which parts of the storage your code reads depends on values in other parts of the code.</p><p>That opens the possibility for the following theoretical DoS attack.</p><p>Alice has her smart contract reading either state entry A or B based on the storage value K. Bob can change this value K. Bob can frontrun his transactions before Alice.</p><p>That way if Alice provides a proof that contains A, Bob can change K before Alice’s transaction, so her transaction fails. If she provides a proof for B, he can again stop the transaction.</p><p>In this simple case, Alice can of course just provide both A and B, but if the address is determined by a uint64 or something similar Alice might have to include the full state in a proof to avoid this attack, which is impossible.</p><p>Of course, this attack is theoretical. But there might be more attacks possible in a similar manner. Moreover with the current amount of money in DApps, we need to be very careful not to break anything.</p><h4>How does ReGenesis help with mitigating that?</h4><p>Deterministic nature of ReGenesis helps to determine how much state the node does have. For the state, that we are sure exists on the node, we need no proof.</p><p>To mitigate the attack we need to be sure that <strong><em>the proof that we provide gets included in the state no matter if the transaction fails due to insufficient state or succeeds</em></strong>.</p><p>So, in the scenario described before.</p><p>When Alice sends a transaction with the proof with the path A, but Bob makes sure that the value at the address K is such that the Alice’s contract has to go to the path B.</p><p>Alice’s transaction fails, but it adds everything that the path A needs to the node’s implicit state.</p><p>Now Alice can re-send the transaction, this time providing the proof for the path B. Bob cannot stop this transaction by this switch anymore, because if he changes the variable at K such that is goes to the path A again, it is too late, it is in the implicit state, so the transaction can go there without any proof. For B, there is a proof.</p><h3>Conclusion</h3><p>Okay, so let’s recap the idea and its key points:</p><ul><li>every N blocks, we just remove all state, keeping only the root hash;</li><li>this event should be relatively rare, maybe each 1.000.000 blocks, maybe each 10.000.000 blocks or something;</li><li>to send a transaction, the sender will need to provide explicit state (as a Transaction Witness);</li><li>the sender pays gas for the transaction witness inclusion based on the witness size;</li><li>to achieve that, the sender will have to keep some pre-ReGenesis state for contracts/accounts it is interested in;</li><li>if the transaction fails due to insufficient explicit state, we add the provides state as implicit and we won’t require it on the next send;</li><li>there is a smart merging mechanism to merge explicit state from the transaction proof with implicit state of a node after running previous transactions in the block.</li></ul><p>As we can see, after zooming out and seeing a bigger picture, ReGenesis approach can <em>potentially</em>:</p><ul><li>shift the incentives balance between Transaction Senders and Infrastructure nodes to achieve higher decentralization of state storage;</li><li>limit state growth to growth between ReGenesis events (with a few caveats);</li><li>allow to use Transaction Witnesses and simplify gas pricing for each witness;</li></ul><p>Of course, a lot of these things should be tested, challenged and proved first. I think it is an interesting and very promising area of research that brings a surprising amount of potential benefits.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97540f457807" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Semi-Stateless Initial Sync Experiment]]></title>
            <link>https://medium.com/@mandrigin/semi-stateless-initial-sync-experiment-897cc9c330cb?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/897cc9c330cb</guid>
            <category><![CDATA[research]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[stateless-ethereum]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Wed, 12 Feb 2020 07:38:46 GMT</pubDate>
            <atom:updated>2020-02-12T07:42:43.619Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A1zUVYXI9ObrUyYKjCkk4w.png" /></figure><pre>Raw data and scripts for the experiment: <a href="https://github.com/mandrigin/ethereum-mainnet-resolver-witness-stats">https://github.com/mandrigin/ethereum-mainnet-resolver-witness-stats</a></pre><h3>***</h3><p>One of the possible ideas to speed up the initial sync process it to use block witnesses to pre-build the cache trie to avoid slow state access. That will cost additional disk space and network bandwidth but potentially can significantly speed up the sync process.</p><p>How will that work? Basically, to run each block, we need some data in a Merkle trie. Before the block execution we already have some nodes there, but it might not be enough to run the block. Normally, this data will be taken from the state db and then added to the trie while the transactions are being executed. That might be slow because of the disk access/db lookups.</p><p>So we have 3 types of a flow here:</p><p><strong>1)Normal flow (as currently in Ethereum nodes)</strong></p><ol><li>Before the block B is executed, we have a trie T1.</li><li>As we execute the block, we add missing bits and pieces to the trie, making it T1&#39;, T1&#39;&#39;, etc. Every time we miss some information, we look it up from the database (slow).</li><li>After the block B is executed we have the trie T2 that has all the account states to run the block B.</li><li>We keep T2 for the future resolutions.</li></ol><p><strong>2)Stateless flow</strong></p><ol><li>Before the block B is executed, we don’t have a trie and we have a witness W to reconstruct the trie required to run this block.</li><li>We execute W and get the trie T2.</li><li>We execute the block B on T2, no DB lookups needed.</li><li>We throw away T2 after the block is executed.</li></ol><p><strong>3)Semi-stateless flow (this experiment)</strong></p><ol><li>Before the block B is executed, we have a trie T1 and witnesses W1, W2, … enough to convert T1 into T2.</li><li>We execute W1, W2, etc on T1, and get the trie T2. No DB lookups needed.</li><li>We execute the block B on T2, no DB lookups needed.</li><li>We keep T2 for the future resolutions.</li></ol><p>Semi-stateless (3) flow on initial sync potentially gives most of the benefits<em>†</em> of the stateless flow (2), but should require less data to sync due to reusing trie cache.</p><p><em>†</em> parallel block execution will be limited to some extent with semi-stateless approach.</p><p>So, to test the Semi-Stateless approach, we need to measure 2 things:</p><ul><li>how much additional space/bandwidth is required for this approach; is it any better than the fully stateful approach?</li><li>how much faster does it make the initial sync.</li></ul><p>In this article, we will focus <strong>on the disk space.</strong></p><h4>Setting up the experiment</h4><ul><li>Max size of the trie (Merkle trie): <strong>1.000.000 </strong>nodes. When the number of nodes exceeds this value, the LRU nodes will be evicted to free up the memory. This way we can keep the used RAM under control.</li><li>The partial witnesses are stored in a db (<a href="https://github.com/ledgerwatch/bolt">our fork of boltdb</a>). Each entry has the following structure:</li></ul><pre>key: [12]byte // block number + max number of nodes in the trie<br>value: []byte // witnessses, serialized as <a href="https://github.com/ledgerwatch/turbo-geth/blob/master/docs/programmers_guide/witness_format.md">described in this doc</a></pre><ul><li>We don’t store the contract code in the witnesses (that is a limitation of the current architecture).</li></ul><p>How the data was collected (required a synced turbo-geth).</p><pre>(in the turbo-geth repository)</pre><pre>make state</pre><pre>./build/bin/state stateless \<br>     — chaindata ~/nvme1/mainnet/mainnet/geth/chaindata \ <br>     — statefile semi_stateless.statefile \<br>     — snapshotInterval 1000000 \<br>     — snapshotFrom 10000000 \<br>     — statsfile new_witness.stats.compressed.2.csv \<br>     — witnessDbFile semi_stateless_witnesses.db \<br>     — statelessResolver \<br>     — triesize 1000000 \</pre><h3>Experiment Results</h3><h4>Total Storage</h4><p>Witnesses DB (bolt db) to sync 6.169.246 blocks from scratch takes 99Gb</p><h4>Quantile analysis</h4><pre>python quantile-analysis.py cache_1_000_000/semi_stateless_witnesses.db.stats.1.csv</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*r6s2Miu98nekDIw5Q3KjgQ.png" /></figure><pre>mean   0.038 MB<br>median 0.028 MB<br>p90    0.085 MB<br>p95    0.102 MB<br>p99    0.146 MB<br>max    2.350 MB</pre><h4>Full Data</h4><pre>python absolute_values_plot.py cache_1_000_000/semi_stateless_witnesses.db.stats.1.csv</pre><p>Witnesses sizes for blocks from 1 to 6100.000, capped at 1.0 MB. Sliding avg 1024.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EDf7uct__tfXM5l5BppCBg.png" /></figure><h4>Normalized Data (after DDoSes)</h4><pre>absolute_values_plot.py cache_1_000_000/semi_stateless_witnesses.db.stats.1.csv 3000000</pre><p>Witnesses sizes after DDoS values, sliding avg 1024.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vpph855bId7E0fWZA9SqEA.png" /></figure><h4>DDos Zoom In</h4><pre>python ddos_zoom.py cache_1_000_000/semi_stateless_witnesses.db.stats.1.csv</pre><p>Zoomed in section to DDoSes influence on witnesses sizes (raw data).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QEGQffIoMRmN5RPl-ib4jA.png" /></figure><p>We can see that due to the DDoSes around blocks 2.3M-2.5M and 2.65M-2.75M the sizes of witnesses are significantly bigger.</p><h4>Full vs Semi</h4><pre>python full_vs_semi.py cache_1_000_000/semi_stateless_witnesses.db.stats.1.csv</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A-1fr0HA67naaQkbDM6W7w.png" /></figure><p>Full Witness sizes are adjusted for missing codes components.</p><p>As we see from this chart, using the semi-stateless approach saves quite a lot of data if we compare it to the full stateless approach.</p><h3>Conclusion</h3><p>Having a stateless resolver adds around 0.4 MB additional information per block that needs to be transferred/stored. That is significantly less data than having a witness per block even when we adjust for code (you can see some charts<a href="https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768"> in my previous post</a>).</p><p>If the performance is good that can be a good mode for the initial sync to speed it up, but requiring less data than a fully stateful approach.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=897cc9c330cb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Stateless Ethereum: Binary Tries Experiment]]></title>
            <link>https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/b2c035497768</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[merkle-tree]]></category>
            <category><![CDATA[experiment]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Fri, 03 Jan 2020 12:01:06 GMT</pubDate>
            <atom:updated>2020-01-03T16:46:24.407Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>data &amp; scripts for this article are in a github repo: <a href="https://github.com/mandrigin/ethereum-mainnet-bin-tries-data">https://github.com/mandrigin/ethereum-mainnet-bin-tries-data</a></blockquote><h3>What is Stateless Ethereum?</h3><p><em>If you are already familiar with what Stateless Ethereum &amp; Block Witnesses are, skip to the next part.</em></p><p>To run blocks and validate transaction, Ethereum nodes need to know the current state of the blockchain — all accounts &amp; contracts balances and storages. This data is typically stored in the DB and is loaded into a Merkle trie when needed (to be able to verify hashes).</p><p>Stateless Ethereum clients work a bit differently. As the name implies, they don’t use a disk DB to run blocks (they might keep a full state though). Instead, they rely on <strong><em>block witnesses</em></strong> — a special piece of data, distributed together with a block, using which, a client can recreate a Merkle subtree, sufficient to execute all transactions inside the received block.</p><p>You can read more in depth about stateless clients in this article: <a href="https://blog.ethereum.org/2019/12/30/eth1x-files-state-of-stateless-ethereum/">https://blog.ethereum.org/2019/12/30/eth1x-files-state-of-stateless-ethereum/</a></p><p>Of course, distributing block witnesses means that the stateless nodes will use more traffic than regular nodes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MeBN8JBgQSM9Wk7_zznZsg.png" /><figcaption>witness size chart (block 5.000.000–8.500.000)</figcaption></figure><p>There are a couple of ideas floating around on how to reduce the size of witnesses: using Validity / Computational Integrity Proofs (including but not limited to Zero-Knowledge), adding some compression, etc. One of the areas is switching Ethereum from hexary Merkle tries to the binary ones.</p><p>That is what this article is exploring. Let’s go.</p><h3>Why Binary Tries?</h3><p>One great property of Merkle tries is that you can validate the root hash even if you don’t have the full trie. In order to do that, every missing, but not empty path in the trie should be replaced with an appropriate hash value.</p><p>What is the problem with the hex tries?</p><p>Imagine that the full trie is filled with data (nodes have almost no nil children). To validate a single block we only need a relatively small percentage of nodes. So, we need to replace all the other paths with hashes to make this trie verifiable.</p><p>Each hash is something that adds more data to the block witness footprint.</p><p>If we switch to binary tries we can theoretically mitigate this issue because each node only has 2 children, so at most one of them will be replaced with a hash. (To paraphrase it, that means that we can “cut” the Merkle paths earlier, because our granularity is 1 bit instead of 4 bits in a hex trie).</p><p>That should cut the witness sizes significantly.</p><p>Let’s look at an example.</p><p>Imagine, that to run our block we only need one account: <strong>Acc1</strong> with the path <strong>3B (0011 1011)</strong>. The tries are fully packed (nodes have no <strong>nil</strong> children).</p><p>Representations of the subtries that we need to be able to run our imaginary block are on the drawings below (in both hex and bin form).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*KPyXN2WkH04SZGp58adnqA@2x.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/729/1*tZhCtx-bBxCLRlu229VHBg@2x.jpeg" /><figcaption>bin trie (left) | hex trie (right)</figcaption></figure><p>The binary trie might look a bit more intimidating, but if that’s because I didn’t want to draw all the hash nodes in the hex trie.</p><p>So let’s count.</p><ul><li>To produce a binary trie, the witness needs to contain 8 hashes, 7 branch nodes and 1 account node. That is 16 block witness elements.</li><li>To produce a hexary trie we need just one branch node, one account node and 15*2 = 30 hashes. That is 32 hash elements.</li></ul><p>So, assuming that hashes and branches take the same amount of space in the block witness (they don’t, hashes are bigger), in our case the bin trie require a witness twice as small than the hex trie needs. Sounds cool.</p><p>That’s the theory.</p><p>Let’s see now how it works in practice. Let’s dive into the wilderness of the Ethereum mainnet.</p><h3>Setting Up The Experiment</h3><p>First things first: how do we validate if the produced block witness is usable?</p><p>To test that, we use the witness to produce a Merkle subtrie, run all the block’s transactions on it and validate the result. As long as all the transactions are executed successfully (there is enough gas, they have the same traces, etc), we can be sure that this witness is at least sufficient.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BVnqt4IQ_rMteE0NspoYSA.png" /><figcaption>How we test (from <a href="https://github.com/ledgerwatch/turbo-geth/blob/master/cmd/state/stateless/stateless.go">https://github.com/ledgerwatch/turbo-geth/blob/master/cmd/state/stateless/stateless.go</a>)</figcaption></figure><p>Secondly, we need some baseline data. For that, we got stats on the witness sizes using hex tries for the blocks 5.000.000–8.500.000 to compare and stored them in a gargantual csv file.</p><p>Our first attempt was to take a hex trie after a block is executed and convert it to a binary one just before extracting the witness from it.</p><p>This approach has some benefits: it is easier to implement, also it is trivial to validate that hex-to-bin conversion.</p><p>Unfortunately, we ran into two problems, one of them was critical.</p><p>First of all, as it turned out, hex tries contain more account nodes than similar binary tries. So, if we are converting them later, we don’t get the exact witnesses as it would be if we just had binary tries from the start.</p><p>Why is that?</p><p>That is due to a fact that hex tries always grow their height in 1/2 byte intervals. Bin tries grow in just 1 bit interval, that makes it possible to have tries with key length with odd number of bits.</p><p>In practice, there are some additional EXTENSION nodes in the witnesses and they are ever so slightly bigger. But even for big blocks (~5000 transactions) this difference was quite small comparing to the witness size (&lt; 5%).</p><p>What was critical is the performance. With the growth of the trie, the conversion was slower and slower.</p><p>To put it in numbers, on our Google Compute Engine VM, the processing speed was around 0.16 block/second. That is less than 10 blocks per minute. To process 1.000.000 blocks we need more than 3 months. Oops.</p><p>So, we decided to go with a more complicated approach and built an experimental branch that uses binary tries natively. That means, that we replaced all hex tries in turbo-geth codebase with bin tries, so the blocks always run on binary tries.</p><p>On the downside, a few hashes checks had to be ignored (block root hash, and sometimes account storage hashes due to a limitation of our blockchain snapshots mechanism).</p><p>But the main verification mechanism stayed the same: we should be able to execute blocks using bin tries and subtries generated from witnesses.</p><p>Let’s talk about keys.</p><p>For simplicity, we encode keys very inefficiently: 1 byte per nibble; 1 byte per bit of a key. That simplified the code changes <em>a lot, </em>but<em> </em>the<em> </em>&quot;keys” component of the block witness (see <a href="https://medium.com/@akhounov/data-from-the-ethereum-stateless-prototype-8c69479c8abc">this article</a> to learn what a witness consists of) is 8 times bigger than it should be, if we used bitsets (as we should).</p><p><strong>So, for the further analysis I will assume that all keys are optimal (they encode 1 bit of information using 1 bit of memory).</strong></p><h3>Hex vs. Bin: Results</h3><p>I ran the analysis on 2m blocks from the Ethereum mainnet in 2 intervals.</p><h4>blocks 5.000.000–6.500.000</h4><p>I will also provide commands to repeat the experiment using python scripts in the github repo: <a href="https://github.com/mandrigin/ethereum-mainnet-bin-tries-data">https://github.com/mandrigin/ethereum-mainnet-bin-tries-data</a></p><p>First, let’s analyze or dataset a bit.</p><pre>python percentile.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CoNwfILjAfHnWilDQk8WCg.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Box_plot">a box plot</a>, with the box between P25-P75 and whiskers between P1-P99</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2268eaedbf9840e41a96507ad8b7c3d5/href">https://medium.com/media/2268eaedbf9840e41a96507ad8b7c3d5/href</a></iframe><p>Now let’s make some cool charts!</p><pre>python xy-scatter-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OeVmZa14ZzE2yMaybQgj1g.png" /><figcaption>XY scatter-plot (adjusted for optimal keys)</figcaption></figure><p>As we see here, the size of binary witnesses is always better with binary tries.</p><p>Let’s plot another parameter, and divide our binary witness sizes to hex witness sizes to see what kind of improvement we can get.</p><pre>python size-improvements-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FvUHVt0hZuhWZew-dNcQ2Q.png" /><figcaption>size of binary witness / size of hex witness (the smaller the better) across blocks</figcaption></figure><p>To understand this chart better, we can also print average, mean and percentile values like before.</p><p>mean = 0.51 = improvement 49%<br>p95 = 0.58 = improvement 42%<br>p99 = 0.61 = improvement 39%</p><p>What does it mean in practice?</p><p>For <strong>99%</strong> of the blocks you will get <strong>at least 39%</strong> improvements in the witness size.<br>For <strong>95%</strong> of the blocks you will get <strong>at least 42%</strong> improvements in the witness size.<br>On average, you will get 49% improvements of the witness size.</p><p>Let’s also see the absolute values of witnesses. To make them readable, let’s pick a sliding average of 1024 blocks.</p><pre>python absolute-values-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SDmJC-MqYRmxfjy8qKm0EQ.png" /><figcaption>Witnesses sizes in MB across the timeline</figcaption></figure><p>Now, let’s repeat everything for the newer blocks.</p><h4>blocks 8.000.000–8.500.000</h4><pre>python percentile.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v_ktGhCj0EbA3hqHOidAyQ.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Box_plot">a box plot</a>, with the box between P25-P75 and whiskers between P1-P99</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/735d8cb844822a270f12522861fcec59/href">https://medium.com/media/735d8cb844822a270f12522861fcec59/href</a></iframe><p>Now the XY scatter-plot</p><pre>python xy-scatter-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RxhZ0VNlHyJZVSLo_Ndrgg.png" /></figure><p>…and size improvements</p><pre>python size-improvements-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Io8zLlBK5xpUEwE61YJ48Q.png" /><figcaption>size of binary witness / size of hex witness (the smaller the better) across blocks</figcaption></figure><p>mean = 0.53 = 47% improvements<br>p95 = 0.61 = 39% improvements<br>p99 = 0.66 = 34% improvements</p><p>And, finally, let’s plot witness sizes</p><pre>python absolute-values-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9QJ9IeWjk86nTPSqgi_5aQ.png" /><figcaption>Witnesses sizes in MB across the timeline</figcaption></figure><h3>Conclusion</h3><p>After running our tests on the real Ethereum mainnet data, we can see that indeed, switching to binary tries will give some significant improment for binary witness generation (bin witnesses are 47–49% smaller on average).</p><p>One more outcome is that this improvement isn’t as dramatic as the theoretical best case scenario. Possibly it is due to the real data layout in the mainnet blocks.</p><p>Probably, by analyzing some edge cases (where bin tries gave the least improvement) we can come up to more ways to improve block witnesses size.</p><p>Feel free to play with the raw data and scripts in the GitHub repo: <a href="https://github.com/mandrigin/ethereum-mainnet-bin-tries-data">https://github.com/mandrigin/ethereum-mainnet-bin-tries-data</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b2c035497768" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Mobile Energy Efficiency BoK]]></title>
            <link>https://medium.com/@mandrigin/mobile-energy-efficiency-bok-dce36f3787f7?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/dce36f3787f7</guid>
            <category><![CDATA[android-development]]></category>
            <category><![CDATA[mobile-app-development]]></category>
            <category><![CDATA[ios-development]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Tue, 01 Jan 2019 12:55:58 GMT</pubDate>
            <atom:updated>2019-01-01T12:55:58.175Z</atom:updated>
            <content:encoded><![CDATA[<p>Happy New Year everyone!</p><p>While working at <a href="https://status.im/">Status</a>, I put together a small guide on testing energy efficiency of a mobile app.</p><p>Of course, some of the parts there are Status-specific, but there is enough information useful for the general public.</p><p>Here is it: <a href="https://github.com/status-im/energy-efficient-bok">https://github.com/status-im/energy-efficient-bok</a>.</p><p>Sections of this BoK that have the most interesting parts are:<br>* <a href="https://github.com/status-im/energy-efficient-bok/blob/master/ENERGY_GUIDE_DEV.md">Dev Guide</a> — a short document describing what affects energy efficiency and how to test it in development.<br>* <a href="https://github.com/status-im/energy-efficient-bok/blob/master/QA_Android.md">Using Battery Historian</a> — how to use <a href="https://developer.android.com/studio/profile/battery-historian">Battery Historian</a> to test energy efficiency on Android.<br>* <a href="https://github.com/status-im/energy-efficient-bok/blob/master/QA.md#introduction">Testing and interpreting results</a>.</p><p>Special shoutout to <a href="https://github.com/lukaszfryc">Lukasz</a> for helping putting this BoK together.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dce36f3787f7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ethereum node services explained]]></title>
            <link>https://medium.com/@mandrigin/ethereum-node-services-explained-5f7d7fe29f1?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/5f7d7fe29f1</guid>
            <category><![CDATA[dapps]]></category>
            <category><![CDATA[ethereum-blockchain]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Wed, 02 May 2018 08:43:44 GMT</pubDate>
            <atom:updated>2018-05-02T08:43:44.436Z</atom:updated>
            <content:encoded><![CDATA[<iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FO43KYgws9Ec&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DO43KYgws9Ec&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FO43KYgws9Ec%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/eced6fb00a9e2cecab3b4beaf3210a25/href">https://medium.com/media/eced6fb00a9e2cecab3b4beaf3210a25/href</a></iframe><p>I did a short explanation about how <a href="https://status.im/">https://status.im</a> interacts with Ethereum. I think it is a decent explanation about how Ethereum RPC APIs work and how to tweak them.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5f7d7fe29f1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Keeping track of development tasks]]></title>
            <link>https://medium.com/@mandrigin/keeping-track-of-development-tasks-2908f59dcd1a?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/2908f59dcd1a</guid>
            <category><![CDATA[productivity]]></category>
            <category><![CDATA[development]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Thu, 15 Mar 2018 12:17:06 GMT</pubDate>
            <atom:updated>2018-03-15T12:17:37.715Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RKvhOzTcV6MXPD3AF1hDzw.jpeg" /></figure><p>When we implement a change in a codebase, it isn’t a single task. It’s a whole project, containing creating new objects, abstractions, functions and methods. We alter a few behaviours, we workaround platform-specific issues. If a change we are implementing isn’t trivial, then development lasts for weeks. It is very easy to forget all the details you knew about it.</p><p>If course, that is where different task manager apps are supposed to help. Except they usually don’t. They are usually too inconvenient to keep track of these tactical tasks.</p><p>Can we do better than that?</p><p>Let’s look at the outside world. When a carpenter fixes furniture or build a new summer house, she doesn’t keep every in a TODO application. They rely heavily on making a lot of marks on the material they are working with.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ho6_SHR9SyHjKEnQi6cGLQ.jpeg" /><figcaption>🤔</figcaption></figure><p>When a road worker needs to change asphalt they don’t keep the exact coordinates of the places to dig in their notebook either.</p><p>So, let’s keep all the tactical tasks in the source code itself.</p><h4>Handling tasks inside the source code.</h4><p>FIXMEs and TODOs, are already used quite heavily in the source code. But, these labels are usually “Someday/Maybe/Never” kind of tasks.</p><p>Let’s use the same technique to keep all the tactical tasks we need to do achieve when implementing a new feature, doing a refactoring and taming bugs.</p><p>I personally prefer to use a separate prefix for these kinds of tasks, to not being mixed with TODOs: TASK.</p><p>Write down as much as you can, don’t keep the tasks needed to do in your head.</p><p>Now, we have a super developer friendly task list for our feature. We can always search for TASKs through the workspace and find what we wanted to change. Each task will bring you to the place you need to finish this task. No app switching, no context switching.</p><p>When the work is done, there shouldn’t be any TASKs left. If there are, they might be converted to TODO, FIXME, etc for documentation purposes.</p><pre>let iTunesSetting = BoolSetting(id: &quot;pause_itunes_if_playing&quot;, name: &quot;When the timer fires: Pause iTunes if playing&quot;)<br><br>// TASK: Create and register DND setting here<br><br>let settingsModel = SettingsModel(settings: [globalHotkeySetting, iTunesSetting])</pre><pre>func loadFromDB() *Model {<br>    // TASK: implement Model loading from the DB<br>}</pre><pre>function handleAppStateChange(state) {<br>   // TASK: handle all possible states from React Native docs:<br>   // see: https://facebook.github.io/react-native/docs/appstate.html<br>   <br>   // TASK: add logging if invalid state is passed<br>}</pre><p>What to do with some more general tasks? Research, read, review. Well, since all the tasks will be displayed at the same time, you can put them anywhere. Even README will do.</p><p>The benefits are obvious:</p><ul><li>no need to switch between a dev environment and a task manager app;</li><li>location of the task itself becomes a part of context;</li><li>it’s compatible with any editor;</li><li>checks are easily automated;</li><li>you can push the code with these TASK for pre-review.</li></ul><p>Hope that simple trick will help you to keep track of longer projects.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2908f59dcd1a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[GTD & Choosing What to Do Next]]></title>
            <link>https://medium.com/@mandrigin/gtd-choosing-what-to-do-next-f46a0cbb31bf?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/f46a0cbb31bf</guid>
            <category><![CDATA[leadership]]></category>
            <category><![CDATA[getting-things-done]]></category>
            <category><![CDATA[project-management]]></category>
            <category><![CDATA[productivity]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Mon, 11 Sep 2017 08:31:39 GMT</pubDate>
            <atom:updated>2017-09-11T08:31:39.805Z</atom:updated>
            <content:encoded><![CDATA[<p>In my <a href="https://hackernoon.com/how-to-maximize-efficiency-when-working-on-product-93b346881749">previous post</a> I’ve discussed what a team leader or a manager can do to optimize the flow of tasks, especially in the beginning of a project.</p><p>Re-reading “<a href="https://en.wikipedia.org/wiki/Getting_Things_Done">Getting Things Done</a>”, I stumbled upon a following story:</p><blockquote>One manager, who had taken over responsibility many months in advance for organizing a major annual conference, asked me how to prevent the crisis all-nighters her team had experienced near the deadline of the previous year. When she produced an outline of the various pieces of the project she’d inherited, I asked, “Which pieces could actually be moved on right now?” After identifying half a dozen, we clarified the next action on each one. It was off and running, in time to prevent a repeat of the previous year’s last-minute chaos.</blockquote><blockquote>Allen, David. Getting Things Done: The Art of Stress-free Productivity (Kindle Locations 1848–1852). Little, Brown Book Group. Kindle Edition.</blockquote><p>That’s a very good generalization of the same principle.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f46a0cbb31bf" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[On Choosing What To Do Next]]></title>
            <link>https://medium.com/hackernoon/how-to-maximize-efficiency-when-working-on-product-93b346881749?source=rss-b63376527faf------2</link>
            <guid isPermaLink="false">https://medium.com/p/93b346881749</guid>
            <category><![CDATA[effectiveness]]></category>
            <category><![CDATA[management]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[productivity]]></category>
            <dc:creator><![CDATA[Igor Mandrigin]]></dc:creator>
            <pubDate>Mon, 07 Aug 2017 09:14:49 GMT</pubDate>
            <atom:updated>2019-05-06T08:59:53.415Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XkC4nLB97785R0n1kQfErA.jpeg" /><figcaption>Image credits: <a href="https://www.flickr.com/photos/alpoma/">Alejandro Polanco</a></figcaption></figure><p>So, you are a <a href="https://hackernoon.com/tagged/technical">technical</a> leader and you and your team is building a product. There are <em>a lot</em> of moving parts: the requirements that constantly fail to be static and well defined, the company’s infrastructure is moving forward somewhat, the <a href="https://hackernoon.com/tagged/codebase">codebase</a> you are working on.</p><p>How to keep the development efficient and not stall while some decisions were not made just yet? How to tackle changing environment? What to do next on the project?</p><p>I use a simple heuristics that I found very useful for that.</p><h4>The Heuristic</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FnWBBaAKfH1stRSgDQijxA.jpeg" /><figcaption>Image credit: <a href="https://www.flickr.com/photos/nmaicas/">Natalio</a></figcaption></figure><p>Imagine your product should be released just now.</p><p>Will that happen? No? Why exactly? What is blocking it?</p><p>Be very specific about the reasons and put it into one of the two buckets: <em>technical reasons</em> and <em>product reasons</em>.</p><p>I use terminology a bit loosely. The product reasons are the features that should exist in the product.</p><p>If all the reasons why your product won’t be released today are solely in the product category (like, it can be deployed today, it is tested, but one of the critical features is missing), then you have nothing else to do than start working on this missing feature.</p><p>Usually though, that’s not the case. There are plenty of technical obstacles to be solved or avoided before the product can be released.</p><p>I suggest to focus on the technical issues as soon as possible.</p><p><strong>Why focusing on technical issues first?<br></strong>Business is not static. While you are building the product, requirements and priorities might shift a couple of times. You, as technical expert, need to keep product in a releasable state all the time, with any set of features.</p><p><strong>The Technical reasons<br></strong>Some types of technical reasons to think about:</p><ol><li>Deployment. Do you already have all the servers up and running? Is there a build/deploy script? Are all the store accounts set up? Are signing keys or SSL certificates already in place?</li><li>Analytics &amp; Monitoring. Is a crash reporter integrated in your app? Do you monitor all the parameters than you need to monitor?</li><li>Security. Was your app security-reviewed in any way? Do you use a strong encryption? Is your auth/auth safe enough for the wild west of the Internet?</li><li>Was the product thoroughly tested? Are the existing features good enough to be released in public? Are all the assets correct?</li><li>L10N &amp; I18N. Is the product localized? Are the translations ready and checked?</li><li>Legal issues. Is the EULA ready? Is the Privacy Policy up-to-date? Did you mention all the libraries you use? Are all the 3rd party libraries have right licences?</li></ol><p>Some of these technical reasons might sound pretty non-technical. But technical decisions aren’t only related with the code written, they are much more than that.</p><p>Not all the reasons might be easily go into one category, or another.</p><p>Sometimes, you might get blocked by some agreement or just email chain or something else. Don’t just wait for it, remember the concurrent programming model and switch yourself to the next reason unsolved.</p><p>This simple heuristics helped me a lot with building my projects, and I hope it will help you to build yours as efficient as possible.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fupscri.be%2Fdde502%3Fas_embed%3Dtrue&amp;dntp=1&amp;url=https%3A%2F%2Fupscri.be%2Fhackernoon%2F&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=upscri" width="800" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/3c851dac986ab6dbb2d1aaa91205a8eb/href">https://medium.com/media/3c851dac986ab6dbb2d1aaa91205a8eb/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=93b346881749" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/how-to-maximize-efficiency-when-working-on-product-93b346881749">On Choosing What To Do Next</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>