add M+1st price private outcome implementation

3 files changed, 234 insertions, 5 deletions

diff --git a/Makefile.am b/Makefile.am
index 92674e6..e0b6356 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -9,6 +9,7 @@ libbrandt_la_SOURCES = \
   crypto.c \
   fp_priv.c \
   fp_pub.c \
+  mp_priv.c \
   util.c
 
 libbrandt_la_LIBADD = \
diff --git a/crypto.h b/crypto.h
index b4344da..35e98a6 100644
--- a/crypto.h
+++ b/crypto.h
@@ -182,6 +182,12 @@ struct BRANDT_Result *fp_pub_determine_outcome (struct BRANDT_Auction *ad,
                                                 uint16_t              *len);
 
 
+void mp_priv_prep_outcome (struct BRANDT_Auction *ad);
+
+struct BRANDT_Result *mp_priv_determine_outcome (struct BRANDT_Auction *ad,
+                                                 uint16_t              *len);
+
+
 /* --- Round dictionaries --- */
 
 typedef void
@@ -233,6 +239,8 @@ static const RoundPrep handler_prep[auction_last][outcome_last][msg_last] = {
                 [outcome_private] =     {
                         [msg_init] = &smc_prep_keyshare,
                         [msg_bid] = &smc_prep_bid,
+                        [msg_outcome] = &mp_priv_prep_outcome,
+                        [msg_decrypt] = &fp_priv_prep_decryption,
                 },
                 [outcome_public] =      {
                         [msg_init] = &smc_prep_keyshare,
@@ -271,6 +279,8 @@ static const MsgIn handler_in[auction_last][outcome_last][msg_last] = {
                 [outcome_private] =     {
                         [msg_init] = &smc_recv_keyshare,
                         [msg_bid] = &smc_recv_encrypted_bid,
+                        [msg_outcome] = &fp_priv_recv_outcome,
+                        [msg_decrypt] = &fp_priv_recv_decryption,
                 },
                 [outcome_public] =      {
                         [msg_init] = &smc_recv_keyshare,
@@ -310,6 +320,8 @@ static const MsgOut handler_out[auction_last][outcome_last][msg_last] = {
                 [outcome_private] =     {
                         [msg_init] = &smc_gen_keyshare,
                         [msg_bid] = &smc_encrypt_bid,
+                        [msg_outcome] = &fp_priv_compute_outcome,
+                        [msg_decrypt] = &fp_priv_decrypt_outcome,
                 },
                 [outcome_public] =      {
                         [msg_init] = &smc_gen_keyshare,
@@ -330,14 +342,14 @@ static const MsgOut handler_out[auction_last][outcome_last][msg_last] = {
  * of 0 means a private outcome, while a value of 1 means public outcome.
  */
 static const Result handler_res[auction_last][outcome_last] = {
-        [auction_firstPrice] = {
+        [auction_firstPrice] =      {
                 [outcome_private] = &fp_priv_determine_outcome,
                 [outcome_public] = &fp_pub_determine_outcome,
         },
-//      [auction_mPlusFirstPrice] = {
-//              [outcome_private] =     ,
-//              [outcome_public] =      ,
-//      },
+        [auction_mPlusFirstPrice] = {
+                [outcome_private] = &mp_priv_determine_outcome,
+//              [outcome_public] = ,
+        },
 };
 
 
diff --git a/mp_priv.c b/mp_priv.c
new file mode 100644
index 0000000..0d45a06
--- /dev/null
+++ b/mp_priv.c
@@ -0,0 +1,216 @@
+/* This file is part of libbrandt.
+ * Copyright (C) 2016 GNUnet e.V.
+ *
+ * libbrandt is free software: you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later
+ * version.
+ *
+ * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ * A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * libbrandt.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file mp_priv.c
+ * @brief Implementation of the m+1st price private outcome algorithm.
+ * @author Markus Teich
+ */
+
+#include "platform.h"
+
+#include <gcrypt.h>
+
+#include "crypto.h"
+#include "internals.h"
+#include "util.h"
+
+
+void
+mp_priv_prep_outcome (struct BRANDT_Auction *ad)
+{
+        gcry_mpi_t       factor = gcry_mpi_new (256);
+        gcry_mpi_point_t subtr = gcry_mpi_point_new (0);
+        gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
+        gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
+        gcry_mpi_point_t *tlta1;
+        gcry_mpi_point_t *tltb1;
+        gcry_mpi_point_t **tlta2;
+        gcry_mpi_point_t **tltb2;
+        gcry_mpi_point_t **tlta3;
+        gcry_mpi_point_t **tltb3;
+
+        ad->gamma3 = smc_init3 (ad->n, ad->n, ad->k);
+        brandt_assert (ad->gamma3);
+
+        ad->delta3 = smc_init3 (ad->n, ad->n, ad->k);
+        brandt_assert (ad->delta3);
+
+        /* create temporary lookup tables with partial sums */
+        tlta1 = smc_init1 (ad->k);
+        tltb1 = smc_init1 (ad->k);
+        tlta2 = smc_init2 (ad->n, ad->k);
+        tltb2 = smc_init2 (ad->n, ad->k);
+        tlta3 = smc_init2 (ad->n, ad->k);
+        tltb3 = smc_init2 (ad->n, ad->k);
+
+        /* temporary lookup table for first summand (building ladder of bids) */
+        for (uint16_t i = 0; i < ad->n; i++)
+        {
+                smc_sums_partial (tlta3[i], ad->alpha[i], ad->k, 1, 1);
+                smc_sums_partial (tltb3[i], ad->beta[i], ad->k, 1, 1);
+                for (uint16_t j = 0; j < ad->k; j++)
+                {
+                        gcry_mpi_ec_sub (tlta2[i][j],
+                                         tlta3[i][ad->k - 1],
+                                         tlta3[i][j],
+                                         ec_ctx);
+                        gcry_mpi_ec_sub (tltb2[i][j],
+                                         tltb3[i][ad->k - 1],
+                                         tltb3[i][j],
+                                         ec_ctx);
+                }
+                brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][ad->k - 1]));
+                brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][ad->k - 1]));
+        }
+        for (uint16_t j = 0; j < ad->k; j++)
+        {
+                /* 2L - 2I */
+                smc_sum (tmpa, &tlta2[0][j], ad->n, ad->k);
+                smc_sum (tmpb, &tltb2[0][j], ad->n, ad->k);
+                gcry_mpi_ec_mul (tlta1[j], GCRYMPI_CONST_TWO, tmpa, ec_ctx);
+                gcry_mpi_ec_mul (tltb1[j], GCRYMPI_CONST_TWO, tmpb, ec_ctx);
+
+                /* I */
+                smc_sum (tmpa, &ad->alpha[0][j], ad->n, ad->k);
+                smc_sum (tmpb, &ad->beta[0][j], ad->n, ad->k);
+
+                /* 2L - 2I + I = 2L - I */
+                gcry_mpi_ec_add (tlta1[j], tlta1[j], tmpa, ec_ctx);
+                gcry_mpi_ec_add (tltb1[j], tltb1[j], tmpb, ec_ctx);
+        }
+        /* This check only works directly after the loop when tmpa/tmpb are still
+         * the sum of the last row */
+        brandt_assert (!ec_point_cmp (tmpa, tlta1[ad->k - 1]));
+        brandt_assert (!ec_point_cmp (tmpb, tltb1[ad->k - 1]));
+
+        /* temporary lookup table for second summand (hide outcome from losers) */
+        gcry_mpi_set_ui (factor, ad->m);
+        gcry_mpi_lshift (factor, factor, 1);
+        gcry_mpi_add_ui (factor, factor, 2);
+        for (uint16_t i = 0; i < ad->n; i++)
+        {
+                for (uint16_t j = 0; j < ad->k; j++)
+                {
+                        gcry_mpi_ec_mul (tlta2[i][j], factor, tlta3[i][j], ec_ctx);
+                        gcry_mpi_ec_mul (tltb2[i][j], factor, tltb3[i][j], ec_ctx);
+                }
+        }
+
+        /* temporary lookup table for subtrahend (getting M+1st highest bid) */
+        gcry_mpi_sub_ui (factor, factor, 1);
+        gcry_mpi_ec_mul (subtr, factor, ec_gen, ec_ctx);
+
+        /* compute gamma and delta */
+        for (uint16_t i = 0; i < ad->n; i++)
+        {
+                for (uint16_t j = 0; j < ad->k; j++)
+                {
+                        /* compute inner gamma */
+                        gcry_mpi_ec_add (tmpa, tlta1[j], tlta2[i][j], ec_ctx);
+                        gcry_mpi_ec_sub (tmpa, tmpa, subtr, ec_ctx);
+
+                        /* compute inner delta */
+                        gcry_mpi_ec_add (tmpb, tltb1[j], tltb2[i][j], ec_ctx);
+
+                        /* copy unmasked outcome to all other bidder layers so they don't
+                         * have to be recomputed to check the ZK proof_2dle's from other
+                         * bidders when receiving their outcome messages */
+                        for (uint16_t a = 0; a < ad->n; a++)
+                        {
+                                ec_point_copy (ad->gamma3[a][i][j], tmpa);
+                                ec_point_copy (ad->delta3[a][i][j], tmpb);
+                        }
+                }
+        }
+
+        gcry_mpi_release (factor);
+        gcry_mpi_point_release (subtr);
+        gcry_mpi_point_release (tmpa);
+        gcry_mpi_point_release (tmpb);
+        smc_free1 (tlta1, ad->k);
+        smc_free1 (tltb1, ad->k);
+        smc_free2 (tlta2, ad->n, ad->k);
+        smc_free2 (tltb2, ad->n, ad->k);
+        smc_free2 (tlta3, ad->n, ad->k);
+        smc_free2 (tltb3, ad->n, ad->k);
+}
+
+
+struct BRANDT_Result *
+mp_priv_determine_outcome (struct BRANDT_Auction *ad,
+                           uint16_t              *len)
+{
+        struct BRANDT_Result *ret;
+        int32_t              price = -1;
+        uint16_t             winners = 0;
+        uint16_t             max_winners;
+        gcry_mpi_point_t     sum_gamma = gcry_mpi_point_new (0);
+        gcry_mpi_point_t     sum_phi = gcry_mpi_point_new (0);
+
+        brandt_assert (ad);
+
+        max_winners = ad->seller_mode ? ad->m : 1;
+        ret = GNUNET_new_array (max_winners, struct BRANDT_Result);
+        for (uint16_t i = 0; i < ad->n; i++)
+        {
+                if (!ad->seller_mode && i != ad->i)
+                        continue;
+
+                for (uint16_t j = 0; j < ad->k; j++)
+                {
+                        smc_sum (sum_gamma, &ad->gamma3[0][i][j], ad->n, ad->n * ad->k);
+                        smc_sum (sum_phi, &ad->phi3[0][i][j], ad->n, ad->n * ad->k);
+                        gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
+                        if (!ec_point_cmp (sum_gamma, ec_zero))
+                        {
+                                weprintf ("lol");
+                                if (winners >= max_winners)
+                                {
+                                        weprintf ("too many winners detected");
+                                        goto fail;
+                                }
+                                if (-1 != price && j != price)
+                                {
+                                        weprintf ("multiple winning prices detected");
+                                        goto fail;
+                                }
+                                price = j;
+
+                                ret[winners].bidder = i;
+                                ret[winners].price = j / ad->n;
+                                ret[winners].status = BRANDT_bidder_won;
+                                winners++;
+                        }
+                }
+        }
+
+        gcry_mpi_point_release (sum_gamma);
+        gcry_mpi_point_release (sum_phi);
+
+        if (ad->m <= ad->n && winners < max_winners && -1 != price)
+                weprintf ("too few winners detected");
+        if (0 == winners)
+                goto fail;
+
+        if (len)
+                *len = winners;
+        return ret;
+
+fail:
+        GNUNET_free (ret);
+        return NULL;
+}