Awarded: ICDev.org Bounty #36 - Signing Tree and DER Encoding - Motoko $10,000

Developers Bounties
1

Signing Tree and DER Encoding - Motoko - #36

Current Status: Discussion

  • Discussion (01/09/2023)
  • Ratification: (01/09/2023)
  • Open for application: (01/09/2023)
  • Assigned
  • In Review
  • Closed

Official Link

Bounty Details

  • Bounty Amount: $10,000 USD of ICP at award date.
  • ICDevs.org Bounty Acceleration: For each 1 ICP sent to 25a63a3dfafde9da5ca73e63b66e6a5912cc61e8cb3581e9df8cd96ca5faa6ab, ICDevs.org will add .25 ICP to this issue and .75 ICP to fund other ICDevs.org initiatives.
  • Project Type: Individual
  • Opened: 01/09/2023
  • Time Commitment: Weeks
  • Project Type: Library
  • Experience Type: Advanced - Motoko; Advanced - Crypto;

Description

IC Subnets are able to sign a set of data and provide certified variables to applications outside of the IC. This functionality can also be used have the subnet sign messages and transactions from the IC.

Reference Material:

Canister signatures available to canisters on all subnets
Certified Data API
Haskell example
Signature Spec
There was an attempt
Structure of transactions for signing
Haskell DER Encoding
Tree Example
Asset Cert Example
Video walking through some of it

This bounty has three parts

  1. Produce a DER encoding library and make it compatible with Vessel and MOPS
  2. Produce a Merkle Tree library that will integrate well with the Certified Data API. Nometa has an example of a one level tree, but we need one that has many levels and allows the creation and verification of witnesses.
  3. Create an example of a canister signing a DER Encoded transaction that can be queried later to find the bytes needed to submit a request to IC.

The developer that completes this bounty will qualify to pursue bounty 23a - Metacalls - Motoko

The following library may be a good starter. GitHub - icdevsorg/motoko-merkle-tree: A Merkle Tree for Motoko for use with Certified Variables. Likely a number of things need to be added such as deleting values from tree. Please evaluate and update the library if it is missing something.

This bounty gives the opportunity to

  • learn about certified data and variables
  • learn about DER Encoding
  • learn how IC transactions are structured

To apply for this bounty you should:

  • Include links to previous work writing tutorials and any other open-source contributions(ie. your github).
  • Include a brief overview of how you will complete the task. This can include things like which dependencies you will use, how you will make it self-contained, the sacrifices you would have to make to achieve that, or how you will make it simple. Anything that can convince us you are taking a thoughtful and expert approach to this design.
  • Give an estimated timeline on completing the task.
  • Post your application text to the Bounty Thread

Selection Process

The ICDevs.org developer’s advisors will propose a vote to award the bounty and the Developer Advisors will vote.

Bounty Completion

Please keep your ongoing code in a public repository(fork or branch is ok). Please provide regular (at least weekly) updates. Code commits count as updates if you link to your branch/fork from the bounty thread. We just need to be able to see that you are making progress.

The balance of the bounty will be paid out at completion.

Once you have finished, please alert the dev forum thread that you have completed work and where we can find that work. We will review and award the bounty reward if the terms have been met. If there is any coordination work(like a pull request) or additional documentation needed we will inform you of what is needed before we can award the reward.

Bounty Abandonment and Re-awarding

If you cease work on the bounty for a prolonged(at the Developer Advisory Board’s discretion) or if the quality of work degrades to the point that we think someone else should be working on the bounty we may re-award it. We will be transparent about this and try to work with you to push through and complete the project, but sometimes, it may be necessary to move on or to augment your contribution with another resource which would result in a split bounty.

Funding

The bounty was generously funded by the DFINITY Foundation. If you would like to turbocharge this bounty you can seed additional donations of ICP to 25a63a3dfafde9da5ca73e63b66e6a5912cc61e8cb3581e9df8cd96ca5faa6ab. ICDevs will match the bounty $40:1 ICP for the first 125 ICP out of the DFINITY grant and then 0.25:1. All donations will be tax deductible for US Citizens and Corporations. If you send a donation and need a donation receipt, please email the hash of your donation transaction, physical address, and name to donations@icdevs.org. More information about how you can contribute can be found at our donations page.

FYI: General Bounty Process

Discussion

The draft bounty is posted to the DFINITY developer’s forum for discussion

Ratification: (01/09/2023)

The developer advisor’s board will propose a bounty be ratified and a vote will take place to ratify the bounty. Until a bounty is ratified by the Dev it hasn’t been officially adopted. Please take this into consideration if you are considering starting early.

Open for application

Developers can submit applications to the Dev Forum post. The council will consider these as they come in and propose a vote to award the bounty to one of the applicants. If you would like to apply anonymously you can send an email to austin at icdevs dot org or sending a PM on the dev forum.

Assigned

A developer is currently working on this bounty, you are free to contribute, but any splitting of the award will need to be discussed with the currently assigned developer.

In Review

The Dev Council is reviewing the submission

Awarded

The award has been given and the bounty is closed.

Other ICDevs.org Bounties

