xref: /freebsd-src/crypto/libecc/src/sig/bip0340.c (revision f0865ec9906d5a18fa2a3b61381f22ce16e606ad)

/*
 *  Copyright (C) 2022 - This file is part of libecc project
 *
 *  Authors:
 *      Ryad BENADJILA <ryadbenadjila@gmail.com>
 *      Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
 *
 *  This software is licensed under a dual BSD and GPL v2 license.
 *  See LICENSE file at the root folder of the project.
 */
#include <libecc/lib_ecc_config.h>
#if defined(WITH_SIG_BIP0340)

/* BIP0340 needs SHA-256: check it */
#if !defined(WITH_HASH_SHA256)
#error "Error: BIP0340 needs SHA-256 to be defined! Please define it in libecc config file"
#endif

#include <libecc/nn/nn_rand.h>
#include <libecc/nn/nn_mul_public.h>
#include <libecc/nn/nn_logical.h>

#include <libecc/sig/sig_algs_internal.h>
#include <libecc/sig/sig_algs.h>
#include <libecc/sig/ec_key.h>
#ifdef VERBOSE_INNER_VALUES
#define EC_SIG_ALG "BIP0340"
#endif
#include <libecc/utils/dbg_sig.h>

/*
 * The current implementation is for the BIP0340 signature as described
 * in https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
 *
 * The BIP0340 signature is only compatible with SHA-256 and secp256k1,
 * but we extend it to any hash function or curve.
 *
 */

/* The "hash" function static prefixes */
#define BIP0340_AUX	 "BIP0340/aux"
#define BIP0340_NONCE	 "BIP0340/nonce"
#define BIP0340_CHALLENGE "BIP0340/challenge"

ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_hash(const u8 *tag, u32 tag_len,
						   const u8 *m, u32 m_len,
						   const hash_mapping *hm, hash_context *h_ctx)
{
	int ret;
	u8 hash[MAX_DIGEST_SIZE];

	MUST_HAVE((h_ctx != NULL), ret, err);

	ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);

	ret = hm->hfunc_init(h_ctx); EG(ret, err);
	ret = hm->hfunc_update(h_ctx, tag, tag_len); EG(ret, err);
	ret = hm->hfunc_finalize(h_ctx, hash); EG(ret, err);

	/* Now compute hash(hash(tag) || hash(tag) || m) */
	ret = hm->hfunc_init(h_ctx); EG(ret, err);
	ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
	ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
	ret = hm->hfunc_update(h_ctx, m, m_len); EG(ret, err);

	ret = 0;
err:
	return ret;
}

/* Set the scalar value depending on the parity bit of the input
 * point y coordinate.
 */
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_set_scalar(nn_t scalar,
							 nn_src_t q,
							 prj_pt_src_t P)
{
	int ret, isodd, isone;

	/* Sanity check */
	ret = prj_pt_check_initialized(P); EG(ret, err);

	/* This operation is only meaningful on the "affine" representative.
	 * Check it.
	 */
	ret = nn_isone(&(P->Z.fp_val), &isone); EG(ret, err);
	MUST_HAVE((isone), ret, err);

	/* Check if Py is odd or even */
	ret = nn_isodd(&(P->Y.fp_val), &isodd); EG(ret, err);

	if(isodd){
		/* Replace the input scalar by (q - scalar)
		 * (its opposite modulo q)
		 */
		ret = nn_mod_neg(scalar, scalar, q); EG(ret, err);
	}

err:
	return ret;
}

/*
 * Generic *internal* helper for BIP340 public key initialization
 * functions. The function returns 0 on success, -1 on error.
 */
int bip0340_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
{
	prj_pt_src_t G;
	int ret;

	MUST_HAVE((out_pub != NULL), ret, err);

	/* Zero init public key to be generated */
	ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);

	ret = priv_key_check_initialized_and_type(in_priv, BIP0340); EG(ret, err);

	/* Y = xG */
	G = &(in_priv->params->ec_gen);
	/* Use blinding when computing point scalar multiplication */
	ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err);

	out_pub->key_type = BIP0340;
	out_pub->params = in_priv->params;
	out_pub->magic = PUB_KEY_MAGIC;

err:
	return ret;
}

/*
 * Generic *internal* helper for BIP0340 signature length functions.
 */
