[about homomorphic update pedersen commitments]

[jscode017]

Hi I am new to this open-source community
Firstly, I want to say thank you to an amazing library
And may I ask that is there an implementation of semi homomorphic update of Pedersen commitments?
And looking at the interface, the message seems to be uint64_t, is there any way to deal with the overflow problem of the message?
e.g. if I would want to subtract two Pedersen commitments:
comm1-comm2
which would equal (m1-m2)G+(r1-r2)H
How could I deal with situations like m1<m2 and still stick to 64 bits unsigned integers?
TIA

[jscode017]

P.S.
I've tried to build subtraction for pedersen commitment
using unsigned char [32]
but sometime it would produce an error
below is my implementation for subtracting two pedersen commitment:
(apologize in advance to post the entire code here, it is long. I wonder if there is some error in my code like overflow issue, help would be really appreciated)

int secp256k1_pedersen_sub(secp256k1_pedersen_commitment *res, const secp256k1_pedersen_commitment *commit1, const secp256k1_pedersen_commitment *commit2){
    secp256k1_gej accj;
    secp256k1_ge acc;
    secp256k1_gej_set_infinity(&accj);
    secp256k1_pedersen_commitment_load(&acc, commit2);
    secp256k1_gej_add_ge_var(&accj, &accj, &acc, NULL);
    secp256k1_gej_neg(&accj, &accj);
    secp256k1_pedersen_commitment_load(&acc, commit1);
    secp256k1_gej_add_ge_var(&accj, &accj, &acc, NULL);
    secp256k1_ge_set_gej(&acc, &accj);
    secp256k1_pedersen_commitment_save(res, &acc);
    secp256k1_gej_clear(&accj);
    secp256k1_ge_clear(&acc);
    return 1;
}

and the function I implement to subtract scalar(of unsigned char [32])

int secp256k1_scalar_sub_char(unsigned char *arr0, const unsigned char *arr1, const unsigned char *arr2)
{
    secp256k1_scalar scalar0;
    secp256k1_scalar scalar1;
    secp256k1_scalar scalar2;
    int overflow=0;
    secp256k1_scalar_set_b32(&scalar1, arr1, &overflow);
    secp256k1_scalar_set_b32(&scalar2, arr2, &overflow);
    secp256k1_scalar_negate(&scalar2, &scalar2);
    (void)secp256k1_scalar_add(&scalar0, &scalar1, &scalar2);
    secp256k1_scalar_get_b32(arr0, &scalar0);
    return 1;
}

What I am testing is take a1(unsigned char [32]), a2, r1(unsigned char [32]), r2, comm1(a1G+r1H), comm2(a2G+r2H)
and call secp256k1_pedersen_sub(res_comm, comm1, comm2)
and also
secp256k1_scalar_sub_char(res_a, a1, a2)
secp256k1_scalar_sub_char(res_r, r1, r2)
and check if a1, r1 gives me res_comm by implementing the pedersen commitment function for unsigned char [32]:

int secp256k1_pedersen_commit_256(const secp256k1_context* ctx, secp256k1_pedersen_commitment *commit, const unsigned char *blind, unsigned char *value, const secp256k1_generator *gen){
    secp256k1_ge genp;
    secp256k1_gej rj;
    secp256k1_ge r;
    secp256k1_scalar sec;
    int overflow;
    int ret = 0;
    /*VERIFY_CHECK(ctx != NULL);
    ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
    ARG_CHECK(commit != NULL);
    ARG_CHECK(blind != NULL);
    ARG_CHECK(gen != NULL);*/
    secp256k1_generator_load(&genp, gen);
    secp256k1_scalar_set_b32(&sec, blind, &overflow);
    if (!overflow) {
        secp256k1_pedersen_ecmult_256(&ctx->ecmult_gen_ctx, &rj, &sec, value, &genp);
        if (!secp256k1_gej_is_infinity(&rj)) {
            secp256k1_ge_set_gej(&r, &rj);
            secp256k1_pedersen_commitment_save(commit, &r);
            ret = 1;
        }
        secp256k1_gej_clear(&rj);
        secp256k1_ge_clear(&r);
    }
    secp256k1_scalar_clear(&sec);
    return ret;
}

with secp256k1_pedersen_ecmult_256 looks like:

SECP256K1_INLINE static void secp256k1_pedersen_ecmult_256(const secp256k1_ecmult_gen_context *ecmult_gen_ctx, secp256k1_gej *rj, const secp256k1_scalar *sec, unsigned char* value, const secp256k1_ge* genp) {
    secp256k1_gej vj;
    secp256k1_ecmult_gen(ecmult_gen_ctx, rj, sec);
    secp256k1_pedersen_ecmult_big(&vj, value, genp);
    /* FIXME: constant time. */
    secp256k1_gej_add_var(rj, rj, &vj, NULL);
    secp256k1_gej_clear(&vj);
}
static void secp256k1_pedersen_ecmult_big(secp256k1_gej *r, unsigned char* gn, const secp256k1_ge* genp) {
    secp256k1_scalar s;
    int overflow;
    secp256k1_scalar_set_b32(&s, gn, &overflow);
    secp256k1_ecmult_const(r, genp, &s, 64);
    secp256k1_scalar_clear(&s);
}

[jscode017]

