Skip to content

SKS

Jump to bottom Edit New page
Leberwurscht edited this page Nov 10, 2010 · 75 revisions

I examine version 1.1.1. To compile with ubuntu:

aptitude install ocaml
aptitude install libdb4.7-dev
cp Makefile.local.unused Makefile.local

then set LIBDB to "-ldb-4.7" in Makefile.local and delete the bzero function in bdb/bdb_stubs.c (this is to make it compile with recent gcc, trick borrowed from the debian source package). Now

make dep
make all

Trying it out

SKS has two commands(see man page):

  • sks db, which answers web requests
  • sks recon, which does the synchronisation work

Extract source to two different directories and build the source as described for each directory. Now, for the first directory, do:

Initialize Database: ./sks build

write to ./sksconf:

hkp_port: 21000
recon_port: 21001
debuglevel: 10

(hkp_port is the web interface port and used for communication with clients, recon_port is the port used for synchronisation between servers)

write to ./membership

localhost 22001

(this will make the server synchronize with the other sks server we will set up on the same machine, but on a different port)

Start the servers:

./sks db &
./sks recon

For the second directory, do:

Initialize Database: ./sks build

write to ./sksconf:

hkp_port: 22000
recon_port: 22001
debuglevel: 10

write to ./membership

localhost 21001

Start the servers:

./sks db &
./sks recon

Now you have two local servers running that synchronize with each other.

To be able to add a test key I have stolen the html page http://keyservers.org:11371/, put it into ./web/index.html for each source directory and adapted the "action" attributes of the forms.

Now I can visit http://localhost:21000/, add a key and observe with wireshark how the key is given to the other local server. One can visit http://localhost:22000/ and search for the key to see if it worked.

Log files are ./db.log and ./recon.log.

Examination of the source

The main entry point seems to be sks.ml. For the recon command, there are the lines:

let module M = Reconserver.F(struct end) in
M.run ()

So we need to inspect reconserver.ml. There are two functions recon_handler (functions as well as variables seem to be defined by let in ocaml) and initiate_recon, calling ReconCS.handle_connection and ReconCS.connect respectively. I think reconserver.ml contains also some code to communicate with the db component. The synchronisation algorithm itelf is called in reconCS.ml:

The handle_connection and connect functions in reconCS.ml then initialize sockets and call Client.handle and Server.handle respectively, which implement the synchronisation algorithm.So we need at least server.ml and client.ml and all their dependencies for our purpose.

make dep has created a file called .depend listing the dependencies. With the script depend.py a dependency graph can be drawn:

server dependencies graph client dependencies graph

List of modules and what they do

  • zZp: the field modulo prime p
  • prefixTree: a Trie module

.....to be worked on......

Log files for reconciliation

The two log files for the synchronisation process contain now the following text (added modules responsible for printing each line in square brackets by doing a grep <message> *.ml in the source directory)

server

