Proof Of Work 算法

工作量证明(proof-of-work),概念最早由Cynthia Dwork和Moni Naor于1993年的学术论文提出,主要用于防止/阻断对服务滥用行为的一种算法对策,早期广泛应用在电子邮件服务上,对抗网络上大部分的垃圾邮件,现在是区块链加密货币共识机制之一

其算法主要原理是提出一个问题且需要通过复杂的计算(穷举)才可以得出答案(极可能是多个),而服务方可以简单且快速运算验证

假设现在服务方提供一个接口，但希望对客户方(请求方)进行一定的频率约束，从而降低接口滥用和资源成本，我们可以设计一种算法，以当前时间为题目，计算出一个字符串，使得其Hash值(假设使用MD5)包含时间戳部分截取信息,并且可以通过对时间戳和服务器当前时间进行校验,偏离过大则拒绝

原理过程

得出一个timestamp:1685808827832

对其后 6 位进行截取得出 827832 , 且进行十六进制处理得出 ca1b8

之后随机出一个值字符串 randomStr

1 2	// JS 代码 let randomStr = Math.random().toString(36).substr(3)

使得 md5(randomStr)的值包含 ca1b8 则代表验证成功

1
2
3

// JS 代码
let timestampCut = timestamp.toString().substr(-6).toString(16) // ca1b8
md5(randomStr).indexOf(timestampCut) != -1

完整代码 pow.js

// 使用前先安装 md5 模块 : npm install md5
const md5 = require("md5")

// 时间戳截取长度 , 从后向前截取
const LENGTH = 6

// check proof of work data
const checkPow = (randomTxt, timestamp) => {
    let [numStr] = getTimeState(timestamp)
    let randMd5Str = md5(randomTxt)
    return randMd5Str.indexOf(numStr) != -1

}

/**
 * 获取 [截取字符串,时间戳]
 *
 * @param {long} fixedTimestamp 固定时间戳，可选，如果设置了则 numStr 以该时间戳截取
 * @returns [numStr,timestamp]
 */
const getTimeState = (fixedTimestamp) => {
    let timestamp = !!fixedTimestamp ? fixedTimestamp : new Date().getTime()
    if(timestamp >>> 38 < 0){
        throw new Error(`${timestamp} is don't look like timestamp type`)
    }
    let timestampStr = timestamp.toString()
    let cutTimestampStr = timestampStr.substr(-LENGTH)
    let num = Number.parseInt(cutTimestampStr)
    let numStr = num.toString(16)
    return [numStr, timestamp]
}

/**
 * generate proof of work data
 */
const pow = () => {
    let [numStr, timestamp] = getTimeState()

    let md5Str = ""
    let count = 0, maxCount = 2000
    let randomStr
    while (md5Str.indexOf(numStr) == -1) {
        randomStr = Math.random().toString(36).substr(3)
        md5Str = md5(randomStr)
        if (count++ > maxCount) {
            [numStr, timestamp] = getTimeState()
            count = 0
        }
    }

    return [randomStr, timestamp]

}

console.time('exhaustive')
let [randomStr, timestamp] = pow()
console.timeEnd('exhaustive')
console.log(`randomStr : ${randomStr} hash(randomStr)=> ${md5(randomStr)} , timestamp : ${timestamp} `)
console.time('check')
console.log(`pow checkout : ${checkPow(randomStr, timestamp)}`)
console.timeEnd('check')

gist

穷举的平均时间大概 100 ms , 而验证仅需 0.1 ms

注意

因为工作量证明是通过无效运算占用CPU时间,这种机制应该应用在客户端上,且也需要平衡实际的用户体验（用户设备,业务操作时长等等）

并且该方法 无法有效阻止 像请求回放、恶意触发等行为，在规模严重的场景下还是需要搭配其他方案（服务器记录请求/调用信息、风控检查等等）