pedersen-commitment 0.1.0 → 0.2.0

raw patch · 7 files changed

+267/−42 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• ChangeLog.md +10/−0
• LICENSE +1/−1
• README.md +28/−13
• pedersen-commitment.cabal +8/−14
• src/Pedersen.hs +8/−8
• src/VectorPedersen.hs +160/−0
• tests/Main.hs +52/−6

@@ -0,0 +1,10 @@+# Revision history for pedersen-commitment++## 0.2++* Added vector Pedersen commitments.++## 0.1++* First version.+

@@ -1,6 +1,6 @@ MIT License -Copyright (c) 2017 Adjoint Inc.+Copyright (c) 2017-2018 Adjoint Inc.  Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal

@@ -26,7 +26,7 @@ example :: IO Bool example = do   -- Setup commitment parameters-  (a, cp) <- setup 256 +  (a, cp) <- setup 256    -- Commit to the message using paramaters: Com(msg, cp)   let msg = 0xCAFEBEEF@@ -57,15 +57,15 @@  ### Pedersen Commitments (Elliptic Curves) -A more efficient implementation of the Pedersen Commitment scheme arises from -Elliptic Curve Cryptography (ECC) which is based on the algebraic structure of +A more efficient implementation of the Pedersen Commitment scheme arises from+Elliptic Curve Cryptography (ECC) which is based on the algebraic structure of elliptic curves over finite (prime) fields. Using ECC, the commitment scheme-computations require fewer bits and as a result yields a much faster commitment -phase. +computations require fewer bits and as a result yields a much faster commitment+phase. -Given a secure elliptic curve (e.g. secp256k1), a Pedersen -commitment can be implemented using the same interface as usual but instead -of prime field modular exponentiation, EC point multiplication and addition +Given a secure elliptic curve (e.g. secp256k1), a Pedersen+commitment can be implemented using the same interface as usual but instead+of prime field modular exponentiation, EC point multiplication and addition are used. The use of EC Pedersen commitments is almost exactly the same as the general prime field implementation: @@ -73,7 +73,7 @@ example :: IO Bool example = do   -- Setup commitment parameters-  (a, cp) <- ecSetup Nothing -- SECP256k1 is used by default +  (a, cp) <- ecSetup Nothing -- SECP256k1 is used by default    -- Commit to the message using paramaters: Com(msg, cp)   let msg = 0xCAFEBEEF@@ -96,11 +96,27 @@ Commit(x,r) + n = Commit(x + n,r) ``` +### Vector Pedersen Commitments (Elliptic Curves) +The Vector Pedersen Commitment is a more powerful variant of the previous Pedersen commitment. It commits to a vector **v** instead of a scalar. This extended form is defined as:++ C' = rH + (v<sub>1</sub>G<sub>1</sub> + v<sub>2</sub>G<sub>2</sub> + ...  + v<sub>n</sub>G<sub>n</sub>)++where v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>n</sub> are scalars that multiply each point G<sub>1</sub>, G<sub>2</sub>, ..., G<sub>n</sub> respectively in the elliptic curve. It is the result of the dot product between two vectors **v** and **G** of arbitrary large number of elements. Each element G<sub>i</sub> is a NUMS ("Nothing Up My Sleeve") generator that can be created using a hash function H such that `H(encode(G) || i)` and a "coerce-hash-to-point" function to construct the point from the randomized hash value.++The new commitment C' is still a point in the curve and a valid Pedersen commitment. It also holds the hiding and binding properties and the same additive homomorphic properties as the Pedersen Commitment:+```+Commit(v, r1) + Commit(w, r2) = Commit(w + v, r1 + r2)+```+```+Commit(v, r) + w = Commit(v + w, r)+```+where v and w are now vectors.+ **References**: -1. Pedersen, Torben Pryds. "Non-interactive and information-theoretic secure verifiable secret sharing." Annual International Cryptology Conference. Springer Berlin Heidelberg, 1991.  APA	-2. Liskov, Moses, et al. "Mutually independent commitments." International Conference on the Theory and Application of Cryptology and Information Security. Springer Berlin Heidelberg, 2001.  APA	+1. Pedersen, Torben Pryds. "Non-interactive and information-theoretic secure verifiable secret sharing." Annual International Cryptology Conference. Springer Berlin Heidelberg, 1991.  APA+2. Liskov, Moses, et al. "Mutually independent commitments." International Conference on the Theory and Application of Cryptology and Information Security. Springer Berlin Heidelberg, 2001.  APA 3. Blum, Manuel, and Silvio Micali. "How to generate cryptographically strong sequences of pseudorandom bits." SIAM journal on Computing 13.4 (1984): 850-864.  Usage@@ -116,7 +132,7 @@ -------  ```-Copyright 2017 Adjoint Inc+Copyright 2017-2018 Adjoint Inc  Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.@@ -130,4 +146,3 @@ See the License for the specific language governing permissions and limitations under the License. ```-

