<?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 Kyle on Medium]]></title>
        <description><![CDATA[Stories by Kyle on Medium]]></description>
        <link>https://medium.com/@kyle-crypto?source=rss-106f26f617ea------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*_J5ucpOEk1NVtCEbXq8Dkg@2x.jpeg</url>
            <title>Stories by Kyle on Medium</title>
            <link>https://medium.com/@kyle-crypto?source=rss-106f26f617ea------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 20:25:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kyle-crypto/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[Why Secure Randomness Matters for Blockchain Apps: Tokamak’s Commit-Reveal² Approach]]></title>
            <link>https://medium.com/tokamak-network/distributed-random-beacon-a-trusted-decentralized-randomness-generation-on-blockchains-bbeee97df0f4?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/bbeee97df0f4</guid>
            <category><![CDATA[randomness]]></category>
            <category><![CDATA[research]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Wed, 18 Jun 2025 11:20:28 GMT</pubDate>
            <atom:updated>2025-07-07T06:05:56.952Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kiINhkrm4Oh0bL83Zmp3Iw.png" /></figure><p><strong>Author</strong></p><p>Kyle Huang (ZKP researcher, Tokamak Network); reviewed by <a href="https://medium.com/@suhyeon-tokamak">Suhyeon Lee</a> and <a href="https://medium.com/@praveen.s_52036">Praveen Surendran</a>.</p><p><strong>Introduction</strong></p><p>In the world of Web3 and blockchain, randomness isn’t just a <strong>nice-to-have</strong>; it’s a core requirement. Whether it’s selecting validators in proof-of-stake blockchains, shuffling participants in DAO voting, running fair lotteries, or generating cryptographic proofs, randomness underpins fairness and security across decentralized systems. And it can’t be just any randomness which must be efficient, practicable, unpredictable, bias-resistant, and publicly verifiable, even in adversarial conditions.</p><p>However, generating secure randomness in a decentralized application (dApp) environment is fundamentally challenging. Blockchains are deterministic and fully transparent: every piece of data written to a smart contract is instantly visible to all, including potential attackers. This makes it impossible for smart contracts to safely store or generate secret values on-chain without exposing them to front-running or manipulation. In other words, once a “secret” hits the blockchain, it’s no longer secret. Any naive attempt to embed randomness directly in contract logic invites exploitation.</p><p>Because of this, randomness in dApps must come from external sources or be collaboratively generated through cryptographic protocols that obscure or delay the revelation of sensitive data. This is where <strong>Distributed Randomness Beacons (DRBs) </strong>[3] come in: for those protocols designed to generate random values in a decentralized, verifiable way. Their mission is clear: no single party should control the outcome, yet everyone should be able to verify its integrity.</p><p>Several research efforts have explored both the strengths and limitations of these mechanisms. For instance, “last revealer attacks” [2] is a commonly addressed issue if the DRB solution is constructed using commit-reveal architecture. Commit-reveal is a two-step method where someone first locks in a secret (commit) and then later shows it (reveal) to prove they didn’t change it. It is a commonly utilized cryptographic mechanism to avoid one user deciding its input after seeing others. A broader survey of DRBs, including the trust assumptions and implementation trade-offs, is provided in the comprehensive SoK (Systematization of Knowledge) work by Choi et al. [4]. Other efforts like Spurt aim to achieve transparent setup and scalable performance under practical constraints [5]. Meanwhile, adversarial strategies to optimally manipulate RANDAO mechanisms are also being actively studied [6].</p><figure><img alt="A series of decentralized randomness generation schemes. Photo by pixabay.com." src="https://cdn-images-1.medium.com/max/1024/1*olxDbeFpf5vStZv__s01Ng.jpeg" /><figcaption>A series of decentralized randomness generation schemes. Photo by <a href="https://pixabay.com/photos/table-game-lotto-kegs-the-numbers-4572818/">pixabay.com</a>.</figcaption></figure><h3>Commit-Reveal-Reveal, CR² : DRB solution proposed by Tokamak Network</h3><p>Tokamak Network proposed a solution called CR² [1], which follows the commit-reveal design to optimize the gas consumption and meanwhile reduces the risk of the last revealer attacks.</p><p><strong>Overview of CR²</strong></p><p>The CR² distributed randomness beacon is designed to be compatible with any EVM-compatible blockchain environment, including Ethereum mainnet, sidechains, and Layer-2 rollups. This flexibility allows developers to seamlessly integrate robust, verifiable randomness into a wide range of decentralized applications, regardless of their deployment platform, leveraging existing tooling and infrastructure.</p><p>CR² (Commit-Reveal-Reveal) is a three-phase protocol designed to generate decentralized, tamper-resistant randomness. It improves upon the traditional commit-reveal scheme by introducing a second reveal phase, which establishes a fair, verifiable order in which participants must disclose their secrets.</p><p>A key innovation in CR² is the use of <strong>overlapped commitments</strong>. Each participant first commits to a secret value by submitting two layers of hashes: one for the secret itself, and another for the hash of that commitment. This layered structure prevents anyone from determining their reveal order, while enabling the protocol to derive a <strong>random reveal order</strong> before the secrets are disclosed.</p><p>This added reveal phase ensures that no participant can strategically delay their reveal to influence the final output — a known vulnerability in simpler schemes like RANDAO. By enforcing a randomized reveal order and validating all commitments on-chain or via cryptographic proofs, CR² offers both fairness and resistance against last-revealer attacks.</p><p><strong>Prior Work: 1. Node Staking and Slashing</strong></p><p>Participation in CR² requires nodes to <strong>stake tokens</strong> as collateral. If deployed on an EVM compatible blockchain, the chain’s native token can be used for staking. For example, if the chain is deployed using the Thanos stack (developed and maintained by Tokamak Rollup Hub), Tokamak network TON will be used as the staking token. This staking mechanism ensures:</p><ul><li><strong>Economic Security:</strong> Nodes risk losing staked tokens if they behave dishonestly.</li><li><strong>Network Commitment:</strong> Only nodes with economic interest participate, reducing Sybil attacks.</li><li><strong>Quality Assurance:</strong> Staked value motivates nodes to follow protocol steps correctly.</li></ul><p>Nodes violating protocol rules face <strong>slashing penalties</strong>, where a portion or all of their staked tokens are confiscated. Typical slashing triggers include:</p><ul><li><strong>Failure to Commit:</strong> Not submitting a valid commitment during the commit phase.</li><li><strong>Failure to Reveal:</strong> Missing either of the two required reveals.</li><li><strong>Inconsistent Reveal:</strong> Revealing secrets that do not match previous commitments or conflicting data across reveals.</li></ul><p>Slashed tokens may be burned or redistributed as rewards to honest nodes, incentivizing good behavior.</p><p><strong>Prior Work: 2. Roles in the DRB system.</strong></p><ol><li><strong>On-chain mode</strong> VS <strong>hybrid mode</strong>. There are two modes proposed by Tokamak Network which fit different requirements. In an <strong>on-chain mode</strong>, it is more decentralized but gas-expensive, in which all operations will be between nodes and the smart contract. On the contrary, a hybrid mode outsources many operations like data aggregation, verifications and communication to a leader node to reduce the gas cost, only core operations are requested to the smart contract. In this article, we demonstrate CR² using the <strong>hybrid mode</strong>.</li><li>Leader Node. In the hybrid mode of CR², a leader node is introduced to reduce on-chain communication and computation costs. The process of selecting the leader node can be defined or adapted from existing consensus algorithms. The leader node is the key factor of efficiency improvement in the hybrid model (on-chain and off-chain).</li><li>Participants (regular nodes). Assume there are <em>n</em> nodes are included in one session; the staked nodes are indexed from <em>1</em> to <em>n</em>. It is assumed that each participant has registered by staking sufficient fund to the system; meanwhile, each participant <em>i</em> owns a verified key pair <em>(pkᵢ, skᵢ)</em> which the public key <em>pkᵢ</em> is published to the whole system. We emphasize the leader node is not included as a participant; and the order in this stage is independent from the randomness generation result. While talking about the limit of <em>n</em>, a minimum requirement that <em>n &gt; 1</em>. Theoretically there is no maximum limit; but in practical, it is suggested that <em>n ≤ 32</em> to optimize communicational and computational cost consideration.</li><li>Smart contracts. A fair and public party that keeps immutable proofs and final randomness outputs.</li></ol><figure><img alt="Off-chain Leveraged CR² Protocol." src="https://cdn-images-1.medium.com/max/1024/1*z7aYunTKiWbd1FaYCpzFwg.png" /><figcaption>Off-chain Leveraged CR² Protocol.</figcaption></figure><p><strong>The Commit Phase</strong></p><p>During the <strong>commit phase</strong>, each node <em>i</em>:</p><ol><li>Generates a secret seed <em>sᵢ</em>.</li><li>Computes a cryptographic commitment by hashing the secret: <em>coᵢ = hash(sᵢ)</em>.</li><li>Computes a cryptographic commitment by hashing the commitment: <em>cvᵢ = hash(coᵢ)</em>.</li><li>Sign the commitment <em>σᵢ = sign(skᵢ, cvᵢ)</em>.</li><li>Send <em>cvᵢ</em> and <em>σᵢ</em> to the leader node. If any node <em>i</em> fails to submit its commitment, it will be penalized according to the <strong>Failure to Commit</strong> rules, and the entire session will be considered failed.</li></ol><p>The leader node submits the merkle root <em>Mᵥ = MerkleRoot(cv₁, cv₂, . . . , cvₙ)</em> to the smart contract if all signatures <em>σᵢ</em> are verified valid.</p><p>This step <strong>binds nodes to their secret inputs</strong> without revealing them, preventing manipulation after seeing others’ inputs.</p><p><strong>The First Reveal Phase</strong></p><p>After the commit phase ends, the protocol enters the <strong>first reveal phase</strong>. Each node <em>i</em>:</p><ol><li>All node <em>i r</em>eveals <em>coᵢ</em> to the leader node. If any node <em>i</em> fails to reveal, it will be penalized according to the <strong>Failure to Reveal</strong> rules, and the entire session will be considered failed.</li><li>The leader node verifies that all revealed <em>coᵢ</em> satisfies <em>cvᵢ = hash(coᵢ)</em>. If any revealed <em>coᵢ</em> is invalid, it will be penalized according to the <strong>Inconsistent Reveal</strong> rules, and the entire session will be considered failed.</li><li>Each node computes <em>Ωᵥ = hash(co₁ || co₂ || . . . || coₙ)</em> and determines the <strong>seed order</strong> by the descending order of dᵢ where dᵢ = hash(|Ωᵥ-cvᵢ|). Let <em>sᵈ₁, sᵈ₂, …, sᵈₙ</em> be the <strong>seeds with </strong>descending order<strong>. </strong>E.g, if <em>d₁ = 100</em>, <em>d₂ = 235</em>, <em>d₃ = 97</em>; then the re-ordered seeds will be <em>sᵈ₁ = s₂</em>, <em>sᵈ₂ = s</em>₃ and <em>sᵈ</em>₃<em> = s₁</em>.</li></ol><p>This <strong>seed order</strong> is determined from the distance between <em>Ωᵥ</em> and <em>cvᵢ</em>, whereas <em>Ωᵥ</em> is bound to <em>coᵢ</em>. By the hidden property of commitment, the adversary cannot easily decide its position during the <strong>commit phase</strong>.</p><p><strong>The Second Reveal Phase</strong></p><p>Following the first reveal, a <strong>second reveal phase</strong> takes place for the randomness generation finalization:</p><ol><li>Let <em>sᵈ₁, sᵈ₂, …, sᵈₙ</em> be the <strong>re-ordered seeds </strong>computed in <strong>the first reveal phase.</strong> Seed <em>sᵈ₁</em> will be revealed to the leader node first; and then <em>sᵈ₂, …, sᵈₙ</em> gradually. If any node <em>i</em> fails to reveal, it will be penalized according to the <strong>Failure to Reveal</strong> rules, and the entire session will be considered failed.</li><li>The leader node verifies that the revealed sᵢ satisfies <em>coᵢ = hash(sᵢ)</em>. If any revealed <em>coᵢ</em> is invalid or violates the revealing order, it will be penalized according to the <strong>Inconsistent Reveal</strong> rules, and the entire session will be considered failed.</li><li>After collecting all valid secrets and associated signatures, the leader node sends these reveals and signatures to the smart contract. The<br>contract validates each secret and constructs, and then output the randomness <em>Ωₒ = hash(sᵈ₁ || sᵈ₂ || … || sᵈₙ)</em> if those signatures, seeds and commits are all verified correctly.</li></ol><p>The two reveal phases together <strong>enhance protocol robustness</strong>, making it more resistant to complex cheating strategies, with only tiny overhead. From RANDAO, an additional revealing round reduces the probability of a successful <strong>last revealer attack</strong> by adding a <strong>public verifiable re-ordering</strong> process along the process.</p><h3>Why DRBs Matter for Tokamak TRH Rollup Hub and AppChains?</h3><p>Tokamak Rollup Hub is an on-demand platform for seamless Layer-2 appchain deployment. Integrating Distributed Randomness Beacon (DRB) brings significant value to appchain operators, especially when the DApps running on their chains require secure and reliable randomness. Here’s why:</p><p><strong>Secure, Fair Randomness for AppChains</strong></p><p>App-specific chains like gaming networks or NFT marketplaces often require unbiased and unpredictable randomness for lotteries, in-game events, validator rotation, or NFTs minting. Embedding a DRB ensures that no single node or sequencer can manipulate outcomes, maintaining integrity at scale.</p><p><strong>Lightweight Decentralization</strong></p><p>Unlike massive network-level validators, small L2s benefit from a <strong>minimal, gas-efficient DRB</strong> that fits well into smart contracts. Developers can implement robust randomness without relying on centralized oracles or resource-heavy cryptographic schemes.</p><p><strong>Modular, Plug‑and‑Play Integration</strong></p><p>Tokamak’s Rollup Hub provides a modular SDK for appchain components. A DRB can be an optional “plug-in” easily enabled, audited, and customized per appchain. Whether a chain needs periodic randomness or just occasional draws, the toolkit supports it seamlessly.</p><p><strong>Cost-Effective Trust Model</strong></p><p>DRBs like Commit‑Reveal² enable <strong>on‑chain randomness without requiring trusted third parties</strong>, while keeping operational and gas costs low. This substantially reduces barriers for smaller developers.</p><p>Overall, equipping Rollup Hub-powered appchains with DRB capabilities not only strengthens decentralization and security but also unlocks rich on-chain randomness use cases without adding complexity. It’s a strategic fit for the Tokamak vision of empowering casual, customizable, application-specific L2 ecosystems. The aforementioned work has been implemented in a <a href="https://github.com/tokamak-network/DRB-node">public repository</a> on GitHub, developed by Tokamak Network.</p><p><strong>Acknowledgement</strong></p><p>This article was crafted as part of Tokamak Network’s R&amp;D endeavors. We at Tokamak Network are committed to advancing blockchain technologies to the best of our abilities.</p><p><strong>Reference</strong></p><ol><li>Lee, Suheyon, and Euisin Gee. “Commit-Reveal $^ 2$: Randomized Reveal Order Mitigates Last-Revealer Attacks in Commit-Reveal.” <em>arXiv preprint arXiv:2504.03936</em> (2025). Available: <a href="https://arxiv.org/pdf/2504.03936">https://arxiv.org/pdf/2504.03936</a></li><li>Son, Do Hai, Tran Thi Thuy Quynh, and Le Quang Minh. “RANDAO-based RNG: Last Revealer Attacks in Ethereum 2.0 Randomness and a Potential Solution.” <em>arXiv preprint arXiv:2403.09541</em> (2024). Available: <a href="https://arxiv.org/pdf/2403.09541">https://arxiv.org/pdf/2403.09541</a></li><li>Meng, Xuanji, et al. “Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon.” <em>Cryptology ePrint Archive</em> (2024). Available: <a href="https://eprint.iacr.org/2024/641.pdf#page=1.61">https://eprint.iacr.org/2024/641.pdf#page=1.61</a></li><li>Choi, Kevin, Aathira Manoj, and Joseph Bonneau. “Sok: Distributed randomness beacons.” <em>2023 IEEE Symposium on Security and Privacy (SP)</em>. IEEE, 2023. Available: <a href="https://ieeexplore.ieee.org/iel7/10179215/10179280/10179419.pdf?casa_token=95SS_TgFs7UAAAAA:4_yvv6gW1BBoQjo4XzdeqNytt-gWVjzwRE6lUhvYfJsxYXi3TGxurqg-Hxcfhy4MvNjtEqQpBw">https://arxiv.org/pdf/2205.13333</a></li><li>Das, Sourav, et al. “Spurt: Scalable distributed randomness beacon with transparent setup.” <em>2022 IEEE Symposium on Security and Privacy (SP)</em>. IEEE, 2022. Available: <a href="https://ieeexplore.ieee.org/iel7/9833550/9833558/09833580.pdf?casa_token=csmpGXVU2-EAAAAA%3AQUkjykZhNrh0g9ixeLcuo_skRlFM2Tu97fULBRVt9CReMjv1YcV-cPHxcWnl3ioJFgKaOP4LFw">https://ieeexplore.ieee.org/iel7/9833550/9833558/09833580.pdf?casa_token=csmpGXVU2-EAAAAA:QUkjykZhNrh0g9ixeLcuo_skRlFM2Tu97fULBRVt9CReMjv1YcV-cPHxcWnl3ioJFgKaOP4LFw</a></li><li>Alpturer, Kaya, and S. Matthew Weinberg. “Optimal RANDAO manipulation in Ethereum.” <em>arXiv preprint arXiv:2409.19883</em> (2024). Available: <a href="https://arxiv.org/pdf/2409.19883">https://arxiv.org/pdf/2409.19883</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bbeee97df0f4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tokamak-network/distributed-random-beacon-a-trusted-decentralized-randomness-generation-on-blockchains-bbeee97df0f4">Why Secure Randomness Matters for Blockchain Apps: Tokamak’s Commit-Reveal² Approach</a> was originally published in <a href="https://medium.com/tokamak-network">Tokamak Network</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Zero knowledge proofs]]></title>
            <link>https://kyle-crypto.medium.com/zero-knowledge-proofs-6c06a295f0ea?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c06a295f0ea</guid>
            <category><![CDATA[commitment]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Tue, 29 Oct 2019 03:28:17 GMT</pubDate>
            <atom:updated>2019-10-29T03:28:17.948Z</atom:updated>
            <content:encoded><![CDATA[<p>The zero knowledge proofs, ZKPs, becomes a buzz-word recently due to its magic application: <em>to prove a secret to someone without leaking out the secret</em>?! It sounds a bit abstract, powerful , even contrary. Let’s come up with the following scenarios for better understanding.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jAAhQN5L5a_FZ-iJN1wlUA.png" /><figcaption>The scenarios for zero-knowledge proofs.</figcaption></figure><p>In the upper case, Alice can convince others that she has the knowledge of her password (secret) for the bank account by withdrawing money from the ATM. In the second case, Bob makes retailers convinced he’s older than 20 by showing his driving license while keeping his age secret. Although theoretically these two cases do not satisfy the definition of <em>cryptographic zero-knowledge proof</em>, they are still referable for easily realizing.</p><h4>Definition.</h4><p>Informally, zero knowledge proof is a two-men game that a prover tries to convince a verifier that the prover knows a secret, without leaking any clue of the secret.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nWGowTZEAdYqWtA-LPD2Qw.png" /><figcaption>The syntax of zero-knowledge proofs.</figcaption></figure><h4>Commit phase</h4><p>The syntax of zero-knowledge proofs is shown in above picture. Similar to the <em>commit</em>-<em>open</em>-<em>verify</em> process in the commitment, the zero-knowledge process is <em>commit</em>-(<em>request</em>-<em>challenge</em>-<em>response</em>-<em>verify</em>) <em>* n</em>. It firstly generates a <a href="https://medium.com/@kylehuang_96433/cryptographic-commitments-55ccc4f297c9">cryptographic commitment</a> in the <strong>commit phase</strong>. The <strong>hiding property</strong> of commitments ensure the verifier acquires no information from the commitment; the <strong>binding property</strong> of commitments guarantees that the prover will not change his / her mind after the <strong>commit phase</strong>. Then, the <em>open</em> operation is obviously not the next step since the <em>secret</em> should been kept private in the zero-knowledge proofs.</p><h4>Challenge phase</h4><p>Rather than opening the commit, the <strong>challenge phase</strong> works as follows: the prover sends a request to the verifier on demand and the verifier can challenge depending on the commitment and the request. On receiving a challenge <em>chg</em>, the prover replies a corresponding response <em>res</em> and the verifier can verify the validity through <em>verify</em>(<em>com</em>, <em>req</em>, <em>chg</em>, <em>res</em>). After many times of the challenge series <em>request</em>-<em>challenge</em>-<em>response</em>-<em>verify</em>, the verifier believes the fact that the prover owns the <em>secret</em> if the prover always passes the verifications.</p><h3>Properties</h3><p>In principle, a proof process is called zero-knowledge proof if all these three properties hold.</p><h4>Completeness</h4><p>The honest prover always convinces the verifier.</p><h4>Soundness</h4><p>The dishonest prover fails in overwhelming probability.</p><h4>Zero-knowledge</h4><p>The verifier acquires nothing but the fact the prover knows the <em>secret</em>.</p><p>The <strong>correctness</strong> is usually intuitive; while the <strong>zero-knowledge</strong> property is a bit too sophisticated to be described. Hence, let’s dive a bit deeper to the <strong>soundness</strong> of those ZKP protocols.</p><h4>Proofs or arguments</h4><pre> - <strong>Zero-knowledge proof</strong>:if the <strong>soundness</strong> hold and<strong> </strong>the prover has <strong>unbounded</strong> computational ability.<br><strong> </strong>- <strong>Zero-knowledge argument</strong>: if the <strong>soundness</strong> hold and<strong> </strong>the prover has only <strong>bounded</strong> computational power.</pre><h4>The false-positive probabilities</h4><p>In some special cases, a dishonest prover who does not own the secret may probabilistically pass the verification. To discuss about this, some knowledge of the challenge phase has to be clarified.</p><h3>The challenge</h3><p>The challenge is issued by the verifier to ensure the prover knows the secret, such as a random examination. However, if the challenge is predictable for the prover, it is not hard for the prover to fake a valid pair of (<em>request</em>,<em> response</em>) that pass the verification without knowing the secret.</p><pre>For a commitment <em>com</em> = <em>Commit</em>(<em>secret</em>) where the <em>secret is unknown to </em>the prover<em>,</em> if the prover can predict the challenge <em>chg</em> of the verifier, it is easy to find a pair (<em>req</em>, <em>res)</em> = <em>fake</em>(<em>com</em>, <em>chg</em>) that <em>verify</em>(<em>com</em>, <em>req</em>, <em>chg</em>, <em>res</em>} = <em>True</em>.</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2XaFdyH1hB7lhTVJrrwwbg.png" /><figcaption>A fake proof that passes even not knowing secret x.</figcaption></figure><h4>The dishonest prover may guess the challenge</h4><p>This condition happens probabilistically depends on the domain size of <em>chg</em>. In short, the prover may guess the challenge. Take the Fiat-Shamir ZKP for example, which is designed to proof the knowledge of a square root of a commitment <em>com</em>, the dishonest who doesn’t knows the secret <em>x</em> can still pass the verification if he / she successfully guesses the challenge <em>chg</em>. Here <em>n</em> is a public parameter, and the square root of values in the <em>mod n</em> environment is difficult due to some mathematic issues.</p><h4>Why should the challenge be executed many times?</h4><p>It is trivially observed that the domain size of challenges is too small to guarantee the fact that the prover is honest. In above Fiat-Shamir case, each time the prover pass the the verification, there is only half probability that he / she really knows the secret <em>x</em>. Thus, many interactions are executed to avoid the probabilistically guessing. For instance, if the prover successfully passes the verification for 128 times and none of them fails; then, the verifier may be convinced because 2^(-128) is negligible.</p><h4>The order of request, challenge and response</h4><p>Definitely, aforementioned Fiat-Shamir square root ZKP is a special case whose challenge space is quite small so that malicious prover might success. Assume the challenge space is big, there is another factor that matters: the order. We could easily observe that</p><pre>The <strong>honest</strong> prover generates a request, receives a challenge and returns a response (<em>req</em> - <em>chg</em> - <em>res</em>).<br>The <strong>dishonest </strong>prover predicts a challenge, generates the response and finally computes the request (<em>chg</em> - <em>res</em> - <em>req</em>).</pre><p>An intuitive solution is to import some one-way functions to guarantee the orders. For example, the Fiat-Shamir transfer adopted the hash functions as the one-way functions which makes order as wish. The detail description will be discuss in the next phase.</p><h3>Interactions</h3><p>It is obvious that the proof needs many times of interactions between the prover and the verifier; however, the interaction on one hand costs much computational and communicational resources; and on the other hand may not be applicable if the prover and the verifier are not online at the same time. So, users may think about one problem that may we deal with the challenges and those interactions in a non-interactive manner? The answer is <em>YES.</em></p><h4>ZKP vs NIZK</h4><p>We already know the zero-knowledge proofs (ZKP). The non-interactive zero-knowledge proofs (NIZK) is also a ZKP which adopts cryptographic transfers that makes challenges non-interactive. As aforementioned, the challenges should be unpredictable and the order (<em>req - chg -</em> <em>res</em>) does matter. For those ZKP algorithms whose challenge space are big, a famous Fiat-Shamir transfer that adopts hash functions as the challenge generator makes NIZK possible.</p><pre><strong>ZKP</strong>: (1) the prover generates a request <em>req</em>, (2) the verifier chooses a challenge <em>chg</em>, (3) the prover replies a response <em>res = response(secret, req, chg)</em>.<br><strong>NIZK</strong>: (1) the prover generates a request <em>req</em>, computes the challenge <em>chg</em> = hash(com, req) and the response <em>res = response(secret, req, chg)</em></pre><p>The first difference is the challenge is computed by the hash function rather than randomly chosen by the verifier; and the second difference is it is only executed <strong>once</strong>. Then, how does the properties satisfied in this transfer?</p><h4>Unpredictable</h4><p>In the random oracle model, the hash value acts like a random number since it is <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236">uniformly-distributed</a>.</p><h4>Correct order</h4><p>The <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236">one-wayness</a> of hash function ensures that the challenge is generated after both the commitment and the request are chosen and inputted. The (<em>chg - res -</em> <em>req</em>) cheating will definitely not work.</p><p>The verification of NIZK is simply modified as follow:</p><pre><em>verify_NIZK</em>(<em>com</em>, <em>req</em>, <em>chg</em>, <em>res</em>):<br>  return (<em>chg</em> == <em>hash</em>(<em>com</em>, <em>req</em>) &amp;&amp; verify_ZKP(<em>com</em>, <em>req</em>, <em>chg</em>, <em>res</em>))</pre><p>Due to the non-interactive requirement and the cryptographic properties of hash functions, the challenge phase is executed only <strong>once</strong> in NIZK protocols, which the strength equals to the ZKP protocols based on the assumption of the common reference string (CRS) model and the random oracle (RO) model. At the end of this story, we ignore these theoretical models for better concentrating on the zero-knowledge proofs.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c06a295f0ea" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cryptographic commitments]]></title>
            <link>https://kyle-crypto.medium.com/cryptographic-commitments-55ccc4f297c9?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/55ccc4f297c9</guid>
            <category><![CDATA[commitment]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[hash-function]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[multi-party-computation]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Mon, 07 Oct 2019 07:53:04 GMT</pubDate>
            <atom:updated>2025-02-10T12:19:26.195Z</atom:updated>
            <content:encoded><![CDATA[<p>The commitment is a useful tool in cryptography that is often utilized with the zero-knowledge proof. In principle, the commitment is designed to ensure some values are selected in the correct manner. The description is subtle so let’s consider a concrete case: a ‘<em>Rock Paper Scissor</em>’ game.</p><p>Let Alice and Bob be the players of the ‘<em>Rock Paper Scissor</em>’ game. Imagine the scenario that they’re playing this game through internet, <em>how could they play this game fairly without a trusted third party</em>? The term <strong>fair</strong> denotes no one decides his / her choice after acquiring the other’s choice. Ideally, if they can express their choices together, it may be a fair game. As we all know, the synchronization in the network is a tough issue which is quite impractical.</p><p>Then, how to design the protocol? For data hiding, the <a href="https://medium.com/@kylehuang_96433/symmetric-asymmetric-encryption-5d8d4f6d80f1">symmetric / asymmetric encryption</a> schemes may be an intuitive cryptographic tool; for the <a href="https://medium.com/@kylehuang_96433/digital-signature-c601da3c0c02">non-repudiation</a>, the digital signature may be required. And these two tools may in advance need the certifications from a trusted third party like key distribution center (KDC).</p><p>In this post, we’re introducing another powerful cryptographic tool to solve this problem, the cryptographic commitment. There are two phases in the commitment protocol, the commit phase and the open phase. In the commit phase, a prover makes a commit <em>com</em> to hide his / her <em>secret</em> along with a random number <em>r</em>; after some confirmations, the prover opens both the secret and the random number to a verifier; finally, the verifier can verify the validity of the set {<em>commit</em>, <em>secret</em>, <em>r</em>}.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fvT1jMdS8qu_whlddaUgBA.png" /><figcaption>The cryptographic commitments.</figcaption></figure><p>Shown as above there are three algorithms in the commitment framework where the open algorithm just reveals <em>secret</em> and <em>r</em> without any computation. The commitment does not rely on the symmetric / asymmetric keys so there is also no corresponding key management issues like key distribution or KDC. With the commitment, two properties will be guaranteed with cryptography:</p><h4>Hiding</h4><p>In the commit phase, the verifier acquires no information about <em>secret</em> and <em>r</em> from the commit <em>com</em>.</p><h4>Binding</h4><p>The prover is not able to open {secret’, r’} !={secret, r} which makes <em>verify</em>(<em>com</em>, <em>secret’</em>, <em>r’</em>) = <em>True.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*FFI2LjsPLv9oyY0K4C41UA.jpeg" /><figcaption>The ‘Rock Paper Scissor’ application based on cryptographic commitments.</figcaption></figure><p>Take the aforementioned ‘<em>Rock Paper Scissor</em>’ game for example, we’ll realize the commitment much better. Assume secretA, secretB belong to {‘<em>Rock’, ‘Paper’, ‘Scissor</em>’} and they denote the choices for Alice and Bob respectively,</p><p>First, Alice and Bob exchange their commits in the commit phase as depicted in above picture. By the <strong>hiding property</strong> of the commitment, no value will be leaked in the commit phase so that both of them cannot cheat.</p><p>Then, after they confirm they’ve received the commitment from the other one, it comes to the open phase. Two players reveal their <em>secret</em> and <em>r</em> to the other so that the commit could be verified. By the <strong>binding property</strong> of the commitment, the prover is not able to change his / her mind after giving a commit; that is, it is cryptographically guaranteed the ‘<em>opened secret</em>’ is the same as the ‘<em>committed secret</em>’. The commitment thus guarantees a fair game between two parties.</p><h3>Concrete constructions</h3><p>So far, maybe the commitment sounds magic but it is actually not very difficult to be implemented. There are several famous implementations such as hash-based commitment, ElGamal commitment and Pederson commitment. Following, we take advantage of the <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236">properties of hash functions</a> to construct a straightforward commitment.</p><h4><em>com = Commit</em>(secret, r)</h4><pre><em>r</em> = <em>random(512)</em> // a 512 bits random number to guarantee the entropy<br><em>com</em> = <em>hash</em>(<em>secret</em>, <em>r</em>)<br>return com</pre><p>The <strong>one-wayness</strong> of the hash function directly guarantees the <strong>hiding property </strong>of the commitment.</p><h4>T / F = Verify(com, secret, r)</h4><pre>return (com == hash(secret, r))</pre><p>The <strong>collision-resistant property</strong> of the hash function inherently leads to the <strong>binding property</strong> of the commitment.</p><p>So far, a basic knowledge of cryptographic commitment has been introduced. In the following story of zero-knowledge proof, there will be some advanced commitment schemes introduced.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=55ccc4f297c9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A simplified PoC for Bitcoin]]></title>
            <link>https://kyle-crypto.medium.com/a-simplified-poc-for-bitcoin-8bb2db549c32?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/8bb2db549c32</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[poc]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Thu, 22 Aug 2019 16:04:11 GMT</pubDate>
            <atom:updated>2019-12-25T09:15:38.819Z</atom:updated>
            <content:encoded><![CDATA[<p>The Bitcoin has been fascinating for several years, which also triggered the arise of the whole blockchain industry. However, the Bitcoin is somehow too complex to be clearly recognized as a promising technique composed of cryptography, distributed systems and FinTech. This article aims to simplify some detail settings and introduce the proof of concept of Bitcoin through JavaScript. Also, this story could be regarded as an extension of <a href="http://twitter.com/spenserhuang">@spenserhuang</a>‘s article <a href="https://medium.com/@spenserhuang/learn-build-a-javascript-blockchain-part-1-ca61c285821ea">Learn &amp; Build a Javascript Blockchain</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XpLhUqrK7PiR6Fq7Z4NPSg.png" /></figure><h4>Background requirements</h4><p>Audiences of this story are expected to keep an open mind and acknowledge some basic JavaScript programming skills. First, the cryptographic part mainly requires <a href="https://medium.com/@kylehuang_96433/digital-signature-c601da3c0c02">digital signature</a> and <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236">hash function</a>, some previous stories might provide some conceptually understanding. Secondly, the consensus algorithm, proof of work, will be implemented in the application as the distributed system part. Finally, a basic object-oriented programing concept is required before starting this story.</p><h4>Conceptually introduction</h4><p>Fundamentally, we are writing a blockchain which is a “chain-of-blocks”, and each block contains many “transactions”; aside from that, there are many “users” who own private keys so that they can transfer and mine. The overview gives us a concept to write some “objects” over a top-down viewpoint. Each object mentioned above is described as a class in the programming language.</p><h3>Begin to construct</h3><h4>NPM and Git</h4><p>Let’s start with the npm tool. If npm has not been installed, refer to this <a href="https://www.npmjs.com/get-npm">site</a>. My developing version is 6.11.1, perhaps you might need a close version. The following command may help to check the version of npm.</p><pre>npm -v</pre><p>Then, git is also an import tool before the construction, find some instruction <a href="https://git-scm.com/book/en/v2/Getting-Started-Installing-Git">here</a> if git is still unavailable on your computer.</p><h4>Start the PoC for Bitcoin</h4><p>I prepared a project composed of some JavaScript code to gradually implement a PoC for Bitcoin. First, go to the file path you like, clone the repository BitcoinPoC and enter the folder after download.</p><pre>cd your/path<br>git clone <a href="https://github.com/Kylesstory/BitcoinPoC.git">https://github.com/Kylesstory/BitcoinPoC.git</a><br>cd ./BitcoinPoC/</pre><p>Then, some existing library may help us a lot while dealing with hash functions and the ECDSA digital signature. These libraries have been utilized in the sample codes. So, let’s install them first.</p><pre>npm install</pre><p>Ideally, the required libraries will be automatically installed if you’re lucky. Have a look what we just installed:</p><pre>npm list</pre><p>A similar result might look like this:</p><pre>npm list</pre><pre>bitcoinpoc@1.0.0 your/path/BitcoinPoC<br>├── crypto@1.0.1</pre><pre>├── crypto-js@3.1.9-1</pre><pre>├─┬ elliptic@6.5.0</pre><pre>│ ├── bn.js@4.11.8</pre><pre>│ ├── brorand@1.1.0</pre><pre>│ ├─┬ hash.js@1.1.7</pre><pre>│ │ ├── inherits@2.0.4 </pre><pre>│ │ └── minimalistic-assert@1.0.1 </pre><pre>│ ├─┬ hmac-drbg@1.0.1</pre><pre>│ │ ├── hash.js@1.1.7 </pre><pre>│ │ ├── minimalistic-assert@1.0.1 </pre><pre>│ │ └── minimalistic-crypto-utils@1.0.1 </pre><pre>│ ├── inherits@2.0.4</pre><pre>│ ├── minimalistic-assert@1.0.1</pre><pre>│ └── minimalistic-crypto-utils@1.0.1</pre><pre>└── hex-to-binary@1.0.1</pre><p>Assume you’re a lucky guy, now we can forget the npm and git things; then look forward to focus on implementing a simplified Bitcoin blockchain. Let’s open file PoCBitcoin.js in your preferred text editor like Sublime or VSCode, it may look like this.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0a52daef6406ebcdee8cd3a600f42f09/href">https://medium.com/media/0a52daef6406ebcdee8cd3a600f42f09/href</a></iframe><p>As previously mentioned, the code has been almost completed. The first 5 lines are imported libraries; line 12 to 21 are some global variables; line 23 to 111 are some general functions which could help some repetitive works. The program begins from line 296. We’ll focus on the <strong>classes</strong> from line 115 to line 294, the objects <em>User</em>, <em>Transaction</em>, <em>Block</em> and <em>Blockchain</em> we mentioned in the beginning. All blanks need to be filled will be labeled by <strong>[ write code here ]</strong>.</p><h4>User (part 1)</h4><p>Let’s begin from the <em>User</em> class. In Bitcoin, a user owns a pair of private key and public key along with the mnemonic and an address.</p><p>The private / public key pair makes the user unique because he or she can sign digital signatures that cannot be forged by others who does not own the private key. That makes users distinguishable and not replaceable (and also the immutable of the signed content). That’s also why each user should keep their private key secretly.</p><p>The mnemonic could be realized as the copy of secret key encoded into a human-readable format like 12 or 24 English words. It is not implemented here for clear.</p><p>The public key represents for a user. However the public key is too long as an identifier so that the addresses are proposed to replace the public keys. Conceptually, the address is the hash value of the public key. By the <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236"><em>collision-resistant</em></a> property of hash functions, different public keys become different addresses in an overwhelming probability so the addresses could still be identifiers of users. The detail implementation could be found <a href="https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses">here</a>, which is composed of a series of hash functions (SHA256 and RIPEMD-160), checksum and <a href="https://en.wikipedia.org/wiki/Base58">Base58 encoding</a>. For clear expression, we just simplified addresses as the “shortHash” of the public key, which “shortHash” is a pre-defined SHA256 based hash function in this program.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f463551e64dc16e8066faf73c51dcb41/href">https://medium.com/media/f463551e64dc16e8066faf73c51dcb41/href</a></iframe><p>The <em>constructor()</em> means it create a User object without any parameter. At first, we need a pair of private/public key pair. This could be achieved with the aid of library <em>ec</em>.</p><pre>constructor(){ // to create a new user with name, secret key, public key, address and balance<br>  // 1. create public key and secret key<br>  this.key = ec.genKeyPair();<br>  // Note. In Bitcoin and Etherum, there are mechanisms to avoid secret key losing.<br>  // In Bitcoin improvement proposal 39, their is a technique called mnemonic which<br>  // encodes the secret key into English words, users can write it down as the cold storage of secret key.<br>  // Still that sentence, we omit it for clear.<br> }</pre><p>Then, we need to add a line to compute users’ addresses. Although the address is conceptually the hash value of public key, it is somewhat complete to implement so that we just “shortHash” the public key as the address.</p><pre>constructor(){ // to create a new user with name, secret key, public key, address and balance<br>  // 1. create public key and secret key<br>  this.key = ec.genKeyPair();<br>  // Note. In Bitcoin and Etherum, there are mechanisms to avoid secret key losing.<br>  // In Bitcoin improvement proposal 39, their is a technique called mnemonic which<br>  // encodes the secret key into English words, users can write it down as the cold storage of secret key.<br>  // Still that sentence, we omit it for clear.<br>  <br>  // 2. compute the address<br>  const publicKey = this.key.getPublic();<br>  // Warn! This is a simplified version of address, not the official one.<br>  this.address = shortHash(publicKey.getX().toString(&#39;hex&#39;) + publicKey.getY().toString(&#39;hex&#39;));<br> }</pre><p>Third, register the address to a global user list so that the created user could be found by enter “<em>users[address]”</em>.</p><pre>constructor(){ // to create a new user with name, secret key, public key, address and balance<br>  // 1. create public key and secret key<br>  this.key = ec.genKeyPair();<br>  // Note. In Bitcoin and Etherum, there are mechanisms to avoid secret key losing.<br>  // In Bitcoin improvement proposal 39, their is a technique called mnemonic which<br>  // encodes the secret key into English words, users can write it down as the cold storage of secret key.<br>  // Still that sentence, we omit it for clear.<br>  <br>  // 2. compute the address<br>  const publicKey = this.key.getPublic();<br>  // Warn! This is a simplified version of address, not the official one.<br>  this.address = shortHash(publicKey.getX().toString(&#39;hex&#39;) + publicKey.getY().toString(&#39;hex&#39;));<br>  // 3. register the address to the blockchain<br>  users[this.address] = this;<br>  addresses.push(this.address);<br> }</pre><p>Following, let’s glimpse the <em>Transaction</em> class.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4ef2029e12ba6188b0e4c92e6619c2b8/href">https://medium.com/media/4ef2029e12ba6188b0e4c92e6619c2b8/href</a></iframe><p>For short, transaction is sometimes abbreviated as tx. Then, while looking at the constructor of transaction, there are 4 parameters: <em>from</em>, <em>to</em>, <em>amount</em>, and <em>tip</em>. The former two are addresses, and the later two are numbers. It is intuitive that a transaction is sent by <em>user[from]</em>, sent to <em>user[to]</em>, with <em>amount</em> and <em>tip</em>.</p><p>Imagine the scenario you have a dinner in the restaurant in US, you’ll pay the price (amount) to the restaurant for food as well as the tip to the waiters for service. Bitcoin employees the similar concept: while a user transfers a specific amount of Bitcoin to another user, a small piece of tip is required as the service fee for the transaction verifier who participants in mining and maintaining the robust of the blockchain. The transaction sender decides how much the tip is and then he/ she signs the transaction using his / her private key to authorize the transaction.</p><p>Let’s come back to the <em>User</em> class concerning on the <em>transfer</em> function. Three parameters <em>to</em>, <em>amount</em> and <em>tip</em> will be passed in to construct a transaction. We have several things to fulfill in the function entity. First, the balance is verified first to ensure the transfer may success.</p><pre>transfer(to, amount, tip){ // to transfer money to someone<br>  // 1. make sure users&#39; balance if enough to transfer<br>  if (users[this.address].balance &gt;= (amount + tip)){<br>   <br>  } else{<br>   console.log(&#39;Insufficient balance.&#39;)<br>  }<br> }</pre><p>Second, if sufficient fund is checked, create a transaction with the parameters and it’s own address.</p><pre>transfer(to, amount, tip){ // to transfer money to someone<br>  // 1. make sure users&#39; balance if enough to transfer<br>  if (users[this.address].balance &gt;= (amount + tip)){<br>   // 2. create a transaction<br>   const tx = new Transaction(this.address, to, amount, tip);<br>   const txString = tx.toString();</pre><pre>  } else{<br>   console.log(&#39;Insufficient balance.&#39;)<br>  }<br> }</pre><p>Third, the sender signs the transaction using its private key.</p><pre>transfer(to, amount, tip){ // to transfer money to someone<br>  // 1. make sure users&#39; balance if enough to transfer<br>  if (users[this.address].balance &gt;= (amount + tip)){<br>   // 2. create a transaction<br>   const tx = new Transaction(this.address, to, amount, tip);<br>   const txString = tx.toString();<br>   // 3. sign the transaction<br>   tx.signature = this.key.sign(txString);<br>   <br>  } else{<br>   console.log(&#39;Insufficient balance.&#39;)<br>  }<br> }</pre><p>Forth, publish the transaction to the blockchain (<em>unpackagedTxs</em> in this program).</p><pre>transfer(to, amount, tip){ // to transfer money to someone<br>  // 1. make sure users&#39; balance if enough to transfer<br>  if (users[this.address].balance &gt;= (amount + tip)){<br>   // 2. create a transaction<br>   const tx = new Transaction(this.address, to, amount, tip);<br>   const txString = tx.toString();<br>   // 3. sign the transaction<br>   tx.signature = this.key.sign(txString);<br>   // 4. save the created transaction to &#39;unpackagedTxs&#39;<br>   unpackagedTxs.push(tx);<br>   <br>  } else{<br>   console.log(&#39;Insufficient balance.&#39;)<br>  }<br> }</pre><p>Now, we’ve finished the phased task. We built the <em>User</em> object, who has a pair of signing keys and an address as the identifier; besides, the user can transfer to someone through proposing transactions. Following, let’s temporarily leave the function <em>mine()</em> behind and take a look over the transaction class.</p><h4>Transaction</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3e93b6fa1114749d7d7632c3cfb7d999/href">https://medium.com/media/3e93b6fa1114749d7d7632c3cfb7d999/href</a></iframe><p>What we need to do in this class is a bit easier. Just make the transaction verifiable afterward. Two things have to be done: make sure the transaction is signed, and it is signed correctly.</p><pre>verify(){<br>  // To make sure the transaction is valid.<br>        <br>  // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>  if (this.signature === &#39;&#39;) {<br>   return false;<br>  } else{<br>   <br>  }<br> }</pre><p>The commands above ensures the signature of this transaction is fulfilled; and the commands below verifies the digital signature of the sender.</p><pre>verify(){<br>  // To make sure the transaction is valid.<br>        <br>  // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>  if (this.signature === &#39;&#39;) {<br>   return false;<br>  } else{<br>   // 2. Verify the validation of the digital signature.<br>   const user = users[this.from];<br>   return user.key.verify(this.toString(), this.signature);<br>  }<br> }</pre><p>It is really a piece of cake, right? Take a break, have your coffee ready and we’re moving forward to the <em>Block</em> class.</p><h4>Block</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2d7ce6cb98891242c2d7fdf243514765/href">https://medium.com/media/2d7ce6cb98891242c2d7fdf243514765/href</a></iframe><p>Block is a bit more complex because it is the basic unit of blockchain. It works like a box concealing some data inside and attaches some meta-data outside, such as a HTTP package.</p><p>The concealing data is obviously the transaction data. In the official Bitcoin setting, the block size is set to 1MB which may contains dynamically hundreds of transactions depending on their size. To help understanding, it is set that each block may contains three transactions in this PoC. By the way, the merkle tree data structure is employed to make a proof of hierarchical hash footprint for transaction data. It sounds difficult so that it is also omitted here.</p><p>The metadata includes the <em>timestamp</em>, <em>previousHash</em>, <em>nonce</em>, and <em>signature</em>.</p><ol><li>The <em>timestamp</em> is straightforward.</li><li>The <em>previousHash</em> plays a <strong>vital</strong> role in the blockchain. By the <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236"><em>collision-resistant</em></a> property of hash functions, the <em>previousHash</em> may stand for the previous block. Block <em>n</em> hasn’t been modified if the <em>previousHash n</em> kept in block <em>n+1</em> is correct, and <em>previousHash n-1</em> kept in block <em>n</em> ensures the correctness of block <em>n-1</em>. Recursively, the hash value of a previous block is stored in the current block. It repeatedly ensures the accuracy of the previous blocks, which finally constructs an immutable blockchain system. The is the main idea about how immutable the blockchain is.</li><li>The nonce variable is the key factor of the famous consensus protocol, proof of work. By the <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236">uniform distribution property</a> of hash functions, the outputs of hash functions are unpredictable unless you practically compute it. It creates an interesting and perhaps fair situation for each participant to compete calculating a ”target range” of hash values. More precisely, the <em>transaction data</em>, <em>timestamp</em>, and <em>previousHash</em> are fixed input fields, and miners are expected find an input nonce together with three aforementioned input fields to compute a great hash output which belongs to the desired range. I know the description is still a mist, sorry. For example, the hash value output locates uniformly random from 0 to 255 ; and the “target range” is “less than 32”. With the fixed <em>transaction data</em>, <em>timestamp</em>, and <em>previousHash</em> input, the miner keeps trying different <em>nonces</em> until <em>hash(transaction data</em>, <em>timestamp</em>, <em>previousHash, nonce) = x</em> and <em>x &lt; 32</em>. Hope that the example may help understanding. The “<em>nonce</em>-finding” process is called as mining, or solve a puzzle. Actually it is not an easy job, and the first one who solves a puzzle will acquire a great amount of award. The mining award is initially 50 Bitcoins per block, but it reduces to half every four years. It is worthy to be noted that the “<em>target</em> range” is not fixed in Bitcoin; it dynamically arises or reduces to keep the average mining time is about 10 mins / block. For simplicity, this PoC project keeps it statistic at 3.</li><li>After packaging <em>transactions</em>, collecting a <em>timestamp</em> and the <em>previousHash</em>, and mining a suitable <em>nonce</em>, the block verifier signs the block using her / his private key as the proof of work evidence (to claim the mining reward afterward).</li></ol><p>Now, are you still awake? If so, let’s run into the code implementation. The puzzle is implemented by the cooperation of the <em>User</em> object and the <em>Block</em> object. Conceptually, the user mines with function <em>mine()</em>, and the block returns the validity through function <em>challenge()</em>.</p><pre>challenge(){ // if the hash value begins with three (defined by variable &#39;blockchain.difficulty&#39;) 0s<br>        const binary = hexToBinary(this.hash);<br>        // [ Write code here ]</pre><pre>        // To ensure the found &#39;nonce&#39; satisfy the puzzle challenge <br>        // of Bitcoin proof of work with &#39;difficulty&#39;.<br>    }</pre><p>The variable <em>difficulty</em> defines the number of a consecutive 0s at the most significant bits. For example, let <em>difficulty=3</em>, it means the block is valid if the block verifier finds a nonce so that the hash output of the block begins with at least three 0s. Try the following solution or you can write in your designing.</p><pre>challenge(){ // if the hash value begins with three (defined by variable &#39;blockchain.difficulty&#39;) 0s<br>  const binary = hexToBinary(this.hash);<br>  let x = 0;<br>  for (let i = 0; i &lt; binary; i++){<br>   if (binary[i] === &#39;0&#39;){<br>    x += 1;<br>   } else{<br>    return false;<br>   }<br>   if (x &gt;= blockchain.difficulty){<br>    return true;<br>   }<br>  }<br>  return false;<br> }</pre><p>After the <em>challenge()</em> function, the block has to be verified valid so that the function <em>verify()</em> is also required. Four checks have to been implemented in this code section.</p><pre>verify(){ // to verify a single block<br>     if (this.signature === &#39;&#39;){ <br>     // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>      return false<br>     }<br>     <br>    }</pre><ol><li>The signature of this block has been generated.</li></ol><pre>verify(){ // to verify a single block<br>     if (this.signature === &#39;&#39;){ <br>     // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>      return false<br>     }<br>     if (this.hash !== shortHash(this.toString())){ <br>     // 2. Ensure &#39;this.hash&#39; has been correctly computed. <br>        //    This step makes sure the block data hasn&#39;t been modified.<br>      return false<br>     }<br>     <br>    }</pre><p>2. The hash property is correctly computed.</p><pre>verify(){ // to verify a single block<br>     if (this.signature === &#39;&#39;){ <br>     // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>      return false<br>     }<br>     if (this.hash !== shortHash(this.toString())){ <br>     // 2. Ensure &#39;this.hash&#39; has been correctly computed. <br>        //    This step makes sure the block data hasn&#39;t been modified.<br>      return false<br>     }<br>     if (! this.challenge()){ <br>     // 3. Ensure the found &#39;this.nonce&#39; in this block satisfies the Bitcoin puzzle.<br>      return false<br>     }<br>     <br>    }</pre><p>3. The puzzle in this block is solved.</p><pre>verify(){ // to verify a single block<br>     if (this.signature === &#39;&#39;){ <br>     // 1. Ensure &#39;this.signature&#39; has been filled by some verifier.<br>      return false<br>     }<br>     if (this.hash !== shortHash(this.toString())){ <br>     // 2. Ensure &#39;this.hash&#39; has been correctly computed. <br>        //    This step makes sure the block data hasn&#39;t been modified.<br>      return false<br>     }<br>     if (! this.challenge()){ <br>     // 3. Ensure the found &#39;this.nonce&#39; in this block satisfies the Bitcoin puzzle.<br>      return false<br>     }<br>     // 4. Verify the validation of the digital signature.<br>     const user = users[this.verifier];<br>     return user.key.verify(this.toString(), this.signature);<br>    }</pre><p>4. The signature of the block verifier is valid.</p><p>The block is valid if all these four checks pass. Then, let’s come back to the User object again to setup mining.</p><h4>User (part 2)</h4><p>Now we have built the block and its puzzle challenge verification. Let’s construct the <em>mine()</em> function step by step. There are six steps in total.</p><pre>mine(){<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>        <br>        // [ Write code here ]</pre><pre>        // 1. collect the timestamp<br>        const timestamp = new Date();<br>        <br>    }</pre><ol><li>setup the timestamp</li></ol><pre>mine(){ // to mine the coins<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>  <br>  // 1. collect the timestamp<br>  const timestamp = new Date();<br>  // 2. pick several transactions (defined by variable &#39;capability&#39;)  <br>  // Warning. Bitcoin deals with transactions using Merkle tree data structure.<br>  // In this PoC case, merkle tree is omitted for easy understanding.<br>  const txs = []; <br>  while (unpackagedTxs.length &gt; 0 &amp;&amp; txs.length &lt; capability) { // if the block has space and there are unpackaged tx<br>   const tx = unpackagedTxs.pop(0);<br>   txs.push(tx);<br>  }<br>  const data = JSON.stringify(txs);</pre><pre> }</pre><p>2. pick some transactions to package into block</p><pre>mine(){ // to mine the coins<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>  <br>  // 1. collect the timestamp<br>  const timestamp = new Date();<br>  // 2. pick several transactions (defined by variable &#39;capability&#39;)  <br>  // Warning. Bitcoin deals with transactions using Merkle tree data structure.<br>  // In this PoC case, merkle tree is omitted for easy understanding.<br>  const txs = []; <br>  while (unpackagedTxs.length &gt; 0 &amp;&amp; txs.length &lt; capability) { // if the block has space and there are unpackaged tx<br>   const tx = unpackagedTxs.pop(0);<br>   txs.push(tx);<br>  }<br>  const data = JSON.stringify(txs);<br>  // 3. collect the hash value of previous block<br>  const previousHash = blockchain.latestBlock().hash;</pre><pre> }</pre><p>3. collect the hash value of the previous block</p><pre>mine(){ // to mine the coins<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>  <br>  // 1. collect the timestamp<br>  const timestamp = new Date();<br>  // 2. pick several transactions (defined by variable &#39;capability&#39;)  <br>  // Warning. Bitcoin deals with transactions using Merkle tree data structure.<br>  // In this PoC case, merkle tree is omitted for easy understanding.<br>  const txs = []; <br>  while (unpackagedTxs.length &gt; 0 &amp;&amp; txs.length &lt; capability) { // if the block has space and there are unpackaged tx<br>   const tx = unpackagedTxs.pop(0);<br>   txs.push(tx);<br>  }<br>  const data = JSON.stringify(txs);<br>  // 3. collect the hash value of previous block<br>  const previousHash = blockchain.latestBlock().hash;<br>  // 4. try different nonces until solve the puzzle.<br>  let nonce, block;<br>  while (true){ // trying different nonces to satisfy the challenge<br>   nonce = crypto.randomBytes(32).toString(&#39;hex&#39;);<br>   block = new Block(timestamp, data, previousHash, nonce);<br>   if (block.challenge()){<br>    break;<br>   }<br>  }<br>  <br> }</pre><p>4. mining</p><pre>mine(){ // to mine the coins<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>  <br>  // 1. collect the timestamp<br>  const timestamp = new Date();<br>  // 2. pick several transactions (defined by variable &#39;capability&#39;)  <br>  // Warning. Bitcoin deals with transactions using Merkle tree data structure.<br>  // In this PoC case, merkle tree is omitted for easy understanding.<br>  const txs = []; <br>  while (unpackagedTxs.length &gt; 0 &amp;&amp; txs.length &lt; capability) { // if the block has space and there are unpackaged tx<br>   const tx = unpackagedTxs.pop(0);<br>   txs.push(tx);<br>  }<br>  const data = JSON.stringify(txs);<br>  // 3. collect the hash value of previous block<br>  const previousHash = blockchain.latestBlock().hash;<br>  // 4. try different nonces until solve the puzzle.<br>  let nonce, block;<br>  while (true){ // trying different nonces to satisfy the challenge<br>   nonce = crypto.randomBytes(32).toString(&#39;hex&#39;);<br>   block = new Block(timestamp, data, previousHash, nonce);<br>   if (block.challenge()){<br>    break;<br>   }<br>  }<br>  // 5. sign the solved block<br>  block.verifier = this.address;<br>  block.signature = this.key.sign(block.toString());<br>  // 6. add the block using &#39;blockchain.addblock()&#39; <br>  blockchain.addBlock(block);<br> }</pre><p>5. sign the block after successfully mining</p><pre>mine(){ // to mine the coins<br>        // This is the proof of work, keep trying different nonces until satisfying the block challenge (puzzle)<br>  <br>  // 1. collect the timestamp<br>  const timestamp = new Date();<br>  // 2. pick several transactions (defined by variable &#39;capability&#39;)  <br>  // Warning. Bitcoin deals with transactions using Merkle tree data structure.<br>  // In this PoC case, merkle tree is omitted for easy understanding.<br>  const txs = []; <br>  while (unpackagedTxs.length &gt; 0 &amp;&amp; txs.length &lt; capability) { // if the block has space and there are unpackaged tx<br>   const tx = unpackagedTxs.pop(0);<br>   txs.push(tx);<br>  }<br>  const data = JSON.stringify(txs);<br>  // 3. collect the hash value of previous block<br>  const previousHash = blockchain.latestBlock().hash;<br>  // 4. try different nonces until solve the puzzle.<br>  let nonce, block;<br>  while (true){ // trying different nonces to satisfy the challenge<br>   nonce = crypto.randomBytes(32).toString(&#39;hex&#39;);<br>   block = new Block(timestamp, data, previousHash, nonce);<br>   if (block.challenge()){<br>    break;<br>   }<br>  }<br>  // 5. sign the solved block<br>  block.verifier = this.address;<br>  block.signature = this.key.sign(block.toString());<br>  // 6. add the block using &#39;blockchain.addblock()&#39; <br>  blockchain.addBlock(block);<br> }</pre><p>6. publish this block to the blockchain</p><p>As you might notice, the 6th step have employed undefined function <em>addBlock(block)</em> in the Blockchain object. Let’s move on the last step to build a Blockchain.</p><h4>Blockchain</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/718c79cfcb0304a5c48251ea78ba9bc2/href">https://medium.com/media/718c79cfcb0304a5c48251ea78ba9bc2/href</a></iframe><p>With a quick glimpse of the constructor, it is obvious that the <em>Blockchain</em> object contains only three variables, the <em>chain</em> (of blocks), the mining <em>difficulty</em> and the mining <em>reward</em>. The first block is called the genesis block, which is quite different than other blocks. Some initial settings may be defined here. The only two work left here is to finish the <em>addBlock(block)</em> and the <em>verifyAllBlocks()</em> functions.</p><pre>addBlock(block){ // to add a new block<br>     // 1. verify the validity of the block<br>     if (block.verify()){<br>      <br>     } else{<br>        console.log(&#39;Invalid block.&#39;)<br>     }<br>    }</pre><p>The first thing is to verify the validity of the block desired to be added. Thanks god, it has been down in the <em>Block</em> object.</p><pre>addBlock(block){ // to add a new block<br>     // 1. verify the validity of the block<br>     if (block.verify()){<br>        // 1-1. verify the validity of all transactions<br>        const txs = JSON.parse(block.data);<br>        let validTxs = true, tx, sender;<br>        for (let i = 0; i &lt; txs.length; i++){ // for all txs in block, verify the signature<br>        tx = new Transaction(txs[i][&#39;from&#39;], txs[i][&#39;to&#39;], txs[i][&#39;amount&#39;], txs[i][&#39;tip&#39;]);<br>        tx.signature = txs[i][&#39;signature&#39;];<br>        if (! tx.verify()){<br>           validTxs = false;<br>           break;<br>        }<br>     } else{<br>        console.log(&#39;Invalid block.&#39;)<br>     }<br>    }</pre><p>The second thing is to check whether all transactions in this block are valid or not. It’s a bit messy, the above code conceptually rebuilds transactions objects and calls its function <em>Transaction.verify()</em> as the validity check.</p><pre>addBlock(block){ // to add a new block<br>     // 1. verify the validity of the block<br>     if (block.verify()){<br>        // 1-1. verify the validity of all transactions<br>        const txs = JSON.parse(block.data);<br>        let validTxs = true, tx, sender;<br>        for (let i = 0; i &lt; txs.length; i++){ // for all txs in block, verify the signature<br>        tx = new Transaction(txs[i][&#39;from&#39;], txs[i][&#39;to&#39;], txs[i][&#39;amount&#39;], txs[i][&#39;tip&#39;]);<br>        tx.signature = txs[i][&#39;signature&#39;];<br>        if (! tx.verify()){<br>           validTxs = false;<br>           break;<br>        }<br>        // 1-2. if all transactions are verified valid, deal with the payment<br>        if (! validTxs){<br>            console.log(&#39;Invalid transaction found.&#39;);<br>        } else{<br>            // 1-3. for each payment<br>            for (let i = 0; i &lt; txs.length; i++){ // for all txs in block<br>            const tx = txs[i];<br>            // 1-3-1. pay amount to tx.to<br>            pay(tx.from, tx.to, tx.amount); <br>            // 1-3-2. pay tip to the block verifyer<br>            pay(tx.from, block.verifier, tx.tip); <br>            // 1-3-3. record the transaction on the blockchain<br>            txs[tx.hash] = tx; // record the transaction<br>        }<br>     } else{<br>        console.log(&#39;Invalid block.&#39;)<br>     }<br>    }</pre><p>Third, deal with the payment if all transactions are verified valid. The payment in Bitcoin relies on the unspent transaction object (UTXO). Because the story is too long and I’m tired so that we just forget it at this while. A pre-define function <em>pay(from, to amount)</em> is treated as an intuitive implementation to deal with the bill. For each transactions:</p><ol><li>the sender pays the receiver the “<em>amount</em>”</li><li>the sender pays the block verifier the “<em>tip</em>”</li><li>add the transaction to the history</li></ol><pre>addBlock(block){ // to add a new block<br>     // 1. verify the validity of the block<br>     if (block.verify()){<br>        // 1-1. verify the validity of all transactions<br>        const txs = JSON.parse(block.data);<br>        let validTxs = true, tx, sender;<br>        for (let i = 0; i &lt; txs.length; i++){ // for all txs in block, verify the signature<br>        tx = new Transaction(txs[i][&#39;from&#39;], txs[i][&#39;to&#39;], txs[i][&#39;amount&#39;], txs[i][&#39;tip&#39;]);<br>        tx.signature = txs[i][&#39;signature&#39;];<br>        if (! tx.verify()){<br>           validTxs = false;<br>           break;<br>        }<br>        // 1-2. if all transactions are verified valid, deal with the payment<br>        if (! validTxs){<br>            console.log(&#39;Invalid transaction found.&#39;);<br>        } else{<br>            // 1-3. for each payment<br>            for (let i = 0; i &lt; txs.length; i++){ // for all txs in block<br>            const tx = txs[i];<br>            // 1-3-1. pay amount to tx.to<br>            pay(tx.from, tx.to, tx.amount); <br>            // 1-3-2. pay tip to the block verifyer<br>            pay(tx.from, block.verifier, tx.tip); <br>            // 1-3-3. record the transaction on the blockchain<br>            txs[tx.hash] = tx; // record the transaction<br>            // 1-4. deal with the block<br>            // 1-4-1. the blockchain pays block award to the block verifier<br>            pay(admin.address, block.verifier, this.reward); <br>            // the admin pays the mining reward to the block verifier<br>            // 1-4-2. add the block to the blockchain<br>            this.chain.push(block);<br>        }<br>     } else{<br>        console.log(&#39;Invalid block.&#39;)<br>     }<br>    }</pre><p>Forth, the blockchain rewards the hard working block verifier and add this block to the blockchain.</p><p>Finally, we have the last function to implement. The <em>verifyAllBlock()</em> is relatively straightforward compared to aforementioned other functions.</p><pre>verifyAllBlocks() { // to verify all blocks of the chain<br>        <br>    // [ Write code here ]</pre><pre>    // 1. for each block<br>    for(let i = 1; i &lt; this.chain.length; i++) {<br>        const currentBlock = this.chain[i];<br>        const previousBlock = this.chain[i - 1];<br>        // 1-1. make sure the hash value of each block is kept in the next block<br>        if (previousBlock.hash !== currentBlock.previousHash) {<br>            return false;<br>        }<br>      }<br>        console.log(&#39;Whole blockchain is verified correct.\n&#39;);<br>        return true;<br>    }<br>}</pre><p>For each block, ensure the hash of the <em>previousBlock</em> is stored in the <em>currentBlock</em>.</p><pre>verifyAllBlocks() { // to verify all blocks of the chain<br>        <br>    // [ Write code here ]</pre><pre>// 1. for each block<br>    for(let i = 1; i &lt; this.chain.length; i++) {<br>        const currentBlock = this.chain[i];<br>        const previousBlock = this.chain[i - 1];<br>        // 1-1. make sure the hash value of each block is kept in the next block<br>        if (previousBlock.hash !== currentBlock.previousHash) {<br>            return false;<br>        }<br>        // 1-2. make sure each block (except for the first block, genesis) is valid<br>        if (! currentBlock.verify()) {<br>           return false;<br>        }<br>      }<br>        console.log(&#39;Whole blockchain is verified correct.\n&#39;);<br>        return true;<br>    }<br>}</pre><p>Second, make sure all blocks are valid.</p><p>Congrats!! We have finished our Bitcoin PoC, it’s really a tough work (for writing as well). Hope this may help you practically realize more design details about the Bitcoin. If you really work hard, but the program doesn’t work, a ready program called index.js is available in the same directory. Any question or anything you found that I may misunderstand, please let me know. To be honest, many designs in Bitcoin have been omitted in this story, but it still looks unfriendly long. Hope that there will be some experts finish the omitted parts in the future.</p><p>If you enjoy the stories and willing to read more easily-understanding cryptographic or blockchain-related content, please give me some claps. I’ll be flattered if there are some sponsorship via Bitcoin or Ethereum.</p><p>Bitcoin: 36FmpfiDPVAJdxKtXM79Lj5G5awZgDNKar</p><p>Ethereum: 0x37fd7D56a7228344F1bca1132d7D1b1ED398FCaa</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8bb2db549c32" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Symmetric & Asymmetric encryption]]></title>
            <link>https://kyle-crypto.medium.com/symmetric-asymmetric-encryption-5d8d4f6d80f1?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d8d4f6d80f1</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[public-key-cryptography]]></category>
            <category><![CDATA[asymmetric-encryption]]></category>
            <category><![CDATA[digital-signatures]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Sun, 09 Jun 2019 16:32:33 GMT</pubDate>
            <atom:updated>2022-03-28T17:36:53.442Z</atom:updated>
            <content:encoded><![CDATA[<p>When it comes to encryption, most people may feel boring and complex. Inevitably, in most cases, I admit it is not as fascinating as 3D animations, neither comparable with AI computations, etc. However, it at least satisfies a basic requirement that we can whisper to someone.</p><p>Imaging a private channel between you and your friends that no outsider can eavesdrop, the encryption suddenly becomes more important. Furthermore, the encryption indeed plays a pretty vital role while the private channel is established to protect your credit card numbers as well as some sensitive private information from being tampered or sniffed. In this story, some essential concept of encryption will be chatted about. There will be not too much complex technical terms, symbols or professional computations. This story may be regarded as a history where the encryption comes from and a rough image what does it look like nowadays.</p><h3>Symmetric encryption — shift and substitution</h3><p>Again, when it comes to encryption, an intuitive way to make strings “unrecognizable” is to shift several digits, such as from “<em>cat</em>” to “<em>ecv</em>”. The sender make shift of the origin message and delivers it via an insecure public channel; if one receiver knows the secret 2 (or so called the key), he can roll back the original message. Definitely, it is not a strong encryption yet, there are only few possible keys if only shift is taken into consideration. Following, the substitution is also adopted. Assume a mapping table is set to map “<em>c</em>” into “<em>Z</em>”, “<em>a</em>” into “<em>1</em>” and “<em>t</em>” into “<em>h</em>”. The ciphertext “<em>Z1h</em>” comes out after computing <em>encrypt(key, “cat”)</em> where the key definitely indicates to the mapping table. If a receiver know the table, the decryption <em>“cat” = decrypt(key, “Z1h”)</em> is an inverse mapping using the same mapping table. The combination of two elements, shift and substitution, conceptually build up the symmetric encryption system where the term “symmetric” denotes that the encryption and decryption relies on the same key.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uu6JschI8cAZkkppCwvUXw.png" /><figcaption><strong>How symmetric encryption work and its related shortcuts.</strong></figcaption></figure><p>From the <a href="https://en.wikipedia.org/wiki/Caesar_cipher">Caesar Cipher</a> thousands of years ago to present, the symmetric encryption was kept progressing. A well-known cryptography-related movie, the imitation game, described how Alan Tuning broke the German cipher machine, <a href="https://en.wikipedia.org/wiki/Enigma">Enigma</a>, to help terminate the second-world war earlier; and Enigma is also an implementation of symmetric encryption. Until today, the modern symmetric encryption algorithms like advanced encryption standard (AES), triple data encryption standard (3-DES) and pretty good privacy (PGP) still work both robustly and efficiently. Whereas, some issues also occur along with the usage of symmetric encryption schemes.</p><h4>Key distribution issues</h4><p>To make the decryption success, the receiver has to learn the corresponding key of a ciphertext. How could the key be delivered in an insecure channel becomes a tough problem. The condition is depicted in above picture: the key should be transferred in a secure channel; however, to construct a secure channel, a key is necessary. It fails into a deadlock that each side is waiting for the other side. In case that two parties of the data transfer are not geographically close, the key distribution is quite tough.</p><h4>Key storage issues</h4><p>Another potencial problem of symmetric encryptions is the key storage. For each pair of sender and receiver, there should be one key for secure transfer. If there are <em>n</em> parties, the total key requirements is basically <em>n(n-1)/2</em>, that’s horrible. For example, there are totally 4950 keys among a group of 100 members. Shown in above picture as well, the key storage needs <em>O(n²)</em> space consumptions.</p><h3>Asymmetric encryption — a pair of keys</h3><p>There is a story that cryptographers occationaly found a “pair” idea from some mathmatical textbook. Then, the asymmetric encryption was born while the pair concept was adopted into cryptography. In brief, a pair of keys (say key <em>a</em> and key <em>b</em>) be generated in the key generation phase; then, the operation between the plaintext and key <em>a</em> can only be ”undone” by key <em>b</em>, and vise versa. Following, the key <em>a</em> is published as a public key, and key <em>b</em> is kept secret as a secret key. It is intuitive to build up an asymmetric encryption which the encryption could be constructed by the public key and the decryption is implemented by the related secret key. Illustrated in the picture below, it is how asymmetric encryption works.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1STKrEXUW_R0mHO8kPVhog.png" /><figcaption><strong>The architecture of asymmetric encryption.</strong></figcaption></figure><p>Let <em>(sk, pk)</em> be the key pair of Alice, which stands for the secret key and the public key respectively, generated by algorithm <em>key-generation.</em> Bob encrypts message <em>m</em> into a ciphertext <em>c=encrypt(pk, m)</em> using Alice’s public key <em>pk</em>; and Alice obtains <em>m=decrypt(sk, c)</em> through decryption with her secret key <em>sk </em>after receiving. Due to the essentially difference from symmetric encryption, the asymmetric encryption is also called public key encryption.</p><h4>Application — RSA encryption</h4><p>As the first asymmetric encryption, RSA is a famous algorithm that perfectly illustartes the pair idea. Now, let’s quickly go through a simplified version of RSA to help understand the asymmetric encryption. All messages of RSA encryption is encoded as a number <em>m</em> between <em>2</em> and <em>n-1</em>, which are represented as <em>m mod n</em>. Operator <em>mod</em> denotes modular, such as <em>8 mod 3 = 2</em>. Then, assume the public key is <em>pk</em> and the secret key is <em>sk</em>, it is easy to implement the encryption <em>encrypt(pk, m)</em> by computing <em>c=m^pk mod n</em>; and the related decryption <em>decrypt(sk, c)</em> is computed by <em>m=c^sk mod n</em>. Two keys <em>sk</em> and <em>pk</em> will be slashed while they’re puting together in the modular operation. In case that parameters <em>sk </em>and <em>n</em> are big enough, the RSA encryption will be computationally secure.</p><p>Hope that above scenario helps understand the architecture of asymmetric encryption. Due to that fact that the operation between the plaintext and the public key can only be “undone” by the secret key, it is designed that the public key could be shared to the world to make everybody able to encrypt; but only the secret key owner has the capability of decryption. After the architecture, let’s move forward to realize how does asymmetric encryptions deal with the problems that bother symmetric encryptions?</p><h4>Key distribution issues</h4><p>It is straightforward that the asymmetric encryptions easily solve the key distribution issues by hidding credentials to the secret key. Everyone knows the public key can encrypt, but only the secret key owner can decrypt. Obviously, no key distribution issue exist over asymmetric encryption.</p><h4>Key storage issues</h4><p>In the asymmetric case, everyone only has to remember their own part: the secret key, the public key, and a certificate signed by a trusted third party. The certificate is a proof that someone owns the public key provided by a trusted third party, which will be introduced soon.</p><h4>Remark</h4><p>It is emphasised that I’m <strong>not</strong> saying the asymmetric encryption is greater than the symmetric encryptions and the former should replace the latter. Both of them have some irreplaceable advantages. In general, the symmetric encryptions are much higher efficient and robust because it bases on bit-wise based operations; and the asymmetric encryptions do not suffer from the key distribution and storages issues. Besides, some special functionality like homomorphism over asymmetric encryptions make it more creative in some private-preserving services.</p><h3>Digital signature</h3><p><a href="https://medium.com/@kylehuang_96433/digital-signature-c601da3c0c02?source=friends_link&amp;sk=6c44146e06831b1f69d13b50f0efbeac">Digital signature</a> is an interesting well-known appplication of the asymmetric key setting. In the same scenario that the public key is published and the secret key is kept secretly. Then,the secret key owner is able to convince others that a document is “encrypted by the secret key”. Following, we also take RSA for example to demonstrate how a digital signature work in a simplified manner.</p><h4>Application — RSA signature</h4><p>Let h() be a collision-resistant <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236?source=friends_link&amp;sk=bfdfe10b88fb24da352ee3bd05fa2750">hash function</a>, <em>m</em> stands for some message and <em>n</em> denotes the modular number, the RSA signature is computed as <em>sig=h(m)^sk mod n</em>; and the verification is testing the equality between <em>h(m) </em>and<em> sig^pk mod n</em>. Two keys <em>sk</em> and <em>pk</em> will be slashed while they’re puting together in the modular operation. This is an intuitive implementation of digital signature based on the asymmetric key setting.</p><p>Here we take term “sign” instead of “encrypt” for clear expression of <em>sig=sign(sk, h(m))</em>. Since only the secret key can make the signature as well as the operation between plaintext and the secret key can be “undone” by the related public key, everyone knowing the public key and message is able to verify the identity of the signer through algorithm <em>verify(pk, h(m), sig)</em>. More detail about digital signature could be found in another <a href="http://If you enjoy the stories and willing to read more easily-understanding cryptographic or blockchain-related content, please give me some claps. I&#39;ll be flattered if there are some sponsorship via Bitcoin or Ethereum.  Bitcoin: 36FmpfiDPVAJdxKtXM79Lj5G5awZgDNKar  Ethereum: 0x37fd7D56a7228344F1bca1132d7D1b1ED398FCaa">story</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d8d4f6d80f1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Digital signature]]></title>
            <link>https://kyle-crypto.medium.com/digital-signature-c601da3c0c02?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/c601da3c0c02</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[digital-signatures]]></category>
            <category><![CDATA[hash-function]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Sun, 02 Jun 2019 09:01:50 GMT</pubDate>
            <atom:updated>2022-03-28T17:30:50.390Z</atom:updated>
            <content:encoded><![CDATA[<p>The digital signature is a frequently utilized tool in the modern IT technique, which could be regarded as a cryptographic version of electronic hand-made signature. Before our subject digital signature, let’s review the real-world scenarios of hand-made signatures.</p><h4>Scenarios</h4><ol><li>Alice signs the receipt of a credit card bill, which denotes not only the authorization of the transaction but also the authentication of Alice that only Alice can make the hand-made signature (assuming the signature isn’t forged).</li><li>Bob signs on the right bottom corner of a contract as a proof of two things: first, the authentication of Bob (assuming the signature isn’t forged); and secondly, Bob agrees with the contract.</li></ol><p>It is not hard to observe that the signature authenticates the signer first. If the authentication is verified, then the signed document works on behalf of the signer such as Alice approves the transaction in the first case and Bob makes deal in the second scenario.</p><p>So far, a signing architecture is taking shape that composed of a signer, a signing target and some verifiers. The signer and only the signer is able to generate a signature corresponding to a specific signing target. Then, the signature may be verified (publicly or not), which convinces the verifiers that the signature is made on behalf of the signer.</p><p>So, what is a digital signature?</p><p>Digital signature is a cryptographic tool based on the cooperation of <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236?source=friends_link&amp;sk=bfdfe10b88fb24da352ee3bd05fa2750">hash functions</a> and asymmetric encryption. Similar to hand-made signatures, digital signature is attached with a signing target with three properties:</p><h4>Authentication of the signer</h4><p>This is the most essential and core functionality that verifiers are convinced who signed the target.</p><p>For security aspect, the authentication relies on the unforgeability of digital signature, which is the most improved part from the hand-made signatures. In the scenarios above, it was assumed that no forging hand-made signatures exists. However, it occasionally occurs everywhere surrounds us.</p><p>In terms of digital signatures, the cryptographic unforgeability of digital signature guarantees that it’s computationally difficult (which is close to impossible in real-world) to forge a digital signature without knowing the secret key. In other words, only the signer who owns the secret key can sign the signature.</p><h4>Non-repudiation of the signer</h4><p>Based on the powerful unforgeability above, the signer cannot deny the signature afterward.</p><h4>Integrity of the signing target</h4><p>This is another import part but often missed that the signed target has to be unchanged. Assume it’s a 5-dollars bill, the payer may not be happy if the signature is still valid while it is tampered to 50 dollars. The integrity part is mostly achieved by adopting collision-resistant <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236?source=friends_link&amp;sk=bfdfe10b88fb24da352ee3bd05fa2750">hash functions</a>.</p><h3>How does a digital signature work?</h3><p>Now, a basic concept of digital signature has been established. We may take a closer look to realize how it works practically.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tkHS1TRI-Mo0NuohhJ9Aig.png" /><figcaption><strong>The general data flow of a digital signature.</strong></figcaption></figure><p>Assume that every user already has a unique pair of secret key <em>sk</em> and public key <em>pk </em>in an <a href="https://medium.com/@kylehuang_96433/symmetric-asymmetric-encryption-5d8d4f6d80f1?source=friends_link&amp;sk=df0ffd71ad8e037f2bcdfa0f37b17916">asymmetric key setting</a>. The secret key is kept privately in a secure place like offline hardwares; and the related public key could be published so that everyone in the network knows the user owns that public key. By the way, assume the signing target is a message <em>m</em>.</p><h4>Signing steps</h4><ol><li>The signer computes the hash value of input message: <em>h=hash(m)</em>.</li><li>The signer takes its secret key as well as the hash value as input, and outputs the signature <em>sig = sign(sk, h)</em>.</li></ol><p>With the aid of <a href="https://medium.com/@kylehuang_96433/hash-function-a0912682d236?source=friends_link&amp;sk=bfdfe10b88fb24da352ee3bd05fa2750">hash functions</a>, the digital signature can take any kind of files, strings or number as the signing target. Then, everyone knows the signer’s public key can be a verifier. Once receiving the message <em>m</em> and signature <em>sig</em>, the verifying steps work as follows.</p><h4>Verifying steps</h4><ol><li>The verifier also computes, <em>h=hash(m)</em>.</li><li>The verifier executes the verifying algorithm that outputs one of results, valid or invalid, which is <em>verify(pk, h, sig)</em>.</li></ol><p>The practical implementation varies from distinct signing algorithms such as RSA, DSA and ECDSA. This story addresses the basic image of digital signatures so let’s expect the above-mentioned algorithms may appear in other stories in the near future.</p><p>If you enjoy the stories and willing to read more easily-understanding cryptographic or blockchain-related content, please give me some claps. I’ll be flattered if there are some sponsorship via Bitcoin or Ethereum.</p><p>Bitcoin: 36FmpfiDPVAJdxKtXM79Lj5G5awZgDNKar</p><p>Ethereum: 0x37fd7D56a7228344F1bca1132d7D1b1ED398FCaa</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c601da3c0c02" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Hash function]]></title>
            <link>https://kyle-crypto.medium.com/hash-function-a0912682d236?source=rss-106f26f617ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/a0912682d236</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[hash-function]]></category>
            <dc:creator><![CDATA[Kyle]]></dc:creator>
            <pubDate>Tue, 28 May 2019 16:25:18 GMT</pubDate>
            <atom:updated>2022-03-28T17:27:57.225Z</atom:updated>
            <content:encoded><![CDATA[<h3>Hash functions</h3><p>With the rapid growth of blockchain, FinTech, or Bitcoin, hash functions gradually attract more attentions in recent years. Several mining machines or application-specific integrated circuits (ASICs) became famous with their great computational hash power. That hash power becomes an ability that profits in the Bitcoin society.</p><p>So, what exactly is a hash function?</p><p>A hash function is a function that takes any string with arbitrary bit-length as input, then it produces a <em>deterministic</em> fixed-length string as the function output. The short output may be a unique identifier representing the original input. By the way, the term <em>deterministic </em>denotes the same outputs come out while given the same inputs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l-hDP-gpVp6eNiYyT5t-IA.png" /></figure><h3>A practical hash operation</h3><p>Before theorems and definitions, users with a linux-based operating system like MacOS, Fedora or Ubuntu can easily obtain a SHA256 hash value of files through following command.</p><pre>openssl dgst [algorithm] [path-to-file]</pre><p>There are some common hash algorithm like -sha256 and -sha384 could be found by entering</p><pre>openssl dgst -help</pre><p>Following, a practical command which produces a SHA256 hash value of a file <em>path-to-file</em>. No matter that file accounts tens of megabytes or even gigabytes, the SHA256 hash value is 256 bits.</p><p><strong>Command</strong></p><pre>openssl dgst —sha256 [path-to-file]</pre><p><strong>Output</strong></p><pre>SHA256(path-to-file)= bb4a9cbd401e3ed8b9bad674bbb50febe8b9df0acb4e2f87be7a79369ead6430</pre><p>For more hash implementations, plenty of <a href="https://www.fileformat.info/tool/hash.htm">online hash function calculator</a> might help us understand the computation before and after various hash functions.</p><h3>Common hash functions</h3><p>The secure hash algorithm (SHA) series are endorsed by FIPS and NIST so that they’re the mostly widely adopted hash algorithms. The older versions SHA0 and SHA1 have been corrupted so that please carefully avoid these algorithms; while the definition of security and corrupted will be later introduced. By the way, the algorithm SHA1 is pretty similar to SHA2, and SHA1 has been corrupted. However, SHA2 keeps secure or so called survived due to the fact that its output length is 256 bits or more (depend on its variants), which is much longer than outputs of SHA1 (160 bits). NIST chose SHA3 as the next generation member of the SHA family because SHA3 executes totally different algorithm from SHA1 and SHA2. That might be a quite long story if we’re going to discuss about the history. Here we just list some common recommended and corrupted algorithms as common senses.</p><h4>Recommended</h4><p>SHA2 series (SHA256, SHA384, SHA512), SHA3 (keccak), RIPEMD-160</p><h4>Insecure</h4><p>MD4, MD5, SHA1</p><p>Then, let’s keep going deeper to understand what are hash functions and what roles can hash functions play in the modern IT industries. Don’t worry, it will not be very theoretically.</p><h3>Why do we need hash functions?</h3><p>A hash function converts its various source inputs into fixed format outputs known as the <em>hash value</em>, the <em>digest</em> or the <em>footprint</em>. There are numerous advantages that make it so powerful in our modern IT industries: on one hand, it works quite efficiently so that each binary files in the computer or Internet could become a digest easily; on the other hand, it provides powerful utilities along with its properties such as <em>one-way</em>, <em>collision-resistant</em>, <em>avalanche effect</em> and <em>universal distribution</em>.</p><h4>One-way</h4><p>Let <em>y = hash(x)</em>, it is efficient to compute <em>y</em> from <em>x</em>; but it is extremely difficult to reveal any bit of <em>x</em> while given value <em>y</em> and hash function. With this property, it could be guaranteed that value <em>x</em> exists before value <em>y</em> does. Besides, one party may deliver <em>y</em> in order to make a secure data comparison without revealing data <em>x</em> to another party.</p><h4>Collision-resistant</h4><p>For any two different values <em>a</em> and <em>b</em> as inputs, it is harshly difficult to find a collision that satisfies <em>hash(a) = hash(b)</em>. Hence, the correctness of hash value overwhelmingly implies the integration of its source input. The collision-resistant property ensures the integrity of original inputs in a very cheap way, which enables the short fixed-length footprint to stand for its large source. Many large file transferring services like Linux distributions provide digest for file integration verification.</p><h3>Applications of hash functions</h3><p>Two properties above are mostly common utilized. The most well-known application is that: with the aids of hash functions, the <a href="https://medium.com/@kylehuang_96433/digital-signature-c601da3c0c02?source=friends_link&amp;sk=6c44146e06831b1f69d13b50f0efbeac">digital signature</a> works on input any format of electronic files or strings. Besides, in the Bitcoin case, block <em>n+1</em> contains the digest of block <em>n</em>. On one hand, it proves block <em>n</em> exists prior to block <em>n+1</em>(one-way); and on the other hand, it ensures the integrity and correctness of block <em>n</em> (collision-resistant). The latter blocks repeatedly empower the integrity of former blocks so that the blockchain structure continuously become more and more immutable. Bitcoin is an elegant technique that needs more stories to describe, if you’re interested in that part, some <a href="https://bitcoin.org/en/how-it-works">resource</a> could be referred.</p><p>Another famous application about the hash function is the password storage. For example, those big companies like Google and Facebook owns billions of user accounts and personal information. If they store users’ password as plaintext without processing, the whole data is in danger once the identity server is corrupted. A well-known solution is to save the hash values of users’ passwords rather than the passwords. On one hand, it keeps password verifiable; on the other hand, if the identity server is corrupt, by the <em>one-way</em> property, those digests keep password much much more secure. The acquirement of each password becomes extremely difficult for hackers. This is a serious issue that might be discussed in some future.</p><h3>Security of hash functions</h3><p>When it comes to security, it is unavoidably more theoretical, I’ll try my best to keep it not that sophisticated. Let’s recall the process that a hash function maps an any-length input to a fix-length output. In other words, it is well-known that theoretically, there must be many collisions that <em>x != y</em> and <em>hash(x)=hash(y)</em>. The pigeon-hole theory explains this situation in an easily-understanding manner: <em>n+1</em> pigeons live in <em>n</em> cages, there must be at least one cage contains <em>2</em> pigeons.</p><p>First, the <em>one-way</em> property is easily-understanding while the collisions exists. Given the digest <em>hash(x)=hash(y)</em>, it is impossible to precisely indicate the input values <em>x</em> and <em>y</em>. Considering the fact that an <em>infinity-to-one</em> mapping occurs along with the hash computation, the <em>one-way</em> property is trivially obtained.</p><p>Secondly, the <em>collision-resistant</em>!? Contradictorily, it seems that we just discussed about the <em>infinity-to-one</em> mapping that cause a lot collisions. Yes, we’re magically insisting on its <em>collision-resistant</em> property. More precisely, the collisions in fact exist; however, they’re computationally hard to find. The difficulty depends on the output length of hash functions. Take SHA256 for example, it outputs a non-predictable <em>256</em>-bit number between <em>0</em> and <em>2²⁵⁶ -1</em>. There are trillions of trillions of trillions of trillions of possible outputs so that the collisions quite rarely occur. Note that the wide range of outputs is insufficient to guarantee the <em>collision-resistant</em> property, more properties like <em>uniform distribution</em> is required which will be introduced later, which is even more theoretical and difficult to be proven. Before scientists conquer the proof issues, the hash functions currently act like <em>collision-resistant</em>, and we just <em>believe</em> the employed hash function are <em>collision-resistant</em> until it is corrupted. Aforementioned SHA1 and MD5 hash functions have been corrupted since collisions of them were found.</p><h3>Other properties</h3><p>The following two properties are not that commonly adopted in modern IT industries so that readers may decide to skip this phrase or continue to understand the other sides of hash functions.</p><h4>Avalanche effect</h4><p>This is an appropriate name about this property which describes a tiny difference between two input sources (even only one-bit difference) makes numerous bias between two hash values. A stronger definition called strict avalanche effect defines each one bitwise change influences approximately half bits of the hash outputs.</p><h4>Uniform distribution</h4><p>This is an ideal assumption adopted in some cryptographic works, which assumes the outputs of hash function is uniformly distributed in the domain it locates. While the input is unknown, the hash function works unpredictably as a random number generator in the specific domain. This is so far still an argument that whether it exists or not. Random oracle model is a theoretical model aside from cryptographic security proofs that assumed hash functions are uniform distribution.</p><p>If you enjoy the stories and willing to read more easily-understanding cryptographic or blockchain-related content, please give me some claps. I’ll be flattered if there are some sponsorship via Bitcoin or Ethereum.</p><p>Bitcoin: 36FmpfiDPVAJdxKtXM79Lj5G5awZgDNKar</p><p>Ethereum: 0x37fd7D56a7228344F1bca1132d7D1b1ED398FCaa</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a0912682d236" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>