2 Likes
2

Nice! Some questions about the precise scope:

Is this expected to be a full-fledged DER encoding library, or only just enough code to create an IC Canister Signature, i.e. create a “The public key is encoded as a DER-wrapped COSE key”?

Does the canister have to create the transaction (including implementing the “representation independent hash” and CBOR encoding)? Or is it enough if the canister signs arbitrary blobs, and some other tool (e.g. dfx) creates the transaction, and uses the canister merely as a signature oracle?

1 Like
3

I think that for the bounty, the ability to produce an IC transaction is enough. If someone needs robust DER support they can always enhance it later. Having the basics would be great.

Does the canister have to create the transaction (including implementing the “representation independent hash” and CBOR encoding)? Or is it enough if the canister signs arbitrary blobs, and some other tool (e.g. dfx ) creates the transaction, and uses the canister merely as a signature oracle?

I think the end goal would be for a canister to post the message to the IC itself, so CBOR would be nice…but an alternate pathway is probably fine. Likely someone would want to set up a proxy that supports IPv6 and can do this step. If the tool can hand the signature off via https outcalls, that is likely enough. We do have a CBOR library though, so maybe it isn’t difficult: GitHub - edjCase/motoko_cbor

It would be cool to close the circle.

4

Ha, I completely forgot that since we last talked about this, HTTP calls from canisters have become a thing! Yes, the canister posting this is surely nicest for the demo :smiley:

5

Great bounty! I’m particularly interested in a Motoko implementation of a Merkle Tree library that will integrate with Certified Data API. Internally in Dfinity we’ve been working on an update to the Rust/JS versions of asset certification and verification: GitHub - dfinity/response-verification: Client side response verification for the Internet Computer. If anyone picks this up, I think it would be great to get some of this work integrated into that repository.

2 Likes
6

A few clarifications are possible. It’s not entirely clear to me.
Let’s say the user has a public key (a keyring with a private one)
This public is encoded in DER encoding. (according to secp256r1 and Ed25519 specifications)

let pubKey = DER.decode(pub);

Next, we can save it in the canister CertifiedData.set(pubKey);
And extract, if necessary,

let pubKey = CertifiedData.getCertificate();

For example, we can sign the data:

let signVal = Crypto.Ed25519.sign(pubKey, value);

We can send signed data and verify it to users using the user’s private key.
Did I understand correctly?
I’m also interested in how the Merkle Tree should participate in all this?

7

My understanding is that if you keep things in a Merkle tree that you can sign a witness and it will be considered signed. I get a bit lost in it and I really wish we had a good visual of how all of this worked. I started playing with some of this at playground but I made some bad assumptions…specifically:

“The / in the spec are not literal text, but separate the keys in the tree structure! so there is a key sig at the root, containing a subtree with keys that is the seed and at each key a subtree with keys that are m .”

8

This is a really cool bounty!

Here’s how I would do it. Not sure if this is entirely correct, though. The best role model would be the Internet Identity implementation.

I think the most important and high-leverage part would be an implementation of ic-certified-map in Motoko. (Though the HashTree part would be sufficient here if I understand correctly.)

Then you do the following:

You start with a proper unauthenticated IC message m, i.e. a content map according to Internet Computer Content Validation Bootstrap

Then, in an update call:

  1. Put m into the hash tree at position sig/<something>/m <something> is some arbitrary string that allows your canister to have multiple canister “public keys”
  2. Get the root hash of the tree and set this as CertifiedData

Then you need to do a query call because the certificate is only available in a query call.
The query call should return (if you want to work outside the IC for the rest):

With the first two elements, you can form the signature according to the interface spec:

* The signature is a CBOR value consisting of a data item with major type 6 ("Semantic tag") and tag value `55799` (see [Self-Describe CBOR](https://tools.ietf.org/html/rfc7049#section-2.4.5)), followed by a map with two mandatory fields:
  * `certificate` (`blob`): A CBOR-encoded certificate as per [Encoding of certificates](https://internetcomputer.org/docs/current/references/ic-interface-spec#certification-encoding).
  * `tree` (`hash-tree`): A hash tree as per [Encoding of certificates](https://internetcomputer.org/docs/current/references/ic-interface-spec#certification-encoding).

Then you need to assemble the properly authenticated call according to Internet Computer Content Validation Bootstrap

9

@skilesare nudged me to consider this bounty, and I am sufficiently tempted to take it on. Here is my plan of attack:

  • Build on https://github.com/nomeata/motoko-merkle-tree (and maybe https://github.com/icdevs/motoko-merkle-tree), because half the hard parts are already there, and it has a decent testing story already set up. Then:
    • Generalize the trie therein from fixed-length blobs to arbitrary length-blobs. This may yield an independently useful and usable BlobTrie data structure.
    • Generalize from one nesting level to arbitrary nesting level.
    • Add more operations: delete and get; maybe union.
  • Write a small library that performs DER, as needed to create Canister Signatures and IC transactions.
  • Write an example canister that can produce IC transactions accepted by the IC HTTP Interface, and maybe even submit them themselves.
  • Add to Vessel and Mops.
  • Decide on a suitable charity to receive the bounty, as I’ll do this pro-charity. I guess this means that if others find that cause worth supporting, they can up the bounty :slight_smile:

I am fairly certain that I will find enough spare time until April 17 to do this (and will likely be done earlier).

3 Likes
10

Awesome! Thanks, @nomeata!

11

Allright, I felt productive. Here is what works so far:

Left to do: Creating Canister Signatures, submitting a request to the IC, uploading libraries to vessel and MOPS.

I just noticed that the bounty also mentions “verification of witnesses in motoko”. I’d expect verification to be purely client side. What would be the use-case for that?

12

Hi
I don’t know much about these things. I want to clarify for myself. Do I understand correctly that we get a certified value from the func value_page(key : Text): Blob function?

That is, we have created a tree in accordance with the specification
#1
Internet Computer Specification

public type witness = {
# empty;
#sliced : Hash;
#fork : (Witness, witness);
#marked : (Key, witness);
#sheet : Value;
};

#2
Recorded this data in CertifiedData.set(MerkleTree.treeHash(mt));
#3
If necessary, we request data from CertifiedData.GetCertificate(); Then we find the key data in this merkle tree. The found value is certified. Is it like that?

13

value_page returns the body of the page at, for example, https://wpsi7-7aaaa-aaaai-acpzq-cai.ic0.app/get/key1.

For this to be certified, we have to put a hash of that value also in the canister’s hash tree:

        mt := MerkleTree.put(mt, ["http_assets", T.encodeUtf8("/get/" # k)], h(value_page(k)));
…
    CertifiedData.set(MerkleTree.treeHash(mt));

and when the user requests that page, we include a witness and the certificate in the response headers:

  func certification_header(url : Text) : HeaderField {
    let witness = MerkleTree.reveal(mt, ["http_assets", T.encodeUtf8(url)]);
    let encoded = MerkleTree.encodeWitness(witness);
    let cert = switch (CertifiedData.getCertificate()) {
      case (?c) c;
      case null { … }
    };
    return
      ("ic-certificate",
        "certificate=:" # base64(cert) # ":, " #
        "tree=:" # base64(encoded) # ":"
      )
  };
2 Likes
14

Unit testing? I’m trying to think of some use cases.

One may be where you want to store witnesses for easy distribution…but this may not be practical.

Or perhaps some service that doesn’t have to hold the tree but needs to use the tree and trusts the tree. Say we have a parent that keeps the tree and files the root. It creates a bunch of child canisters and we don’t want to distribute the tree to all the children. Instead, we want a client to directly relay a witness and instructions to the child and the child will only do the processing if the witness proves a certified variable.

15

Most likely that we cannot check under the subtree (witness) separately. We can send the certificate and the tree. Bypass the tree and if the root cache is equal to the certificate, then all the witnesses are “correct”. Although I’m not sure there aren’t other options.

16

More progress:

I made the canister produce a request, signed using a Canister Signature of the canister, that was accepted by the IC, and encoded using CBOR.

I used dfx to get that request and submit it with curl.

What seems to be impossible right now is to let the canister submit it directly, for annoying reasons:

I tried to work my way around it by using http_request to invoke the IC’s query call HTTP API, and get the certificate out. But http_request fires the request off multiple times, and requires the responses to be the same (for consensus etc.). In our case, they are not the same, e.g. different block times. Or maybe other issues, I am not sure – I could not make it work. I don’t think it’s useful to pursue this further – those who want their canisters to sign and send requests can probably use an external proxy that queries the canisters and sends the request.

I think this crosses all the boxes in terms of functionality. What’s left is some cleanup:

  • Some of the code that’s currently in the demo/ directory is worth promoting to the actual library.
  • Maybe I’ll rename the library, as it contains more than just the Merkle Tree. Maybe ic-interface, given that it contains a bunch of definitions related to the IC Interface Specification?
  • The library needs to be uploaded. It uses depenencies from all over the place (cbor, xtended-numbers, sha224); these need to be uploaded/added to the vessel package set as well.
  • Maybe write a blog post about how things fit together, or record a talk.

Does that sound about right?

3 Likes
17

Awesome!!

That sounds fantastic.

18

Did you or someone else have a concrete application in mind that was pending on this bounty? Now is already a good time to pick up my library and see if it provides the expected features, and provide early feedback.

19

Latest status:

I’ll consider this as “done” now, and hand it over to @skilesare or whoever to evaluate if this fulfils the bounty or if there are pieces still missing or worth improving, before then making a 1.0.0 release.

Also, @skilesare, probably the bounty status needs to be updated :slight_smile:

4 Likes
20

Hi! @nomeata
Can we do the following?

Let’s say two canisters A and B
Canister A supports certified data.
Canister B is the consumer, that is, the recipient of data from canister A.
Canister A receives a request from canister B to process the data and get the result (back to B).
Canister A processes this data, certifies, temporarily stores and sends the result.
Canister B receives the result, and makes sure that canister A really sent this data to her. Using Certificate A. (There was no substitution)

Is it possible?