Define the anoncreds 2 revocation ledger transactions, content and work required (from JIRA INDY-2365)

[swcurran]

Discussions were held about anoncreds revocation 2.0 (aka Merkle Tree-based revocation) based on the capabilities exposed in Ursa.  We propose that the following attributes and approaches be used in the Indy credential revocation 2.0 instance.

• Tree leaves will be indexed bits (vs. bytes) that are either 0 (not revoked) or 1 (revoked).
• The Merkle tree will be an 8-ary tree (vs. binary or 4-ary).
• Nodes holding the tree leaves will be 64-bit unsigned integers,
  • As such, a minimum revocation registry is one layer deep with a root hash and eight 64 bit ints, and hence would be capable of handling 512 credentials.
• On creation of a revocation registry, a parameter will be the depth of the tree, with a value of 1 to 7, supporting up to ~134 million credentials in a single registry.
  • The table below gives the number of credentials and MByte size of the leaves by the number of layers of the registry.
• The two existing revocation-related ledger transactions will continue to be used - REVOC_REG_DEF and REVOC_REG_ENTRY
  • REVOC_REG_DEF will contain at least a link to the cred def and the number of layers of the Merkle Tree. Since all the leaves are 0 (all credentials unrevoked), the Merkle Tree itself is not needed.
  • REVOC_REG_ENTRY will contain at least a signed Merkle Tree root and a gzip compressed set of leaf nodes in a well-defined configuration.
    • Since the distribution of revoked credentials is likely to be skewed one way or the other, the compression rate in the common case is likely to be high.
    • For a 7-layer ledger with (unlikely) ineffective compression the worst ledger entry size would be ~16Mb.
    • The interior nodes of the Merkle Tree must be calculated from the leaves and the calculated root verified against that in the ledger transaction.
    • It may be possible to organize the leaves such that a prover can stream the compressed data, decompressing only the section necessary to construct the proof--the path from the credential leaf to the root.
    • A "domain separation" value is needed as well, for reasons to be added here.
• As is necessary today, the holder/prover and verifier must read from the ledger the REVOC_REG_DEF and appropriate REVOC_REG_ENTRY values in creating and verifying the proof.
  • Unlike today, no tails file is needed by the prover.

To be determined is whether any change is needed to Indy Node to support the transaction content, or whether the current Indy Node code can support the same transaction with different content. Note that Indy Node does not have to do anything with the transaction content other than write it to the ledger and pass it back to any readers.

[swcurran]

This was discussed on the Indy Collaborators call on 2020.04.20. In that call a concern was raised about the computing/space resources constraints on mobile devices when computing the interior nodes of the revocation.

On that same call it was stated that while the changes to Indy Node would be minimal based on this approach, some changes would be necessary to implement verification of the object passed in the transaction.

[dhh1128]

Just a note: there appear to be 2 different merkle tree impls already visible in the libindy codebase. One is in libindy itself (libindy/src/services/ledger/merkletree/merkletree.rs). That merkle tree is unable to meet the design requirements above, because it is binary and not sparse. The second is in Ursa (./libzmix/bulletproofs_amcl/src/r1cs/gadgets/sparse_merkle_tree_8_ary.rs). This is closer to the design requirements, since it's already 8-ary and sparse. However, it seems to me that it is also 8-ary at the leaves (I need to confirm this; if I'm wrong, this is the answer), whereas what we've spec'ed out above is 64-bit at the leaves and 8-ary everywhere else. This might require yet another custom merkle tree impl, which is problematic because A) it's redundant code; and B) we might have to rewrite the Ursa code that already generates the zkSNARKs circuit from the merkle tree. There are half a dozen Rust crates that provide merkle tree impls, but so far I'm unaware of any that allow different X-ary choices for leaves vs. intermediate nodes...

I will investigate further. If I'm misunderstanding something, and someone else knows more, please comment.

[dhh1128]

It looks like none of the available Rust crates are good options. The closest is merkletree (https://crates.io/crates/merkletree). It allows 64-bit leaves, but it is a binary tree in all cases; doesn't support 8-ary.

[swcurran]

@mikelodder7 - could you weigh in on this?

I'd say we go with Ursa's implementation as is and adjust the planned definition accordingly. Mike had said leaves could be 1 bit or 1 byte, so that seems to align to what Daniel is saying. I believe that means that the size of the leaf set remains the same, but we go up a layer to achieve the same "number of credentials" size RevReg (e.g. layers=1 is a 64 credential registry, layers=2 is 512, etc.). The ramification of that is that there is an extra layer of interior nodes for the prover to calculate, increasing the resource (CPU and memory) pressure on the prover.

Sorry for the rabbit hole, Daniel.

[mikelodder7]

The implementation in ./libzmix/bulletproofs_amcl/src/r1cs/gadgets/sparse_merkle_tree_8_ary.rs allows for anything to be stored. What happens is the values are converted to field elements when they are used for proof computation but storage can be anything. For example, you can use the in-memory version here. Where you can switch to bits and bytes is in the insert and get methods. Insert only requires the hash and the value. The value can be stored however you want and get can convert the retrieved value to the appropriate field element. No need to store more than is necessary. For us, we only care about storing 1 bit.