Haskell Whileループで再帰は単純にはできませんか？

Question

私はハスケルと宣言言語の初心者ですが、思考実験として、興味深いコーディング演習がHashcash algorithmのようなものを実装することになると決めました。あなたがそれに精通していなければ、基本的にBitcoin Proof of Workスキームの祖父です。これは、SHA-1ダイジェストにハッシュされたときに、最初にnビットがゼロであるはずの電子メールヘッダーの作成を指定します。nは、作業証明の難しさです。これは、受信者の妥当性を確認するのは簡単なことですが、大量のスパム送信操作を阻止しようとしている送信者には、CPUサイクルの控えめな費用がかかります。非常に具体的だが潜在的に大量の不可欠な一連のステップを機能的かつ宣言的な方法で取り組もうとしながら、ByteStringsやビットをHaskellで操作する方法を学ぶことができたので、これは私にとって興味深い行為でした。本質的には、送信側はカウンタをインクリメントして潜在的なヘッダを再構築してテストしなければならず、その特定のテストが有効であれば有効なヘッダを持っていなければなりません。難易度が上がるにつれて指数関数的になるように設計されています。

この時点で私の問題は、1と2ビットのゼロの難しさはうまくいくようですが、3つ以上の難易度になると、スタックが爆発するまで無限ループに巻き込まれるようです。 whileループを使用するのではなく、再帰的な方法でこれを実行しようとしたので、カウンタの厳密性を指定して、次のステップに移る前に前回のサンクを計算しなければならなくなりました。無限ループに陥っ（またはおそらくパフォーマンスは、私が最後に取得することはありませんように悪いのですか？）こと