@@ -1,37 +1,30 @@--- This file has been generated from package.yaml by hpack version 0.19.3.+-- This file has been generated from package.yaml by hpack version 0.20.0. -- -- see: https://github.com/sol/hpack+--+-- hash: 791088eebb790d77e07818fdaa551d0927606369753e61d1c4aa6223f8ab6095  name:           pedersen-commitment-version:        0.1.0+version:        0.2.0 synopsis:       An implementation of Pedersen commitment schemes-description:    An implementation of Pedersen commitment schemes+description:    An implementation of Pedersen commitment schemes for multiparty protocols. category:       Cryptography homepage:       https://github.com/adjoint-io/pedersen-commitment#readme bug-reports:    https://github.com/adjoint-io/pedersen-commitment/issues maintainer:     Adjoint Inc (info@adjoint.io)-license:        Apache+license:        MIT license-file:   LICENSE build-type:     Simple cabal-version:  >= 1.10  extra-source-files:+    ChangeLog.md     README.md  source-repository head   type: git   location: https://github.com/adjoint-io/pedersen-commitment -flag optimized-  description: Perform compiler optimizations-  manual: False-  default: False--flag static-  description: Emit statically-linked binary-  manual: False-  default: False- library   hs-source-dirs:       src@@ -49,6 +42,7 @@   exposed-modules:       PrimeField       Pedersen+      VectorPedersen       MICP.Internal       MICP   other-modules:

@@ -66,7 +66,7 @@  data CommitParams = CommitParams   { pedersenSPF :: SPF     -- ^ Safe prime field for pedersen commitment-  , pedersenH   :: Integer -- ^ h = g^a mod p where a is random+  , pedersenH   :: Integer -- ^ \(h = g^a \mod p\) where a is random   }  newtype Commitment = Commitment { unCommitment :: Integer }@@ -74,7 +74,7 @@  data Reveal = Reveal   { revealVal :: Integer -- ^ Original value comitted-  , revealExp :: Integer -- ^ random exponent r, g^x * h^r+  , revealExp :: Integer -- ^ random exponent r, \(g^x \cdot h^r\)   }  data Pedersen = Pedersen@@ -83,7 +83,7 @@   }  -- | Generates a Safe Prime Field (p,q,g) and a random value--- `a in Zq` such that `g^a = h`, where g and h are the bases+-- \(a \in Z_q\) such that \(g^a = h\), where g and h are the bases -- to be used in the pedersen commit function. setup :: MonadRandom m => Int -> m (Integer, CommitParams) setup nbits = do@@ -94,8 +94,8 @@     return (a,h)   return (a, CommitParams spf h) --- | Commit a value by generating a random number `r in Zq`--- and computing `C(x) = g^x * h^r` where x is the value to commit+-- | Commit a value by generating a random number \(r \in Z_q\)+-- and computing \(C(x) = g^x \cdot h^r\) where x is the value to commit commit :: MonadRandom m => Integer -> CommitParams -> m Pedersen commit x (CommitParams spf h) = do   (r,c) <- runSPFT spf $ do@@ -106,7 +106,7 @@  -- | Open the commit by supplying the value commited, `x`, the -- random value `r` and the pedersen bases `g` and `h`, and--- verifying that `C(x) == g^x * h^r`+-- verifying that \(C(x) \overset{!}{=} g^x * h^r\) open :: CommitParams -> Commitment -> Reveal -> Bool open (CommitParams spf h) (Commitment c) (Reveal x r) =     resCommit == c@@ -171,11 +171,11 @@   }  -- | Setup EC Pedersen commit params, defaults to curve secp256k1-ecSetup :: MonadRandom m => Maybe ECC.CurveName -> m (ECC.PrivateNumber, ECCommitParams)+ecSetup :: MonadRandom m => Maybe ECC.CurveName -> m ECCommitParams ecSetup mCurveName = do     a <- ECC.scalarGenerate curve     let h = ECC.pointBaseMul curve a-    return (a, ECCommitParams curve h)+    return $ ECCommitParams curve h   where     curve = case mCurveName of       Nothing -> secp256k1

