mimblewimble / secp256k1-zkp Goto Github PK

Some scalars add to the wrong number (see webwarrior-ws@1c27f70).
Numbers in that commit were cross-checked using Wolfram Alpha, Python and Pharo.
So I assume there is either a bug in addition or in byte array representation of scalars.

Note that when built on a system using openssl 3.0, (more recent arch distros, for instance), the test

run_ecdsa_der_parse on line 4654 of tests.c fails.

I have not looked into the reason, (this function is unused by grin) but we'll likely need to revisit the build when most of the world moves on to openssl 3.

Gary Yu @garyyu 14:35
Oh, I can’t find file aggsig/main_impl.h in upstream BlockstreamResearch/secp256k1-zkp#23 ? @yeastplume
but the first commit message of this file is updating BPs with master and upstream PR 23, what’s exact origin writer of this aggsig/main_impl.h?

Yeastplume @yeastplume 16:18
I wrote the aggsig code based on something andrew did earlier. It doesn't exist anywhere upstream.

Gary Yu @garyyu 16:19
Ok @yeastplume

" I wrote the aggsig code based on something andrew did earlier."

The git commit log lost? I can’t find the andrew’s record.

Yeastplume @yeastplume 16:21
it was in a PR that was withdrawn
and it was set up to do multisig while holding a context internally, which didn't really work for us, hence me rewriting it

Gary Yu @garyyu 16:21
Oh, that make sense.

Gary Yu @garyyu 16:23
@yeastplume Could you add yourself into the header?

/**********************************************************************
 * Copyright (c) 2017 Andrew Poelstra, Pieter Wuille                  *
 * Distributed under the MIT software license, see the accompanying   *
 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
 **********************************************************************/

It’s awkward I send question to Pieter Wuille about this code, but actually it’s written by you or/and Andrew.

Yeastplume @yeastplume 16:26
at some point we'll add grin developers to it

Gary Yu @garyyu 16:30
👍 I will submit an issue to remind you to change this,...

If I understand it correctly, then the blind and nonce can be chosen independently (even if the rust api sets nonce = blind) when creating and unwinding bulletproofs. However, if nonce != blind, then only the first 32 bytes of the message can be unwinded as in the following test which can be inserted into perdersen.rs.

	#[test]
	fn test_bullet_nonce_neq_blind() {
		use std;
		use super::*;
		let secp = Secp256k1::with_caps(ContextFlag::Commit);
		let mut rng = OsRng::new().unwrap();
		let value = 1234567;
		let blind = SecretKey::new(&secp, &mut rng);
		let nonce = SecretKey::new(&secp, &mut rng);
		//let nonce = blind; // this works
		let mut msg = [0u8; 64];
		rng.fill_bytes(&mut msg);

		// ffi structures
		let n_bits = 64;
		let mut proof = [0; constants::MAX_PROOF_SIZE];
		let mut plen = constants::MAX_PROOF_SIZE as size_t;
		let extra_data = vec![];

		// create proof
		let success = unsafe {
			ffi::secp256k1_bulletproof_rangeproof_prove_single_w_scratch(
				secp.ctx,
				proof.as_mut_ptr(),
				&mut plen,
				value,
				blind.as_ptr(),
				constants::GENERATOR_H.as_ptr(),
				n_bits as size_t,
				nonce.as_ptr(),
				extra_data.as_ptr(),
				extra_data.len() as size_t,
				msg.as_ptr()
			) == 1
		};
		assert!(success);

		// unwind proof
		let mut unwinded_msg = [0u8; 64];
		let commit = secp.commit(value, blind).unwrap();
		let success = unsafe {
			ffi::secp256k1_bulletproof_rangeproof_unwind_message(
				secp.ctx,
				proof.as_ptr(),
				plen as size_t,
				commit.as_ptr(),
				n_bits as size_t,
				constants::GENERATOR_H.as_ptr(),
				extra_data.as_ptr(),
				extra_data.len() as size_t,
				nonce.as_ptr(),
				unwinded_msg.as_mut_ptr(),
			) == 1
		};
		assert!(success);

		println!("msg:     {:?}", msg.to_vec());
		println!("unwinded:{:?}", unwinded_msg.to_vec());

		for i in 0..msg.len() {
			assert_eq!(msg[i], unwinded_msg[i]);
		}
	}

From here, the library use builtin num instead of GMP num.

#define USE_NUM_NONE 1
#define USE_FIELD_INV_BUILTIN 1
#define USE_SCALAR_INV_BUILTIN 1
#define USE_FIELD_10X26 1
#define USE_SCALAR_8X32 1

I tested it on local, GMP version is 3 times faster than builtin. What's the consideration?

I have been trying to make sense of the proof array filled in by secp256k1_bulletproof_rangeproof_prove, but its format doesn't seem to be documented, so I'm left trying to infer it from the code. Is this documented somewhere?

