[GNUnet-SVN] [gnunet] 08/18: Unfinished implementation of bidirectional search:

[gnunet]

This is an automated email from the git hooks/post-receive script.

martin-schanzenbach pushed a commit to branch master
in repository gnunet.

commit 7b749c91759eb75eda5cac1e02954cc82ef27db3
Author: Andreas Ebner <address@hidden>
AuthorDate: Sun Aug 11 17:04:00 2019 +0200

    Unfinished implementation of bidirectional search:
    
    - queue to add all currently found nodes
    - backward_resolution implementation of what to do when you find a matching 
one
    - new test for bidirecitonal search
    - still a lot to do / still has a lot of prints and comments that need to 
be removed
---
 src/credential/gnunet-service-credential.c | 193 ++++++++++++++++++++++++++---
 src/credential/test_credential_bi.sh       |  90 ++++++++++++++
 src/credential/test_credential_own.sh      |   1 +
 3 files changed, 270 insertions(+), 14 deletions(-)

diff --git a/src/credential/gnunet-service-credential.c 
b/src/credential/gnunet-service-credential.c
index 41f4f64d6..9de16bf72 100644
--- a/src/credential/gnunet-service-credential.c
+++ b/src/credential/gnunet-service-credential.c
@@ -243,6 +243,11 @@ struct DelegationSetQueueEntry
    * The delegation chain entry
    */
   struct DelegationChainEntry *delegation_chain_entry;
+
+  /**
+   * True if added by backward resolution
+   */
+  bool from_bw;
 };
 
 
@@ -369,6 +374,10 @@ static struct GNUNET_STATISTICS_Handle *statistics;
  */
 static struct GNUNET_GNS_Handle *gns;
 
+//TODO vrh dependent
+static struct DelegationSetQueueEntry *dsq_head;
+static struct DelegationSetQueueEntry *dsq_tail;
+
 
 /**
  * Handle to namestore service
@@ -564,7 +573,8 @@ send_lookup_response (struct VerifyRequestHandle *vrh)
 
   GNUNET_MQ_send (GNUNET_SERVICE_client_get_mq (vrh->client), env);
   GNUNET_CONTAINER_DLL_remove (vrh_head, vrh_tail, vrh);
-  cleanup_handle (vrh);
+  //TODO fix cleanup with bidirectional
+  //cleanup_handle (vrh);
 
   GNUNET_STATISTICS_update (statistics,
                             "Completed verifications",
@@ -806,6 +816,42 @@ forward_resolution (void *cls,
       }
     }
 
+    // TODO testing area   
+
+    // Check list
+    for (struct DelegationSetQueueEntry *del_entry = dsq_head;
+               del_entry != NULL;
+               del_entry = del_entry->next)
+    {
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"--fw-------- %s.%s <- %s.%s\n", 
+      
GNUNET_CRYPTO_ecdsa_public_key_to_string(&del_entry->delegation_chain_entry->issuer_key),
+      del_entry->delegation_chain_entry->issuer_attribute,
+      
GNUNET_CRYPTO_ecdsa_public_key_to_string(&del_entry->delegation_chain_entry->subject_key),
+      del_entry->delegation_chain_entry->subject_attribute);
+
+      // only check entries not added by forward algorithm
+      if(del_entry->from_bw)
+      {
+        // key of list entry matches actual key
+        if (0 == memcmp (&del_entry->delegation_chain_entry->subject_key,
+                             &ds_entry->delegation_chain_entry->issuer_key,
+                             sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)))
+        {
+          // compare entry subject attributes to this trailer (iss attr + old 
trailer)
+          if (0 == strcmp 
(del_entry->delegation_chain_entry->subject_attribute,
+                               ds_entry->attr_trailer))
+          {
+            GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"--fw-------- Found match with 
above!\n"); 
+            send_lookup_response (vrh);
+            return;
+          }
+        }
+      }
+    }
+    // No crossmatch/bidirectional result, add this ds_entry for the bw algo 
to match
+    ds_entry->from_bw = false; 
+    GNUNET_CONTAINER_DLL_insert (dsq_head, dsq_tail, ds_entry);
+
     // Starting a new GNS lookup
     vrh->pending_lookups++;
     ds_entry->handle = vrh;
@@ -832,6 +878,17 @@ forward_resolution (void *cls,
   }
 }
 
+static void
+print_deleset(struct DelegationSetQueueEntry *dsentry, char* text)
+{
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"%s %s.%s <- %s.%s\n",
+                        text, 
+                        
GNUNET_CRYPTO_ecdsa_public_key_to_string(&dsentry->delegation_chain_entry->issuer_key),
+                        dsentry->delegation_chain_entry->issuer_attribute,
+                        
GNUNET_CRYPTO_ecdsa_public_key_to_string(&dsentry->delegation_chain_entry->subject_key),
+                        dsentry->delegation_chain_entry->subject_attribute);
+}
+
 static void
 backward_resolution (void *cls,
                      uint32_t rd_count,
@@ -934,14 +991,15 @@ backward_resolution (void *cls,
                                    dq_entry->set_entries_tail,
                                    ds_entry);
 
-      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Checking for cred match\n");
       /**
        * Check if this delegation already matches one of our credentials
        */
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Checking for cred match\n");
+
       for (del_pointer = vrh->del_chain_head; del_pointer != NULL;
            del_pointer = del_pointer->next)
       {
-        // If key and attribute match credential continue and backtrack
+        // If key and attribute match credential: continue and backtrack
         if (0 != memcmp (&set->subject_key,
                          &del_pointer->delegate->issuer_key,
                          sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)))