int bip0340_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize,
		    u8 *siglen)
{
	int ret;

	MUST_HAVE((siglen != NULL), ret, err);
	MUST_HAVE(((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
		   (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
		   (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE)),
		   ret, err);

	(*siglen) = (u8)BIP0340_SIGLEN(p_bit_len, q_bit_len);
	ret = 0;

err:
	return ret;
}

/*
 * Generic *internal* helper for BIP0340 signature.
 * NOTE: because of the semi-deterministinc nonce generation
 * process, streaming mode is NOT supported for signing.
 * Hence the following all-in-one signature function.
 *
 * The function returns 0 on success, -1 on error.
 */
int _bip0340_sign(u8 *sig, u8 siglen, const ec_key_pair *key_pair,
		  const u8 *m, u32 mlen, int (*rand) (nn_t out, nn_src_t q),
		  ec_alg_type sig_type, hash_alg_type hash_type,
		  const u8 *adata, u16 adata_len)
{
	prj_pt_src_t G;
	prj_pt Y;
	nn_src_t q;
	nn k, d, e;
	prj_pt kG;
	const ec_priv_key *priv_key;
	const ec_pub_key *pub_key;
	bitcnt_t p_bit_len, q_bit_len;
	u8 i, p_len, q_len;
	int ret, cmp, iszero;
	hash_context h_ctx;
	const hash_mapping *hm;
	u8 buff[MAX_DIGEST_SIZE];
#ifdef USE_SIG_BLINDING
	/* b is the blinding mask */
	nn b, binv;
	b.magic = binv.magic = WORD(0);
#endif /* USE_SIG_BLINDING */

	k.magic = d.magic = e.magic = kG.magic = Y.magic = WORD(0);

	FORCE_USED_VAR(adata_len);

	/* No ancillary data is expected with BIP0340 */
	MUST_HAVE((key_pair != NULL) && (sig != NULL) && (adata == NULL), ret, err);

	/* Check our algorithm type */
	MUST_HAVE((sig_type == BIP0340), ret, err);

	/* Check that keypair is initialized */
	ret = key_pair_check_initialized_and_type(key_pair, BIP0340); EG(ret, err);

	/* Get the hash mapping */
	ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
	MUST_HAVE((hm != NULL), ret, err);
	ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);

	/* Make things more readable */
	priv_key = &(key_pair->priv_key);
	pub_key = &(key_pair->pub_key);
	G = &(priv_key->params->ec_gen);
	q = &(priv_key->params->ec_gen_order);
	p_bit_len = priv_key->params->ec_fp.p_bitlen;
	q_bit_len = priv_key->params->ec_gen_order_bitlen;
	q_len = (u8)BYTECEIL(q_bit_len);
	p_len = (u8)BYTECEIL(p_bit_len);

	/* Copy the public key point to work on the unique
	 * affine representative.
	 */
	ret = prj_pt_copy(&Y, &(pub_key->y)); EG(ret, err);
	ret = prj_pt_unique(&Y, &Y); EG(ret, err);

	ret = nn_init(&d, 0); EG(ret, err);
	ret = nn_copy(&d, &(priv_key->x)); EG(ret, err);

	dbg_nn_print("d", &d);

	/* Check signature size */
	MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
	MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
	MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);

	/* Fail if d = 0 or d >= q */
	ret = nn_iszero(&d, &iszero); EG(ret, err);
	ret = nn_cmp(&d, q, &cmp); EG(ret, err);
	MUST_HAVE((!iszero) && (cmp < 0), ret, err);

	/* Adjust d depending on public key y */
	ret = _bip0340_set_scalar(&d, q, &Y); EG(ret, err);

	/* Compute the nonce in a deterministic way.
	 * First, we get the random auxilary data.
	 */
#ifdef NO_KNOWN_VECTORS
	/* NOTE: when we do not need self tests for known vectors,
	 * we can be strict about random function handler!
	 * This allows us to avoid the corruption of such a pointer.
	 */
	/* Sanity check on the handler before calling it */
	MUST_HAVE((rand == nn_get_random_mod), ret, err);
#endif
	ret = nn_init(&e, 0); EG(ret, err);
	ret = nn_one(&e); EG(ret, err);
	ret = nn_lshift(&e, &e, (bitcnt_t)(8 * q_len)); EG(ret, err);
	if(rand == NULL){
		rand = nn_get_random_mod;
	}
	ret = rand(&k, &e); EG(ret, err);
	dbg_nn_print("a", &k);

	MUST_HAVE((siglen >= q_len), ret, err);
	ret = nn_export_to_buf(&sig[0], q_len, &k); EG(ret, err);

	/* Compute the seed for the nonce computation */
	ret = _bip0340_hash((const u8*)BIP0340_AUX, sizeof(BIP0340_AUX) - 1,
		      &sig[0], q_len, hm, &h_ctx); EG(ret, err);
	ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);

	ret = nn_export_to_buf(&sig[0], q_len, &d); EG(ret, err);

	if(q_len > hm->digest_size){
		for(i = 0; i < hm->digest_size; i++){
			sig[i] ^= buff[i];
		}
		ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
				    &sig[0], q_len, hm, &h_ctx); EG(ret, err);
	}
	else{
		for(i = 0; i < q_len; i++){
			buff[i] ^= sig[i];
		}
		ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
				    &buff[0], hm->digest_size, hm, &h_ctx); EG(ret, err);
	}
	ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
	ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
	ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
	ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);

	/* Now import the semi-deterministic nonce modulo q */
	ret = nn_init_from_buf(&k, buff, hm->digest_size); EG(ret, err);
	ret = nn_mod(&k, &k, q); EG(ret, err);

	dbg_nn_print("k", &k);

	/* Fail if the nonce is zero */
	ret = nn_iszero(&k, &iszero); EG(ret, err);
	MUST_HAVE((!iszero), ret, err);

	/* Proceed with the modulation exponentiation kG */
#ifdef USE_SIG_BLINDING
	/* We use blinding for the scalar multiplication */
	ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
#else
	ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
#endif
	ret = prj_pt_unique(&kG, &kG); EG(ret, err);

	dbg_ec_point_print("(k G)", &kG);

	/* Update k depending on the kG y coordinate */
	ret = _bip0340_set_scalar(&k, q, &kG); EG(ret, err);

	/* Compute e */
	/* We export our r here */
	ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);
	ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
			    &sig[0], p_len, hm, &h_ctx); EG(ret, err);
	/* Export our public key */
	ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
	ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
	/* Update with the message */
	ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
	ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
	ret = nn_init_from_buf(&e, buff, hm->digest_size); EG(ret, err);
	ret = nn_mod(&e, &e, q); EG(ret, err);
	dbg_nn_print("e", &e);

	/* Export our r in the signature */
	dbg_nn_print("r", &(kG.X.fp_val));
	ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);

	/* Compute (k + ed) mod n */
