HàPhan 河

HashCash - crypto currencies' algorithm

Introduction

At the moment of writting this post, Bitcoin just hit $60,000 with a market cap over 1 TRILLION USD. That's huge number.

If you invested 250$ for 17 Bitcoin in 2013, now you are billionaire.
I wish I have a time-machine to travel to the past and buy some :cry:

Hmm just get back to life :). As you may know, every Bitcoin transactions block need to be sealed, when someone seal it correctly they will get rewards. So how to generate the Stamp to seal?

Each block of transactions contains header and body. Body is the list of transactions, header is a string which has format:
version:hashPrevblock:hashMerkleRoot:time:bits:nonce

  • version: block version number
  • hashPrevBlock: 256-bit hash of the previous block header
  • hashMerkleRoot: 256-bit hash of current block body
  • time: current block time stamp, since 1970-01-01T00:00 UTC
  • bits: current target in compact format
  • nonce: 32bit-number start from 0

A block is considered as valid one, if SHA256(SHA256(header)) passing the verification algorithm - check result string has exact number of leading zeros. Valid header is the Stamp to be mined.

The algorithm to calculate header based on Hashcash algorithm.
Let see how it works.

The Input and the Output

Input

version: version of block
resource: consider as block information (hashPrevBlock and hashMerkleRoot)
bits: leading zeros padding to validate (default is 20)
ext: additional information (optional)
timestamp: current datetime in format yyyyMMddHHmmss
saltLength: length to create a random string to make result unique (default is 16)

the final input:
version:bits:timestamp:resource:ext:saltString

Output

Output format should be: version:bits:timestamp:resource:ext:saltString:counter

counter was made while algorithm running.
It starts from 0 until valid output was found.

Algorithm

The algorithm is not hard as you though:

  • Build input strings with correct format
  • Add counter to input
  • Hash the input
  • Repeat step 2 and 3 if hashed value is not contains exactly leading zeros
  • Return result if the loop was breaked.
func mint(
    version: Int,
    resource: String,
    bits: Int = 20,
    ext: String = "",
    timestamp: String,
    saltLength: Int = 16
) -> String {
    let salt = String.salt(length: saltLength)
    let input = "\(version):\(bits):\(timestamp):\(resource):\(ext):\(salt)"
    
    var counter = 0
    while(true) {
        let challenge = input + ":\(String(format: "%02x", counter))"
        let hashed = challenge.sha256()
        if hashed.hasLeadingZeros(bits) {
            return challenge
        }
        counter += 1
    }
}

extension String {
    static func salt(length: Int) -> String {
        let chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/="
        return (0..<length).map { _ -> String in
            let random = Int.random(in: 0..<chars.count)
            let index = chars.index(chars.startIndex, offsetBy: random)
            return String(chars[index])
        }.joined()
    }
    
    func sha256() -> String {
        let data = self.data(using: .utf8)!
        let hashed = SHA256.hash(data: data)
        return hashed.compactMap { String(format: "%02x", $0) }
            .joined()
    }
    
    func hasLeadingZeros(_ zerosCount: Int) -> Bool {
        let digits = Int(ceil(Double(zerosCount) / 4))
        let zeros = String(repeating: "0", count: digits)
        let indexToCheck = self.index(self.startIndex, offsetBy: digits)
        return zeros == self[startIndex..<indexToCheck]
    }
}

extension Date {
    func timestamp() -> String {
        let formatter = DateFormatter()
        formatter.dateFormat = "yyyyMMddHHmmss"
        return formatter.string(from: self)
    }
}

Verify the seal

To verify this seal version:bits:timestamp:resource:ext:saltString:counter
we need to do some steps:

  • verify order of elements
  • check expirations of timestamp
  • verify resource is matching
  • verify hashed string contains correct leading zeros.
protocol Validator {
    var version: Int { get }
    var timeFormat: String { get }
    var expiration: UInt? { get }
    var bits: UInt { get }
    
    func validate(_ stamp: String, _ resource: String?) -> Bool
}

extension Validator {
    func validate(_ stamp: String, _ resource: String?) -> Bool {
        let components = stamp.components(separatedBy: ":")
        
        guard components.count > 6 else {
            return false
        }
        
        guard checkVersion(components[0]),
              checkBits(components[1]),
              checkDate(components[2]),
              checkResource(components[3], with: resource) else {
            return false
        }
        
        return checkHash(stamp)
    }
    
    private func checkDate(_ date: String) -> Bool {
        let dateformatter = DateFormatter()
        dateformatter.dateFormat = self.timeFormat
        guard let date = dateformatter.date(from: date) else {
            return false
        }
        
        if let expiration = self.expiration {
            let expDate = Date(timeIntervalSinceNow: -TimeInterval(expiration))
            guard (date >= expDate) else {
                return false
            }
        }
        
        return true
    }
    
    private func checkVersion(_ ver: String) -> Bool {
        return (Int(ver) ?? 1) <= self.version
    }
    
    private func checkResource(_ res: String, with res2: String?) -> Bool {
        if res2 == nil {
            return true
        }
        return res2 == res
    }
    
    private func checkBits(_ bits: String) -> Bool {
        return Int(bits) == Int(self.bits)
    }
    
    private func checkHash(_ string: String) -> Bool {
        return string.sha256().hasLeadingZeros(bits)
    }
}

let give it a try

let stamp = mint(version: 1, resource: "hallo", timestamp: Date().timestamp())
print(stamp)
print(Ver1Validator().validate(stamp, "hallo"))

this is a sample valid result i tried on my machine:

1:20:20210403170942:hallo::MoxqvFOLGnwjs=Ko:8717
with hashed value
000005219105fb754ab98d4715e23fd2b489823b0468c337db7121c6432bbe9e

Conclusion

Finally we did it... That's good start to deep understand how crypto currency works.

But this algorithm is just a tiny part of crypto currency.
There're much more difficulty in real world like: tool to create transactions, to to distribute the whole block-chain to validators (miner) or infrastructure for system...

Let see more in near future.

Comments