@@ -956,7 +1014,9 @@ backward_resolution (void *cls,
           continue;
 
         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found issuer\n");
+        // increase refcount of the start delegation
         del_pointer->refcount++;
+
         // Backtrack
         for (tmp_set = ds_entry; NULL != tmp_set->parent_queue_entry;
              tmp_set = tmp_set->parent_queue_entry->parent_set)
@@ -973,6 +1033,7 @@ backward_resolution (void *cls,
             break;
         }
 
+        // if the break above is not called the condition of the for is met 
         if (NULL == tmp_set->parent_queue_entry)
         {
           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "All solutions found\n");
@@ -983,10 +1044,11 @@ backward_resolution (void *cls,
         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Not all solutions found yet.\n");
         continue;
       }
+
       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                   "Building new lookup request from %s\n",
                   ds_entry->unresolved_attribute_delegation);
-      // Continue with backward resolution
+      // Continue with next/new backward resolution
       char issuer_attribute_name[strlen (
                                    ds_entry->unresolved_attribute_delegation) +
                                  1];
@@ -1011,6 +1073,106 @@ backward_resolution (void *cls,
         ds_entry->attr_trailer = GNUNET_strdup (next_attr);
       }
 
+
+      // TODO testing area
+      // Check list
+      for (struct DelegationSetQueueEntry *del_entry = dsq_head;
+                del_entry != NULL;
+                del_entry = del_entry->next)
+      {
+        print_deleset(del_entry, "-----bw----- ");
+
+        // only check entries not added by forward algorithm
+        if(!del_entry->from_bw)
+        {
+          // key of list entry matches actual key
+          if (0 == memcmp (&del_entry->delegation_chain_entry->issuer_key,
+                              &ds_entry->delegation_chain_entry->subject_key,
+                              sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)))
+          {
+            // compare entry subject attributes to this trailer (iss attr + 
old trailer)
+            if (0 == strcmp (del_entry->attr_trailer,
+                                
ds_entry->delegation_chain_entry->subject_attribute))
+            {
+              GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"--bw-------- Found match 
with above!\n"); 
+              
+              //TODO parents are not set correctly, for FW parents are going 
down in the chain
+              // and for BW parents are going up
+              // therefore: parent fixing needs to be done and then the stuff 
from above
+              // backtrack(required solutions) and refcount++
+              // might need some functions cuz its getting real big in here
+
+              struct DelegationSetQueueEntry *old_fw_parent;
+              struct DelegationSetQueueEntry *fw_entry = del_entry;
+              struct DelegationSetQueueEntry *bw_entry = ds_entry;
+              // parentset and add
+              while(NULL != fw_entry->parent_queue_entry)
+              {
+                print_deleset(fw_entry, "-----in while----- ");
+                old_fw_parent = fw_entry->parent_queue_entry->parent_set;
+                // set parent
+                fw_entry->parent_queue_entry->parent_set = bw_entry;
+
+                bw_entry = fw_entry;
+                fw_entry = old_fw_parent;
+              }
+              GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "NACH WHILE\n");
+              // set last entry of chain as actual ds_entry
+              ds_entry = bw_entry;
+              // set refcount, loop all delegations
+              for (del_pointer = vrh->del_chain_head; del_pointer != NULL;
+                  del_pointer = del_pointer->next)
+              {
+                if (0 != memcmp 
(&ds_entry->delegation_chain_entry->subject_key,
+                         &del_pointer->delegate->issuer_key,
+                         sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)))
+                  continue;
+                if (0 != strcmp 
(ds_entry->delegation_chain_entry->subject_attribute,
+                                del_pointer->delegate->issuer_attribute))
+                  continue;
+
+                GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found delegate.\n");
+                // increase refcount of the start delegation
+                del_pointer->refcount++;
+              }
+              // backtrack
+              for (tmp_set = ds_entry; NULL != tmp_set->parent_queue_entry;
+                  tmp_set = tmp_set->parent_queue_entry->parent_set)
+              {
+                //TODO set refcount
+                print_deleset(tmp_set, "-----ENDSET----- ");
+                tmp_set->parent_queue_entry->required_solutions--;
+
+                // add new found entry to vrh
+                vrh->delegation_chain_size++;
+                GNUNET_CONTAINER_DLL_insert (vrh->delegation_chain_head,
+                                         vrh->delegation_chain_tail,
+                                         tmp_set->delegation_chain_entry);
+
+                // if one node on the path still needs solutions, this current
+                // patch cannot fullfil the conditions and therefore stops here
+                // however, it is in the vrh and can be used by the other paths
+                // related to this path/collection/verification
+                if (0 < tmp_set->parent_queue_entry->required_solutions)
+                {
+                  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Chain requires more 
solutions, waiting...\n");
+                  return;
+                }
+              }
+              GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "NACH FOR\n");
+              
+              send_lookup_response (vrh);
+              return;
+            }
+          }
+        }
+      }
+      // No crossmatch/bidirectional result, add this ds_entry for the bw algo 
to match
+      ds_entry->from_bw = true; 
+      GNUNET_CONTAINER_DLL_insert (dsq_head, dsq_tail, ds_entry);
+
+
+
       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                   "Looking up %s\n",
                   ds_entry->lookup_attribute);