#ifdef USE_SIG_BLINDING
	ret = nn_get_random_mod(&b, q); EG(ret, err);
	dbg_nn_print("b", &b);
#endif /* USE_SIG_BLINDING */

#ifdef USE_SIG_BLINDING
	/* Blind e with b */
	ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
	/* Blind k with b */
	ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */

	ret = nn_mod_mul(&e, &e, &d, q); EG(ret, err);
	ret = nn_mod_add(&e, &k, &e, q); EG(ret, err);

#ifdef USE_SIG_BLINDING
	/* Unblind */
	/* NOTE: we use Fermat's little theorem inversion for
	 * constant time here. This is possible since q is prime.
	 */
	ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
	ret = nn_mod_mul(&e, &e, &binv, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */

	/* Export our s in the signature */
	dbg_nn_print("s", &e);
	ret = nn_export_to_buf(&sig[p_len], q_len, &e); EG(ret, err);

err:
	PTR_NULLIFY(G);
	PTR_NULLIFY(q);
	PTR_NULLIFY(priv_key);
	PTR_NULLIFY(pub_key);
	PTR_NULLIFY(hm);

	prj_pt_uninit(&Y);
	nn_uninit(&k);
	nn_uninit(&e);
	nn_uninit(&d);

	return ret;
}

/* local helper for context sanity checks. Returns 0 on success, -1 on error. */
#define BIP0340_VERIFY_MAGIC ((word_t)(0x340175910abafcddULL))
#define BIP0340_VERIFY_CHECK_INITIALIZED(A, ret, err) \
	MUST_HAVE((((const void *)(A)) != NULL) && \
		  ((A)->magic == BIP0340_VERIFY_MAGIC), ret, err)

/*
 * Generic *internal* helper for BIP0340 verification initialization functions.
 * The function returns 0 on success, -1 on error.
 */
int _bip0340_verify_init(struct ec_verify_context *ctx,
			 const u8 *sig, u8 siglen)
{
	bitcnt_t p_bit_len, q_bit_len;
	u8 p_len, q_len;
	int ret, cmp;
	nn_src_t q;
	prj_pt Y;
	fp *rx;
	nn *s;
	u8 Pubx[NN_MAX_BYTE_LEN];

	/* First, verify context has been initialized */
	ret = sig_verify_check_initialized(ctx); EG(ret, err);

	/* Do some sanity checks on input params */
	ret = pub_key_check_initialized_and_type(ctx->pub_key, BIP0340); EG(ret, err);
	MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
		(ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
	MUST_HAVE((sig != NULL), ret, err);

	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);

	/* Make things more readable */
	q = &(ctx->pub_key->params->ec_gen_order);
	p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen;
	q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
	p_len = (u8)BYTECEIL(p_bit_len);
	q_len = (u8)BYTECEIL(q_bit_len);
	s = &(ctx->verify_data.bip0340.s);
	rx = &(ctx->verify_data.bip0340.r);

	MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
	MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
	MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);

	/* Copy the public key point to work on the unique
	 * affine representative.
	 */
	ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
	ret = prj_pt_unique(&Y, &Y); EG(ret, err);

	/* Extract r and s */
	ret = fp_init(rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err);
	ret = fp_import_from_buf(rx, &sig[0], p_len); EG(ret, err);
	ret = nn_init_from_buf(s, &sig[p_len], q_len); EG(ret, err);
	ret = nn_cmp(s, q, &cmp); EG(ret, err);
	MUST_HAVE((cmp < 0), ret, err);

	dbg_nn_print("r", &(rx->fp_val));
	dbg_nn_print("s", s);

	/* Initialize our hash context */
	ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
			    &sig[0], p_len, ctx->h,
			    &(ctx->verify_data.bip0340.h_ctx)); EG(ret, err);
	ret = fp_export_to_buf(&Pubx[0], p_len, &(Y.X)); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), &Pubx[0], p_len); EG(ret, err);
	ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);

	ctx->verify_data.bip0340.magic = BIP0340_VERIFY_MAGIC;

err:
	PTR_NULLIFY(q);
	PTR_NULLIFY(rx);
	PTR_NULLIFY(s);

	prj_pt_uninit(&Y);

	if (ret && (ctx != NULL)) {
		/*
		 * Signature is invalid. Clear data part of the context.
		 * This will clear magic and avoid further reuse of the
		 * whole context.
		 */
		IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0,
			     sizeof(bip0340_verify_data)));
	}

	return ret;
}

/*
 * Generic *internal* helper for BIP0340 verification update functions.
 * The function returns 0 on success, -1 on error.
 */
int _bip0340_verify_update(struct ec_verify_context *ctx,
			   const u8 *chunk, u32 chunklen)
{
	int ret;

	/*
	 * First, verify context has been initialized and public
	 * part too. This guarantees the context is an BIP0340
	 * verification one and we do not update() or finalize()
	 * before init().
	 */
	ret = sig_verify_check_initialized(ctx); EG(ret, err);
	BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err);

	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), chunk,
				chunklen);

err:
	return ret;
}

/*
 * Generic *internal* helper for BIP0340 verification finalization
 * functions. The function returns 0 on success, -1 on error.
 */
