Question: Positive Accumulator Membership test

[ppoliani]

I'm trying to get my head around how I can use the ECC accumulator to effectively create membership verifications. I've added the following test

    #[test]
    fn test_membership() {
      let mut rng = StdRng::seed_from_u64(0u64);
      let params = SetupParams::<Bls12_381>::generate_using_rng(&mut rng);
      let keypair = Keypair::<Bls12_381>::generate_using_rng(&mut rng, &params);
      let mut accumulator = PositiveAccumulator::initialize(&params);

      let elems = [
        Fr::from(1),
        Fr::from(2),
        Fr::from(3),
        Fr::from(4),
      ];

      for elem in elems {
        accumulator.0 = accumulator.compute_new_post_add(&elem, &keypair.secret_key);
      };

      // verify membership
      let verification_accumulator = PositiveAccumulator::from_accumulated(*accumulator.value());
      let member = &Fr::from(100);
      let wtns = verification_accumulator.compute_membership_witness(member, &keypair.secret_key);

      assert!(verification_accumulator.verify_membership(
        member,
        &wtns,
        &keypair.public_key,
        &params
      ));
    }

My assumption here is the verify_membership should fails since value 100 is not part of the elems that generate the accumulator. However, the above test simply passes. As a matter of fact it passes using an arbitrary member value.

Apparently my assumption is wrong 😆. Nonetheless, it would be nice to know if I can use this cryptographic tool to use prove membership. IBasically, want to use it instead of a Merkle Tree

[mark-moir]

@ppoliani note that compute_membership_witness takes the accumulator's secret_key, and therefore can only be called by the accumulator's owner/manager (which is trusted by the Verifier), not by a Prover (which is not).

A more realistic scenario is that, when the owner first adds Prover's element to the accumulator, owner provides a witness (e.g., computed using compute_membership_witness) to the Prover.

Prover can use that witness until there are subsequent additions and/or removals, at which point it can use functions such as compute_update_using_public_info_after_batch_updates (see here) to update its witness.

Hope this helps.

[lovesh]

@ppoliani The problem is that compute_membership_witness is being called on a value that is not part of the accumulator. As @mark-moir pointed out, compute_membership_witness is called by a trusted party (accumulator manager) who would first check in its state if this element is actually a member. See get_membership_witness for creating witness, it checks the state if the element is actually present.

Also, instead of

accumulator.0 = accumulator.compute_new_post_add(&elem, &keypair.secret_key);

you should use following because its prevents entering duplicates in the accumulator

accumulator = accumulator.add(&elem, &keypair.secret_key, &mut state);

Now i am realizing that this expectation should have been documented.

I can explain the cryptographic reason for above behaviour if needed.