@@ -1305,7 +1467,12 @@ handle_verify (void *cls, const struct VerifyMessage 
*v_msg)
   }
 
   // Switch resolution algo
-  if (GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo)
+  if(GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo && 
GNUNET_CREDENTIAL_FLAG_FORWARD & vrh->resolution_algo)
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "--------BOTH\n");
+    delegation_chain_fw_resolution_start (vrh);
+    delegation_chain_bw_resolution_start (vrh);
+  } else if (GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo)
   {
     delegation_chain_bw_resolution_start (vrh);
   }
@@ -1313,10 +1480,6 @@ handle_verify (void *cls, const struct VerifyMessage 
*v_msg)
   {
     delegation_chain_fw_resolution_start (vrh);
   }
-  else
-  {
-    //TODO
-  }
 }
 
 static void
@@ -1335,7 +1498,13 @@ delegate_collection_finished (void *cls)
   struct VerifyRequestHandle *vrh = cls;
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done collecting delegates.\n");
 
-  if (GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo)
+  //TODO correct calls
+  if(GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo && 
GNUNET_CREDENTIAL_FLAG_FORWARD & vrh->resolution_algo)
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "--------BOTH\n");
+    delegation_chain_fw_resolution_start (vrh);
+    delegation_chain_bw_resolution_start (vrh);
+  }else if (GNUNET_CREDENTIAL_FLAG_BACKWARD & vrh->resolution_algo)
   {
     delegation_chain_bw_resolution_start (vrh);
   }
@@ -1343,10 +1512,6 @@ delegate_collection_finished (void *cls)
   {
     delegation_chain_fw_resolution_start (vrh);
   }
-  else
-  {
-    //TODO
-  }
 }
 
 static void
