split different auction format algorithms into separate files

1 files changed, 584 insertions, 0 deletions

diff --git a/fp_priv.c b/fp_priv.c
new file mode 100644
index 0000000..c96f969
--- /dev/null
+++ b/fp_priv.c
@@ -0,0 +1,584 @@
+/* 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 fp_pub.c
+ * @brief Implementation of the first price public outcome algorithm.
+ * @author Markus Teich
+ */
+
+#include "platform.h"
+
+#include <gcrypt.h>
+
+#include "crypto.h"
+#include "internals.h"
+#include "util.h"
+
+
+void
+fp_priv_prep_outcome (struct BRANDT_Auction *ad)
+{
+	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 (no one has a higher bid) */
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		smc_sums_partial (tlta2[i], ad->alpha[i], ad->k, 1, 1);
+		smc_sums_partial (tltb2[i], ad->beta[i], ad->k, 1, 1);
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			gcry_mpi_ec_sub (tlta3[i][j],
+			                 tlta2[i][ad->k - 1],
+			                 tlta2[i][j],
+			                 ec_ctx);
+			gcry_mpi_ec_sub (tltb3[i][j],
+			                 tltb2[i][ad->k - 1],
+			                 tltb2[i][j],
+			                 ec_ctx);
+		}
+		brandt_assert (!ec_point_cmp (ec_zero, tlta3[i][ad->k - 1]));
+		brandt_assert (!ec_point_cmp (ec_zero, tltb3[i][ad->k - 1]));
+	}
+	for (uint16_t j = 0; j < ad->k; j++)
+	{
+		smc_sum (tlta1[j], &tlta3[0][j], ad->n, ad->k);
+		smc_sum (tltb1[j], &tltb3[0][j], ad->n, ad->k);
+	}
+	brandt_assert (!ec_point_cmp (ec_zero, tlta1[ad->k - 1]));
+	brandt_assert (!ec_point_cmp (ec_zero, tltb1[ad->k - 1]));
+	/* \todo: merge into one nested i,j loop and one nested j,i loop? */
+
+	/* temporary lookup table for second summand (my bid is not lower) */
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			gcry_mpi_ec_sub (tlta2[i][j], tlta2[i][j], ad->alpha[i][j], ec_ctx);
+			gcry_mpi_ec_sub (tltb2[i][j], tltb2[i][j], ad->beta[i][j], ec_ctx);
+		}
+		brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][0]));
+		brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][0]));
+	}
+
+	/* temporary lookup table for third summand (no one with a lower index has
+	 * the same bid) */
+	for (uint16_t j = 0; j < ad->k; j++)
+	{
+		smc_sums_partial (&tlta3[0][j], &ad->alpha[0][j], ad->n, ad->k, ad->k);
+		smc_sums_partial (&tltb3[0][j], &ad->beta[0][j], ad->n, ad->k, ad->k);
+		for (uint16_t i = 0; i < ad->n; i++)
+		{
+			gcry_mpi_ec_sub (tlta3[i][j], tlta3[i][j], ad->alpha[i][j], ec_ctx);
+			gcry_mpi_ec_sub (tltb3[i][j], tltb3[i][j], ad->beta[i][j], ec_ctx);
+		}
+		brandt_assert (!ec_point_cmp (ec_zero, tlta3[0][j]));
+		brandt_assert (!ec_point_cmp (ec_zero, tltb3[0][j]));
+	}
+
+	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_add (tmpa, tmpa, tlta3[i][j], ec_ctx);
+
+			/* compute inner delta */
+			gcry_mpi_ec_add (tmpb, tltb1[j], tltb2[i][j], ec_ctx);
+			gcry_mpi_ec_add (tmpb, tmpb, tltb3[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_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);
+}
+
+
+/**
+ * fp_priv_compute_outcome computes encrypted outcome shares and packs them into
+ * a message buffer together with proofs of correctnes.
+ *
+ * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
+ * @param[out] buflen Size of the returned message buffer in bytes
+ * @return A buffer containing the encrypted outcome vectors
+ * which needs to be broadcast
+ */
+unsigned char *
+fp_priv_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
+{
+	unsigned char     *ret;
+	unsigned char     *cur;
+	struct msg_head   *head;
+	gcry_mpi_point_t  tmpa = gcry_mpi_point_new (0);
+	gcry_mpi_point_t  tmpb = gcry_mpi_point_new (0);
+	struct ec_mpi     *gamma;
+	struct ec_mpi     *delta;
+	struct proof_2dle *proof2;
+
+	brandt_assert (ad && buflen);
+
+	*buflen = (sizeof (*head) +                /* msg header */
+	           ad->n * ad->k *                 /* nk * (gamma, delta, proof2) */
+	           (sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2)));
+	ret = GNUNET_new_array (*buflen, unsigned char);
+
+	head = (struct msg_head *)ret;
+	head->prot_version = htonl (0);
+	head->msg_type = htonl (msg_outcome);
+	cur = ret + sizeof (*head);
+
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			gamma = (struct ec_mpi *)cur;
+			delta = &((struct ec_mpi *)cur)[1];
+			proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
+
+			ec_point_copy (tmpa, ad->gamma3[ad->i][i][j]);
+			ec_point_copy (tmpb, ad->delta3[ad->i][i][j]);
+
+			/* apply random masking for losing bidders */
+			smc_zkp_2dle (ad->gamma3[ad->i][i][j],
+			              ad->delta3[ad->i][i][j],
+			              tmpa,
+			              tmpb,
+			              NULL,
+			              proof2);
+
+			ec_point_serialize (gamma, ad->gamma3[ad->i][i][j]);
+			ec_point_serialize (delta, ad->delta3[ad->i][i][j]);
+
+			cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
+		}
+	}
+
+	gcry_mpi_point_release (tmpa);
+	gcry_mpi_point_release (tmpb);
+	return ret;
+}
+
+
+int
+fp_priv_recv_outcome (struct BRANDT_Auction *ad,
+                      const unsigned char   *buf,
+                      size_t                buflen,
+                      uint16_t              sender)
+{
+	int                 ret = 0;
+	const unsigned char *cur = buf;
+	struct proof_2dle   *proof2;
+	gcry_mpi_point_t    gamma = gcry_mpi_point_new (0);
+	gcry_mpi_point_t    delta = gcry_mpi_point_new (0);
+
+	brandt_assert (ad && buf);
+
+	if (buflen != (ad->n * ad->k *
+	               (2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
+	{
+		weprintf ("wrong size of received outcome");
+		goto quit;
+	}
+
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			ec_point_parse (gamma, (struct ec_mpi *)cur);
+			ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
+			proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
+			if (smc_zkp_2dle_check (gamma,
+			                        delta,
+			                        ad->gamma3[sender][i][j],
+			                        ad->delta3[sender][i][j],
+			                        proof2))
+			{
+				weprintf ("wrong zkp2 for gamma, delta received");
+				goto quit;
+			}
+			ec_point_copy (ad->gamma3[sender][i][j], gamma);
+			ec_point_copy (ad->delta3[sender][i][j], delta);
+			cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
+		}
+	}
+
+	ret = 1;
+quit:
+	gcry_mpi_point_release (gamma);
+	gcry_mpi_point_release (delta);
+	return ret;
+}
+
+
+void
+fp_priv_prep_decryption (struct BRANDT_Auction *ad)
+{
+	gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
+
+	ad->phi3 = smc_init3 (ad->n, ad->n, ad->k);
+	brandt_assert (ad->phi3);
+
+	ad->phiproofs3 = GNUNET_new_array_3d (ad->n,
+	                                      ad->n,
+	                                      ad->k,
+	                                      struct proof_2dle);
+	brandt_assert (ad->phiproofs3);
+
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			smc_sum (tmp, &ad->delta3[0][i][j], ad->n, ad->n * ad->k);
+
+			/* copy still encrypted 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 decryption messages */
+			for (uint16_t a = 0; a < ad->n; a++)
+				ec_point_copy (ad->phi3[a][i][j], tmp);
+		}
+	}
+
+	gcry_mpi_point_release (tmp);
+}
+
+
+static unsigned char *
+fp_priv_decrypt_outcome_seller (struct BRANDT_Auction *ad, size_t *buflen)
+{
+	unsigned char     *ret;
+	unsigned char     *cur;
+	struct msg_head   *head;
+	gcry_mpi_point_t  tmp = gcry_mpi_point_new (0);
+	struct ec_mpi     *phi;
+	struct proof_2dle *proof2;
+
+	*buflen = (sizeof (*head) +
+	           (ad->n - 1) * ad->n * ad->k * (sizeof (*phi) +
+	                                          sizeof (*proof2)));
+	ret = GNUNET_new_array (*buflen, unsigned char);
+
+	head = (struct msg_head *)ret;
+	head->prot_version = htonl (0);
+	head->msg_type = htonl (msg_decrypt);
+	cur = ret + sizeof (*head);
+
+	for (uint16_t h = 0; h < ad->n; h++)
+	{
+		for (uint16_t i = 0; i < ad->n; i++)
+		{
+			/* don't reveal outcome to losing bidders */
+			if (h == i)
+				continue;
+
+			for (uint16_t j = 0; j < ad->k; j++)
+			{
+				phi = (struct ec_mpi *)cur;
+				proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
+
+				ec_point_serialize (phi, ad->phi3[h][i][j]);
+				memcpy (proof2, &ad->phiproofs3[h][i][j], sizeof (*proof2));
+
+				cur += sizeof (*phi) + sizeof (*proof2);
+			}
+		}
+	}
+
+	gcry_mpi_point_release (tmp);
+	return ret;
+}
+
+
+static unsigned char *
+fp_priv_decrypt_outcome_bidder (struct BRANDT_Auction *ad, size_t *buflen)
+{
+	unsigned char     *ret;
+	unsigned char     *cur;
+	struct msg_head   *head;
+	gcry_mpi_point_t  tmp = gcry_mpi_point_new (0);
+	struct ec_mpi     *phi;
+	struct proof_2dle *proof2;
+
+	*buflen = (sizeof (*head) +
+	           ad->n * ad->k * (sizeof (*phi) + sizeof (*proof2)));
+	ret = GNUNET_new_array (*buflen, unsigned char);
+
+	head = (struct msg_head *)ret;
+	head->prot_version = htonl (0);
+	head->msg_type = htonl (msg_decrypt);
+	cur = ret + sizeof (*head);
+
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			phi = (struct ec_mpi *)cur;
+			proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
+
+			ec_point_copy (tmp, ad->phi3[ad->i][i][j]);
+
+			/* decrypt outcome component and prove the correct key was used */
+			smc_zkp_2dle (ad->phi3[ad->i][i][j],
+			              NULL,
+			              tmp,
+			              ec_gen,
+			              ad->x,
+			              proof2);
+
+			ec_point_serialize (phi, ad->phi3[ad->i][i][j]);
+
+			cur += sizeof (*phi) + sizeof (*proof2);
+		}
+	}
+
+	gcry_mpi_point_release (tmp);
+	return ret;
+}
+
+
+/**
+ * fp_priv_decrypt_outcome decrypts the own shares of the outcome and packs them
+ * into a message buffer together with proofs of correctnes. When this is called
+ * as the seller it will not decrypt anything, but just create the message
+ * buffer from all received decryption shares to broadcast back to all bidders.
+ *
+ * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
+ * @param[out] buflen Size of the returned message buffer in bytes
+ * @return A buffer containing the share of the decrypted outcome
+ * which needs to be broadcast
+ */
+unsigned char *
+fp_priv_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
+{
+	brandt_assert (ad && buflen);
+	if (ad->seller_mode)
+		return fp_priv_decrypt_outcome_seller (ad, buflen);
+	else
+		return fp_priv_decrypt_outcome_bidder (ad, buflen);
+}
+
+
+static int
+fp_priv_recv_decryption_seller (struct BRANDT_Auction *ad,
+                                const unsigned char   *buf,
+                                size_t                buflen,
+                                uint16_t              sender)
+{
+	int                 ret = 0;
+	const unsigned char *cur = buf;
+	struct proof_2dle   *proof2;
+	gcry_mpi_point_t    phi = gcry_mpi_point_new (0);
+
+	if (buflen != (ad->n * ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
+	{
+		weprintf ("wrong size of received outcome decryption from bidder");
+		goto quit;
+	}
+
+	for (uint16_t i = 0; i < ad->n; i++)
+	{
+		for (uint16_t j = 0; j < ad->k; j++)
+		{
+			ec_point_parse (phi, (struct ec_mpi *)cur);
+			proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
+			if (smc_zkp_2dle_check (phi,
+			                        ad->y[sender],
+			                        ad->phi3[sender][i][j],
+			                        ec_gen,
+			                        proof2))
+			{
+				weprintf ("wrong zkp2 for phi, y received from bidder");
+				goto quit;
+			}
+
+			/* store proof. we need to rebroadcast it to the other bidders */
+			memcpy (&ad->phiproofs3[sender][i][j], proof2, sizeof (*proof2));
+
+			ec_point_copy (ad->phi3[sender][i][j], phi);
+			cur += sizeof (struct ec_mpi) + sizeof (*proof2);
+		}
+	}
+
+	ret = 1;
+quit:
+	gcry_mpi_point_release (phi);
+	return ret;
+}
+
+
+static int
+fp_priv_recv_decryption_bidder (struct BRANDT_Auction *ad,
+                                const unsigned char   *buf,
+                                size_t                buflen,
+                                uint16_t              sender)
+{
+	int                 ret = 0;
+	const unsigned char *cur = buf;
+	struct proof_2dle   *proof2;
+	gcry_mpi_point_t    phi = gcry_mpi_point_new (0);
+
+	if (buflen != ((ad->n - 1) * ad->n * ad->k * (sizeof (struct ec_mpi) +
+	                                              sizeof (*proof2))))
+	{
+		weprintf ("wrong size of received outcome decryption from seller");
+		goto quit;
+	}
+
+	for (uint16_t h = 0; h < ad->n; h++)
+	{
+		for (uint16_t i = 0; i < ad->n; i++)
+		{
+			/* those combinations are not sent by the seller */
+			if (h == i)
+				continue;
+
+			/* we already have our own phi values */
+			if (h == ad->i)
+			{
+				cur += ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2));
+				continue;
+			}
+
+			for (uint16_t j = 0; j < ad->k; j++)
+			{
+				ec_point_parse (phi, (struct ec_mpi *)cur);
+				proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
+				if (smc_zkp_2dle_check (phi,
+				                        ad->y[h],
+				                        ad->phi3[h][i][j],
+				                        ec_gen,
+				                        proof2))
+				{
+					weprintf ("wrong zkp2 for phi, y received from seller");
+					goto quit;
+				}
+				ec_point_copy (ad->phi3[h][i][j], phi);
+				cur += sizeof (struct ec_mpi) + sizeof (*proof2);
+			}
+		}
+	}
+
+	ret = 1;
+quit:
+	gcry_mpi_point_release (phi);
+	return ret;
+}
+
+
+int
+fp_priv_recv_decryption (struct BRANDT_Auction *ad,
+                         const unsigned char   *buf,
+                         size_t                buflen,
+                         uint16_t              sender)
+{
+	brandt_assert (ad && buf);
+	if (ad->seller_mode)
+		return fp_priv_recv_decryption_seller (ad, buf, buflen, sender);
+	else
+		return fp_priv_recv_decryption_bidder (ad, buf, buflen, sender);
+}
+
+
+struct BRANDT_Result *
+fp_priv_determine_outcome (struct BRANDT_Auction *ad,
+                           uint16_t              *len)
+{
+	struct BRANDT_Result *ret;
+	int32_t              price = -1;
+	int32_t              winner = -1;
+	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);
+
+	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))
+			{
+				if (-1 != price)
+				{
+					weprintf ("multiple winning prices detected");
+					return NULL;
+				}
+				if (-1 != winner)
+				{
+					weprintf ("multiple winners detected");
+					return NULL;
+				}
+				price = j;
+				winner = i;
+			}
+		}
+	}
+
+	gcry_mpi_point_release (sum_gamma);
+	gcry_mpi_point_release (sum_phi);
+
+	if (-1 == winner || -1 == price)
+		return NULL;
+
+	ret = GNUNET_new (struct BRANDT_Result);
+	ret->bidder = winner;
+	ret->price = price;
+	ret->status = BRANDT_bidder_won;
+	if (len)
+		*len = 1;
+	return ret;
+}