[DONE] Simple Revocation List #806
Replies: 6 comments 9 replies
-
I would argue for making this as simple as possible and only using a single bitmap for revocation. If the issuer wants the credential subject to be allowed to access a different set of services after the credential becomes deactivated, the issuer could instead just issue a new credential dedicated to that other set of services for example: |
Beta Was this translation helpful? Give feedback.
-
|
I agree, I don't think we should use anything more than a bitmap. Deactivated VCs would require storing a timestamp, which would be significantly more expensive.
Yeah, although that wouldn't allow a verifier to check that, for example, that person was indeed a student during a certain time. (Edit: Well, I suppose you meant that In any case, I think we can find an alternative for the deactivation list. |
Beta Was this translation helpful? Give feedback.
-
|
Another downside of the "exchange" approach is that the Issuer and Holder have to interact with each other. There might be natural use cases where the holder e.g. trades in a ticket, which is then deactivated and receives a certificate of participation (not the best example, but you get the gist). But in other "ad-hoc" cases the Holder would be unaware that the credential was revoked and would need to establish a connection and run through an "exchange"-like flow. |
Beta Was this translation helpful? Give feedback.
-
|
This is a good point @eike-hass. It will be a problem in the cases where the holder is unaware of the credential being revoked, but this should be a relatively rare scenario. Furthermore if one only wants to know if the credential once was issued by the signing authority it is enough to simply check the issuer's signature on the credential. Hence as @PhilippGackstatter essentially pointed out the extra map keeping track of deactivated credential identifiers is only useful when one additionally needs to know when the credential got deactivated (before its natural expiry date). I imagine the use-cases where these conditions apply would be extremely niche. |
Beta Was this translation helpful? Give feedback.
-
Some bitmap implementations have a standard on-disk format (such as for instance Roaring bitmaps) and if this is the case for whichever bitmap implementation is decided on in this context, then it is probably a good idea to use that format regardless of how it affects Brotli compression (unless it makes it much worse). |
Beta Was this translation helpful? Give feedback.
-
This can be considered if there is popular demand for it, but not otherwise. Besides the privacy implications already mentioned it also introduces more complexity in the verification logic in the library. EDIT: In the case of ZKP the data required for checking revocation will in many cases be too large to fit in the issuer's DID Document, in which case it might have to be hosted elsewhere. In that case it could make sense to also allow this for |
Beta Was this translation helpful? Give feedback.
-
|
I believe resolving to hosted revocation lists is something that will get important for high volume issuers, where updating DID Documents multiple times per day/hour/minute might become infeasible or undesirable, due to mana requirements, technical or procedural overhead etc. The challenge here would be to follow the algorithm of encoding the revocation info in a VC. Public VCs might easily solve that, but they don't exist yet. We could argue that validating the VC is a resolver detail and go with the initially proposed service structure and design the resolver in a way that it just returns a "status result" in the form of valid / invalid. Maybe we can embed a VC in the DID document, although that seems very inefficient. |
Beta Was this translation helpful? Give feedback.
-
Hosted Revocation Schemes
Yes and no. One can argue that high-volume issuers with performance requirements should ideally run their own node/s with sufficient throughput and mana to meet them. However, they will still run into the hard limitation of message sizes on the Tangle. Increasing data payloads also scale proof-of-work requirements, significantly slowing publishing. Concerns of using externally-hosted revocation schemes:
Embedded/on-Tangle solutions avoid these issues entirely. If one can lookup an issuer's DID Document, they automatically get the revocation status at the same time. On-Tangle public verifiable credentials may require an extra resolution, however, which leads to the next point.
There's nothing stopping us from expanding a custom scheme to support arbitrary URLs later. However, it's also important to note the impact of external links on verifiers. Specifically that they cause an extra lookup during the verification process in addition to the DID Document of the issuer/s, which may significantly slow down interactions when querying IPFS for instance. Multiple verifiable credentials also means multiple revocation status lookups and may present a denial-of-service vulnerability without adequate measures put in place. @OliverAnderson #806 (comment)
With all that said, it is inevitable that we support external revocation schemes, due to the data size limitations and proof-of-work/mana requirements for both DID Documents and (potentially) public Verifiable Credentials hosted on the Tangle. See the rest of this comment for elaboration.
|
| Revocations | 0 | 10 | 100 | 1,000 | 10,000 | 100,000 | 131,072 (all) |
|---|---|---|---|---|---|---|---|
| Bitset | 21846 | 21846 | 21846 | 21846 | 21846 | 21846 | 21846 |
| Bitset+Zlib | 51 | 94 | 416 | 2319 | 10458 | 21860 | 51 |
| Bitset+Brotli | 18 | 68 | 376 | 2186 | 10298 | 21851 | 18 |
| Roaring | 11 | 59 | 299 | 2688 | 21878 | 21878 | 21878 |
| Roaring+Zlib | 16 | 59 | 314 | 2703 | 10483 | 21892 | 79 |
| Roaring+Brotli | 16 | 64 | 304 | 2694 | 10314 | 21883 | 50 |
Compression, particularly around the 10,000 revocations mark, notably decreases the size of Roaring bitmaps. In all cases, compression is a necessity for bitsets.
My preference would be for roaring bitmaps as they appear better for fewer, sparser revocations and do not require a fixed size up-front. The difference between the two options is minor, at most 300 bytes less for bitset arrays in the worst case.
DID Message Size
The setup is the same as before except the resulting Base64-encoded string is inserted into a DID Document as a service.
E.g. empty Roaring bitmap compressed with Zlib:
{
"doc": {
"id": "did:iota:6epMytmzkzFQdRyNcPDyGHr1uWxtfs28oymSp88TzQE5",
"capabilityInvocation": [
{
"id": "did:iota:6epMytmzkzFQdRyNcPDyGHr1uWxtfs28oymSp88TzQE5#sign-0",
"controller": "did:iota:6epMytmzkzFQdRyNcPDyGHr1uWxtfs28oymSp88TzQE5",
"type": "Ed25519VerificationKey2018",
"publicKeyMultibase": "zDjWmyKJhZmepS3PCvEf4rd5wR13WRS2hNaGBP3qPWUyC"
}
],
"service": [
{
"id": "did:iota:6epMytmzkzFQdRyNcPDyGHr1uWxtfs28oymSp88TzQE5#service",
"type": "EmbeddedRevocation2022",
"serviceEndpoint": "data:,eJyzMmAAAwADKABr"
}
]
},
"meta": {
"created": "2022-05-02T10:57:48Z",
"updated": "2022-05-02T10:57:48Z"
}
}Note that the data URI scheme is used to comply with the DID specification that serviceEndpoint entries be valid URIs. It does not add significant overhead.
The DID Document is then compressed into a DID Message using Brotli. The figures shown are the length in bytes of the resulting DID Messages.
| Revocations | 0 | 10 | 100 | 1,000 | 10,000 | 100,000 | 131,072 (all) |
|---|---|---|---|---|---|---|---|
| Bitset | 299 | 334 | 617 | 2217 | 8528 | 16750 | 301 |
| Bitset+Zlib | 321 | 362 | 625 | 2076 | 8201 | 16761 | 322 |
| Bitset+Brotli | 304 | 353 | 595 | 1972 | 8080 | 16757 | 306 |
| Roaring | 296 | 331 | 534 | 2344 | 8545 | 16780 | 325 |
| Roaring+Zlib | 303 | 343 | 547 | 2363 | 8210 | 16779 | 343 |
| Roaring+Brotli | 303 | 335 | 536 | 2347 | 8086 | 16783 | 335 |
The difference in overall size when using compression seems minor: in the worst case it costs an extra 10 bytes or so at most, and at best it saves ~500 bytes. I'm more concerned about the decompressed DID Document size, which has far greater implications as compressing the revocation list can save ~10KB there.
While compressing the revocation list itself in addition to the overall message means extra compuation and memory to decompress it, it lowers the memory footprint if not used (in the context of being embedded in a DID Document). Therefore it is a (minor) cost that only verifiers have to deal with, while everyone just resolving a DID Document for any other purpose benefits from a significantly lower decompressed size.
Note that the use of compression may open us up to decompression bombs, causing any vulnerable verifier to crash. However, one could theoretically do the same with the Brotli-compressed DID Messages already, so it is unclear at this point whether this is a valid concern.
Publishing Time
To determine how viable publishing DID Messages the size of several kilobytes is, I checked the time taken to publish an arbitrary DID Document as a JSON message to the Tangle.
Setup:
- IOTA DevNet.
- Proof-of-work performed locally (AMD Ryzen 9 3900, 12 cores, 3.1GHz base).
- Does not wait for milestone confirmation.
| Size | Publish Time (seconds) |
|---|---|
| 2KB | 1.25 |
| 4KB | 1.57 |
| 8KB | 6.00 |
| 16KB | 7.98 |
| 32KB | n/a |
At a size of 32KB, the client threw an "invalid indexation data length" error, so I'm taking that as indicating a hard upper-limit somewhere between 16KB and 32KB.
Note that:
- The proof-of-work difficulty setting on the nodes was not checked, so it could have been lower during the test for some reason.
- Times were not averaged and therefore could have significant variance.
- The test was performed on an uncongested Tangle, results could vary significantly in other circumstances.
- There is no guarantee this upper-limit will not reduced in the future.
What this indicates is that roughly 100,000 revocations total is the practical upper-limit for an embedded revocation list.
Responses to Open Questions
Track both revocation and deactivation lists?
Should the revocation list on the Issuers side contain two separate bitmaps: one for revoked VCs and one for deactivated VCs? A deactivated VC would be considered valid in the past, while a revoked VC is considered invalid in the past and future. Perhaps this also needs better names that are more descriptive to the two states.
I agree with previous comments that the use-case is extremely niche and would require storing the timestamp of when something was revoked, increasing complexity and data requirements.
#806 (comment)
#806 (reply in thread)
Proposed outcome: defer this to a future discussion and rather focus on the simpler use-case of revocation only, which is more likely to meet the needs of the majority of users and reflects existing revocation schemes.
Compress the revocation bitmap?
Is there any advantage to have a bitmap compression algorithm for the revocation bitmap(s), since we compress with Brotli afterwards?
See the previous results tables. While compressing the revocation list does not significantly reduce the on-Tangle size of DID Messages, it can significantly reduce the DID Document size when the DID Message is decompressed.
Proposed outcome: yes, compression is necessary.
Support external revocation schemes?
Should we support the revocation list to be hosted outside of a DID Document?
As mentioned before, I believe it is inevitable that we will have to support external revocation schemes due to size limitations.
@OliverAnderson #806 (comment)
In the case of ZKP the data required for checking revocation will in many cases be too large to fit in the issuer's DID Document, in which case it might have to be hosted elsewhere.
Proposed outcome: restrict the initial custom revocation scheme to on-Tangle only, embedded in a DID Document. This can be extended to support external resources later, which could be optional for verifiers and other implementers.
Cryptographic Accumulators
I have excluded discussions of zero knowledge proofs and cryptographic accumulators as options for revocation schemes for now. While they have desirable properties and are viable, such as the RSA accumulator-based revocation scheme adopted by Hyperledger Indy, the particulars, practicality, and trade-offs of such schemes are still uncertain.
Not all issuers will require the properties that such accumulators have over simple revocation bitsets, nor desire the performance trade-offs of maintaining them. The RSA accumulator revocation scheme referenced above, for instance, requires maintaining tails files of "hundreds of thousands to tens of millions" of randomly generated factors.
Therefore, simple revocation lists will likely still be useful even if more advanced revocation schemes are supported in the future.
Conclusion
Embedded or on-Tangle revocation schemes are extremely limited by data size and, in the future, mana requirements, and are infeasible to maintain at a high scale. They are, however, still useful and have advantages in terms of privacy, accessibility, availability and ease-of-adoption, and can support roughly 100,000 revocations at most per DID Document.
It is my recommendation that a simple embedded revocation scheme using a compressed bitset---either array or roaring bitmap---be decided upon and implemented. That scheme, if different from RevocationList2020, should be extended to support externally-hosted revocation lists (at least via HTTP) in the form of verifiable credentials either in the initial implementation or shortly thereafter. Options should be put in place for verifiers to reject externally-hosted revocation lists for safety and performance.
Beta Was this translation helpful? Give feedback.
-
This concerned me for a little bit as it doesn't solve a thing to add a second revocation list within the same DID Document. This means companies might need to maintain multiple identities, which is fine, but inconvenient.
However, this could be the saving grace. By having public VCs in the future. One could link from DID Documents to on-Tangle VCs, which is scalable as you can link probably tens or hundreds of public VCs, each holding a revocation list with ~100k entries. So I agree with the recommended approach from @cycraig, let's implement on-chain, embedded revocation list that is NOT based on RevocationList2020, and later consider adding RevocationList2020 combined with public VCs. |
Beta Was this translation helpful? Give feedback.
-
Indeed, 100,000 is pretty much the upper-limit ignoring deposits and mana costs. I would agree that 1,000 - 10,000 is likely a soft-cap, but even that number is still useful for individuals and small-scale issuers. My assumption is that revocation is an uncommon occurrence and that issuers should rather rely on expiration datetimes (similar to JWTs). E.g. if 1% of credentials are being revoked, then a 10,000 cap can still support 1,000,000 credentials.
It's less clear-cut due to compression working better on structured data, such as revoking consecutive indices, and worse on random data. One could just not use compression and budget for a fixed-sized bitset, but that seems wasteful.
I still prefer Roaring bitmaps for not requiring a fixed-size upfront and being able to handle sparse entries more easily. E.g. if I have 100,000,000 credentials and revoke only number 99,999,999: |
Beta Was this translation helpful? Give feedback.
-
|
In order to fix the uncompression size of DID Document, @eike-hass came up with the idea to just use Brotli twice. We compress the bitset with brotli and compress the entire DID Message again with Brotli. Naturally double compression does not reduce size of the compressed DID Message, but it will keep the bitset compressed while the rest of the DID message gets decompressed, making it possible to briefly decompress the bitmap during use and removing the burden from memory asap. By using Brotli in both cases we reduce dependency bloat and I believe this would actually be pretty efficient as well. In addition, while Bitset is very efficient to compress and it is generally not needed, we could allow "implicit zero's". This makes it possible to make the bitset non-fixed, allowing developers to increase the revocation list size as they add / revoke credentials. Otherwise we burden the developers / application developers to decide the size of the list at the start. We experienced with Merkle Key Collection that it is an annoying experience. |
Beta Was this translation helpful? Give feedback.
-
Yes, that option is represented as
That's perfectly possible except it doesn't address the disadvantages of a bitset in the sparse revocations case: one always needs a bitset as large as the biggest revoked index. |
Beta Was this translation helpful? Give feedback.
-
We only avoid an extra dependency for Zlib if we do not support
|
Beta Was this translation helpful? Give feedback.
-
|
Further discussion and implementation will happen in the context of #853 |
Beta Was this translation helpful? Give feedback.
-
Introduction
A fundamental unanswered design in the SSI space is the revocation mechanism. This mechanism allows Issuers of Verifiable Credentials (VCs) to revoke / deactivate these VCs in a decentralized manner where the Verifier will always be aware of its status update, yet does not have to contact the Issuer. This is often done by adding some sort of data to the Issuers DID Document, such as a revocation list.
With the release of IOTA Identity v0.5, we discontinued the Merkle Key Collection, which was our initial attempt to providing a revocation mechanism that scales and is secure. While the idea worked and was improving, we did realize that the design was overly complicated and could be simplified greatly without loosing any of the features we supported. Therefore the design was discontinued without a clear replacement. This does mean that this topic has a high priority for a replacement due to the framework lacking a scalable solution as of version 0.5.
Requirements
A perfect solution would fulfill all of the requirements listed below. However, we recognize the challenge of solving an community wide unresolved problem in a simple discussion. The SSI community has yet to centralize around a single best solution to ticks all requirements perfectly. We opt for a solution where the framework supports two (or more) revocation mechanism that focus on different properties and requirements. Currently we expect two solution, a simple yet fast revocation list and a Zero Knowledge Proof compatible revocation mechanism. This discussion focuses on the first: a simple yet fast revocation list. The following requirements are things to to take into consideration and might not all need to be tackled by one revocation mechanism.
Requirements:
Nice-to-have:
Performance considerations:
Other work
At the moment, two candidate solution seem to gain the most traction and have the most promising technical design to consider. The first is the RevocationList2020, a standard-in-development at W3C. This solution is a revocation list that is referenced inside a Verifiable Credential and has to be resolved. The design allows the revocation list to be stored anywhere, which includes on-chain but also off-chain endpoints. This complicates the design and creates potential attack vectors for the privacy of the Holder or Verifier as the revocation lists would naturally be hosted by the Issuer, which would now be able to monitor how often credentials are checked and from which IP address.
The second revocation method currently being used allows more ZKP compatibility via the use of a Cryptographic Accumulator. It is used by Hyperledger Indy, but has some significant downside / challenges. A large "tails" file has to be hosted by Issuers and downloaded by Verifiers, which is several MBs. This has similar privacy concerns as hosting this on-chain is not feasible. In addition, the overall performance of Cryptographic Accumulators might not make this solution ideal for all use cases.
Simple Revocation List solution
I would like to propose and discuss an initial revocation solution that is based on
RevocationList2020Statusfrom W3C, but simplified. As the revocation list can be hosted anywhere, they decided to publish it in the form of a VC. If we limit ourselves to a on-chain hosted revocation list, we can reduce the overhead significantly.Holder's Credentials side
RevocationList2020Statusby W3C:Holder's Credentials side proposed
SimpleRevocationList2022:Issuer's Revocation side
RevocationList2020Statusby W3C:Issuer's Revocation side proposed
SimpleRevocationList2022inside a DID Document:Possibly Allow externally hosted
SimpleRevocationList2022:Open Questions
Beta Was this translation helpful? Give feedback.
All reactions