Horchata is a Spanish drink made from chufas. An entry for it is here:

  http://www.epicurious.com/db/dictionary/terms/h/horchata.html

Here's an explantion (From: Mathieu Wehrung):

Chufas, cyperaceae cyperus esculentus as they go by their scientific
name, are a chick-pea sized tuberous roots of a sedge-like African
plant, with a brown skin and white flesh that I have never seen in any
other places than in Spanish or Mexican markets.

So, would these be paleo?

Don.