QH-E-logo

Quadhelion Engineering

A Primer on Blockchain focusing on fundamental Cryptography as it applies to Bitcoin

adoc - Python & Julia Worksheet

Required Reading

Total reading time all 3 ⇒ 37 mins

  1. A Peer-to-Peer Electronic Cash System (20mins: original source, simple readthrough ingestion w/o total comprehenion)

  2. Hijacking Bitcoin (7min: Cliffnotes)

  3. How Epstein Saved Bitcoin (10mins: News Article)

Chapter 1

Cryptographic Hash Functions

  • Mathematical Hash function:

    • Takes any string as input

    • Fixed size output (We’ll use 256 as does Bitcoin [$BTC])

    • Efficiently Computable

  • Security Properties of Cryptographic Hash Functions

    • Collision free

    • Hiding

    • Puzzle-Friendly

Collision Free

--- title: Nobody can find x and y such that x != y and H(x) = H(y) --- stateDiagram-v2 X --> H\\(x\\)\\=H\\(y\\) Y --> H\\(x\\)\\=H\\(y\\)
Perspective

Mathematical probability for collision

$$\sum^{m-1}_{i=1} \frac{i}{T} = \frac{M(M-1)}{2T}$$

For i-th element, the probability of total number of collisions = (i-1)/T as there are i-1 previous elements which can collide and T is the total number of possible values, where M is a given hash value *

Table 1. Collision rates
Bits In Elements for 1st Collision

8

23

16

362

32

92,682

64

6,074,001,000 (6 Billion)

128

26,087,635,650,665,564,424

256

4.8 x 10^38

Hashes are NOT Collision Free and People DO find them

In 2008, the CMU Software Engineering Institute declared MD5 "cryptographically broken and unsuitable for further use"
SHA-256 is under heavy fire from AI on High Performance Computing Grids and Quantum Computing. FERMILAB, CERN, IBM, or Microsoft may already have the hardware capability.
MD5 Hash Broken via Collision Attack of Less Than $1

  • How to find a Collision

    • Try 2^130 randomly chosen inputs

    • 99.8% change that two of them are the same output from different input

  • This works no matter how long H (Hash function elements) are but it takes too long to matter for regular computers

"If every computer ever made by Humanity was computing since the beginning of the Universe up to now, the odds they would have found a collision is so infinitesimally small it would be like the chance of being hit by an asteroid in the next two seconds."
— Ed Felton

  • Brute forcing is interminably slower than Birthday Attacks.

  • No H (Hash function) has ever been proven to be collision free

"We choose to believe that some hash functions are collision free"
— Ed Felton

  • Many hash functions have been broken and are insecure

  • We will go forward assuming our hash function is collision free.

Hashes as message digests

  • Hash as a pointer to unique information relayable through a network

  • Useful because the hash is small

  • Compare 256bit hashes of files instead of files

Hiding

  • Infeasible to know the content of the input string being hashed from the hash unless input set of elmenents are low and can be recreated and matched with the hash.

  • Thus, inputs must be broad and as random as possible

  • Done by prepending high-min-entropy r (Random) to the input $$H(r | x)$$

Application Hiding: Commitment

CryptoWiki Explainer

A commitment scheme in the context of Bitcoin allows a sender to commit to a value while keeping it hidden from the receiver, with the ability to reveal the value later. This process ensures that the sender cannot change the committed value after it has been revealed, a property known as binding. Additionally, the receiver should not be able to determine the committed value during the commitment phase, known as the hiding property 
(com, key) --> commit(msg)
match --> verify(com, key, msg)

  • Sealing transactions
    (com, key) -→ commit(msg) -→ publish: com

  • Opening transactions
    Publish: key, msg where anyone can use verify() to check validity

Commitment API

  • Commitments are binding

Where H is a hash function, key or k is a random 256bit value, com is transaction data, | is concatenation

commit(msg) = H(key | msg), key)
verify(com, key, msg) = (H (key | msg) == com)
From the Whitepaper
Satoshi on transaction hashing
Figure 1. Satoshi says

Puzzle-Friendly

  • Property implies that no solving strategy is much better than brute-forcing commitments

Bitcoin Uses SHA-256

--- title:SHA-256 Hash Function --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart LR msgBlock-1@{ shape: stored-data } msgBlock-2@{ shape: stored-data } msgBlock-Nth@{ shape: stored-data } padding@{ shape: fork, label: "Padding bits appended" } padding@{ shape: processes, label: "Padding (10* | length)" } style c1 fill:#F5E10A style c2 fill:#F5E10A style c3 fill:#F5E10A Input@{ shape: manual-input, label: "256bit Input Variable \"IV\" "} style Input fill:#9B0AF5, stroke-width:5px,color:#000, stroke-dasharray: 5 5 style Hash fill:#80680A c2@{ animate: true } Input --> c1 c1{compression} --> c2{compression} c2@==> c3{compression} msgBlock-1 -- 512 bits --> c1 msgBlock-2 -- 512 bits --> c2 msgBlock-Nth --> padding padding-. One 1 and zeroes until the final 64bit length field .-> c3{compression} c3{compression} --> Hash@{ shape: lin-cyl, label: "256bit\nHASH" }