int _bip0340_verify_finalize(struct ec_verify_context *ctx)
{
	prj_pt_src_t G;
	nn_src_t s, q;
	fp_src_t r;
	nn e;
	prj_pt sG, eY, Y;
	u8 e_buf[MAX_DIGEST_SIZE];
	u8 hsize;
	int ret, iszero, isodd, cmp;

	ret = sig_verify_check_initialized(ctx); EG(ret, err);
	BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err);

	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);

	/* Zero init points */
	ret = local_memset(&sG, 0, sizeof(prj_pt)); EG(ret, err);
	ret = local_memset(&eY, 0, sizeof(prj_pt)); EG(ret, err);

	/* Make things more readable */
	G = &(ctx->pub_key->params->ec_gen);
	hsize = ctx->h->digest_size;
	q = &(ctx->pub_key->params->ec_gen_order);
	s = &(ctx->verify_data.bip0340.s);
	r = &(ctx->verify_data.bip0340.r);

	/* Copy the public key point to work on the unique
	 * affine representative.
	 */
	ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
	ret = prj_pt_unique(&Y, &Y); EG(ret, err);

	/* Compute e */
	ret = ctx->h->hfunc_finalize(&(ctx->verify_data.bip0340.h_ctx),
			&e_buf[0]); EG(ret, err);
	ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err);
	ret = nn_mod(&e, &e, q); EG(ret, err);

	dbg_nn_print("e", &e);

	/* Compute s G - e Y */
	ret = prj_pt_mul(&sG, s, G); EG(ret, err);
	ret = nn_mod_neg(&e, &e, q); EG(ret, err); /* compute -e = (q - e) mod q */
	/* Do we have to "lift" Y the public key ? */
	ret = nn_isodd(&(Y.Y.fp_val), &isodd); EG(ret, err);
	if(isodd){
		/* If yes, negate the y coordinate */
		ret = fp_neg(&(Y.Y), &(Y.Y)); EG(ret, err);
	}
	ret = prj_pt_mul(&eY, &e, &Y); EG(ret, err);
	ret = prj_pt_add(&sG, &sG, &eY); EG(ret, err);
	ret = prj_pt_unique(&sG, &sG); EG(ret, err);

	dbg_ec_point_print("(s G - e Y)", &sG);

	/* Reject point at infinity */
	ret = prj_pt_iszero(&sG, &iszero); EG(ret, err);
	MUST_HAVE((!iszero), ret, err);

	/* Reject non even Y coordinate */
	ret = nn_isodd(&(sG.Y.fp_val), &isodd); EG(ret, err);
	MUST_HAVE((!isodd), ret, err);

	/* Check the x coordinate against r */
	ret = nn_cmp(&(r->fp_val), &(sG.X.fp_val), &cmp); EG(ret, err);
	ret = (cmp == 0) ? 0 : -1;

err:
	PTR_NULLIFY(G);
	PTR_NULLIFY(s);
	PTR_NULLIFY(q);
	PTR_NULLIFY(r);

	nn_uninit(&e);
	prj_pt_uninit(&sG);
	prj_pt_uninit(&eY);
	prj_pt_uninit(&Y);

	/*
	 * We can now clear data part of the context. This will clear
	 * magic and avoid further reuse of the whole context.
	 */
	if(ctx != NULL){
		IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0,
			     sizeof(bip0340_verify_data)));
	}

	return ret;
}

/*
 * Helper to compute the seed to generate batch verification randomizing scalars.
 *
 */
/****************************************************/
/*
 * 32-bit integer manipulation macros (big endian)
 */
#ifndef GET_UINT32_LE
#define GET_UINT32_LE(n, b, i)                          \
do {                                                    \
        (n) =     ( ((u32) (b)[(i) + 3]) << 24 )        \
                | ( ((u32) (b)[(i) + 2]) << 16 )        \
                | ( ((u32) (b)[(i) + 1]) <<  8 )        \
                | ( ((u32) (b)[(i)    ])       );       \
} while( 0 )
#endif

#ifndef PUT_UINT32_LE
#define PUT_UINT32_LE(n, b, i)				\
do {							\
        (b)[(i) + 3] = (u8) ( (n) >> 24 );		\
        (b)[(i) + 2] = (u8) ( (n) >> 16 );		\
        (b)[(i) + 1] = (u8) ( (n) >>  8 );		\
        (b)[(i)    ] = (u8) ( (n)       );		\
} while( 0 )
#endif

#ifndef PUT_UINT32_BE
#define PUT_UINT32_BE(n, b, i)				\
do {							\
        (b)[(i)    ] = (u8) ( (n) >> 24 );		\
        (b)[(i) + 1] = (u8) ( (n) >> 16 );		\
        (b)[(i) + 2] = (u8) ( (n) >>  8 );		\
        (b)[(i) + 3] = (u8) ( (n)       );		\
} while( 0 )
#endif

#define _CHACHA20_ROTL_(x, y) (((x) << (y)) | ((x) >> ((sizeof(u32) * 8) - (y))))
#define CHACA20_ROTL(x, y) ((((y) < (sizeof(u32) * 8)) && ((y) > 0)) ? (_CHACHA20_ROTL_(x, y)) : (x))

#define CHACHA20_QROUND(a, b, c, d) do {			\
	(a) += (b);						\
	(d) ^= (a);						\
	(d) = CHACA20_ROTL((d), 16);				\
	(c) += (d);						\
	(b) ^= (c);						\
	(b) = CHACA20_ROTL((b), 12);				\
	(a) += (b);						\
	(d) ^= (a);						\
	(d) = CHACA20_ROTL((d), 8);				\
	(c) += (d);						\
	(b) ^= (c);						\
	(b) = CHACA20_ROTL((b), 7);				\
} while(0)