{-# LANGUAGE BangPatterns #-} 

module HashCash where 

import Data.Int 
import Data.List 
import Data.List.Split (splitOn) 
import Data.Char 
import Data.Function 
import System.Random 
import Data.Bits 
import Data.Either 
import Data.Binary.Strict.Get 
import System.IO as SIO 
import Data.Word (Word32) 
import Data.ByteString as B 
import Data.ByteString.Char8 as BC 
import Data.ByteString.UTF8 as BU 
import Data.ByteString.Base64 as B64 
import Data.ByteString.Conversion as BCON 
import Data.ByteArray as BA 
import Crypto.Random 
import Crypto.Hash 


startingCounter :: Int32 
startingCounter = 1 
difficulty :: Int 
difficulty = 4 
template = "X-Hashcash: 1:{:{:{::{:{" 
dateTemplate = "YYMMDDhhmmss" 
address = "a@a" 

-- example date because I dont want to mess with date formatting just now 
exampleDate = "150320112233" 

convertToString :: ByteString -> String 
convertToString b = BU.toString b 

convertFromString :: String -> ByteString 
convertFromString s = BU.fromString s 

convertIntToString :: Int -> String 
convertIntToString a = convertToString . BCON.toByteString' $ a 

encodeInt32 :: Int32 -> ByteString 
encodeInt32 a = B64.encode . BCON.toByteString' $ a 

mahDecoder :: Get Word32 
mahDecoder = do 
    first32Bits <- getWord32be 
    return first32Bits 

firstBitsZero :: (Bits a) => a -> Int -> Bool 
firstBitsZero val num = Data.List.foldl' (\acc x -> (testBit val x) && acc) True [1..num] 

formatTemplate :: String -> [String] -> String 
formatTemplate base [] = base 
formatTemplate base (x:xs) = 
    let splix = (Data.List.Split.splitOn "{" base) :: [String] 
     splixHead = Data.List.head splix ++ x 
     splixTail = Data.List.tail splix 
     concatSplitTail = Data.List.init $ Data.List.concatMap (++ "{") splixTail 
    in formatTemplate (splixHead ++ concatSplitTail) xs 

get16RandomBytes :: (DRG g) => g -> IO (ByteString, g) 
get16RandomBytes gen = do 
    let a = randomBytesGenerate 16 gen 
    return $ a 

getBaseString :: ByteString -> Int32 -> String 
getBaseString bs counter = 
    let encodedVal = B64.encode bs 
     encodedCounter = encodeInt32 counter 
     baseParams = [(convertIntToString difficulty), exampleDate, address, (convertToString encodedVal), (convertToString encodedCounter)] 
    in formatTemplate template baseParams 

hashSHA1Encoded :: ByteString -> ByteString 
hashSHA1Encoded bs = 
    let hashDigest = hash bs :: Digest SHA1 
     byteString = B.pack . BA.unpack $ hashDigest 
    in B64.encode byteString 

-- Pass a counter and if the first 20 bits are zero then return the same counter value else increment it 
-- signifying it is time to test the next number (NOTE: recursive style, may overflow stack) 
testCounter :: ByteString -> Int32 -> Int32 
testCounter rb !counter = 
    let baseString = getBaseString rb counter 
     hashedString = hashSHA1Encoded $ convertFromString baseString 
     !eitherFirst32 = runGet mahDecoder hashedString 
     incCounter = counter + 1 
    in case eitherFirst32 of 
    (Left first32, _) -> testCounter rb incCounter 
    (Right first32, _) -> if (firstBitsZero first32 difficulty) 
          then counter 
          else testCounter rb incCounter 

generateHeader :: IO String 
generateHeader = do 
    g <- getSystemDRG 
    (ran, _) <- get16RandomBytes g 
    let counter = testCounter ran startingCounter 
    return $ getBaseString ran counter 

main :: IO() 
main = do 
    header <- generateHeader 
    SIO.putStrLn header 
    return() 

だから、明確にこれは動作しませんし、私はまだ、なぜそれほどわかりませんが、私はでした私がこれを解決できるよりよい方法について考えようとしています。たとえば、testCounterのモナドアクションのsequenceを作成し、それぞれのアクション結果の条件についてtakeWhileを実行して、もはや必要があるかどうかを確認できますか？

もしそうでなければ、Proof of Workアルゴリズムは、宣言的な関数型プログラミングには意味がないクラスのアプリケーションに当てはまりますか？

Answer 1

問題はコードの効率性ではありません。

"0"ビットではなく「1」ビットをチェックしているので、実際には無限ループに入っています。

ハッシュの実際のビットではなく、Base64でエンコードされたハッシュのバージョンにfirstBitsZeroを適用しています。

Base64（つまり、ASCII！）表現が「始まる」（以下を参照）のビット数が1ビットおよび/または0ビットより少ないハッシュを生成するのに問題はないのは驚きではありません。

この2つの問題を修正すると、-O2最適化をオンにコンパイルすると、プログラムが1分以内に20ビットのHashCashを生成することがわかります。まだ遅すぎるが、はっきりとはるかに改善された。代わりに、

SPOILERS 



SPOILERS 



SPOILERS 

• 最初の32ビット・ワードの少なくとも上位ビットがゼロである場合は、チェックされています

  は、あなたはまだ、実際のhashcashと互換性のないプログラムを作るバグの数を持っています（そして、testBitのビットインデックスが1で始まると仮定していますが、実際にはゼロで始まります）。

• ハッシュする文字列の一部ではない、X-HashCash:のプレフィックスを含むヘッダー全体がハッシュされています。

これらを修正すると、プログラムが正常に動作しているように見えます。たとえば、難易度20でプログラムによって生成されたハッシュキャッシュは、mahDecoderを使って20ビットのゼロビットで始まることを検証できます。

> runGet mahDecoder (hashSHA1 "1:20:150320112233:a@a::2go+qPr1OxIigymGiuEDxw==:NTE3MDM0") 
(Right 753,"[\191\GS\237iw\NAKIp\193\140)BZI_") 
> 

また、確認する文字列はX-HashCashヘッダーを除外します。

ところで、プロジェクトの素晴らしい選択。