Chapter Quiz

Which of the following is true of SHA-256?

It has been proven not to have a collision?

False

We hope that there are no collisions?

False

No collision has ever been found?

True

It has been proven that there is no fast way to find collisions?

False

Further Information

Deterministic bitcoin commitments

Chapter 2

What is a Hash Pointer?

A cryptographic hash that references another data storage location

Functions

  1. Retrieve stored data

  2. Verify Integrity

  3. Consists of two data stores: hash + pointer

You can Build Data Structures with Hash Pointers on top of another structure type like Merkle Trees for example
--- title: Linked List --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart LR mp1@{ shape: win-pane, label: "Data" } mp2@{ shape: win-pane, label: "Data" } mp3@{ shape: win-pane, label: "Data" } comment-end@{ shape: braces, label: "Linked List\n Chain of Blocks" } style HASH fill:#80680A comment-end ~~~ HASH HASH ~~~ comment-end mp3 --> HASH mp1 -- previous Hash pointer --> mp2 mp2 -- previous Hash pointer --> mp3
--- title: Hacked Log File --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart LR mp1@{ shape: win-pane, label: "Genisys Block" } mp2@{ shape: win-pane, label: "Tampered Data" } mp3@{ shape: win-pane, label: "𝚫 HASH" } comment-end@{ shape: braces, label: "Tamper Evident\n Chain" } style mp2 fill:#FFF,stroke-width:2px,color:red,stroke-dasharray: 5 5 style mp3 stroke-width:2px,color:red style HASH fill:#80680A,stroke-width:2px,color:red,stroke-dasharray: 5 comment-end ~~~ HASH{"!= HASH"} HASH{"!= HASH"} ~~~ comment-end mp3 --> HASH{"!= HASH"} mp1 -- previous Hash pointer --> mp2 mp2 -- previous Hash pointer --> mp3
--- title: Merkle Tree of Hash Pointers, H --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart TB mp1@{ shape: win-pane, label: "Data" } mp2@{ shape: win-pane, label: "Data" } mp3@{ shape: win-pane, label: "Data" } mp4@{ shape: win-pane, label: "Data" } mp5@{ shape: win-pane, label: "Data" } mp6@{ shape: win-pane, label: "Data" } mp7@{ shape: win-pane, label: "Data" } mp8@{ shape: win-pane, label: "Data" } H-a1 --> H-b1 H-a1 --> H-b2 H-b1 --> H-c1 H-b1 --> H-c2 H-b2 --> H-c3 H-b2 --> H-c4 H-c1 --> mp1 H-c1 --> mp2 H-c2 --> mp3 H-c2 --> mp4 H-c3 --> mp5 H-c3 --> mp6 H-c4 --> mp7 H-c4 --> mp8
--- title: Merkle Tree Membership Proof --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart TB mp8@{ shape: win-pane, label: "Data" } H-a1 --> H-b2 H-b2 --> H-c4 H-c4 --> mp8

PROOF of membership: Sequence branch

Items to show, Time to verification $$O(\log n)$$

Advantages Of Merkle Trees

  • Many itmes, one hash

  • Membership verification of data block in O(log n) time/space

  • SORTED Merkle Tree can verify non-membership in O(log n) time/space

    • Showing items before and after the non-existent data block

      • Members beore and after are consecutive

  • Can use Hash pointers in any datastructure that doesn’t cycle

Chapter Quiz

Which of the following types of modifications of a block chain data structure can be detected?

Insertion of a block?

True

Deletion of a block?

True

Tampering of data in a block?

True

Re-ordering of blocks?

True

Chapter 3

Digital Signatures

Schema

  • pk = public key

  • sk = secret key

  • m and/or M = Message

  • sig = cryptographic signature we are talking about

Requirements

  • Cannot be forged

  • Like PGP, only one signer per key

    • Keys are tied to signer/user by another system

      • Usually the first to announce the public key

  • Open Verification

    • verify -→ public key + message + signature

  • Verification of signer and message go togther

    • Per message authenticity

      • Public Key

  • In totality constitutues a signature scheme

  • Cannot be forged

Features

  • Key Size

  • Utilize Randomization

Characteristics

And I’ll just point out here that attacks on the source of randomness are a favorite trick of intelligence agencies.
— Ed Felton
https://www.coursera.org/learn/cryptocurrency/lecture/bx6si/digital-signatures

  • Minimizing message size lends itself to send hashes of messages instead of messages