#define CHACHA20_INNER_BLOCK(s) do {				\
	CHACHA20_QROUND(s[0], s[4], s[ 8], s[12]);		\
	CHACHA20_QROUND(s[1], s[5], s[ 9], s[13]);		\
	CHACHA20_QROUND(s[2], s[6], s[10], s[14]);		\
	CHACHA20_QROUND(s[3], s[7], s[11], s[15]);		\
	CHACHA20_QROUND(s[0], s[5], s[10], s[15]);		\
	CHACHA20_QROUND(s[1], s[6], s[11], s[12]);		\
	CHACHA20_QROUND(s[2], s[7], s[ 8], s[13]);		\
	CHACHA20_QROUND(s[3], s[4], s[ 9], s[14]);		\
} while(0)

#define CHACHA20_MAX_ASKED_LEN 64

ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_chacha20_block(const u8 key[32], const u8 nonce[12], u32 block_counter, u8 *stream, u32 stream_len){
	int ret;
	u32 state[16];
	u32 initial_state[16];
	unsigned int i;

	MUST_HAVE((stream != NULL), ret, err);
	MUST_HAVE((stream_len <= CHACHA20_MAX_ASKED_LEN), ret, err);

	/* Initial state */
	state[0] = 0x61707865;
	state[1] = 0x3320646e;
	state[2] = 0x79622d32;
	state[3] = 0x6b206574;

	for(i = 4; i < 12; i++){
		GET_UINT32_LE(state[i], key, (4 * (i - 4)));
	}
	state[12] = block_counter;
	for(i = 13; i < 16; i++){
		GET_UINT32_LE(state[i], nonce, (4 * (i - 13)));
	}

	/* Core loop */
	ret = local_memcpy(initial_state, state, sizeof(state)); EG(ret, err);
	for(i = 0; i < 10; i++){
		CHACHA20_INNER_BLOCK(state);
	}
	/* Serialize and output the block */
	for(i = 0; i < 16; i++){
		u32 tmp = (u32)(state[i] + initial_state[i]);
		PUT_UINT32_LE(tmp, (u8*)(&state[i]), 0);
	}
	ret = local_memcpy(stream, &state[0], stream_len);

err:
	return ret;
}

ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_one_scalar(const u8 *seed, u32 seedlen,
									      u8 *scalar, u32 scalar_len, u32 num)
{
	int ret;
	u8 nonce[12];

	/* Sanity check for ChaCha20 */
	MUST_HAVE((seedlen == SHA256_DIGEST_SIZE) && (scalar_len <= CHACHA20_MAX_ASKED_LEN), ret, err);

	/* NOTE: nothing in the BIP340 specification fixes the nonce for
	 * ChaCha20. We simply use 0 here for the nonce. */
	ret = local_memset(nonce, 0, sizeof(nonce)); EG(ret, err);

	/* Use our CSPRNG based on ChaCha20 to generate the scalars */
	ret = _bip0340_chacha20_block(seed, nonce, num, scalar, scalar_len);

err:
	return ret;
}

ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_scalars(const u8 *seed, u32 seedlen,
									   u8 *scalar, u32 scalar_len,
									   u32 *num, nn_src_t q,
									   bitcnt_t q_bit_len, u8 q_len,
									   nn_t a)
{
	int ret, iszero, cmp;
	u32 size, remain;

	MUST_HAVE((seed != NULL) && (scalar != NULL) && (num != NULL) && (a != NULL), ret, err);
	MUST_HAVE((scalar_len >= q_len), ret, err);

gen_scalar_again:
	size = remain = 0;
	while(size < q_len){
		MUST_HAVE((*num) < 0xffffffff, ret, err);
		remain = ((q_len - size) < CHACHA20_MAX_ASKED_LEN) ? (q_len - size): CHACHA20_MAX_ASKED_LEN;
		ret = _bip0340_compute_batch_csprng_one_scalar(seed, seedlen,
							       &scalar[size], remain,
							       (*num)); EG(ret, err);
		(*num)++;
		size += remain;
	}
	if((q_bit_len % 8) != 0){
		/* Handle the cutoff when q_bit_len is not a byte multiple */
		scalar[0] &= (u8)((0x1 << (q_bit_len % 8)) - 1);
	}
	/* Import the scalar */
	ret = nn_init_from_buf(a, scalar, q_len); EG(ret, err);
	/* Check if the scalar is between 1 and q-1 */
	ret = nn_iszero(a, &iszero); EG(ret, err);
	ret = nn_cmp(a, q, &cmp); EG(ret, err);
	if((iszero) || (cmp >= 0)){
		goto gen_scalar_again;
	}

	ret = 0;
err:
	return ret;
}

ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_seed(const u8 **s, const u8 *s_len,
								        const ec_pub_key **pub_keys,
								        const u8 **m, const u32 *m_len, u32 num,
								        u8 p_len, u8 *seed, u32 seedlen)
{
	int ret;
	u32 i;
	hash_context h_ctx;
	u8 Pubx[NN_MAX_BYTE_LEN];
	const hash_mapping *hm;

	/* NOTE: sanity checks on inputs are performed by the upper layer */

	ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);

        /* Get our hash mapping for SHA-256 as we need a fixed 256-bit key
	 * for keying our ChaCha20 CSPRNG
	 */
        ret = get_hash_by_type(SHA256, &hm); EG(ret, err);
        MUST_HAVE((hm != NULL), ret, err);

	MUST_HAVE((seedlen == hm->digest_size), ret, err);

	/* As per specification, seed = seed_hash(pk1..pku || m1..mu || sig1..sigu), instantiated
	 * with SHA-256 */
	ret = hm->hfunc_init(&h_ctx); EG(ret, err);
	for(i = 0; i < num; i++){
		ret = fp_export_to_buf(&Pubx[0], p_len, &(pub_keys[i]->y.X)); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
	}
	for(i = 0; i < num; i++){
		ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
	}
	for(i = 0; i < num; i++){
		ret = hm->hfunc_update(&h_ctx, s[i], s_len[i]); EG(ret, err);
	}
	ret = hm->hfunc_finalize(&h_ctx, seed);