2010-10-18 00:00:05 Marshalling: LogQuery: (5000,1287266711.937730)
2010-10-18 00:00:05 Unmarshalling: LogResp: 0 events
2010-10-18 00:00:09 Recon partner: <ADDR_INET [127.0.0.1]:21001> [reconserver.ml]
2010-10-18 00:00:09 Initiating reconciliation [reconCS.ml]
2010-10-18 00:00:09 Marshalling: Config [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: Config [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: ReconRqst_Full(2,) [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Marshalling: Elements(len:0) [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: Flush [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Flush occured [server.ml]
2010-10-18 00:00:09 Unmarshalling: Done [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Done received [server.ml]
2010-10-18 00:00:09 Reconciliation complete [reconserver.ml]
2010-10-18 00:00:09 Hashes recovered from <ADDR_INET [127.0.0.1]:21000> [recoverList.ml]
2010-10-18 00:00:09 	DEE9A3FEBEB306EDE4894DE875B9FE6E
2010-10-18 00:00:09 Disabling gossip [recoverList.ml]
2010-10-18 00:00:09 Requesting 1 missing keys from <ADDR_INET [127.0.0.1]:21000>, starting with DEE9A3FEBEB306EDE4894DE875B9FE6E [reconserver.ml]
2010-10-18 00:00:09 1 keys received [reconserver.ml]
2010-10-18 00:00:09 Marshalling: KeyStrings: 1 keystrings [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: Ack: 0 [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Marshalling: LogQuery: (5000,1287266711.937730) [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: LogResp: 1 events [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 setting synctime to 1287352809.686156 [catchup.ml]
2010-10-18 00:00:09 Added 1 hash-updates. Caught up to 1287352809.686156 [catchup.ml]
2010-10-18 00:00:09 Enabling gossip [recoverList.ml]
2010-10-18 00:00:09 Marshalling: LogQuery: (5000,1287352809.686156)
2010-10-18 00:00:09 Unmarshalling: LogResp: 0 events

client

2010-10-18 00:00:06 Marshalling: LogQuery: (5000,1287266685.729216)
2010-10-18 00:00:06 Unmarshalling: LogResp: 1 events
2010-10-18 00:00:06 setting synctime to 1287352804.893544 [catchup.ml]
2010-10-18 00:00:06 Added 1 hash-updates. Caught up to 1287352804.893544 [catchup.ml]
2010-10-18 00:00:09 Beginning recon as server, client: <ADDR_INET [127.0.0.1]:59897> [reconserver.ml]
2010-10-18 00:00:09 Joining reconciliation [reconCS.ml]
2010-10-18 00:00:09 Marshalling: Config [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: Config [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Marshalling: ReconRqst_Full(2,) [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Queue length: 1 [client.ml]
2010-10-18 00:00:09 Operation would have blocked [nbMsgContainer.ml]
2010-10-18 00:00:09 Marshalling: Flush [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Queue length: 2 [client.ml]
2010-10-18 00:00:09 Operation would have blocked [nbMsgContainer.ml]
2010-10-18 00:00:09 Unmarshalling: Elements(len:0) [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Marshalling: Done [msgContainer.ml or nbMsgContainer.ml]
2010-10-18 00:00:09 Reconciliation complete [reconserver.ml]
2010-10-18 00:00:09 No hashes recovered from <ADDR_INET [127.0.0.1]:22000> [recoverList.ml]
2010-10-18 00:00:11 Marshalling: LogQuery: (5000,1287352804.893544)
2010-10-18 00:00:11 Unmarshalling: LogResp: 0 events

I think sks has some hash for every key and first compares the two sets of hashes between the servers with its reconciliation algorithm. Then it transmits the missing keys. The hashes seem to be stored in a Trie:

  • reconserver.ml:185 calls get_ptree()
  • get_ptree is defined in pTreeDB.ml, ptree is initialized by init_ptree, see lines 172ff.

Internally, there is some hash <-> element of prime field mapping. Need to find out how hashes are computed.

Log file for key adding

Same procedure for key adding:

2010-10-18 22:49:56 Handling /pks/add for 1 keys [dbserver.ml]
2010-10-18 22:49:56 /pks/add: key C503A871EFBB85CD5873B8D5E611037F added to database [dbserver.ml]
2010-10-18 22:49:56 0 potential merges found for keyid AF78C0AE [keydb.ml]
2010-10-18 22:49:56 1 updates found before filtering [keydb.ml]
2010-10-18 22:49:56 Applying 1 changes [keydb.ml]
2010-10-18 22:49:56 Adding hash C503A871EFBB85CD5873B8D5E611037F [keydb.ml]
2010-10-18 22:49:56 Keydb.add_key_merge: Enqueing new key for transmission to other hosts [keydb.ml]
2010-10-18 22:49:58 Unmarshalling: LogQuery: (5000,1287352809.686156) 
2010-10-18 22:49:58 Sending LogResp size 1 [dbserver.ml]
2010-10-18 22:49:58 Marshalling: LogResp: 1 events
2010-10-18 22:49:59 checking for key emails [mailsync.ml]
2010-10-18 22:49:59 Failed to find mtime, can't decide whether to load mailsync file
2010-10-18 22:49:59 <mail transmit keys> error in callback.: Failure("No partners specified")

these lines in dbserver.ml are responsible for computing the hash(comments added):

                let keytext = Scanf.sscanf body "keytext=%s" (fun s -> s) in (* get url-encoded keytext *)
		let keytext = Wserver.decode keytext in (* decode, this is the text you submitted *)
		let keys = Armor.decode_pubkey keytext in (* creates a key object of this string *)
		plerror 3 "Handling /pks/add for %d keys" 
		  (List.length keys); 
		cout#write_string "<html><body>";
		let ctr = ref 0 in
		List.iter keys
		  ~f:(fun origkey -> 
			try
			  let key = Fixkey.canonicalize origkey in
			  plerror 3 "/pks/add: key %s added to database"
			    (KeyHash.hexify (KeyHash.hash key));
....

key object creation works like this:

  • armor.ml:110: Armor.decode_pubkey calls Key.of_string_multiple
  • key.ml:135: Key.of_string_multiple calls Key.next_of_channel
  • key.ml:95: Key.next_of_channel calls ParsePGP.read_packet with the submitted string

parsePGP.ml:80 returns a dictionary made of this string:

	{ (* packet_tag = packet_tag; *)
	  content_tag = content_tag;
	  packet_type = content_tag_to_ptype content_tag;
	  packet_length = length;
	  packet_body = cin#read_string length;
	}

this Fixkey.canonicalize in dbserver.ml seems to transform this dictionary further to some object.

  • dbserver.ml:430: Fixkey.canonicalize is called
  • fixkey.ml:111: Fixkey.canonicalize calls KeyMerge.dedup_key
  • keyMerge.ml:253: KeyMerge.dedup_key calls KeyMerge.key_to_pkey
  • keyMerge.ml:215: KeyMerge.key_to_pkey calls KeyMerge.parse_keystr
  • keyMerge.ml:124: parsing is done

Compiling and linking experiments

add file test.ml:

open PTreeDB;;

module ZSet = ZZp.Set;;

let settings = { (* copied from reconserver.ml *)
	mbar = !Settings.mbar;
	bitquantum = !Settings.bitquantum;
	treetype = (if !Settings.transactions
		then `transactional
		else if !Settings.disk_ptree 
		then `ondisk else `inmem);
	max_nodes = !Settings.max_ptree_nodes;
	dbdir = Lazy.force Settings.ptree_dbdir;
	cache_bytes = !Settings.ptree_cache_bytes;
	pagesize = !Settings.ptree_pagesize;
};;

print_string "Database dir: ";;
print_string (Lazy.force Settings.ptree_dbdir);;
print_string "\n";;

init_db settings;;
init_ptree settings;;

let tree = get_ptree ();;

let root = PrefixTree.root tree;;

let num_elements = PrefixTree.num_elements tree root;;

print_string "Elements:\n";;

let el = PrefixTree.elements tree root;;

ZSet.iter ~f:(fun s -> Printf.printf "%s\n" (Number.to_string (ZZp.to_number s))) el;;

then add to Makefile:

test: $(LIBS) $(ALLOBJS) test.cmx
        $(OCAMLOPT) -o test $(OCAMLOPTFLAGS) $(ALLOBJS) test.cmx

Now you can compile the program with make test; you get an executable named test that will print the elements stored in the trie in their numeric representation.

Things I figured out:

  • Each hash has a representation as element of field modulo p
  • ZSet is a generic set class, a set type that can hold elements of the prime field can be obtained with module ZSet = ZZp.Set, which is defined in zZp.ml:183.
  • Number is a module containing a type z that can store arbitrary size integers.
  • Elements of the field modulo p cannot be easily printed, one must convert them to the Number type using ZZp.to_number, which still cannot be printed. One has to apply Number.to_string to get a string that can be printed. The definition of the to_number function looks like an identity function, but the types for input and output are defined in zZp.mli:101, so this seems to convert the type.
  • The prime p seems to be defined in rMisc.ml:153

Next goal: write a basic server in ocaml that can later be extended to synchronize our data. It is probably the best to use the sks Eventloop module for this. Eventloop.evloop is defined in eventloop.ml:230, and used in reconserver.ml:343 and dbserver:640. The arguments of the evloop function are events and socklist, but the arguments that are passed in reconserver.ml and dbserver.ml are very strange.

socklist seems to be a list of tuples like

(comsock, Eventloop.make_th ~name:"command handler" ~timeout:!Settings.command_timeout ~cb:(eventify_handler command_handler))

with comsock defined as let comsock = Eventloop.create_sock recon_command_addr.

I succeeded in writing a server one can connect to with telnet localhost 20000:

let addr = Unix.ADDR_INET (Unix.inet_addr_of_string "0.0.0.0", 20000);; 
let sock = Eventloop.create_sock addr;;

let test addr cin cout =
	let ccout = (new Channel.sys_out_channel cout) in
		ccout#write_string "test\n";
		ccout#flush;

	Common.plerror 1 "%s tried to connect" (ReconMessages.sockaddr_to_string addr);
	[];;

let timeout = !Settings.reconciliation_config_timeout;;

Eventloop.evloop [] [sock, Eventloop.make_th ~name:"test" ~cb:test ~timeout:timeout];;
(* make_th stands for make timed handler *)

Now a basic client, I looked at reconCS.ml:132ff. for this:

let socket = Unix.socket Unix.PF_INET Unix.SOCK_STREAM 0;;

let sockaddr = Unix.ADDR_INET(Unix.inet_addr_of_string "127.0.0.1", 20000);;

Unix.connect socket sockaddr;;

(* let cin = Channel.sys_in_from_fd socket;; *)
let cout = Channel.sys_out_from_fd socket;;

cout#write_string "test\n";;
cout#flush;;

Unix.close socket;;

Test it by installing netcat and doing a nc -l 20000 before running the executable.

attempt to write server and client that synchronize their prefix trees

Combine the server/client examples with the prefixtree example and call Server.handle and Client.handle:

server:

open PTreeDB;;

let settings = { (* copied from reconserver.ml *)
	mbar = !Settings.mbar;
	bitquantum = !Settings.bitquantum;
	treetype = (if !Settings.transactions
		then `transactional
		else if !Settings.disk_ptree 
		then `ondisk else `inmem);
	max_nodes = !Settings.max_ptree_nodes;
	dbdir = Lazy.force Settings.ptree_dbdir;
	cache_bytes = !Settings.ptree_cache_bytes;
	pagesize = !Settings.ptree_pagesize;
};;

init_db settings;;
init_ptree settings;;

let addr = Unix.ADDR_INET (Unix.inet_addr_of_string "0.0.0.0", 20000);; 
let sock = Eventloop.create_sock addr;;

let timeout = !Settings.reconciliation_config_timeout;;

let test addr cin cout =
	let cin = (new Channel.sys_in_channel cin)
	and cout = (new Channel.sys_out_channel cout) in
		let data = Client.handle (get_ptree ()) cin cout in
		ignore(data);

	Common.plerror 1 "talked with %s" (ReconMessages.sockaddr_to_string addr);
	[];;

Eventloop.evloop [] [sock, Eventloop.make_th ~name:"test" ~cb:test ~timeout:timeout];;

client:

open PTreeDB;;

let settings = { (* copied from reconserver.ml *)
	mbar = !Settings.mbar;
	bitquantum = !Settings.bitquantum;
	treetype = (if !Settings.transactions
		then `transactional
		else if !Settings.disk_ptree 
		then `ondisk else `inmem);
	max_nodes = !Settings.max_ptree_nodes;
	dbdir = Lazy.force Settings.ptree_dbdir;
	cache_bytes = !Settings.ptree_cache_bytes;
	pagesize = !Settings.ptree_pagesize;
};;

init_db settings;;
init_ptree settings;;

let socket = Unix.socket Unix.PF_INET Unix.SOCK_STREAM 0;;

let sockaddr_to = Unix.ADDR_INET(Unix.inet_addr_of_string "127.0.0.1", 20000);;

Unix.connect socket sockaddr_to;;

let cin = Channel.sys_in_from_fd socket;;
let cout = Channel.sys_out_from_fd socket;;

let data = Server.handle (get_ptree ()) cin cout;;

Unix.close socket;;

Seems to work somehow:

Server output:

2010-10-24 13:44:34 Opening PTree database
2010-10-24 13:44:34 Setting up PTree data structure
2010-10-24 13:44:34 PTree setup complete
2010-10-24 13:44:41 Marshalling: ReconRqst_Full(4,)
2010-10-24 13:44:41 Queue length: 1
2010-10-24 13:44:41 Operation would have blocked
2010-10-24 13:44:41 Marshalling: Flush
2010-10-24 13:44:41 Queue length: 2
2010-10-24 13:44:41 Operation would have blocked
2010-10-24 13:44:41 Unmarshalling: Elements(len:0)
2010-10-24 13:44:41 Marshalling: Done
2010-10-24 13:44:41 talked with <ADDR_INET [127.0.0.1]:56116>

Client output:

2010-10-24 13:44:41 Opening PTree database
2010-10-24 13:44:41 Setting up PTree data structure
2010-10-24 13:44:41 PTree setup complete
2010-10-24 13:44:41 Unmarshalling: ReconRqst_Full(4,)
2010-10-24 13:44:41 Marshalling: Elements(len:0)
2010-10-24 13:44:41 Unmarshalling: Flush
2010-10-24 13:44:41 Flush occured
2010-10-24 13:44:41 Unmarshalling: Done
2010-10-24 13:44:41 Done received

Now, a program that allows to add entries to the prefix tree would be pleasant. So how does sks add entries?

prefixTree.ml has a function called insert in line 828, let's try with that. catchup.ml can give some hints how to deal with txn (database transaction) argument: prefixTree.insert_str is called by applylog in line 53, applylog has argument txn itself. Catchup.single_catchup (line 74) calls applylog like this:

	let txn = new_txnopt () in
	begin
	  try
	    applylog txn log;
	    plerror (if length = 0 then 5 else 3) 
	      "Added %d hash-updates. Caught up to %f" 
	      length newts;
	    PTree.clean txn (get_ptree ());
	    commit_txnopt txn
	  with
...

So we need to start a new database transaction with new_txnopt, then alter the prefix tree (here done by applylog). I think the PTree.clean command will recompute some checksums in the tree. Then the transaction must be commited by commit_txnopt.

So the number 1234 is added like this, for example:

let txn = new_txnopt () in
	PTree.insert (get_ptree ()) txn (ZZp.of_string "1234");
	PTree.clean txn (get_ptree ());
	commit_txnopt txn

So with some help of http://www.ocaml-tutorial.org/command-line_arguments we have:

open PTreeDB;;

module ZSet = ZZp.Set;;

let settings = { (* copied from reconserver.ml *)
	mbar = !Settings.mbar;
	bitquantum = !Settings.bitquantum;
	treetype = (if !Settings.transactions
		then `transactional
		else if !Settings.disk_ptree 
		then `ondisk else `inmem);
	max_nodes = !Settings.max_ptree_nodes;
	dbdir = Lazy.force Settings.ptree_dbdir;
	cache_bytes = !Settings.ptree_cache_bytes;
	pagesize = !Settings.ptree_pagesize;
};;

init_db settings;;
init_ptree settings;;

let txn = new_txnopt () in
	PTree.insert (get_ptree ()) txn (ZZp.of_string Sys.argv.(1));
	PTree.clean txn (get_ptree ());
	commit_txnopt txn

You can call this program and provide it with a number as command line argument which is to be added to the set.

Now we have programs to list the numbers of the set, add numbers, and a server and a client for synchronisation. Testing it shows that it does not work yet, the server and the client get the set of missing keys, but this set is not yet added to the database.

The ZSet is saved in data for both our server and client. So we can make a function

let add_number number =
	Printf.printf "got %s\n" (Number.to_string (ZZp.to_number number));
	let txn = new_txnopt () in
		PTree.insert (get_ptree ()) txn number;
		PTree.clean txn (get_ptree ());
		commit_txnopt txn

and call the following with the data variable:

ZSet.iter ~f:add_number data;

Now is the time to fill the repo on github... I made a git clone of the mercurial repository, some notes here. Then I branched off an development branch and added the four test programs. You can omit the instructions above and simply use the code in the repository by now(October 22, 2010).

Add a custom footer
Add a custom sidebar
Clone this wiki locally