@@ -0,0 +1,160 @@+module VectorPedersen (+  dot,+  mkGs,+  scalarGenerateN,+  ecCommit,+  ecOpen,+  ecVerifyAddCommitments,+  vecSum,+  ecAddVector,+  ecVerifyAddVector,++  ECReveal(..),+  ECPedersen(..),+  ECCommitParams(..),+  ECCommitment(..)+) where++import           Protolude                  hiding (hash)+import           Crypto.Hash+import           Crypto.Number.Serialize    (os2ip)+import qualified Crypto.PubKey.ECC.Prim     as ECC+import qualified Crypto.PubKey.ECC.Types    as ECC+import           Crypto.Random.Types (MonadRandom(..))+import qualified Data.ByteArray             as BA+import           Data.Monoid                ((<>))+import Pedersen (+    ecSetup,+    ECCommitParams(..),+    ECCommitment(..)+  )++-------------------------------------------------------------------------------+-- Vector Pedersen Commitment Scheme - Elliptic Curve (SECP256k1)+-------------------------------------------------------------------------------++-- | ecRevealVal is a vector of scalars+data ECReveal = ECReveal+  { ecRevealVal :: [Integer]+  , ecRevealScalar :: Integer+  }++data ECPedersen = ECPedersen+  { ecCommitment :: ECCommitment+  , ecReveal     :: ECReveal+  }++-- | Outputs unpredictable but deterministic random values+oracle :: ECC.Curve -> ByteString -> Integer+oracle curve x = os2ip (sha256 x) `mod` n+  where+    -- | Order of the curve+    n :: Integer+    n = ECC.ecc_n $ ECC.common_curve curve++-- | Secure cryptographic hash function+sha256 :: ByteString -> ByteString+sha256 bs = BA.convert (hash bs :: Digest SHA3_256)++-- | Generate a commit value which is a vector of N elements+scalarGenerateN :: MonadRandom m => ECC.Curve -> Word8 -> m [Integer]+scalarGenerateN curve n = scalarGenerateN' curve n []++scalarGenerateN' :: MonadRandom m => ECC.Curve -> Word8 -> [Integer] -> m [Integer]+scalarGenerateN' curve n v+  | n == 0 = return v+  | otherwise = do+      vi <- ECC.scalarGenerate curve+      if vi `elem` v+        then scalarGenerateN' curve n v+        else scalarGenerateN' curve (n-1) (vi:v)++-- | Dot product between a vector of scalars and a vector of ECC.Points+dot :: ECC.Curve -> [Integer] -> [ECC.Point] -> ECC.Point+dot curve scalars points = foldl' (ECC.pointAdd curve) ECC.PointO $+  zipWith (ECC.pointMul curve) scalars points++-- | Concatenate point coordinates to create a hashable type+appendCoordinates :: ECC.Point -> ByteString+appendCoordinates ECC.PointO      = ""+appendCoordinates (ECC.Point x y) = show x <> show y++-- | Generate vector of generators in a deterministic way from the curve generator g+-- by applying H(encode(g) || i) where H is a secure hash function+mkGs :: ECC.Curve -> [ECC.Point]+mkGs curve =+  fmap (ECC.pointBaseMul curve . oracle curve . (<> appendCoordinates g) . show) [1..]+  where+      g = ECC.ecc_g $ ECC.common_curve curve++-- | Commitment function. The value we commit to is now a vector+ecCommit :: MonadRandom m => [Integer] -> ECCommitParams -> m ECPedersen+ecCommit v (ECCommitParams curve h) = do+  r <- ECC.scalarGenerate curve++  let vG = dot curve v (mkGs curve)+  let rH = ECC.pointMul curve r h++  let commitment = ECCommitment $ ECC.pointAdd curve vG rH+  let reveal = ECReveal v r+  return $ ECPedersen commitment reveal++-- | Open commitment to check its validity+ecOpen :: ECCommitParams -> ECCommitment -> ECReveal -> Bool+ecOpen (ECCommitParams curve h) (ECCommitment c) (ECReveal v r) =+    c == ECC.pointAdd curve vG rH+  where+    vG = dot curve v (mkGs curve)+    rH = ECC.pointMul curve r h++-- | Sum of vectors in a curve+vecSum :: ECC.Curve -> [Integer] -> [Integer] -> [Integer]+vecSum curve = zipWith (\a b -> a + b `mod` n)+    where+      n :: Integer+      n = ECC.ecc_n $ ECC.common_curve curve++-- | Verify the addition of two EC Vector Pedersen Commitments by constructing+-- the new Pedersen commitment on the uncommitted values.+ecVerifyAddCommitments+  :: ECCommitParams+  -> ECPedersen+  -> ECPedersen+  -> ECPedersen+ecVerifyAddCommitments (ECCommitParams curve h) p1 p2 =+    ECPedersen newCommitment newReveal+  where+    ECReveal v r1 = ecReveal p1+    ECReveal w r2 = ecReveal p2++    vw = vecSum curve v w+    r = r1 + r2++    vwG = dot curve vw (mkGs curve)+    rH = ECC.pointMul curve r h++    newCommitment = ECCommitment $ ECC.pointAdd curve vwG rH+    newReveal = ECReveal vw r++-- | Add a vector to the committed value such that C'= C + wG +ecAddVector :: ECCommitParams -> ECCommitment -> [Integer] -> ECCommitment+ecAddVector (ECCommitParams curve h) (ECCommitment c) w =+    ECCommitment $ ECC.pointAdd curve wG c+  where+    wG = dot curve w (mkGs curve)++-- Access the reveal values of the vector pedersen commitment (r and v)+-- Return a new commitment adding an input vector w such that C' = (v + w)G + rH+ecVerifyAddVector :: ECCommitParams -> ECPedersen -> [Integer] -> ECPedersen+ecVerifyAddVector (ECCommitParams curve h) p w =+    ECPedersen newCommitment newReveal+  where+    ECReveal v r = ecReveal p++    vw = vecSum curve v w++    vwG = dot curve vw (mkGs curve)+    rH = ECC.pointMul curve r h -- rH doesn't change++    newCommitment = ECCommitment $ ECC.pointAdd curve vwG rH+    newReveal = ECReveal vw r -- r doesn't change