Signing a hash pointer creating a signature of that pointer covers the whole structure.
Using that tip, signing the last block in a chain would enumeratively digitally signing the contents of all prior blocks.

Specifications of Bitcoin

Bitcoin’s choice/implementation for Signature Algorithm is Elliptic Curve Digital Signature Algorithm (ECDSA) — DETAILED CRYPTO REFERENCE which is a United States Government Standard

The Current Director of the National Institute of Science and Technology is temporarily a Lawyer named Craig Burkhardt
"6. The Elliptic Curve Digital Signature Algorithm (ECDSA) — This standard (FIPS 186-5) specifies (in Section 6.4) methods for digital signature generation and verification using the Elliptic Curve Digital Signature Algorithm (ECDSA). Specifications for the generation of the domain parameters used during the generation and verification of digital signatures are included in SP 800-186, Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters [5]. ECDSA is the elliptic curve analog of DSA. ECDSA keys shall not be used for any other purpose (e.g., key establishment). Deterministic ECDSA (Section 6.3.2) is a variant of ECDSA, where a per-message secret number is a function of the message that is signed, thereby resulting in a deterministic mapping of messages to signatures. This variant does not impact the signature verification process. IETF RFC 6979, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) [4], describes this deterministic digital signature generation procedure. The use of deterministic ECDSA may be desirable for devices that do not have a good source of quality random numbers. For signature schemes, secrecy of the private key is critical. This is especially true with deterministic signature schemes, which return a unique signature computed from the hash of the private key and the message. Care must be taken to protect implementations against attacks, such as side-channel attacks or fault attacks [17, 18, 19, 20, 21, 22]. A cryptographic device may leak critical information with side-channel analysis or attacks that allow internal data or keying material to be extracted without breaking the cryptographic primitives. It is also important to verify the correctness of group arithmetic computations for ECC implementations. These types of attacks may be of particular concern for hardware implementations of deterministic signature schemes, as well as embedded or IoT devices and smartcards."
— from NIST.gov https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf
You probably leaked your private key
— Ed Felton

Chapter Quiz

Which of these keys are required for verifying a signature?

  1. The secret key

    False

  2. The public key

    True

  3. Both the secret and the public key

    False

  4. None. Keys are required only for signing; anyone can verify the signature without a key

    False

Chapter 4

Public Keys as Indentities

  • Only one person knows the secret and that is the identity for them which the public can verify

  • Can be Anonymous

  • De-centralized identity management

In Bitcoin, an address is an identity

You can create an identity by typing the followig into a shell: ssh-keygen -f ~/.ssh/MY-NEW-IDENTITY -C "your@email.address" -t ECDSA -b 521

Chapter Quiz

If you generate numerous identities (public keys) for yourself and interact online using those different identities, what might happen? (Check all that apply)

  1. Others might be able to take over your identities if your randomness is bad

    True

  2. Others may be able to link your identities because public keys generated on the same computer look similar

    False

Others may be able to de-anonymize you by analyzing your activity patterns True

Chapter 5

A simple sample cryptocurrency

SimpliCoin Where H is a Hash Pointer

  • SimpliCoin can create coins CoinID

  • SimpliCoin signs transactions

  • Sign coins CoinID{pk}

  • SimpliCoin signs to Bob CoinID{Bob}

  • CoinID{Bob} -→ H() -→ SimpliCoin sig

  • Transaction from CoinID{Bob} to CoinID{Alice} CoinID{Alice} H() -→ CoinID{Bob} H() -→ CoinID{SimpliCoin}

--- title: Merkle Tree Membership Proof --- %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart LR CoinID1@{ shape: win-pane, label: "Data" } CoinID1{"Alice Hash Pointer"} --> CoinID2{"Bob Hash Pointer"} --> CoindID3{"SimpliCoin pk"}

Software Method - AIM

Three is simple and robust enough which is our AIM to never fail

title Each word means ALL the facets of it, the sub-bullets are mandatory highlights and do not mean only that part of the parent.

  1. Account

    • Features

      • Main classes

    • Problems

  2. Identify

    • Structures

      • Modularize core components

        • Enables transition from modularized existing replacments to whole replicatable system of core modules

    • Dataflow

    • Chokepoints

      • Databases

      • Networks

  3. Manage

    • Goals

    • Formats

Chapter Quiz

In ScroogeCoin, you have ten coins each of value 3.0. You’d like to transfer coins of value 5.0 to your friend. This requires:

  1. One transaction, one new coin created, and one signature

    False

  2. One transaction, two new coins created, and two signatures

    True

  3. Two transactions, two new coins created, and four signatures

    False

  4. Two transactions, one new coin created, and two signatures

    False

Powered By

Powered by MathJax     LaTeX logo     Ruby Programming Language     Asciidoc Markdown