diff --git a/src/credential/test_credential_bi.sh 
b/src/credential/test_credential_bi.sh
new file mode 100755
index 000000000..2b8cfc452
--- /dev/null
+++ b/src/credential/test_credential_bi.sh
@@ -0,0 +1,90 @@
+#!/usr/bin/env bash
+trap "gnunet-arm -e -c test_credential_lookup.conf" SIGINT
+
+LOCATION=$(which gnunet-config)
+if [ -z $LOCATION ]
+then
+  LOCATION="gnunet-config"
+fi
+$LOCATION --version 1> /dev/null
+if test $? != 0
+then
+       echo "GNUnet command line tools cannot be found, check environmental 
variables PATH and GNUNET_PREFIX"
+       exit 77
+fi
+
+rm -rf `gnunet-config -c test_credential_lookup.conf -s PATHS -o GNUNET_HOME 
-f`
+
+
+
+
+which timeout > /dev/null 2>&1 && DO_TIMEOUT="timeout 10"
+gnunet-arm -s -c test_credential_lookup.conf
+
+gnunet-identity -C a -c test_credential_lookup.conf
+gnunet-identity -C b -c test_credential_lookup.conf
+gnunet-identity -C c -c test_credential_lookup.conf
+gnunet-identity -C d -c test_credential_lookup.conf
+gnunet-identity -C e -c test_credential_lookup.conf
+gnunet-identity -C f -c test_credential_lookup.conf
+gnunet-identity -C g -c test_credential_lookup.conf
+AKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep a | awk 
'{print $3}')
+BKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep b | awk 
'{print $3}')
+CKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep c | awk 
'{print $3}')
+DKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep d | awk 
'{print $3}')
+EKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep e | awk 
'{print $3}')
+FKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep f | awk 
'{print $3}')
+GKEY=$(gnunet-identity -d -c test_credential_lookup.conf | grep g | awk 
'{print $3}')
+
+#   (1) (A.a) <- B.b
+#   (2) (B.b) <- C.c
+#   (3) C.c <- (D.D)
+#   (4) D.d <- (E.e)
+#   (5) E.e <- (F)
+
+# BIDIRECTIONAL
+gnunet-credential --createIssuerSide --ego=a --attribute="a" --subject="$BKEY 
b" --ttl=5m -c test_credential_lookup.conf
+gnunet-namestore -D -z a
+gnunet-credential --createIssuerSide --ego=b --attribute="b" --subject="$CKEY 
c" --ttl=5m -c test_credential_lookup.conf
+gnunet-namestore -D -z b
+
+SIGNED=`$DO_TIMEOUT gnunet-credential --signSubjectSide --ego=c 
--attribute="c" --subject="$DKEY d" --ttl="2019-12-12 10:00:00"`
+gnunet-credential --createSubjectSide --ego=d --import "$SIGNED"
+gnunet-namestore -D -z d
+SIGNED=`$DO_TIMEOUT gnunet-credential --signSubjectSide --ego=d 
--attribute="d" --subject="$EKEY e" --ttl="2019-12-12 10:00:00"`
+gnunet-credential --createSubjectSide --ego=e --import "$SIGNED"
+gnunet-namestore -D -z e
+SIGNED=`$DO_TIMEOUT gnunet-credential --signSubjectSide --ego=e 
--attribute="e" --subject="$FKEY" --ttl="2019-12-12 10:00:00"`
+gnunet-credential --createSubjectSide --ego=f --import "$SIGNED" --private
+gnunet-namestore -D -z f
+
+# Starting to resolve
+echo "+++ Starting to Resolve +++"
+
+DELS=`$DO_TIMEOUT gnunet-credential --collect --issuer=$AKEY --attribute="a" 
--ego=f --forward --backward -c test_credential_lookup.conf | paste -d, -s`
+echo $DELS
+echo gnunet-credential --verify --issuer=$AKEY --attribute="a" --subject=$FKEY 
--delegate=\'$DELS\' --forward --backward -c test_credential_lookup.conf
+RES_DELS=`gnunet-credential --verify --issuer=$AKEY --attribute="a" 
--subject=$FKEY --delegate="$DELS" --forward --backward -c 
test_credential_lookup.conf`
+
+# Cleanup properly
+gnunet-namestore -z epub -d -n $DISC_ATTR -t ATTR -c 
test_credential_lookup.conf
+gnunet-namestore -z eorg -d -n $PREF_ATTR -t ATTR -c 
test_credential_lookup.conf
+gnunet-namestore -z stateu -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+#gnunet-namestore -z a -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+#gnunet-namestore -z d -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+#gnunet-namestore -z e -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+#gnunet-namestore -z f -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+#gnunet-namestore -z g -d -n $STATE_STUD_ATTR -t ATTR -c 
test_credential_lookup.conf
+
+gnunet-arm -e -c test_credential_lookup.conf
+
+if [ "$RES_DELS" != "Failed." ]
+then
+  # TODO: replace echo -e bashism
+  echo -e "${RES_DELS}"
+  exit 0
+else
+  echo "FAIL: Failed to verify credential $RES_DELS."
+  exit 1
+fi
+
diff --git a/src/credential/test_credential_own.sh 
b/src/credential/test_credential_own.sh
index 4ff1a8e08..2bb5cb070 100755
--- a/src/credential/test_credential_own.sh
+++ b/src/credential/test_credential_own.sh
@@ -110,6 +110,7 @@ echo gnunet-credential --verify --issuer=$EPUB_KEY 
--attribute=$DISC_ATTR --subj
 RES_DELS=`gnunet-credential --verify --issuer=$EPUB_KEY --attribute=$DISC_ATTR 
--subject=$ALICE_KEY --delegate="$DELS" --backward -c 
test_credential_lookup.conf`
 
 
+
 # Cleanup properly
 gnunet-namestore -z epub -d -n $DISC_ATTR -t ATTR -c 
test_credential_lookup.conf
 gnunet-namestore -z eorg -d -n $PREF_ATTR -t ATTR -c 
test_credential_lookup.conf

-- 
To stop receiving notification emails like this one, please contact
address@hidden.