NFD » ndn-cxx

From https://gerrit.named-data.net/5494

I had a working design earlier in the quarter where an InterestSignatureInfo was a subclass of SignatureInfo, and that worked well independently, but it became very messy in conjunction with Signature.

Given InterestSignatureInfo and DataSignatureInfo can have different fields, they should be different classes.

/// base class
class SignatureInfo
{
  // have fields that appear in both Interest and Data
};

class InterestSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Interest only
};

class DataSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Data only, ValidityPeriod and "other TLVs" should be moved there
};

The Signature type is messy and difficult to use. Deprecate it, and replace with four methods on both Interest and Data: getSignatureInfo setSignatureInfo getSignatureValue setSignatureValue.

https://gerrit.named-data.net/5502 patchset3 extends ValidatorConfig with three replay checkers that verifies SignatureNonce SignatureTime SignatureSeqNum elements according to spec. They appear as a checker under a rule, along with two key name checkers.
According to rules in general section:

A packet is treated as valid if it can pass at least one of the checkers and as invalid when it cannot pass any checkers.

This means, suppose I write a rule that contains two key name checkers, one SignatureTime checker, and one SignatureSeqNum checker, a signed Interest would be treated as valid if it (1) has an untrusted key name (2) has an unacceptable SignatureTime (3) has an acceptable SignatureSeqNum, because all it takes to pass the validator is one successful checker.
This violates the signed Interest spec that requires all three checkers to pass.

Simply defining all replay checkers to have an AND relation is insufficient, because an application may want to allow the incoming signed Interest to carry either a valid SignatureTime or a valid SignatureSeqNum. This practice is permitted by the spec: the spec requires validation of both SignatureTime and SignatureSeqNum if they are present, but does not forbid an application to accept either of them.

To solve this problem, define explicit logical relation operators among checkers:

checker {
  type AND
  checker {
    type OR
    checker {
      type hierarchical
      sig-type rsa-sha256
    }
    checker {
      type hierarchical
      sig-type ecdsa-sha256
    }
  }
  checker {
    type timestamp
  }
  checker {
    type seq-num
  }
}

Given InterestSignatureInfo and DataSignatureInfo can have different fields, they should be different classes.

/// base class
class SignatureInfo
{
  // have fields that appear in both Interest and Data
};

class InterestSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Interest only
};

class DataSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Data only, ValidityPeriod and "other TLVs" should be moved there
};

Sounds great. Should these be in separate files? If so, should they go in a signature/ or security/signature/ subdirectory, since there would be 6 files total? I don't want to spam the top-level dir with that many related components.

On the NDN platform call on May 29, 2020, it was decided to change SignatureNonce into a variable-length field with a minimum length of 1. In the spec, we will recommend a minimum length of 8.

Alex Afanasyev wrote in #note-22:

signed interest helper

What's that?

CommandInterestSigner. This one prepares nonce and other stuff.

Alex Afanasyev wrote in #note-24:

CommandInterestSigner. This one prepares nonce and other stuff.

Do we need to update CommandInterestSigner to use v0.3 (do we also allow it to still generate v0.2?) or are we going to add a new SignedInterestSigner that supports v0.3?

While reviewing https://gerrit.named-data.net/c/ndn-cxx/+/6221 I got curious about the performance characteristics of boost::multi_index_container, specifically insert and find operations for ordered indexes vs hashed indexes, and wrote a very quick-and-dirty and probably inaccurate benchmark. I'm copying it below in case it becomes useful again in the future.

Compile it with something like: g++ -O2 -std=c++14 benchmark.cpp $(pkg-config --cflags --libs libndn-cxx) -o benchmark
and either -DBENCHMARK_ORDERED or -DBENCHMARK_HASHED or both.

#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#include <ndn-cxx/name.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/key_extractors.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>

struct Record
{
    explicit Record(const ndn::Name& n) : name(n) {}

    ndn::Name name;
    // some junk to make the struct larger
    uint64_t pad1 = 1;
    uint64_t pad2 = 2;
    uint64_t pad3 = 3;
    uint64_t pad4 = 4;
};

using HashedContainer = boost::multi_index_container<
  Record,
  boost::multi_index::indexed_by<
    boost::multi_index::hashed_unique<
      boost::multi_index::member<Record, ndn::Name, &Record::name>,
      std::hash<ndn::Name>
    >,
    boost::multi_index::sequenced<>
  >
>;
using OrderedContainer = boost::multi_index_container<
  Record,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::member<Record, ndn::Name, &Record::name>
    >,
    boost::multi_index::sequenced<>
  >
>;

static ndn::Name
generateName(unsigned long nComp, unsigned long compLen)
{
    using RandEngine = std::independent_bits_engine<std::mt19937, 8, unsigned char>;
    static RandEngine rng = [] {
        std::random_device rd;
        // seed with 256 bits of entropy
        std::seed_seq seeds{rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()};
        return RandEngine{seeds};
    }();

    ndn::Name n;
    for (; nComp > 0; --nComp) {
        std::vector<uint8_t> bytes(compLen);
        std::generate(bytes.begin(), bytes.end(), [&] { return rng(); });
        n.append(bytes.data(), bytes.size());
    }
    return n;
}

int
main(int argc, char *argv[])
{
    if (argc != 4) {
        std::cerr << argv[0] << " <NUM_OF_NAMES> <NUM_OF_NAME_COMPONENTS> <NAME_COMPONENT_LEN>" << std::endl;
        return 1;
    }
    auto nNames = std::strtoul(argv[1], nullptr, 0);
    auto nComp = std::strtoul(argv[2], nullptr, 0);
    auto compLen = std::strtoul(argv[3], nullptr, 0);

    std::vector<ndn::Name> names(nNames);
    std::generate(names.begin(), names.end(), [&] { return generateName(nComp, compLen); });

#ifdef BENCHMARK_HASHED
    HashedContainer hashed;
    hashed.reserve(nNames);
#endif
#ifdef BENCHMARK_ORDERED
    OrderedContainer ordered;
#endif

    size_t nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t1 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.emplace(names[i]).second;
    }
#endif
    auto t2 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.emplace(names[i]).second;
    }
    auto t3 = std::chrono::steady_clock::now();
#endif

    std::cout << "EMPLACE NEW " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t2 - t1).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t3 - t2).count()
             #endif
              << std::endl;

    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t4 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.emplace(names[i]).second;
    }
#endif
    auto t5 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.emplace(names[i]).second;
    }
    auto t6 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nEMPLACE EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t5 - t4).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t6 - t5).count()
             #endif
              << std::endl;

    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t7 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.find(names[i]) != hashed.end();
    }
#endif
    auto t8 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.find(names[i]) != ordered.end();
    }
    auto t9 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nFIND EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t8 - t7).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t9 - t8).count()
             #endif
              << std::endl;

    auto anotherName = generateName(nComp, compLen);
    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t10 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.find(anotherName) != hashed.end();
    }
#endif
    auto t11 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.find(anotherName) != ordered.end();
    }
    auto t12 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nFIND NON-EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t11 - t10).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t12 - t11).count()
             #endif
              << std::endl;

    return 0;
}