hash-tree 0.0.1 → 0.1.0
raw patch · 4 files changed
+403/−321 lines, 4 filesdep +hash-treedep +ramdep −memorydep ~crypton
Dependencies added: hash-tree, ram
Dependencies removed: memory
Dependency ranges changed: crypton
Files
- Data/HashTree.hs +41/−29
- Data/HashTree/Internal.hs +242/−207
- hash-tree.cabal +49/−43
- test/HashTreeSpec.hs +71/−42
Data/HashTree.hs view
@@ -3,46 +3,58 @@ -- The API design is inspired by Certificate Transparency defined in RFC 6962. module Data.HashTree ( -- * Settings- Settings- , defaultSettings+ Settings,+ defaultSettings,+ -- ** Accessors- , hash0- , hash1- , hash2+ hash0,+ hash1,+ hash2,+ -- * Merkle Hash Trees- , MerkleHashTrees+ MerkleHashTrees,+ -- ** Accessors- , info- , size- , digest+ info,+ size,+ digest,+ -- ** Related types- , TreeSize- , Index+ TreeSize,+ Index,+ -- ** Creating Merkle Hash Trees- , empty- , fromList+ empty,+ fromList,+ -- ** Appending an element- , add+ add,+ -- * Inclusion Proof- , InclusionProof- , defaultInclusionProof+ InclusionProof,+ defaultInclusionProof,+ -- ** Accessors- , leafIndex- , treeSize- , inclusion+ leafIndex,+ treeSize,+ inclusion,+ -- ** Proof and verification- , generateInclusionProof- , verifyInclusionProof+ generateInclusionProof,+ verifyInclusionProof,+ -- * Consistency Proof- , ConsistencyProof- , defaultConsistencyProof+ ConsistencyProof,+ defaultConsistencyProof,+ -- ** Accessors- , firstTreeSize- , secondTreeSize- , consistency+ firstTreeSize,+ secondTreeSize,+ consistency,+ -- ** Proof and verification- , generateConsistencyProof- , verifyConsistencyProof- ) where+ generateConsistencyProof,+ verifyConsistencyProof,+) where import Data.HashTree.Internal
Data/HashTree/Internal.hs view
@@ -1,40 +1,46 @@ {-# LANGUAGE OverloadedStrings #-} module Data.HashTree.Internal (- Settings(..)- , defaultSettings- , MerkleHashTrees(..)- , digest- , info- , currentHead- , empty- , fromList- , toHashTree- , add- , InclusionProof(..)- , defaultInclusionProof- , generateInclusionProof- , verifyInclusionProof- , ConsistencyProof(..)- , defaultConsistencyProof- , TreeSize- , Index- , generateConsistencyProof- , verifyConsistencyProof- ) where+ Settings (..),+ defaultSettings,+ MerkleHashTrees (..),+ digest,+ info,+ currentHead,+ empty,+ fromList,+ toHashTree,+ add,+ InclusionProof (..),+ defaultInclusionProof,+ generateInclusionProof,+ verifyInclusionProof,+ ConsistencyProof (..),+ defaultConsistencyProof,+ TreeSize,+ Index,+ generateConsistencyProof,+ verifyConsistencyProof,+) where -import Crypto.Hash (Digest, SHA256, HashAlgorithm, hash)-import Data.Bits (testBit, finiteBitSize, countLeadingZeros, (.&.), unsafeShiftR)+import Crypto.Hash (Digest, HashAlgorithm, SHA256, hash)+import Data.Bits (+ countLeadingZeros,+ finiteBitSize,+ testBit,+ unsafeShiftR,+ (.&.),+ ) import Data.ByteArray (ByteArrayAccess) import qualified Data.ByteArray as BA import Data.ByteString (ByteString) import qualified Data.ByteString as BS import Data.ByteString.Char8 ()+import Data.IntMap.Strict (IntMap)+import qualified Data.IntMap.Strict as IntMap import Data.List (foldl') import Data.Map.Strict (Map) import qualified Data.Map.Strict as Map-import Data.IntMap.Strict (IntMap)-import qualified Data.IntMap.Strict as IntMap -- $setup -- >>> :set -XOverloadedStrings@@ -48,14 +54,14 @@ -- To create this, use 'defaultSettings': -- -- > defaultSettings { hash0 = ..., hash1 = ..., hash2 = ... }-data Settings inp ha = Settings {- -- | A hash value for non input element.- hash0 :: Digest ha- -- | A hash function for one input element to calculate the leaf digest.- , hash1 :: inp -> Digest ha- -- | A hash function for two input elements to calculate the internal digest.- , hash2 :: Digest ha -> Digest ha -> Digest ha- }+data Settings inp ha = Settings+ { hash0 :: Digest ha+ -- ^ A hash value for non input element.+ , hash1 :: inp -> Digest ha+ -- ^ A hash function for one input element to calculate the leaf digest.+ , hash2 :: Digest ha -> Digest ha -> Digest ha+ -- ^ A hash function for two input elements to calculate the internal digest.+ } sha256 :: ByteString -> Digest SHA256 sha256 = hash@@ -63,11 +69,12 @@ -- | A default Settings with 'ByteString' and 'SHA256'. -- This can be used for CT(Certificate Transparency) defined in RFC 6962. defaultSettings :: Settings ByteString SHA256-defaultSettings = Settings {- hash0 = sha256 ""- , hash1 = \x -> sha256 (BS.singleton 0x00 `BS.append` x)- , hash2 = \x y -> sha256 $ BS.concat [BS.singleton 0x01, BA.convert x, BA.convert y]- }+defaultSettings =+ Settings+ { hash0 = sha256 ""+ , hash1 = \x -> sha256 (BS.singleton 0x00 `BS.append` x)+ , hash2 = \x y -> sha256 $ BS.concat [BS.singleton 0x01, BA.convert x, BA.convert y]+ } ---------------------------------------------------------------- @@ -80,17 +87,17 @@ -- | The data type for Merkle Hash Trees. -- The first parameter is input data type. -- The second one is digest data type.-data MerkleHashTrees inp ha = MerkleHashTrees {- settings :: !(Settings inp ha)- -- | Getting the log size- , size :: !TreeSize- -- index is size of HashTree- -- 0 for Empty- -- 1 for Leaf 0 0- -- 'size' for the last HashTree- , hashtrees :: !(IntMap (HashTree inp ha)) -- the Int key is TreeSize- , indices :: !(Map (Digest ha) Index)- }+data MerkleHashTrees inp ha = MerkleHashTrees+ { settings :: !(Settings inp ha)+ , size :: !TreeSize+ -- ^ Getting the log size+ , -- index is size of HashTree+ -- 0 for Empty+ -- 1 for Leaf 0 0+ -- 'size' for the last HashTree+ hashtrees :: !(IntMap (HashTree inp ha)) -- the Int key is TreeSize+ , indices :: !(Map (Digest ha) Index)+ } -- | Getting the Merkle Tree Hash. digest :: TreeSize -> MerkleHashTrees inp ha -> Maybe (Digest ha)@@ -111,40 +118,41 @@ ---------------------------------------------------------------- -data HashTree inp ha =- Empty !(Digest ha)- | Leaf !(Digest ha) !Index inp- | Node !(Digest ha) !Index !Index !(HashTree inp ha) !(HashTree inp ha)- deriving (Eq, Show)+data HashTree inp ha+ = Empty !(Digest ha)+ | Leaf !(Digest ha) !Index inp+ | Node !(Digest ha) !Index !Index !(HashTree inp ha) !(HashTree inp ha)+ deriving (Eq, Show) -- | Creating an empty 'MerkleHashTrees'. -- -- >>> info $ empty defaultSettings -- (0,e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855) empty :: Settings inp ha -> MerkleHashTrees inp ha-empty set = MerkleHashTrees {- settings = set- , size = 0- , hashtrees = IntMap.insert 0 (Empty (hash0 set)) IntMap.empty- , indices = Map.empty- }+empty set =+ MerkleHashTrees+ { settings = set+ , size = 0+ , hashtrees = IntMap.insert 0 (Empty (hash0 set)) IntMap.empty+ , indices = Map.empty+ } value :: HashTree inp ha -> Digest ha-value (Empty ha) = ha-value (Leaf ha _ _) = ha-value (Node ha _ _ _ _) = ha+value (Empty ha) = ha+value (Leaf ha _ _) = ha+value (Node ha _ _ _ _) = ha ---------------------------------------------------------------- idxl :: HashTree inp ha -> Index-idxl (Leaf _ i _) = i+idxl (Leaf _ i _) = i idxl (Node _ i _ _ _) = i-idxl _ = error "idxl"+idxl _ = error "idxl" idxr :: HashTree inp ha -> Index-idxr (Leaf _ i _) = i+idxr (Leaf _ i _) = i idxr (Node _ _ i _ _) = i-idxr (Empty _) = error "idxr"+idxr (Empty _) = error "idxr" ---------------------------------------------------------------- @@ -152,23 +160,26 @@ -- -- >>> info $ fromList defaultSettings ["0","1","2"] -- (3,725d5230db68f557470dc35f1d8865813acd7ebb07ad152774141decbae71327)-fromList :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> [inp] -> MerkleHashTrees inp ha+fromList+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> [inp] -> MerkleHashTrees inp ha fromList set xs = foldl' (flip add) (empty set) xs -- | Adding (appending) an element. O(log n) -- -- >>> info $ add "1" $ empty defaultSettings -- (1,2215e8ac4e2b871c2a48189e79738c956c081e23ac2f2415bf77da199dfd920c)-add :: (ByteArrayAccess inp, HashAlgorithm ha)- => inp -> MerkleHashTrees inp ha -> MerkleHashTrees inp ha+add+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => inp -> MerkleHashTrees inp ha -> MerkleHashTrees inp ha add a mht@(MerkleHashTrees set tsiz htdb idb) = case Map.lookup hx idb of- Just _ -> mht+ Just _ -> mht Nothing -> case IntMap.lookup tsiz htdb of- Just ht -> let ht' = newht ht- htdb' = IntMap.insert tsiz' ht' htdb- in MerkleHashTrees set tsiz' htdb' idb'+ Just ht ->+ let ht' = newht ht+ htdb' = IntMap.insert tsiz' ht' htdb+ in MerkleHashTrees set tsiz' htdb' idb' Nothing -> mht -- never reach where tsiz' = tsiz + 1@@ -181,13 +192,14 @@ x = Leaf hx ix a hash2' = hash2 set- ins (Empty _) = x- ins l@(Leaf hl il _ ) = Node (hash2' hl hx) il ix l x+ ins (Empty _) = x+ ins l@(Leaf hl il _) = Node (hash2' hl hx) il ix l x ins t@(Node h il ir l r)- | isPowerOf2 sz = Node (hash2' h hx) il ix t x- | otherwise = let r' = ins r- h' = hash2' (value l) (value r')- in Node h' il ix l r'+ | isPowerOf2 sz = Node (hash2' h hx) il ix t x+ | otherwise =+ let r' = ins r+ h' = hash2' (value l) (value r')+ in Node h' il ix l r' where sz = ir - il + 1 @@ -195,72 +207,83 @@ -- | A simple algorithm to create a binary balanced tree. O(n log n) -- This is just for testing.-toHashTree :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> [inp] -> HashTree inp ha+toHashTree+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> [inp] -> HashTree inp ha toHashTree set [] = Empty $ hash0 set -- not used toHashTree set xs = ht where toLeaf = uncurry (leaf set)- leaves = map toLeaf $ zip xs [0..]+ leaves = map toLeaf $ zip xs [0 ..] ht = buildup set leaves -leaf :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> inp -> Index -> HashTree inp ha+leaf+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> inp -> Index -> HashTree inp ha leaf set x i = Leaf (hash1 set x) i x -link :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> HashTree inp ha -> HashTree inp ha -> HashTree inp ha+link+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> HashTree inp ha -> HashTree inp ha -> HashTree inp ha link set l r = Node h (idxl l) (idxr r) l r where h = hash2 set (value l) (value r) -buildup :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> [HashTree inp ha] -> HashTree inp ha-buildup _ [ht] = ht-buildup set hts = buildup set (pairing set hts)+buildup+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> [HashTree inp ha] -> HashTree inp ha+buildup _ [ht] = ht+buildup set hts = buildup set (pairing set hts) -pairing :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha -> [HashTree inp ha] -> [HashTree inp ha]-pairing set (t:u:vs) = link set t u : pairing set vs-pairing _ hts = hts+pairing+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha -> [HashTree inp ha] -> [HashTree inp ha]+pairing set (t : u : vs) = link set t u : pairing set vs+pairing _ hts = hts ---------------------------------------------------------------- -- | The type for inclusion proof (aka audit proof).-data InclusionProof ha = InclusionProof {- -- | The index for the target.- leafIndex :: !Index- -- | The hash tree size.- , treeSize :: !TreeSize- -- | A list of digest for inclusion.- , inclusion :: ![Digest ha]- } deriving (Eq, Show)+data InclusionProof ha = InclusionProof+ { leafIndex :: !Index+ -- ^ The index for the target.+ , treeSize :: !TreeSize+ -- ^ The hash tree size.+ , inclusion :: ![Digest ha]+ -- ^ A list of digest for inclusion.+ }+ deriving (Eq, Show) -- | The default value for 'InclusionProof' just to create a new value. defaultInclusionProof :: InclusionProof ha-defaultInclusionProof = InclusionProof {- leafIndex = 0- , treeSize = 1- , inclusion = []- }+defaultInclusionProof =+ InclusionProof+ { leafIndex = 0+ , treeSize = 1+ , inclusion = []+ } -- | Generating 'InclusionProof' for the target at the server side.-generateInclusionProof :: Digest ha -- ^ The target hash (leaf digest)- -> TreeSize -- ^ The tree size- -> MerkleHashTrees inp ha- -> Maybe (InclusionProof ha)+generateInclusionProof+ :: Digest ha+ -- ^ The target hash (leaf digest)+ -> TreeSize+ -- ^ The tree size+ -> MerkleHashTrees inp ha+ -> Maybe (InclusionProof ha) generateInclusionProof h tsiz (MerkleHashTrees _ _ htdb idb) = do ht <- IntMap.lookup tsiz htdb i <- Map.lookup h idb- if i < tsiz then do- let digests = reverse $ path i ht- Just $ InclusionProof i tsiz digests- else- Nothing+ if i < tsiz+ then do+ let digests = reverse $ path i ht+ Just $ InclusionProof i tsiz digests+ else+ Nothing where path m (Node _ _ _ l r)- | m <= idxr l = value r : path m l- | otherwise = value l : path m r+ | m <= idxr l = value r : path m l+ | otherwise = value l : path m r path _ _ = [] -- | Verifying 'InclusionProof' at the client side.@@ -273,73 +296,82 @@ -- >>> let Just rootDigest = digest treeSize mht -- >>> verifyInclusionProof defaultSettings leafDigest rootDigest proof -- True-verifyInclusionProof :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha- -> Digest ha -- ^ The target hash (leaf digest)- -> Digest ha -- ^ Merkle Tree Hash (root digest) for the tree size- -> InclusionProof ha -- ^ InclusionProof of the target- -> Bool+verifyInclusionProof+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha+ -> Digest ha+ -- ^ The target hash (leaf digest)+ -> Digest ha+ -- ^ Merkle Tree Hash (root digest) for the tree size+ -> InclusionProof ha+ -- ^ InclusionProof of the target+ -> Bool verifyInclusionProof set leafDigest rootDigest (InclusionProof idx tsiz pps)- | idx >= tsiz = False- | otherwise = verify (idx,tsiz - 1) leafDigest pps+ | idx >= tsiz = False+ | otherwise = verify (idx, tsiz - 1) leafDigest pps where- verify (_,sn) r [] = sn == 0 && r == rootDigest- verify (_,0) _ _ = False- verify fsn@(fn,sn) r (p:ps)- | fn `testBit` 0 || fn == sn = let r' = hash2 set p r- fsn' = shiftR1 $ untilSet fsn- in verify fsn' r' ps- | otherwise = let r' = hash2 set r p- fsn' = shiftR1 fsn- in verify fsn' r' ps+ verify (_, sn) r [] = sn == 0 && r == rootDigest+ verify (_, 0) _ _ = False+ verify fsn@(fn, sn) r (p : ps)+ | fn `testBit` 0 || fn == sn =+ let r' = hash2 set p r+ fsn' = shiftR1 $ untilSet fsn+ in verify fsn' r' ps+ | otherwise =+ let r' = hash2 set r p+ fsn' = shiftR1 fsn+ in verify fsn' r' ps ---------------------------------------------------------------- -- | The type for consistency proof.-data ConsistencyProof ha = ConsistencyProof {- -- | The first hash tree size.- firstTreeSize :: !TreeSize- -- | The second hash tree size.- , secondTreeSize :: !TreeSize- -- | A list of digest for consistency.- , consistency :: ![Digest ha]- } deriving (Eq, Show)+data ConsistencyProof ha = ConsistencyProof+ { firstTreeSize :: !TreeSize+ -- ^ The first hash tree size.+ , secondTreeSize :: !TreeSize+ -- ^ The second hash tree size.+ , consistency :: ![Digest ha]+ -- ^ A list of digest for consistency.+ }+ deriving (Eq, Show) -- | The default value for 'ConsistencyProof' just to create a new value. defaultConsistencyProof :: ConsistencyProof ha-defaultConsistencyProof = ConsistencyProof {- firstTreeSize = 1- , secondTreeSize = 2- , consistency = []- }+defaultConsistencyProof =+ ConsistencyProof+ { firstTreeSize = 1+ , secondTreeSize = 2+ , consistency = []+ } -- | Generating 'ConsistencyProof' for the target at the server side.-generateConsistencyProof :: TreeSize -> TreeSize -> MerkleHashTrees inp ha -> Maybe (ConsistencyProof ha)+generateConsistencyProof+ :: TreeSize -> TreeSize -> MerkleHashTrees inp ha -> Maybe (ConsistencyProof ha) generateConsistencyProof m n (MerkleHashTrees _ _ htdb _)- | m < 0 || n < 0 = Nothing- | m > n = Nothing- | m == 0 = do- htn <- IntMap.lookup n htdb- return $ ConsistencyProof m n [value htn]- | otherwise = do- htm <- IntMap.lookup m htdb- htn <- IntMap.lookup n htdb- let digests = prove htm htn True- return $ ConsistencyProof m n digests+ | m < 0 || n < 0 = Nothing+ | m > n = Nothing+ | m == 0 = do+ htn <- IntMap.lookup n htdb+ return $ ConsistencyProof m n [value htn]+ | otherwise = do+ htm <- IntMap.lookup m htdb+ htn <- IntMap.lookup n htdb+ let digests = prove htm htn True+ return $ ConsistencyProof m n digests where prove htm htn flag- | idxl htm == idxl htn && idxr htm == idxr htn- = if flag then [] else [value htm]- prove htm@(Leaf _ _ _) (Node _ _ _ ln rn) flag- = prove htm ln flag ++ [value rn]+ | idxl htm == idxl htn && idxr htm == idxr htn =+ if flag then [] else [value htm]+ prove htm@(Leaf _ _ _) (Node _ _ _ ln rn) flag =+ prove htm ln flag ++ [value rn] prove htm@(Node _ midxl midxr lm rm) (Node _ nidxl nidxr ln rn) flag- | sizm <= k = prove htm ln flag ++ [value rn]- | otherwise = prove rm rn False ++ [value lm]+ | sizm <= k = prove htm ln flag ++ [value rn]+ | otherwise = prove rm rn False ++ [value lm] where sizm = midxr - midxl + 1 sizn = nidxr - nidxl + 1 k = maxPowerOf2 (sizn - 1) -- e.g. if 8, take 4.- prove _ _ _ = error "generateConsistencyProof:prove"+ prove _ _ _ = error "generateConsistencyProof:prove" -- | Verifying 'ConsistencyProof' at the client side. --@@ -350,37 +382,40 @@ -- >>> let Just proof = generateConsistencyProof m n mht1 -- >>> verifyConsistencyProof defaultSettings digestM digestN proof -- True-verifyConsistencyProof :: (ByteArrayAccess inp, HashAlgorithm ha)- => Settings inp ha- -> Digest ha -- start- -> Digest ha -- end- -> ConsistencyProof ha- -> Bool+verifyConsistencyProof+ :: (ByteArrayAccess inp, HashAlgorithm ha)+ => Settings inp ha+ -> Digest ha -- start+ -> Digest ha -- end+ -> ConsistencyProof ha+ -> Bool verifyConsistencyProof set firstHash secondHash (ConsistencyProof first second path)- | first == 0 = case path of- [c] -> secondHash == c- _ -> False- | first == second = null path && firstHash == secondHash- | otherwise = case path' of- [] -> False- c:cs -> verify (untilNotSet (first - 1, second - 1)) c c cs -- fixme:cs+ | first == 0 = case path of+ [c] -> secondHash == c+ _ -> False+ | first == second = null path && firstHash == secondHash+ | otherwise = case path' of+ [] -> False+ c : cs -> verify (untilNotSet (first - 1, second - 1)) c c cs -- fixme:cs where path'- | isPowerOf2 first = firstHash : path- | otherwise = path- verify _ fr sr [] = fr == firstHash && sr == secondHash- verify (_,0) _ _ _ = error "verifyConsistencyProof:verify"- verify fsn@(fn,sn) fr sr (c:cs)- | fn `testBit` 0 || fn == sn = let fr' = hash2 set c fr- sr' = hash2 set c sr- fsn'- | not (fn `testBit` 0) = untilSet fsn- | otherwise = fsn- fsn'' = shiftR1 fsn'- in verify fsn'' fr' sr' cs- | otherwise = let sr' = hash2 set sr c- fsn' = shiftR1 fsn- in verify fsn' fr sr' cs+ | isPowerOf2 first = firstHash : path+ | otherwise = path+ verify _ fr sr [] = fr == firstHash && sr == secondHash+ verify (_, 0) _ _ _ = error "verifyConsistencyProof:verify"+ verify fsn@(fn, sn) fr sr (c : cs)+ | fn `testBit` 0 || fn == sn =+ let fr' = hash2 set c fr+ sr' = hash2 set c sr+ fsn'+ | not (fn `testBit` 0) = untilSet fsn+ | otherwise = fsn+ fsn'' = shiftR1 fsn'+ in verify fsn'' fr' sr' cs+ | otherwise =+ let sr' = hash2 set sr c+ fsn' = shiftR1 fsn+ in verify fsn' fr sr' cs ---------------------------------------------------------------- @@ -393,16 +428,16 @@ maxPowerOf2 :: Int -> Int maxPowerOf2 n = 2 ^ (width n - 1) -shiftR1 :: (Int,Int) -> (Int,Int)-shiftR1 (x,y) = (x `unsafeShiftR` 1, y `unsafeShiftR` 1)+shiftR1 :: (Int, Int) -> (Int, Int)+shiftR1 (x, y) = (x `unsafeShiftR` 1, y `unsafeShiftR` 1) -untilNotSet :: (Int,Int) -> (Int,Int)-untilNotSet fsn@(fn,_)- | fn `testBit` 0 = untilNotSet $ shiftR1 fsn- | otherwise = fsn+untilNotSet :: (Int, Int) -> (Int, Int)+untilNotSet fsn@(fn, _)+ | fn `testBit` 0 = untilNotSet $ shiftR1 fsn+ | otherwise = fsn -untilSet :: (Int,Int) -> (Int,Int)-untilSet fsn@(fn,_)- | fn == 0 = fsn- | fn `testBit` 0 = fsn- | otherwise = untilSet $ shiftR1 fsn+untilSet :: (Int, Int) -> (Int, Int)+untilSet fsn@(fn, _)+ | fn == 0 = fsn+ | fn `testBit` 0 = fsn+ | otherwise = untilSet $ shiftR1 fsn
hash-tree.cabal view
@@ -1,47 +1,53 @@-Name: hash-tree-Version: 0.0.1-Author: Kazu Yamamoto <kazu@iij.ad.jp>-Maintainer: Kazu Yamamoto <kazu@iij.ad.jp>-License: BSD3-License-File: LICENSE-Synopsis: Merkle Hash Tree-Description: Purely functional Merkle hash tree which- implements appe nd-only logs and- provides both inclusion proof and consistency proof.-Category: Data-Cabal-Version: >= 1.10-Build-Type: Simple+cabal-version: >=1.10+name: hash-tree+version: 0.1.0+license: BSD3+license-file: LICENSE+maintainer: Kazu Yamamoto <kazu@iij.ad.jp>+author: Kazu Yamamoto <kazu@iij.ad.jp>+synopsis: Merkle Hash Tree+description:+ Purely functional Merkle hash tree which+ implements appe nd-only logs and+ provides both inclusion proof and consistency proof. -Library- Default-Language: Haskell2010- GHC-Options: -Wall- Exposed-Modules: Data.HashTree- Other-Modules: Data.HashTree.Internal- Build-Depends: base >= 4 && < 5- , bytestring- , containers- , crypton- , memory+category: Data+build-type: Simple -Test-Suite spec- Type: exitcode-stdio-1.0- Default-Language: Haskell2010- HS-Source-Dirs: test, .- Ghc-Options: -Wall- Main-Is: Spec.hs- Other-Modules: HashTreeSpec- Data.HashTree- Data.HashTree.Internal- Build-Depends: base >= 4 && < 5- , QuickCheck- , bytestring- , base64-bytestring- , containers- , crypton- , hspec- , memory+source-repository head+ type: git+ location: https://github.com/kazu-yamamoto/hash-tree -Source-Repository head- Type: git- Location: https://github.com/kazu-yamamoto/hash-tree+library+ exposed-modules: Data.HashTree+ other-modules: Data.HashTree.Internal+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >=4 && <5,+ bytestring,+ containers,+ crypton >=1.1.0 && <1.2,+ ram +test-suite spec+ type: exitcode-stdio-1.0+ main-is: Spec.hs+ hs-source-dirs: test .+ other-modules:+ HashTreeSpec+ Data.HashTree+ Data.HashTree.Internal++ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >=4 && <5,+ QuickCheck,+ bytestring,+ base64-bytestring,+ containers,+ crypton,+ hash-tree,+ hspec,+ ram
test/HashTreeSpec.hs view
@@ -1,5 +1,5 @@-{-# OPTIONS_GHC -fno-warn-orphans #-} {-# LANGUAGE OverloadedStrings #-}+{-# OPTIONS_GHC -fno-warn-orphans #-} module HashTreeSpec where @@ -16,8 +16,7 @@ import Test.Hspec.QuickCheck import Test.QuickCheck --newtype Input = Input [ByteString] deriving Show -- non empty list+newtype Input = Input [ByteString] deriving (Show) -- non empty list instance Arbitrary ByteString where arbitrary = BS.pack <$> listOf arbitrary -- Gen Word8@@ -33,12 +32,12 @@ let mht = add (bs :: ByteString) $ empty set h1 = snd $ info mht h2 = hash1 set bs- in h1 == h2+ in h1 == h2 describe "fromList" $ do prop "create a perfectly branched tree" $ \(Input bss) -> let Just ht = currentHead $ fromList set bss ht' = toHashTree set $ nub bss- in ht == ht'+ in ht == ht' describe "verifyInclusionProof" $ do it "can verify the certificate transparency" $ verifyInclusionProof set dl d2 iProof `shouldBe` True@@ -48,15 +47,15 @@ len = length bss x0' = adjust x0 len y0' = adjust y0 len- (i,tsiz)- | x0' < y0' = (x0',y0')- | x0' > y0' = (y0',x0')- | otherwise = (x0',y0'+1)+ (i, tsiz)+ | x0' < y0' = (x0', y0')+ | x0' > y0' = (y0', x0')+ | otherwise = (x0', y0' + 1) target = bss !! i leafDigest = hash1 set target proof = fromJust $ generateInclusionProof leafDigest tsiz mht Just rootDigest = digest tsiz mht- in verifyInclusionProof set leafDigest rootDigest proof+ in verifyInclusionProof set leafDigest rootDigest proof describe "verifyConsistencyProof" $ do it "can verify the certificate transparency" $ verifyConsistencyProof set d1 d2 cProof `shouldBe` True@@ -65,16 +64,16 @@ siz = size mht m0' = adjust m0 siz n0' = adjust n0 siz- (m,n) = if m0' <= n0' then (m0',n0') else (n0',m0')+ (m, n) = if m0' <= n0' then (m0', n0') else (n0', m0') proof = fromJust $ generateConsistencyProof m n mht Just dm = digest m mht Just dn = digest n mht- in verifyConsistencyProof set dm dn proof+ in verifyConsistencyProof set dm dn proof adjust :: Int -> Int -> Int adjust x b- | x < 0 = negate x `mod` b- | otherwise = x `mod` b+ | x < 0 = negate x `mod` b+ | otherwise = x `mod` b toDigest :: ByteString -> Digest SHA256 toDigest x = d@@ -82,7 +81,6 @@ Right r = decode x Just d = digestFromByteString r - {- % wget https://ct.googleapis.com/icarus/ct/v1/get-sth {"tree_size":129596132,"timestamp":1508198131197,"sha256_root_hash":"qyJv/TObheataX8uFjAJsR+dJtJgNlfjzTe5CX8Ej2s=","tree_head_signature":"BAMASDBGAiEAhtcpfpVSKRuZOxEMpPRRiu5nPdd8UL3JnQBk23Zrk/ACIQD+n4YSigh3o1KaJvBTvJkcmq2CW5QtrIBdI2oDiItN1A=="}@@ -104,31 +102,32 @@ cProof :: ConsistencyProof SHA256 cProof = ConsistencyProof 129596132 129721434 cs where- bs = ["5mrKRX9GRLriSIAtkX0kdvlnjt/f+P0vTrhmzOdhnzs="- ,"VEqL3Z55VZTVRp45WX7gTdcwxOorltn+uCQpHjv9rjE="- ,"2Euj4VXixjEAGj9p23OMo+ciB1tQ2KXH97TkWgcZLpI="- ,"rG0l6AHdk3TRkgAnwTK1Ys5kU7uuKRkMQSkrES0ocj0="- ,"JSxii5BAGCuwifRNIgIsarVA/aSC/QJNv4kfT9zii3Y="- ,"WPaErDHN/lYCuv8TsvosmAsIDbEOfPNZ/LxqLvuQcdY="- ,"HjN1fCoS6OYw8VH+DAcQPQkCjksWljkvr3AJiZTsi6Y="- ,"liuu+DeQohOzAyQadR3imE0SLo8pSsv9K0Y9f1dGrwA="- ,"oUQV+oip0wozcwv4mmMv4MrP545ugwXDIMU6HkZrfl0="- ,"V9BPc7aq1Sq1XwFV3gMx7/9Wv+8l/81S5Gb+bDriRZE="- ,"h3PJZDxVUsGMPBMEaJsQnqAVjlpuxUPGAUfYCY6TkWY="- ,"Rj09QnLzZ2MmyKjJYkcSO8Ko6lGhgwrnOydn+RdHdeI="- ,"Dc7oYAljc9VEYI8JuvYVyJtTHP8uW7igIKVqnWXgvFs="- ,"tJfBVa+YE0GK8T1L74hkkGmT3QO+mznMf+XrKnS3YOE="- ,"V9uRJUhCpCMwss1i4c85X5ceJnNePXdjAVrxtU6EezY="- ,"nf6Yq8xIs56hgor/mk30dvpaUO1/1w+MUlz8thiEb3o="- ,"SEVW3kh8HQ9Za+LjCoGaAkbbUfYmiwNs3SDasWKS6xo="- ,"96r7XxdWTPAZSygfov9mTTd4Gs6chZfdkznd8HAmzKc="- ,"t6OBvH84uFTwEubekO8rdcv+AlqPcpuZX9pwLYopKGg="- ,"nl6nrmkzk5qSYBiUHN609SD8IH3HuTPYR6r1YWKtWag="- ,"NbPA38XBZUXC5ca/cNcU/mNhq31qg2okTS3kJdptnxg="- ,"Ur4mOpiyDl1Zq/MH/SGszUlBP7jmOfupNVodMT6Mg2M="- ,"LUTvZyrtuEoSL7PNqR2Iv2FbcbtI5lQrq5/97sMFIsU="- ,"Bh+FIkHuIdFAcvCYOTlkKMxR15aDaaT9UlUsrCeuLUY="- ]+ bs =+ [ "5mrKRX9GRLriSIAtkX0kdvlnjt/f+P0vTrhmzOdhnzs="+ , "VEqL3Z55VZTVRp45WX7gTdcwxOorltn+uCQpHjv9rjE="+ , "2Euj4VXixjEAGj9p23OMo+ciB1tQ2KXH97TkWgcZLpI="+ , "rG0l6AHdk3TRkgAnwTK1Ys5kU7uuKRkMQSkrES0ocj0="+ , "JSxii5BAGCuwifRNIgIsarVA/aSC/QJNv4kfT9zii3Y="+ , "WPaErDHN/lYCuv8TsvosmAsIDbEOfPNZ/LxqLvuQcdY="+ , "HjN1fCoS6OYw8VH+DAcQPQkCjksWljkvr3AJiZTsi6Y="+ , "liuu+DeQohOzAyQadR3imE0SLo8pSsv9K0Y9f1dGrwA="+ , "oUQV+oip0wozcwv4mmMv4MrP545ugwXDIMU6HkZrfl0="+ , "V9BPc7aq1Sq1XwFV3gMx7/9Wv+8l/81S5Gb+bDriRZE="+ , "h3PJZDxVUsGMPBMEaJsQnqAVjlpuxUPGAUfYCY6TkWY="+ , "Rj09QnLzZ2MmyKjJYkcSO8Ko6lGhgwrnOydn+RdHdeI="+ , "Dc7oYAljc9VEYI8JuvYVyJtTHP8uW7igIKVqnWXgvFs="+ , "tJfBVa+YE0GK8T1L74hkkGmT3QO+mznMf+XrKnS3YOE="+ , "V9uRJUhCpCMwss1i4c85X5ceJnNePXdjAVrxtU6EezY="+ , "nf6Yq8xIs56hgor/mk30dvpaUO1/1w+MUlz8thiEb3o="+ , "SEVW3kh8HQ9Za+LjCoGaAkbbUfYmiwNs3SDasWKS6xo="+ , "96r7XxdWTPAZSygfov9mTTd4Gs6chZfdkznd8HAmzKc="+ , "t6OBvH84uFTwEubekO8rdcv+AlqPcpuZX9pwLYopKGg="+ , "nl6nrmkzk5qSYBiUHN609SD8IH3HuTPYR6r1YWKtWag="+ , "NbPA38XBZUXC5ca/cNcU/mNhq31qg2okTS3kJdptnxg="+ , "Ur4mOpiyDl1Zq/MH/SGszUlBP7jmOfupNVodMT6Mg2M="+ , "LUTvZyrtuEoSL7PNqR2Iv2FbcbtI5lQrq5/97sMFIsU="+ , "Bh+FIkHuIdFAcvCYOTlkKMxR15aDaaT9UlUsrCeuLUY="+ ] cs = map toDigest bs {-@@ -139,10 +138,40 @@ dl :: Digest SHA256 dl = hash1 defaultSettings r where- Right r = decode "AAAAAAFexROk9wAAAAUdMIIFGTCCBAGgAwIBAgISBC/2U32dBHf/8H9aIod2qqPFMA0GCSqGSIb3DQEBCwUAMEoxCzAJBgNVBAYTAlVTMRYwFAYDVQQKEw1MZXQncyBFbmNyeXB0MSMwIQYDVQQDExpMZXQncyBFbmNyeXB0IEF1dGhvcml0eSBYMzAeFw0xNzA5MjcxOTQzMDBaFw0xNzEyMjYxOTQzMDBaMBsxGTAXBgNVBAMTEGdlbS1qZXdlbGVycy5jb20wggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQDB61H4Kvny8rX0gBuvPciX9VpPzfkdYHjRwmZLU3uj3awfN+4qouO7ipz9Cyz1saCI53NXisHr3lttxAF1ISnidvywgRyaO9G0BVAn6Tl5zarOhwrf56wopfyEGaHfpyO8dCV5nfNWM99gbmrcJgWqs5/7Np9L+Y0ZMah751X6oZsJqKSs6FCUbAtyeAhXBQMuSOqkd85nObSpnf2W0CAfWYy66VPbDL8OAhq0A/3U+gh9ThWCAPPn9pVghazBKsSL+c1KW84xsXuHWkkgLjJ3f/oL9FPTzNBfqYzzeuAVAEwazYXPyEu5SlbdqzDi1Lesp0+2yoMO9h7MWy9Mom05AgMBAAGjggImMIICIjAOBgNVHQ8BAf8EBAMCBaAwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMAwGA1UdEwEB/wQCMAAwHQYDVR0OBBYEFDQaIW5tEaFbKN9qRmVdZEk2eB4GMB8GA1UdIwQYMBaAFKhKamMEfd265tE5t6ZFZe/zqOyhMG8GCCsGAQUFBwEBBGMwYTAuBggrBgEFBQcwAYYiaHR0cDovL29jc3AuaW50LXgzLmxldHNlbmNyeXB0Lm9yZzAvBggrBgEFBQcwAoYjaHR0cDovL2NlcnQuaW50LXgzLmxldHNlbmNyeXB0Lm9yZy8wMQYDVR0RBCowKIIQZ2VtLWpld2VsZXJzLmNvbYIUd3d3LmdlbS1qZXdlbGVycy5jb20wgf4GA1UdIASB9jCB8zAIBgZngQwBAgEwgeYGCysGAQQBgt8TAQEBMIHWMCYGCCsGAQUFBwIBFhpodHRwOi8vY3BzLmxldHNlbmNyeXB0Lm9yZzCBqwYIKwYBBQUHAgIwgZ4MgZtUaGlzIENlcnRpZmljYXRlIG1heSBvbmx5IGJlIHJlbGllZCB1cG9uIGJ5IFJlbHlpbmcgUGFydGllcyBhbmQgb25seSBpbiBhY2NvcmRhbmNlIHdpdGggdGhlIENlcnRpZmljYXRlIFBvbGljeSBmb3VuZCBhdCBodHRwczovL2xldHNlbmNyeXB0Lm9yZy9yZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAMMIZaoRMUdLpIyc7TmFmjz8h9q24xnwY04J61CALDVV8c8IjzRwuheqcCzOmBAfI4ejBnAb3wxIYIq/FlYmWbLHEdpOviPFgyV6uskNGGAyEWjU+ah3E9NXxJ2+/h/GmDOLk3D6aXeLyFpZr1nAhl9+Sr+Gj/gWijiAhpKKT/al73u4ZG8exhsRlfTr84Mtgn29NwolMAQ5anMuLgk3d7YTOpsi602vQTyEAj5G7SUryBvf+lYhDvyZwLkbEqaQnuUvHu2uLGbtRb002CAptZeqTLQ84hIjS1JJ5YZgdEtPlbUqduuR6CB3nIA6cKdLKyoTw3Yxwh9Xeowe6OEVEIwAA"+ Right r =+ decode+ "AAAAAAFexROk9wAAAAUdMIIFGTCCBAGgAwIBAgISBC/2U32dBHf/8H9aIod2qqPFMA0GCSqGSIb3DQEBCwUAMEoxCzAJBgNVBAYTAlVTMRYwFAYDVQQKEw1MZXQncyBFbmNyeXB0MSMwIQYDVQQDExpMZXQncyBFbmNyeXB0IEF1dGhvcml0eSBYMzAeFw0xNzA5MjcxOTQzMDBaFw0xNzEyMjYxOTQzMDBaMBsxGTAXBgNVBAMTEGdlbS1qZXdlbGVycy5jb20wggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQDB61H4Kvny8rX0gBuvPciX9VpPzfkdYHjRwmZLU3uj3awfN+4qouO7ipz9Cyz1saCI53NXisHr3lttxAF1ISnidvywgRyaO9G0BVAn6Tl5zarOhwrf56wopfyEGaHfpyO8dCV5nfNWM99gbmrcJgWqs5/7Np9L+Y0ZMah751X6oZsJqKSs6FCUbAtyeAhXBQMuSOqkd85nObSpnf2W0CAfWYy66VPbDL8OAhq0A/3U+gh9ThWCAPPn9pVghazBKsSL+c1KW84xsXuHWkkgLjJ3f/oL9FPTzNBfqYzzeuAVAEwazYXPyEu5SlbdqzDi1Lesp0+2yoMO9h7MWy9Mom05AgMBAAGjggImMIICIjAOBgNVHQ8BAf8EBAMCBaAwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMAwGA1UdEwEB/wQCMAAwHQYDVR0OBBYEFDQaIW5tEaFbKN9qRmVdZEk2eB4GMB8GA1UdIwQYMBaAFKhKamMEfd265tE5t6ZFZe/zqOyhMG8GCCsGAQUFBwEBBGMwYTAuBggrBgEFBQcwAYYiaHR0cDovL29jc3AuaW50LXgzLmxldHNlbmNyeXB0Lm9yZzAvBggrBgEFBQcwAoYjaHR0cDovL2NlcnQuaW50LXgzLmxldHNlbmNyeXB0Lm9yZy8wMQYDVR0RBCowKIIQZ2VtLWpld2VsZXJzLmNvbYIUd3d3LmdlbS1qZXdlbGVycy5jb20wgf4GA1UdIASB9jCB8zAIBgZngQwBAgEwgeYGCysGAQQBgt8TAQEBMIHWMCYGCCsGAQUFBwIBFhpodHRwOi8vY3BzLmxldHNlbmNyeXB0Lm9yZzCBqwYIKwYBBQUHAgIwgZ4MgZtUaGlzIENlcnRpZmljYXRlIG1heSBvbmx5IGJlIHJlbGllZCB1cG9uIGJ5IFJlbHlpbmcgUGFydGllcyBhbmQgb25seSBpbiBhY2NvcmRhbmNlIHdpdGggdGhlIENlcnRpZmljYXRlIFBvbGljeSBmb3VuZCBhdCBodHRwczovL2xldHNlbmNyeXB0Lm9yZy9yZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAMMIZaoRMUdLpIyc7TmFmjz8h9q24xnwY04J61CALDVV8c8IjzRwuheqcCzOmBAfI4ejBnAb3wxIYIq/FlYmWbLHEdpOviPFgyV6uskNGGAyEWjU+ah3E9NXxJ2+/h/GmDOLk3D6aXeLyFpZr1nAhl9+Sr+Gj/gWijiAhpKKT/al73u4ZG8exhsRlfTr84Mtgn29NwolMAQ5anMuLgk3d7YTOpsi602vQTyEAj5G7SUryBvf+lYhDvyZwLkbEqaQnuUvHu2uLGbtRb002CAptZeqTLQ84hIjS1JJ5YZgdEtPlbUqduuR6CB3nIA6cKdLKyoTw3Yxwh9Xeowe6OEVEIwAA" iProof :: InclusionProof SHA256 iProof = InclusionProof 120000000 129721434 is where- bs = ["xNXDvcL4JYFTwHXfnl0an0vyCjS0am5+B8dxDozc5ag=","LJc7lPt79J4pgFqY0hbGYXZi401EnFVix2vFUSovrB8=","QFcF13awbePeLAqSfFoNB6cYYU40wwY7aLYQXk/ss/A=","Wlc9EJxIODGOKavf7zXfPOrymuWwviwGUI8K6h9EBFQ=","aigt2QVYyMjXSLFAhuaEvBmqctsFVKFZEgtJYl/gPL8=","DALuGNF8WzgEgdYT34KFCzbRlV+wx5Ie1jrUsfJS+Jo=","wfZyGm8U+u587alYY91O5sOCVVMPqNA1wwst8/CLsWA=","frRFNtjphdfOKw0X1I1AZfU6yuCMZ+/bC9sHXg6L4DQ=","5DgE84Ns18cCD9zOiiPUuUP17nOmxMm4copkw2MHY9g=","ggacmAKa8hnTxehF0WUAbknaQk1Ks6c33x2g/zOVWgw=","I1YeaNL1rb0YNDCb7Xe9VPosJKP0fv3msScVnNsn4PA=","BPVDHS1+mcuIEsShBg19U6UCwIQKJwRZeXIECFA6zcw=","7smS/3DRbnKci59UoBg7xDf+NlAVGAZ2qtG4ILaAK/Q=","75SJNIAzyepGCUnfvUTVrZSddSfWaSxxXXmBiHewa8g=","YxHvS/I+2i1yJLilSU/ZKjyr5jc5ABhuU4Wh6H+oBUY=","7DBov9qK6s/uy8g0iL//5A97ZAELOSE6SjGMGVBK8dY=","JsXCAk0Ztn8YZFmyfUkuJYzAzlV70D+mefthbBvRjaY=","YHBP2MPkXLUeRIMQTdQ9LVxolKbn1onla0Uedgp1x+Y=","yE4z+aQ1n/7sLJRG8jM5xKLq+JlHg3GoN3ApPovnh/o=","fwU2Yg7p+8ACX6v3e7xiJGwDeYo0b+33hbxy+KMdMfA=","5gj0c1LVruisvtT8VA1J9IeWyRaTf0+dwuLnamseTl8=","HQec1yNY1oQtctj/ZfpEtDZZf3aT19Qdo4aaBPvaT+I=","FPtmqvOXlhE5gi/rc/sfWQpvLT7tPfHKJiSCEgmf3Hk=","EtTWrgka0wMLdqJ4oFojyDzjsuLoSyZpyzKzff+yFxU=","Ur4mOpiyDl1Zq/MH/SGszUlBP7jmOfupNVodMT6Mg2M=","LUTvZyrtuEoSL7PNqR2Iv2FbcbtI5lQrq5/97sMFIsU=","Bh+FIkHuIdFAcvCYOTlkKMxR15aDaaT9UlUsrCeuLUY="]+ bs =+ [ "xNXDvcL4JYFTwHXfnl0an0vyCjS0am5+B8dxDozc5ag="+ , "LJc7lPt79J4pgFqY0hbGYXZi401EnFVix2vFUSovrB8="+ , "QFcF13awbePeLAqSfFoNB6cYYU40wwY7aLYQXk/ss/A="+ , "Wlc9EJxIODGOKavf7zXfPOrymuWwviwGUI8K6h9EBFQ="+ , "aigt2QVYyMjXSLFAhuaEvBmqctsFVKFZEgtJYl/gPL8="+ , "DALuGNF8WzgEgdYT34KFCzbRlV+wx5Ie1jrUsfJS+Jo="+ , "wfZyGm8U+u587alYY91O5sOCVVMPqNA1wwst8/CLsWA="+ , "frRFNtjphdfOKw0X1I1AZfU6yuCMZ+/bC9sHXg6L4DQ="+ , "5DgE84Ns18cCD9zOiiPUuUP17nOmxMm4copkw2MHY9g="+ , "ggacmAKa8hnTxehF0WUAbknaQk1Ks6c33x2g/zOVWgw="+ , "I1YeaNL1rb0YNDCb7Xe9VPosJKP0fv3msScVnNsn4PA="+ , "BPVDHS1+mcuIEsShBg19U6UCwIQKJwRZeXIECFA6zcw="+ , "7smS/3DRbnKci59UoBg7xDf+NlAVGAZ2qtG4ILaAK/Q="+ , "75SJNIAzyepGCUnfvUTVrZSddSfWaSxxXXmBiHewa8g="+ , "YxHvS/I+2i1yJLilSU/ZKjyr5jc5ABhuU4Wh6H+oBUY="+ , "7DBov9qK6s/uy8g0iL//5A97ZAELOSE6SjGMGVBK8dY="+ , "JsXCAk0Ztn8YZFmyfUkuJYzAzlV70D+mefthbBvRjaY="+ , "YHBP2MPkXLUeRIMQTdQ9LVxolKbn1onla0Uedgp1x+Y="+ , "yE4z+aQ1n/7sLJRG8jM5xKLq+JlHg3GoN3ApPovnh/o="+ , "fwU2Yg7p+8ACX6v3e7xiJGwDeYo0b+33hbxy+KMdMfA="+ , "5gj0c1LVruisvtT8VA1J9IeWyRaTf0+dwuLnamseTl8="+ , "HQec1yNY1oQtctj/ZfpEtDZZf3aT19Qdo4aaBPvaT+I="+ , "FPtmqvOXlhE5gi/rc/sfWQpvLT7tPfHKJiSCEgmf3Hk="+ , "EtTWrgka0wMLdqJ4oFojyDzjsuLoSyZpyzKzff+yFxU="+ , "Ur4mOpiyDl1Zq/MH/SGszUlBP7jmOfupNVodMT6Mg2M="+ , "LUTvZyrtuEoSL7PNqR2Iv2FbcbtI5lQrq5/97sMFIsU="+ , "Bh+FIkHuIdFAcvCYOTlkKMxR15aDaaT9UlUsrCeuLUY="+ ] is = map toDigest bs