diff --git a/swh/model/hypothesis_strategies.py b/swh/model/hypothesis_strategies.py
--- a/swh/model/hypothesis_strategies.py
+++ b/swh/model/hypothesis_strategies.py
@@ -143,7 +143,7 @@
 
 
 def branch_names():
-    return binary()
+    return binary(min_size=1)
 
 
 def branch_targets_object():