err:
	return ret;
}

/* Batch verification function:
 * This function takes multiple signatures/messages/public keys, and
 * checks in an optimized way all the signatures.
 *
 * This returns 0 if *all* the signatures are correct, and -1 if at least
 * one signature is not correct.
 *
 */
static int _bip0340_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
		                           const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
					   hash_alg_type hash_type, const u8 **adata, const u16 *adata_len)
{
	nn_src_t q = NULL;
	prj_pt_src_t G = NULL;
	prj_pt_t R = NULL, Y = NULL;
	prj_pt Tmp, R_sum, P_sum;
	nn S, S_sum, e, a;
	fp rx;
	u8 hash[MAX_DIGEST_SIZE];
	u8 Pubx[NN_MAX_BYTE_LEN];
	const ec_pub_key *pub_key, *pub_key0;
	int ret, iszero, isodd, cmp;
	prj_pt_src_t pub_key_y;
	hash_context h_ctx;
	const hash_mapping *hm;
	ec_shortw_crv_src_t shortw_curve;
	ec_alg_type key_type = UNKNOWN_ALG;
	bitcnt_t p_bit_len, q_bit_len;
	u8 p_len, q_len;
	u16 hsize;
	u32 i;
	u8 chacha20_seed[SHA256_DIGEST_SIZE];
	u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
	u32 chacha20_scalar_counter = 1;

	Tmp.magic = R_sum.magic = P_sum.magic = WORD(0);
	S.magic = S_sum.magic = e.magic = a.magic = WORD(0);
	rx.magic = WORD(0);

	FORCE_USED_VAR(adata_len);
	FORCE_USED_VAR(adata);

        /* First, some sanity checks */
        MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);
        /* We need at least one element in our batch data bags */
        MUST_HAVE((num > 0), ret, err);

	/* Zeroize buffers */
	ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
	ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
	ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
	ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err);

        pub_key0 = pub_keys[0];
        MUST_HAVE((pub_key0 != NULL), ret, err);

        /* Get our hash mapping */
        ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
        hsize = hm->digest_size;
        MUST_HAVE((hm != NULL), ret, err);

	for(i = 0; i < num; i++){
		u8 siglen;
		const u8 *sig = NULL;

		ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err);

		/* Make things more readable */
		pub_key = pub_keys[i];

		/* Sanity check that all our public keys have the same parameters */
		MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);

		q = &(pub_key->params->ec_gen_order);
		shortw_curve = &(pub_key->params->ec_curve);
		pub_key_y = &(pub_key->y);
		key_type = pub_key->key_type;
		G = &(pub_key->params->ec_gen);
		p_bit_len = pub_key->params->ec_fp.p_bitlen;
		q_bit_len = pub_key->params->ec_gen_order_bitlen;
		p_len = (u8)BYTECEIL(p_bit_len);
		q_len = (u8)BYTECEIL(q_bit_len);

                /* Check given signature length is the expected one */
		siglen = s_len[i];
		sig = s[i];
		MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
		MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err);

		/* Check the key type versus the algorithm */
		MUST_HAVE((key_type == sig_type), ret, err);

                if(i == 0){
                        /* Initialize our sums to zero/point at infinity */
                        ret = nn_init(&S_sum, 0); EG(ret, err);
                        ret = prj_pt_init(&R_sum, shortw_curve); EG(ret, err);
                        ret = prj_pt_zero(&R_sum); EG(ret, err);
                        ret = prj_pt_init(&P_sum, shortw_curve); EG(ret, err);
                        ret = prj_pt_zero(&P_sum); EG(ret, err);
			ret = prj_pt_init(&Tmp, shortw_curve); EG(ret, err);
                        ret = nn_init(&e, 0); EG(ret, err);
			ret = nn_init(&a, 0); EG(ret, err);
			/* Compute the ChaCha20 seed */
			ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
								 p_len, chacha20_seed,
								 sizeof(chacha20_seed)); EG(ret, err);
		}
		else{
			/* Get a pseudo-random scalar a for randomizing the linear combination */
			ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
								    chacha20_scalar, sizeof(chacha20_scalar),
								    &chacha20_scalar_counter, q,
								    q_bit_len, q_len, &a); EG(ret, err);
		}

		/***************************************************/
		/* Extract r and s */
		ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
		ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
		ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err);
		ret = nn_cmp(&S, q, &cmp); EG(ret, err);
		MUST_HAVE((cmp < 0), ret, err);

		dbg_nn_print("r", &(rx.fp_val));
		dbg_nn_print("s", &S);

		/***************************************************/
		/* Add S to the sum */
		/* Multiply S by a */
		if(i != 0){
			ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
		}
		ret = nn_mod_add(&S_sum, &S_sum, &S, q); EG(ret, err);

		/***************************************************/
		R = &Tmp;
		/* Compute R from rx */
		ret = fp_copy(&(R->X), &rx); EG(ret, err);
		ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
		/* "Lift" R by choosing the even solution */
		ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
		if(isodd){
			ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
		}
		ret = fp_one(&(R->Z)); EG(ret, err);
		/* Now multiply R by a */
		if(i != 0){
			ret = _prj_pt_unprotected_mult(R, &a, R); EG(ret, err);
		}
		/* Add to the sum */
		ret = prj_pt_add(&R_sum, &R_sum, R); EG(ret, err);
		dbg_ec_point_print("aR", R);

		/***************************************************/
		/* Compute P and add it to P_sum */
		Y = &Tmp;
		/* Copy the public key point to work on the unique
		 * affine representative.
		 */
		ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
		ret = prj_pt_unique(Y, Y); EG(ret, err);
		/* Do we have to "lift" Y the public key ? */
		ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
		if(isodd){
			/* If yes, negate the y coordinate */
			ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
		}
		dbg_ec_point_print("Y", Y);
		/* Compute e */
		ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
				    &sig[0], p_len, hm,
				    &h_ctx); EG(ret, err);
		ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
		ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);

		ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
		ret = nn_mod(&e, &e, q); EG(ret, err);

		dbg_nn_print("e", &e);

		/* Multiply e by 'a' */
		if(i != 0){
			ret = nn_mod_mul(&e, &e, &a, q); EG(ret, err);
		}
		ret = _prj_pt_unprotected_mult(Y, &e, Y); EG(ret, err);
		dbg_ec_point_print("eY", Y);
		/* Add to the sum */
		ret = prj_pt_add(&P_sum, &P_sum, Y); EG(ret, err);
	}

	/* Sanity check */
        MUST_HAVE((q != NULL) && (G != NULL), ret, err);

	/* Compute S_sum * G */
	ret = nn_mod_neg(&S_sum, &S_sum, q); EG(ret, err); /* -S_sum = q - S_sum*/
	ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err);
	/* Add P_sum and R_sum */
	ret = prj_pt_add(&Tmp, &Tmp, &R_sum); EG(ret, err);
	ret = prj_pt_add(&Tmp, &Tmp, &P_sum); EG(ret, err);
	/* The result should be point at infinity */
	ret = prj_pt_iszero(&Tmp, &iszero); EG(ret, err);
	ret = (iszero == 1) ? 0 : -1;

