barrywhitehat / semaphore Goto Github PK

I investigated a mechanism which may reduce the number of constraints in the proving circuit: using a cryptographic accumulator and membership test.

See: https://github.com/HarryR/solcrypto/blob/master/pysolcrypto/accumulator.py

The accumulate function takes take your public point, hashes it, and adds it to the set.

The proving circuit takes your secret scalar, the set accumulator and the witness. Only the accumulator parameter is public knowledge so the smart-contract can verify you're proving membership of the correct set.

I performs the pairing check for the witness using the hash of your public point (computed from your secret).

It is possible to reduce the SNARK circuit to something like:

def ismember_snark(signal_guid, secret, AkX_G2_pairing, W_x):
    x = hashpn(multiply(G1, secret), signal_guid)    # equivalent to SHA256(public.x, public.y, signal_guid)
    e2 = pairing(multiply(G2, x), W_x)
    return e2 == AkX_G2_pairing

# signal_guid is a public input
# AkX_G2_pairing is a public input, verified by smart contract
# secret is private
# W_x is private

Which is 1 round of SHA-256, two scalar multiply and one pairing operation. I wonder if this is cheaper than ~64 rounds of SHA-256?

The on-chain accumulator function would be something like:

function AddToSet( uint256[2] in_public_key ) public
{
    bytes32 xi = sha256(abi.encodePacked(in_public_key, m_group_guid));
    m_x0_mul_to_xn = mulmod(m_x0_mul_to_xn, uint256(xi), FIELD_ORDER);
}

The set can be frozen, at which point the AkX point is generated, otherwise the AkX point needs to be generated at verification time - alternatively x0_mul_to_xn could be passed to the circuit to push computation from on-chain to off-chain. shrugs

Any ideas or suggestions?

As per:

• barryWhiteHat/miximus#20
• barryWhiteHat/miximus#19

With a different proving circuit as described above, and the Groth 16 paper both the off-chain and on-chain proving and verification cost will be reduced. I estimate the number of constraints will be below 40,000, or a 40x reduction. If the reduction is relative to the overall proving time, then that takes it from ~12 minutes (on an old Xeon core) to ~20 seconds. .... however, with just 1 SHA256 round I'm already at 50k constraints... and adding a full pairing (miller loop etc.) will probably increase it massively.

Bugs / Problems / Solutions:

• Need to bind each public key to the membership of a set, e.g. upon set registration it takes your public key and multiplies it by a randomly chosen group membership scalar (e.g. the hash of the JSON signal description), then you add that into your secret as your key is now g^(xs) - then your signature set membership witness is specific to that signal. Alternatively your public key can be hashed with the signal GUID included, this removes a scalarmult operation in the on-chain accumulator function.
• The only point which needs validating is W_x on G1

Big blocker at the moment:

The libsnark::pairing_selector<libff:alt_bn128_pp> template isn't defined... which means it's not possible to use the weierstrass gadgets from libsnark in the prover yet. That's getting far out of my territory because I'm confused by names like Fqe vs Fqk, and the mnt6 and mnt4 pairing selectors reference each other.

We want to use this with miximus so its a good idea to break the ./src directory into a depedency that can be called from miximus and sepaphore.

If we do not do this an attacker could pass invaid address bits that are not 0 , 1.

I am unsure if this will cause a problem but its good to be sure/

Something like this from zcash from zcash should fix it.

        for (size_t i = 0; i < INCREMENTAL_MERKLE_TREE_DEPTH; i++) {
            // TODO: This might not be necessary, and doesn't
            // appear to be done in libsnark's tests, but there
            // is no documentation, so let's do it anyway to
            // be safe.
            generate_boolean_r1cs_constraint<FieldT>(
                this->pb,
                positions[i],
                "boolean_positions"
            );
}

Cross posting in miximus. But I hope we can finish the miximus rewrite with Semaphore as a dependency so we don't need to make this fix over there.

You say you link to a python script under section Identitiy merkle root examples. But the link is empty. Also the syntax for a link is [here](LINK_URL).