<?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 Lucas Amorim on Medium]]></title>
        <description><![CDATA[Stories by Lucas Amorim on Medium]]></description>
        <link>https://medium.com/@lucasaamorim?source=rss-ac8de99211f9------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*_dum_Nqdb3wOxd14GXbn8A.jpeg</url>
            <title>Stories by Lucas Amorim on Medium</title>
            <link>https://medium.com/@lucasaamorim?source=rss-ac8de99211f9------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 14:38:35 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@lucasaamorim/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[CodeQL for Solidity: Bringing Semantic Code Analysis to Smart Contracts]]></title>
            <link>https://medium.com/@lucasaamorim/codeql-for-solidity-bringing-semantic-code-analysis-to-smart-contracts-4568dcb3160b?source=rss-ac8de99211f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/4568dcb3160b</guid>
            <dc:creator><![CDATA[Lucas Amorim]]></dc:creator>
            <pubDate>Tue, 03 Feb 2026 18:39:09 GMT</pubDate>
            <atom:updated>2026-02-07T23:31:06.850Z</atom:updated>
            <content:encoded><![CDATA[<p>Smart contract security tooling has a false positive problem. Tools like Slither and Mythril are indispensable for auditors, but anyone who’s run them on a real codebase knows the drill: sift through dozens of findings, most of which don’t matter, to find the handful that do. The signal-to-noise ratio gets worse as contracts grow in complexity.</p><p>I’ve been thinking about this gap for a while. As someone who audits smart contracts and builds static analysis tools professionally, I wanted something that could reason about Solidity code at a deeper level, not just pattern matching, but actual dataflow analysis, taint tracking, and call graph resolution.</p><p>GitHub’s CodeQL engine does exactly this for languages like Java, C++, Go, and Python, but it has never officially supported Solidity.</p><p>So I built it. <a href="https://github.com/lucasallan/codeql-solidity">codeql-solidity</a> is an open-source CodeQL extractor and query library for Solidity. It lets you treat your smart contract source code as a queryable database and write precise, semantic queries to find vulnerabilities.</p><h3>Why CodeQL?</h3><p>CodeQL treats source code as data. You create a database from your codebase, then write queries in QL (a declarative, logic-programming language related to Datalog) to find patterns. The key advantage over regex-based or AST-only tools is that CodeQL understands how data flows through your program. You can ask questions like “does user input reach this external call without passing through a check?” and get precise answers.</p><p>For traditional software, this is a solved problem: GitHub ships CodeQL support for C/C++, Java, C#, Go, JavaScript, Python, Ruby, Swift, and recently Rust. <br>But Solidity has been left out, despite being the language where a single missed vulnerability can mean millions of dollars drained from a protocol.</p><p>There’s been prior work in this space. CoinFabrik’s CyScout project explored a similar approach, adapting CodeQL’s Ruby extractor pipeline for Solidity.</p><p>My project takes a different path: a clean, independent implementation with a Rust-based extractor, published as installable CodeQL packs, with dataflow, taint tracking, and inheritance analysis built in.</p><h3><strong>How It Works</strong></h3><p>The architecture follows the same pattern that CodeQL uses for its officially supported languages:</p><p><strong>Tree-sitter Parsing</strong> → The extractor uses tree-sitter’s Solidity grammar to parse source files into concrete syntax trees. Tree-sitter is battle-tested, incremental, and handles error recovery well, important when you’re analyzing contracts that might not compile cleanly.</p><p><strong>Rust Extractor</strong> → A Rust binary walks the tree-sitter AST and emits TRAP files (CodeQL’s intermediate representation format). This is the bridge between raw Solidity source and a CodeQL database. The extractor also generates the database schema (solidity.dbscheme) and the base QL library (TreeSitter.qll) directly from the grammar definition.</p><p><strong>QL Libraries</strong> → On top of the auto-generated AST representation, the QL library (lucasamorimca/solidity-all) provides the abstractions you need for real analysis: dataflow, taint tracking, call graphs, and contract inheritance resolution.</p><h3>Getting Started</h3><p>Installation is straightforward if you already have the CodeQL CLI:</p><pre># Install the packs<br>codeql pack install lucasamorimca/solidity-all<br>codeql pack install lucasamorimca/solidity-queries<br><br># Download the extractor from GitHub Releases<br># Set up the extractor path<br>export CODEQL_EXTRACTOR_SOLIDITY_ROOT=/path/to/extractor-pack<br><br># Create a database from your contracts<br>codeql database create my-db \<br>  --language=solidity \<br>  --source-root=/path/to/contracts<br><br># Run the security queries<br>codeql database analyze my-db lucasamorimca/solidity-queries \<br>  --format=sarif-latest \<br>  --output=results.sarif</pre><p>The output is standard SARIF, so it plugs into whatever tooling you already use for triaging findings.</p><p><strong>Writing Custom Queries</strong></p><p>This is where CodeQL really shines compared to other static analyzers. Instead of being limited to a fixed set of detectors, you can write your own queries against the full semantic model of the code. If you’ve audited a protocol and found a novel vulnerability class, you can encode that knowledge as a query and run it across every Solidity codebase you encounter from that point forward.</p><p>The QL library exposes Solidity-specific constructs, function definitions, modifiers, state variables, external calls, inheritance hierarchies, through a clean, declarative API. Combined with CodeQL’s built-in dataflow and taint tracking libraries, you can express complex security properties concisely.</p><p>Building from Source</p><p>The extractor is written in Rust. If you want to build it yourself or contribute:</p><pre>cd extractor<br>cargo build --release<br><br># Regenerate the schema and QL library from the grammar<br>./target/release/codeql-extractor-solidity generate \<br>  --dbscheme ../ql/lib/solidity.dbscheme \<br>  --library ../ql/lib/codeql/solidity/ast/internal/TreeSitter.qll</pre><p>The project is Apache-2.0 licensed. Contributions, bug reports, and new query ideas are all welcome.</p><h3>What’s Next</h3><p>his is an early release. The foundation is solid: parsing, database creation, and the core analysis libraries all work, but there’s a lot of room to grow the query library. <br>Reentrancy variants, access control misconfigurations, flash loan attack patterns, price oracle manipulation, and dozens of other vulnerability classes specific to DeFi protocols are all expressible in QL and waiting to be written.</p><p>If you’re a security researcher or auditor working in the Solidity ecosystem, I’d encourage you to try it out and see what queries you can build. The entire point of making this open source is that the community can contribute detectors based on real-world findings, and everyone’s analysis gets better as a result.</p><p>The repo is at <a href="https://github.com/lucasamorimca/codeql-solidity">github.com/lucasamorimca/codeql-solidity</a>. Issues and PRs are open.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4568dcb3160b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Schnorr Nonce Generation: When "Random" is (and isn’t) a Vulnerability]]></title>
            <link>https://medium.com/@lucasaamorim/schnorr-nonce-generation-when-random-is-and-isnt-a-vulnerability-b79d33676c0b?source=rss-ac8de99211f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/b79d33676c0b</guid>
            <category><![CDATA[security-assessments]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[security]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Lucas Amorim]]></dc:creator>
            <pubDate>Mon, 29 Dec 2025 08:39:32 GMT</pubDate>
            <atom:updated>2025-12-29T08:39:32.441Z</atom:updated>
            <content:encoded><![CDATA[<p>A technical analysis of nonce security in Schnorr signatures, and how threat model and deployment context determine vulnerability.</p><p>Part of my work as a Security Researcher at <a href="https://www.webacy.com/">Webacy</a> is building static analysis tools. Recently, I’ve been developing security analysis tooling for crypto projects written in Rust. Before writing the detectors, I audited several open source Rust cryptography projects to calibrate detection heuristics against real world code patterns.</p><p>During an audit, I encountered this pattern:</p><pre>pub fn sign&lt;R: Rng + CryptoRng, T: Tagged&gt;(&amp;self, rng: &amp;mut R, msg: &amp;T) -&gt; Signature {<br>let k: pp::Fr = rng.gen(); // Nonce generation<br>…<br>}</pre><p>An external RNG generating a Schnorr nonce. This pattern has historically been the source of catastrophic cryptographic failures, but context determines whether it constitutes an actual vulnerability.</p><p><strong>Historical Context: The $170 Million Lesson</strong></p><p>In 2010, Sony shipped every PlayStation 3 with the same ECDSA signing key. Security researchers would eventually need that key to run homebrew software. Sony’s cryptographers knew better than to expose it directly, the key was locked in tamper-resistant hardware.</p><p>However, the implementation contained a critical flaw:</p><pre>ECDSA signature: (r, s) where s = k⁻¹(z + r·sk)</pre><p>The variable <strong><em>k</em></strong> is the <strong><em>nonce</em></strong>. It must be unique for every signature. Sony’s implementation used the same <strong><em>k</em></strong> for every signature as a constant value.</p><p>At the 27th Chaos Communication Congress, the <a href="https://fail0verflow.com/">fail0verflow</a> group demonstrated that with two signatures sharing the same nonce, the private key can be recovered through straightforward algebra:</p><pre>s₁ - s₂ = k⁻¹(z₁ - z₂)<br>k = (z₁ - z₂) / (s₁ - s₂)<br>sk = (s₁·k - z₁) / r</pre><p>Sony’s master signing key was published. The PS3 was permanently compromised. Estimated impact was $170 million in piracy losses.</p><p>Three years later, a flaw in Android’s <em>SecureRandom</em> caused the same class of failure. Bitcoin wallets were drained. $5.7 million lost.</p><p><strong>The Attack Vector</strong></p><p>The mathematical foundation of nonce reuse attacks in Schnorr signatures follows similar principles.</p><p><strong>Schnorr signature construction</strong></p><pre>Signing: s = k + e·sk (where e = H(R, PK, m))<br>Two sigs: s₁ = k + e₁·sk<br>s₂ = k + e₂·sk</pre><p><strong>With identical nonce k</strong> (requires <strong><em>e₁ ≠ e₂</em></strong>, guaranteed when messages differ since <strong><em>e = H(R, PK, m))</em></strong>:</p><pre>s₁ - s₂ = (e₁ - e₂)·sk<br>sk = (s₁ - s₂) · (e₁ - e₂)⁻¹</pre><p>Complete private key recovery from two signatures.</p><p><strong>A note on threat modeling:</strong> All these attacks: VM snapshot state reuse, fork inherited RNG buffers may sound esoteric. But cryptography operates under a different standard: if a theoretical attack exists, we assume a sufficiently motivated adversary will find it. The PS3 and Android incidents weren’t discovered by nation states with unlimited resources; they were found by independent security researchers. Cyptographic systems require mathematical certainty or explicit acknowledgment of the threat model boundaries.</p><p><strong>Specification Analysis</strong></p><p>When auditing cryptographic implementations, the specification is the authority in the threat modeling. In this case, the protocol’s cryptographic specification document defined the signing algorithm as follows:</p><pre>Sig.Sign(sk, m):<br>1. r ←$ F ← Note this notation<br>2. Δ ← [r]·G<br>3. c ← H(PK, Δ, m)<br>4. z ← c·sk + r<br>5. Return (Δ, z)</pre><p>The specification explicitly mandates random nonce generation. The implementation is correct.</p><p><strong>Why random over deterministic?</strong> Protocol designers choose <strong><em>r ←$ F</em></strong> for several reasons: simplicity of specification (no need to define HMAC-DRBG parameters), elimination of HMAC side-channel concerns in the signing path, and compatibility with hardware security modules that may have high-quality entropy sources but limited programmability. The tradeoff is accepting RNG quality as a security dependency.</p><p>This raises an important distinction: an implementation matching its specification is not vulnerable, even if alternative designs exist with different security properties.</p><p><strong>Random vs Deterministic Nonce Generation</strong></p><p>Two valid approaches to nonce generation exist in signature schemes:</p><p><strong>Random nonces</strong> (<em>k ← random()</em>) are used by many academic protocols and BLS signatures. They’re secure when the RNG is cryptographically secure, the implementation is correct, the execution environment doesn’t introduce state reuse (VM snapshots, process forks), and sufficient entropy is available.</p><p><strong>Deterministic nonces</strong> (<em>k = HMAC(sk, message)</em>) following<a href="https://datatracker.ietf.org/doc/html/rfc6979"> RFC 6979</a> are used by Bitcoin, Ethereum, and modern wallets. They’re secure when HMAC-DRBG is implemented correctly, sidechannel protections are in place, and signature determinism is acceptable.</p><p><strong>The audited implementation:</strong></p><blockquote>- Requires <em>CryptoRng </em>trait (Rust’s marker for cryptographically secure RNG)</blockquote><blockquote>- Uses <em>OsRng</em> or <em>thread_rng</em>() in all calling code</blockquote><blockquote>- Targets controlled server infrastructure</blockquote><blockquote>- Does not include VM snapshot/restore in the threat model</blockquote><p>The implementation is secure within its specified threat model.</p><h4><strong>Failure Modes for Random Nonces</strong></h4><p>Random nonce generation fails under specific, identifiable conditions.</p><p><strong>VM Snapshot/Restore</strong></p><pre>Time 0: VM running, RNG state = X<br>Time 1: Sign message A, nonce from state X<br>Time 2: VM snapshot taken<br>Time 3: Sign message B, nonce from state X&#39;<br>Time 4: VM restored to snapshot<br>Time 5: Sign message C, nonce from state X&#39; ← STATE COLLISION</pre><p>Cloud environments, development workflows, and disaster recovery processes involving VM snapshots introduce RNG state reuse risk.</p><p><strong>Process Fork</strong></p><pre>Parent process: RNG state = X<br>fork()<br>├─ Parent: continues signing with state X<br>└─ Child: continues signing with state X ← STATE COLLISION</pre><p>The first signature in each process after a fork uses the same RNG state. While some OS-level primitives handle this correctly (Linux <strong><em>getrandom</em></strong> uses <strong><em>MADV_WIPEONFORK</em></strong> to invalidate memory pages containing RNG state), many user-space libraries maintain their own buffered state that persists across forks. Rust<strong> <em>thread_rng</em> </strong>handles fork detection correctly.</p><p><strong>Is it a vulnerability or not?</strong></p><p>Random nonce generation in Schnorr signatures is a valid cryptographic design choice when the following conditions are met: cryptographically secure RNG implementation, adequate entropy availability, and no RNG state reuse vectors (VM snapshots, process forks).</p><p>The historical failures in PS3 (constant nonce) and Android (broken PRNG seeding) represent specific implementation defects, not inherent flaws in random nonce generation.</p><p><strong>Security assessment must distinguish between:</strong></p><p>- Implementations that deviate from specification (potential vulnerability)</p><p>- Implementations that match specification with different tradeoffs than alternatives (design decision)</p><p>- Implementations with reduced attack surface (hardening opportunity)</p><p>Pattern recognition from historical incidents informs but does not determine risk. Contextual analysis, examining the RNG implementation, deployment environment, threat model, and specification will always be required for accurate security assessment.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b79d33676c0b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Merkle Patricia Tries Explained: May the Hash Be With You]]></title>
            <link>https://medium.com/@lucasaamorim/merkle-patricia-tries-explained-may-the-hash-be-with-you-c32ba0df96ee?source=rss-ac8de99211f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/c32ba0df96ee</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[merkle-patricia-trie]]></category>
            <dc:creator><![CDATA[Lucas Amorim]]></dc:creator>
            <pubDate>Mon, 03 Mar 2025 19:11:09 GMT</pubDate>
            <atom:updated>2025-03-03T19:11:09.729Z</atom:updated>
            <content:encoded><![CDATA[<p>Today we will demystify one of the most important data structures in Ethereum: the Merkle Patricia Trie (MPT). It might sound like something Yoda would struggle to pronounce, but I promise by the end of this post, you’ll understand why this is the data structure you’ve been looking for.</p><h3>What the Heck is a Merkle Patricia Trie?</h3><p>Think of an MPT as the R2-D2 of data structures — it looks complicated, but it’s incredibly useful and solves multiple problems at once:</p><h3>Why Does Ethereum Care?</h3><p>Ethereum uses MPTs for basically everything important:</p><ul><li>Storing account balances and nonces (State Trie)</li><li>Managing smart contract storage (Storage Trie)</li><li>Keeping track of transactions (Transaction Trie)</li></ul><p>It’s like how the Empire keeps track of rebel bases but with better cryptographic security.</p><h3>The Three Types of Nodes in Our Galaxy</h3><p>Just like how Star Wars has Jedi, Sith, and those confused folks in the middle, our MPT has three types of nodes:</p><h4>1. Leaf Nodes</h4><p>These store actual key-value pairs and don’t care who shot first:</p><pre>// Leaf is a leaf node that contains a key-value pair<br>type Leaf struct {<br>    Key   []byte<br>    Value []byte<br>    hash  []byte<br>}</pre><h4>2. Extension Nodes</h4><p>These wise nodes optimize paths by compressing shared segments:</p><pre>// Extension is an extension node that contains a shared prefix<br>type Extension struct {<br>    SharedPath []byte<br>    Next       Node<br>    hash       []byte<br>}</pre><h4>3. Branch Nodes</h4><p>A collection of all sorts of characters (up to 16 of them), each leading to different paths:</p><pre>// Branch is a branch node with up to 16 children (for hex nibbles)<br>type Branch struct {<br>    Children [16]Node<br>    Value    []byte <br>    hash     []byte<br>}</pre><h3>Let’s Store Some Star Wars Data!</h3><p>Instead of storing boring key-value pairs, let’s use our MPT to store info about Star Wars characters and their home planets:</p><pre>func main() {<br>    // Create a new MPT<br>    mpt := NewMPT()<br>    <br>    // Add Star Wars characters and their home planets<br>    mpt.Put([]byte(&quot;luke&quot;), []byte(&quot;tatooine&quot;))<br>    mpt.Put([]byte(&quot;leia&quot;), []byte(&quot;alderaan&quot;))<br>    mpt.Put([]byte(&quot;lando&quot;), []byte(&quot;cloud city&quot;))<br>    mpt.Put([]byte(&quot;han&quot;), []byte(&quot;corellia&quot;))<br>    <br>    // Get the root hash<br>    rootHash := mpt.RootHash()<br>    fmt.Printf(&quot;Root Hash: %s\n&quot;, hex.EncodeToString(rootHash))<br>    <br>    // Retrieve some values<br>    value, found := mpt.Get([]byte(&quot;luke&quot;))<br>    if found {<br>        fmt.Printf(&quot;Home planet of Luke: %s\n&quot;, string(value))<br>    }<br>    <br>    // Uh oh, the Rebel Alliance has a new member!<br>    mpt.Put([]byte(&quot;rey&quot;), []byte(&quot;jakku&quot;))<br>    newRootHash := mpt.RootHash()<br>    fmt.Printf(&quot;New Root Hash: %s\n&quot;, hex.EncodeToString(newRootHash))<br>}</pre><h3>How It Works: The Force Behind MPT</h3><h3>Encoding Keys</h3><p>Before we insert keys, we convert each byte into two nibbles (4 bits each), like translating Basic to the Aurebesh alphabet:</p><pre>// hexPrefix converts a byte slice to a hex nibble slice<br>func hexPrefix(key []byte) []byte {<br>    result := make([]byte, len(key)*2)<br>    for i, b := range key {<br>        result[i*2] = b &gt;&gt; 4       // High bits, like Jedi training<br>        result[i*2+1] = b &amp; 0x0F   // Low bits, like Sith passion<br>    }<br>    return result<br>}</pre><h3>The Hashing: More Secure Than Imperial Encryption</h3><p>Each node calculates its hash based on its content. It’s like getting a unique Force signature:</p><pre>func (l *Leaf) Hash() []byte {<br>    if l.hash == nil {<br>        h := sha256.New()<br>        h.Write([]byte{byte(LeafNode)})<br>        h.Write(l.Key)<br>        h.Write(l.Value)<br>        l.hash = h.Sum(nil)<br>    }<br>    return l.hash<br>}</pre><p>For branch nodes, we include the hashes of all children:</p><pre>func (b *Branch) Hash() []byte {<br>    if b.hash == nil {<br>        h := sha256.New()<br>        h.Write([]byte{byte(BranchNode)})<br>        <br>        // Hash all children like the Skywalker family tree<br>        for _, child := range b.Children {<br>            if child != nil {<br>                h.Write(child.Hash())<br>            } else {<br>                h.Write([]byte{0}) // Empty like a Stormtrooper&#39;s aim<br>            }<br>        }<br>        <br>        if b.Value != nil {<br>            h.Write(b.Value)<br>        }<br>        <br>        b.hash = h.Sum(nil)<br>    }<br>    return b.hash<br>}</pre><h3>What Our MPT Looks Like: A Galaxy Map</h3><p>After inserting our Star Wars characters, our trie might look something like this:</p><pre>ROOT<br>                         |<br>                      [Branch]<br>                     /   |   \<br>                    h    l    r<br>                   /     |     \<br>                 [Leaf]  |     [Leaf]<br>            &quot;han:corellia&quot; |     &quot;rey:jakku&quot;<br>                           |<br>                        [Branch]<br>                        /     \<br>                       u       e<br>                      /         \<br>                   [Leaf]     [Branch]<br>             &quot;luke:tatooine&quot;   /     \<br>                              i       a<br>                             /         \<br>                          [Leaf]     [Leaf]<br>                   &quot;leia:alderaan&quot;  &quot;lando:cloud city&quot;</pre><p>(This is simplified — the actual trie would have extension nodes to optimize shared paths)</p><h3>The MPT in Action</h3><p>Here’s the coolest part: When we add “rey” to our trie, the root hash changes completely — just like how one new Jedi can change the balance of the Force.</p><p>This is why Ethereum loves MPTs:</p><ol><li>You can efficiently prove that a specific key exists</li><li>You can track changes through different state versions</li><li>You only need to update the path from the changed leaf to the root</li></ol><h3>How Ethereum’s MPT Differs from Ours</h3><p>Our MPT is like the original trilogy — good but simplified. Ethereum’s version is more like the expanded universe with:</p><ol><li><strong>Keccak-256 hashing</strong>: Like Kylo Ren’s lightsaber — basically the same thing but with some modifications</li><li><strong>RLP encoding</strong>: An extra step that serializes nodes before hashing</li><li><strong>Database storage</strong>: Nodes are stored with their hash as the key</li><li><strong>Special encoding for paths</strong>: Extra information to differentiate leaf and extension nodes</li></ol><h3>Wrapping Up: The MPT Strikes Back</h3><p>So there you have it! MPTs might seem as complex as the plot of “The Last Jedi,” but they’re an elegant data structure for a more civilized blockchain.</p><p>Whether you’re building on Ethereum or just curious about how blockchain state works, understanding MPTs will give you a new hope for efficient, verifiable data structures.</p><p>May the source be with you!</p><h3>The Code: A New Hope</h3><p>Here’s the complete Go code for your copy-paste pleasure:</p><pre>package main<br><br>import (<br>	&quot;bytes&quot;<br>	&quot;crypto/sha256&quot;<br>	&quot;encoding/hex&quot;<br>	&quot;fmt&quot;<br>)<br><br>// NodeType represents the type of MPT node<br>type NodeType int<br>const (<br> LeafNode NodeType = iota<br> ExtensionNode<br> BranchNode<br> NilNode<br>)<br>// Node represents a node in the Merkle Patricia Trie<br>type Node interface {<br> Type() NodeType<br> Hash() []byte<br>}<br>// Leaf is a leaf node that contains a key-value pair<br>type Leaf struct {<br> Key   []byte<br> Value []byte<br> hash  []byte<br>}<br>func (l *Leaf) Type() NodeType {<br> return LeafNode<br>}<br>func (l *Leaf) Hash() []byte {<br> if l.hash == nil {<br>  h := sha256.New()<br>  h.Write([]byte{byte(LeafNode)})<br>  h.Write(l.Key)<br>  h.Write(l.Value)<br>  l.hash = h.Sum(nil)<br> }<br> return l.hash<br>}<br>// Extension is an extension node that contains a shared prefix<br>type Extension struct {<br> SharedPath []byte<br> Next       Node<br> hash       []byte<br>}<br>func (e *Extension) Type() NodeType {<br> return ExtensionNode<br>}<br>func (e *Extension) Hash() []byte {<br> if e.hash == nil {<br>  h := sha256.New()<br>  h.Write([]byte{byte(ExtensionNode)})<br>  h.Write(e.SharedPath)<br>  h.Write(e.Next.Hash())<br>  e.hash = h.Sum(nil)<br> }<br> return e.hash<br>}<br>// Branch is a branch node with up to 16 children (for hex nibbles)<br>type Branch struct {<br> Children [16]Node<br> Value    []byte // For the case when a key ends at this node<br> hash     []byte<br>}<br>func (b *Branch) Type() NodeType {<br> return BranchNode<br>}<br>func (b *Branch) Hash() []byte {<br> if b.hash == nil {<br>  h := sha256.New()<br>  h.Write([]byte{byte(BranchNode)})<br>  <br>  // Hash all children<br>  for _, child := range b.Children {<br>   if child != nil {<br>    h.Write(child.Hash())<br>   } else {<br>    h.Write([]byte{0}) // Empty hash for nil child<br>   }<br>  }<br>  <br>  // Hash the value if present<br>  if b.Value != nil {<br>   h.Write(b.Value)<br>  }<br>  <br>  b.hash = h.Sum(nil)<br> }<br> return b.hash<br>}<br>// MerklePatriciaTrie represents a Merkle Patricia Trie<br>type MerklePatriciaTrie struct {<br> root Node<br>}<br>// NewMPT creates a new empty MPT<br>func NewMPT() *MerklePatriciaTrie {<br> return &amp;MerklePatriciaTrie{}<br>}<br>// hexPrefix converts a byte slice to a hex nibble slice<br>func hexPrefix(key []byte) []byte {<br> result := make([]byte, len(key)*2)<br> for i, b := range key {<br>  result[i*2] = b &gt;&gt; 4<br>  result[i*2+1] = b &amp; 0x0F<br> }<br> return result<br>}<br>// Put adds or updates a key-value pair in the trie<br>func (mpt *MerklePatriciaTrie) Put(key, value []byte) {<br> hexKey := hexPrefix(key)<br> mpt.root = mpt.put(mpt.root, hexKey, value)<br>}<br>// Helper function to insert a key-value pair<br>func (mpt *MerklePatriciaTrie) put(node Node, key, value []byte) Node {<br> // If the node is nil, create a leaf node<br> if node == nil {<br>  return &amp;Leaf{Key: key, Value: value}<br> }<br> switch n := node.(type) {<br> case *Leaf:<br>  // If the keys are the same, update the value<br>  if bytes.Equal(n.Key, key) {<br>   return &amp;Leaf{Key: key, Value: value}<br>  }<br>  <br>  // Find the common prefix<br>  prefixLen := 0<br>  for prefixLen &lt; len(n.Key) &amp;&amp; prefixLen &lt; len(key) &amp;&amp; n.Key[prefixLen] == key[prefixLen] {<br>   prefixLen++<br>  }<br>  <br>  // Create a branch node<br>  branch := &amp;Branch{}<br>  <br>  // Insert the existing leaf<br>  if prefixLen &lt; len(n.Key) {<br>   childIndex := n.Key[prefixLen]<br>   if prefixLen+1 &lt; len(n.Key) {<br>    branch.Children[childIndex] = &amp;Leaf{Key: n.Key[prefixLen+1:], Value: n.Value}<br>   } else {<br>    branch.Value = n.Value<br>   }<br>  }<br>  <br>  // Insert the new leaf<br>  if prefixLen &lt; len(key) {<br>   childIndex := key[prefixLen]<br>   if prefixLen+1 &lt; len(key) {<br>    branch.Children[childIndex] = &amp;Leaf{Key: key[prefixLen+1:], Value: value}<br>   } else {<br>    branch.Value = value<br>   }<br>  }<br>  <br>  // If there&#39;s a common prefix, create an extension node<br>  if prefixLen &gt; 0 {<br>   return &amp;Extension{SharedPath: key[:prefixLen], Next: branch}<br>  }<br>  <br>  return branch<br>  <br> case *Extension:<br>  // Find the common prefix with the extension&#39;s shared path<br>  prefixLen := 0<br>  for prefixLen &lt; len(n.SharedPath) &amp;&amp; prefixLen &lt; len(key) &amp;&amp; n.SharedPath[prefixLen] == key[prefixLen] {<br>   prefixLen++<br>  }<br>  <br>  // If the key shares the entire prefix<br>  if prefixLen == len(n.SharedPath) {<br>   // Continue down the trie<br>   n.Next = mpt.put(n.Next, key[prefixLen:], value)<br>   n.hash = nil // Reset hash as the node has changed<br>   return n<br>  }<br>  <br>  // Split the extension node<br>  branch := &amp;Branch{}<br>  <br>  // Insert the existing extension<br>  if prefixLen &lt; len(n.SharedPath) {<br>   childIndex := n.SharedPath[prefixLen]<br>   if prefixLen+1 &lt; len(n.SharedPath) {<br>    branch.Children[childIndex] = &amp;Extension{<br>     SharedPath: n.SharedPath[prefixLen+1:],<br>     Next:       n.Next,<br>    }<br>   } else {<br>    branch.Children[childIndex] = n.Next<br>   }<br>  }<br>  <br>  // Insert the new key<br>  if prefixLen &lt; len(key) {<br>   childIndex := key[prefixLen]<br>   if prefixLen+1 &lt; len(key) {<br>    branch.Children[childIndex] = &amp;Leaf{Key: key[prefixLen+1:], Value: value}<br>   } else {<br>    branch.Value = value<br>   }<br>  }<br>  <br>  // If there&#39;s a common prefix, create a new extension node<br>  if prefixLen &gt; 0 {<br>   return &amp;Extension{SharedPath: key[:prefixLen], Next: branch}<br>  }<br>  <br>  return branch<br>  <br> case *Branch:<br>  // If the key is empty, update the value of the branch<br>  if len(key) == 0 {<br>   n.Value = value<br>   n.hash = nil // Reset hash<br>   return n<br>  }<br>  <br>  // Get the index of the next child<br>  childIndex := key[0]<br>  <br>  // Update the child<br>  n.Children[childIndex] = mpt.put(n.Children[childIndex], key[1:], value)<br>  n.hash = nil // Reset hash<br>  return n<br>  <br> default:<br>  panic(&quot;Unknown node type&quot;)<br> }<br>}<br>// Get retrieves a value from the trie<br>func (mpt *MerklePatriciaTrie) Get(key []byte) ([]byte, bool) {<br> if mpt.root == nil {<br>  return nil, false<br> }<br> <br> hexKey := hexPrefix(key)<br> return mpt.get(mpt.root, hexKey)<br>}<br>// Helper function to retrieve a value<br>func (mpt *MerklePatriciaTrie) get(node Node, key []byte) ([]byte, bool) {<br> switch n := node.(type) {<br> case *Leaf:<br>  if bytes.Equal(n.Key, key) {<br>   return n.Value, true<br>  }<br>  return nil, false<br>  <br> case *Extension:<br>  // Check if the key starts with the shared path<br>  if len(key) &lt; len(n.SharedPath) {<br>   return nil, false<br>  }<br>  <br>  // Check shared prefix<br>  for i := 0; i &lt; len(n.SharedPath); i++ {<br>   if n.SharedPath[i] != key[i] {<br>    return nil, false<br>   }<br>  }<br>  <br>  // Continue down the trie<br>  return mpt.get(n.Next, key[len(n.SharedPath):])<br>  <br> case *Branch:<br>  // If the key is empty, return the value of the branch<br>  if len(key) == 0 {<br>   if n.Value != nil {<br>    return n.Value, true<br>   }<br>   return nil, false<br>  }<br>  <br>  // Get the index of the next child<br>  childIndex := key[0]<br>  <br>  // If the child is nil, the key doesn&#39;t exist<br>  if n.Children[childIndex] == nil {<br>   return nil, false<br>  }<br>  <br>  // Continue down the trie<br>  return mpt.get(n.Children[childIndex], key[1:])<br>  <br> default:<br>  return nil, false<br> }<br>}<br>// RootHash returns the hash of the root node<br>func (mpt *MerklePatriciaTrie) RootHash() []byte {<br> if mpt.root == nil {<br>  // Return a hash of an empty node<br>  h := sha256.New()<br>  h.Write([]byte{byte(NilNode)})<br>  return h.Sum(nil)<br> }<br> return mpt.root.Hash()<br>}<br>func main() {<br> // Create a new MPT<br> mpt := NewMPT()<br> <br> // Add Star Wars characters and their home planets<br> mpt.Put([]byte(&quot;luke&quot;), []byte(&quot;tatooine&quot;))<br> mpt.Put([]byte(&quot;leia&quot;), []byte(&quot;alderaan&quot;))<br> mpt.Put([]byte(&quot;lando&quot;), []byte(&quot;cloud city&quot;))<br> mpt.Put([]byte(&quot;han&quot;), []byte(&quot;corellia&quot;))<br> <br> // Get the root hash<br> rootHash := mpt.RootHash()<br> fmt.Printf(&quot;Root Hash: %s\n&quot;, hex.EncodeToString(rootHash))<br> <br> // Retrieve some values<br> value, found := mpt.Get([]byte(&quot;luke&quot;))<br> if found {<br>  fmt.Printf(&quot;Home planet of Luke: %s\n&quot;, string(value))<br> }<br> <br> // Uh oh, the Rebel Alliance has a new member!<br> mpt.Put([]byte(&quot;rey&quot;), []byte(&quot;jakku&quot;))<br> newRootHash := mpt.RootHash()<br> fmt.Printf(&quot;New Root Hash: %s\n&quot;, hex.EncodeToString(newRootHash))<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c32ba0df96ee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Deep Dive into Polygon (MATIC) Checkpoints]]></title>
            <link>https://medium.com/@lucasaamorim/deep-dive-into-polygon-matic-checkpoints-44e887a9b466?source=rss-ac8de99211f9------2</link>
            <guid isPermaLink="false">https://medium.com/p/44e887a9b466</guid>
            <category><![CDATA[blockchain-security]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[polygon-matic]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Lucas Amorim]]></dc:creator>
            <pubDate>Thu, 09 Jan 2025 00:27:08 GMT</pubDate>
            <atom:updated>2025-01-09T00:27:08.918Z</atom:updated>
            <content:encoded><![CDATA[<p>I’m a seasoned software engineer and security researcher who took the Web3 plunge about two years ago. After spending over a decade breaking and securing traditional systems, I found myself fascinated by the unique security challenges in blockchain technology.</p><p>Recently, I’ve been diving deep into how Polygon (MATIC) handles its bridge security, and I got super curious about its checkpoint mechanism. After spending some time digging through the codebase and testing implementations, I’m here to share everything I learned.</p><h3>What Are Checkpoints Anyway?</h3><p>So here’s the deal — checkpoints are like those save points in your favorite game, but for the blockchain. Every ~30 minutes (~10k blocks), Polygon takes a snapshot of what’s happening on its chain and posts it to Ethereum. Here’s what a checkpoint looks like in code:</p><pre>type Checkpoint struct {<br>    // Start block number of the checkpoint<br>    StartBlock uint64<br>    <br>    // End block number of the checkpoint<br>    EndBlock uint64<br>    <br>    // Root hash of the Merkle tree containing block headers<br>    RootHash common.Hash<br>    <br>    // Bitmap of validators who signed this checkpoint<br>    ValidatorBitmap []byte<br>    <br>    // Aggregated signature of all validators<br>    ValidatorSignatures []byte<br>    <br>    // Timestamp when checkpoint was created<br>    Timestamp uint64<br>}</pre><h3>The Checkpoint Dance: How It Works</h3><p>The whole process is pretty slick. Here’s how it goes down:</p><h3>Step 1: Block Collection</h3><p>Heimdall collects block headers and creates a Merkle tree. Check out this code that creates a Merkle tree from block headers:</p><pre>func BuildCheckpointMerkleTree(blocks []HeaderBlock) (*MerkleTree, error) {<br>    var data [][]byte<br>    <br>    // Prepare block data<br>    for _, block := range blocks {<br>        // Hash block header components<br>        blockData := append(<br>            block.Hash.Bytes(),<br>            block.Number.Bytes()...,<br>        )<br>        blockData = append(blockData, block.StateRoot.Bytes()...)<br>        <br>        data = append(data, blockData)<br>    }<br>    <br>    // Create Merkle tree<br>    return NewMerkleTree(data)<br>}</pre><h3>Step 2: Validator Sign-off</h3><p>Here’s how the broadcast to validators works in code:</p><pre>func (bm *BroadcastManager) BroadcastCheckpoint(ctx context.Context, proposal *CheckpointProposal) (*SignatureCollection, error) {<br>    // Create signature collection channel<br>    sigChan := make(chan *ValidatorSignature, len(bm.validators))<br>    <br>    // Broadcast to all validators<br>    var wg sync.WaitGroup<br>    for _, validator := range bm.validators {<br>        wg.Add(1)<br>        go func(v *ValidatorNode) {<br>            defer wg.Done()<br>            sig, err := bm.sendProposal(ctx, v, proposal)<br>            if err != nil {<br>                return<br>            }<br>            sigChan &lt;- &amp;ValidatorSignature{<br>                ValidatorAddress: v.Address,<br>                Signature:       sig,<br>                Timestamp:       time.Now(),<br>            }<br>        }(validator)<br>    }<br>}</pre><h3>The Merkle Tree Deep Dive 🌳</h3><p>This is where it gets REALLY interesting. The Merkle tree is the secret sauce that makes the whole checkpoint system efficient.</p><h3>What’s a Merkle Tree?</h3><p>Think of it as a pyramid of hashes where:</p><ul><li>Each leaf node is a hash of block data</li><li>Each non-leaf node is a hash of its children</li><li>The root hash represents ALL the data below it</li></ul><p>Here’s the basic structure:</p><pre>               Root Hash<br>              /         \<br>           Hash1       Hash2<br>          /    \      /    \<br>      Hash3  Hash4  Hash5  Hash6<br>      /  \    /  \   /  \   /  \<br>    Blk1 Blk2 Blk3 Blk4 Blk5 Blk6</pre><p>And here’s how it looks in code:</p><pre>type MerkleTree struct {<br>    Root  *Node<br>    Leaves []*Node<br>}<br><br>type Node struct {<br>    Left  *Node<br>    Right *Node<br>    Hash  []byte<br>    Data  []byte<br>}</pre><h3>Building the Tree</h3><p>The construction process is fascinating. Here’s what happens:</p><ol><li><strong>Leaf Creation</strong>: Each block header gets hashed:</li></ol><pre>func hashHeaderBlock(header *HeaderBlock) common.Hash {<br>    return crypto.Keccak256Hash(<br>        header.Hash.Bytes(),<br>        header.Number.Bytes(),<br>        header.StateRoot.Bytes(),<br>        header.ReceiptRoot.Bytes(),<br>        common.BigToHash(big.NewInt(int64(header.Time))).Bytes(),<br>    )<br>}</pre><p><strong>2. Tree Construction</strong>: Pairs of hashes get combined up the tree:</p><pre>for len(nodes) &gt; 1 {<br>    level := make([]*Node, 0, (len(nodes)+1)/2)<br>    for i := 0; i &lt; len(nodes); i += 2 {<br>        // Handle last odd node<br>        if i+1 == len(nodes) {<br>            level = append(level, nodes[i])<br>            break<br>        }<br>        <br>        // Create parent node<br>        hash := sha256.Sum256(append(nodes[i].Hash, nodes[i+1].Hash...))<br>        parent := &amp;Node{<br>            Left:  nodes[i],<br>            Right: nodes[i+1],<br>            Hash:  hash[:],<br>        }<br>        level = append(level, parent)<br>    }<br>    nodes = level<br>}</pre><h3>The Magic of Merkle Proofs</h3><p>This is where it gets interesting. When you want to prove a transaction was included in a checkpoint, you don’t need the whole tree — you just need a path from your transaction to the root.</p><h4>Why This Is Genius</h4><ol><li><strong>Space Efficiency</strong>:<br>- A proof is only log₂(n) size<br>- For 10k blocks, you only need ~14 hashes<br>- That’s like 448 bytes instead of 320,000 bytes!</li><li><strong>Verification Speed</strong>:<br>- O(log n) operations to verify<br>- No need to reconstruct the whole tree<br>- Super gas efficient on Ethereum</li></ol><h3>The Complete Checkpoint Flow</h3><p>Here’s how everything comes together:</p><ol><li><strong>Heimdall Collection Phase</strong>:<br>- Collects 10k block headers<br>- Builds Merkle tree<br>- Calculates root hash</li><li><strong>Validator Signing</strong>:<br>- Broadcasts to validators<br>- Collects 2/3+ signatures<br>- Aggregates signatures</li><li><strong>Ethereum Submission</strong>:<br>- Submits root + signatures<br>- Verifies validator set<br>- Stores checkpoint</li></ol><h3>User Withdrawal Process: A Deep Dive</h3><p>When you want to move your assets from Polygon back to Ethereum, you must go through the “exit process.” Here’s how it works:</p><h3>Step 1: Initiate Withdrawal on Polygon</h3><p>First, you burn your tokens on Polygon:</p><pre>contract PolygonToken {<br>    function withdraw(uint256 amount) external {<br>        require(balance[msg.sender] &gt;= amount, &quot;Insufficient balance&quot;);<br>        <br>        // Burn tokens on Polygon<br>        balance[msg.sender] -= amount;<br>        <br>        // Emit event for proof generation<br>        emit Withdraw(msg.sender, amount, block.number);<br>    }<br>}</pre><h3>Step 2: Wait for Checkpoint</h3><p>You need to wait for:</p><ul><li>At least 30 minutes (checkpoint interval)</li><li>Your transaction block to be included</li><li>Checkpoint to be submitted to Ethereum</li></ul><h3>Step 3: Generate the Proof</h3><p>This is where we use our Merkle tree knowledge:</p><pre>func GenerateExitProof(<br>    exitData *ExitData,<br>    checkpointManager *CheckpointManager,<br>) (*MerkleProof, error) {<br>    // Get the block containing the exit transaction<br>    block := exitData.BlockHeader<br>    <br>    // Get checkpoint containing this block<br>    checkpoint, err := checkpointManager.GetCheckpointContainingBlock(block.Number)<br>    if err != nil {<br>        return nil, err<br>    }<br>    <br>    // Generate Merkle proof<br>    proof, err := checkpoint.Tree.GetProof(exitData.BlockIndex)<br>    if err != nil {<br>        return nil, err<br>    }<br>    <br>    return &amp;MerkleProof{<br>        BlockHeader: block,<br>        Siblings:    proof.Siblings,<br>        Path:        proof.Path,<br>        Index:       exitData.BlockIndex,<br>        RootHash:    checkpoint.RootHash,<br>    }, nil<br>}</pre><h3>Step 4: Submit Proof to Ethereum</h3><p>Finally, you prove your withdrawal on Ethereum:</p><pre>contract RootChainManager {<br>    function exit(<br>        bytes memory exitData,<br>        bytes32[] memory proof,<br>        uint256 blockNumber,<br>        uint256 timestamp<br>    ) external {<br>        // Verify the checkpoint exists<br>        require(<br>            checkpoints[blockNumber].timestamp &gt; 0,<br>            &quot;Checkpoint does not exist&quot;<br>        );<br>        <br>        // Verify the Merkle proof<br>        require(<br>            MerkleProof.verify(<br>                proof,<br>                checkpoints[blockNumber].root,<br>                keccak256(exitData)<br>            ),<br>            &quot;Invalid proof&quot;<br>        );<br>        <br>        // Verify not already exited<br>        bytes32 exitHash = keccak256(exitData);<br>        require(!processedExits[exitHash], &quot;Exit already processed&quot;);<br>        <br>        // Process the exit<br>        processedExits[exitHash] = true;<br>        processExit(exitData);<br>    }<br>}</pre><h3>Important Withdrawal Considerations 🤔</h3><ol><li><strong>Security Timelock<br>- </strong>7-day challenge period<br>- Prevents fraudulent withdrawals<br>- Allows for dispute resolution</li><li><strong>Gas Optimization<br>- </strong>Batch withdrawals when possible<br>- Choose low gas times<br>- Proof submission is gas-intensive</li><li><strong>Common Issues<br>- </strong>Wrong proof generation<br>- Checkpoint not yet submitted<br>- Challenge period not complete<br>- Invalid transaction inclusion proof</li></ol><h3>Why This System is Secure</h3><p>The whole system is secured by:</p><ol><li><strong>Multi-layer Verification<br>- </strong>Validator signatures (2/3+ required)<br>- Merkle proof verification<br>- Challenge period<br>- Transaction inclusion proof</li><li><strong>Economic Security<br>- </strong>Validators have staked MATIC<br>- Malicious behavior = stake slashing<br>- High cost for attacks</li><li><strong>Cryptographic Guarantees<br>- </strong>Merkle tree properties<br>- ECDSA signatures<br>- Hash function security</li></ol><h3>Final Thoughts</h3><p>The checkpoint and proof system in Polygon is a brilliant piece of engineering that:</p><ul><li>Keeps bridge operations secure</li><li>Minimizes gas costs</li><li>Provides strong guarantees</li><li>Scales efficiently</li></ul><p>For developers building on Polygon:</p><ul><li>Always wait for checkpoints</li><li>Verify your proofs</li><li>Handle edge cases</li><li>Monitor gas costs</li></ul><p>Stay safe out there, and happy bridging!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=44e887a9b466" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>