err:
        PTR_NULLIFY(q);
        PTR_NULLIFY(pub_key);
        PTR_NULLIFY(pub_key0);
        PTR_NULLIFY(shortw_curve);
        PTR_NULLIFY(pub_key_y);
        PTR_NULLIFY(G);
        PTR_NULLIFY(R);
        PTR_NULLIFY(Y);

        prj_pt_uninit(&R_sum);
        prj_pt_uninit(&P_sum);
        prj_pt_uninit(&Tmp);
        nn_uninit(&S);
        nn_uninit(&S_sum);
        nn_uninit(&e);
        nn_uninit(&a);
	fp_uninit(&rx);

	return ret;
}

static int _bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
		                 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
				 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
				 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
{
	nn_src_t q = NULL;
	prj_pt_src_t G = NULL;
	prj_pt_t R = NULL, Y = NULL;
	nn S, a;
	nn_t e = NULL;
	fp rx;
	u8 hash[MAX_DIGEST_SIZE];
	u8 Pubx[NN_MAX_BYTE_LEN];
	const ec_pub_key *pub_key, *pub_key0;
	int ret, iszero, isodd, cmp;
	prj_pt_src_t pub_key_y;
	hash_context h_ctx;
	const hash_mapping *hm;
	ec_shortw_crv_src_t shortw_curve;
	ec_alg_type key_type = UNKNOWN_ALG;
	bitcnt_t p_bit_len, q_bit_len = 0;
	u8 p_len, q_len;
	u16 hsize;
	u32 i;
        /* NN numbers and points pointers */
        verify_batch_scratch_pad *elements = scratch_pad_area;
        u64 expected_len;
	u8 chacha20_seed[SHA256_DIGEST_SIZE];
	u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
	u32 chacha20_scalar_counter = 1;

	S.magic = a.magic = WORD(0);
	rx.magic = WORD(0);

	FORCE_USED_VAR(adata_len);
	FORCE_USED_VAR(adata);

        /* First, some sanity checks */
        MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);

	MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
	MUST_HAVE(((2 * num) >= num), ret, err);
        MUST_HAVE(((2 * num) + 1) >= num, ret, err);

	/* Zeroize buffers */
	ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
	ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
	ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
	ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err);

        /* In oder to apply the algorithm, we must have at least two
         * elements to verify. If this is not the case, we fallback to
         * the regular "no memory" version.
         */
        if(num <= 1){
                if(scratch_pad_area == NULL){
                        /* We do not require any memory in this case */
                        (*scratch_pad_area_len) = 0;
			ret = 0;
			goto err;
                }
                else{
                        ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
                                                              hash_type, adata, adata_len); EG(ret, err);
			goto err;
                }
        }

        expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad);
        MUST_HAVE((expected_len < 0xffffffff), ret, err);

        if(scratch_pad_area == NULL){
                /* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers
                 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices
                 */
                (*scratch_pad_area_len) = (u32)expected_len;
                ret = 0;
                goto err;
        }
        else{
                MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err);
        }

        pub_key0 = pub_keys[0];
        MUST_HAVE((pub_key0 != NULL), ret, err);

        /* Get our hash mapping */
        ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
        hsize = hm->digest_size;
        MUST_HAVE((hm != NULL), ret, err);

	for(i = 0; i < num; i++){
		u8 siglen;
		const u8 *sig = NULL;

		ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err);

		/* Make things more readable */
		pub_key = pub_keys[i];

		/* Sanity check that all our public keys have the same parameters */
		MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);

		q = &(pub_key->params->ec_gen_order);
		shortw_curve = &(pub_key->params->ec_curve);
		pub_key_y = &(pub_key->y);
		key_type = pub_key->key_type;
		G = &(pub_key->params->ec_gen);
		p_bit_len = pub_key->params->ec_fp.p_bitlen;
		q_bit_len = pub_key->params->ec_gen_order_bitlen;
		p_len = (u8)BYTECEIL(p_bit_len);
		q_len = (u8)BYTECEIL(q_bit_len);

                /* Check given signature length is the expected one */
		siglen = s_len[i];
		sig = s[i];
		MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
		MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err);

		/* Check the key type versus the algorithm */
		MUST_HAVE((key_type == sig_type), ret, err);

                if(i == 0){
                        /* Initialize our sums to zero/point at infinity */
			ret = nn_init(&a, 0); EG(ret, err);
			ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err);
			ret = prj_pt_copy(&elements[(2 * num)].point, G); EG(ret, err);
			/* Compute the ChaCha20 seed */
			ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
								 p_len, chacha20_seed,
								 sizeof(chacha20_seed)); EG(ret, err);
		}
		else{
			/* Get a pseudo-random scalar a for randomizing the linear combination */
			ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
								    chacha20_scalar, sizeof(chacha20_scalar),
								    &chacha20_scalar_counter, q,
								    q_bit_len, q_len, &a); EG(ret, err);
		}

		/***************************************************/
		/* Extract r and s */
		ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
		ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
		ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err);
		ret = nn_cmp(&S, q, &cmp); EG(ret, err);
		MUST_HAVE((cmp < 0), ret, err);

		dbg_nn_print("r", &(rx.fp_val));
		dbg_nn_print("s", &S);

		/***************************************************/
		/* Add S to the sum */
		/* Multiply S by a */
		if(i != 0){
			ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
		}
		ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number,
				 &S, q); EG(ret, err);

		/***************************************************/
		/* Initialize R */
		R = &elements[i].point;
		ret = prj_pt_init(R, shortw_curve); EG(ret, err);
		/* Compute R from rx */
		ret = fp_copy(&(R->X), &rx); EG(ret, err);
		ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
		/* "Lift" R by choosing the even solution */
		ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
		if(isodd){
			ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
		}
		ret = fp_one(&(R->Z)); EG(ret, err);

		if(i != 0){
			ret = nn_init(&elements[i].number, 0); EG(ret, err);
			ret = nn_copy(&elements[i].number, &a); EG(ret, err);
		}
		else{
			ret = nn_init(&elements[i].number, 0); EG(ret, err);
			ret = nn_one(&elements[i].number); EG(ret, err);
		}
		dbg_ec_point_print("R", R);

		/***************************************************/
		/* Compute P and add it to P_sum */
		Y = &elements[num + i].point;
		/* Copy the public key point to work on the unique
		 * affine representative.
		 */
		ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
		ret = prj_pt_unique(Y, Y); EG(ret, err);
		/* Do we have to "lift" Y the public key ? */
		ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
		if(isodd){
			/* If yes, negate the y coordinate */
			ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
		}
		dbg_ec_point_print("Y", Y);
		/* Compute e */
		/* Store the coefficient */
		e = &elements[num + i].number;
		ret = nn_init(e, 0); EG(ret, err);
		ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
				    &sig[0], p_len, hm,
				    &h_ctx); EG(ret, err);
		ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
		ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);

		ret = nn_init_from_buf(e, hash, hsize); EG(ret, err);
		ret = nn_mod(e, e, q); EG(ret, err);

		dbg_nn_print("e", e);

		/* Multiply e by 'a' */
		if(i != 0){
			ret = nn_mod_mul(e, e, &a, q); EG(ret, err);
		}
	}

        /* Sanity check */
        MUST_HAVE((q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err);

        /********************************************/
        /****** Bos-Coster algorithm ****************/
        ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len);
	if(ret){
		if(ret == -2){
			/* In case of Bos-Coster time out, we fall back to the
			 * slower regular batch verification.
			 */
                        ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
                                                              hash_type, adata, adata_len); EG(ret, err);
		}
		goto err;
	}

        /* The first element should contain the sum: it should
         * be equal to zero. Reject the signature if this is not
         * the case.
         */
	ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err);
        ret = iszero ? 0 : -1;

