zk-census-proof incremental index for leafs

[arnaucube]

These last days we've updated the design & impl of the circuit for the anonymous-voting with zk-census-proofs. But currently the usage of the merkletree leafs, is that the key that determines the path of the leaf in the tree is determined by the hash of the secretKey of the user. This brings into a tree that might not be fully used, having empty leafs that might not be used before finding a collision in the paths. Meaning that if the tree has for example 10 levels, it has available 1024 leafs, but not all the spots will be used as there will be collisions much before of reaching the 1024 available leafs, thus having an inefficient use of the tree space.

As an example, I did some tests with random key values in leafs (the old approach), and with 10 levels, when adding the leaf 27 it found a collision of already used leaf. Even using 16 levels (2**16=65536 total leafs) there were collisions when adding the leaf number 526. With 21 levels (2**21=2097152 leafs) is the smaller nLevels that allowed me to insert 1000 leafs (with random keys) without finding collisions (and even some of the iterations there were collisions).

So, the proposal would be that for the leaf, instead of using key: hash(secretKey), value: 0, to use a incremental index in the key, so the tree can eventually be filled at its maximum potential. It would look like key: incremental-index, value: hash(secretKey). The index would start at 0 and be incremented by 1 for each new leaf addition.
Meaning that if the tree has for example 10 levels, it has available 1024 leafs, and all the spots will be able to be used always.

This translates into more efficient usage of the Merkle Trees, thus using smaller circuits for the same census size, which means faster zkSNARK proof generation time in the user side.
For the previous example numbers, for a census of 1000 leafs, we could use a tree of 10 levels instead of a tree of at least 21 levels).
The current circuit for 10 levels it has 4214 constraints, while for 21 levels it has 6931 constraints (and take in mind that with 21 levels for 1000 leafs in the old approach there are still high probabilities of collision, so more levels would be needed to be safe).

Current Leaf structure
Proposal of Leaf structure

This design is possible in the zk-census-proof scheme because is the Vochain who is updating the merkletree, so can maintain in the state the current index to be used in the next leaf addition.

This change would require:

• circuit: Add a new private input leafIndex to the circuit, and update the way how the leaf is done to use the leafIndex as key and the hash(secretKey) as the value of the leaf
• vocdoni-node: Add the leafIndex needed logic into the Vochain. And make the gateway return the leafIndex of the user leaf when sends the siblings to the user
• dvote-js: Update the client side to use the leafIndex value when generating the zkInputs data structure

[brickpop]

I have a few questions:

• Wouldn't this allow people to register the same value twice, only that with different indexes?
  • If so, would I be able to generate two Merkle Proofs for the very same value?
• At the moment of generating Merkle Proofs, how can a voter know his/her index in advance to ask for a Merkle Proof?
• Maybe it's not relevant, but could this impact features like proof of non-existance?

[arnaucube]

(I've added numbers to the answers that map the order of the questions, to know to which question the answer is)

1. No, the index is determined by the Vochain, which also should ensure that the same zkCensusKey (the hash of the secretKey) is not added twice.
2. When the user send their zkCensusKey to the Vochain to get registered, the Vochain state gets updated (with the user's zkCensusKey being added to the CensusTree), and so the index counter that the Vochain maintains can be sent back tot he user.
   Another option could be that the User does not know their indexKey, and when the user wants their MerkleProof siblings, the Vochain has a way to know which index belongs for the given zkCensusKey. This second option would require that the Vochain maintains a key-value equivalence to map the zkCensusKey with its indexKey, but this key-value state could be used also to know if the zkCensusKey has been registered yet.
3. Yes, it could affect cases where proof of non-existence is needed. I understand that for the moment this is not required

So regarding the answers 1 & 2, the proposal has the extra need of having the mentioned map of zkCensusKey - indexKey, but the benefit is major, as the MerkleTree used in the zk census is used much more efficiently, meaning that for most of the cases we will be able to use smaller circuits with less constraints, which traduces to smaller zk proving time in the user side.

Edit: fix typos

[p4u]

I do see the benefits behind this proposal and I think it makes sense. We are optimizing the zkProof creation specially on the big census (i.e Nation size), so I'd go for it.

However as @brickpop stated, we need to be aware of some details in order to allow a user fetch its MerkleProof (the user does not know about the index). We need to abstract the behavior and write a special implementation of the census tree which will be composed of two data structures:

A. The merkle tree itself (using an incremental index as key)
B. A Map between a zk-census-key and its index

Lets take into account that we have two use cases for this zkSnark census:

1. The snark-friendly merkle tree is built offchain (by the organizer using some private database)
2. The snark-friendly merkle tree is built inchain by the Vochain nodes (as part of the blockchain state) if preRegister flag is true

So for the scenario 1 the census-service (HTTP based) will keep this index internally when the keys are being added. This census needs to be published on IPFS so other Gateways can import it and use for generating merkle-proofs for the users. The export dataset must contain an ordered data structure which allow other Gateways to reconstruct both the merkle tree and the index-map. So when a user asks for a merkle-proof she only needs to provide its key (not the index).

For the second scenario the census is build inchain thus the Gateways do not need to import the census from IPFS and it does not need to be exported either.

[ed255]

I think this is a major improvement because it allows decreasing the merkle tree size in the circuit reducing the number of constraints considerable, which means less computation time on the phone of the user. Without incremental indexes, collisions can happen in the hash used as key, and the two solutions are not nice: either increase the merkle tree size so that the collision probability is negligible (more constraints), or find a way to calculate alternative keys until there's no collision (which is cumbersome).

[arnaucube]

Added the spec in the docs.vocdoni.io: vocdoni/docs#60
And added the update in the circuit following the spec: vocdoni/zk-franchise-proof-circuit#5