Go语言HashCash算法：高效哈希碰撞检测与类型转换实践

// 原始尝试中的部分代码片段，存在类型转换问题
// func partialAllZeroes (zeroCount uint8, val int64) (bool, error) { /* ... */ }
// hasher := sha1.New()
// // ...
// testCollision := hasher.Sum(nil) // []byte
// // 如何将 testCollision 的前 x 位转换为 int64 以供 partialAllZeroes 使用是一个难题

package main

import (
    "crypto/sha1"
    "fmt"
    "strconv"
    "strings"
    "time"
)

// partialAllZeroes 检查字节数组 b 的前 zeroCount 位是否全为零
func partialAllZeroes(zeroCount uint8, b []byte) bool {
    // 逐字节检查：如果当前字节不为0，则直接返回false
    // 每次循环处理8位
    i := 0
    for zeroCount >= 8 {
        if b[i] != 0 {
            return false
        }
        i++
        zeroCount -= 8
    }

    // 处理剩余不足8位的零位要求
    // 构建一个掩码，用于检查最后一个部分字节
    var mask byte
    switch zeroCount {
    case 0:
        mask = 0x00 // 不需要检查任何位
    case 1:
        mask = 0x80 // 检查最高位 (10000000)
    case 2:
        mask = 0xC0 // 检查前两位 (11000000)
    case 3:
        mask = 0xE0 // 检查前三位 (11100000)
    case 4:
        mask = 0xF0 // 检查前四位 (11110000)
    case 5:
        mask = 0xF8 // 检查前五位 (11111000)
    case 6:
        mask = 0xFC // 检查前六位 (11111100)
    case 7:
        mask = 0xFE // 检查前七位 (11111110)
    }

    // 注意：这里的掩码是用于检测 *非零* 位。
    // 如果 b[i] & mask == 0，意味着在掩码对应的位置上，b[i] 的位都为零。
    // 例如，zeroCount=3，mask=0xE0 (11100000)。如果 b[i] = 00010000，那么 b[i] & mask = 0。
    // 这表示 b[i] 的前三位是零。

    // 为了使逻辑更直观，我们可以检查 (b[i] >> (8 - zeroCount)) == 0。
    // 或者，使用一个反向的掩码来检查是否所有 *期望为零* 的位都为零。
    // 假设我们期望最高 zeroCount 位为零。
    // 那么需要检查 b[i] & (0xFF << (8 - zeroCount)) 是否为零。
    // 例如，zeroCount=3，期望 b[i] 的前三位为零。掩码为 0xFF << 5 = 11100000 (0xE0)。
    // 如果 (b[i] & 0xE0) == 0，则前三位为零。

    // 修正后的掩码逻辑：
    // 目标是检查字节 b[i] 的前 zeroCount 位是否为零。
    // 构造一个掩码，其前 zeroCount 位为1，其余为0。
    // 然后与 b[i] 进行按位与操作，如果结果为0，则表示前 zeroCount 位为0。
    if zeroCount > 0 { // 只有当还有位需要检查时才执行
        if i >= len(b) { // 如果已经超出了字节数组的范围
            return false // 或者根据需求返回true/false，这里假设超出范围则不满足条件
        }
        // 例如，zeroCount = 3，mask应为 11100000 (0xE0)
        // 0xFF (11111111) << (8 - 3) = 0xFF << 5 = 11100000
        mask = 0xFF << (8 - zeroCount)
        return (b[i] & mask) == 0
    }
    return true // 如果 zeroCount 为 0，则始终满足条件
}

// HashCashProofOfWork 模拟客户端寻找满足条件的Nonce
func HashCashProofOfWork(baseString string, zeroBits uint8) (string, time.Duration) {
    startTime := time.Now()
    var nonce int64 = 0 // 从0开始尝试Nonce
    for {
        // 将baseString和当前nonce组合
        data := baseString + strconv.FormatInt(nonce, 10)

        // 计算SHA-1哈希
        hasher := sha1.New()
        hasher.Write([]byte(data))
        hash := hasher.Sum(nil) // 获取 []byte 类型的哈希值

        // 检查哈希值是否满足零位条件
        if partialAllZeroes(zeroBits, hash) {
            duration := time.Since(startTime)
            return strconv.FormatInt(nonce, 10), duration
        }
        nonce++
        // 避免无限循环，可以设置一个最大nonce值或时间限制
        if nonce > 1_000_000_000 { // 示例：限制最大尝试次数
            return "", time.Since(startTime) // 未找到
        }
    }
}

func main() {
    // 示例：客户端寻找Nonce
    baseCollisionString := "example@domain.com:1678886400:random_data:" // 包含邮箱、时间戳等
    targetZeroBits := uint8(20) // 目标是哈希值前20位为零

    fmt.Printf("开始寻找 HashCash Nonce，目标前 %d 位为零...\n", targetZeroBits)
    foundNonce, duration := HashCashProofOfWork(baseCollisionString, targetZeroBits)

    if foundNonce != "" {
        fmt.Printf("找到 Nonce: %s\n", foundNonce)
        fmt.Printf("耗时: %s\n", duration)

        // 验证：服务端验证过程
        finalData := baseCollisionString + foundNonce
        hasher := sha1.New()
        hasher.Write([]byte(finalData))
        finalHash := hasher.Sum(nil)

        fmt.Printf("验证哈希: %x\n", finalHash)
        if partialAllZeroes(targetZeroBits, finalHash) {
            fmt.Println("验证成功：哈希值前", targetZeroBits, "位确实为零。")
        } else {
            fmt.Println("验证失败：哈希值不满足条件。")
        }
    } else {
        fmt.Printf("在指定尝试次数内未找到满足条件的 Nonce。耗时: %s\n", duration)
    }

    // 另一个简单的测试用例
    fmt.Println("\n--- 简单测试 partialAllZeroes ---")
    testBytes1 := []byte{0x00, 0x00, 0x01, 0x00} // 00000000 00000000 00000001 00000000
    fmt.Printf("Bytes: %x, 检查 8 位零: %t\n", testBytes1, partialAllZeroes(8, testBytes1))   // true
    fmt.Printf("Bytes: %x, 检查 16 位零: %t\n", testBytes1, partialAllZeroes(16, testBytes1)) // true
    fmt.Printf("Bytes: %x, 检查 17 位零: %t\n", testBytes1, partialAllZeroes(17, testBytes1)) // false (第三个字节的最高位是1)

    testBytes2 := []byte{0x00, 0x00, 0x00, 0x00}
    fmt.Printf("Bytes: %x, 检查 32 位零: %t\n", testBytes2, partialAllZeroes(32, testBytes2)) // true

    testBytes3 := []byte{0x0F, 0x00} // 00001111 00000000
    fmt.Printf("Bytes: %x, 检查 4 位零: %t\n", testBytes3, partialAllZeroes(4, testBytes3))   // true
    fmt.Printf("Bytes: %x, 检查 5 位零: %t\n", testBytes3, partialAllZeroes(5, testBytes3))   // false
}