P.S.: The above does not work when
a1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 (print out hex )
r1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
comm1: 8 bd bc 61 ee 9b 4 f3 52 4f 91 37 71 ee ee 93 c6 99 3c 5a 9c 98 d5 a3 f4 3a ec cf 9a ac 18 b5 (print out commit->data)
a2: 33 13 c6 eb 8d d4 7c 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
r2: 79 be 66 7e f9 dc bb ac 55 a0 62 95 ce 87 b 7 2 9b fc db 2d ce 28 d9 59 f2 81 5b 16 f8 17 98
comm2: 8 5b 75 fd 5f 49 e7 81 91 a4 5e 1c 94 38 64 4f e5 d0 65 ea 98 92 c 63 e9 ee f8 6e 15 1e 99 b8

Then I get:
res_a: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 83 2b 72 14 3e ec d5
res_r: 86 41 99 81 6 23 44 53 aa 5f 9d 6a 31 78 f4 f7 b8 12 e0 b 81 7a 77 62 65 df dd 31 b9 3e 29 a9
res_comm: 8 c1 a1 a8 b3 1b 68 41 48 8d 2e b1 f5 1a a4 d c9 1c cf d 97 51 c f6 c1 49 42 8d f5 c0 3f 86 8e 6c 65 7e 76 a7 21 77 86 ac 9d 47 7f b d3 54 a3 1e 88 6d 23 92 af 40 7f 9d 34 a3 12 e7 ca 5d
which seems to not equal using secp256k1_pedersen_verify_tally

[jonasnick]

Hi,

And may I ask that is there an implementation of semi homomorphic update of Pedersen commitments?

What do you mean exactly?

And looking at the interface, the message seems to be uint64_t, is there any way to deal with the overflow problem of the message?

I skimmed your code and what you're attempting to do seems roughly correct. I have no idea where your bug is.

[apoelstra]

How could I deal with situations like m1<m2 and still stick to 64 bits unsigned integers?

You need to know boh m1 and m2 -- and their blinding factors -- in order to detect this case. If you could detect m1 < m2 otherwise, you could exploit this to determine the value inside a commitment, by just attempting to subtract various fixed numbers until the result failed the check.

If you do know the openings to both commitments, and you want to prove that no overflow occurred, then you want to use a rangeproof. We have a production-ready but inefficient rangeproof in this library in the rangeproof module and an upcoming much-more-efficient one in #207.

[jscode017]

Hi @apoelstra @jonasnick
Thanks a lot for the reply
I am trying to do some commitment enhancement secret sharing, so that's why I would need to do some semi homomorphic updates on the secrets
And with the updates of secret, the secrets may overflow, I agree that it is a great way for using range proof or checking them not overflow
But I am also looking at message space > 64 bits, so I am building interfaces for unsigned char [32]

What I have checked know is that the secp256k1_scalar_set_b32(&s, gn, &overflow) would not trigger overflow, so the problem seems not to come out with int secp256k1_scalar_sub_char
The problem may come out of my implementation of secp256k1_pedersen_ecmult_256 or secp256k1_pedersen_sub
Any thoughts of bugs that may happen when the commitment, message or randomness is huge?
Thanks again for your help and reply, truly appreciate it

BTW I am using

void *globals::none_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_VERIFY));
secp256k1_context *globals::none = secp256k1_context_preallocated_create(globals::none_prealloc, SECP256K1_CONTEXT_NONE);

Does it affect anything?

[jscode017]

For more details when I am debugging:
in this function:

int secp256k1_pedersen_sub(secp256k1_pedersen_commitment *res, const secp256k1_pedersen_commitment *commit1, const secp256k1_pedersen_commitment *commit2){
    secp256k1_gej accj;
    secp256k1_ge acc;
    secp256k1_gej_set_infinity(&accj);
    secp256k1_pedersen_commitment_load(&acc, commit2);
    secp256k1_gej_add_ge_var(&accj, &accj, &acc, NULL);
    secp256k1_gej_neg(&accj, &accj);
    secp256k1_pedersen_commitment_load(&acc, commit1);
    secp256k1_gej_add_ge_var(&accj, &accj, &acc, NULL);
    secp256k1_ge_set_gej(&acc, &accj);
    secp256k1_pedersen_commitment_save(res, &acc);
    secp256k1_gej_clear(&accj);
    secp256k1_ge_clear(&acc);
    return 1;
}

based on whether the secp256k1_pedersen_commitment_load function triggers negate:

secp256k1-zkp/src/modules/generator/main_impl.h

Line 250 in ff33018

secp256k1_ge_neg(ge, ge);

If the first and second commit load does not triggers: error would happen
If the first trigers negate and second commit load does not triggers: error wont happen

[apoelstra]

Ultimately you'll need a rangeproof-like object to guarantee no overflow. If you extend the commitments in this library past 64 bits you'll need to implement your own proof -- and be aware that if your commitment space is larger than half the group size, rangeproofs won't work and you'll have to do something much more elaborate.

[jscode017]

Thanks for the reply, so does that means that the commitment would not work if overflow happens?

[apoelstra]

It will work fine, but these commitments commit to elements of the scalar group, not to integers. If you want to pretend that they're integers you need to restrict their range and use rangeproofs to enforce this.

[jscode017]

thanks, @apoelstra
I would try to do the unsigned char [32] interface then(rather than)

Furthermore, would it be possible for you to provide some insight into any potential mistakes I might be making based on the information provided above?
TIA

[jonasnick]

@jscode017 have you tried running your program in valgrind? Also I think your context should be SECP256K1_CONTEXT_SIGN.

[jscode017]

@jscode017 have you tried running your program in valgrind? Also I think your context should be SECP256K1_CONTEXT_SIGN.

Thanks, I would try to run in valgrind and change the context. Appreciate for your help