I'm south of you, so the zone is milder, but it's also hotter, longer. I've been putting together of list of plants and trees that fit
Geoff Lawton's basic guidelines for the first
permaculture pioneers. In deserts, he has said that using succulents to trap moisture is a good first step. We are using prickly pear. I believe the Eastern Prickly Pear is the one for your region, zone 4. Here is an article about it:
https://practicalselfreliance.com/cold-hardy-cactus/
Prickly pear are so easy to get going, just stick a pad in the ground and give it a little water through the summer. Here, we have to protect them from peccary (javelina), but they might not have predators in your area other than extremely desperate
rabbits?
Then the fastest growing, lowest water use, most tolerant legume I could find after poring through many New Mexico extension service lists is black locust. I found lists that had black locusts surviving with as low as 15 inches of water/year - whereas honey locust requires a lot more, most lists said 30 inches per year.
My next layer fast growing legume tree won't work for your region (it's Leuceana retusa, Golden Leadball tree, zone 8 minimum), so I suggest looking into my third level legume, False Indigo, Amorpha fruticosa. Many plants are called indigo, so be sure to look by the latin name.
False indigo (Amorpha fruticosa) is hardy to zone 4 (some sites say zone 2), a legume, and likes speckled shade. It grows wild here in the canyons of the Chihuahua Mountains. It can tolerate long periods of drought once established. This is an understory legume.
Fruitwood Nursery online sells affordable seedlings if you wanted to try a few. I've bought a lot from Fruitwood and find them a great permaculture resource.
https://fruitwoodnursery.com/starter-plugs-seedlings-and-rooted-cuttings/nut-and-leguminous-trees-in-starter-plugs/leguminous-trees-in-starter-plugs/false-indigo-bush-amorpha-fructicosa-seedling-plug-detail
For your curiosity sake - I am also growing Purple Locust (possibly a black locust hybrid with bristly locust), Redbud (a slow growing nitro fixer, but with lovely edible pods and I think hardy in your area), and more that are only for us here in zone 8a, like Palo Verdes, Albiza ("mimosa"), and Mesquites.
And one more resource - if you can, visit the Central Rocky Mountain Permaculture Institute.
https://crmpi.org/ My husband and I did some years ago, and got a tour from Jerome, the founder. They have figured out how to do high cold desert permaculture very effectively. Here is their nursery list -
https://crmpi.org/wp-content/uploads/2018/01/EdibleLandscapeNurseryatCRMPI_29Jan2018.pdf
If a plant is on that list, you can likely grow it in your area, too. You may be at a drier site, but what works for them you can figure out how to apply in your area. Look at the list and scroll down to "nitrogen fixers". You'll see they
sell Black Locust, Buffaloberry, Indigobush (I'm thinking this is Amorpha, but you might ask), Mountain Mahogany, Silverberry, Siberian Pea, and Speckled Alder. Some of those might be considered "invasive" in your region, just check first and decide what makes sense.
Some great points about black locust:
- The bark is toxic so mammals are less likely to eat it. In my area, without cages and tree tubes, everything will be eaten by rabbits, peccary or
deer. That said, I still use protection on the little locusts. This is a great advantage. Here where I am in the desert, some of our trees have to have trunk protection their whole lives, or rabbits will ring them. This is extremely inconvenient and expensive to maintain! So we try to plant trees that don't need this level of care, like those with toxic bark.
- The leaves are good animal forage, except for horses. Though many places in the US (extension services and such) will claim they are poisonous, that's not totally accurate. The bark is toxic, and that's the beauty of the plant when you are trying to get it to grow in a desert. If you look online you will find numerous studies done on the value of black locust as forage for livestock. Lots of studies on using black locust in goat silvopasture.
-This is a tree that, to quote Paul Wheaton, "Plays well with others". That's exactly what you want for your first level permaculture tree, a tree that other plants grow well around. It's even been studied as a partner plant for aiding the growth of black walnut in orchards. I have an experiment going with this right now, and my Arizona black walnuts do look better for the first time in three years.
- You can get seed for free in almost any desert town - check the trees around parking lots. Once I started paying attention to them, I look for trees with zero irrigation and collect seeds from those. Read up on how to start seeds as they can be a little tricky to stratify. Try different methods and see what works.
Here are some links to help explain what I've said above:
Cornell article on the many uses of Black Locust including silvopasture
https://smallfarms.cornell.edu/2018/01/black-locust/
Forage value of deciduous trees in Mediterranean goat silvopasture
https://www.researchgate.net/publication/226378644_Forage_value_of_Mediterranean_deciduous_woody_fodder_species_and_its_implication_to_management_of_silvo-pastoral_system_for_goats
Documented indigenous American uses:
http://naeb.brit.org/uses/species/3406/
Bark is toxic to horses and some other animals. Leaves used as forage for other livestock, especially sheep, goats, and rabbits.
Where to buy live Black Locust saplings very inexpensively in large amounts, Cold Stream Farm:
https://www.coldstreamfarm.net/product/black-locust-robinia-pseudoacacia/
A nursery to buy small amounts of black locust saplings affordably, Spencer Creek Nursery, a wonderful permaculture nursery out of Eugene, Oregon. (Also good friends of mine, for full disclosure!) I have other plants from them and they are doing very well:
https://spencercreeknursery.com/product/black-locust/