@@ -18,13 +18,16 @@  import Pedersen import PrimeField+import qualified VectorPedersen as VP  suite :: TestTree suite = testGroup "Test Suite" [     testGroup "Units"-      [ pedersenTests-      , micpTests-      ]+      [vectorPedersenTests]+      -- [ pedersenTests+      -- , micpTests+      -- , vectorPedersenTests+      -- ]   ]  pedersenTests :: TestTree@@ -56,14 +59,14 @@    , testProperty "x == Open(Commit(x),r) (EC) " $       monadicIO $ do-        (a,cp) <- liftIO $ ecSetup Nothing -- uses SECP256k1 by default+        cp <- liftIO $ ecSetup Nothing -- uses SECP256k1 by default         x <- liftIO $ ECC.scalarGenerate $ ecCurve cp         pc <- liftIO $ ecCommit x cp         QM.assert $ ecOpen cp (ecCommitment pc) (ecReveal pc)    , testCaseSteps "Additive Homomorphic Commitments (EC) " $ \step -> do       step "Generating commit params..."-      (a,ecp) <- ecSetup Nothing+      ecp <- ecSetup Nothing       let curve = ecCurve ecp        step "Generating two random numbers in Ep (EC prime field order q)..."@@ -81,7 +84,7 @@    , testCaseSteps "Additive Homomorphic property (EC) | nG + C(x) == (x + n)G + rH" $ \step -> do       step "Generating commit params..."-      (a,ecp) <- ecSetup Nothing+      ecp <- ecSetup Nothing       let curve = ecCurve ecp        step "Generating a random number to commit..."@@ -109,6 +112,49 @@   , testCase "Testing MICP Wrapper" $       assertBool "MICP Wrapper test failed!" =<< micpWrapper 256   ]+++vectorPedersenTests :: TestTree+vectorPedersenTests = testGroup "Vector Pedersen Commitment"+  [+  localOption (QuickCheckTests 10) $+      testProperty "xs == Open(Commit(xs),r) (EC) " $ \n ->+        monadicIO $ do+          cp <- liftIO $ ecSetup Nothing -- uses SECP256k1 by default+          v <- liftIO $ VP.scalarGenerateN (ecCurve cp) n+          pc <- liftIO $ VP.ecCommit v cp+          QM.assert $ VP.ecOpen cp (VP.ecCommitment pc) (VP.ecReveal pc)++  , localOption (QuickCheckTests 10) $+      testProperty "Additive Homomorphic Commitments (EC) " $ \n ->+        monadicIO $ do+          cp <- liftIO $ ecSetup Nothing+          v <- liftIO $ VP.scalarGenerateN (ecCurve cp) n+          w <- liftIO $ VP.scalarGenerateN (ecCurve cp) n++          pv@(VP.ECPedersen cv rv) <- liftIO $ VP.ecCommit v cp+          pw@(VP.ECPedersen cw rw) <- liftIO $ VP.ecCommit w cp++          let cz = ecAddCommitments cp cv cw+          let pz = VP.ecVerifyAddCommitments cp pv pw+          QM.assert $ cz == VP.ecCommitment pz++   , localOption (QuickCheckTests 10) $+      testProperty "Additive Homomorphic property (EC) | wG + C(v) == (v + w)G + rH" $ \n ->+        monadicIO $ do+          cp <- liftIO $ ecSetup Nothing++          v <- liftIO $ VP.scalarGenerateN (ecCurve cp) n+          pv@(VP.ECPedersen cv rv) <- liftIO $ VP.ecCommit v cp++          w <- liftIO $ VP.scalarGenerateN (ecCurve cp) n++          let cw = VP.ecAddVector cp cv w+          let pw = VP.ecVerifyAddVector cp pv w++          QM.assert $ cw == VP.ecCommitment pw+    ]+  main :: IO () main = defaultMain suite