err:
        PTR_NULLIFY(q);
        PTR_NULLIFY(e);
        PTR_NULLIFY(pub_key);
        PTR_NULLIFY(pub_key0);
        PTR_NULLIFY(shortw_curve);
        PTR_NULLIFY(pub_key_y);
        PTR_NULLIFY(G);
        PTR_NULLIFY(R);
        PTR_NULLIFY(Y);

        /* Unitialize all our scratch_pad_area */
        if((scratch_pad_area != NULL) && (scratch_pad_area_len != NULL)){
                IGNORE_RET_VAL(local_memset((u8*)scratch_pad_area, 0, (*scratch_pad_area_len)));
        }

        nn_uninit(&S);
        nn_uninit(&a);
	fp_uninit(&rx);

	return ret;
}

int bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
	                 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
			 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
			 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
{
	int ret;

	if(scratch_pad_area != NULL){
		MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
		ret = _bip0340_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type,
				            hash_type, adata, adata_len,
				            scratch_pad_area, scratch_pad_area_len); EG(ret, err);

	}
	else{
		ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
					              hash_type, adata, adata_len); EG(ret, err);
	}

err:
	return ret;
}

#else /* defined(WITH_SIG_BIP0340) */

/*
 * Dummy definition to avoid the empty translation unit ISO C warning
 */
typedef int dummy;
#endif /* defined(WITH_SIG_BIP0340) */