Re: Semi-distributed searching (and maybe fully distributed too)

--===============1605321442==
Content-Type: multipart/signed;
  boundary="nextPart17071436.jSQ9CPYTEX";
  protocol="application/pgp-signature";
  micalg=pgp-sha1
Content-Transfer-Encoding: 7bit

--nextPart17071436.jSQ9CPYTEX
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On Monday 19 July 2010 21:55:26 Matthew Toseland wrote:
> FASD paper:
> http://freenetproject.org/papers/kronfol_final_thesis.pdf
>=20
> The FASD paper enables keyword searching but is spammable. Basically this=
 is really easy (I haven't read it in a while so my terminology may be comp=
letely different to his):
> - Keywords are hashed, of course, and these hashes translate to routing l=
ocations.
> - An index element has a list of keywords connected to it.
> - These are inserted as normal keys, except that they are inserted to the=
 locations of *each* of the keywords.
> - A search can be routed to all of the keyword locations or to some subse=
t of them. It will include a list of keywords.
> - The receiving nodes will send back any index elements that match the se=
arch.
> - Standard algorithms for relevance are used to rank results (based on re=
lative frequency etc). This can easily be extended for arbitrary insert-tim=
e relevance numbers.
> - I don't recall whether flow control was specified, it could become a pr=
oblem, but the obvious solution is just to limit the number of returned ite=
ms.
>=20
> The fundamental problem has always been spam: These are effectively KSKs,=
 and when you fetch them you propagate all the spam that the spammer has in=
serted.
>=20
> So solve it the same way we solve this for chat. All we have to do to mak=
e FASD feasible is:
> - Make the items signed.
> - Send a compressed list of the inserter identities we are interested in =
along with the request.
>=20
> Clearly scalability is limited in much the same way as it is for chat. Ho=
wever it should be workable provided there is a certain amount of aggregati=
on and centralisation at the end-user level. And it's a big improvement fro=
m having to download several huge indexes and intersect them on the client.=
 Arguably it may be more efficient to use this mechanism only for popular k=
eywords; for unpopular keywords the btree indexes should be very efficient.=
 And it's probably a useful primitive for many applications...
>=20
> Could it be made fully distributed, without needing a WoT? Yes, but only =
with:
> 1) Some sort of reputation feedback mechanism. This most likely involves =
not propagating, or de-propagating, content that was fetched and not wanted=
, and
> 2) A sufficiently high cost for inserts of keywords to deter spamming. E.=
g. something similar to the Scarce KSKs proposal - limit the number of keyw=
ord index items that can be inserted to one per X seconds per link.
>=20
> These are in principle feasible but may open serious attacks e.g. the fir=
st may introduce censorship attacks, links to the wider question of is it s=
afe ever to allow to discover the location of a document without propagatin=
g it. IMHO the main issue there is path folding, and we can turn path foldi=
ng off for keyword searches (just like we turn it off for SSKs and inserts)=
=2E Plus, will users give sufficient useful feedback?
>=20
> KISS: Simplest mechanism: Keep an LRU (random replacement better for data=
 storage but not here). When a fetch happens, generate an unforgeable token=
 for each returned datum. If the user gives positive feedback, this is sent=
 back to us, we "spend" the token (i.e. commit it to persistent storage, it=
 cannot be spent twice, like digicash), and promote the item. This would be=
 an operation similar to an insert, which would promote on those nodes wher=
e it matched the original fetch. Obviously it will only work for a relative=
ly short period after the original request. We might have recently fetched =
items stored in a special cache to be promoted into the main cache if feedb=
ack comes in, and dropped if it doesn't. To prevent abuse, we could perhaps=
 use rate limiting similar to that proposed for inserting? A spammer keepin=
g stuff in the cache indefinitely without anyone else fetching it may be po=
ssible by repeatedly requesting (he can't repeatedly insert) - but not if w=
e don't promote items that we have already returned from a node that was cl=
ose to the originator. Or we just impose rate limiting on search requests a=
s well as inserts. Or ignore it - spam is only a problem if it is in volume=
, and inserts are throttled anyway.
>=20
> Hmmm, what exactly does FASD say about this? My recollection was that FAS=
D was spammable. I should really read the paper again! It looks like it *mi=
ght* be a tractable problem ...
>=20
> And can these mechanisms prevent spam on chat too?? Yes, chat is essentia=
lly a search problem.
>=20
I would just like to point out that we are a long way away from the above:
=2D Scarce KSKs or similar mechanism is equivalent to token passing. It's h=
ard.
=2D Even for the single-inserter/WoT case, load balancing would be a proble=
m; one solution is to "partition by document and by keyword" in the jargon =
of RFC4981 i.e. segment either all documents, or the results from a single =
keyword, into manageable-sized groups which can be inserted to different lo=
cations. The latter gives us sane sized groupings, and the different sub-ke=
ywords could be indicated in the btree - we fetch from the btree, if the ma=
tches are small we just get the data; if the matches are big we get a list =
of keyword hashes which we then search for with the above mechanism (this w=
ill be faster than downloading and intersecting multi-gigabyte index files).

=46or the time being, btree indexes and WoT are the way to go. There is muc=
h that can be done to improve on them. On-network intersection is stuff to =
consider much later on e.g. post-1.0. Hence my posting it to tech@.

--nextPart17071436.jSQ9CPYTEX
Content-Type: application/pgp-signature; name=signature.asc 
Content-Description: This is a digitally signed message part.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABEIAAYFAkxFnL8ACgkQYUNbc3WUHYimqgCfaPf90OoMNYqJo1pSBKagagNs
ikIAnjRMGleH3KSf85nq/rlZoTpvSKY5
=zx8i
-----END PGP SIGNATURE-----

--nextPart17071436.jSQ9CPYTEX--

--===============1605321442==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Tech mailing list
[email protected]
http://freenetproject.org/cgi-bin/mailman/listinfo/tech
--===============1605321442==--