My assumption is that this is incorrect:

Am I wrong?

The following is called in the various range proof functions -

secp256k1_generator_load(&genp, gen);

We're not passing in gen from Grin (via rust-secp256k1-zkp) and it is not clear to me what we need to be doing here.

Gary Yu @garyyu 12:10
If nobody against (I suppose), I’m going to enable the Travis-CI for our secp256k1-zkp repo, some test codes can’t build and not good. With Travis-CI we can avoid it in the future.

Ignotus Peverell @ignopeverell 12:14
@garyyu

Gary Yu @garyyu 12:40
(Insufficient permissions)
perhaps only you can do that @ignopeverell

Upstream is the Elements project code with Bulletproof PR 23 applied:
BlockstreamResearch/secp256k1-zkp#23

Downstream is this repository, as of commit 4d64b7b

The major differences are:

• We've made additions to the bulletproof code, hiding a four byte BIP32 identifier into the nonce 'alpha'. This was just an extension to work Andrew had already done to allow Proofs to be rewound
• Changes to bulletproofs to allow for multi party proofs. The relevant PR with those changes is:
  #24
• A completely custom aggsig module that doesn't exist upstream, at https://github.com/mimblewimble/secp256k1-zkp/tree/master/src/modules/aggsig
  This was originally based on Andrew's code, however that code was never particularly reviewed and it's been re-written over time by us to suit Grin's requirements.

Diffs of the include and src directories are here:

diffs_include.txt
diffs_src.txt

Just putting an issue here to keep track of this.. the /aggsig branch has been created, which is:

master
+bitcoin-core/secp256k1#486
+bitcoin-core/secp256k1#461

+Manual tweaks and fixes to get compile/test working, particularly updates to ec_mult functionality as per 486

All tests seem to run without issue.

Please don't make any changes to master without checking with me first, as it would be nice to keep this branch mergeable ... this will have the potential to get very messy if we don't manage changes here properly.

Is it possible to build this library with MinGW in windows 7? How can I do it?

Gary Yu @garyyu 11:00
@jaspervdm Now I remember where I saw e = hash(P,R,m) firstly.
https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L72-L81

And we both agree to be compatible with BIP-schnorr, that’s why we use e = hash(R,P,m):
https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L45-L57

We should not mix 2 different definition of e. Please let's stick to BIP-schnorr, and correct the https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L72-L81

Will give a PR on this.

https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L498-L499

    /* just going to inefficiently allocate every time */
    secp256k1_scratch_space *scratch = secp256k1_scratch_space_create(ctx, 1024*4096);

Mark here: This line need an optimization, to avoid 4M bytes RAM allocation on each call. Will give a PR on this.

It turned out that the Pedersen commitment tests were disabled. I re-enabled them in #34 but some of the tests are broken.

There is no secp256k1_pedersen_commit_sum in src/modules/rangeproof/main_impl.h.

Grin depends on this via rust-secp256k1-zkp

See here for what we have in Grin itself -
https://github.com/ignopeverell/grin/blob/44c8f9e22dad35d7bac6b6c37e482053052e2ba9/secp256k1zkp/depend/secp256k1-zkp/src/modules/rangeproof/main_impl.h#L107

Hello.

I think there is a related-key attack in the way you produce Schnorr signatures.

sizeof(buf-1) = 8
sizeof(buf) - 1 = 32

so to my understanding you're copying only 8 bytes of the public key.

Therefore, if the signature
(s, e) is verified by H(_ || sG - eX) = e for public key X = xG
then, the signature
(s+ev, e) is verified by H(_ || (s+ev)G - e(X+vG)) = e for public key X + vG for any v in \ZZ_p for which X + vG has the same leading 64 bits of X.

Am I doing something wrong in here? Could you help me understand?

I tryed to build lirary on Ubuntu 16.04 and met with this error:

gcc -I. -g -O2 -Wall -Wextra -Wno-unused-function -c src/gen_context.c -o gen_context.o
gcc gen_context.o -o gen_context
./gen_context
  CC       src/libsecp256k1_la-secp256k1.lo
In file included from src/field_impl.h:19:0,
                 from src/secp256k1.c:11:
src/field_5x52_impl.h:165:12: error: conflicting types for ‘secp256k1_fe_normalizes_to_zero’
 static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r) {
            ^
In file included from src/field_5x52_impl.h:16:0,
                 from src/field_impl.h:19,
                 from src/secp256k1.c:11:
src/field.h:46:12: note: previous declaration of ‘secp256k1_fe_normalizes_to_zero’ was here
 static int secp256k1_fe_normalizes_to_zero(const secp256k1_fe *r);
            ^
Makefile:1107: ошибка выполнения рецепта для цели «src/libsecp256k1_la-secp256k1.lo»
make: *** [src/libsecp256k1_la-secp256k1.lo] Ошибка 1

How can I fix it?

see https://twitter.com/pwuille/status/1309722142607515648

https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L278-L282

    /* finalize */
    secp256k1_scalar_get_b32(sig64, &sec);
    secp256k1_ge_set_gej(&final, &pubnonce_j);
    secp256k1_fe_normalize_var(&final.x);
    secp256k1_fe_get_b32(sig64 + 32, &final.x);

Mark here: we're using (s,r) format for signature, which is not the convention.
@yeastplume @jaspervdm Please confirm whether or not we need to correct this?

Conventionally, people stick to (r,s) format for signature.
For example:

• For ECDSA: https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/src/ecdsa_impl.h#L194-L197
• bip-schnorr: https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

def schnorr_sign(msg, seckey):
    k = sha256(seckey.to_bytes(32, byteorder="big") + msg) % n
    R = point_mul(G, k)
    if jacobi(R[1]) != 1:
        k = n - k
    e = sha256(R[0].to_bytes(32, byteorder="big") + bytes_point(point_mul(G, seckey)) + msg) % n
    return R[0].to_bytes(32, byteorder="big") + ((k + e * seckey) % n).to_bytes(32, byteorder="big")

• Wiki: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

7. The signature is the pair (r,s).

This function can converts a pedersent commit to a pubkey

SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_pedersen_commitment_to_pubkey(
  const secp256k1_context* ctx,
  secp256k1_pubkey* pubkey,
  const secp256k1_pedersen_commitment* commit
);

How to converts a pubkey to pedersent commit ?

https://github.com/mimblewimble/secp256k1-zkp/blob/master/src/modules/aggsig/main_impl.h#L137-L138

int secp256k1_aggsig_generate_nonce_single(const secp256k1_context* ctx, secp256k1_scalar *secnonce, secp256k1_gej* pubnonce, secp256k1_rfc6979_hmac_sha256* rng) {
    int retry;
    ...
    /* generate nonce from the RNG */
    do {
        secp256k1_rfc6979_hmac_sha256_generate(rng, data, 32);
        secp256k1_scalar_set_b32(secnonce, data, &retry);
        retry |= secp256k1_scalar_is_zero(secnonce);
    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */
    ...

2 problems here:

• Variable retry should give zero initialization
• The while loop looks like a trap to infinite loop. If retry becomes not zero, then loop forever.

I guess retry |= should be retry = . Please confirm if it's.

Hey, I'm wondering - what is the code that generated the jubjub circuits that are benchmarked? Couldn't find it in the repository.

One of building job: BUILD=distcheck will fail.

$ make  dist-gzip am__post_remove_distdir='@:'
make: *** No rule to make target 'src/bench_aggsig.c', needed by 'distdir'.  Stop.

Before we find a fix on the Makefile for this, I have to disable it to let all remaining 38 building jobs works for Travis-CI.

How to produce? You can run the following script on Linux:

#!/bin/sh

export FIELD=auto
export BIGNUM=auto
export SCALAR=auto
export ENDOMORPHISM=no
export STATICPRECOMPUTATION=yes
export ASM=no
export BUILD=check
export EXTRAFLAGS=
export HOST=
export ECDH=no
export RECOVERY=no
export EXPERIMENTAL=no
export JNI=no
export GUAVA_URL=https://search.maven.org/remotecontent?filepath=com/google/guava/guava/18.0/guava-18.0.jar
export GUAVA_JAR=src/java/guava/guava-18.0.jar
export BUILD=distcheck
export TRAVIS_COMPILER=gcc
export CC=gcc
export CC_FOR_BUILD=gcc
export CASHER_DIR=${TRAVIS_HOME}/.casher
gcc --version
mkdir -p `dirname $GUAVA_JAR`
if [ ! -f $GUAVA_JAR ]; then wget $GUAVA_URL -O $GUAVA_JAR; fi
# ./autogen.sh
if [ -n "$HOST" ]; then export USE_HOST="--host=$HOST"; fi
if [ "x$HOST" = "xi686-linux-gnu" ]; then export CC="$CC -m32"; fi
./configure --enable-experimental=$EXPERIMENTAL --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION --enable-module-ecdh=$ECDH --enable-module-recovery=$RECOVERY --enable-module-generator=$GENERATOR --enable-module-commitment=$COMMITMENT --enable-module-rangeproof=$RANGEPROOF --enable-module-bulletproof=$BULLETPROOF --enable-module-whitelist=$WHITELIST --enable-module-surjectionproof=$SURJECTIONPROOF --enable-jni=$JNI $EXTRAFLAGS $USE_HOST && make -j2 $BUILD

is this repository used by Grin?

since there are several similar ones, so I am not sure about this.